§ 4. Анализ погрешностей метода

В § 1 был рассмотрен процесс, в котором строились последовательность вложенных гиперпространств , возрастающей размерности и последовательность точек , доставляющих условный максимум функции , соответственно, на гиперпространствах . При этом оказалось, что векторы  являются -ортогональными.

Покажем сейчас, что справедливо в некотором смысле и обратное утверждение.

Если:

1) векторы  -ортогональны, т. е.

 при ,

2) точки  получены из рекуррентного условия:  доставляет условный максимум функции  на прямой

при произвольной фиксированной точке ,

то точка  доставляет условный максимум  на гиперпространстве , определяемом как совокупность векторов вида

.                     (16.27)

В самом деле, подставляя формулу (16.26) в выражение для , получим

.

Положим

 и .

Тогда, учитывая -ортогональность  и  при , получим

.                  (16.28)

Чтобы найти вектор , доставляющий максимум  на , продифференцируем  по  и приравняем частные производные к нулю. Тогда

(здесь  из-за положительной определенности формы), откуда

.                   (16.29)

Сопоставляя выражения (16.27) для  и , имеем

,

.

Таким образом, точка  лежит на прямой вида

и, очевидно, доставляет функции  условный максимум на этой прямой, поскольку в этой точке достигается условный максимум на всем гиперпространстве , включающем прямую.

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

.

Будем считать, что . Тогда коэффициенты  для  при  в представлении (16.27) равны нулю. Поиск максимума на прямой

равносилен поиску максимума выражения (16.28) по переменной  при фиксированных остальных переменных . Осуществляя эту операцию, убеждаемся, что , как и раньше, равно . Таким образом, -й шаг возмущенного процесса совпадает с соответствующим шагом невозмущенного, откуда следует, что ошибки просто складываются. Если суммарная накопившаяся ошибка после  шагов заведомо мала по сравнению с перемещением от начальной точки к точке оптимума (это условие выполняется при работе на ЭВМ), то во всяком случае после двух-трех повторных применений алгоритма максимум будет найден с очень высокой точностью.

Все эти рассуждения верны в предположении, что система -ортогональных векторов  получена заранее и с достаточно высокой точностью. Но в действительности метод сопряженных градиентов строит эти векторы, используя рекурсивную процедуру. Оказывается, что при этом дело может обстоять значительно хуже, а именно: однажды возникшая малая ошибка может привести к лавинообразному нарастанию ошибок в ходе дальнейших вычислений.

В самом деле, рассмотрим метод сопряженных градиентов в форме II:  – произвольно и при

1) ,              (16.30')

2) ,                     (16.30'')

3) ,                      (16.30"')

где

,

.            (16.31)

Выведем рекуррентные соотношения для величин  и . Из (16.30") имеем

.

Подставляя это выражение в (16.30') и умножая скалярно обе части равенства на , получим

(в последнем члене использовано равенство ). Далее, чтобы получить рекуррентное выражение для , заменим  по формуле (16.30"); получим

.                (16.32)

Теперь воспользуемся снова соотношением, вытекающим из (16.30') и (16.30"),

и подставив его в (16.32) получим

.

Наконец, из формулы (16.30")

,

и окончательно рекуррентное соотношение примет вид

.

Перепишем рекуррентные соотношения в новых обозначениях, полагая , . При  получаем

               (16.33)

.

При  получаем

.

Нетрудно убедиться, что коэффициенты  и  подобраны в алгоритме именно так, чтобы  и  обратились точно в нуль. Поэтому можно рассматривать систему (16.33) при  с граничным условием , . Так как система (16.31) является линейной и однородной, то при этих начальных условиях она имеет единственное решение

,  при .

Заметим, что этот вывод является другим доказательством того, что метод сопряженных градиентов на -м шаге достигает условного максимума в , так как для этого достаточно, чтобы  при .

Но система (16.31) может быть неустойчивой. Этого нельзя утверждать в общем случае, ибо оказывается, что всегда можно подобрать функцию  и начальную точку так, чтобы  и  приняли любые наперед заданные положительные значения, а последние можно подобрать и так, чтобы система оказалась устойчивой. Но во многих случаях она все-таки оказывается неустойчивой. Покажем это на примере, положив

,  при ,

для всех .

Допустим, что при некотором  происходит единичное возмущение величины , т. е. , причем  при ,  при всех .

Легко видеть, что решение выглядит следующим образом:

				1
			1	–3
		1	–3	9
	1	–3	9	–27
		1	–3	9
			1	–3
				1

 

		–1	4
	–1	4	–12
	4	12	36
	–1	4	–12
		–1	4

Аналитическое решение таково:

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

Такого рода явления можно устранить, если на каждом шаге проводить полную -ортогонализацию очередного вектора  относительно всех предшествующих , а не только , но это требует большего числа действий на каждом шаге.