Все формулы РФ

Математика / Матрицы, определители

Холѐцкое разложение нормальных уравнений

Разложение Холецкого применяет положительную определенность A^T A и заменяет решение нормальных уравнений двумя треугольными системами.

Опубликовано: Обновлено:

Линейная алгебра

Формула

$$A^\top A = LL^\top,\; L y=A^\top b,\; L^\top \hat x = y.$$
table Шаги Холецкого для МНК

A^\top A разлагается и решается двумя треугольными системами.

Факторизация снижает потребность в обратной матрице.

Обозначения

$L$
нижнетреугольный фактор Холецкого, n×n матрица
$y$
промежуточный вектор, вектор
$\hat x$
решение МНК, вектор

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

  • A^\top A симметрична и положительно определена.
  • A имеет полный столбцовый ранг.
  • Размеры задачи допускают факторизацию.

Ограничения

  • Если A плохо обусловлена, число обусловленности сохраняется в нормальных уравнениях.
  • Точный разбор не применяют к разреженным очень крупным системам без модификаций.
  • Для ранга-дефицитных случаев нужна модификация или псевдообратная.

Подробное объяснение

Матрица A^T A всегда симметрична и неотрицательно определена. При полном столбцовом ранге она положительно определена, а значит допускает разложение Холецкого A^T A = LL^T или R^T R. Нормальная система превращается в LL^T x = A^T b, которую решают в два этапа: сначала прямой подстановкой находят y из Ly=A^T b, затем обратной подстановкой находят x из L^T x=y. Такой путь экономит вычисления по сравнению с общим LU-разложением и сохраняет симметрию системы, но унаследует главный недостаток нормальных уравнений: ухудшение обусловленности. Важно видеть эту формулу в общей цепочке: исходные данные задают матрицу наблюдений A и правую часть b, затем выбирается способ приблизить b в пространстве столбцов A. Холѐцкое разложение нормальных уравнений отвечает за прикладная задача наименьших квадратов, поэтому она не существует отдельно от ранга матрицы, ортогональности остатка и устойчивости вычислений. Если столбцы A хорошо различимы и данные имеют умеренный шум, нормальные уравнения могут дать понятный ручной путь. Если столбцы почти зависимы, лучше пользоваться QR или SVD, потому что они меньше усиливают ошибки округления. После вычисления результата полезно проверить три вещи: размерности всех матриц, величину остатка и связь с соседними формулами раздела. Такой подход превращает формулу из механической записи в рабочий инструмент анализа данных, регрессии, инженерных измерений и численной математики.

Как пользоваться формулой

  1. Вычислите A^\top A и проверьте SPD.
  2. Найдите L в разложении A^\top A=LL^\top.
  3. Решите L y=A^\top b и затем L^\top x=y.
  4. Проверьте оптимальность через остаток: он должен быть ортогонален столбцам A или, в QR-записи, давать Q^T r=0.

Историческая справка

Андре-Луи Холецкий разработал метод разложения симметричных положительно определенных матриц в начале XX века для геодезических вычислений. После публикации метод быстро стал стандартным инструментом численной линейной алгебры, особенно в задачах МНК, статистики и инженерных расчетов. В XX веке эта тема стала частью стандартной численной линейной алгебры: вычислительные машины сделали возможной массовую обработку переопределенных систем, но одновременно показали, что алгебраически эквивалентные формулы могут вести себя по-разному из-за округления. Поэтому учебники начали разделять теоретический вывод МНК, геометрическое объяснение через проекции и практические алгоритмы QR, Холецкого и SVD. Такой исторический сдвиг важен для пользователя: он объясняет, почему на странице рядом стоят не только “красивая формула”, но и условия применимости, ограничения и типичные ошибки.

Историческая линия формулы

Разложение названо в честь Андре-Луи Холецкого; его применение к нормальным уравнениям является естественным следствием положительной определенности матрицы A^T A при полном ранге. Современная запись является результатом развития метода наименьших квадратов, матричной алгебры и численных методов; поэтому атрибуция здесь распределенная: классические идеи связаны с Гауссом и Лежандром, а устойчивые вычислительные формы — с более поздней численной линейной алгеброй.

Пример

Если A^T A=[[3,3],[3,5]], то можно взять разложение LL^T, где L=[[sqrt(3),0],[sqrt(3),sqrt(2)]]. Сначала решают L y = A^T b, затем L^T x = y. Для A^T b=(5,6)^T первый шаг дает y1=5/sqrt(3), y2=(6-5)/sqrt(2)=1/sqrt(2). Второй шаг возвращает x=(7/6,1/2)^T. Практически это означает, что вместо общего метода для произвольной матрицы используется структура симметрии и положительной определенности. Дополнительная проверка: после получения численного ответа всегда подставь найденный вектор обратно в Ax, вычисли остаток r=b-Ax и сравни его норму с нормой остатка для соседнего пробного решения. Если речь идет о МНК, маленькое изменение параметров не должно уменьшать критерий; если оно уменьшает сумму квадратов, значит нормальные уравнения, QR-шаг или ручное исключение выполнены с ошибкой. Такой контроль особенно полезен в учебных задачах, где итоговое число легко получить, но трудно заметить неверный знак или перепутанный порядок умножения.

Частая ошибка

Нельзя применять Холецкого к любой матрице нормальных уравнений без проверки ранга и положительной определенности. Если столбцы A зависимы, A^T A будет вырождена. Если задача плохо обусловлена, метод может формально работать, но выдавать численно ненадежный результат.

Практика

Задачи с решением

Один шаг факторизации

Условие. C=A^\top A=\begin{bmatrix}4&3\\3&10\end{bmatrix},\ A^\top b=(12,11)^\top.

Решение. L=\begin{bmatrix}2&0\\1.5&\sqrt7\end{bmatrix},\ y=(6,\sqrt7)^\top,\ \hat x=(1,1)^\top.

Ответ. Решение МНК: \hat x=(1,1)^\top.

Диагональный случай

Условие. C=\begin{bmatrix}9&0\\0&4\end{bmatrix},\ A^\top b=(9,8)^\top.

Решение. L=\begin{bmatrix}3&0\\0&2\end{bmatrix},\ y=(3,4)^\top,\ \hat x=(1,2)^\top.

Ответ. x̂=(1,2)^\top.

Дополнительные источники

  • Golub, Van Loan, Matrix Computations, Ch. 4
  • Nocedal, Numerical Optimization

Связанные формулы

Математика

Число обусловленности для задачи МНК

$\kappa_2(A^\top A)=\frac{\sigma_{\max}^2}{\sigma_{\min}^2}=\kappa_2(A)^2.$

При переходе к нормальным уравнениям число обусловленности фактически возводится в квадрат, поэтому ошибки округления и шум в данных могут заметно усилиться.

Математика

Обратная матрица 2x2

$A^{-1}=\frac{1}{ad-bc}\begin{pmatrix}d&-b\\-c&a\end{pmatrix}$

Обратная матрица 2x2 существует только при ненулевом определителе. Она обращает действие исходной матрицы: A^{-1}A = I, то есть возвращает исходный вектор.