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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

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

Алгоритм[править | править вики-текст]

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

L_{ii} = \sqrt{A_{ii} - \sum_{k=1}^{i-1} L_{ik}^2}
L_{ij} = \frac{1}{L_{jj}} \left(A_{ij} - \sum_{k=1}^{j-1} L_{ik} L_{jk} \right), если j < i.

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

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

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

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

Приложения[править | править вики-текст]

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

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

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

Реализация в математических пакетах программ[править | править вики-текст]

  • В SAS используется функция ROOT( matrix ), входящая в пакет SAS IML.
  • В системах MATLAB, Octave, R разложение выполняется командой U = chol(A).
  • В Maple и NumPy существует процедура cholesky в модуле linalg.
  • В Mathematica используется процедура CholeskyDecomposition[A].
  • В GSL используется функция gsl_linalg_cholesky_decomp.
  • В библиотеке от Google ceres-solver.

Примечания[править | править вики-текст]

  1. Вержбицкий В. М. Основы численных методов. — М.: Высшая школа, 2009. — 840 с. — ISBN 9785060061239.
  2. 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.
  3. Martin Haugh. Generating Correlated Random Variables.