EssayAI
Блог
Блог
Математика и алгоритмы

Разложение Холецкого: условия, формулы и пример

8 ноября 2026Время чтения: 8 минут
#разложение холецкого#положительно определённая матрица#матрицы#линейные системы#численные методы
Разложение Холецкого: условия, формулы и пример

Разложение Холецкого представляет симметричную положительно определённую матрицу как произведение нижней треугольной матрицы на её транспонированную: A=LLTA=LL^T. Это помогает решать системы линейных уравнений и вычислять определитель, используя только один треугольный множитель. Но симметрии для метода недостаточно: прежде нужно проверить знак квадратичной формы. В калькуляторе можно менять один элемент матрицы и наблюдать, как из него получается последний диагональный элемент LL.

Идея: матрица как произведение двух треугольников

Пусть AA - действительная квадратная матрица. Если она симметрична и положительно определена, существует единственная нижняя треугольная матрица LL с положительными диагональными элементами, для которой A=LLTA=LL^T. Например, в двух измерениях запись выглядит так:

(abbc)=(l110l21l22)(l11l210l22).\begin{pmatrix}a&b\\b&c\end{pmatrix}= \begin{pmatrix}l_{11}&0\\l_{21}&l_{22}\end{pmatrix} \begin{pmatrix}l_{11}&l_{21}\\0&l_{22}\end{pmatrix}.

Верхний множитель не ищут отдельно: его получают транспонированием нижнего. Требование положительной диагонали фиксирует знаки и обеспечивает единственность. Иногда используют эквивалентную запись A=UTUA=U^TU с верхней треугольной матрицей U=LTU=L^T. Именно обе эти формы поддерживает процедура DPOTRF библиотеки LAPACK.

Движение ниже показывает конкретную зависимость: при увеличении tt в матрице A(t)=(422t)A(t)=\left(\begin{smallmatrix}4&2\\2&t\end{smallmatrix}\right) последний диагональный элемент LL растёт как t−1\sqrt{t-1}. Полоса затем возвращается к исходной длине.

При изменении t золотая полоса показывает величину последнего диагонального элемента множителя L; когда t возвращается, полоса снова принимает исходную длину.

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

Когда разложение существует

Матрица положительно определена, если для любого ненулевого действительного столбца xx выполняется xTAx>0x^TAx>0. Для симметричной матрицы это равносильно положительности всех её собственных значений. Другой удобный ручной тест - критерий Сильвестра: все угловые главные миноры должны быть положительными. Это определители верхних левых блоков размеров 1,2,…,n1,2,\ldots,n.

Для семейства из калькулятора первые два минора равны 44 и 4t−44t-4. Значит, условие здесь сводится к t>1t>1. В доступном диапазоне 1,25≤t≤51{,}25\le t\le5 оно выполняется; при t=1t=1 матрица уже вырождена, а при t<1t<1 определитель отрицателен. Положительные элементы на диагонали сами по себе ничего не гарантируют: например, (1221)\left(\begin{smallmatrix}1&2\\2&1\end{smallmatrix}\right) симметрична, но её определитель равен −3-3.

Условия можно связать с геометрией квадратичной формы. Если существует множитель с положительной диагональю, он обратим. Для любого ненулевого вектора после умножения на транспонированный множитель результат остаётся ненулевым. Поэтому квадратичная форма равна квадрату его длины и строго положительна. Положительная определённость необходима для такого представления. Обратное утверждение гарантирует существование множителя и объясняет, почему все требуемые остатки оказываются положительными.

При проверке критерия Сильвестра важно выбирать именно верхние левые блоки. Например, у матрицы третьего порядка сначала проверяют первый элемент, затем определитель блока из первых двух строк и столбцов и лишь после этого определитель всей матрицы. Другие главные миноры тоже положительны для положительно определённой матрицы, но для этого критерия достаточно указанной последовательности. Этот тест применяют после проверки симметрии.

Проверка условия не просто формальность. При вычислении диагонали приходится извлекать квадратные корни из последовательных остатков. Для положительно определённой матрицы они положительны. Нулевой остаток не позволяет продолжить обычный алгоритм с положительной диагональю, а отрицательный не имеет действительного квадратного корня.

Формулы вычисления по столбцам

Пусть уже найдены первые j−1j-1 столбцов LL. Тогда диагональный элемент и элементы ниже него вычисляются по формулам

ljj=ajj−∑k=1j−1ljk2,lij=aij−∑k=1j−1likljkljj,i>j.l_{jj}=\sqrt{a_{jj}-\sum_{k=1}^{j-1}l_{jk}^{2}},\qquad l_{ij}=\frac{a_{ij}-\sum_{k=1}^{j-1}l_{ik}l_{jk}}{l_{jj}},\quad i>j.

Пустая сумма считается нулём. Сначала находят диагональ столбца, затем все элементы под ней; над диагональю стоят нули. Каждое произведение в сумме учитывает вклад уже вычисленных столбцов. Отсюда понятен смысл остатка под корнем: это часть диагонального элемента AA, ещё не объяснённая предыдущими столбцами.

Для большой плотной матрицы прямой алгоритм требует порядка n3/3n^3/3 операций умножения и сложения в принятой оценке числа операций с плавающей точкой. Это примерно половина ведущего члена стоимости обычного плотного LU-разложения; фактическое время зависит от реализации и устройства компьютера. Достаточно хранить один треугольник симметричной матрицы, хотя конкретный формат хранения определяется библиотекой.

Пример с проверкой умножением

Возьмём значение t=2t=2, выбранное в калькуляторе по умолчанию:

A=(4222).A=\begin{pmatrix}4&2\\2&2\end{pmatrix}.

Матрица симметрична, её угловые миноры равны 44 и 4⋅2−22=44\cdot2-2^2=4: оба положительны. Поэтому алгоритм применим. Сначала l11=4=2l_{11}=\sqrt4=2, затем l21=2/2=1l_{21}=2/2=1. Последний остаток равен 2−12=12-1^2=1, откуда l22=1l_{22}=1.

При t равно 2 остаток под корнем равен 1 и последний диагональный элемент множителя Холецкого равен 1
При t равно 2 остаток под корнем равен 1 и последний диагональный элемент множителя Холецкого равен 1

Итак,

L=(2011),LLT=(2011)(2101)=(4222).L=\begin{pmatrix}2&0\\1&1\end{pmatrix},\qquad LL^T=\begin{pmatrix}2&0\\1&1\end{pmatrix} \begin{pmatrix}2&1\\0&1\end{pmatrix}= \begin{pmatrix}4&2\\2&2\end{pmatrix}.

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

Обратное умножение проверяет не только диагональ: внедиагональный элемент 22 тоже должен совпасть. В калькуляторе попробуйте t=1,25t=1{,}25: остаток уменьшится до 0,250{,}25, а последний корень - до 0,50{,}5. При t=5t=5 они станут равны 44 и 22 соответственно. Во всех трёх случаях первый столбец множителя остаётся прежним.

Решение системы и определитель

Чтобы решить Ax=bAx=b, подставим A=LLTA=LL^T и введём промежуточный вектор yy. Сначала решаем Ly=bLy=b прямой подстановкой, затем LTx=yL^Tx=y обратной. Явно находить обратную матрицу не требуется. Один раз найденный множитель можно использовать повторно для разных правых частей.

Для примера выше возьмём b=(6,4)Tb=(6,4)^T. Из уравнений 2y1=62y_1=6 и y1+y2=4y_1+y_2=4 получаем y=(3,1)Ty=(3,1)^T. Далее x2=1x_2=1 и 2x1+x2=32x_1+x_2=3, поэтому x=(1,1)Tx=(1,1)^T. Проверка: A(1,1)T=(6,4)TA(1,1)^T=(6,4)^T. В реализации LAPACK для решения по уже найденному множителю предусмотрена процедура DPOTRS.

Определитель треугольной матрицы равен произведению диагональных элементов. Поэтому

det⁡A=(det⁡L)2=(∏i=1nlii)2.\det A=(\det L)^2=\left(\prod_{i=1}^{n}l_{ii}\right)^2.

В примере это (2⋅1)2=4(2\cdot1)^2=4, что совпадает с прямым вычислением. Свойства произведения и транспонирования разобраны отдельно в статье о свойствах определителя. Для очень больших или маленьких результатов в программах часто удобнее хранить логарифм определителя: log⁡det⁡A=2∑ilog⁡lii\log\det A=2\sum_i\log l_{ii}.

Где полезен метод и что происходит у границы

Симметричные положительно определённые матрицы возникают, например, в некоторых задачах упругости и оптимизации. В методе наименьших квадратов матрица XTXX^TX положительно определена, если столбцы XX линейно независимы. Однако образование XTXX^TX может ухудшить обусловленность, поэтому на практике для исходной задачи наименьших квадратов часто выбирают QR или SVD. В больших разреженных системах важны также порядок переменных и заполнение нулями при факторизации.

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

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

Если матрица задана приближёнными измерениями, её элементы по обе стороны диагонали иногда немного различаются. Это повод выяснить происхождение расхождения до применения алгоритма: предположение симметрии относится к самой математической модели. Не следует автоматически считать, что выбранный программой треугольник исправляет ошибки во входных данных. Документация конкретной процедуры подскажет, какую часть массива она читает.

Симметричная полуопределённая матрица может иметь представление с нулевыми диагональными элементами, но стандартный алгоритм с делением на положительные диагональные элементы не гарантирует его нахождение. Для симметричных неопределённых матриц применяют другие методы, например подходящее разложение LDLTLDL^T с перестановками. При вычислениях с округлением ошибка факторизации может указывать как на нарушение условия, так и на чувствительность задачи около границы; полезно проверять данные и масштаб.

Частые ошибки

  • Проверять только симметрию. Нужна ещё положительная определённость; отрицательный определитель приведённого выше контрпримера сразу её исключает.
  • Проверять только определитель всей матрицы. Для критерия Сильвестра нужны все угловые главные миноры, а не только последний.
  • Забывать квадрат в остатке. На диагонали вычитают сумму ljk2l_{jk}^2, а не сумму самих элементов.
  • Переставлять множители. В выбранной записи A=LLTA=LL^T; произведение LTLL^TL обычно даёт другую матрицу.
  • Округлять промежуточные результаты слишком рано. Сохраняйте точность до проверки: возле вырожденности округление особенно заметно.

FAQ

Для какой матрицы разложение Холецкого единственно?
Для действительной симметричной положительно определённой матрицы оно единственно при условии, что диагональ нижнего множителя положительна. Без условия на знаки возможны другие треугольные множители.

Можно ли применять метод к комплексной матрице?
Да, для эрмитовой положительно определённой матрицы используют A=LL∗A=LL^*, где звёздочка означает сопряжённое транспонирование. Обычное транспонирование здесь недостаточно.

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

Коротко

Разложение Холецкого записывает симметричную положительно определённую матрицу в виде LLTLL^T. Его элементы находят последовательно по столбцам, а положительность остатков под корнем обеспечивает продолжение алгоритма. Множитель помогает решать системы и находить определитель; перед применением проверяют условия и учитывают обусловленность исходной задачи.

Доверьте текст нейросети EssayAI

Открыть EssayAI

Бесплатно, на русском языке и без VPN

Читайте также

Диагональное преобладание матрицы: проверка и примеры

Диагональное преобладание матрицы: проверка и примеры

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

8 ноября 20268 минут
Комбинированный метод хорд и касательных

Комбинированный метод хорд и касательных

Комбинированный метод хорд и касательных: как выбрать концы отрезка, вычислить границы корня, оценить погрешность и выполнить итерации на примере уравнения.

8 ноября 20268 минут
Метод Эйлера для ОДУ: пошаговый расчёт

Метод Эйлера для ОДУ: пошаговый расчёт

Метод Эйлера для ОДУ: как построить ломаную по начальным данным, составить таблицу шагов, сравнить численный результат с точным решением и оценить погрешность.

8 ноября 20268 минут
Метод Ньютона для систем нелинейных уравнений

Метод Ньютона для систем нелинейных уравнений

Метод Ньютона для систем нелинейных уравнений: как составить матрицу Якоби, найти поправку, выполнить итерации и проверить точность решения на подробном примере.

8 ноября 20268 минут
Метод Ньютона в оптимизации: формула и пример

Метод Ньютона в оптимизации: формула и пример

Метод Ньютона для поиска минимума: как построить квадратичную модель, вычислить шаг по градиенту и гессиану и проверить условия сходимости на примере.

8 ноября 20268 минут
Метод предиктор-корректор: прогноз и поправка

Метод предиктор-корректор: прогноз и поправка

Метод предиктор-корректор для задачи Коши: формулы прогноза и поправки, подробный пример пары Адамса и трапеций, оценка ошибки, запуск и ограничения схемы.

8 ноября 20268 минут