Метод квадратного корня (Холесского)

Если А — симметричная положительно определенная матрица, то существует и единственное разложение

,

где U— верхняя треугольная матрица.

Выполним первый шаг факторизации, для чего запишем заданную матрицуАв блочной форме

 

 

,

 

где ; В — симметричная подматрица размерности n -1; , i=k+1, k+2,..., п — вектор, построенный из элементов матрицыА; k— номер шага факторизации.

Теперь матрицуАможно факторизовать следующим образом:

 

 

 

где 0 — нулевой вектор-столбец,

- матрица порядка n-1,

— симметричная и положительно определенная матрица, ее можно факторизовать таким же образом. Выполнив факторизацию праз, получим А в виде 2п элементарных матриц . Их произве­дение

.

Решение факторизованной системы осуществляется путем введе­ния промежуточной векторной переменной Y

,

что анолгоично решению системы АХ=B.

Эффективный алгоритм для такой схемы можно построить путем последовательного приравнивания элементов п-п — матрицАи UTU, стоящих в позициях (1,1), (1,2),..., (1, n), (2,2),..., (2, п),..., (n, n). Окончательно алгоритм метода Холесского разложе­ния матрицы на множители может быть записан следующим образом:

1) Для k=1,2,3,..., п выполнить пп. 2 - 4.

2) Вычислить .

3) Для j= k+ 1, k + 2, . . .,n выполнить .

4) Для i = k + 1,k + 2,...,nиj = k + 1,k + 2,...,п выполнить

5) Конец алгоритма. Элементы матрицы А изменили свои значения.

 

Можно модифицировать алгоритм так, чтобы элементы матрицы Uбыли получены на месте элементов исходной матрицы А. Для этого необходимо заменить все переменные n на a.

К недостатку метода можно отнести необходимость извлечения пквадратных корней, что является на некоторых типах ЭВМ достаточно медленной функцией.

Метод исключения Холесского позволяет проверить положитель­ную определенность матрицы. Если матрица не является положитель­но определенной, то в процессе исключения потребуется извлечь ко­рень квадратный из отрицательного числа. Следует иметь в виду, что отрицательное подкоренное значение может также иметь место за счет погрешности, обусловленной накоплением ошибок округления для по­ложительно определенных, но плохо обусловленных (почти вырожден­ных) матриц.