WikiSort.ru - Не сортированное

Разложе́ние Холе́цкого — представление симметричной положительно-определённой матрицы ${\displaystyle A}$ в виде ${\displaystyle A=LL^{T}}$ , где ${\displaystyle L}$ — нижняя треугольная матрица со строго положительными элементами на диагонали. Иногда разложение записывается в эквивалентной форме: ${\displaystyle A=U^{T}U}$ , где ${\displaystyle U=L^{T}}$ — верхняя треугольная матрица. Разложение Холецкого всегда существует и единственно для любой симметричной положительно-определённой матрицы.

Существует также обобщение этого разложения на случай комплекснозначных матриц. Если ${\displaystyle A}$ — положительно-определённая эрмитова матрица, то существует разложение ${\displaystyle A=LL^{*}}$ , где ${\displaystyle L}$ — нижняя треугольная матрица с положительными действительными элементами на диагонали, а ${\displaystyle L^{*}}$ — эрмитово-сопряжённая к ней матрица.

Разложение названо в честь французского математика Андре-Луи Шолески^[en] (1875—1918).

Алгоритм

Элементы матрицы ${\displaystyle L}$ можно вычислить, начиная с верхнего левого угла матрицы, по формулам

${\displaystyle L_{ii}={\sqrt {A_{ii}-\sum _{k=1}^{i-1}L_{ik}^{2}}},}$

${\displaystyle L_{ij}={\frac {1}{L_{jj}}}\left(A_{ij}-\sum _{k=1}^{j-1}L_{ik}L_{jk}\right),}$ если ${\displaystyle j<i.}$

Выражение под корнем всегда положительно, если ${\displaystyle A}$ — действительная положительно-определённая матрица.

Вычисление происходит сверху вниз, слева направо, т. е. сперва ${\displaystyle L_{ij}}$ , а затем ${\displaystyle L_{ii}}$ .

Для комплекснозначных эрмитовых матриц используются формулы

${\displaystyle L_{ii}={\sqrt {A_{ii}-\sum _{k=1}^{i-1}L_{ik}L_{ik}^{*}}},}$

${\displaystyle L_{ij}={\frac {1}{L_{jj}}}\left(A_{ij}-\sum _{k=1}^{j-1}L_{ik}L_{jk}^{*}\right),}$ если ${\displaystyle j<i.}$

Приложения

Это разложение может применяться для решения системы линейных уравнений ${\displaystyle Ax=b}$ , если матрица ${\displaystyle A}$ симметрична и положительно-определена. Такие матрицы часто возникают, например, при использовании метода наименьших квадратов и численном решении дифференциальных уравнений.

Выполнив разложение ${\displaystyle A=LL^{T}}$ , решение ${\displaystyle x}$ можно получить последовательным решением двух треугольных систем уравнений: ${\displaystyle Ly=b}$ и ${\displaystyle L^{T}x=y}$ . Такой способ решения иногда называется методом квадратных корней.^[1] По сравнению с более общими методами, такими как метод Гаусса или LU-разложение, он устойчивее численно и требует примерно вдвое меньше арифметических операций.^[2]

Разложение Холецкого также применяется в методах Монте-Карло для генерации коррелированных случайных величин. Пусть ${\displaystyle X}$  — вектор из независимых стандартных нормальных случайных величин, а ${\displaystyle \Sigma =LL^{T}}$  — желаемая ковариационная матрица. Тогда вектор ${\displaystyle Y=LX}$ будет иметь многомерное нормальное распределение с нулевым математическим ожиданием и ковариационной матрицей ${\displaystyle \Sigma }$ .^[3]

Реализация в математических пакетах программ

• В SAS используется функция ROOT(matrix), входящая в пакет SAS IML.
• В системах MATLAB, Octave, R разложение выполняется командой U = chol(A).
• В Maple и NumPy существует процедура cholesky в модуле linalg.
• В Mathematica используется процедура CholeskyDecomposition[A].
• В MathCAD для разложения используется функция cholesky(A)
• В GSL используется функция gsl_linalg_cholesky_decomp.
• В библиотеке от Google ceres-solver^[4].
• В библиотеке Apache Commons Math (начиная с версии 2.0) используется класс CholeskyDecomposition^[5].
• В библиотеке Torch присутствует функция torch.potrf^[6].
• В библиотеке Intel Data Analytics Acceleration Library присутствует алгоритмcholesky::Batch.

Примечания

Имеется викиучебник по теме
«Примеры реализации разложения Холецкого»