Меню Главная Случайная статья Настройки Разложение Холецкого Материал из https://ru.wikipedia.org Разложение Холецкого (метод квадратного корня) — представление симметричной положительно определённой матрицы ${\displaystyle A}$ в виде ${\displaystyle A=LL^{T}}$, где ${\displaystyle L}$ — нижняя треугольная матрица со строго положительными элементами на диагонали. Иногда разложение записывается в эквивалентной форме: ${\displaystyle A=U^{T}U}$, где ${\displaystyle U=L^{T}}$ — верхняя треугольная матрица. Разложение Холецкого всегда существует и единственно для любой симметричной положительно определённой матрицы. Существует также обобщение этого разложения на случай комплекснозначных матриц. Если ${\displaystyle A}$ — положительно определённая эрмитова матрица, то существует разложение ${\displaystyle A=LL^{*}}$, где ${\displaystyle L}$ — нижняя треугольная матрица с положительными действительными элементами на диагонали, а ${\displaystyle L^{*}}$ — эрмитово-сопряжённая к ней матрица. Разложение названо в честь французского математика польского происхождения Андре-Луи Шолески[англ.] (1875—1918). Содержание 1 Алгоритм 2 Приложения 3 Реализация в математических пакетах программ 4 Примечания Алгоритм Элементы матрицы ${\displaystyle L}$ можно вычислить, начиная с верхнего левого угла матрицы, по формулам ${\displaystyle {\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}}}$ Выражение под корнем всегда положительно, если ${\displaystyle A}$ — действительная положительно определённая матрица. Вычисление происходит сверху вниз, слева направо, т. е. сперва ${\displaystyle L_{ij}}$, а затем ${\displaystyle L_{ii}}$. Для комплекснозначных эрмитовых матриц используются формулы ${\displaystyle {\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}}}$ Приложения Это разложение может применяться для решения системы линейных уравнений ${\displaystyle Ax=b}$, если матрица ${\displaystyle A}$ симметрична и положительно определена. Такие матрицы часто возникают, например, при использовании метода наименьших квадратов и численном решении дифференциальных уравнений. Выполнив разложение ${\displaystyle A=LL^{T}}$, решение ${\displaystyle x}$ можно получить последовательным решением двух треугольных систем уравнений: ${\displaystyle Ly=b}$ и ${\displaystyle L^{T}x=y}$. Такой способ решения иногда называется методом квадратных корней.[1] По сравнению с более общими методами, такими как метод Гаусса или LU-разложение, он устойчивее численно и требует примерно вдвое меньше арифметических операций.[2] Разложение Холецкого также применяется в методах Монте-Карло для генерации коррелированных случайных величин. Пусть ${\displaystyle X}$ — вектор из независимых стандартных нормальных случайных величин, а ${\displaystyle \Sigma =LL^{T}}$ — желаемая ковариационная матрица. Тогда вектор ${\displaystyle Y=LX}$ будет иметь многомерное нормальное распределение с нулевым математическим ожиданием и ковариационной матрицей ${\displaystyle \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. Martin Haugh. Generating Correlated Random Variables Архивировано 5 января 2012 года.. Ceres Solver — A Large Scale Non-linear Optimization Library  (неопр.). Дата обращения: 7 сентября 2017. Архивировано из оригинала 2 сентября 2017 года. CholeskyDecomposition Архивная копия от 7 ноября 2017 на Wayback Machine. torch.potrf Архивная копия от 20 августа 2017 на Wayback Machine.