II Иванова Е.Е Дифференциальное исчисление функций одного переменного (1081372), страница 47
Текст из файла (страница 47)
! И Л Л Здесь и и р — наибольшее и наименьшее значения положи- тельной производной ~'(х) на отрезке [а, ф Отсюда )1х1х)) < д = тах()1 — -/, )1 — — )) . Из условия ~1 — и/Л~ = ~1 — )ы/Л~ имеем Л = (и+ ус)/2 и 41 = = (и — р)/(и+р), что обычно несколько лучше, чем д=1 — т/М. Помимо (11.21) есть и другие способы эквивалентного преобразования (11.1) к виду (11.16). Среди них выделим способ, обеспечивающий 1р'(х') = О. Тогда по мере приближения х„к х' растет скорость сходимости метода при его хорошей обусловленности.
Пример 11.5. Извлечение квадратного корня из числа а > > 0 можно представить как решение уравнения ~(х) = хг — а = О. Приведем его к виду (11.16) преобразованием хг = а+ хг — хг, или 1 а 1 а г х = 1р(х) = — (х + †) = — ~Гх — — + ~/а. ~11.24) 2 х 2 х На рис. 11.4 показаны графики левой и правой частей (11.24), причем ~р'(/а) =О. При любом нулевом приближении хо >0 последовательность (х„) с элементами 1 а Хи = ~Р(Х22-1) = — Хи-1+ 2 " х„-~ 11.Б. Метод простой итерации Рис.
11.4 начиная с х1 — — (хо+а/хо)/2, монотонно сходится к пределу х = ~/а, так как (~/х — ~/а/х)~ > О Ух > О. Она построена древнегреческим математиком, энциклопедистом античной прикладной математики Героном Александрийским (1 в. н.э.) и носит его имя. Основанный на этой последовательности итерационный алгоритм используется в современных ЗВМ. Если на и-й итерации относительная погрешность б„= ~х„— х'~/х' << 1, т.е.
х„= (1+б„)х', то с учетом 1/(1+б„) ж1 — б„+б2 — Я и х' = ~/а 1/ а х„+1 — — — ~(1+ б„)х'+ (1+ б„)х'~ и б„+1 — ~х„+1 — х'~/х' = б~/2. Отсюда следует, что число верных десятичных знаков в искомом значении х' примерно 382 11. РЕШЕНИЕ НЕЛИНЕЙНЫХ УРАВНЕНИЙ 11.7. Метод Ньютона Естествен вопрос: можно ли ускорить процесс уточнения значения х корня (11.1) по сравнению с методом простой итерации, используя дополнительную информацию о функции Дх)? Если ~(х) дважды непрерывно дифферениируема в некоторой окрестности 0(х ) корня х', то положительный ответ на этот вопрос дает применение метода Ньютпона (или метиода касательных). линеариэуем Дх) в окрестности точки х„1 е ~1(х ), приближенно заменив дугу графика функции ~(х) касательной к нему в точке М„1 (рис.
11.5, а): Дх) ~ ~(х„1) + ~'(х„1) (х — х„1). Приравнивая правую часть нулю, получаем следующий после х„1 элемент итерационной последовательности (х„) с но- мером и: Дха-1) р( )~ (11.25) равный абсциссе точки пересечения касательной с осью Ох. Отметим, что если в (11.21) выбирать параметр А на каждой итерации из условия ~р'(х„~) = 1 — ~'(х„1)/А = О, то получим А = ~'(х„д) и затем (11.25), т.е. метод Ньютона является обобщением метода простой итерации, если в (11.21) принять д(х) = х — ~(х)(~'(х). Тогда ~р (х) = Дх) (П.26) удваивается за очередную итерацию. Так, при а=4 и хв- — 1 получим х1 — 2,5000 (один верный знак); х2 — — 2,0500 (два верных знака); хз —— 2,0001 (четыре верных знака) и т.д.
383 11.7. Метод Ньютона Рис. 11.5 и по мере приближения х к х' ~(х) ~ ~(х') = О, так что ф(х) тоже стремится к нулю, дополнительно ускоряя сходимость (х„~. В силу формулы (7.19) Тейлора с остаточным членом в форме Лагранжа ~(х') = О = ~(х„ 1) + ~'(х„ 1)(х' — х„ 1) + + — (х' — х„1), (11.27) ~н(х) 384 11.
РЕШЕНИЕ НЕЛИНЕЙНЫХ УРАВНЕНИЙ где х заключено между х' и х„1, или у(х -1) у (х), 2 У'(х„1) 2~'(х„1) Вычитая отсюда почленно (11.25), получаем ~х х„~ — (х х„1) < С~х х„1~, у"(х) . 2 < . 2 2У хэъ-1 где С = шах~~"(х)~/пнп ~2~'(х)~ при х Е У(х'), что соответствует (11.12) при р=2. Итак, в случае простого корня х' Щх') ф О) существует окрестность Щх'), в которой метод имеет кеадратпичную скоростпь сходимостпи.
В силу теоремы 10.4, если радиус б этой окрестности удовлетворяет условию С6 < 1, то для погрешности справедлива оценка (11.14), и итерационная последовательность (х„) не выходит из указанной окрестности. В окрестности с радиусом о/2 ~х„1 — х'~ < о/2, и с учетом С< 1/о и неравенства (1.4) ~1~ имеем 2~х„— х'~ < 2С~х„1 — х'~~ < -~х„1 — х'~~ < < ~х„1 — х'~ < ~х„1 — х„~+ ~х„— х'~. Отсюда ~х„— х'~ < ~х„~ — х„~, т.е. у значения х„верны все совпадающие с х„1 десятичные знаки. Метод Ньютона обладает лояа.яьной саодамомоствью в том смысле, что для его сходимости необходимо хорошее начальное приближение хо, попадающее в окрестность радиуса о.
Однако ответ на вопрос, включает ли эта окрестность отрезок локализации корня х или принадлежит ли ей выбранное значение хо, на практике далеко не всегда возможен. Подойдем к этому вопросу иначе. Итерационная последовательность (х„) сходится к пределу х' мокошокмо, если О«, 1. х — хв 1 386 П. РЕШЕНИЕ НЕЛИНЕЙНЫХ УРАВНЕНИЙ х =х Р(хо) (11.28) так как при знакопостоянстве ~"(х) на отрезке между х' и х„шах Д'(х)~ = ~,~'(хв)~, что гарантирует монотонную сходимость (х„) к х' (рис.
11.6,б). Построение (х„), согласно (11.28), характеризует упрощенный метиод Ньютона. Он имеет линейную скорость сходимости, так как совпадает с методом простой итерации при выборе в (11.21) А = ~'(хо) =сопМ, и применим, например, для двустороннего приближения к значению корня х' четной или нечетной кратности т> 2 (рис. 11.6,в и г).
11.8. Комбинированные методы Каждый из рассмотренных методов численного решения (11.1) имеет определенные ограничения. Поэтому иногда хорошие результаты дает сочетание двух (реже трех) методов одновременно. Характерным примером является комбинация упрощенного метода Ньютона и метпода секущих, который является также модификацией метода Ньютона: в (11.25) ~'(х„1) заменяют на разделенную разность первого порядка Для сохранения квадратичной скорости сходимости в случае корня кратности т следует в (х„) положить х„= х„1— -т~(х. 1Я(х.
1). Для метода Ньютона как обобщения метода простой итерации при условии <р'(х') ф О радиус интервала неопределенности я~Ь, =ЛАЯ'(х')~ совпадает со значением е в (11.15), и в данном случае преобразование (11.1) к виду (11.16) не влияет на обусловленность метода. Если вычисление производной ~'(х„1) в (11.25) громоздко, то при выполнении достаточного условия сходимости метода Ньютона в (х„) можно принять 387 11.8. Комбинированные методы (Дх„~ ) — ~(х„г) ) /(х„1 — х„г) и получают (11.29) Метод секущих двухшаговый, и для построения итерационной последов атпельноспьи (х„~ необходимо сначала располагать двумя приближениями хо и х1 к значению х' искомогокорня.
Если на отрезке ~а, 6] локализации этого корня функция Дх) дважды непрерывно дифферениируема и г" (х) знакопостоянна, то целесообразно за хо принять тот конец [а, 6~, на котором знаки ~(х) и ~в(х) совпадают, а за аУ(6) — 6|(а) Д6) — ~(а) (11.30) ~н(х') Дх„1) т ~'(х') (х„1 — х') + (х„1 — х') 2 ,~" (х') 1(х„-г) У (х )(х -г х')+ (х„г — х') 2 и подставим в (11.29). В итоге, пренебрегая бесконечно малыми более высокого порядка при х„1 -+ х' и х„г -+ х', получаем х„— х' = с(х„1 — х') (х„г — х'), с =, . (11.31) Подставляя в (11.31) х„— х'=с~(х„1 — х")~ и приравнивая нулю степени при основаниях с и х„г, находим вр=1 и абсциссу точки пересечения с осью Ох хорды, стягивающей дугу графика функции ~'(х) на ~а, 61 (рис.
11.7, а), т.е. первую итерацию выполнить согласно методу хорд, а следующие — в соответствии с (11.29). Для оценки скорости сходимости метода секущих представим в окрестности х' сучетом ~(х ) =О по формуле Тейлора 389 П.8. Комбинированные методы рг — р — 1 = О. Сходящемуся процессу отвечают значения 45+1 1 ~Л-1 Р т1,618> 0 и в= — = =0,618 2 р 2 (отношения золотого сечения!).
Таким образом, в методе секущих погрешность ж„- ж' убывает медленнее, чем в методе Ньютона (р= 2), в котором на каждой итерации нужно вычислять и функцию и производную, а в методе секущих — только функцию. Поэтому при одинаковой трудоемкости вычислений метод секущих позволяет выполнить вдвое больше итераций и в итоге получить более высокую точность. Метод секущих обладает лишь локальной сгодимостью, реализуемой обычно в достаточно малой окрестности корня.
За пределами этой окрестности метод может расходиться (последовательность (х„) выходит эа пределы отрезка локализации кормя) (рис. 11.7, б) или „зацикливаться". Этот метод целесообразно сочетать с упрощенным методом Ньютона, чередуя их применение для я б Х: П~г -г) ~ге = ~г -г— хг„1 — хг„ ~г„+1 — — ~г„1 .( ( ) ~(~г„1) (при и = 1 хг„1 —— х1 берут по (11.30)). Элементы итерационной последовательности с номерами различной четности монотонно стремятся к х с разных сторон (рис.
11.7, в). Поэтому все десятичные знаки, совпадающие у хг„и хг„+1, будут верными для х'. В знаменателе формулы для хг„+1 стоит разность значений ~(х), которые сближаются при приближении х к ж', что может привести к потере значащих цифр и точности расчета. Потеря будет только увеличиваться, если правую часть этой формулы привести к общему знаменателю. На практике итерации проводят до тех пор, пока 390 11. РЕШЕНИЕ НЕЛИНЕЙНЫХ УРАВНЕНИЙ Хл * Хл-1 сон зФ. Хл-1 Х Хл-2 Заменяя приближенное равенство точным, вместо х' получим уточненное значение г ХлХл-2 Хл-1 Хл 2Хл-1 +Хл-2 (11.32) Последовательность (х„), построенная по такому трехшаговому методу, обладает квадратпичной схоростпью сходимостпи. Дополнение 11.1.
Метод 'Чебышева Пусть на отпрезке локализации [а, 6~ = Х простого корня х' уравнения (11.1) функция ~(х) непрерывно дифференцируама по крайней мере р > 2 раэ, причем ~'(х) ф- 0 Чх 1= Х. Тогда ~'(х) знакопостоянна на Х и функция у = Дх) на Х строго монотонна (см. 8.1), а в силу теоремы 9.6 ~!~ имеет строго монотонную обратную функцию х = д(у) = ~ '(у), областью определения которой будет отрезок с концами Да) значение ~хг„+1 — хг„~ не станет меньше заданной погрешности.
Возрастание этого значения является по правилу Гарвина признаком начала „разболтки" расчета: расчет прекращают и последнюю итерацию отбрасывают. Итерационные методы можно сочетать с интерполированием. Так, через точки (х2„1, Дхг„1)), (хг„, Дхгл)) И (Хгл+1, ДХгл+1)) ПОСЛЕ ОЧЕрЕдНОй ПарЫ ИтЕрацИй ПрОВОдят параболу х = аоуг+а1у+аг (т.е. применяют обратную квадратпичную интперполяцию) и, положив у = О, находят уточненное значение хг„+1 —— аг, которое используют на следующей паре итераций. Такой комбинированный метод является трехшаговым.
В методе с линейной скоростпью сходимостпи погрешность убывает примерно по геометрической прогрессии (см. 11.5): 391 Д.11,1. Метод Чебьипева х' — х = ~ д~ ~(д) — „, +д~~~(д) —, (-у)" (-у)' /с=1 И р! (11.33) где и — точка между точками О и у. Производные функции д(у) по у можно найти дифференцированием по х сложной функции х =дух)): д'(у)~'(х) =1; д"(у)(~'(х)) +д'(у)~"(х) =0; д"'(у) (У'(х) ) + Зд" (у) ~ (х) ~Г (х) + д'(у) ~'"(х) = О; Отсюда последовательно можно выразить производные функ- ции д(у) через производные функции Дх): 1 „~" (х) „, (~" (х)) ~вд(х) (Х) ~ уР( ))31 уд( ))5 уд( ))4 и так далее.