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

Эта статья находится на начальном уровне проработки, в одной из её версий выборочно используется текст из источника, распространяемого под свободной лицензией
Материал из энциклопедии Руниверсалис

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

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

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

Алгоритм

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

[math]\displaystyle{ \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]\displaystyle{ A }[/math] — действительная положительно определённая матрица.

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

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

[math]\displaystyle{ \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]\displaystyle{ Ax = b }[/math], если матрица [math]\displaystyle{ A }[/math] симметрична и положительно определена. Такие матрицы часто возникают, например, при использовании метода наименьших квадратов и численном решении дифференциальных уравнений.

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

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

Примечания

  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 Архивная копия от 7 ноября 2017 на Wayback Machine.
  6. ↑ torch.potrf Архивная копия от 20 августа 2017 на Wayback Machine.


Источник — https://xn--h1ajim.xn--p1ai/index.php?title=Разложение_Холецкого&oldid=11145914