Метод Холесского

Исключительно эффективную реализацию метода LU-факторизации можно получить, если ограничиться классом линейных систем с симметрической положительно определенной матрицей A, т. е. Такую реализацию называют методом Холесского, либо методом квадратного корня.

Будем полагать, что решаемая система

имеет симметрическую положительно определенную матрицу A. В этом случае матрица A представляется в виде

Здесь – нижняя треугольная матрица. Такое разложение существует и единственно для положительно определенных симметрических матриц.

Система преобразуется к виду

.

Вектор ищется путем последовательного решения двух систем с треугольными матрицами:

; .

Для получения расчетных соотношений элементов матрицы рассмотрим произвольный элемент матрицы A:

Суммирование здесь выполняется только до j, т. к. j≤i. Выделим член при значении k=j:

.

Теперь

Эти соотношения позволяют вычислить по столбцам элементы матрицы .

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

Существует другой вариант разложения симметрической положительно определенной матрицы, в котором удается избежать операций извлечения квадратного корня. В этом варианте вводится новая матрица по правилу

,

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

,

где

.

Расчетные соотношения для элементов матриц и можно получить, как и прежде, привлекая правило перемножения матриц

,

из которого следует, что

т. к. матрица имеет единичную диагональ.

Такой алгоритм потребует вдвое большего числа перемножений, чем схема Холесского. Однако, если ввести замену переменных

,

то расчетные соотношения примут вид

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

Date: 2015-07-27; view: 523; Нарушение авторских прав