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

Разложение Холецкого (или метод квадратного корня) — это представление симметричной положительно определённой матрицы в виде произведения нижней треугольной матрицы и её транспонированной (сопряжённой) верхней треугольной матрицы. Является частным случаем LU-разложения, применяемым исключительно к матрицам, удовлетворяющим условию положительной определённости. Разложение названо в честь французского математика и геодезиста Андре-Луи Холецкого, который предложил этот метод в начале XX века для решения систем линейных уравнений в задачах геодезии.

¶История

Идея разложения симметричной матрицы на треугольные множители восходит к работам Гаусса, однако в явном виде алгоритм был сформулирован и опубликован в 1910 году французским офицером и математиком Андре-Луи Холецким (1875–1918). Холецкий работал в области геодезии и топографии, где требовалось решать большие системы линейных уравнений, возникающие при обработке геодезических измерений методом наименьших квадратов. Предложенный им метод позволял значительно сократить объём вычислений по сравнению с методом Гаусса.

После гибели Холецкого в Первую мировую войну его работа оставалась малоизвестной. В 1924 году метод был заново открыт и популяризирован французским математиком Бенуа, который опубликовал его описание в контексте решения систем линейных алгебраических уравнений. В англоязычной литературе разложение часто называют разложением Холецкого (Cholesky decomposition) или методом квадратного корня.

¶Математическая формулировка

Пусть A — симметричная (или эрмитова в комплексном случае) положительно определённая матрица размера n×n. Тогда существует единственная нижняя треугольная матрица L с положительными диагональными элементами, такая что:

A = L L^T

где L^T — транспонированная матрица (для действительных матриц) или сопряжённая (для комплексных). В комплексном случае разложение называется разложением Холецкого для эрмитовых матриц и записывается как A = L L^*.

Если матрица положительно полуопределена, разложение также существует, но матрица L может иметь нулевые диагональные элементы, и её столбцы, соответствующие нулевым диагональным элементам, могут быть выбраны произвольно.

¶Алгоритм вычисления

Элементы матрицы L вычисляются последовательно, начиная с первого столбца. Для i = 1, 2, ..., n:

1. Диагональный элемент:

l_ii = sqrt( a_ii - sum_{k=1}^{i-1} l_ik^2 )

1. Внедиагональные элементы (для j > i):

l_ji = ( a_ji - sum_{k=1}^{i-1} l_jk * l_ik ) / l_ii

Алгоритм требует выполнения примерно n^3/3 арифметических операций, что вдвое меньше, чем при стандартном LU-разложении (n^3/3 против 2n^3/3), поскольку используется симметрия матрицы.

¶Условия применимости

Разложение Холецкого существует и единственно тогда и только тогда, когда матрица A является симметричной (или эрмитовой) и положительно определённой. Положительная определённость означает, что все собственные значения матрицы строго положительны (или, эквивалентно, что все ведущие главные миноры положительны).

На практике разложение часто применяется к матрицам, которые являются положительно определёнными по построению, например, к матрицам Грама, матрицам ковариации, матрицам жёсткости в методе конечных элементов.

¶Варианты разложения

¶Разложение Холецкого для разреженных матриц

Для разреженных матриц (с большим количеством нулевых элементов) существуют специализированные алгоритмы, которые минимизируют заполнение (fill-in) — появление ненулевых элементов в матрице L на месте нулей в исходной матрице. Используются методы перестановок строк и столбцов (например, обратное упорядочение Катхилла-Макки) для уменьшения ширины ленты или профиля матрицы.

¶LDL^T-разложение

Вариант разложения, в котором матрица A представляется как L D L^T, где L — нижняя треугольная матрица с единичной диагональю, а D — диагональная матрица. Этот вариант позволяет избежать извлечения квадратного корня и работает для симметричных матриц, не обязательно положительно определённых (например, для индефинитных матриц). В этом случае разложение называется LDL^T-разложением.

¶Разложение Холецкого в комплексном случае

Для эрмитовых положительно определённых матриц применяется комплексное разложение Холецкого: A = L L^, где L — нижняя треугольная матрица с комплексными элементами, а L^ — эрмитово-сопряжённая матрица. Алгоритм аналогичен действительному случаю, но с использованием комплексных операций.

¶Применение

¶Решение систем линейных уравнений

Основное применение разложения Холецкого — решение систем линейных уравнений вида A x = b, где A — симметричная положительно определённая матрица. Решение выполняется в два этапа:

1. Прямая подстановка: решается система L y = b относительно y.
2. Обратная подстановка: решается система L^T x = y относительно x.

Этот подход в два раза быстрее LU-разложения для симметричных матриц и численно более устойчив.

¶Метод наименьших квадратов

В задачах аппроксимации данных методом наименьших квадратов возникает система нормальных уравнений A^T A x = A^T b. Матрица A^T A является симметричной положительно определённой (если столбцы A линейно независимы), поэтому к ней применимо разложение Холецкого. Однако на практике для больших разреженных задач часто предпочитают QR-разложение или сингулярное разложение (SVD) из-за лучшей численной устойчивости.

¶Обращение матриц

Разложение Холецкого может использоваться для вычисления обратной матрицы, хотя это редко является основной целью. Обратная матрица вычисляется как A^{-1} = (L^{-1})^T L^{-1}, где L^{-1} — обратная к нижней треугольной матрице, которая легко вычисляется.

¶Вычисление определителя

Определитель положительно определённой матрицы может быть вычислен как квадрат произведения диагональных элементов матрицы L:

det(A) = (∏_{i=1}^{n} l_ii)^2

Это позволяет избежать прямого вычисления определителя, что особенно полезно для больших матриц.

¶Метод Монте-Карло и моделирование

Разложение Холецкого используется для генерации многомерных нормально распределённых случайных векторов с заданной ковариационной матрицей Σ. Если Σ = L L^T, то вектор x = L z, где z — вектор независимых стандартных нормальных случайных величин, будет иметь ковариацию Σ.

¶Фильтр Калмана

В задачах оценивания состояния динамических систем (фильтр Калмана) разложение Холецкого применяется для численно устойчивого обновления ковариационных матриц. Используется так называемый квадратно-корневой фильтр Калмана, в котором ковариационная матрица хранится и обновляется в виде разложения Холецкого, что гарантирует её положительную определённость.

¶Машинное обучение и статистика

В гауссовских процессах, методах опорных векторов, линейной регрессии и других статистических моделях разложение Холецкого используется для решения систем линейных уравнений, возникающих при обучении моделей. В частности, в гауссовских процессах требуется решать системы с матрицами ковариации, которые всегда положительно определённы.

¶Численная устойчивость

Разложение Холецкого является численно устойчивым для положительно определённых матриц. Ошибки округления не приводят к значительному искажению результата, если матрица хорошо обусловлена. Для плохо обусловленных матриц (с большим числом обусловленности) может наблюдаться потеря точности, однако в целом метод считается более устойчивым, чем стандартное LU-разложение без выбора ведущего элемента.

Для улучшения численной устойчивости иногда применяется модифицированное разложение Холецкого, которое позволяет обрабатывать матрицы, близкие к вырожденным, добавляя малую положительную величину к диагональным элементам (регуляризация).

¶Ограничения

Основное ограничение разложения Холецкого — требование симметричности и положительной определённости матрицы. Для несимметричных или индефинитных матриц оно неприменимо. В таких случаях используются другие методы: LU-разложение, QR-разложение, сингулярное разложение.

Для очень больших разреженных матриц (размером более 10^6) прямое разложение Холецкого может потребовать слишком много памяти из-за заполнения. В таких ситуациях применяются итерационные методы (например, метод сопряжённых градиентов), которые не требуют явного разложения матрицы.

¶Пример

Рассмотрим симметричную положительно определённую матрицу 3×3:

A = [[4, 2, 2], [2, 5, 3], [2, 3, 6]]

Вычислим разложение Холецкого A = L L^T.

1. l_11 = sqrt(4) = 2
2. l_21 = 2 / 2 = 1
3. l_31 = 2 / 2 = 1
4. l_22 = sqrt(5 - 1^2) = sqrt(4) = 2
5. l_32 = (3 - 1*1) / 2 = 2 / 2 = 1
6. l_33 = sqrt(6 - 1^2 - 1^2) = sqrt(4) = 2

Таким образом:

L = [[2, 0, 0], [1, 2, 0], [1, 1, 2]]

Проверка: L L^T = [[4, 2, 2], [2, 5, 3], [2, 3, 6]] = A.

¶Реализации в программном обеспечении

Разложение Холецкого реализовано во всех основных библиотеках линейной алгебры:

• LAPACK — функция DPOTRF (для действительных матриц) и ZPOTRF (для комплексных).
• BLAS — низкоуровневые операции, используемые в LAPACK.
• MATLAB — функция chol.
• Python (NumPy/SciPy) — numpy.linalg.cholesky и scipy.linalg.cholesky.
• Julia — функция cholesky.
• R — функция chol.
• C++ (Eigen) — класс LLT.
• CUDA — библиотека cuSOLVER предоставляет функцию cusolverDnDpotrf.

¶Интересные факты

• Разложение Холецкого является основой для метода квадратного корня, который в советской литературе часто называли «методом квадратного корня» для решения систем линейных уравнений с симметричной матрицей.
• В некоторых источниках разложение Холецкого называют «разложением Холецкого-Банашевича» или «методом Холецкого-Банашевича», поскольку польский математик Тадеуш Банашевич независимо разработал аналогичный метод в 1938 году.
• Алгоритм разложения Холецкого может быть распараллелен, что позволяет эффективно использовать его на многопроцессорных системах и графических ускорителях (GPU).

¶Источники

• Голуб Дж., Ван Лоун Ч. Матричные вычисления. — М.: Мир, 1999.
• Деммель Дж. Вычислительная линейная алгебра. — М.: Мир, 2001.
• Хорн Р., Джонсон Ч. Матричный анализ. — М.: Мир, 1989.
• Benoit, C. (1924). "Sur la méthode de résolution des équations normales de M. Cholesky". Bulletin Géodésique, 2(1), 67–77.
• Higham, N. J. (2002). Accuracy and Stability of Numerical Algorithms. SIAM.