Введение в вычислительную физику - Федоренко Р.П.
ISBN 5-7417-0002-0
Скачать (прямая ссылка):
минимума г2= II/(х)Il2.
Метод продолжения по параметру. Опишем в общих чертах другой прием, имеющий ту же цель — ослабить требования к выбору начального приближения и обеспечить надежную сходимость метода решения системы уравнений f(x) = 0. В литературе этот метод иногда называют «методом инвариантного погружения».
Рассмотрим семейство задач F(x, X) = 0, где X — скалярный параметр. Сконструируем это семейство так, что F(x, 1) = /(х), а при X = O уравнение F(x, 0) = 0 легко решается или даже имеет явное решение. Это и есть «погружение» исходной задачи в семейство задач. Формально построить такое погружение часто не представляет труда. Вот, например, самый простой способ:
F(x, X) = (l- Х)х + X /(х). (5)
Уравнение F(x, 0)=0 имеет очевидное решение х = 0. Пусть х ( X.) есть решение уравнения (5). Последовательно решается серия задач. Имея решение х(Х), меняем X на А. + ДА. и решаем уравнение F(x, X + АХ) = 0 тем или иным итерационным методом. Используем х(Х) как хорошее начальное приближение (АХ, естественно, считаем малым изменением). Таким образом можно (при благоприятном ходе событий) добраться до X = 1 и получить решение исходной задачи.
Нетрудно оформить эту конструкцию в виде задачи Коши для системы обыкновенных дифференциальных уравнений, т.е. вычислить производную dx/dX. В самом деде, дифференцируя по X, получаем
24
ОСНОВЫ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ
откуда
Связь с методом Ньютона достаточно прозрачная. Сведение к задаче Коши иногда считают исчерпывающим решением проблемы, поскольку многие полагают эту задачу самой простой в вычислительной математике. Это мнение (ошибочное в столь общей форме, как мы увидим в дальнейшем) основано на том факте, что для решения задачи Коши существуют не только строго обоснованные алгоритмы, но даже стандартные программы и можно, не имея представления о том, как они работают, просто обращаться к ним.
Реализуя метод продолжения по параметру, часто сталкиваются с тем, что график х(Х) имеет S-образную форму, т.е. имеется несколько ветвей решения уравнения F(x, Я) = 0. Отслеживая одну из них, достигают некоторой точки X1, за которую данная ветвь х(Х) не продолжается, — решения уравнения F(x, X + АХ) = 0, близкого к а:(Я-), не существует. Внешне это проявляется в вырождении матрицы Fx, т.е. det Fx -* 0. Для продолжения решения задачи нужно двигаться по X в обратном направлении, перейдя, однако, на другую ветвь функции х(Х).
Технически это реализуется следующим образом: n-мерный вектор х и скалярный параметр X объединяются в единый (« + ^-мерный вектор у= ..., Специальным образом на каждом ша-
ге процесса продолжения выбирается одна из компонент yt, которой дается предписанное приращение; остальные находятся решением системы п нелинейных уравнений. Выбор номера этой ведущей компоненты основан на анализе предшествующих шагов. Рекомендуется выбирать в качестве ведущей ту компоненту yt, эволюция которой в процессе продолжения не дает оснований предположить возможное изменение направления ее движения. Признаком приближения точки поворота для компоненты _у. может служить, например, уменьшение ее приращения за один шаг.
§ 2. Численное дифференцирование
Практическое применение приведенных в § 1 формул численного дифференцирования связано с необходимостью выбора подходящего шага h. Возникающие здесь проблемы рассмотрим для простоты на примере функции только одного переменного /(х). Нас интересует погрешность формулы численного дифференцирования. Тривиальный («школьный») ответ «чем меньше К, тем точнее формула численного дифференцирования» основан на известном соотношении
Ho» .
н-*о
§2]
ЧИСЛЕННОЕ ДИФФЕРЕНЦИРОВАНИЕ
25
Однако, как мы увидим, при реальных вычислениях ситуация сложнее.
Пусть функция f(x) гладкая, но, работая на ЭВМ, мы имеем дело не с fix), а с ее машинным представлением
где ?(х) — относительная погрешность вычисления /. Разумеется ? зависит ОТ X, HO для всех интересующих нас х пусть имеется оценка |є(х)| є*« 1. Величина е может быть связана хотя бы с ко-
нечным числом знаков в представлении / в памяти ЭВМ (е,« IO-12 на БЭСМ-6, є я» IO-7 на ЕС, ей IO-16 на ЕС при двойной точности). Ho если f(x) вычисляется достаточно сложно, погрешность є может быть и существенно большей величиной, не всегда допускающей хорошую оценку.
Таким образом, используя численное дифференцирование, вычисляем
Погрешность численного дифференцирования состоит из двух частей. Первая из них связана с заменой оператора дифференцирования оператором конечной разности. Она имеет величину 0(fxxh) и стремится к нулю при А -»• 0. Степень А в погрешности аппроксимации называю* порядком аппроксимации. Вторая часть погрешности связана с неточностью вычисления /. Она имеет величину 0(tf/h) и при А -* 0 стремится к бесконечности. Полная погрешность численного дифференцирования есть сумма погрешностей аппроксимации и округления: 0Shfxx + Izflh.
Легко вычислить шаг h0, при котором полная погрешность минимальна. Очевидно, A0 = V41 tf/fxx I . Это грубая оценка: ведь A0 вычисляется через ? и fxx, точные значения которых обычно неизвестны. Существуют достаточно надежные алгоритмы численного дифференцирования, основанные на вычислении большего числа значений /. По этим значениям вычисляются варианты разностной производной, из сравнений которых между собой отбирается наиболее достоверное значение. Надежность подобных алгоритмов оплачивается большим объемом вычислений. Часто, например при реше-
