Факторизация матриц по методу Холецкого

Для произвольных невырожденных матриц выбор главного элемента является необходимой процедурой, но некоторые типы матриц не требуют никаких перестановок – в частности, диагонально-доминирующие матрицы и положительно определенные симметричные матрицы. В случае симметричной положительно определенной матрицы можно использовать вариант Гауссова исключения под названием метода Холецкого. Он основан на разложении

A=LL^T,

где L – нижняя треугольная матрица, у которой на главной диагонали не обязательно стоят единицы, как было в LU-разложении. При положительности диагональных элементов L разложение будет единственным. Правило получения элементов матрицы L через элементы А получим, приравнивая элементы в левой и правой частях A=LL^T. Принимая во внимание, что l_ij=0 при j>i, получаем:

.

Приравнивая элементы первого столбца слева и справа от знака равенства видим, что a_i1=l_i1l_i1, так что первый столбец матрицы L находится по формулам l₁₁=(a₁₁)^1/2, l_i1=a_i1/l₁₁, i=2, …, n.

Аналогично получаем a_ii= a_ij= j<i для последовательного определения столбцов матрицы L по следующему алгоритму:

Разложение Холецкого

Для j=1 до n

l_jj=

Для i=j+1 до n

l_ij= .

После вычисления матрицы L решение линейной системы может быть получено точно так, как в случае LU-разложения: решаем Ly=b, затем решаем L^Tx=y.

Чтобы метод Холецкого работал, необходимо, чтобы

a_jj– >0,

что соблюдается при положительной определенности матрицы А. При этом метод будет и численно устойчивым.

Метод легко адаптируется для ленточных матриц. Если р – число ненулевых диагоналей ниже и выше главной, то алгоритм Холецкого принимает вид:

Разложение Холецкого для ленточных матриц

Для j=1 до n

q=max(1, j-p), l_jj=(a_jj–

Для i=j+1 до min(j+p, n)

r=max(1, i-p), l_ij=(a_ij–