Научная литература
booksshare.net -> Добавить материал -> Физика -> Федоренко Р.П. -> "Введение в вычислительную физику" -> 5

Введение в вычислительную физику - Федоренко Р.П.

Федоренко Р.П. Введение в вычислительную физику — М.: Физ-тех, 1994. — 528 c.
ISBN 5-7417-0002-0
Скачать (прямая ссылка): vvedenievvichesleniyah1994.djvu
Предыдущая << 1 .. 2 3 4 < 5 > 6 7 8 9 10 11 .. 210 >> Следующая


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

С||/(х°)||<*<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}.
Предыдущая << 1 .. 2 3 4 < 5 > 6 7 8 9 10 11 .. 210 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed