Численные методы. Ионкин (2009) (формат хуже) (1160431), страница 8

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 8)

Ëîêàëèçóåì êîðíè (ïðè ýòîì êîðíè ìîãóò áûòü êîìïëåêñíûå)2. Ñòðîèì èòåðàöèîííûé ìåòîä íàõîæäåíèÿ êîðíÿÎïðåäåëåíèå. a-îêðåñòíîñòüþ êîðíÿ x∗ íàçûâàåòñÿ ìíîæåñòâî òî÷åêUa (x∗ ) = {x : |x − x∗ | ≤ a}Ðàññìîòðèì ñïîñîáû ëîêàëèçàöèè êîðíÿ:1. Ðàçîáüåì îòðåçîê[a, b]ìíîæåñòâîì òî÷åê{xi }N1a ≤ x0 < x1 < . . . < xN ≤ b70Ìåòîä ïðîñòîé èòåðàöèè71Òîãäà ìîæíî óòâåðæäàòü, ÷òî åñëè[xi−1 ..xi ]f (xi−1 )f (xi ) < 0),òî íà îòðåçêååñòü ïî êðàéíåé ìåðå îäèí êîðåíü (òàêæå èõ ìîæåò áûòüíå÷åòíîå ÷èñëî).

Åñëè æåf (xi−1 )f (xi ) > 0), òî ñêàçàòü íè÷åãî íåëü-çÿ, òàê êàê íà ýòîì îòðåçêå ëèáî ÷åòíîå ÷èñëî êîðíåé, ëèáî êîðíåéíåò âîîáùå.2. Ìåòîä áèñåêöèè (äåëåíèÿ ïîïîëàì) Ïóñòüf (x) ∈ C[a, b]; f (a) < 0, f (b) > 0ÂîçüìåìÅñëèÅñëèÅñëèx0 =a+b.2f (x0 ) > 0, òî êîðåíü óðàâíåíèÿ x∗ ∈ (a, x0 )f (x0 ) < 0 , òî êîðåíü óðàâíåíèÿ x∗ ∈ (x0 , b)f (x0 ) = 0, òî ìû íàøëè êîðåíü óðàâíåíèÿ.x +ba+x0, âî âòîðîì x1 = 0, è àíàëî22ãè÷íî ïîâîòðèì ïðîöåäóðó ëîêàëèçàöèè êîðíÿ, è òàê äàëåå.Âî ïåðâîì ñëó÷àå âîçüìåìx1 = ñëó÷àå, åñëè äàíà ñèñòåìà óðàâíåíèéf1 (x1 , . . .

, xm ) = 0,...fm (x1 , . . . , xm ) = 0,åå ìîæíî ïðåäñòàâèòü â âèäå(x1 , x2 , . . . , xm )TŸ2f~(~x) = 0,ãäåf~ = (f1 , f2 , . . . , fm )T , ~x =Ìåòîä ïðîñòîé èòåðàöèèÈòàê, ìû ðåøàåì óðàâíåíèåf (x) = 0x∗- êîðåíü óðàâíåíèÿ, ëîêàëèçîâàííûé íà(1)Ua (x∗ )Çàìåíèì óðàâíåíèå íà ýêâèâàëåíòíîåx = S(x)(2)Ìåòîä ïðîñòîé èòåðàöèè72S(x) = x + r(x)f (x)ãäå ôóíêöèÿr(x)íå ìåíÿåò çíàê íàÏîñòðîèì ïîñëåäîâàòåëüíîñòü{xn }(3)Ua (x∗ )ñëåäóþùèì îáðàçîì:x0 ∈ Ua (x∗ )xn+1 = S(xn ), n = 0, 1, . . .(4)Îïðåäåëåíèå. Ôóíêöèÿ S(x) Ëèïøèö-íåïðåðûâíà(óäîâëåòâîðÿåò óñëîâèþ Ëèïøèöà) ñ êîíñòàíòîé q >0, åñëè|S(x1 ) − S(x2 )| ≤ q|x1 − x2 |, ∀x1 , x2 ∈ (a, b)Óòâåðæäåíèå. Åñëè 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, .

Характеристики

Список файлов лекций