Том 2 (1160084), страница 23
Текст из файла (страница 23)
На рис. 6 и 7 Рис. 7. Рис. б. изображена геометрическая картина метода итераций !4) для случаев, когда О ( т'(х) ( К ( ! и — 1 ( — К ( <р' !х) ( О. Геометрически видно, что если в окрестности корня х = а имеет место неравенство О ( р'(х) ( К ( 1, то последовательность !х„) монотонно сходится к корню, причем с той стороны, с которой расположено начальное пРиближение хт а в слУчае — 1 ( — К ( 1!'!х) ( О последовательные приближения расположены поочередно с разных сторон от точки х = и.
В последнем случае по двум последовательным приближениям корня можно судить о достигнутой точности на каждом шаге, так как отклонение х„ от и не больше )х„ — х„ Г!. Эти утверждения можно доказать и аналитически, но мы не будем останавливаться на этом доказательстве. 135 % 41 итвгационныв методы вешания 2. Простейшие итерационные методы: метод секущих и метод Ньютона. Если уравнение /(х)=О имеет корень х=а, а функция ф(х) непрерывна в окрестности х=а, то уравнение х = е (х) = х — ф (х) / (х) также имеет корень х = а. функцию ф(х) можно подобрать так, что итерационный процесс для уравнения (17) будет сходвцимся. Рассмотрим два классических метода, которые можно получить этим способом. Пусть /(х) — действительная функция действительного переменного х, а х = а — действительный корень уравнения /(х) = О. Предположим, чзо в некоторой окрестности точки х = а функция /(х) вместе с /'(х) и /"(х) непрерывна, а /'(х) и /"(х) в этой окрестности не меняют знака.
Это означает, что при переходе через х = а функция /(х) меняет знак и имеет точку х = а простым корнем. Пус1ь хо в точка рассматриваемой окрестности, в которой /(хо)/" (хо) > О. В (17) в качесзве функции т(х) возьмем функцию /(«) — 7 («о) ф(х) =— Тогда уравнение х = гр(х) = х — «о /(х) = о~~) «/("о) (15) / («) — /(«о) / («) — У («о) также имеет корнем х= а. За начальное приближение примем любую, достаточно близкую к а точку х, рассматриваемой окрестности, в когорой /(х,) имеет знак, противоположный знаку /(хо), а последующие приближения будем строить обычным способом: «о/(«и — 1) — «о 1/ («о) г 2 5 ъ Так как, с одной стороны, у'(а) («о/' (о) — 7 (хоП 1/ (о) — 7(«о)) — У' (о)!«о/(о) — о/(хоП (/(о) 7 («о)П / («о) + (а — «о) /' (а) / («о) а с другой стороны, по формуле Тейлора /(х) =/(а)+( — )/'(а)+ ' „"'/" (1).
где $ заключено между а и х, то, полагая х= хо, получим: /(хо)+ (а хо)/ (а) о / (() Следовательно, («о — о)з уо(6) т (а) 2 /(~) 136 гашение алгавгличвских и тглнсцяндзнтных явлвнений 1гл. 7 При ха, достаточно близком к х=и, о'(и) — малое число, и поэтому существует такая окрестность точки а, в ко1орой будет иметь место неравенство (у'(х)( ( К ( 1, и если х, взято нз этой окрестности, то последовательность (19) будет сходиться к х = а, Так как ) (х„) = )(х„) — Г'(и) = )' Д)(х„ — а), то, положив иг= ~У'(х)~, будем иметь: хб1хм хг) !Х(~~) ! (20) что позволяет на каждом шаге ио значениям у(х„) следить за достигнутой точностью. Геометрически этот метод состоит в том, что значение х„е, есть абсцисса точки пересечения прямой, проходящей через точки (хю у(х,)) и (х„, г(х„)), с осью х (рис. 8).
Поэтому этот метод Рис. 8. называют методом секущих или методом линейной интерполяции, так как иа каждом шаге за приближенное значение корня х„э, принимается корень интеряоляционного многочлена первой степени, построенного по значениям у(х) в точках х, и х„. 137 5 41 итвглционныа методы гашения Метод секущих является итерационным методом первого порядка. Второй классический метод решения уравнения 7(х) = 0 — метод Ньютона — получим, если положить в (17) 1 ф(х) =— т. е.
свести отыскание корня х=а уравнения 7(х) =0 к отысканию корня уравнения х = х —, = у (х). 7" (х) (21) Будем предполагать, что на отрезке !а, б), содержащем единственный корень х = а уравнения 7(х) = О, функция 7(х) имеет непрерывные производные 7'(х) и 7'"(х), не обращающиеся в нуль на этом отрезке.
В этом случае р'(х) = !в у'2 (х) у(х) ул (х) уж (х) и у'(а) =О. Это означает, что существует такая окрестность точки х= а, что если начальное приближение х= хе взято из эгой окрестности, то последовательность х„=х„,—, " ' (и=!, 2, ...) (22) у' (х„~) будет сходиться к х = я, Начальное приближение хз целесообразно выбирагь так, чтобы было У(хо) У (хо) ) О.
(23) Метод Ньютона применим не только для отыскания действительных корней уравнения 7(х) = О, но и комплексных корней, только нужно иметь в виду, что при отыскании комплексного корня в случае действительной функции 7(х) начальное приближение хъ нужно брать комплексным числом, а не действительным. В случае, если х = а является действительным корнем уравнения 7(х) = О, этот метод имеет простую геометрическую интерпретацию. Значение х„ъ, есть абсцисса точки.
пересечения касательной к кривой у =,г(х) в точке х = х„ с осью х (рис. 9). Поэтому метод Ньютона часто называют методом касательных. Как видно из рис. 9 последовательные приближения к действительному корню в методе Ньютона сходятся к нему монотонно, приближаясь со стороны хз. Если за начальное приближение в методе Ньютона взять точку хз. где 7(хъ)Уь(хе) < О, то, как видно из рис. 10, мы можем не прийти к корню х = а, если только начальное приближение не очень хорошее. Так как в методе Ньютона у'(а) = О, а ъ" (а), вообще говоря.
не равна нулю, то метод Ньютона является итерационным методом второго порядка. 138 лишение ллгевглических и челнсцендентных гелвнений ~гл. 7 Рис. 9. Рис. 10. $4) итееационныа методы гашения Скорость скодимости метода Ньютона можно оценить следующим образом. По формуле Тейлора О = У (а) = / (х„) + У' (х„) (и — х„) + —, г'" (() (а — х„)', где ( заключено между а и х„.
Отсюда Х(хе) 1 Хе(я) а =х„— а — —, (и — х ). У' (хч) " 2 /' (хв) Следовательно. У (хч) 1 У» ($) х — п=х — и —, " = —,—, (а — х )'. У( ) 2 Г(„) Если т, = ппп (,у' (х) /, а Ма = гпах1,1" (х) ), где [а, Ь) — отрезок, 1и, Ы 1а Ы содержащий хе и а, на котором не меняют знака Г" (х) и У" (х), то ~ х„ь, — а) ( — '1х„— а1а. ~1 (24) у(а) ау(Ь) — Ь|(а) у' (а) ' ' у(Ь) — у(а) (25) а следующие приближения находим по формулам: хгп — еУ ( 'еа — г) — хач — ~У (хее-а) у(хел г) — у(хеа е) У(хеп-з) хап=ха -е у у' (ха„а) Если же г(Ь))г" (Ь)) О, то хе и х, находим по формулам: У(Ь) аУ(Ь) — ЬУ(а) — У(Ь) (25') Это указывает на быструю сходимость метода Ньютона.
Комбинируя метод секущих и метод Ньютона, можно получить несчационарный метод отыскания действительных корней уравнения у(х) = О, преимущество которого заключается в том, что при прежних предположениях относительно у'(х) и )" (х) последовательные приближения х„и х„е, лежат по разные слороны от корня, и по. эгому можно следить в процессе вычислений за достигнутой точностью, и в то же время он сходится значительно быстрей метода секущих. Пусть на отрезке (а, Ь) содержится единственный корень уравнения У(х)= О, а У'(х) и У" (х) на этом отрезке не меняют знаков.
Если )(а)У" (а)) О, то находим хе и х, по формулам: 140 гашения ллгезвличаских и тглнсцандвнтных яплвнвний [гл. 7 а следующие приближения — по тем же формулам (26). Как видно из рис. 11, последовательные приближения х,„и хе„~, всегда расположены по разные стороны от х = и и первые совпадающие знаки х,„и хз„э, и будут верными знаками для х=п. у~~х) Рис, 11. 3. Метод Чебышева построения итераций высших порядков.
В 1838 г. П. Л. Чебышев предложил метод отыскания действительных корней уравнения Г(х) = О, частными случаями которого явились многие, разработанные до него методы, В основе метода Чебышева лежит представление функции, обратной к функции 7(х), по формуле Тейлора. Пусть уравнение /(х)= О на отрезке [а, б! имеет корень х=а. Относительно функции /(х) предположим, что она непрерывна на отрезке [а, й] вместе с производными достаточно высокого порядка и 7'(х) ~ О на [а, Ь[. При этих предположениях функция у=/(х) имеет обратную функцию х=г".(у), определенную на отрезке [с, ~1[, являющемся областью значений 7(х) при х~[а, Ь[.
Функция г".(у) имеет столько же непрерывных производных, сколько имеет и 7(х). Так как х=г. [У(х)! (х ~\а, й[), у= — У!Г(у)! (уЕ [с, 4), (27) 141 9 4[ итивационныв мвтоды ввшиния то (28) и= Р(0). При у ~ [с, с(] формула Тейлора лает «Р<ю(у) =Р(О) =Р(у)+ У,( — 1) — 1 у«+)юг+о (29) где остаточный член может быть записан в виде ьяР'+О(Ч) 7[ + =( 1) (г+1)! У (30) (з] заключено между 0 и у), или х,е,— — р„(х„) (в=О, 1, ..., хр~-[а, в[), получим итерационный метод (г+1)-го порядка, так как р~'~(а)=0 (1=1, 2,..., г), Если хр взято достаточно близко к к, то последовательность [х„] сходится к а, ибо существует такая окрестносчь точки и, в которой [ср'(х)] (К( 1, и для сходимости [х„] нужно только потребовать, чтобы х, при- надлежала этой окрестности.
функцию е„(х) можно найти в явном виде через )'(х) и ее про- изводные, так как из тождества (27) имеем: Р' [7 (х)] ° 7' (х) = 1, Р" [г' (х)] г"' (х) + Р' [7 (х)[,Г' (х) = О, Р" [7 (х)] г (х)+ЗР" [7 (х)] 7'(х)7" (х)+Р' [7 (х)]7л' (х) = 0 Лля упрощения записи положим Р [7 (х)] = — а«(х), срг (х) = — х+ ~~~~~ ( — 1) «(, ) [7 (х)[«. (32) «1 Уравнение х = е„(х) (33) имеет коРень х=а, так как сР„(к)=а — ~~~ ( — 1) — [7(о)] « а« (е) « «1 «-з Положив (34) 142 вешания ллгвввличвских и твлнсцвндвнтных гвлвнвний (гл.
7 или а)(х)7'(х) = 1, а,(х)7' (х) + а,(х)7"(х) = О, аа(х)7' (х)+За!(х)7'(х) 7а(х)+а)(х)7т~(х) =О, (35) т. е; можно последовательно найти а,(х), а,(х), ..., а следовательно, и уг(х). При г=! ч))(х)=х — —; — и х =х— У (х) у (х„) 7' (х) Е' (х„) ' (36) т, е. мы снова получаем метод Ньютона. При г=2 г'(х) г'а (х) г'! (х) 7" (х) 27"! (х) (37) Г (ха) уа (х„) Г! (ха) г' (х„) 2г '! (х„) Оценка погрешности и скорость сходимости легко получаются из равенства (31).
Полагая в нем х=х„и учитывая (34), получим: г("+" 17(1П (38) где 1 лежит между а и х„. Если положить Е= )пах (7'(х) ~, !)е(а, ь) М„.))= шах (Р 17(х)1( и учесть, что ай(а, Ь) ~1'(х„)) =(7(ха) — 7(а) != (У'(~) /! х„— а! (Е!х„— а!, то из (38) имеем: Отсюда следует, что (а — х ! ((7)+(г+!)+(г+!)'+" )-(!+!)ы (~х а~(" (г"— (!.+ !)"'- ! (ае!) (! -!)-~! =И!ха — а1) " (ха — а( Таким образом, если (ха — а! < 1 и )7( х — а(=а) < 1, то а+и'"-! 1а — х,„1 ( а) (40) !'+ 1 !' '-! М„+)Е „+! „+))г М„+)Е 1а — ха )1< ( )х„— а~ =()(х„— а( (()= ). (39) 143 $4] итввлционныв методы вешания что указывает на очень быструю сходимость метода.
Так, если ы(0,1 и !хв — а)(! то при г=1 (метод Ньютона) )а — хг~(10, (а — х ((10 (а — х,) (1О при г=2 )а — х,~ (10, )а — ха~ (10 ', !а — х !( ~а — хв! (10 ', !а — хь~ (10 т. е. количество верных десятичных знаков быстро возрастает. а= 1пп сч ю.ь,л си+1 (41) где с„— коэффициент при л в разложении — ио степеням л.
И т (2) г (г) 1(оказательство. Так как для функции — точка а=а У(е) является ближайшей к началу координат особой точкой, то ряд (42) сходится при всех !л) ( а, а ряд (л — а) — 7! ичл т (е) ъч у(с) . ~а (43'г сходится при всех л, для которых ~л / ( г. Отсюда СО СО ~У с„в" (л — а) = ч~ д„л" — ась=де, с„,— ас„=д„(п=1, 2, ...). (44) Таким образом, ~~' дааа= — асс+ ч', (с„,— аса)аа= — с а .ь!. (45) а-о ь-! 4. Построение итераций высших порядков с помощью теоремы Кенига. А.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
