Буслов, Яковлев - Введение в численный анализ (947494), страница 11

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 11)

Действительно, (У')' — О" УХ" (п)г (уг)г то если х. корень кратности о, то в его окрестности У(х) - а(х — х.) и, следовательно, Г'(х.) = =' . Заметим, что если х ] простой корень, то сходимость метода касательных квадратичная (то есть порядок сходимости равен 2). н* ) Убедимся в этом. Поскольку х ег — х = х — х — — т-;~ —, то х г.1 — х. 1 )'(х ) 1 (х, -х.)г х, — х. )г(х,)(х, -х.)г х, — х. г (х )(х, — х ) + -'1 (х )(хг — х,) т о [(х, — х.) ) (х, — х.)г [Г(х.) + у»(х,)(х, — х.) + о(х, — х.)] откуда Таким образом, если производная меньше единш1ы. то Г является сжатием.

Условие Г([а,Ь]) С [а,Ь] суп1ественно, ибо если, например, Г(х) = 2 на [О,Ц, го неподвижная точка отсутствует, хотя производная равна нулю. Скорость сходимости зависит от величины о . с1ем меныпе о, тем быстрее скодимость. Пример. Решить уравнение: х = а . Здесь, если в качестве Г взять функцию Г(х) = '— ', то соответствующая г Таким образом сходимость метода Ньютона очень быстрая. При этом без всяких изменений метод обобщается на комплексный случай. Если корень х.

является корнем второй кратности и выше, то, как нетрудно убедиться, порядок сходимости сразу падает и становится линейным. К недостаткам метода Ньютона следует отнести его локальность, поскольку он гарантированно сходится при произвольном стартовом приближении только если везде выполнено ~О" ~/(г"' ) С 1, в противной ситуации сходимость есть лишь в некоторой окрестности корня.

Другим недостатком метода Ньютона является тот факт, что на калсдом шаге необходимо заново вычислять производную. 5.1.3 Метод секущих Чтобы взбежать вычисления производной, метод Ньютона можно упростить, заменив производную на разностную, вычисленную по двум предыдущим итерациям, что эквивалентно замене функции 7(х) на интерполяционный полипом, проходящий через точки х и х, 1 . При этом итерационный процесс принимает вид Л(хз — х~ 1) Л вЂ” Л-1 где 1" = у(х ) . Это двухшаговый итерационный процесс, поскольку использует для нахождения последующего при- ближения два предыдущих. Порядок сходимости метода секущих естественно ниже чем у метода касательных и равен в случае однократного корня И = хкх-' .

Убедимся в этом считал для удобства, что х. = О . ~Ц.'х, + 17',"х, + 0(х~))(ху — х, 1) Л (хз хз -1) Л вЂ” Л- 11(х — х, ) т 1~;"(хэ — хз,) + 0(хз — хз,) Таким образом с точностью до бесконечно мшгых более высокого порядка Л (х1 хз — ! ) ~'*" х,ы=х,—,, = — *„,х,х, ~+0(х,) Л вЂ” Л ~ йу'. Отбрасывая остаточный член> получаем рекурентное соотношение хз<.~ = ах хз 1, о = —,*,, решение которого естественно искать в виде хз.г~ = о'хз . После подстановки имеем: о) = 1 н и' — с) — 1 = О, откуда в силу того, что 4 з для сходимости необходимо.

чтобы 4 было положительным, заключаем что д = ' зт' . 3 Поскольку знание производной не требуется, то при том же объеме вычислений в методе секущих (несмотря на меньший порядок сходимости) можно добиться большей точности, чем в методе касательных, Отметим, что вб~шзн корня приходится делить ва малое число и это приводит к потере точности (особенно в случае кратных корней), поэтому выбрав относительно малое б выполняют вычислении до выполнения ~хз~.1 — х ~ с Б и продолжают их пока модуль разности соседних приближений убывает. Как только начнется рост, вычисления прекращают и последнюю итерацию не используют.

Метод секущих становится неприменимым. Такая процедура определения момента окончания итераций называется приемом Гарвпка. Метод парабол Рассмотрим трехшаговый метод, в котором приближение х,з.~ определяется по трем предыду|пим точкам х,, х, и х, з . Для этого заменим, аналогично методу секущих, функцию Л(х) интерполяционной параболой проходящей через точки хз, хз 1 и хз з . В форме Ньютона она имеет внд рэ(х) =Л+Л 1п(х — х,)+Л зо кз(х — х,)(х — х, 1) 57 Точка хзэ1 определяется как тот из корней этого полинома, который ближе по модулю к точке тз .

Порядок сходимости метода парабол вьппе, чем у метода секущих, но ниже, чем у метода Ньютона. Важным отличием от ранее рассмотренных методов, является то обстоятельство, что даже если г(х) вещественна при вещественных в и стартовые приближения выбраны вещественными, метод парабол может привести к комплексному корню исходной задачи. Этот метод очень удобен для поиска корней многочленов высокой степени. Поиск всех корней Общим недостатком гючти всех итерационных методов нахождения корней является то, что они при однократном применении позволяют найти лишь один корень функции, при том неизвестно какой.

Чтобы найти другие корни, можно было бь1 брать новые стартовые точки и применять метод заново, ио нет никакой гарантии, что при этом итерации сойдутся к новому корню, а не к уже найденному (еслн вообще сойдутся, как скажем возможно в методе Ньютона) . Для поиска других корней используется метод удаления корней. Пусть з1 корень функции у(т) .

рассмотрим функцию г1(т) = ~~"~ . Точка х| будет являться корнем функции г1(х) на единицу меньшей кратности, чем г(х), при этом все остальные корни у функций 1'(т) и 11(т) совпадают с учетом кратности. Применяя тот или иной метод нахождения корней к функции 11(х), мы найдем новый корень зз (который может в случае кратных корней *,)Л р р ф Ы)=~.~=...„',, р, юп рг указанную процедуру мовсио найти все корни 1(з) с учетом кразиостн. Заметим, что когда мы производим деление на тот или иной корень в., то в действительности мы делим лишь на найденное приближение з'. и тем самым несколько сдвигаем корни вспомогательной функции относительно истинных корней функции 1(з) .

Это может привести к значительным погрешностям, если процедура отделения применялась уже достаточное число раз. Чтобы избежать этого, с помощью вспомогательных функций вычисляются лишь первые итерации, а окончательные проводятся по исходной функции 1(з), используя в кызестве стартового приближения, последнюю итерацию, полученную по вспомогательной функции. 5.1.4 Многомерный случай Метод простых итераций Метод простых итераций (последовательных приближений) легко обобщается на случай системы нелинейных уравнений ~ь(тыве,...,хи) = О, й = 1,2,,%, или в векторной форме з(х) = О . Эту систему удобно как и в одномерном случае записать в виде задачи на неподвижную точку Р(х) = х Замечание. Нахомсдеиие такой формы записи может оказаться само по себе серьезной задачей. Необходимо добиться и того, чтобы отображение Р являлось сжатием (для схо„щмости итераций) в, прн этом было эквивалентно исходной постановке.

Выбрав стартовое приближение, организуем итерации хо+ ~ = Р(хб1) 58 Если итерации сходятся, то они сходятся к одному из решений системы уравнений. Порядок сходямости простых итераций линейный. Действительно, пусть х решение, к которому сходятся итерации, тогда для каждой Й-ой его компоненты хе"'-х„=Р,(хб') — Рь(х ) =У "(') (х',"-г,*), 1=! где яэ некоторый вектор в направлении хО~ — х" лежащий между этими точками. Отображение Р будет являться (эк, о" ~ 1 сжатием, если норма матрицы производных (согласованная с нормой вектора в данном пространстве) меньше единицы.

Поскольку в конечномерном пространстве все нормы эквивалентны (а значит и последовательность сходящаяся по одной норме, будет сходиться и по любой другой), то достаточно это условие проверить для любой из эг норм матрицы с элементами Мм = шах ~~е„~, мажорирующей соответствующие нормы ( э Улучшить сходимость метода последовательных приближений, можно (хотя она по прежнему останется линейной) Ото если уже найденные компоненты гб~ использовать для нахождения компонент этого же приближения хп+П с номерами большими к, то есть организовать итерации следующим образом хб+ ~ Р сгб+» хо+ хе+ х» х~» х»1 Метод Ньютона Метод Ньютона, являясь частным случаем метода простых итераций с вектор-функцией Р равной естественно обобщается на многомерный случай.

Итерации по методу Ньютона имеют вид <+П <~ дг"(х) <> дх = о~ Проверка условий сходимости (то есть того, что норма матрицы производных дР/дх меньше единицы) почти никогда не производится, поскольку требует большого объема вычислений. Сам же метод Ньютона обычно используют в несколько другой записи. Именно ! Ьхе~ = -Г(хб~) Ьхб~ = хб+П вЂ” хб~ дх — <й Определяя из этой линейной системы (скажем методом Гаусса) вектор анхо~ и, соответственно, приближение хоэо, заново расчитывают матрицу производных и продолжают итерации. Если начальное приближение выбрано удачно, то обычно достаточно всего нескольких итераций, поскольку сходнмость квадратичная.

Методы спуска Введем функцию Ф = ~ ~Д (х)~~ . Она ограничена снизу нулем и достигает своего глобального минимума (нуля) э=1 только в тех точках, где Г(х) = О . Таким образом задача на поиск корней вектор-функции сводится к зада эе на поиск минимума скалярной функции многих переменных, методы решения которой мы рассмотрим в соответствующей главе. Здесь лишь отметим, что этн методы называются методами спуска, и являются сходящимися Лдя гладких функций, однако точность нх невелика, и поэтому их естественно использовать для нахождения начального приближения с последующим использованием метода Ньютона.

Важно также иметь в виду, что методы спуска могут сходится не к глобальному минимуму, а к одному из локальных (в зависимости от выбора стартовой точки), не отвечающих разумеется корням исходной задачи. 5.2 Решение линейных систем 5.2.1 Обусловленность линейных систем, погрешность При решении абстрактной задачи Ах = Ь, где А — оператор произвольной природы важным моментом является корректность ее постановки. Задача считается корректной если решение существует и единственно и, кроме того, решение непрерывно зависит от входных данных (то есть, при тзЬ -+ О, Ьх также стремится к нулю).

Однако и непрерывная зависимость от входных данных может иметь свои нюансы. Чем меньшее (болывее) изменение решения вызывает вариация входных данных, тем более хорошо (плохо) обусловленной считается задача. Понятие обусловленности является тем более существенным для численных методов, поскольку на практике входные данные известны как правило с некоторой погрешностью. Кроме того, существуют ошибки округления, возникающие при вычислениях. Таким образом формально корректная задача, являясь плохо обусловленной, может оказаться разрешимой столь неточно, что в этом будет отсутствовать практический смысл. Чем можно охарактеризовать количественно обусловленность для линейных систем? Пусть А — квадратная Х х Х-матрипж Рассмотрим задачу Ах = Ь Пусть также О * 'О - есть какая-нибудь норма в Гь~ (например ОхО=шах(х,(, = ~ )х,), = ~/Ях,-").

Характеристики

Список файлов книги