В.Б. Андреев - Численные методы (2 в 1). (2007) (1160465), страница 16
Текст из файла (страница 16)
. . .(12.4)Èòåðàöèîííûé ïðîöåññ (12.4) íàçûâàåòñÿ ìåòîäîì ïðîñòûõ èòåðàöèé.Òåîðåìà 12.1. Ïóñòü x∗ êîðåíü óðàâíåíèÿ (12.2). Òîãäà, åñëè |ϕ0 (x)| 6 q < 1äëÿ x ∈ [x∗ − δ, x∗ + δ], òî ïðè ëþáîì íà÷àëüíîì ïðèáëèæåíèè x0 ∈ [x∗ − δ, x∗ +δ] ìåòîä ïðîñòûõ èòåðàöèé ñõîäèòñÿ ñî ñêîðîñòüþ ãåîìåòðè÷åñ÷êîé ïðîãðåññèè,çíàìåíàòåëåì êîòîðîé ÿâëÿåòñÿ ÷èñëî q . Ïðè ýòîì|xk − x∗ | 6 q k |x0 − x∗ |.122 12. ÌÅÒÎÄÛ ÐÅØÅÍÈß ÍÅËÈÍÅÉÍÛÕ ÓÐÀÂÍÅÍÈÉÝòà òåîðåìà èëè åé àíàëîãè÷íàÿ áûëà äîêàçàíà â êóðñå ìàòåìàòè÷åñêîãî àíàëèçà.Äàäèì ãåîìåòðè÷åñêóþ èëëþñòðàöèþ èòåðàöèîííîãî ïðîöåññà (12.4). Èçîáðàçèìíà ïëîñêîñòè Oxy ïðÿìóþ y = x è êðèâóþ y = ϕ(x). Ïóñòü ñíà÷àëà 0 < ϕ0 (x) < 1.¤C¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡x¡¡∗XX»»x2x1x0x∗∗Ðèñ. 2Èç ðèñóíêà 2 âèäíî, ÷òî ïðè 0 < ϕ0 (x) 6 q < 1 ïîñëåäîâàòåëüíîñòü xk ìîíîòîííîñõîäèòñÿ ê x∗ , ïðè÷åì ñ òîé ñòîðîíû, ñ êîòîðîé ðàñïîëîæåíî íà÷àëüíîå ïðèáëèæåíèå.Åñëè ϕ0 (x∗∗ ) > 1, òî èòåðàöèè íå ñõîäÿòñÿ ê x∗∗ .Ïðè −1 < ϕ0 (x) < 0 ïðèáëèæåíèÿ äâóñòîðîííèå (ñì. ðèñ.
3).  ýòîì ñëó÷àå ïîäâóì ïîñëåäîâàòåëüíûì ïðèáëèæåíèÿì ëåãêî ñóäèòü î äîñòàòî÷íîé òî÷íîñòè|xk − x∗ | < |xk − xk−1 |.Ìîæíî òàêæå óâèäåòü, ÷òî ñõîäèìîñòü òåì áûñòðåå, ÷åì ìåíüøå |ϕ0 |. Åñëè ϕ0 (x∗∗ ) ¿ 1,òî ïðîöåññ ñõîäèìîñòè óñêîðÿåòñÿ ïî ìåðå ïðèáëèæåíèÿ ê êîðíþ.12.3. ÌÅÒÎÄ ÍÜÞÒÎÍÀ123¤C¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡XX»»x0x2x1Ðèñ. 312.3 Ìåòîä ÍüþòîíàÏóñòü k -å ïðèáëèæåíèå xk ê ðåøåíèþ óðàâíåíèÿ (12.1) íàéäåíî. Ðàçëîæèì ôóíêöèþf (x) â òî÷êå xk ïî ôîðìóëå Òåéëîðàf (x) = f (xk ) + (x − xk )f 0 (xk ) + O((x − xk )2 )èëè∆f = f (x) − f (xk ) = df + O(d2 f ),df ≡ f 0 dx.Çàìåíèì ïðèáëèæåííî ïðèðàùåíèå ôóíêöèè åå äèôôåðåíöèàëîì∆f ≈ dfèëèf (x) ≈ f (xk ) + (x − x)f 0 (xk ) =: P1 (x).124 12. ÌÅÒÎÄÛ ÐÅØÅÍÈß ÍÅËÈÍÅÉÍÛÕ ÓÐÀÂÍÅÍÈÉÏðèðàâíÿåì òåïåðü ôóíêöèþ P1 (x), ÿâëÿþùóþñÿ ïðèáëèæåíèåì ê f (x), íóëþP1 (x) = 0 :f (xk ) + (x − xk )f 0 (xk ) = 0è íàéäåì êîðåíü ïîëó÷åííîãî óðàâíåíèÿx − xk = −f (xk )f 0 (xk )⇒x = xk −f (xk ).f 0 (xk )Ýòîò êîðåíü è ïðèìåì çà íîâîå ïðèáëèæåíèå.
Èòàê, àëãîðèòì ìåòîäà Íüþòîíà ñëåäóþùèé:f (xk )xk+1 = xk − 0, k = 0, 1, . . . , x0 çàäàíî.(12.5)f (xk )Ãåîìåòðè÷åñêàÿ èíòåðïðåòàöèÿ ìåòîäà Íüþòîíà òàêîâà. Êàê èçâåñòíî èç ìàòåìàòè÷åñêîãî àíàëèçà, f 0 (xk ) åñòü òàíãåíñ óãëà íàêëîíà êàñàòåëüíîé ê êðèâîé y = f (x)â òî÷êå x = xk . Ïðÿìàÿy = P1 (x)(12.6)èìååò òîò æå íàêëîí, ÷òî è êàñàòåëüíàÿ ê f (x) â òî÷êå xk . Áîëåå òîãî, â òî÷êå x = xkçíà÷åíèÿ P1 (x) è f (x) ñîâïàäàþò, è, ñëåäîâàòåëüíî, (12.6) åñòü óðàâíåíèå êàñàòåëüíîéê êðèâîé y = f (x) â òî÷êå x = xk .´´´´xk+2¿¿¿xk+1¿¿¿¿¿¿¿xkÐèñ. 4Òåì ñàìûì, â ìåòîäå Íüþòîíà íà êàæäîé èòåðàöèè êðèâàÿ y = f (x) çàìåíÿåòñÿêàñàòåëüíîé â òî÷êå xk , è âìåñòî óðàâíåíèÿ f (x) = 0 ðåøàåòñÿ óðàâíåíèå P1 (x) = 0.12.3. ÌÅÒÎÄ ÍÜÞÒÎÍÀ125Ñâÿçü ìåòîäà Íüþòîíà ñ ìåòîäîì ïðîñòûõ èòåðàöèé.
Ïðè ïðèìåíåíèè ìåòîäàïðîñòûõ èòåðàöèé ê ðåøåíèþ óðàâíåíèÿ (12.1) îíî ñíà÷àëà ïðåîáðàçîâûâàëîñü ê âèäó(12.2), ãäå ôóíêöèÿ ϕ(x) îïðåäåëÿëàñü ñîîòíîøåíèåì (12.3), à èòåðàöèè ïðîâîäèëèñüïî ôîðìóëå (12.4). Ñðàâíèâàÿ (12.4) è (12.5), íàõîäèì, ÷òîϕ(x) = x −f (x),f 0 (x)(12.7)ò.å. τ (x) èç (12.3) åñòü [−f 0 (x)]−1 .
Êàê ñëåäóåò èç òåîðåìû 12.1, äëÿ ñõîäèìîñòè ìåòîäàïðîñòûõ èòåðàöèé ïðîèçâîäíàÿ ôóíêöèè ϕ(x) â îêðåñòíîñòè êîðíÿ x∗ äîëæíà áûòüïî ìîäóëþ ìåíüøå åäèíèöû. Èç (12.7)ϕ0 (x) = 1 −(f 0 (x))2 − f (x)f 00 (x)f (x)f 00 (x)=.(f 0 (x))2(f 0 (x))2Åñëè x∗ ïðîñòîé êîðåíü óðàâíåíèÿ (12.1), òî f 0 (x∗ ) 6= 0, à ϕ0 (x∗ ) = 0, è ñóùåñòâóåòîêðåñòíîñòü x∗ , ãäå |ϕ0 (x)| < 1. Ïîýòîìó ìåòîä Íüþòîíà âñåãäà ñõîäèòñÿ, åñëè íà÷àëüíîå óñëîâèå âûáðàíî óäà÷íî.Îöåíêà ñêîðîñòè ñõîäèìîñòè ìåòîäà Íüþòîíà. Åùå ðàç ðàçëîæèì f (x) â òî÷êåxkf (x) = f (xk ) + (x − xk )f 0 (xk ) +(x − xk )2 00f (ξk ),2ξk ∈ (x, xk ).Ïîëàãàÿ çäåñü x = x∗ , ïîëó÷èì0 = f (xk ) + (x∗ − xk )f 0 (xk ) + ñèëó (12.5)(x∗ − xk )2 00 ∗f (ξk ),2ξk∗ ∈ (x∗ , xk ).0 = (xk+1 − xk )f 0 (xk ) + f (xk ).Âû÷èòàÿ ýòî ñîîòíîøåíèå èç ïðåäûäóùåãî, ïîëó÷èì10 = (x∗ − xk+1 )f 0 (xk ) + (x∗ − xk )f 00 (ξk∗ ).2Îòñþäà(xk+1 − x∗ ) =1 f 00 (ξk∗ )(xk − x∗ )2 .2 f 0 (xk )(12.8)Áóäåì ïðåäïîëàãàòü, ÷òî|f 0 (x)| > m1 ,|f 00 (x)| 6 M2 .|xk+1 − x∗ | 6M2|xk − x∗ |2 .2m1Òîãäà(12.9)126 12.
ÌÅÒÎÄÛ ÐÅØÅÍÈß ÍÅËÈÍÅÉÍÛÕ ÓÐÀÂÍÅÍÈÉÄîìíîæàÿ ëåâóþ è ïðàâóþ ÷àñòè ýòîãî íåðàâåíñòâà íà M2 /(2m1 ), ïîëó÷èì, ÷òî·¸2M2M2∗∗βk+1 =|xk+1 − x | 6(xk − x ) = βk2 ,2m12m1ò.å.βk+1 6 βk2 ,(12.10)ãäåβk =M2|xk − x∗ |.2m1(12.11)Èç (12.10) èìååìβ1 6 β02 ,2β2 6 β12 6 β04 = β02 ,è âîîáùå3β3 6 β22 6 β02kβk2 6 β02 .Ïðèíèìàÿ âî âíèìàíèå (12.11), íàõîäèì, ÷òî¸2k·2m1 M2∗∗|xk − x | 6|x0 − x | .M2 2m1(12.12)Äëÿ ñõîäèìîñòè íóæíî, ÷òîáûM2|x0 − x∗ | 6 q < 1.2m1(12.13)Èòàê, äîêàçàíàÒåîðåìà 12.2. Ïóñòü f (x) ∈ C 2 [x∗ − δ, x∗ + δ], ãäå x∗ ïðîñòîé êîðåíü óðàâíåíèÿ(12.1), è ïðè x ∈ [x∗ − δ, x∗ + δ] ñïðàâåäëèâû îöåíêè (12.9).
Òîãäà, åñëè íà÷àëüíîåïðèáëèæåíèå x0 ∈ [x∗ −δ, x∗ +δ] òàêîâî, ÷òî ñïðàâåäëèâî (12.13), òî ìåòîä Íüþòîíà(12.5) ñõîäèòñÿ ñ êâàäðàòè÷íîé ñêîðîñòüþ, è ñïðàâåäëèâà îöåíêà (12.12).Ïðèìåð 12.2. Ïóñòü òðåáóåòñÿ íàéòè êîðåíü ñòåïåíè p èç ÷èñëà a > 0. Òîãäàxk+1f (x) := xp − axp − ap−1a= xk − k p−1 =xk + p−1 .ppxkpxkÏðè p = 2 è a = 3xk+1 =(12.14)xk3+.22xkÏóñòü x0 = 2.
Òîãäà977= 1.75, x2 =≈ 1.7321, x3 ≈ 1.7320508,456à x∗ = 1.7320508 . . . . Îòñþäà ñëåäóåò, ÷òî åñëè â x0 îäèí âåðíûé çíàê, òî â x1 äâà, â x2 ÷åòûðå è ò.ä. Ãðóáî ãîâîðÿ, ÷èñëî âåðíûõ çíàêîâ ïîñëå êàæäîé èòåðàöèèóäâàèâàåòñÿ.x1 =12.3.
ÌÅÒÎÄ ÍÜÞÒÎÍÀ127Çàìå÷àíèå 12.1. Ñõîäèìîñòü ìåòîäà Íüþòîíà óñòàíîâëåíà ïðè óñëîâèè, ÷òî êîðåíüx∗ ÿâëÿåòñÿ ïðîñòûì. Íó, à ÷òî áóäåò, åñëè êîðåíü îêàæåòñÿ êðàòíûì? ×òîáû îòâåòèòüíà ýòîò âîïðîñ, èññëåäóåì f f 00 /(f 0 )2 . Åñëè êîðåíü x∗ èìååò êðàòíîñòü p > 1, òî¡¢f (x) = a(x − x∗ )p + O (x − x∗ )p+1¡¢f 0 (x) = ap(x − x∗ )p−1 + O (x − x∗ )p¡¢f 00 (x) = ap(p − 1)(x − x∗ )p−2 + O (x − x∗ )p−1 .Îòñþäàf (x)f 00 (x)ϕ (x) ==[f 0 (x)]2¡¢a2 p(p − 1)(x − x∗ )2p−2 + O (x − x∗ )2p−1p−1¡¢==+ O(x − x∗ )22∗2p−2∗2p−1pp a (x − x )+ O (x − x )0(12.15)è â ìàëîé îêðåñòíîñòè x∗ |ϕ0 (x)| < 1. Òåì ñàìûì, ìåòîä Íüþòîíà áóäåò ñõîäèòüñÿè ê êðàòíîìó êîðíþ, íî ýòà ñõîäèìîñòü íå áóäåò êâàäðàòè÷íîé; îíà áóäåò ñêîðîñòüþñõîäèìîñòè ãåîìåòðè÷åñêîé ïðîãðåññèè ñî çíàìåíàòåëåì q = (p − 1)/p < 1.Âîçíèêàåò âîïðîñ, à íåëüçÿ ëè óâåëè÷èòü ñêîðîñòü ñõîäèìîñòè ê êðàòíîìó êîðíþ? Îòâåò íà ýòîò âîïðîñ ïîëîæèòåëüíûé. Ýòî ìîæíî ñäåëàòü ïóòåì ñëåäóþùåãîîáîáùåíèÿ ìåòîäà Íüþòîíà.
Èòåðàöèè áóäåì âåñòè ïî ôîðìóëåxk+1 = xk − τf (xk ),f 0 (xk )ãäå çíà÷åíèå ïàðàìåòðà τ îïðåäåëÿåòñÿ êðàòíîñòüþ èñêîìîãî êîðíÿ. Íàéäåì ýòî çíà÷åíèå. Èìååìϕ(x) = x − τf (x),f 0 (x)ϕ0 (x) = 1 − τf 02 − f f 00f f 00=(1−τ)+τ.f 02f 02Îòñþäà ñ ó÷åòîì (12.15)¸p−1p−1∗+ O(x − x ) = 1 − τ + τ+ O(x − x∗ ).ϕ (x) = (1 − τ ) + τpp·0Âûáåðåì τ èç óñëîâèÿ, ÷òî ϕ0 (x∗ ) = 0. Òîãäà τ = p, è îáîáùåííûé ìåòîä Íüþòîíàxk+1 = xk − pf (xk ),f 0 (xk )ãäå p êðàòíîñòü èñêîìîãî êîðíÿ, îáëàäàåò ñêîðîñòüþ ñõîäèìîñòè ìåòîäà Íüþòîíàê ïðîñòîìó êîðíþ.128 12.
ÌÅÒÎÄÛ ÐÅØÅÍÈß ÍÅËÈÍÅÉÍÛÕ ÓÐÀÂÍÅÍÈÉÏðèìåð 12.3. Ïóñòü f (x) = x2 . Çäåñü x∗ = 0 åñòü äâóêðàòíûé êîðåíü. ÌåòîäÍüþòîíà ïðèâîäèò ê ñîîòíîøåíèþxk+1 = xk −x2k1= xk .2xk2Ýòè ñîîòíîøåíèÿ ïðåäñòàâëÿþò ñîáîé ãåîìåòðè÷åñêóþ ïðîãðåññèþ ñî çíàìåíàòåëåìq = 1/2.Îáîáùåííûé ìåòîä äëÿ ýòîãî ïðèìåðà ñðàçó äàåò òî÷íîå ðåøåíèå.Ïðèìåð 12.4.
Ïóñòü f (x) = x2 (x + 1) è x∗ = 0 äâóêðàòíûé êîðåíü. Îáîáùåííûéìåòîä Íüþòîíà ïðèíèìàåò âèäxk+1 =Åñëè x0 = 1, òî x1 =x2k.2 + 3xk11= 0.2, x2 == 0.015, x3 = 0.0000115 è ò.ä.565 13Ìåòîä ñåêóùèõ.Îñíîâíûì äîñòîèíñòâîì ìåòîäà Íüþòîíà, êîòîðîå äåëàåò åãî î÷åíü ïðèâëåêàòåëüíûì, ÿâëÿåòñÿ âûñîêàÿ ñêîðîñòü ñõîäèìîñòè.
Ê íåäîñòàòêàì ñëåäóåò îòíåñòè íåîáõîäèìîñòü âû÷èñëåíèÿ íà êàæäîì øàãå èòåðàöèé ïðîèçâîäíîé. Âòîðîé íåäîñòàòîê ñèëüíàÿ çàâèñèìîñòü ðåçóëüòàòèâíîñòè ìåòîäà îò íà÷àëüíîãî ïðèáëèæåíèÿ: åñëèíà÷àëüíîå ïðèáëèæåíèå îêàçàëîñü íåóäà÷íûì (íåäîñòàòî÷íî áëèçêèì ê èñêîìîìóðåøåíèþ), ìåòîä ïðîñòî ðàñõîäèòñÿ. Ïåðâûé íåäîñòàòîê â êàêîé-òî ìåðå ìîæåò áûòüïðåîäîëåí ïóòåì çàìåíû ïðîèçâîäíîé ðàçíîñòíûì îòíîøåíèåì. Èìåííî, çàìåíèì â(13.5) ïðîèçâîäíóþ f 0 (xk ) íà ðàçíîñòíîå îòíîøåíèå∆fkfk − fk−1=,∆xkxk − xk−1ãäå fk = f (xk ).  ðåçóëüòàòå áóäåì èìåòüxk+1 = xk − fkxk − xk−1,fk − fk−1k = 1, 2, . . .
.(13.1)Îòìåòèì, ÷òî ýòîò ìåòîä äâóõøàãîâûé: ÷òîáû íàéòè xk+1 , íóæíî çíàòü xk è xk−1 . Â÷àñòíîñòè, äëÿ òîãî, ÷òîáû íà÷àòü èòåðàöèè, òàêæå òðåáóþòñÿ çíà÷åíèÿ íà÷àëüíûõïðèáëèæåíèé x0 è x1 .Îáðàòèìñÿ ê ãåîìåòðè÷åñêîé èíòåðïðåòàöèè ìåòîäà (13.1). ÏóñòüL1 (x) = fk−1x − xkx − xk−1+ fkxk−1 − xkxk − xk−1(13.2) èíòåðïîëÿöèîííûé ìíîãî÷ëåí Ëàãðàíæà ïåðâîé ñòåïåíè, ïîñòðîåííûé ïî çíà÷åíèÿì ôóíêöèè f (x) â óçëàõ xk−1 è xk . Ðàññìîòðèì ïðÿìóþy = L1 (x)129130 13.
ÌÅÒÎÄ ÑÅÊÓÙÈÕè íàéäåì åå íóëü, ò.å. ðåøåíèå óðàâíåíèÿ L1 (x) = 0. Ïðèíèìàÿ âî âíèìàíèå (13.2),íàõîäèì, ÷òîfk−1 (x − xk ) = fk (x − xk−1 ) ≡ fk (x − xk ) + fk (xk − xk−1 ).Îòñþäàx = xk − fkxk − xk−1,fk − fk−1÷òî ñîâïàäàåò ñ xk+1 èç (13.1). Îòñþäà ñëåäóåò, ÷òî åñëè â ìåòîäå Íüþòîíà êðèâàÿy = f (x) âñÿêèé ðàç çàìåíÿåòñÿ êàñàòåëüíîé â òî÷êå xk , òî â ìåòîäå (13.1) êðèâàÿy = f (x) çàìåíÿåòñÿ ñåêóùåé, ïåðåñåêàþùåé y = f (x) ïðè x = xk−1 è x = xk . Ýòàãåîìåòðè÷åñêàÿ èíòåðïðåòàöèÿ ìåòîäà (13.1) è äàåò åìó íàçâàíèå ìåòîä ñåêóùèõ.Îáðàòèìñÿ ê îöåíêå ñêîðîñòè ñõîäèìîñòè ìåòîäà ñåêóùèõ.
Ñíà÷àëà çàìåòèì, ÷òîâ ñèëó (13.2) è ñ ó÷åòîì ôîðìóëû êîíå÷íûõ ïðèðàùåíèéL1 (xk+1 ) − L1 (x∗ ) =xk+1 − xkxk+1 − xk−1x∗ − xkx∗ − xk−1= fk−1+ fk− fk−1− fk=xk−1 − xkxk − xk−1xk−1 − xkxk − xk−1xk+1 − x∗xk+1 − x∗fk − fk−1= fk−1+ fk=(xk+1 − x∗ ) =xk−1 − xkxk − xk−1xk − xk−1= f 0 (ξk )(xk+1 − x∗ ), ξk ∈ (xk−1 , xk )è ïîýòîìóxk+1 − x∗ =L1 (x∗ )L1 (xk+1 ) − L1 (x∗ )=−,f 0 (ξk )f 0 (ξk )(13.3)èáî ïî ïîñòðîåíèþ L1 (xk+1 ) = 0. Ïðè âû÷èñëåíèè L1 (x∗ ) âîñïîëüçóåìñÿ ôîðìóëîé äëÿïîãðåøíîñòè èíòåðïîëÿöèè1f (x) − L1 (x) = f 00 (ηk )(x − xk−1 )(x − xk ),2ηk ∈ (x, xk−1 , xk ),ãäå (x, xk−1 , xk ) îòêðûòûé èíòåðâàë, êîíöàìè êîòîðîãî ÿâëÿþòñÿ êðàéíèå èç óêàçàííûõ òðåõ òî÷åê.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
