Введение в вычислительную физику - Федоренко Р.П.
ISBN 5-7417-0002-0
Скачать (прямая ссылка):
Теперь можно более точно указать, насколько хорошим должно быть начальное приближение х°, чтобы процесс заведомо сходился. Очевидно, для этого достаточно выполнения неравенства
С||/(х°)||<*<1.
РЕШЕНИЕ СИСТЕМ НЕЛИНЕЙНЫХ УРАВНЕНИЙ
13
Можно уточнить и вид области, в которой предполагаются выполненными сформулированные в условиях теоремы оценки производных. Такой областью может быть область, выделенная неравенством \\f(x)\\ < l/C. В самом деле, если х° лежит в области С IIZ(X0)II «<7<1, то Wf(X1)W^q1ZC и т.д., т.е. все последующие приближения Xk лежат в этой области.
Условие IIZJi(X)II ^ C1 существенно. Оно гарантирует взаимную однозначность (в некоторой области) отображения х-*/(х), что, как известно, очень важно для существования и единственности решения системы /(х) = 0.
Модификация метода Ньютона. Метод Ньютона, являясь весьма эффективным средством уточнения сравнительно хорошего начального приближения, может расходится, если X0 — слишком грубое приближение к искомому решению. В схему алгоритма были
внесены изменения, имеющие целью ослабить требования к начальному приближению и сделать-сходимость не столь зависящей от его выбора. Идею такой модификации поясним, начав с геометрической интерпретации метода Ньютона в двумерном случае (п = 2).
Итак, пусть решается система
Zi(xj, х2) = 0, Zг(Хр х2) = 0.
На рис. 2 изображены плоскости (xt, х2) и (Z1, f2)• Точка х° отображается в точку Z0- В этой точке отображение x-*f(x) линеаризуется, т.е. заменяется отображением
и находится точка (х1, х2), в линейном отображении переходящая в точку (0, 0). Однако в нелинейном отображении х -* f(x) точка х1 отображается не в нуль, а в Z1-
14
ОСНОВЫ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ
[4-І
Изучим непрерывное движение ОТ X0 К X1 по прямой. Обозначив Sx — X1 — х°, рассмотрим отрезок прямой
x(s) = X0 + s Ьх, s^O, X(I) = X1
(в расчетах обычно берут x(s) = х° + s 6х/||6х||). Образ этого отрезка в нелинейном отображении есть кривая /[s] = f(x(s)) (см. рис. 2). В точке s = 0 она касается направления на точку (0, 0). В самом деле, при достаточно малых s имеем
/[s] = f(x° + ^ Ьх) = /° + s fx(x°) Ьх + 0(s2).
В силу /Х(х°) Ьх — —/° функция
/[s] = /° — s /° + 0(s2) = (I — s) /° + 0(s2).
Другими словами, при малых s точка /[s] движется почти (с точностью до 0(s2)) прямо в начало координат.
По мере увеличения s величины 0(s2) возрастают, они могут стать определяющими и существенно отклонить траекторию f[s] от желаемого движения в начало координат. Теперь очевидно, что нужно двигаться по [х°, Xі] до тех пор, пока точка /[s] приближается к началу координат, т.е. шаг s* определяется решением одномерной задачи минимизации. Ищется
min Il/(х° + s Ьх) Il.
S
Точку минимума принято обозначать .в виде
s* = arg min ||/(х° + s 6х) ||.
S
Итак, сформируем алгоритм модифицированного метода Ньютона (MMH):
1) имеется некоторая точка х;
2) вычисляются /(х) и /Х(х);
3) находится Ьх из системы / + /х Ьх = 0;
4) определяется функция скалярного аргумента s:
F(s) = \\f(x+sbx)\\-,
5) находится
s* = arg min F(s)\
S
6) вычисляется следующее приближение:
х-=х + s* Ьх.
§ 1] РЕШЕНИЕ СИСТЕМ НЕЛИНЕЙНЫХ УРАВНЕНИЙ 15
В приведенном алгоритме есть элемент, требующий уточнения, — это решение задачи min F. Этой задаче посвящен § 26. Иногда используют совсем простую процедуру дробления шага. Сначала берут значение S=I (как в стандартном методе Ньютона). Если окажется, что К f(x 4- s Ьх) Il < ||Z(x)||, то этот шаги остается. В противном случае s заменяют на s/2 и снова сравнивают нормы. И т.д. — до получения соотношения ||/(х + 6х/2р)|| < ||/(х)||.
Докажем теорему о сходимости модифицированного метода Ньютона.
Теорема 2. Определим область Q как множество точек, в которых ||/(х)|| «а ||/(х°)||. Предположим, что:
а) /(х) — гладкая функция и \\fхх(х)\\ ^ C2, х Є Я;
б) отображение х -* /(х) равномерно невырождено и IIZJi(X)II ^ ^C11VxEfi;
в) Q — ограниченная связная область.
Пусть хк — точки, последовательно полученные, начиная с х°, согласно модифицированному методу Ньютона, а гк — соответствующие невязки (rk = IIZ(Xlt)II). Тогда в области Q существует единственное решение х* системы уравнений (т.е. Z(x*) =0) и
. Iim хк = х*, Iim гк — 0.
Доказательство. Отметим очевидный факт: невязки rk монотонно убывают, т.е. г0 з* г, »... » rk > ... Следовательно, все хк Є Оценим величину убывания невязки rk за один шаг, используя соотношение
f(xk + s 6х) = (I — s) f(xk) + S2 0(([ 6х||2), дх = ZJjZ(Xi). Отсюда следует (при s Є [0, 1])
rk+i = min И/(** + 5 5*)И <min {(1 - s) IIf(Xk)H + Cs2rl).
5 0«s«l
Здесь мы оценили
ЦО(||6х||2)|| ^ C2 ||6х||2 ^ C2 IIZJiII2 Il Z(Xfc)II2.
Таким образом,
rJt+1 * min K1 - s)rk + Cs2r2}.
0«s«l
Вычислим минимум правой части (игнорируя пока ограничение s ^l). Он достигается в точке s" — \/(2Crk), а значение
16
ОСНОВЫ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ
[Ч.І
минимума в этом случае есть гк — 1/(4С). Если s’^1, будем использовать эту оценку; если s* > 1, оценим минимум значением в точке s=l. В этом случае rk+1 ^ Сг\. Так как при этом s* = 1/(2Сгк) > 1, то Cr1kKrkI2. Итак, в любом случае при переходе от Xk к х*+1 невязка убывает не меньше, чем на величину min (1/(4С), гк/2}.