Введение в вычислительную физику - Федоренко Р.П.
ISBN 5-7417-0002-0
Скачать (прямая ссылка):
Теперь допустим, что метод не сходится, т.е. Iim Xk 5* х* и-Iim гк > 0. По предположению Q — ограниченная замкнутая область, т.е. последовательность {хк}к=0 имеет в Q хотя бы одну точку сгущения х, причем г = Wf(X) Il =Tt 0. Тогда в силу непрерывности г(х) — ||/(х)|| > г/2 в некоторой e-окрестности х. В эту окрестность попадает бесконечное число точек хк; обозначим их хк< (і = 1,2,3,...). Переход от xki к хк-+[ сопровождается падением невязки:
г* +1 < rk. — min (1/(4С), г/4}.
Так как на остальных шагах невязка по меньшей мере не возрастает, получаем явное противоречие. Итак, в каждой точке сгущения /(х) = 0. Доказательство закончено.
Отметим важное обстоятельство: в условиях теоремы 2 по сравнению с условиями теоремы 1 отсутствует предположение о достаточной малости г° («количественное» предположение). Используются только «качественные» предположения о гладкости и невырожденности (взаимной однозначности) отображения х -» /(х). Эти свойства очень важны для существования и единственности решения системы, которые в условия теоремы не включены. Они следуют из сформулирован-ных предположений. He вдаваясь в подробности, заметим, что если гладкая функция ||/(х) ||2 в области Q не обращается в нуль, то она достигает минимума, в котором все ее производные обращаются в нуль. Вычислим их:
,Если не все fi(x) = 0, то det (fx) = 0, что противоречит одному из предположений.
Наконец, важно отметить, что в тех случаях, когда система /(х) = 0 имеет много решений, модифицированный метод Ньютона приводит к одному из них; к какому именно, это зависит от выбора начального приближения. Как говорят, каждое решение имеет свою «область притяжения» — совокупность точек х, стартуя из которых метод Ньютона приводит именно к этому решению.
§ U
РЕШЕНИЕ СИСТЕМ НЕЛИНЕЙНЫХ УРАВНЕНИЙ
17
Методы простых итераций. В некоторых ситуациях применение метода Ньютона может быть затруднено как из-за слишком трудоемкого вычисления матрицы f х, так и из-за необходимости решать систему линейных уравнений. Поэтому наряду с надежным и эффективным методом Ньютона в вычислениях используются и более простые итерационные методы.
Рассмотрим простой пример, поясняющий суть дела. Решается система двух уравнений
Пусть функции / и <р таковы, что из уравнения }(х, .у) = 0 при заданном у легко определяется х, а из уравнения ф(х, у) = 0 определяется у. Тогда можно построить итерационный процесс следующего вида. Если известны хк, у*, то следующее приближение вычисляется так:
1) из уравнения /(х, у*) = 0 находится xk+[\
2) из уравнения ip(x*+J, у)= 0 находится JfiT1,- и т.д. Проанализируем сходимость. Анализ таких процессов проводим
в предположении, что Xі, у* достаточно близки к решению х*, у*, т.е. полагаем
Xk = Xt + дхк, ук = у' + 6ук.
Считая дх, ду малыми, линеаризуем уравнения итерационного процесса. Из
/(х* + 6х*+1, у* + 6/) = 0, ф(х’ + 6х*+1, У + 6ук+1) = О,
Сходимость обеспечивается при: а) достаточно хорошем начальном приближении х°; б) при ||Л||^^<1 (в этом случае ||6z*|| ^
Заметим, что между схемой простых итераций и методом Ньютона есть принципиальное отличие: сходимость метода Ньютона рбеспечивается (при наличии хорошего приближения) чисто качественными факторами — гладкостью / и невырожденностью отображения х -*¦ /. Для метода простых итераций требуется еще важное количественное условие: ||Л|| < 1. При ||Л|| > 1 метод может расхо-
/(*> У) = 0, <р(х, у) = 0.
(4)
получаем линейные соотношения
/х 6х*+1 + /у 6/ = О, 6х*+1 + 6yk+l = 0.
Обозначая dz = (дх, ду), имеем векторное соотношение
IlSz0II).
18
ОСНОВЫ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ
[4-І
даться в сколь угодно благополучном случае при сколь угодно хорошем начальном приближении.
Метод простых итераций в действительности объединяет необозримое количество итерационных методов, которые конструируются по-своему в том или ином конкретном случае. Например, можно одни и те же переменные, входящие в решаемое уравнение, брать один раз «с верхней» итерации, другой раз «с нижней». Поясним суть дела простым примером. Пусть имеется функция F(x, ?), а нужно решить уравнение
/(х) =F(х, х) =0.
Тогда можно построить итерационный процесс вида
F(xk+l,xk)= 0,
конечно, при условии, что из такого уравнения сравнительно легко находится х^+1 при известном хк.
Анализ сходимости приводит к соотношению
Fx 6x*+1 + F4 Ьхк = 0, или 6x*+1 = -FxlFl Ьхк,
и сходимость (в окрестности решения) определяется нормой матри-цы FxlF^: если она меньше единицы, процесс сходится; если она больше единицы, процесс расходится. Очевидно также, что если процесс сходится, т.е. существует Iim Xk = х*, то, переходя к преде-
к
лу в соотношении ^(x*+1, xk) =0, получаем F(x\ х*) =0.
Если в уравнении /(х) = 0 не удается выделить «разрешаемую» относительно X часть, можно ввести ее искусственно и очень просто, например преобразовав уравнение к виду
х — х + а/(х) = 0 и построив итерационный процесс
Х* + 1 = хк _ af(xk).
Строятся такие методы, как видим, легко, но сходимость их не гарантируется и является в известном смысле делом случая.
