Если А — симметричная положительно определенная матрица, то существует и единственное разложение
,
где 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.
К недостатку метода можно отнести необходимость извлечения пквадратных корней, что является на некоторых типах ЭВМ достаточно медленной функцией.
Метод исключения Холесского позволяет проверить положительную определенность матрицы. Если матрица не является положительно определенной, то в процессе исключения потребуется извлечь корень квадратный из отрицательного числа. Следует иметь в виду, что отрицательное подкоренное значение может также иметь место за счет погрешности, обусловленной накоплением ошибок округления для положительно определенных, но плохо обусловленных (почти вырожденных) матриц.