Ответы на экзаменационные вопросы (1163657), страница 11
Текст из файла (страница 11)
Óðàâíåíèå äëÿ îøèáêèBet + Ae = 0⇔Bek+1 − ek+ Aek = 0τóìíîæèì ñêàëÿðíî íà 2τ et , èñïîëüçóåì òîæäåñòâî(Ae, 2τ et ) ≡ kek+1 k2A − kek k2A − τ 2 ket k2A ,ãäå kek2A = (Ae, e),ïîëó÷àåì "ýíåðãåòè÷åñêîå" òîæäåñòâî´³τ2τ (B − A)et , et ) + kek+1 kA = kek kA .274Èñïîëüçóåì ýêâèâàëåíòíîñòü âñåõ íîðì â êîíå÷íîìåðíîì ïðîñòðàíñòâå´³τ2τ (B − A)B −1 Aek , B −1 Aek ) + kek+1 kA = kek kA ,2kek+1 kA = kek kA − 2τ kek k∗ ,kek+1 kA = kek kA − 2τ εkek kA ,kek+1 kA = qkek kA ,q < 1.Èç Ëåêöèè 13:A = AT > 0Ax = bm ≤ λ(A) ≤ M(Ax, x)≤ M1B = B T > 0,0 < m1 ≤(Bx, x)Bxn+1 = Bxn − α(Axn − b)MÀ1mMM1¿mm1Òî÷íîå ðåøåíèå: Bx = Bx − α(Ax − b). Ðåøàåì, ïîëó÷àåì óðàâíåíèå íà ïîãðåøíîñòüBz n+1 = Bz n − αAz n| · B −1/2 (ñëåâà)1/2n+11/2n−1/2B z= B z − αBAz nÏóñòü B 1/2 z n = v n ⇒ z n = B −1/2 v n ⇒⇒ v n+1 = v n − αCv n , ãäå C = B −1/2 AB 1/2v n+1 = (E − αC)v nÎöåíèì ñîáñòâåííûå çíà÷åíèÿ ìàòðèöû C.1).
C = C + > 0 Ä/Ç.(Cx, x)=Ó ýòîé ôóíêöèè äîñòèãàþòñÿ inf - íàèìåíüøåå ñîáñòâåííîå2). ω(x) =(x, x)çíà÷åíèå, sup - íàèáîëüøåå(Ay, y), ò.ê. B −1/2 x = y(By, y)M1 − m12,⇒ kE − αCk2 ≤α=M1 + m1M1 + m1nv n = B 1/2pzpnkv k2 = (B 1/2 z n , B 1/2 z n ) = (Bz n , z n )= ω(B 1/2 y) =0 < m2 ≤ λ(B) ≤ M21z n = B −1/2 v nkz n k2 ≤ kv n k2 · kB −1/2 k2 ≤ √ kv n k2m2r¶µ¶n 0µnM−mMkvkM−m112211kz 0 k2 , ò.ê.≤kz n k2 ≤√m2 M1 + m1m2M1 + m1v 0 = B 1/2 z 0kv 0 k2 ≤ kB 1/2 k2 kz 0 k2 ≤75√M2 · kz 0 k2 .32×èñëåííûå ìåòîäû ðåøåíèÿ ñèñòåì íåëèíåéíûõóðàâíåíèé.Ìåòîä ïðîñòîé èòåðàöèè.Ìåòîä êàñàòåëüíûõ.Âû÷èñëåíèå êðàòíûõ êîðíåé.Ìåòîä áèñåêöèé ýòî ìåòîä äåëåíèÿ îòðåçêà ïîïîëàì.
Åñëè ôóíêöèÿ íà îòðåçêå íåïðåðûâíàè ïðèíèìàåò â êîíöàõ îòðåçêà çíà÷åíèÿ ðàçíûõ çíàêîâ, òî ìîæíî ðàçäåëèòü îòðåçîê ïîïîëàìè âûáðàòü òó ïîëîâèíêó, íà êîíöàõ êîòîðîé ôóíêöèÿ ïðèíèìàåò çíà÷åíèÿ ðàçíûõ çíàêîâ èò.ä. Òóò ëèáî òî÷íî â íîëü ïîïàäåì íà êàêîì-òî øàãå, ëèáî ñî ñêîðîñòüþ ãåîìåòðè÷åñêîéïðîãðåññèè ñ ïîêàçàòåëåì 1/2 áóäåì ïðèáëèæàòüñÿ ê êîðíþ ôóíêöèè.Äëÿ ðåøåíèÿ óðàâíåíèÿ x = ϕ(x) ïðèìåíÿåì ìåòîä ïðîñòîé èòåðàöèè ñëåäóþùèìîáðàçîì: âûáèðàåì íà÷àëüíîå ïðèáëèæåíèå èç êàêèõ-íèáóäü ñîîáðàæåíèé, âû÷èñëÿåìïîñëåäîâàòåëüíûå ïðèáëèæåíèÿ ïî ôîðìóëå xn+1 = ϕ(xn ).y6y=xk3 ¡¡ y=ϕ(x)¡¡k2 ¡¡¡Êîðíè k1 è k3 ìîæíî íàéòè¡ìåòîäîì ïðîñòîé èòåðàöèè.¡¡Êîðåíü k2 íåëüçÿ íàéòèk1 ¡ýòèì ìåòîäîì íè ïðè êàêîì¡¡âûáîðå íà÷àëüíîãî ïðèáëèæåíèÿ.0 ¡x¡¡¡¡¡Åñëè èìååòñÿ ñèñòåìà óðàâíåíèé, òî ìåòîä ïðîñòîé èòåðàöèè âûãëÿäèò òî÷íî òàê æå.Ìîæíî âåçäå äëÿ íàãëÿäíîñòè ïðèðèñîâàòü çíàê âåêòîðà:Âûáèðàåì ~x 0 , âû÷èñëÿåì ~x n+1 = ϕ~ (~x n ),ïðèìåíÿåì êàêîé-íèáóäü êðèòåðèé îñòàíîâêè ðàñ÷åòà.
Êîíå÷íî, êðèòåðèè âûãëÿäÿòñòàíäàðòíîkxn − xn−1 k≤ ε,kxn − xn−1 k ≤ ε èëèkxn kãäå ε òðåáóåìàÿ òî÷íîñòü, êîòîðóþ òîæå çàäàåì ñàìè. Ýòî â ñëó÷àå, åñëè ïðîñòðàíñòâîíîðìèðóåìîå, è ìû çíàåì êàêóþ âçÿòü íîðìó.Ôîðìóëèðîâêè î ñõîäèìîñòè ìåòîäà ïðîñòîé èòåðàöèè ïî÷åìó-òî ïðèíÿòî äåëàòü íå âíîðìèðîâàííîì ïðîñòðàíñòâå, à â ïîëíîì ìåòðè÷åñêîì, â êîòîðîì åñòü ìåòðèêà ρ(x, y).76Ôóíêöèÿ ϕ(x) ÿâëÿåòñÿ ñæèìàþùèì îòîáðàæåíèåì, åñëè ... ýòî âñå çíàþò. Ñæèìàåìîñòüìîæåò áûòü íà êàêèõ-òî ó÷àñòêàõ, à íà äðóãèõ åå ìîæåò è íå áûòü.
Äîñòàòî÷íûì óñëîâèåìñæèìàåìîñòè ìîæåò áûòü|ϕ0 (x)| ≤ q < 1 èëè°°°°°°°°°°°°°∂ϕ1∂x1∂ϕ2∂x1...∂ϕN∂x1∂ϕ1∂x2∂ϕ2∂x2...∂ϕN∂x2............∂ϕ1∂xN∂ϕ2∂xN...∂ϕN∂xN°°°°°°°°≤q<1°°°°°äëÿ õîòü êàêîé-íèáóäü íîðìû. Òåïåðü ÿñíî ïî ðèñóíêó, ïî÷åìó ê êîðíþ k2 íåëüçÿïðèáëèçèòüñÿ ìåòîäîì ïðîñòîé èòåðàöèè. Òàì ïðîèçâîäíàÿ ôóíêöèè áîëüøå åäèíèöû.Åñëè ìåòîä ïðîñòîé èòåðàöèè ñõîäèòñÿ, òî ñõîäèòñÿ îí íå õóæå, ÷åì ñî ñêîðîñòüþãåîìåòðè÷åñêîé ïðîãðåññèè.×èñëî k íàçûâàåòñÿ ïîðÿäêîì ìåòîäà, åñëè ñóùåñòâóþò ïîëîæèòåëüíûå êîíå÷íûåïîñòîÿííûå C1 è C2 òàêèå, ÷òî ñïðàâåëèâî íåðàâåíñòâîρ(xn+1 , X) ≤ C2 [ρ(xn , X)]kρ(xn , X) ≤ C1∀n = 1, 2, .
. .ãäå X òî÷íîå ðåøåíèå óðàâíåíèÿ.Ó ìåòîäà ïðîñòîé èòåðàöèè ïîðÿäîê ñêîðîñòè ñõîäèìîñòè íå ìåíüøå, ÷åì ïåðâûé. Ëó÷øåãîâîðèòü, ÷òî ïðîñòî ïåðâûé, ÷òîáû íå ïîïðîñèëè ïðèâåñòè ïðèìåð, êîãäà îí, íàïðèìåð1,35623461...Ýòîò âîïðîñ èçëîæåí â Ëåêöèè 14.2. Ãðóïïà èòåðàöèîííûõ ìåòîäîâ âèäàxn+1 = ϕ(xn , xn−1 , ..., xn−k ).Ðàññìàòðèâàþòñÿ òîëüêî k = 0 è k = 1.k = 0 - ìåòîä ïðîñòîé èòåðàöèè xn+1 = ϕ(xn ).k = 1.
Ïðîèíòåðïîëèðóåì íàøó ôóíêöèþ f (x) ≈ a0 x+a1 è ïîñòðîèì èòåðàöèîííûé ìåòîäâèäà xn+1 = ϕ(xn , xn−1 ), êîòîðûé ñâîäèòñÿ ê ðåøåíèþ ëèíåéíîãî óðàâíåíèÿ a0 x + a1 = 0.Ýòî áóäåò2a. Ìåòîä ñåêóùèõ.77y06%%%%%%%x%x% xnn−1% x6n+1%a0 =fn − fn−1xn − xn−1a1 =xn fn−1 − xn−1 fnxn − xn−1xn+1 = −a1a06ZZZZZZZZZZZZ0xZ -yxn−1xnxn+1Äëÿ îñóùåñòâèìîñòè ìåòîäà íåïðåðûâíîñòè ôóíêöèè íåäîñòàòî÷íî.¾Åñëè íà äîñòàòî÷íîì ó÷àñòêå îêîëî êîðíÿ ôóíêöèÿ ñîõðàíÿåò âûïóêëîñòü, òî ìåòîäîñóùåñòâèì¿ - ïðèìåðíàÿ ôîðìóëèðîâêà.Ðàññìîòðèì ìåòîä ïðîñòîé èòåðàöèè.xn+1 = ϕ(xn )f (x) = 0 ⇔ x = ϕ(x), íàïðèìåð x = x + g(x)f (x), g(x) 6= 0 ∀x.Ïðåäïîëàãàåòñÿ, ÷òî òî÷íîå ðåøåíèå x̄ óäîâëåòâîðÿåò óðàâíåíèþ: x̄ = ϕ(x̄). Èñïîëüçóÿôîðìóëó Òåéëîðà, ïîëó÷èìxn+1 − x̄ = ϕ(xn ) − ϕ(x̄) = ϕ(x̄ + (xn − x̄)) =1% =°= ϕ(x̄)% +ϕ0 (x̄) · (xn − x̄) + ϕ00 (x̄) · (xn − x̄)2 + ...
− ϕ(x̄)278Ñ÷èòàåì, ÷òî xn äîñòàòî÷íî áëèçêî ê êîðíþ. Îòáðàñûâàÿ ñëàãàåìûå ìàëîãî ïîðÿäêà,ïîëó÷èì=° a1 (xn − x̄) + a2 (xn − x̄)2 + ō¯((xn − x̄)2 )Îïðåäåëåíèå. Ãîâîðÿò, ÷òî èòåðàöèîííûé ìåòîä èìååò ïîðÿäîê ñêîðîñòè ñõîäèìîñòè p,åñëè|xn+1 − x̄| ≤ C · |xn − x̄|p .Åñëè p = 1, òî äîëæíî áûòü C < 1.1. Åñëè a1 6= 0, òî p = 1 è C ≈ a1 = ϕ0 (x̄). C - â îïðåäåëåíèè ñêîðîñòè ñõîäèìîñòè.Ñ÷èòàåì, ÷òî |ϕ(x̄)| < 1.2.
a1 (= ϕ0 (x̄)) = 0, òîãäà p = 2 è C ≈ a2 =ϕ00 (x̄).2Ðàññìîòðèì 1 ñëó÷àé.xn+1 − x̄ = ϕ(xn ) − ϕ(x̄)= ϕ0 (ξn )(xn − x̄) =ò.Ëàãð= ϕ0 (ξn )(ϕ(xn−1 ) − ϕ(x̄)) = ϕ0 (ξn )ϕ0 (ξn−1 )(xn−1 − x̄) = . . . == (x0 − x̄) · ϕ0 (ξn ) · . . . · ϕ0 (ξ0 )Åñëè âñå ïðèáëèæåíèÿ ëåæàò â îáëàñòè |ϕ(x)| ≤ q < 1 ñæèìàåìîñòè îòîáðàæåíèÿ, òî |xn+1 −x̄| ≤ const|ϕ0 (ξn )...ϕ0 (ξ0 )| ≤ q n .Èëëþñòðàöèè ïîâåäåíèÿ ìåòîäà ïðîñòîé èòåðàöèè.6y Ïðèáëèæåíèå ñ îäíîé ñòîðîíû¡-¡¡0 < ϕ0 < 1¡¡¡¡0 ¡¡x1 x2 x3¡-x6yÑ ðàçíûõ ñòîðîí¡¡¡−1 < ϕ0 < 0-¡¡¡¡0 ¡¡x1 x3 x2¡xxn+1 = ϕ(xn )êðèòåðèè îñòàíîâêè½|xn+1 − xn | < ε|f (xn+1 )| < εÏåðâûé êðèòåðèé îñòàíîâêè ðàñ÷åòà ìîæåò äàòü ïëîõîé ðåçóëüòàò, åñëè ϕ0 ≈ 1, è ôóíêöèÿy = ϕ(x) áëèçêà ê y = x, íî äî òî÷êè ïåðåñå÷åíèÿ åùå î÷åíü äàëåêî (ëåâûé ðèñóíîê).Âòîðîé êðèòåðèé ìîæåò íå ñðàáîòàòü, êîãäà ϕ0 ≈ −1, èçìåíåíèÿ xn -íûõ âåëèêè (ïî÷òèçàöèêëèâàþùèéñÿ ìåòîä), à ñàìà ôóíêöèÿ f (x) ìàëà (ïðàâûé ðèñóíîê).79Ðàññìîòðèì 2 ñëó÷àé.|xn+1 − x̄| ≤ C|xn − x̄|2 .33×èñëåííûå ìåòîäû ðåøåíèÿ ñèñòåì íåëèíåéíûõóðàâíåíèé.Ìåòîä Íüþòîíà.Ìåòîä Íüþòîíà, êîãäà êîëè÷åñòâî óðàâíåíèé íå ðàâíî êîëè÷åñòâó íåèçâåñòíûõ, òðåáóåòââåäåíèÿ íîâûõ ïîíÿòèé ðåøåíèé, ïîýòîìó çäåñü íå ðàññìàòðèâàåòñÿ.Óðàâíåíèå çàïèñûâàåòñÿ â âèäå f (x) = 0.
 ïðèíöèïå, óðàâíåíèå ìîæåò áûòü âåêòîðíûì,àðãóìåíò òîæå. Áóäåì ñ÷èòàòü, ÷òî óðàâíåíèé ñòîëüêî, ñêîëüêî íåèçâåñòíûõ.Äëÿ îäíîãî óðàâíåíèÿ ìåòîä Íüþòîíà ïðîõîäÿò â ñðåäíåé øêîëåx0 âûáèðàåì ñàìè, xn+1 = xn −f (xn )= xn − [f 0 (xn )]−1 f (xn ) âû÷èñëÿåì ïðè n = 0, 1, . .
.f 0 (xn )êðèòåðèé îêîí÷àíèÿ âû÷èñëåíèé îáû÷íûé - ïîêà ïîñëåäîâàòåëüíîñòü íå çàñòàáèëèçèðóåòñÿ.Âòîðîå ðàâåíñòâî ðàñ÷åòíîé ôîðìóëû èìååò áîëåå óíèâåðñàëüíóþ ôîðìó, òàê êàê âñëó÷àå ñèñòåìû óðàâíåíèé ðàñ÷åòíàÿ ôîðìóëà áóäåò âûãëÿäåòü òî÷íî òàê æå.  âåêòîðíîìñëó÷àå xn - âåêòîðû, êîòîðûå ëó÷øå âîñïðèíèìàòü êàê âåðòèêàëüíûå, f (xn ) - òîæå âåêòîðû,à f 0 (xn ) - ìàòðèöû nxn+1x11 xn+1 xn2 2 ... = ...xnNxn+1N − ∂f1 (xn )∂x1∂f2 (xn )∂x1...∂fN (xn )∂x1∂f1 (xn )∂x2∂f2 (xn )∂x2...∂fN (xn )∂x2∂f1 (xn )∂xN∂f2 (xn )...∂xN...
...∂fN (xn )...∂xN...−1f1n (xn ) f2n (xn ) ...nnfN (x )Ìåòîä Íüþòîíà, åñëè âûáðàòü íà÷àëüíîå ïðèáëèæåíèå òàê, ÷òîáû f 0 (x0 ) = 0, ñðàçóïðåäëàãàåò îñóùåñòâèòü äåëåíèå íà íîëü. Òàêîãî æå ìîæíî îæèäàòü íà ëþáîì øàãå. ÌåòîäÍüþòîíà ìîæåò çàöèêëèòüñÿ äàæå äëÿ îäíîãî óðàâíåíèÿ80f (x)60!aaaa!!!!!aaa!!ax(2k+1)x-Ìåòîä Íüþòîíà íàçûâàåòñÿìåòîäîì êàñàòåëüíûõ äëÿ ñëó÷àÿîäíîãî óðàâíåíèÿ.Âûáðàâ x0 , íàéäåì x1 , çàòåì x2 = x0 .x(2k)Åñëè êîðåíü óðàâíåíèÿ êðàòíûé, à òåì áîëåå ìíîãîêðàòíûé, òî ìåòîä Íüþòîíà ñõîäèòñÿìåäëåííî.
Åñëè æå êîðåíü íå êðàòíûé, è íà÷àëüíîå ïðèáëèæåíèå áëèçêî ê êîðíþ, òî ìåòîäÍüþòîíà ñõîäèòñÿ î÷åíü áûñòðî, ïîðÿäîê ñõîäèìîñòè â ýòîì ñëó÷àå íå ìåíåå 2. Ëó÷øåãîâîðèòü, ÷òî ðàâåí 2, ò.å.nkxn − XkH ≤ C −1 (Ckx0 − XkH )2 ,k . kH − êàêàÿ-íèáóäü íîðìà.(Õî)!Äàëåå ñôîðìóëèðîâàíû óñëîâèÿ, ñïåöèàëüíî ïîäîãíàííûå äëÿ óäîáñòâà äîêàçàòåëüñòâàâ äâå ñòðî÷êè ýòîãî íåðàâåíñòâà:Îáîçíà÷èì ÷åðåç Ωh = {x : kX − xkH < h} îòêðûòóþ (!) h - îêðåñòíîñòü ðåøåíèÿ, è ïóñòüïðè íåêîòîðûõ h, a1 a2 : 0 < h, 0 ≤ a1 , a2 < ∞, âûïîëíåíû óñëîâèÿ:1)k(F 0 (x))−1 ykH ≤ a1 kykYïðè x ∈ Ωhè ïðîèçâîëüíîì y;2)kF (u1 ) − F2 (u2 ) − F 0 (u2 )(u1 − u2 )kY ≤ a2 ku1 − u2 k2Hu1 , u2 ∈ Ωh .Îáîçíà÷èì òàêæå c = a1 a2 , b = min (h, c−1 ) .
Òîãäà ïðè íà÷àëüíîì óñëîâèè èç Ωh áóäåò (Õî!),áóêâû C, f íàäî òîëüêî ïîìåíÿòü íà c, F .Åñëè êîðåíü íå êðàòíûé, òî ìåòîä Íüþòîíà ðåøåíèÿ óðàâíåíèÿ f (x) = 0 ÿâëÿåòñÿìåòîäîì ïðîñòîé èòåðàöèè ðåøåíèÿ óðàâíåíèÿ x = ϕ(x), ãäå ϕ(x) = x − [f 0 (x)]−1 f (x), âîòòîëüêî ïîðÿäêè ñêîðîñòè ñõîäèìîñòè ó ýòèõ ìåòîäîâ (ïî÷åìó-òî) ðàçíûå.Ýòîò âîïðîñ èçëîæåí â Ëåêöèè 15.Ïóñòü èìååòñÿ 2 ËÍÏ X è Y è îïåðàòîð F : X → Y .Îïðåäåëåíèå.
Ëèíåéíûé îïåðàòîð : X → Y - ïðîèçâîäíàÿ îïåðàòîðà F â ò. x , åñëèkF (x + h) − F (x) − P hk = o(khk).Îáîçíà÷åíèå P = F 0 .81µÅñëè F = (f1 , f2 , ..., fm)T ,òîF 0 (x)=¶∂fi.∂xjÐàññìîòðèì óðàâíåíèå F (x̄) = 0.Ïðåäïîëàãàåì, ÷òî ñóùåñòâóåò ïðîèçâîäíàÿ îïåðàòîðà F . Äîïóñòèì, ïîëó÷èëè íåêîòîðîåïðèáëèæåíèå ê ðåøåíèþ.
Äîïóñòèì, îïåðàòîð ïðîèçâîäíîé äèàãîíàëèçèðóåì (îáðàòèì) âîêðåñòíîñòè ïðèáëèæåíèÿ. Èç ôîðìóëûF (x̄n ) − F (x̄) − P (x̄n )(x̄n − x̄) = o(kx̄n − x̄k).q0Âûáèðàÿ x̄n+1 âìåñòî x̄ è îòáðàñûâàÿ ÷ëåíû ìàëîãî ïîðÿäêà, ïîëó÷èì ðàñ÷åòíóþ ôîðìóëóìåòîäà Íüþòîíà¡¢−1x̄n+1 = x̄n − F 0 (x̄n )F (x̄n ).Íà êàæäîì øàãå íåîáõîäèìî âû÷èñëÿòü è îáðàùàòü ìàòðèöó - ïðîèçâîäíóþ îïåðàòîðà.(Äàëåå ÷åðòó íàä x ðèñóåì äëÿ îáîçíà÷åíèÿ ðåøåíèÿ.)Îáîçíà÷åíèå: U (x̄, a) - îòêðûòàÿ îêðåñòíîñòü òî÷êè x̄ ðàäèóñà a.Ïóñòü ∃ a, ò.÷.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
