Метод ортогонализации и метод сопряженных градиентов (стр. 2 из 4)
1.2 Метод ортогонализации в случае несимметрической матрицы
В случае несимметрической матрицы процесс ортогонализации проводится точно также. Пусть векторы
уже построены. Тогда 
ищется в виде
(29)Коэффициенты
определяются из системы 
(30)Система в случае несимметрической матрицы будет треугольной.
Аналогично строится система «биортогональных» векторов, т.е. система 2n векторов, удовлетворяющих условию (12). При этом
– n произвольных линейно независимых векторов, а векторы 
строятся последовательно в виде 
(31)Коэффициенты
находятся из системы 
(32)Также поступаем, отыскивая коэффициенты
и 
, при построении систем векторов (14) и (15), удовлетворяющих условиям (16).При этом получим две системы:
(33)из которых и определяем
и .Остановимся еще на одном методе ортогонализации. Будем рассматривать строки матрицы А как векторы:
(34)Ортонормируем эту систему векторов. Первое уравнение системы
делим на 
. При этом получим 
(35)где
(36)Второе уравнение системы заменится на
(37)где
(38)Аналогично поступаем дальше. Уравнение с номером i примет вид
(39)где
(40)Процесс будет осуществим, если система уравнений линейно независима. В результате мы придем к новой системе
, где матрица С будет ортогональной, т.е. обладает свойством СС¢=I.Таким образом, решение системы можно записать в виде
. (41)Практически, вследствие ошибок округления, СС¢ будет отлична от единичной матрицы и может оказаться целесообразным произвести несколько итераций для системы
.2. Метод сопряженных градиентов
2.1 Первый алгоритм метода
Пусть требуется решить систему линейных алгебраических уравнений
(1)с положительно определенной матрицей A порядка n.
Рассмотрим функционал
, (2)представляющий многочлен второго порядка относительно x1, x2, …, xn. Обозначим через
решение системы (1), т.е. 
. В силу симметричности и положительной определенности матрицы, имеем: 
При этом знак равенства возможен лишь при
. Таким образом, задача решения уравнения (1) сводится к задаче отыскания вектора 
, обращающего в минимум функционал (2).Для отыскания такого вектора применим следующий метод.
Пусть
– произвольный начальный вектор, а 
(4)– вектор невязок системы. Покажем, что вектор невязок
имеет направление нормали к поверхности 
в точке 
. В самом деле, направление нормали совпадает с направлением быстрейшего изменения функции 
в точке . Это направление мы найдем, если найдем среди векторов 
, для которых 
, такой вектор, что 
имеет наибольшее значение. Но
Но среди векторов
постоянный длины 
достигает максимального значения, если имеет направление вектора или ему противоположное. Утверждение доказано. Будем двигаться из точки 
в направлении вектора до тех пор, пока функция 
достигает минимального значения. Это будет при 
, т.е. при 
. (5)Вектор
(6)и принимаем за новое приближение к решению.
В методе сопряженных градиентов следующее приближение
находится так. Через точку 
проведем гиперплоскость (n-1) – го измерения 
(7)и через
обозначим новую невязку системы 
. (8)Вектор
направлен по нормали к поверхности 
в точке , а вектор параллелен касательной плоскости в этой точке. Поэтому 
. (9)Гиперплоскость (7) проходит через точку
, так как 
.При любом
вектор 
параллелен некоторой нормальной плоскости к поверхности 
в точке . Найдем среди них тот, который лежит в гиперплоскости (7), т.е. ортогонален к 
. Из условия ортогональности имеем:
,или
. (10)Вектор
(11)имеет направление нормали к сечению поверхности
гиперплоскости (7) в точке 
. Будем двигаться из точки в направлении вектора 
до тех пор, пока функция 
достигнет минимума. Это будет при