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

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

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

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

Алгоритм

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

{\begin{aligned}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{aligned}}

Выражение под корнем всегда положительно, если

A

— действительная положительно определённая матрица.

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

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

{\begin{aligned}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{aligned}}

Приложения

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

Выполнив разложение $A=LL^{T}$ , решение $x$ можно получить последовательным решением двух треугольных систем уравнений: $Ly=b$ и $L^{T}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].
В 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.

Примечания

Вержбицкий В. М. Основы численных методов. — М.: Высшая школа, 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 Архивировано 5 января 2012 года..
Ceres Solver — A Large Scale Non-linear Optimization Library (неопр.) (недоступная ссылка). Дата обращения: 7 сентября 2017. Архивировано 2 сентября 2017 года.
CholeskyDecomposition.
torch.potrf.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[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 Архивировано 5 января 2012 года..

[4] Ceres Solver — A Large Scale Non-linear Optimization Library (неопр.) (недоступная ссылка). Дата обращения: 7 сентября 2017. Архивировано 2 сентября 2017 года.

[5] CholeskyDecomposition.

[6] torch.potrf.

Методы решения СЛАУ
Прямые методы	Матричный метод Метод Гаусса Метод Гаусса — Жордана Метод Крамера LU-разложение Разложение Холецкого Метод прогонки
Итерационные методы	Метод Якоби Метод Гаусса — Зейделя Метод итерации Метод релаксации Метод сопряженных градиентов Метод бисопряжённых градиентов Стабилизированный метод бисопряжённых градиентов
Общее	Обратная матрица Проекционные методы решения СЛАУ Предобуславливание