Разложение Холецкого

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

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

Разложение названо в честь французского математика польского происхождения Шаблон:Iw (1875—1918).

Алгоритм

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

$\begin{array}{cc}{l}_{11}& =\sqrt{a_{11}},\\ l_{j1}& =\frac{a_{j1}}{l_{11}},j\in [2,n],\\ l_{ii}& =\sqrt{a_{ii}-\sum _{p=1}^{i-1}{l}_{ip}^2},i\in [2,n],\\ l_{ji}& =\frac{1}{l_{ii}}(a_{ji}-\sum _{p=1}^{i-1}{l}_{ip}{l}_{jp}),i\in [2,n-1],j\in [i+1,n].\end{array}$

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

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

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

$\begin{array}{cc}{l}_{ii}& =\sqrt{a_{ii}-\sum _{p=1}^{i-1}{l}_{ip}{l}_{ip}^{*}},i\in [2,n],\\ l_{ji}& =\frac{1}{l_{ii}}(a_{ji}-\sum _{p=1}^{i-1}{l}_{ip}{l}_{jp}^{*}),i\in [2,n-1],j\in [i+1,n].\end{array}$

Приложения

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

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

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

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

• В 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.
• В библиотеке Apache Commons Math (начиная с версии 2.0) используется класс CholeskyDecomposition.
• В библиотеке Torch присутствует функция torch.potrf.
• В библиотеке JAMA языка программирования java.
• В библиотеке Intel Data Analytics Acceleration Library присутствует алгоритмcholesky::Batch.