Введение в вычислительную физику - Федоренко Р.П.
ISBN 5-7417-0002-0
Скачать (прямая ссылка):
fr Ьх + /„ by = 80-6.26- 108-5.67^500-611 = -111.
* У
(Здесь 111 — действительно малая величина, ведь ее естественно относить к величине 500 + 611 = 1111, т.е. в «безразмерных» единицах величина 111 мала в том же смысле, в каком 0.1 мала относительно 1.)
Итак, направление (6х, 6у) «почти совпадает» с касательной к линии уровня f(x, у) = const, а вдоль касательной приращение / определяется членами второго порядка, которые алгоритм игнорирует. Почему же алгоритм выбирает такое направление, т.е. его «не интересует» уменьшение величины / = 111, он в большей степени заинтересован в уменьшении относительно малой величины <р = 17? Возникает парадоксальное предположение: видимо, в точках
(хк, ук) уравнение / = 0 уже почти выполнено, а уравнение Ф = 0 — нет. Ведь из того, что / =111, а ф = 17, еще ничего не следует. Откуда известно, как нужно сравнивать величины / и ф? Подобные вопросы всегда должны возникать перед вычислителем. Они приводят к требованию нормировки задачи.
В самом деле, не меняя существа дела, можно перейти к системе
~^f(x,y) = 0, іф(х, у)=0.
Очевидно, что направление (Ьх, Ьу) инвариантно относительно произвольного выбора «единиц измерения» X1 и х2. Ho величина невязки г = [(//X1)2 + (ф/х2)2]1/2 и, следовательно, шаг s такой инвариантностью не обладают. При этом возникает проблема выбора «правильных» масштабов X1, х2. В своей практике автор в подобных ситуациях руководствовался правилом, условно названным «принципом равноправия»: масштабы нужно выбирать такими, чтобы одинаковые изменения х и у приводили к численно близким изменениям / и (р. Формулы для малых приращений / и <р показывают, что эта цель в известной мере будет достигнута (в окрестности данной точки (х, у)), если взять X1 = (/2 + f))in, X2= (<vl + у))т.
Таким образом, мы приходим к модифицированному методу Ньютона с нормировкой. Алгоритм стандартного шага в точке (х, у) дополняется следующим: после вычисления производных и направления (Ьх, Ьу) вычисляются «масштабы» Xi, и шаг s выбирается минимизацией масштабированной невязки. Эффект этого при-
22
ОСНОВЫ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ
[Ч. I
ема иллюстрирует табл. 2. Обозначения в ней — те же, что и в табл. 1, только величины г0 и г1 означают величины масштабированной невязки в точке (Xk, ук) и в следующей точке (хк + ї, yk+l). Заметим, что теперь у нас нет единой невязки, которая убывала бы в процессе решения, чем в сущности и обеспечивается сходимость метода. В точке (хк+*, у*+|) есть две невязки: при масштабировании в точке (хк, ук) и при масштабировании в точке (xk+1, yk+l). Теорема о сходимости модифицированного метода Ньютона утрачивает силу, но зато сама сходимость стала существенно лучше.
Данные / = O и <р = 0 в последней строке табл. 2 означают, что
эти величины не больше 5-Ю-6. На основании вышесказанного естественно возникает вопрос: действительно ли это малая величина? Ответ на него несложен. Если вычислитель постулировал, что для
Таблица 2
к X У / 1P rO rI S
0 2.0000 3.0000 111.000 17.000 5.72 5.52 0.066
X 2.4X4 2.626 127.500 16.32 12.75 11.59 0.125
2 3.209 0.542 338.4 14.66 2.00 0.55 0.50
3 2.891 -0.389 200.0 3.07 0.60 0.0826 1.90
4 1.806 -0.578 17.3 -1.14 0.331 0.026 2.00
5 1.157 -0.460 0.115 ' 0.516 0.031 0.00054 1.0
6 1.14265 -0.48663 0.004 -0.006 0.0006 0 1.0
7 1.14220 -0.48626 0 0
х и у величина IO-5 является малой, то естественно считать малыми для / и <р изменения, порождаемые такими малыми Ьх и Sy. Это опять-таки приводит нас к тому масштабированию, которое было использовано, и величины /, <р порядка 5- IO-6 следует тоже считать малыми.
Из табл. 2 видно, что в единицах ир и2 величина /=111 стала «малой» по сравнению с ф = 17. Допускается ее существенное увеличение ради уменьшения ф. Внешне большое значение / = 338 затем сравнительно малыми изменениями Ьх и Ьу доводится до нуля. Это есть следствие разной чувствительности / и ф к изменениям х, у, т.е. существенно разных величин их производных.
После того как два-три раза подряд минимизация г по s в модифицированном методе Ньютона приводит к значениям, близким к единице, переходят на обычный метод Ньютона, не тратя машинного времени на подбор s. Однако в данном примере, после получения
РЕШЕНИЕ СИСТЕМ НЕЛИНЕЙНЫХ УРАВНЕНИЙ
23
приближения, хорошего в смысле теоремы 1, сходимость оказывается столь быстрой, что этот прием не дал бы нам никакой экономии.
Другая, но по существу близкая, нормировка была предложена немецким математиком Дёфлхардом. В его варианте модифицированного метода Ньютона после вычисления /(х) и матрицы Fx(x)
вычисляется матрица А = f~l и минимизируется невязка rz(s) = (A f(x + s Ьх), Af(x + sbx)).
Смысл этой конструкции станет ясен, если проанализировать поведение правой части при малых 6 (в первом приближении):
Af(x + b) = Af(x) + Afx(x)b = Af(x) + b.
Таким образом, в окрестности точки х невязка устроена очень просто:
г2(Ь) = C +(В, 6) + (6, 6).
Такая ситуация наиболее благоприятна для алгоритмов поиска минимума, а решение системы f(x) = 0 можно трактовать как поиск
