Метод ортогонализации и метод сопряженных градиентов (стр. 3 из 4)
. (12)Вектор
примем за новое приближение к решению
системы. Вектор невязок 
(13)имеет направление нормали к поверхности
в точке 
. Покажем, что он будет ортогонален к 
и 
. В самом деле, используя (9), (11), (12), (13), имеем: 
Рассмотрим гиперплоскость (n-2) – х измерений
, (14)проходящую через точку
. Эта гиперплоскость содержит и 
, так как мы ранее видели, что 
, а 
.Вектор
при любом 
параллелен гиперплоскости (7), так как 
.Подберем
так, чтобы он был параллелен и гиперплоскости (14), т.е. потребуем ортогональности к вектору 
. Будем иметь: 
,или
(15)Вектор
(16)будет иметь направление нормали к сечению поверхности
гиперплоскостью (14) в точке . Из точки сместимся в направлении этого вектора так, чтобы функция 
достигла минимального значения. Это будет при 
, (17) 
(18)примем за новое приближение к
. Новый вектор невязок будет: 
. (19)Продолжая процесс, получим последовательности векторов
, 
, 
, определяемые рекуррентными соотношениями:
(20)Для этих векторов имеют место следующие соотношения:
(21) 
(22)В самом деле, в силу самого построения при i¹j
Далее, при i>j
Если i=j+1, то правая часть равна нулю, в силу определения
, если же i>j+1, то 
, по доказанному, и 
.Продолжая понижение индекса у вектора
, через несколько шагов придем к скалярному произведению 
(по определению 
). Таким образом, соотношения (21) доказаны. Для доказательства (22), в силу равноправия индексов i и j, предположим, что i>j. Тогда 
.Так как в n-мерном векторном пространства не может быть более n взаимно ортогональных векторов, то на некотором шаге
получим 
, т.е. 
будет решением системы (1).На рис. 1 показана геометрическая картина нашего построения при n=3.
Рис. 1
2.2 Второй алгоритм метода
Приведем другой алгоритм метода. Будем обозначать последовательные приближения к решению через
и введем обозначения: 
. (23)Первые два приближения
и 
возьмем так, чтобы
. (24)Предположим, что уже известно приближение
(i³1), вычислены 
и справедливо равенство 
. (25)Будем искать минимум функционала (2) на множестве векторов
. (26)Приравнивая к нулю частные производные от
по 
и 
для определения 
и 
, получим систему: 
(27)или, учитывая (25),
(28)Обозначим через
решение этой системы:
(29)и за (i+1) – е приближение к решению примем:
(30)Из системы (27) следует, что
, (31)а так как
то из (31) следует:
(32)Докажем, что если
(33)то при всех i
(34)что будет доказывать и сходимость, и конечность второго алгоритма.
В самом деле, при условиях (33)
и
т.е. условие (24) выполнено. Предположим, что уже доказаны равенства
(35)и докажем равенство
При предположении (35)
и, следовательно, 
Но из соотношений (20) имеем:
