Разложе́ние Холе́цкого — представление симметричной положительно-определённой матрицы A{displaystyle A} в виде A=LLT{displaystyle A=LL^{T}}, где L{displaystyle L} — нижняя треугольная матрица со строго положительными элементами на диагонали. Иногда разложение записывается в эквивалентной форме: A=UTU{displaystyle A=U^{T}U}, где U=LT{displaystyle U=L^{T}} — верхняя треугольная матрица. Разложение Холецкого всегда существует и единственно для любой симметричной положительно-определённой матрицы.
Существует также обобщение этого разложения на случай комплекснозначных матриц. Если A{displaystyle A} — положительно-определённая эрмитова матрица, то существует разложение A=LL∗{displaystyle !A=LL^{*}}, где L{displaystyle L} — нижняя треугольная матрица с положительными действительными элементами на диагонали, а L∗{displaystyle !L^{*}} — эрмитово-сопряжённая к ней матрица.
Разложение названо в честь французского математика Андре-Луи Холецкого (1875-1918).
Содержание
Алгоритм
Элементы матрицы L{displaystyle L}
можно вычислить, начиная с верхнего левого угла матрицы, по формулам:
- Lii=Aii−∑k=1i−1Lik2{displaystyle L_{ii}={sqrt {A_{ii}-sum _{k=1}^{i-1}L_{ik}^{2}}}}
- Lij=1Ljj(Aij−∑k=1j−1LikLjk){displaystyle L_{ij}={frac {1}{L_{jj}}}left(A_{ij}-sum _{k=1}^{j-1}L_{ik}L_{jk}right)} , если j<i{displaystyle j<i} .
Выражение под корнем всегда положительно, если A{displaystyle A}
— действительная положительно-определённая матрица.
Вычисление происходит сверху вниз, справа налево, т.е. сперва Lii{displaystyle L_{ii}}
, а затем Lij{displaystyle L_{ij}} .
Для комплекснозначных эрмитовых матриц используются формулы:
- Lii=Aii−∑k=1i−1LikLik∗{displaystyle L_{ii}={sqrt {A_{ii}-sum _{k=1}^{i-1}L_{ik}L_{ik}^{*}}}}
- Lij=1Ljj(Aij−∑k=1j−1LikLjk∗){displaystyle L_{ij}={frac {1}{L_{jj}}}left(A_{ij}-sum _{k=1}^{j-1}L_{ik}L_{jk}^{*}right)} , если j<i{displaystyle j<i} .
Приложения
Это разложение может применяться для решения системы линейных уравнений Ax=b{displaystyle Ax=b}
, если матрица A{displaystyle A} симметрична и положительно-определена. Такие матрицы часто возникают, например, при использовании метода наименьших квадратов и численном решении дифференциальных уравнений.
Выполнив разложение A=LLT{displaystyle A=LL^{T}}
, решение x{displaystyle x} получается последовательным решением двух треугольных систем уравнений: Ly=b{displaystyle Ly=b} и LTx=y{displaystyle L^{T}x=y} . Такой способ решения иногда называется методом квадратных корней.[1] По сравнению с более общими методами, такими как метод Гаусса или LU-разложение, он устойчивее численно и требует примерно вдвое меньше арифметических операций. [2]
Разложение Холецкого также применяется в методах Монте-Карло для генерации коррелированных случайных величин. Пусть X{displaystyle X}
— вектор из независимых стандартных нормальных случайных величин, а Σ=LLT{displaystyle Sigma =LL^{T}} — желаемая ковариационная матрица. Тогда вектор Y=LX{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.
Примечания
- ↑ Вержбицкий В. М. Основы численных методов. — М.: Высшая школа, 2009. — 840 с. — ISBN 9785060061239.
- ↑ William H. Press, Saul A. Teukolsky, William T. Vetterling, Brian P. Flannery. 2.9 Cholesky Decomposition // Numerical Recipes in C. — 2nd edition. — Cambridge: Cambridge University Press. — ISBN 0-521-43108-5.
- ↑ Martin Haugh. Generating Correlated Random Variables.