Русская Википедия:Разложение Холецкого

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

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

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

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

Алгоритм

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

<math>\begin{align}

l_{11} & = \sqrt{a_{11}}, \\ l_{j1} & = \frac{a_{j1}}{l_{11}}, \quad j \in [2, n], \\ l_{ii} & = \sqrt{a_{ii} - \sum_{p = 1}^{i - 1} l_{ip}^2}, \quad i \in [2, n], \\ l_{ji} & = \frac{1}{l_{ii}} \left (a_{ji} - \sum_{p = 1}^{i - 1} l_{ip} l_{jp} \right ), \quad i \in [2, n - 1], j \in [i + 1, n]. \end{align}</math>

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

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

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

<math>\begin{align}

l_{ii} & = \sqrt{a_{ii} - \sum_{p = 1}^{i - 1} l_{ip}l_{ip}^*}, \quad i \in [2, n], \\ l_{ji} & = \frac{1}{l_{ii}} \left (a_{ji} - \sum_{p = 1}^{i - 1} l_{ip} l_{jp}^* \right ), \quad i \in [2, n - 1], j \in [i + 1, n]. \end{align}</math>

Приложения

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

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

Разложение Холецкого также применяется в методах Монте-Карло для генерации коррелированных случайных величин. Пусть <math>X</math> — вектор из независимых стандартных нормальных случайных величин, а <math>\Sigma = LL^T</math> — желаемая ковариационная матрица. Тогда вектор <math>Y = LX</math> будет иметь многомерное нормальное распределение с нулевым математическим ожиданием и ковариационной матрицей <math>\Sigma</math>.[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].
  • В библиотеке JAMA языка программирования java.
  • В библиотеке Intel Data Analytics Acceleration Library присутствует алгоритмcholesky::Batch.

Примечания

Шаблон:Примечания

Шаблон:Wikibooks

Шаблон:Вектора и матрицы Шаблон:Методы решения СЛАУ