Н.И. Ионкин - Электронные лекции (2009) (1135239), страница 8
Текст из файла (страница 8)
Åñëè S(x) óäîâëåòâîðÿåò óñëîâèþ Ëèïøèöà ñ 0 < q < 1íàUa (x∗ )è|x − x0 | < a,òî ìåòîä ïðîñòîé èòåðàöèè (4) ðåøåíèÿ óðàâ-íåíèÿ (1) ñõîäèòñÿ, ïðè÷åì ñî ñêîðîñòüþ ãåîìåòðè÷åñêîé ïðîãðåññèèñî çíàìåíàòåëåì q.Äîêàçàòåëüñòâî. Ïî ïîñòðîåíèþ|x0 − x∗ | < a,çíà÷èò|xn+1 − x∗ | = |S(xn ) − S(x∗ )| ≤ q|xn − x∗ | ⇒|xn − x∗ | ≤ q n alimn→∞ qn = 0,òàê êàê0 < q < 1.Ñëåäîâàòåëüíî, ìåòîä ñõîäèòñÿ, ïðè÷åì ñî ñêîðîñòüþ ãåîìåòðè÷åñêîéïðîãðåññè ñî çíàìåíàòåëåì q.Çàìå÷àíèå. Åñëè S(x) äèôôåðåíöèðóåìà íà Ua (x∗ ), òî q = supx∈Ua (x∗ ) |S 0 (x)|Çàìå÷àíèå.
Ïóñòü f(x) äèôôåðåíöèðóåìà, f 0 (x) > 0 íà Ua (x∗ ) è ∃M1 =supx∈Ua (x∗ ) |f 0 (x)|Òîãäà çàïèøåì ìåòîä ïðîñòîé èòåðàöèè â âèäå:xn+1 − xn+ f (xn ) = 0,τxn+1 = S(xn ),τ >0S(x) = x − τ f (x)∃S 0 (x) = 1 − τ f 0 (x) íà Ua (x∗ ). Äëÿ ñõîäèìîñòè ìåòîäà20íåîáõîäèìî, ÷òîáû q = supx∈Ua (x∗ ) |1−τ f (x)| < 1, ò.å.
÷òîáû 0 < τ < M1Ñëåäîâàòåëüíî,Ìåòîä Íüþòîíà è ìåòîä ñåêóùèõ73Ìåòîä Ýéòêåíà (óñêîðåíèå ñõîäèìîñòè)Ìåòîä Ýéòêåíà íå ÿâëÿåòñÿ òåîðåòè÷åñêè îáîñíîâàííûì, íî ïðè ïðèáëèæåííûõ çíà÷åíèÿõ ïàðàìåòðîâ ïîçâîëÿÿåò óâåëè÷èòü ñêîðîñòü ñõîäèìîñòè.Ïóñòüxn − x∗ ' Aq n ,ãäå A è q - íåêîòîðûå êîíñòàíòû. Òîãäà:xn−1 − x∗ = Aq n−1xn − x∗ = Aq nxn+1 − x∗ = Aq n+1ñëåäîâàòåëüíî,(xn+1 − xn )2 = A2 q 2n (q − 1)2(xn+1 − 2xn + xn−1 ) = Aq n−1 (q − 1)2Îòêóäà ïîëó÷àåì:(xn+1 − xn )2= Aq n+1 = xn+1 − x∗xn+1 − 2xn + xn−1Ñòàëî áûòü:x∗ ' xn+1 −(xn+1 − xn )2xn+1 − 2xn + xn−1Èç-çà íåòî÷íîñòè â êà÷åñòâå ñëåäóþùåé èòåðàöèè ìû äîëæíû âçÿòüçíà÷åíèå, áëèçêîå ê3x∗Ìåòîä Íüþòîíà è ìåòîä ñåêóùèõÌû ðåøàåì óðàâíåíèåf (x) = 0Ïóñòü êîðåíü ëîêàëèçîâàí íà0f (x) 6= 0(1)Ua (x∗ ), f (x) ∈ C 1 (Ua (x∗ )),ïðè ýòîìUa (x∗ ).f (x∗ ) ïî Òåéëîðó:íàÐàçëîæèì0 = f (x∗ ) = f (x) + f 0 (x)(x∗ − x) + o(x∗ − x) ≈ f (x) + f 0 (x)(x∗ − x)Ïîëîæèì â ýòîé ôîðìóëåx = xn , x∗ = xn+1 ,òîãäà ïîëó÷èì:Ìåòîä Íüþòîíà è ìåòîä ñåêóùèõxn+1 = xn −Âçÿâx0 ∈ Ua (x∗ ),74f (xn )f 0 (xn )ïîëó÷àåì ìåòîä Íüþòîíà:xn+1 = xn −f (xn ), n = 0, 1, 2, .
. .f 0 (xn )Íà êàæäîé èòåðàöèè ñ÷èòàòü ïðîèçâîäíóþ çàòðàòíî, â òî æå âðåìÿíà íåáîëüøîì èíòåðâàëå îíà, êàê ïðàâèëî, ìåíÿåòñÿ íå ñèëüíî. Ñëåäîâàòåëüíî, ìîæíî èñïîëüçîâàòü ïðîèçâîäíóþ, îäèí ðàç âû÷èñëåííóþ íàïåðâîé èòåðàöèè. Ïîëó÷àåì ìîäèôèöèðîâàííûé ìåòîä Íüþòîíà:xn+1 = xn −f (xn ), n = 0, 1, 2, . . . ; x0 ∈ Ua (x∗ )f 0 (x0 )Ìîäèôèöèðîâàííûé ìåòîä Íüþòîíà ñõîäèòñÿ ìåäëåííåå îáû÷íîãîìåòîäà Íüþòîíà, íî áûñòðåå ìåòîäà ïðîñòîé èòåðàöèè.Ìåòîä Íüþòîíà äëÿ ñèñòåìû óðàâíåíèéÐàññìîòðèì ñèñòåìó:(f1 (x1 , x2 ) = 0,f2 (x1 , x2 ) = 0,Ïóñòü(x∗1 , x∗2 )- åå ðåøåíèå.
Ðàçëîæèìf1(2)èf2â îêðåñòíîñòè êîðíÿ:0 = f1 (x∗1 , x∗2 ) = f1 (x1 , x2 ) +∂f1 (x1 , x2 ) ∗∂f1 (x1 , x2 ) ∗(x1 − x1 ) +(x2 − x2 ) + . . .∂x1∂x20 = f2 (x∗1 , x∗2 ) = f2 (x1 , x2 ) +∂f2 (x1 , x2 ) ∗∂f2 (x1 , x2 ) ∗(x1 − x1 ) +(x2 − x2 ) + . . .∂x1∂x2Çàìåíÿÿxiíàf1 (xn1 , xn2 ) +xnièx∗iíàxn+1,iïîëó÷èì:∂f1 (xn1 , xn2 ) n+1∂f1 (xn1 , xn2 ) n+1(x1 − xn1 ) +(x2 − xn2 ) = 0∂x1∂x2Ìåòîä Íüþòîíà è ìåòîä ñåêóùèõf2 (xn1 , xn2 ) +Îáîçíà÷èì75∂f2 (xn1 , xn2 ) n+1∂f2 (xn1 , xn2 ) n+1(x1 − xn1 ) +(x2 − xn2 ) = 0∂x1∂x2xn = (xn1 , xn2 )T , f n = (f1n , f2n )T ,"n nI(xn ) =∂f1 (x1 ,x2 )∂x1n∂f2 (xn1 ,x2 )∂x1à òàêæån∂f1 (xn1 ,x2 )∂x2n∂f2 (xn1 ,x2 )∂x2#(3)Òîãäà óðàâíåíèå ìîæíî çàïèñàòü â âèäå:f (xn ) + I(xn )(xn+1 − xn ) = 0Åñëè∀n ∃I −1 (xn ),(4)òîxn+1 = xn − I −1 (xn )f (xn ), n = 0, 1, 2, .
. . ;x0 çàäàíî(5)Çàìå÷àíèå. Ñ÷èòàòü I −1 (xn ) íå î÷åíü óäîáíî, ïîýòîìó îáû÷íî ââîäÿòïîãðåøíîñòüv n+1 = xn+1 − xnè ðåøàþò íà êàæäîé èòåðàöèè óðàâíåíèå:I(xn )v n+1 = −f (xn )Çàìå÷àíèå.  ñëó÷àå ñèñòåìû ìîæíî ïðèìåíèòü ìîäèôèöèðîâàííûéìåòîä Íüþòîíà:xn+1 = xn − I −1 (x0 )f (xn )Íî â ýòîì ñëó÷àå ñêîðîñòü ñõîäèìîñòè áóäåò çíà÷èòåëüíî ìåíüøå.Åñëè äàíà ñèñòåìà èç m óðàâíåíèé:f1 (x1 , .
. . , xm ) = 0,f (x , . . . , x ) = 0,2 1m...fm (x1 , . . . , xm ) = 0,òî òàêæå ìîæíî èñïîëüçîâàòü ìåòîä Íüþòîíà, â ýòîì ñëó÷àåI(xn )ij =∂fi (xn ),∂xji, j = 1, mÑèñòåìà â ýòîì ñëó÷àå èìååò òîò æå âèä:f (xn ) + I(xn )(xn+1 − xn ) = 0Ñõîäèìîñòü ìåòîäà Íüþòîíà è îöåíêà ñõîäèìîñòè76Ìåòîä ñåêóùèõÇàïèøåì ìåòîä Íüþòîíà:xn+1 = xn −Çàìåíèì â íåìf (xn ),f 0 (xn )f 0 (xn )íàx0 ∈ Ua (x∗ ),n = 0, 1, 2, . . . .f (xn )−f (xn−1 ).xn −xn−1Ïîëó÷èìxn+1 = xn −xn − xn−1f (xn )f (xn ) − f (xn−1 )(6)Ïîñêîëüêó â çàïèñè äàííîãî ìåòîäà ó÷àâñòâóþò òðè ïîñëåäîâàòåëün+1íûå èòåðàöèè (x, xn è xn−1 ), òî îí íàçûâàåòñÿ äâóõøàãîâûì ìåòîäîì.Äëÿ òîãî, ÷òîáû âîñïîëüçîâàòüñÿ èì, òðåáóåòñÿ çàäàòü äâà íà÷àëüíûõ01ïðèáëèæåíèÿ (x è x ).
Èõ ìîæíî ïîëó÷èòü ìåòîäîì ïðîñòîé èòåðàöèèèëè ìåòîäîì Íüþòîíà.Çàìåòèì, ÷òî, èñïîëüçóÿ ìåòîä ñåêóùèõ, ìû ïîëó÷àåìùè èíòåðïëÿöèè ôóíêöèèxn+1ïðè ïîìî-fïîëèíîìîì ïåðâîé ñòåïåíè (ëèíåéíîé ôóíênn−1öèåé), èñïîëüçóÿ åå çíà÷åíèå â óçëàõ x è x.4Ñõîäèìîñòü ìåòîäà Íüþòîíà è îöåíêà ñõîäèìîñòèÐàññàìòðèâàåòñÿ íåëèíåéíîå óðàâíåíèåf (x) = 0.(1)Çàïèøåì äëÿ íåãî ìåòîä Íüþòîíà:xn+1f (xn )=x − 0 n ,f (x )nn = 0, 1, . . . ;x0 ∈ Ua (x∗ ).Çàïèøåì ýòî ìåòîä â áîëåå îáùåì âèäå:xn+1 = S(xn ),ÒîãäàãäåS(x) = x −f (x).f 0 (x)(f 0 (x))2 − f (x)f 00 (x)f (x)f 00 (x)S (x) = 1 −=.(f 0 (x))2(f 0 (x))20(2)Ñõîäèìîñòü ìåòîäà Íüþòîíà è îöåíêà ñõîäèìîñòèS 0 (x∗ ) = 0.zn = xn − x∗ ïîãðåøíîñòü.77Çàìåòèì, ÷òîÏóñòüÒîãäàz n+1 = xn+1 − x∗ = S(xn ) − S(x∗ ) = S(zn + x∗ ) − S(x∗ ).Âîñïîëüçóåìñÿ ôîðìóëîé Òåéëîðà ñ îñòàòî÷íûì ÷ëåíîì â ôîðìå Ëàãðàíæà:11z n+1 = S(x∗ ) + S 0 (x∗ )zn + S 00 (x̃n )zn2 − S(x∗ ) = S 00 (x̃n )zn2 ,22ãäåx̃n = xn + θzn , |θ| < 1.Ïóñòü ∃M > 0 òàêîå, ÷òî1 00|S (x)| ≤ M,2x ∈ Ua (x∗ ).(3)Òîãäà|zn+1 | ≤ M |zn |2 ,M |zn+1 | ≤ (M |zn |)2 .Ïðèìåíèì ýòî íåðàâåíñòâî ðåêóðñèâíî, ïîëó÷èìnM |zn | ≤ (M |z0 |)2 ,1n(M |z0 |)2 .Mn → ∞ ïîëó÷àåì |zn | → 0 ⇒ xn → x∗ .|zn | ≤ÅñëèM |z0 | < 1,òî ïðèÒàêèì îáðàçîì, äëÿ ñõîäèìîñòè äàííîãî ìåòîäà äîñòàòî÷íî ïîòðåáîâàòü1.M(4)1n(M |x0 − x∗ |)2 .M(5)|z0 | = |x0 − x∗ | ≤Äëÿznèìååì îöåíêó|zn | = |xn − x∗ | ≤Ìû äîêàçàëè ñëåäóþùóþ òåîðåìó.Ñõîäèìîñòü ìåòîäà Íüþòîíà è îöåíêà ñõîäèìîñòèÒåîðåìà∃M > 078(îá îöåíêå ñêîðîñòè ñõîäèìîñòè ìåòîäà Íüþòîíà).
Ïóñòüòàêîå, ÷òî0 1 f (x)f 0 (x) ≤M2 (f 0 (x))2 |x0 − x∗ | ≤∀x ∈ Ua (x∗ ),1.MÒîãäà ìåòîä Íüþòîíà ñõîäèòñÿ è èìååò ìåñòî îöåíêà|xn − x∗ | ≤1n(M |x0 − x∗ |)2 .MÇàìå÷àíèå. Åñëè ìåòîä Íüþòîíà ñõîäèòñÿ, òî îí ñõîäèòñÿ î÷åíüáûñòðî.Çàìå÷àíèå. Íà÷àëüíîå ïðèáëèæåíèå äîëæíî áûòü áëèçêî ê êîðíþ (âñîîòâåòñòâèè ñ óñëîâèåì (4)).Íàïîìíèì, ÷òî ìîäèôèöèðîâàííûé ìåòîä Íüþòîíà èìååò âèä:xn+1 = xn −Äëÿ ýòîãî ìåòîäàS(x)f (xn ).f 0 (x0 )èìååò âèäS(x) = x −f (x).f 0 (x0 )Äëÿ ýòîãî ìåòîäà àíàëîãè÷íîå óòâåðæäåíèå íå èìååò ìåñòî, èáî0â îáùåì ñëó÷àå.S 0 (x∗ ) 6=Ãëàâà IVÐàçíîñòíûå ìåòîäû ðåøåíèÿçàäà÷ ìàòåìàòè÷åñêîé ôèçèêè1Ðàçíîñòíûå ñõåìû äëÿ ïåðâîé êðàåâîé çàäà÷è äëÿ óðàâíåíèÿ òåïëîïðîâîäíîñòèÐàññìîòðèì îáëàñòüD = {(x, y) ∈ R2 : 0 < x < 1, 0 < t ≤ T } (Tçàäàííîå ïîëîæèòåëüíîå ÷èñëî).Çàïèøåì ïåðâóþ êðàåâóþ çàäà÷ó äëÿ óðàâíåíèÿ òåïëîïðîâîäíîñòè âýòîé îáëàñòè:∂ 2u∂u= 2 + f (x, t), (x, t) ∈ D,∂t∂t(u(0, t) = µ1 (t),u(1, t) = µ2 (t),êðàåâûå óñëîâèÿ:(1)(2)íà÷àëüíîå óñëîâèå:u(x, 0) = u0 (x).Ââåäåì ñëåäóþùèå îáîçíà÷åíèÿ:ωh = {xi = ih, i = 1, .
. . , N − 1, hN = 1},ω h = {xi = ih, i = 0, . . . , N, hN = 1},ωτ = {tj = jτ, j = 1, . . . , j0 , τ j0 = T },ω τ = {tj = jτ, j = 0, . . . , j0 , τ j0 = T },79(3)Ðàçíîñòíûå ñõåìû äëÿ ïåðâîé êðàåâîé çàäà÷è äëÿ óðàâíåíèÿòåïëîïðîâîäíîñòè80ωτ h = ωτ × ωh ,ωτ h = ωτ × ωh,uni = u(xi , tn ),fin = f (xi , tn ).ω∗ω ∗ íàçûâàþòñÿ ñåòêàìè, ýëåìåíòû ýòèõ ìíîæåñòâ óçëàìè. Çíà÷åíèÿ τ è h íàçûâàþòñÿ øàãàìè ñåòêè.
Âíóòðåííèìè óçëàìèíàçîâåì óçëû ñåòêè ωτ h .Áóäåì îáîçíà÷àòü ÷èñëåííîå ðåøåíèå ïîñòàâëåííîé çàäà÷è ÷åðåç y(x, t).ÌíîæåñòâàèÏóñòüyin = y(xi , tn ).ßâíàÿ ðàçíîñòíàÿ ñõåìàÇàïèøåì ðàññìàòðèâàåìóþ çàäà÷ó:∂ 2u∂u= 2 + f (x, t),∂t∂t0 < x < 1,0 < t ≤ T,(4)êðàåâûå óñëîâèÿ:(u(0, t) = µ1 (t),u(1, t) = µ2 (t),(5)íà÷àëüíîå óñëîâèå:u(x, 0) = u0 (x).(6)Ðàçíîñòíûé àíàëîã çàäà÷è (4) (6) èìååò âèä:ny n − 2yin + yi+1yin+1 − yin= i−1+ f (xi , tn ),τh2(y0n+1 = µ1 (tn+1 ),n+1yN= µ2 (tn+1 ),yi0 = u0 (xi ),Ìíîæåñòâî óçëîâ(xi , tn ) ∈ ωτ h ,tn+1 ∈ ω τ ,tn+1 ∈ ω τ ,(8)xi ∈ ω h .{(xi , tn ), i = 0, .
. . , N }íàçûâàåòñÿ(9)n-ìñëîåì.Ïðè èçó÷åíèè ðàçíîñòíûõ ñõåì âîçíèêàþò ñëåäóþùèå âîïðîñû:1. Ñóùåñòâîâàíèå è åäèíñòâåííîñòü ðåøåíèÿ(7)Ðàçíîñòíûå ñõåìû äëÿ ïåðâîé êðàåâîé çàäà÷è äëÿ óðàâíåíèÿòåïëîïðîâîäíîñòè812. Ïîãðåøíîñòü àïïðîêñèìàöèè ðàçíîñòíîé ñõåìû3. Àëãîðèòì íàõîæäåíèÿ ÷èñëåííîãî ðåøåíèÿ4. Èññëåäîâàíèå óñòîé÷èâîñòè ðàçíîñòíîé ñõåìû5. Îöåíêà ñêîðîñòè ñõîäèìîñòè ðàçíîñòíîé ñõåìûÎòâåòèì íà âîïðîñû 1 è 3 äëÿ ÿâíîé ðàçíîñòíîé ñõåìû. Ïåðåïèøåì(7) â âèäåyin+1 = yin +Çíà÷åíèÿy(8). Çíà÷åíèÿτ nn(yi−1 − 2yin + yi+1) + τ fin ,2hâ ãðàíè÷íûõ óçëàõ (iyn = 0ïðèi = 1, . . . , N − 1.= 0, i = N )(10)çàäàíû ôîðìóëàìè ôîðìóëîé (9).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
