Федоренко Р.П. Введение в вычислительную физику (Федоренко Р.П. Введение в вычислительную физику.djvu), страница 3

+ — Ьх„. е Отсюда следует расшифровка: ау ау' дх, дх„ ау„ау„ ах, "' ах„ 2. В теоретических оценках будем использовать явную форму Ьх= — У„1У, хотя практически обычно находят матрицу у„, формируют систему линейных алгебраических уравнений (3) н решают ее с помощью стандартной программы. Так поступают в том случае, когда размерность задачи л сравнительно невелика. В дал1 нсйшем мы встретимся с ситуациями, когда ду настолько велико, что применение стандартных методов решения линейных систем невозможно нлн по крайней мере нерационально. Обычно в таких у-у <х) ситуациях матрица у„ имеет специальную структуру, н часто удается з- х1 построить специальные методы реше- хд ння, существенно более эффективные, чем общие. При п = 1 метод Ньютона известен как «метод касательных».

Этот термин поясняет рис. 1. Линеарнзация состоит в том, что кривая у = /(х) заменяется касательной, проведенной в уже най- Рнс. ! денной точке х», а в качестве следую' щего приближения х" +' берется пересечение касательной с осью абсцисс. На рис. ! показано несколько таких итераций и, естественно, возникает предположение о том, что процесс должен быть достаточно эффективным. Это и подтверждается более точным исследованием. [ч.

ь !2 ОСНОВЫ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ Скоднмость метода Ньютона. Докажем теорему о квадратичной сходимости метода. Теорема 1. Пусть х' — решение системы (1). Предположим, что в некоторой окрестности х". а) Г (х) является гладкой функцией в том смысле, что существуют ее производные до второго порядка и имеет место оценка ЦУ„„(х)Ц а С; б) отображение х- г(х) равномерно невырождено в том смысле, что г„'(х) существует и ограничена: Цг'„'(х) Ц к Сг Тогда, если начальное приближение хО достаточно близко к х', метод Ньютона сходится и имеет квадратичную скорость сходимости.

Точный аналитический смысл выражений «квадратнчная скорость скодимости», «х« достаточно близко к х'», «Цг',„Ц ц СВ» выяснится в процессе доказательства. Доказательство. Будем следить за эволюцией в процессе итераций величины Цг(хь)Ц (нормы невязкн). Установим связь между Щх"+')Ц и Щх )Ц: г(х"+') = г(х«) + г„(х") Ьх+ О(ЦЬЛЦз).

Используя выражение Ьх = -1„'(хь) г(х") и оценку ЦО(ЦЬхЦз) Ц ж < Сз Ц ЬхЦз (именно в этом смысле поннмаетсв пРсдположение а) теоремы), получаем У(хь+') = О(ЦЬхЦВ) = О(Цу„г Дз), откуда ЦУ( "') Ц ц С, Цу-' д!' < С,С', Цу(х') Ц', Обозначая г„= Щх«)Ц, имеем основное соотношение: ,мСгз, где С=С,С',. Эта оценка порождает следующую цепочку: г, ц Сг~«, гтрк Сг1 ж Сзг~з, гз» Сгз~ж С г«. Без труда угадываем общую форму: г Ц С 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).