Главная
Новости
Строительство
Ремонт
Дизайн и интерьер




13.01.2022


29.12.2021


09.12.2021


09.12.2021


08.11.2021





Яндекс.Метрика





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

21.03.2022

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

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

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

Алгоритм

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

l 11 = a 11 , l j 1 = a j 1 l 11 , j ∈ [ 2 , n ] , l i i = a i i − ∑ p = 1 i − 1 l i p 2 , i ∈ [ 2 , n ] , l j i = 1 l i i ( a j i − ∑ p = 1 i − 1 l i p l j p ) , i ∈ [ 2 , n − 1 ] , j ∈ [ i + 1 , n ] . {displaystyle {egin{aligned}l_{11}&={sqrt {a_{11}}},l_{j1}&={frac {a_{j1}}{l_{11}}},quad jin [2,n],l_{ii}&={sqrt {a_{ii}-sum _{p=1}^{i-1}l_{ip}^{2}}},quad iin [2,n],l_{ji}&={frac {1}{l_{ii}}}left(a_{ji}-sum _{p=1}^{i-1}l_{ip}l_{jp} ight),quad iin [2,n-1],jin [i+1,n].end{aligned}}} Выражение под корнем всегда положительно, если A {displaystyle A} — действительная положительно определённая матрица.

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

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

l i i = a i i − ∑ p = 1 i − 1 l i p l i p ∗ , i ∈ [ 2 , n ] , l j i = 1 l i i ( a j i − ∑ p = 1 i − 1 l i p l j p ∗ ) , i ∈ [ 2 , n − 1 ] , j ∈ [ i + 1 , n ] . {displaystyle {egin{aligned}l_{ii}&={sqrt {a_{ii}-sum _{p=1}^{i-1}l_{ip}l_{ip}^{*}}},quad iin [2,n],l_{ji}&={frac {1}{l_{ii}}}left(a_{ji}-sum _{p=1}^{i-1}l_{ip}l_{jp}^{*} ight),quad iin [2,n-1],jin [i+1,n].end{aligned}}}

Приложения

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

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

Разложение Холецкого также применяется в методах Монте-Карло для генерации коррелированных случайных величин. Пусть X {displaystyle X} — вектор из независимых стандартных нормальных случайных величин, а Σ = L L T {displaystyle Sigma =LL^{T}} — желаемая ковариационная матрица. Тогда вектор Y = L X {displaystyle Y=LX} будет иметь многомерное нормальное распределение с нулевым математическим ожиданием и ковариационной матрицей Σ {displaystyle 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.