Разложение Грама — Шарлье¶
Разложение Грама — Шарлье — метод факторизации симметричной положительно определённой матрицы, при котором исходная матрица представляется в виде произведения нижней треугольной матрицы, диагональной матрицы и транспонированной нижней треугольной матрицы. Разложение является частным случаем LU-разложения и тесно связано с методом Холецкого, однако отличается тем, что диагональные элементы треугольной матрицы не нормируются к единице, а выносятся в отдельную диагональную матрицу.
¶Определение
Для симметричной положительно определённой матрицы A размера n×n разложение Грама — Шарлье имеет вид:
A = L·D·Lᵀ,
где L — нижняя треугольная матрица с единичной диагональю, D — диагональная матрица с положительными элементами, Lᵀ — транспонированная матрица к L.
Такое представление существует и единственно для любой симметричной положительно определённой матрицы. В отличие от разложения Холецкого, где матрица представляется как A = R·Rᵀ (R — нижняя треугольная), разложение Грама — Шарлье позволяет избежать извлечения квадратных корней при вычислении диагональных элементов, что делает его вычислительно более устойчивым в некоторых случаях.
¶История
Метод назван в честь датского математика Йёргена Педерсена Грама (1850–1916) и французского математика Карла Шарлье (1862–1934). Грам известен прежде всего работами по методу наименьших квадратов и ортогонализации (процесс Грама — Шмидта). Шарлье, работавший в области математической статистики и астрономии, применял подобные разложения при обработке наблюдений. Само название «разложение Грама — Шарлье» закрепилось в вычислительной линейной алгебре в середине XX века, хотя отдельные элементы метода использовались ранее в рамках теории определителей и квадратичных форм.
¶Связь с другими разложениями
¶Разложение Холецкого
Если обозначить D = diag(d₁, d₂, …, dₙ), то разложение Холецкого получается из разложения Грама — Шарлье путём умножения столбцов матрицы L на квадратные корни из соответствующих диагональных элементов:
A = (L·√D)·(L·√D)ᵀ.
Обратный переход от разложения Холецкого A = R·Rᵀ к разложению Грама — Шарлье осуществляется делением каждого столбца матрицы R на его диагональный элемент.
¶LU-разложение
Разложение Грама — Шарлье является симметричной формой LU-разложения без выбора ведущего элемента. Для симметричных положительно определённых матриц оно всегда существует без перестановок строк.
¶Алгоритм вычисления
Разложение Грама — Шарлье может быть получено с помощью следующего рекуррентного алгоритма, аналогичного алгоритму Холецкого, но без извлечения квадратных корней:
Для j = 1, 2, …, n:
- Вычисляется вспомогательный вектор v = (v₁, v₂, …, vⱼ₋₁), где vᵢ = aᵢⱼ − Σₖ₌₁ⁱ⁻¹ lᵢₖ·dₖ·lⱼₖ.
- Диагональный элемент: dⱼ = aⱼⱼ − Σₖ₌₁ⱼ₋₁ lⱼₖ²·dₖ.
- Элементы матрицы L: lᵢⱼ = vᵢ / dⱼ для i > j.
Алгоритм требует примерно n³/3 операций умножения, что вдвое меньше, чем у стандартного LU-разложения, и сопоставимо с методом Холецкого.
¶Применение
Разложение Грама — Шарлье находит применение в следующих областях:
- Решение систем линейных уравнений: позволяет решать системы Ax = b за два шага (прямая и обратная подстановки), что особенно эффективно при многократном решении систем с одной и той же матрицей.
- Вычисление определителя: определитель матрицы A равен произведению диагональных элементов матрицы D, то есть det(A) = d₁·d₂·…·dₙ. Это свойство используется для оценки обусловленности матриц.
- Метод наименьших квадратов: применяется при решении нормальных уравнений, где матрица AᵀA является симметричной положительно определённой.
- Фильтр Калмана: в ковариационной форме фильтрации разложение используется для повышения численной устойчивости.
- Статистика: в теории линейных моделей разложение применяется для вычисления доверительных интервалов и проверки гипотез.
¶Достоинства и недостатки
К достоинствам разложения Грама — Шарлье относят:
- отсутствие операции извлечения квадратного корня, что ускоряет вычисления на некоторых архитектурах;
- возможность оценить обусловленность матрицы по величине диагональных элементов D;
- простота модификации при добавлении строк или столбцов к матрице.
Недостатком является чувствительность к ошибкам округления для плохо обусловленных матриц: в отличие от метода Холецкого, разложение Грама — Шарлье не гарантирует сохранения положительности диагональных элементов при вычислениях с плавающей точкой, если матрица близка к вырожденной.
¶Литература
- Голуб Дж., Ван Лоун Ч. Матричные вычисления. — М.: Мир, 1999.
- Уоткинс Д. С. Основы матричных вычислений. — М.: Бином, 2006.
- Higham N. J. Accuracy and Stability of Numerical Algorithms. — SIAM, 2002.