Разложение Холецкого
5.2 Разложение Холецкого.
Справедлива следующая теорема (Холецкий).
Для симметричной положительно определенной матрицы существует единственное разложение , причем диагональные элементы множителей положительны.
Укажем способ вычисления коэффициентов треугольных множителей.
В индексах это равенство имеет вид
,
откуда следует
(4)
Рекомендуемые материалы
Впрочем, эта формула верна и при , но в этом случае ее надо читать так:
(5)
Из-за формулы (5) метод разложения Холецкого иногда называют методом квадратного корня. Порядок вычислений коэффициентов следующий. Последовательно для строк i=1,2,…,n вначале вычисляется диагональный элемент (5), а затем и все другие коэффициенты в этой строке по формуле (4). При подсчете фактически скалярно перемножаются два «надстолбца» с номерами (он располагается над диагональным элементом ) и (он располагается над текущим элементом ). Все элементы этих «надстолбцов» уже вычислены.
Рекомендуем посмотреть лекцию "12 Системы индексов".
Формулы разложения Холецкого (5), (4) записаны в общем виде для произвольной (заполненной) матрицы. Однако сеточные схемы порождают разреженные матрицы, т.е. такие, у которых подавляющее большинство элементов равны нулю. Главным отрицательным свойством факторизации Холецкого служит заполнение , которое выражается в том, что у треугольных множителей появляются ненулевые элементы в тех позициях, где у исходной матрицы были нули. Это катастрофически увеличивает как требуемый объем памяти для хранения множителей, так и количество вычислений по формулам вида (2), (3). При специальной нумерации узлов сетки можно добиться того, чтобы все ненулевые элементы матрицы располагались вблизи главной диагонали. В этом случае говорят о ленточной матрице. Вводится понятие ширины ленты. Для произвольной строки можно указать такой номер столбца , что все при . Полушириной ленты называют значение . Сама лента показана на рисунке розовым цветом. Вне ленты находятся только нулевые элементы, а внутри ее могут быть как ненулевые, так и равные нулю. Алгоритм построения треугольных множителей через скалярное произведение «надстолбцов» показывает, что заполнение при разложении Холецкого ленточной матрицы происходит лишь внутри ленты.
Итак, найдена верхняя треугольная матрица . Чтобы получить решение задачи вначале решаем задачу . Однако в симметричном случае саму матрицу вычислять не обязательно, достаточно в формуле (3) заменить на :
Затем строим решение исходной задачи, решая систему , см. (2) :