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

LDL-разложение (также известное как LDL-разложение Холецкого или LDLᵀ-разложение) — это вид факторизации (разложения) матрицы, при котором исходная симметричная матрица A представляется в виде произведения трёх матриц: A = LDLᵀ, где L — нижняя треугольная матрица с единицами на главной диагонали, D — диагональная матрица, а Lᵀ — транспонированная матрица L. Данное разложение является вариантом LU-разложения, адаптированным для симметричных матриц, и тесно связано с разложением Холецкого, от которого отличается отсутствием операции извлечения квадратного корня.

¶Определение и математическая формулировка

Пусть A — симметричная матрица размера n×n, то есть A = Aᵀ. LDL-разложение существует, если все главные миноры матрицы A отличны от нуля (матрица является невырожденной и имеет положительно определённые главные подматрицы). В этом случае существует единственное представление:

A = L D Lᵀ,

где:

• L — нижняя треугольная матрица с единичной диагональю: lᵢᵢ = 1, lᵢⱼ = 0 для j > i;
• D — диагональная матрица с элементами dᵢᵢ на главной диагонали;
• Lᵀ — верхняя треугольная матрица, являющаяся транспонированной к L.

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

dᵢᵢ = aᵢᵢ − Σₖ₌₁ⁱ⁻¹ (lᵢₖ)² · dₖₖ

lⱼᵢ = (aⱼᵢ − Σₖ₌₁ⁱ⁻¹ lⱼₖ · lᵢₖ · dₖₖ) / dᵢᵢ, для j > i

Здесь aᵢⱼ — элементы исходной матрицы A. Вычисления требуют порядка n³/3 арифметических операций, что сопоставимо с разложением Холецкого.

¶Связь с разложением Холецкого

Разложение Холецкого (A = G Gᵀ, где G — нижняя треугольная матрица) и LDL-разложение математически эквивалентны для положительно определённых матриц. Если матрица A положительно определена, то все элементы dᵢᵢ в LDL-разложении положительны, и можно записать:

G = L · √D,

где √D — диагональная матрица, элементы которой равны √dᵢᵢ. Таким образом, LDL-разложение является обобщением разложения Холецкого на случай, когда извлечение квадратного корня нежелательно или невозможно (например, при работе с рациональными числами или при численной нестабильности).

Основное преимущество LDL-разложения перед разложением Холецкого — отсутствие операции извлечения квадратного корня, что позволяет:

• работать с матрицами, имеющими неположительные собственные значения (например, в задачах оптимизации с ограничениями);
• избежать потери точности при вычислении квадратных корней в условиях ограниченной разрядности чисел;
• упростить реализацию в целочисленной арифметике.

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

Существует несколько вариантов алгоритма LDL-разложения. Наиболее распространённый — компактная схема, при которой элементы матриц L и D вычисляются непосредственно, без промежуточного хранения полной матрицы A. Алгоритм работает «на месте»: исходная матрица A постепенно заменяется элементами L и D.

¶Псевдокод (для симметричной матрицы A размера n)

``` for i = 1 to n: // Вычисление d[i][i] sum = a[i][i] for k = 1 to i-1: sum = sum - a[i][k] a[i][k] a[k][k] a[i][i] = sum // теперь a[i][i] = d[i][i]

// Вычисление l[j][i] для j > i for j = i+1 to n: sum = a[j][i] for k = 1 to i-1: sum = sum - a[j][k] a[i][k] a[k][k] a[j][i] = sum / a[i][i] // теперь a[j][i] = l[j][i] a[i][j] = a[j][i] // для симметрии ```

После завершения алгоритма нижняя треугольная часть матрицы A (включая диагональ) содержит элементы L и D: на диагонали — dᵢᵢ, ниже диагонали — lⱼᵢ.

¶Применение

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

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

1. Разложение: A = L D Lᵀ.
2. Прямая подстановка: решение L y = b (находим y).
3. Диагональное масштабирование: решение D z = y (находим z).
4. Обратная подстановка: решение Lᵀ x = z (находим x).

Общая вычислительная сложность — O(n³) для разложения и O(n²) для каждой подстановки.

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

Определитель матрицы A равен произведению диагональных элементов D:

det(A) = d₁₁ · d₂₂ · … · dₙₙ.

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

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

LDL-разложение может быть использовано для вычисления обратной матрицы A⁻¹. После разложения обратная матрица находится как A⁻¹ = (L⁻¹)ᵀ D⁻¹ L⁻¹, где L⁻¹ — обратная к нижней треугольной матрице (вычисляется за O(n²) операций), а D⁻¹ — диагональная матрица с элементами 1/dᵢᵢ.

¶Численные методы оптимизации

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

¶Криптография и целочисленная арифметика

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

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

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

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

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

¶История

Метод LDL-разложения был впервые описан в 1924 году французским математиком Андре-Луи Шолески (André-Louis Cholesky) в контексте разложения, ныне известного как разложение Холецкого. Однако сам Шолески использовал форму без квадратного корня, то есть фактически LDL-разложение. Впоследствии, в 1940-х годах, американский математик Джордж Форсайт (George Forsythe) и другие исследователи формализовали LDL-разложение как самостоятельный метод. В современной литературе термин «LDL-разложение» закрепился в 1960-х годах с развитием вычислительной линейной алгебры.

¶Источники

• Golub, G. H., & Van Loan, C. F. (2013). Matrix Computations (4th ed.). Johns Hopkins University Press.
• Trefethen, L. N., & Bau, D. (1997). Numerical Linear Algebra. SIAM.
• Demmel, J. W. (1997). Applied Numerical Linear Algebra. SIAM.
• Форсайт, Дж., Молер, К. (1967). Численное решение систем линейных алгебраических уравнений. Мир.