Fedorenko-RP-Vvedenie-v-vychislitelnuyu-fiziku (810773), страница 3
Текст из файла (страница 3)
Без труда угадываем общую форму: г Ц С 1(Сг»)з. Именно эту формулу (с показателем 2«) имеют в виду, когда говорят о квадратичной скорости сходимости. Теперь можно более точно указать, насколько хорошим должно быть начальное приближение хз, чтобы процесс заведомо сходился.
Очевидно, для этого достаточно выполнения неравенства СЦ/(х )Ц ж ч< 1. гешеиие систем нелинейных и'хеиеиий ец Можно уточнить и вид области, в которой предполагаются выполненными сформулированные в условиях теоремы оценки пронзводнмх.
Такой областью может быть область, выделенная неравенспюм 1Ях)11 < 1/С. В самом деле, если хе лежит в области С 11д(хе)11 н д< 1, то 11у(х')11 н дг/с и т.ц., т.е. все последующие приближения х» лежат в этой области. Условие 11У„'(х) 11 ж С, существенно.
Оно гарантирует взаимную однозначность (в некоторой области) отображения х- у(х), что, как известно, очень важно для существования и единственности решения системы У(х) = О. Модификация метода Ньютона. Метод Ньютона, являясь весьма эффективным средством уточнения сравнительно хорошего начального приближения, может расходится, если хд — слишком грубое приближение к искомому решению. В схему алгоритма были Рис. 2 внесены изменения, имеющие целью ослабить требования к начальному приближению и сделать сходимость не столь зависящей от его выбора.
Идею такой модификации поясним, начав с геометрической интерпретации метода Ньютона в двумерном случае (и = 2). Итак, пусть решается система У,(хи х ) =О, У (хи хг) О. На рис. 2 изображены плоскости (х„хг) и (Уи Уг). Точка х отображается е точку Уе. В этой точке отображение х- ~(х) линеаризуется, т.е. заменяется отображением А + дх (Х~ Х1) + дх (Хг — Хг) д дд~ е дг~ 1 дхг .~ог+ — (х» — х») + д (хг — хг) 1 И- и находится точка (х'„хг), в линейном отображении переходящая в точку (О, 0).
Однако в нелинейном отображении х- У(х) точка х' отображается не в нуль, а в ~'. 1ч. г основы вычислительной млтемьтикя 14 Изучим непрерывное движение от хз к х' по прямой. Обозначив Ьх х' — хо, рассмотрим отрезок прямой х(з) = хе+ з Ьх„зжО, х(1) = х' (в расчетах обычно берут х(з) = хе+ з Ьх/))Ьх[[). Образ этого отрезка в нелинейном отображении есть кривая У[з[ ~Дх(з)) (см. рис. 2). В точке з = О она касается направления на точку (О, 0).
В самом деле, при достаточно малых з имеем У[э[ =Дх~+ з Ьх) =Уз+ зУ„(хо) Ьх+ 0(зз). В силу У„(хо) Ьх= — Уо функция /[з[ = гз — г ~е + 0(зз) = (1 — з) Уз + О(зз). Другими словами, при малых з точка У[э] движется почти (с точностью до 0(зз)) прямо в начало координат. По мере увеличения з величины 0(з*) возрастают, они могут стать определяющими и существенно отклонить траекторию У[э[ от желаемого движения в начало координат. Теперь очевидно, что нужно двигаться по [хз, х'[ до тех пор, пока точка У[э[ приближается к началу координат, т.е.
шаг з' определяется решением одномерной задачи минимизации. Ищется ш)п [[7(хо+ з Ьх) [[. Точку минимума принято обозначать л виде з' = агя ппп Щх'+ з Ьх) 1[. Итак, сформируем алгоритм модифицированного метода Ньютона (ммн): 1) имеется некоторая точка х; 2) вычисляются /(х) и у„(х); 3) находится Ьх нз системы У + г„бх = О; 4) определяется функция скалярного аргумента сс Г(з) ш Щх+ з Ьх) [[; 5) находится з' = агк ппп Р(з); 6) вычисляется следующее приближение: х:= х+ з' Ьх. гешенне систем нелинейных тг»вненнй 1нп х» = х', » ф 1пп 㻠— — О. » > Доказательство. Отметим очевидный факт: невязки г» монотонно убывают, т.с.
гв> г, » ... г» и ... Следовательно, все х» е й. Оценим величину убывания невязкн г за один шаг, используя со- отношение /(х» + з Ьх) = (1 — з) /(х») + зз О(Ц ЬхЦз), Ьх =,/„'/(х»). Отсюда следует (при з Е 10, 11) г»,, = пнп Ц/'(х" + з Ьх) Ц м ш1п ((1 — з) Ц/(х») Ц + Сз гз»). Онов! Здесь мы оценили ЦО(ЦЬхЦ )Ц и Сз ЦЬхЦ к Сз Ц/ 'Ц Ц /(х )Ц . Таким образом, Г», иш1п Н1 — з)Г + Ся~г~~). о»*»~ Вычислим минимум правой части (игнорируя пока ограничение Оа » и 1). Он достигается в точке з' = 1/(2Сг ), а значение В приведенном алгоритме есть элемент, требующий уточнения, — это решение задачи ппп Р.
Этой задаче посвящен 5 26. Иногда используют совсем простую процедуру дробления шага. Сначала берут значение з = 1 (как в стандартном методе Ньютона). Если окажется, что ЦУ(х+ з Ьх)Ц < Ц/(х)Ц, тозтотшагиостается. В противном случае з заменяют на з/2 и снова сравнивают нормы. И т.д. — до получения со- отношенияЦУ(х+ Ьх/2г)Ц < ЦУ(х)Ц. Докажем теорему о сходнмости модифицированного метода Ньютона. Теорема 2. Определим область й как множество точек, в котовых Ц/(х)Ц «Ц/(хв)Ц. Предположим, что: а) /(х) — гладкая функция и Ц/„х(х) Ц и См х Я й; б) отображение х - /(х) равномерно невырождено и Ц/„'(х) Ц и ж Со Ч х е й; в) й — ограниченная связная область. Пусть х» — точки, последовательно полученные, начиная с хв, согласно модифицированному методу Ньютона, а г — соответствующие невязки (г = Ц/(х )Ц).
Тогда в области й существует единственное решение х' системы уравнений (т.е. /(х') = О) н осиозы вычислительиоа мАтемАтики 1б минимума в этом случае есть г — 1/(4С). Если з" м1, будем использовать зту оценку; если з' > 1, оценим минимум значением в точке »=1, В этом случае г„+, ж Сгз~.
Так как при этом з' = 1/(2Сге) > 1, то Сг~~ < г /2. Итак, в любом случае при переходе от хе к хам невязка убывает не меньше, чем на величину ппп (1/(4С), г /2). Теперь допустим, что метод не сходится, т.е. Вш хь ~ х* и. Вш г„> О. По предположению й — ограниченная замкнутая область, т,е. последовательность (хе)" имеет в 0 хотя бы одну точку сгущения х, причем г Щх)а ~О. Тогда в силу непрерывности г(х) = В/(х) Й > г/2 в некоторой а-окрестности х. В эту окрестность попадает бесконечное число точек х"; обозначим их хе, (1= 1, 2, 3, ...).
Переход от хе~ к х"+' сопровождается падением невязки: гь +, «г — шш (1/(4С), Р/4). Так как иа остальных шагах невязка по меньшей мере не возрастает, получаем явное противоречие. Итак, в каждой точке сгущения /(х) =- О. Докззательсгво закончено. Отметим важное обстоятельство: в условиях теоремы 2 по сравнению с условиями теоремы 1 отсутствует предположение о достаточной малости го («количественное» предположение) . Используются только «качественные» предположения о гладкости и невырожденности (взаимной однозначности) отображения х- /(х). Эти свойства очень важны для существования и единственности решения системы, которые в условия теоремы не включены.
Они следуют из сформулированных предположений. Не вдаваясь в подробности, заметим, что если гладкая функция з/(х) й з в области И не обращается в нуль, то она достигает минимума, в котором все ее производные обращаются в нуль. Вычислим ик: л л ю ! ,Если не все /;(х) О, то бе1 (/„) = О, что противоречит одному из предположений, Наконец, важно отметить, что в тех случаях, когда система /(х) = О имеет много решений, модифицированный метод Ньютона приводит к одному из них; к какому именно, это зависит от выбора начального приближения.
Как говорят, каждое решение имеет свою «область притяжения» — совокупность точек х, стартуя из которых метод Ньютона приводит именно к этому решению. Решение систем нелинейных уРАВнениЙ Методы простых итераций. В некоторых ситуациях применение метода Ньютона может быть затруднено как нз-за слишком трудоемкого вычисления матрицы /„, так н из-за необходимости решать систему линейных уравнений.
Поэтому наряду с надежным и эффективным методом Ньютона в вычислениях используются и более простые итерационные методы. Рассмотрим простой пример, поясняющий суть дела. Решается система двух уравнений У(х, у) =О, р(х, у) =О. (4) Пусть функции г' и р таковы, что из уравнения Дх, у) = О при заданном у легко определяется х, а из уравнения р(х, у) = О определяется у.
Тогда можно построить итерационный процесс следующего вида. Если известны х», у', то следующее приближение вычисляется так: !) из уравнения Дх, у») = О находится х»+'; 2) из уравнения р(х»~', у) = О находится у»+.', и т.д. Проанализируем сходимость. Анализ таких процессов проводим в предположении, что х», у» достаточно близки к решению х', у', т.е.
полагаем х» = к'+ Ьх», у» у'+ Ьу" Считая Ьх, Ьу малыми, линеаризуем уравнения итерационного про- цесса. Из У(х' + Ьх»+', у' + Ьу») = О, р(х" + Ьх»+', у' + Ьу»") = О, получаем линейные соотношения У„ Ьх~~' + У Ьу» = О, р„ Ьх» ' + р Ьу»+' = О. Обозначая Ьг = (Ьх, Ьу), имеем векторное соотношение Ье»+' =А ЬВ», где А= — ~ Сходнмость обеспечивается нри: а) достаточно хорошем начальном приближении хо; б) при 11А11 н д < 1 (в этом случае 11ЬВ»11 ж м «» 11Ь '1!). Заметим, что между схемой простых итераций и методом Ньютона есть принципиальное отличие: сходимость метода Ньютона обеспечивается (при наличии хорошего приближении) чисто качественными факторами — гладкостью г' и невырожденностью отображения х- г. Для метода простых итераций требуется еще важное колячественное условие: 11А11 < !.
При 11А11 > ! метод может расхо- ОСНОВЫ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ !В У(х) ш Р(х, х) = О. Тогда можно построить итерационный процесс вида Р(х»+', х») =О, конечно, при условии, что нз такого уравнения сравнительно легко находится х»+! прн известном х». .Анализ,сходимости приводит к соотношению илн Ьх» ' = — Р,'Р Ьх», « Р„Ьх»+' + Р! Ьх» = О, и сходимость (в окрестности решения) определяется нормой матрицы Р,!Р»! если она меньше единицы, процесс сходится; если она больше единицы, процесс расходится.
Очевидно также, что если процесс сходится, т.е. существует Еш х» = х', то, переходя к преде» лу в соотношении Р(х»+', х") = О, получаем Р(х', х') = О. Если в уравнении /(х) = О ие удается выделить «разрешаемую» относительно х часть, можно ввести ее искусственно н очень просто, например преобразовав уравнение к виду х — х+ аУ(х) =О и построив итерационный процесс х»'! = х» — айх»).
Строятся такие методы, как видим, легко, но сходимость их не гарантируется н является в известном смысле делом случая. Заметим еще, что существуют теоремы, обосновывающие правомерность пренебрежения членами второго порядка: если метод сходится в теории «первого приближения», т.е. норма соответствующей матрицы !! А!! «е < 1, то прн достаточно хорошем начальном приближении метод действительно сходится. Метод Ньютона в специальных ситуациях. Часто приходится решать уравнение У(х) = О в специальной ситуации, когда функция задана не формулами, а алгоритмом, н достаточно сложным. Други- днться в сколь угодно благополучном случае при сколь угодно хорошем начальном приближении, Метод простых итераций в действительности объединяет необозримое количество итерационншх методов, которые конструируются посвоему в том или ином конкретном случае.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
