Лекции (1163663), страница 7
Текст из файла (страница 7)
Ïåðåéäåì ê ÿçûêó ïîãðåøíîñòåéXXaij zjn+1aij zjn+1 −aii zin+1 = −|aii ||zin+1 |≤j<iXj<i|aij ||zjn |kz n+1 k∞ = |zkn+1 |,+j>iXj>i|aij ||zjn |zkn+1 - ñàìàÿ áîëüøàÿ êîìïîíåíòà53Ðàññìîòðèì äëÿ ñëó÷àÿ i = kXX|akk |kz n+1 k∞ ≤|akj |kz n+1 k∞ +|akj |kz n k∞j<k X⇒ kz n+1 k∞ ≤Xj>k|akk | −âûíîñèì kz n+1 k∞ ⇒j>k|akj |X|akj |kz n k∞ ≤ qkz n k∞ò.ê.X j<kX|akj | ≤ q|akk | −|akj | < q(|akk | −|akj |).j>kj<kA = AT > 0Ax = b÷.ò.ä.j<km ≤ λ(A) ≤ M(Ax, x)≤ M1B = B T > 0,0 < m1 ≤(Bx, x)Bxn+1 = Bxn − α(Axn − b)MÀ1mM1M¿m1mÒî÷íîå ðåøåíèå: Bx = Bx − α(Ax − b).
Ðåøàåì, ïîëó÷àåì óðàâíåíèå íà ïîãðåøíîñòüBz n+1 = Bz n − αAz n| · B −1/2 (ñëåâà)B 1/2 z n+1 = B 1/2 z n − αB −1/2 Az 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)2). ω(x) ==Ó ýòîé ôóíêöèè äîñòèãàþòñÿ inf - íàèìåíüøåå ñîáñòâåííîå(x, x)çíà÷åíèå, sup - íàèáîëüøåå(Ay, y), ò.ê. B −1/2 x = y(By, y)M1 − m12⇒ kE − αCk2 ≤,α=M1 + m1M1 + m1v n = B 1/2pz npkv n 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 k2mrµ¶n 0µ¶2nM−mkvkM−mM112112kz n k2 ≤kz 0 k2 , ò.ê.≤√M1 + m1m2m2 M1 + m1v 0 = B 1/2 z 0kv 0 k2 ≤ kB 1/2 k2 kz 0 k2 ≤54√M2 · kz 0 k2 .14Ëåêöèÿ 14(1).Íåëèíåéíûå óðàâíåíèÿ.Ïóñòü çàäàí îòðåçîê [a, b], è èçâåñòíî, ÷òî íà íåì ∃ ðåøåíèå çàäà÷èf (x) = 0| b|aò.å.
∃ x̄ : f (x̄) = 0.Äëÿ ðåøåíèÿ íåëèíåéíûõ óðàâíåíèé èñïîëüçóþòñÿ èòåðàöèîííûå ìåòîäû, â êîòîðûõñòðîÿòñÿ ïîñëåäîâàòåëüíîñòè {xn } : xn → x̄. Åñòü ìåòîäû, â êîòîðûõ ñòðîÿòñÿ {xn } :f (xn ) → 0. Ñ òàêèìè ìåòîäàìè íàäî îáðàùàòüñÿ ïîîñòîðîæíåå:Ïðèìåð.y69f (x)0xn = n, f (xn ) → 0xn →/ x̄-x1. Ìåòîä ïîëîâèííîãî äåëåíèÿ (áèñåêöèÿ).Ðàññìîòðèì f (x) = 0. Ôóíêöèÿ äîëæíà áûòü íåïðåðûâíà. Åñëè f (a)f (b) < 0 äåëèì îòðåçîê ïîïîëàìÏðè óñëîâèè |4n | < εçàêàí÷èâàåì ïðîöåññ|a|c| %b &2. Ãðóïïà èòåðàöèîííûõ ìåòîäîâ âèäà|a|c|c|bxn+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.
Ýòî áóäåò552a. Ìåòîä ñåêóùèõ.y06%%%%%%%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Äëÿ îñóùåñòâèìîñòè ìåòîäà íåïðåðûâíîñòè ôóíêöèè íåäîñòàòî÷íî.¾Åñëè íà äîñòàòî÷íîì ó÷àñòêå îêîëî êîðíÿ ôóíêöèÿ ñîõðàíÿåò âûïóêëîñòü, òîìåòîä îñóùåñòâèì¿ - ïðèìåðíàÿ ôîðìóëèðîâêà.2b. Ìåòîä êàñàòåëüíûõ (ìåòîä Íüþòîíà).56y6¢¢¢f (xn )¢xn+1 = xn − 0¢f (xn ),¢, ¢,x, ¢xn+2 ¢xn+1 xn¢¢0( äàëüíåéøåì áóäåò ðàññììîòðåíî îáîáùåíèå ýòîãî ìåòîäà íà ñëó÷àé ìíîãèõ íåèçâåñòíûõè óðàâíåíèé)Ïóñòü íóæíî íàéòè âñå êîðíè.
Âûáèðàåìx0 : {xn } → x̄1 - íàøëè îäèí êîðåíüx̃0 : {x̃n } → x̃1 - äëÿ ïîèñêà 2-ãî êîðíÿ.f (x)Åñëè 2-îé ðàç ïîëó÷èì 1-é êîðåíü, òî íàäî ðàññìîòðåòü óðàâíåíèå, è èñêàòüx − x̄1åãî êîðíè. Åñëè îïÿòü òîò æå, òî êîðåíü êðàòíîñòè 2.Íî êîðíè ìîãóò áûòü êîìïëåêñòíûå.3. (íà ýêçàìåíå íå áóäåò)Çàìåíèì ôóíêöèþ íà ïàðàáîëó (à íå íà ëèí. ôóíêöèþ)y60xn−2 xn−1 xnxn+1xÏî òðåì òî÷êàì xn−2 , xn−1 , xn ñòðîèì ïàðàáîëó. Êîðíè ó "ïàðàáîëû" u ±√ ¾Åñëè u ≥ 0, òî âûáèðàåì êîðåíü u + √vïðîñòî ïðàâèëîÅñëè u < 0, òî âûáèðàåì êîðåíü u − v57√v.√Åñëè D < 0, òî u ± i v .Êðèòåðèé îêîí÷àíèÿ èòåðàöèé |xk − xk−1 | < ε. íåêîòîðûõ èòåðàöèîííûõ ìåòîäàõ èñïîëüçóåòñÿ îáðàòíàÿ ôóíêöèÿ, (ïðàâäà âëåêöèÿõ ýòî íåïîíÿòíî).Îïðåäåëåíèå. Ãîâîðÿò, ÷òî èòåðàöèîííûé ìåòîä èìååò ïîðÿäîê ñêîðîñòè ñõîäèìîñòèp, åñëè|xn+1 − x̄| ≤ C · |xn − x̄|p .Åñëè p = 1, òî äîëæíî áûòü C < 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̄)% °=2Ñ÷èòàåì, ÷òî xn äîñòàòî÷íî áëèçêî ê êîðíþ. Îòáðàñûâàÿ ñëàãàåìûå ìàëîãî ïîðÿäêà,ïîëó÷èì°= a1 (xn − x̄) + a2 (xn − x̄)2 + ō¯((xn − x̄)2 )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 .58Èëëþñòðàöèè ïîâåäåíèÿ ìåòîäà ïðîñòîé èòåðàöèè.6y Ïðèáëèæåíèå ñ îäíîé ñòîðîíû¡-¡¡0 < ϕ0 < 1¡¡¡¡0 ¡¡¡x1 x2 x3x6yÑ ðàçíûõ ñòîðîí¡¡¡−1 < ϕ0 < 0-¡¡¡¡0 ¡¡¡x1 x3 x2xxn+1 = ϕ(xn )êðèòåðèè îñòàíîâêè½|xn+1 − xn | < ε|f (xn+1 )| < εÏåðâûé êðèòåðèé îñòàíîâêè ðàñ÷åòà ìîæåò äàòü ïëîõîé ðåçóëüòàò, åñëè ϕ0 ≈ 1,è ôóíêöèÿ y = ϕ(x) áëèçêà ê y = x, íî äî òî÷êè ïåðåñå÷åíèÿ åùå î÷åíü äàëåêî(ëåâûé ðèñóíîê).
Âòîðîé êðèòåðèé ìîæåò íå ñðàáîòàòü, êîãäà ϕ0 ≈ −1, èçìåíåíèÿxn -íûõ âåëèêè (ïî÷òè çàöèêëèâàþùèéñÿ ìåòîä), à ñàìà ôóíêöèÿ f (x) ìàëà (ïðàâûéðèñóíîê).Ðàññìîòðèì 2 ñëó÷àé.|xn+1 − x̄| ≤ C|xn − x̄|2 .Çàäà÷à äëÿ ñàìîñòîÿòåëüíîãî ðåøåíèÿf (xn ), x̄ : f (x̄) = 0 ⇒ ϕ0 (x̄) = 0.xn+1 = xn − 0f (x ){z n }|ϕ(xn )Ïðèìåð: f (x) = (x − x̄)p = 0 , p = 2, 3, ...Ïðèìåíèì ìåòîä Íüþòîíà:f (xn )(xn − x̄)p(xn − x̄)=x−= xn −,n0p−1f (xn )p(xn − x̄)p1(xn − x̄) 0, ϕ (x) = 1 − 6= 0 ïðè p 6= 1,ϕ(xn ) = xn −ppp−1ϕ0 (x) =pxn+1 = xn −Ñêîðîñòü ñõîäèìîñòè ìåòîäà ê êîðíþ õàðàêòåðèçóåòñÿ âåëè÷èíîé |ϕ0 | < 1. Èç ýòîãîïðèìåðà âèäíî, ÷òî ïðè áîëüøèõ p ñêîðîñòü ñõîäèìîñòè "óìåíüøàåòñÿ" , ò.å.
êðàòíûåêîðíè óõóäøàþò ìåòîä Íüþòîíà.5915Ëåêöèÿ 15(2).fi (x1 , ..., xm ) = 0 (Rm ) i = 1, ..., m- ñèñòåìà m óðàâíåíèé ñ m íåèçâåñòíûìè.Ìåòîä: x̄ = ϕ̄(x̄) , (x̄n+1 = ϕ̄(x̄n ))- êîãäà ìåòîä ñõîäèòñÿ?Ïóñòü èìååòñÿ 2 ËÍÏ X è Y è îïåðàòîð F : X → Y .Îïðåäåëåíèå. Ëèíåéíûé îïåðàòîð : X → Y - ïðîèçâîäíàÿ îïåðàòîðà F â ò. x ,åñëèkF (x + h) − F (x) − P hk = o(khk).Îáîçíà÷åíèå P = F 0 .µ¶∂fi.∂xjÅñëè F = (f1 , f2 , ..., fm )T , òî F 0 (x) =Ðàññìîòðèì óðàâíåíèå 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, ò.÷. ∀ x ∈ U (x̄, a) ∃ a1 , a2 , 0 ≤ a1 , a2 < ∞, ò.÷.1.
k (F 0 (x̄n ))−1 kY ≤ C1 ;2. ∀ u1 , u2 ∈ U (x̄, a) kF (u1 ) − F (u2 ) − F 0 (u2 )(u1 − u2 )k ≤ a2 ku1 − u2 k2 .Òåîðåìà. C := a1 · a2 , b := min{a, c−1 }Ïóñòü âûïîëíåíû óñëîâèÿ 1, 2 è x0 ∈ U (x̄, b), òîãäà xn → x̄ ïðè ýòîì¡¢2nkxn − x̄k ≤ C −1 Ckx0 − x̄k .60I Èíäóêöèÿ: âñå ïðèáëèæåíèÿ ∈ U : xn ∈ U (x̄, b); u1 = x̄, u2 = xn , ñëåäîâàòåëüíî (ñì.óñë.2)kF (x̄) − F (xn ) − F 0 (x̄n )(x̄ − xn )kY ≤ a1 kx̄ − xn k2 , ïðè÷åìF (xn ) = −F 0 (xn )(xn+1 − xn ) è F (x̄) = 0 çíà÷èòkF 0 (xn )(xn+1 − x̄)kY ≤ a2 kxn − x̄k2kxn+1 − x̄k = k(F 0 (xn ))−1 F 0 (xn )(xn+1 − xn ) ≤ a1 a2 kxn − x̄k2X ≤ a1 a2 b2 ≤ b∀ n kxn+1 − x̄kX ≤ Ckxn − x̄k2Xqn = Ckxn − x̄kX ⇒ qn+1 ≤ qn2³ ´2kk+12n2= q02÷òî èÍàäî ïîêàçàòü qn ≤ q0 .
Ïî èíäóêöèè n = 0 - âåðíî; qk+1 ≤ qk ≤ q02òð.ä.J ,̈_×èñëåííîå ðåøåíèå çàäà÷è Êîøè äëÿ ÎÄÓ.½y 0 (x) = f (x, y(x))y(x0 ) = y0Ïîïûòàåìñÿ ïîñòðîèòü ïîñëåäîâàòåëüíîñòü {y n (x)} → y(x)Åñòü ïîñëåäîâàòåëüíîñòü òî÷åê? y1 ? y2? yN? y0| | ||x0 x1 x1 . . . x NÁóäåì ñ÷èòàòü, ÷òîxn+1 − xn = h =xN − x0NÈç ôîðìóëû Òåéëîðà èìååìy(xn+1 ) − y(xn )= f (xn , y(xn )) + O(h).hÁóäåì ñ÷èòàòü h äîñòàòî÷íî ìàëûì è îòáðîñèì O(). Ïîëó÷èì ðàñ÷åòíóþ ôîðìóëóyn+1 − yn= f (xn , yn ).hÎïðåäåëåíèå.• Ãëîáàëüíàÿ îøèáêà (ïîãðåøíîñòü) En = yn − y(xn ).• Ëîêàëüíàÿ îøèáêà (ïîãðåøíîñòü) en = yn − ỹ(xn ), ãäå ỹ - ðåøåíèå çàäà÷è½ 0ỹ (x) = f (x, ỹ(x))ỹ(xn−1 ) = yn−161Òåîðåìà.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
