Амосов А.А., Дубинский В.А., Копченова Н.В. Вычислительные методы для инженеров (1994) (1095853), страница 23
Текст из файла (страница 23)
2 с) Пусть х'и) Е (х — о, х + о), где о = ппп (бо, — ). Подставляя х = х в (4.38), получим равенство О = ~(х'и) ) + ~'(х'"')(х — х) и) ) + в котором С е (х — о, х + о). Вычитая из него равенство (4.36), имеем 107 Здесь ( — некоторая точка, расположенная между х и х'"'. Заменяя в уравнении ~(х) = О функцию ~(х) главной линейной частью разложе- ний (4.38), получим линейное уравнение ~"(~)(х хг и) )а 2 ~ хггг) х~ < ~хг гг) хсзр-)) ! (4.42) справедливость которой обосновывается следующим утверждением. Т е о р е м а 4 7. Пусть выполнены условия теоремы 4.6 и хоп Е б (х — —, х + — ).
Тогда для всех и ~ 11 верна огьенха (4.42). 2' 2' гг-г и Из оценки (4.41) следует, что )хг" г) — х~ < сгв2 ( <вд = ~хго)— — х~ < —. Поэтому, применяя неравенство (4.40), получим цепочку неравенств 2~х'"' — х~ < 2в ) ~хг" г' — х)э < ~ хг" '' — х~ < ~ хггг г' — х' ™ ~ + ~ хг") — х), из которой вытекает оценка (4.42). И Наличие оценки (4.42) позволяет сформулировать следующий практический критерий окончания итераций метода Ньютона.
При заданной точности е > 0 вычисления нужно вести до тех пор, пока не окажется выполненным неравенство )х[п) хггг-г) ~ < Е (4.43) !!ример 4.8. Используя метод Ньютона, найдем с точностью Е = 10 в положительный корень уравнения 4(1 — ха) — ех = О. В примере 4.2 корень был локализован на отрезке [0, 1). Для 1с(х) 108 Тогда, приравняв модули обеих частей этого равенства и используя условия ограниченности ~~'(х) ~ и )Г'(х) ~, приходим к неравенству сг~хга+г) — х~ ~ — ~хггг) — х~'2, откуда следует справедливость оценки (4.40). Доказательство теоремы завершается применением леммы 4.2.
° Таким образом, при выборе начального приближения из достаточно малой окрестности корня метод Ньютона сходится квадратично. Это означает, грубо говоря, что на каждой итерации число верных цифр приближения примерно удваивается. Приведенные в теореме 4,6 оценки погрешности являются априорными (см. ~ 3.3) и их использование в практике вычислений для количественной оценки погрешности неэффективно или чаще всего невозможно. 4. Критерий окончания. На практике предпочтительнее использование простой апостериорной оценки = 4(1 — х~) — е* имеем Г"(х) = -8х — ех. Очевидно, что 7"'(х) ,-( О, т. е. х— простой корень, Возьмем начальное приближение х( ® = О. 5 и будем выполнять итерации метода Ньютона по формуле 4(1 (х( и) )2) ех(')) 8х(и) + ех(и) результаты первых итераций с 10 знаками мантиссы приведены в табл.
4.4. Таблица 44 ~ х(и) х(и-1) ~ х' "' 0.5000000000 0.7392185177 0.7042444088 0.7034399951 0.7034395712 2.4.10 1 3.5 ° 10 2 8.0 10 а 4.3- 10 г При и = 4 вычисления следует прекратить и после округления получим х = 0.703440 х 0.000001. 4( и+1) — 4( и) — х( и) 1 (х(и) )р а р(х'и))Р 1 р Р(х("')Р( (4.44) При р = 2 эта формула уже была получена в примере 3.17. 5. Связь с методом простой итерации. Метод Ньютона можно рассматривать как один из вариантов метода простой итерации, связанный со специальным преобразованием уравнения 7" (х) = 0 к виду 109 Сравнение результатов итераций со значением х показывает, что приближения х'1', х'2', х(з' содержат 1, 3, 8 верных значащих цифр соответственно.
Можно показать, что приближение х'~) содержит 10 верных цифр. Это подтверждает отмеченный ранее общий факт: при каждой итерации метода Ньютона число верных значащих цифр примерно удваивается. Пример 4.9. Используя метод Ньютона, 'укажем итерационный процесс р— вычисления /а, где а > О, р — натуральное число. Р По определению, х = ~а — это неотрицательная величина, удовлетворяющая равенству хр = а. Таким образом, задача сводится к вычислению положительного корня уравнения Р(х) = О, где Р(х) = хр — а.
Итерационная формула метода Ньютона примет вид х= 1о (х), Ф (4.45) где у (х) = х — ~(х)/~'(х). В самом деле, итерационная формула мето>>> да простой итерации х<п" > = >р.(х' ">) совпадает с формулой (4.37). Ф Исходя из этого с учетом оценки (4.19), можно было бы сделать вывод о том, что метод Ньютона сходится только линейно. Однако Х"( ) заметим, что ~р (х) = г (х), . Так как ~(х) = О, то ~р (х) = О и ю У'( ))' >>г величина а'"'г> = ~у'(~г ">)~, определяющая в силу равенства (4.20) коэффициент сжатия ошибки, стремится и нулю при и ~ м. Скорость сходимости возрастает по мере приближения к корню, отсюда и ее сверхлинейный характер. В качестве аналога теоремы 4.4 для метода Ньютона приведем следующий результат. Т е о р е и а 4.8.
Пусть ~а, о] — отрезок локализации простого корня х уравнения (4.1). Предположим, что на зтом отрезке функция ~ дважды непрерывно дифференцируема, а ее производные 1'(х) и >"(х) знакопостоянны, Пусть хгс> б '>а, о] — произвольное начальное приближение, и в случае >" (хг»>) 1"(х'о>) ( О выполнено дополнительное условие х'" 6 '>а, Ц (первое приближение не выходит за пределы отрезка локализации). Тогда начиная с п = 1 итерационная последовательность метода Ньютона х'"' сходится к х монотонно с той стороны отрезка >а, о], где ~(х) 1"'(х) > О.
Иллюстрацией монотонного характера сходимости может служить рис. 4.9. С л е д с т в и е, Пусть уравнение > (х) имеет корень х, функция >'(х) дважды непрерывно дифференцируема на всей числовой оси, а ее производные 1"' и Г знакопостоянньг. Тогда метод Ньютона сходится при любом начальном приближении хг ш (т. е. является глобально сходягцимся), причем начиная с и = 1 последовательность сходится монотонно с той стороны от корня, где 1(х) ~"(х) > О. 6.
Трудности использования Простота, логическая стройность и высокая скорость сходимости делают метод Ньютона чрезвычайно привлекательным. Однако для его практического применения нужно преодолеть две существенные трудности. Одна из них состоит в необходимости вычисления производной 1'(х). Часто бывает невозможно найти аналитическое выражение для 7"'(х), а определить приближенное значение с высокой точностью очень трудно. Иногда вычисление 110 1 (г) — вполне реальная, но весьма дорогостоящая операция. В этих случаях приходится модифицировать метод, избегая непосредственно— го вычисления производной.
Некоторые из таких модификаций приведены в з 4.7. Более существенно то, что метод Ньютона обладает, вообще говоря, только локальной сходи постыл, Это означает, что областью его сходи- мости является некоторая малая г-окрестность корня х и для гарантии сходимости необходимо выбирать хорошее начальное приближение, попадающее в эту ~т-окрестность. Неудачный выбор начального приближения может дать расходящуюся последовательность (рис.
4.10) и даже привести к аварийному останову (если на очередной итерации 1'(х' "') м О). Для преодоления этой трудности часто используют метод Ньютона в сочетании с каким-либо медленно, но гарантированно сходящимся методом типа бисекции. Такие гибридные алгоритмы находят в последнее время широкое практическое применение. Рис 4.10 7. Влияние погрешности вычислений. Пусть х — простой корень. Если метод Ньютона рассматривать как вариант метода простой итерации, связанный с преобразованием уравнения 1(ю) = 0 к виду (4.45), то можно воспользоваться результатами ~ 4.4 и ~ 4.5.
Поскольку у '(х) = О, справедливо неравенство (4.30) и радиус Ж интервала неопределенности корня х равен примерно Ь(у*). В оценках (4.32) — (4.34) можно считать я* - Ь(ут') и С = 1. Для того чтобы сделать окончательные выводы, остается оценить Л(р*). Пусть ~* и (1"') * — приближенные зйачения функций ~ и <", вычисляемые в малой окрестности корня х. Будем считать, что производная 1' вычисляется хотя бы с точностью до 1 — 2 верных значащих цифр. В противном случае 1особенно, если неверно определяется знак ~') из геометрического смысла метода легко понять, что его применять не следует. В силу предложения 2.5 в малой окрестности корня имеем Так как <р" (х) = х 9 ...то, учитывая погрешность и [к[ем, У'( ) Л (У') *( )' вносимую в <о* вследствие выполнения операции вычитания, получим У <~4о*) е+ [х[е„. Таким образом, преобразование уравнения Ях) = 0 к виду (4.45) практически не меняет обусловленность и радиус с интервала неопределенности корня х.
Итерационный процесс Ньютона дает возмож- ность вычислить решение с точностью е ) я. Отметим, тем не менее, что эти достоинства метода Ньютона реализуются, вообще говоря, только в малой окрестности корня. $4Л. Модификации метода Ньютона В предыдущем параграфе в качестве недостатка метода Ньютона была отмечена необходимость вычисления значения производной у'(х) на каждой итерации. Рассмотрим некоторые модификации метода Ньютона, свободные от этого недостатка. Заметим, что, по существу, излагаемые в этом разделе итерационные методы решения нелинейного уравнения на каждой итерации используют некоторую процедуру его линеаризации, т.
е. исходное нелинейное уравнение заменяется приближенно более простым линейным уравнением. 1. Упрощенный метод Ньютона. Если производная ~'(х) непрерыв- на, то ее значение вблизи простого корня х почти постоянно. Поэтому можно попытаться вычислить 1' лишь однажды в точке х<о<, а затем заменить в формуле <'4.37) значение ~'(х< "~) постоянной 1'(х<о)).
В результате получим расчетную формулу уарощснно<о ~иетпода Ньютиона: 112 (4.46) Геометрическая иллюстрация метода приведена на рис. 4.11. В точке (х'о' 1(хгог)) к графику функции у = 1(х) проводится касательная !о и за приближение х' г ' принимается абсцисса точки пересечения этой касательной с осью Ох (как в методе Ньютона). Каждое следующее приближение х' "" получается здесь как абсцисса точки пересечения с осью Ох прямой, проходящей через точку Мг пг с Рис.,г.11 координатами (х<п> 1(хгп')) и параллельной касательной !о. Упрощение вычислений по сравнению с методом Ньютона достигается здесь ценой резкого падения скорости сходимости. Сходимость этого метода является уже не квадратичной, а линейной.
Метод (4.46) можно рассматривать как метод простой итерации с итерационной функцией ~р(х) = х —, „, . Так как аг (х) = 1— — то для знаменателя о соответствующей геометрической .г" ( х) у'(хг ог ) ~ прогрессии имеем г~ ~ 1 —,,о, . Следовательно, скорость сходи- 1'( ) мости тем выше, чем ближе начальное приближение хг ог к решению х. 2. Метод ложного положения. В основе этой и следующих двух модификаций метода Ньютона лежит приближенное равенство (4.47) Оно верно при условии г'"' ~ х<пг и следует из определения произ- ~(г) — 1 (х) водной: 1'(х) = Пш ~+х х — х Пусть с — фиксированная точка, расположенная в окрестности простого корня.
х. Заменим в расчетной формуле метода Ньютона (4.37) производную 1'(х'и>) правой частью приближенного равенства (4.47), полагая л'пг = с. В результате придем к расчетной формуле метода ложного положения: 113 с- х'"' Х( а+1) — Х( и) ~(х("'), п ~ ~О. У(с) — У (х'"') (4.48) Геометрическая иллюстрация метода приведена на рис. 4.12. Очередное приближение х("") получается здесь как абсцисса точки пересечения с осью Ох прямой, проведенной через расположенные на графике функции у = 1 (х) точки М и М(") с координатами (с, ~(с)) и (х'"', Ях("))).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
