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