Введение в вычислительную физику - Федоренко Р.П.
ISBN 5-7417-0002-0
Скачать (прямая ссылка):
Заметим еще, что существуют теоремы, обосновывающие правомерность пренебрежения членами второго порядка: если метод сходится в теории «первого приближения», т.е. норма соответствующей матрицы Il А у ^ д < 1, то при достаточно хорошем начальном приближении метод действительно сходится.
Метод Ньютона в специальных ситуациях. Часто приходится решать уравнение /(х) = 0 в специальной ситуации, когда функция задана не формулами, а алгоритмом, и достаточно сложным. Други-
РЕШЕНИЕ СИСТЕМ НЕЛИНЕЙНЫХ УРАВНЕНИЙ
19
ми словами, имеется программа, которая по заданному значению аргумента х вычисляет (после миллионов операций) значение /. Именно такую ситуацию изучает современный анализ, в котором термин «функция» (по традиции все-таки ассоциирующийся с такими понятиями, как «формула», «аналитическое выражение» и т.п.) вытесняется термином «отображение»: х -* /, где « » есть символ
каких-то, быть может, очень сложных операций. В такой ситуации метод Ньютона, требующий использования матрицы fх, должен быть дополнен алгоритмом ее вычисления.
Наиболее простым способом (естественно, простота покупается большим объемом вычислений) является численное дифференцирование. Пусть/(х) есть /(X1, х2, ..., х„), a A1, A2, A3, ... — малые числа, «шаги численного дифференцирования». Приближенно можно положить
= -jf [/(*j> •••> я,-1> X1 + Ai, xi+l, ..., X11) /(.X1, ..., Xi, ..., хп)].
Таким образом, для вычисления всех частных производных нужно п раз вычислить значение / при возмущении поочередно аргументов.
Итак, (приближенное) вычисление частных производных функции п переменных по самой простой формуле (называемой формулой одностороннего дифференцирования) требует (я + 1)-кратного вычисления функции. Существуют и другие формулы численного дифференцирования. Среди них особенно популярна формула «центральной разности»
Ц:^[/(^i, •••, Xi + а, ...)—/(X1,..., Xi- а, ...)].
Она, очевидно, более трудоемка: вычисление всех производных «стоит» In + \ вычислений /. Естественно ожидать, что эта формула бсшее точна. Вопросы о точности численного дифференцирования обсуждаются в следующем параграфе. Пока заметим лишь, что напрашивающийся ответ «чем меньше А, тем точнее численное дифференцирование» неверен.
Нормировка задачи. Практическое применение метода Ньютона в сложных задачах иноща приводит к очень медленной сходимости. В связи с этим возникает необходимость разбираться в причинах такого противоречия между обещаниями теории и реальными фактами. Правильно поняв причину, можно разработать приемы, существенно ускоряющие процесс решения. Один из них описывается ниже.
Начнем с простого примера. Применим схему модифицированного метода Ньютона для решения несложной системы уравнений
/(х, у) ш X5 + у4 — 2 = 0, <р(х, у) = (х- 2)3 + (у- 2)3 + 16 = 0.
Начальное приближение: х° = 2.0, у0 = 3.0.
20
ОСНОВЫ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ
В табл. 1 представлены величины, подробно показывающие процесс решения задачи. Поясним обозначения: к — номер шага (итерации); х, у — текущие значения искомых величин; /,<¦р — значе-
Таблица 1
к X У / г S а
0 2.0000 3.0000 111.000 17.000 112.294 0.11 40
1 2.0685 2.9380 110.379 16.826 111.654 0.108 42
2 2.1330 2.8680 109.801 16.656 111.057 0.094 48
4 2.2334 2.7274 108.906 16.398 110.134 0.064 57
5 2.2727 2.6589 108.607 16.306 109.824 0.047 52
7 2.3265 2.5471 108.246 16.199 109.451 0.021 46
8 2.3437 2.5057 108.138 16.170 109.340 0.015 43
10 2.3729 2.4284 108.008 16.130 109.206 0.012 33
12 2.3899 2.3781 107.946 16.113 109.141 0.004 25
14 2.4031 2.3358 107.914 16.130 109.109 0.0017 18
16 2.4108 2.3096 107.898 16.099 109.092 0.0010 15
ния функций в точке (х, у); г — (}г + ф2)1/2 — невязка; s — шаг спуска, найденный решением задачи одномерной минимизации; а — угол (в градусах) между векторами (fx, /у) и (фх, фу). Этот угол характеризует степень «невырожденности» отображения (х, у) -*• (/, ф) в данной точке.
Видно, что поиск решения проходит крайне неэффективно, шаг s очень далек от единицы, т.е. линеаризация уравнения работает на расстояниях, существенно меньших расстояния от текущей точки до искомого решения. Эволюция величины а указывает на приближение какой-то точки вырождения отображения. Однако начало процесса проходит очень медленно и при больших значениях а. Основная, видимо, причина — очень малые размеры области, в которой линейное приближение имеет хорошую точность. Точка (2.0, 3.0), однако, ничем не примечательна, и в данном простом примере можно проверить, что линеаризация / и ф достаточно точна на расстояниях, больших смещения х и у за один шаг процесса.
Попробуем разобраться в ситуации. Для этого стоит посмотреть на систему уравнений метода Ньютона. В точке (2.0, 3.0) она имеет вид
Ifx fy\ /бх\ __//\ /80 108\ (дх) _ /11Л
К <Р,Д&эу W 10 3Jw і 17 J-
РЕШЕНИЕ СИСТЕМ НЕЛИНЕЙНЫХ УРАВНЕНИЙ
21
(В других точках табл. 1 ситуация примерно та же самая.) Решение этой системы: Ьх'= 6.26, by = —5.67. (Противоречие между изменением х и у и шагом S B табл. 1 объясняется нормировкой направления движения.) Обратим внимание на характерную деталь: направление (Ьх, Ьу) «почти ортогонально» вектору (fx, fy):
