Численные методы. Ионкин (2012) (v1.1) (косяки есть), страница 8

Îêàçûâàåòñÿ ÷òî ïðè ðàññìîòðåíèè ïðîñòîãî âàðèàíòà ñèñòåìû:1, x, x2 , ...., xn ;φi (x) = xiÈç ýòîé ñèñòåìû ñêàëÿðíûå ïðîèçâåäåíèÿ ýòèõ ôóíêöèé ðàññìàòðèâàþòñÿ êàêèíòåãðàëû:Zβρ(x)φk (x)φl (x) dx = (φk , φl )αÇäåñüρ(x) > 0- âåñîâàÿ ôóíêöèÿ.Åñëè áðàòü ðàçëè÷íûå âåñà, òî ìîæíî ïîñòðîèòü ñèñòåìó îðòîãîíàëüíûõ ïîëèíîìîâ: ßêîáè, Ëåæàíäðà, ×åáûøåâà è ò.ä.. Ïî ýòèì ïîëèíîìàì íàì óäîáíåé62ñòðîèòü ïðèáëèæåíèÿ.

Åñëè ñèñòåìà îðòîíîðìèðîâàííà, òî òîãäà íåòðóäíî âû÷èñëèòü îòêëîíåíèå íàèëó÷øåãî ñðåäíåêâàäðàòè÷íîãî ïðèáëèæåíèÿ:Zb[f (x) −F (c0 , c1 , ...., cn ) =2ck φk (x)] dx = (f, f ) −(f, f ) ≥nPíåðàâåíñòâî Áåññåëÿ: kf k2 ≥nPc2kk=0 ñëó÷àå ÎÍÁ - ïîëó÷àåìc2k ≥ 0c2k .k=0Òîãäà âûõîäèònXk=0k=0aÒîãäà ïîëó÷àåì, ÷òînX2ðàâåíñòâî Ïàðñåâàëÿ: kf k =nPc2kk=0Îáîáùåíèå:Ïóñòü èìåþòñÿ áàçèñíûå ôóíêöèè:φ0 (xi ), φ1 (xi ), ...., φn (xi )- çàäàííûå â óçëàõ{xi }Òîãäà ââîäèì ïðîñòðàíñòâî äèñêðåòíûõ ôóíêöèéH. íåì ââîäèì ñêàëÿðíîåïðîèçâåäåíèå äëÿ ïðîèçâîëüíûõ ôóíêöèé:(f, g) =nXfi gii=0Òîãäà ìîæíî ââåñòè íîðìó, ýòî áóäåò àíàëîã äèñêðåòíîé L2 íîðìû:nX1kf k = (f, f ) = (fi2 ) 2 )12i=0Äàëüøå ñòðîèìφ(xi ) =kf −nPck φk (xi ),òàêîé ÷òîáûk=0nXck φk (xi )k2 = F (c0 , c1 , ...., cn ) =k=0= (f, f ) − 2nXck (f, φk ) +k=0nXk=0cknXcl (φk φl )l=0Ñëåäîâàòåëüíî, â ñëó÷àå êîãäà è áàçèñíûå ôóíêöèè è ïðèáëèæàåìûå ôóíêöèèçàäàíû äèñêðåòíî, ìû ïîëó÷èì òàêóþ æå ñèñòåìó óðàâíåíèé äëÿ íàõîæäåíèÿ êîýôôèöèåíòîâc̄iîáîáùåííîãî ìíîãî÷ëåíà.

Ïîýòîìó âîïðîñû î ñóùåñòâîâàíèè èåäèíñòâåííîñòè íàèëó÷øåì ñðåäíåêâàäðàòè÷íîì ïðèáëèæåíèè â äèñêðåòíîì ñëó÷àå ðåøàþòñÿ àíàëîãè÷íî.63Ãëàâà 3×èñëåííîå ðåøåíèåíåëèíåéíûõ óðàâíåíèé èñèñòåì íåëèíåéíûõ óðàâíåíèéŸ 1. ÂâåäåíèåÈçó÷àÿ ïðîáëåìû ñîáñòâåííûõ çíà÷åíèé, ñòàíîâèòñÿ ÿñíî, ÷òî ñëîæíî íàéòèñïåêòð îïåðàòîðîâ àíàëèòè÷åñêè.Ïðîáëåìà íàõîæäåíèÿ ðåøåíèÿ íåëèíåéíîãî óðàâíåíèÿf (x) = 0 - î÷åíü àêòó-àëüíà.f (x)- ïðîèçâîëüíàÿ íåïðåðûâíàÿ ôóíêöèÿ. òàêèõ ñëó÷àÿõ íà÷àëüíîå ïðèáëèæåíèå íóæíî âûáèðàòü íå ñëó÷àéíûì.Ïîýòîìó êîðåíü íàäî ëîêàëèçîâàòü.1 ýòàïÏóñòüx∗- êîðåíü, ò.å.f (x∗ ) = 0;Òîãäà íàäî óêàçûâàòü îêðåñòíîñòü êîðíÿ:Ua (x∗ ) = {x : |x∗ − x| < a}2 ýòàïÒóò ìû îðãàíèçîâàâàåì èòåðàöèîííûé ñõîäÿùèéñÿ ïðîöåññf1 (x1 , x2 , ...., xm ) = 0 f (x , x , ...., x ) = 02 1 2m........fm (x1 , x2 , ...., xm ) = 0x̄ = (x1 , x2 , ...., xm )f¯ = (f1 , f2 , ...., fm )f¯(x̄) = 064xn → x∗(3.1)f : Rn → RnÑòîèò îòìåòèòü, ÷òî íåò êàíîíè÷åñêîãî àëãîðèòìà äëÿ ëîêàëèçàöèè êîðíåé.Óêàçàâ îêðåñòíîñòü - ìû íå âñåãäà ìîæåì çíàòü ñêîëüêî êîðíåé â ýòîé îêðåñòíîñòè.

Òàêæå ìîãóò áûòü êðàòíûå êîðíè.  ýòîé ãëàâå îñíîâíîå âíèìàíèå áóäåòóäåëåíî âòîðîìó ýòàïó.1 ñïîñîá ëîêàëèçàöèèÐàçîáüåì îêðåñòíîñòü íà óçëû:{xi }n f (xi )f (x) :È åñëè íàéäåòñÿ ïàðà óçëîâ, òàêèå, ÷òîf (xi )f (xi+1 ) < 0 ⇒ìåæäóxièxi+1åñòü õîòÿ áû îäèí êîðåíü.Òîãäà óæå ýòîò îòðåçîê ìîæíî ðàçìå÷àòü íà óçëû.2 ñïîñîá ëîêàëèçàöèè (Áèñåêöèÿ)f (a) < 0, f (b) > 0a+b∗Ðàññìàòðèâàåì ñåðåäèíó x0 =2 , åñëè f (x0 ) > 0 ⇒ x ∈ (a, x0 )Äåëèì îòðåçîê (a, x0 ) ïîïîëàì, è ò.ä.Áåðåòñÿ îòðåçîê[a; b] :Åñëè âûäåëèòü êîðåíüðàçëîæèòüx∗ , òî äëÿ òîãî, ÷òîáû ðàññìîòðåòü äðóãèå êîðíè, ìîæíîf (x):f (x) = (x − x∗ )g(x)è óæå ðàáîòàòü íàäg(x).Ÿ 2.

Ìåòîä ïðîñòîé èòåðàöèèf (x) = 0(3.2)Âñå ïðîèñõîäèò â âåùåñòâåííîì ïðîñòðàíñòâå.Òåïåðü íà÷èíàåì ðàáîòàåò â ëîêàëèçîâàííîé îêðåñòíîñòè - òåïåðü ñ÷èòàåì, ÷òîêîðåíü â îêðåñòíîñòè åñòü è îí îäèí.Çàïèñûâàåì óðàâíåíèå:ãäåx = S(x)(3.3)xn+1 = S(xn )(3.4)n = 0, 1, ... x0 ∈ Ua (x∗ )65Òåïåðü íàäî âûáðàòüS(x)- èìåííî âûáîðîì ýòîé ôóíêöèè îáóñëàâëèâàåòñÿìåòîä:S(x) = x + r(x)f (x)(3.5)Íàëîæèì îãðàíè÷åíèå:sgn r(x) 6= 0 x ∈ Ua (x∗ ) − ò.å.

r(x) íåìåíÿåò çíàêà âUaÎïðåäåëåíèå:S(x)Ua ,óäîâëåòâîðÿåò óñëîâèþ Ëèïøèöà ñ êîíñòàíòîéQíàUa ,åñëè∀x1 , x2èçâûïîëíåíî:|S(x1 ) − S(x2 )| ≤ Q|x1 − x2 |(3.6)Óòâåðæäåíèå:ÏóñòüS(x)- íåïðåðûâíà ïî Ëèïøèöó ñ êîíñòàíòîéïðèáëèæåíèå áåðåòñÿ èç îêðåñòíîñòèq < 1.Ïóñòü íà÷àëüíîåUa . Òîãäà ìåòîä ïðîñòîé èòåðàöèè ñõîäèòñÿ.Äîêàçàòåëüñòâî:Ïîêàæåì, ÷òî åñëèxn+1 ∈ Ua .òî è|xn+1 − x |:xn+1 = S(xn ):ÎöåíèìÒ.ê.xn ∈ Ua ,∗|xn+1 − x| = |S(xn ) − s(x∗ )| = {ïîóñëîâèþ Ëèïøèöà}≤ q|xn − x∗ | < |xn − x∗ | < a⇒≤xn+1 ∈ UaÇíà÷èò èç îêðåñòíîñòè ìåòîä íå âûõîäèò.Ïðèìåíÿÿ ýòó ôîðìóëó ðåêóððåíòíî, ïîëó÷èì, ÷òîà ïðèn→∞:lim q n = 0n→∞⇒|xn − x∗ | ≤ q n |x0 − x∗ |,lim xn = x.n→∞Çàìå÷àíèå 1:Ïóñòümax∗ |S 0 (x)| = q < 1x∈Ua (x )Òîãäà ìåòîä ïðîñòîé èòåðàöèè ñõîäèòñÿ.Çàìå÷àíèå 2:Ðàññìîòðèì ñëåäóþùèé èòåðàöèîííûé ïðîöåññ:xn+1 − xn+ f (xn ) = 0;τn = 0, 1, ....;66x0 ∈ Ua (x∗ );τ >0(3.7)Ïóñòü äëÿ îïðåäåëåííîñòèf 0 (x) < 0.S(x) = x − τ f (x)Òîãäà â ñèëóçàìå÷àíèÿ 1,S 0 (x) = 1 − τ f 0 (x),Îáîçíà÷èìÒîãäàåñëè|S 0 (x)| < 1,ïðè ïðåäïîëîæåíèè, ÷òîòî ñõîäèìîñòü îáåñïå÷åíàf- ãëàäêàÿM1 = max∗ |f 0 (x)|x∈Ua (x )|1 − τ M1 | < 1 :−1 < 1 − τ M1 < 1Çíà÷èò, çàïèñàííûé â âèäå 3.7 èòåðàöèîííûé ìåòîä ñτ :0 < τ <2M1-ñõîäèòñÿŸ 3.

Ìåòîä Ýéòêåíà óñêîðåíèÿ ñõîäèìîñòè èòåðàöèîííûõ ìåòîäîâÏóñòü íàì èçâåñòíî, ÷òî äâå ñîñåäíèå èòåðàöèè îòëè÷àþòñÿ:xn − x∗ = Aq n ;Òîãäàn = 0, 1, ....xn+1 − x∗ ≈ Aq n−1xn − x∗ ≈ Aq nxn+1 − x∗ ≈ Aq n+1Èç ôîðìóëû 3.10:x∗ ≈ xn+1 − Aq n+1(xn+1 − xn )2 = A2 q 2n (q − 1)2xn+1 − 2xn + xn−1 = Aq n−1 (q − 1)2(xn+1 − xn )2= Aq n+1xn+1 − 2xn + xn−1(xn+1 − xn )2x = xn+1 −(xn+1 − 2xn + xn−1 )67(3.8)(3.9)(3.10)Ðèñ. 3.1:Ÿ 4. Ìåòîä Íüþòîíà è ìåòîä ñåêóùèõÏî-ïðåæíåìó óðàâíåíèåf (x) = 0ëîêàëèçóåì êîðåíü è îêðåñòíîñòüUa (x∗ ).Ìåòîä Íüþòîíà:xãäån = 0, 1, 2..., x0 ∈ Ua (x∗ ).n+1Îáîçíà÷åíèå:(3.11)xnf (xn )=x − 0 nf (x ),nn-ÿèòåðàöèÿ.(3.12) äàííîì ñëó÷àå ìû íå çàáîòèìñÿ î ãëàäêîñòè,÷òîáû áûëî ïðîùå äîêàçûâàòü.Òàêæå äàííûé ìåòîä íàçûâàþò ìåòîäîì êàñàòåëüíûõ.Ìåòîä Íüþòîíà ñõîäèòñÿ î÷åíü áûñòðî, íóæíû îáû÷íî 34 èòåðàöèè äëÿ õîðîøåãî ðåçóëüòàòà.Ôîðìóëà 3.12 ïîëó÷àåòñÿ ðàçëîæåíèåì â îêðåñòíîñòè êîðíÿ ïî ôîðìóëå Òåéëîðà:f (x∗ ) = 0 = f (x) + (x∗ − x)f 0 (x) + ìàëîåÅñëèx∗ → xn+1 , x → xn ⇒0 = f (xn ) + (xn+1 − xn )f 0 (xn )Ïðîèçâîäíàÿ íå äîëæíà îáðàùàòüñÿ â íîëü! Îòñþäà ñëåäóåò 3.12.

Äëÿ ñèñòåìûáóäåò âñ¼ àíàëîãè÷íî.Âàæíî: ïðèìåíèìîñòü!Íåóäà÷íîå ïðèìåíåíèå ìåòîäà Íüþòîíà (çàöèêëèâàíèå) èçîáðàæåíî íà ðèñóíêå 3.2:68Ðèñ. 3.2:Ìîäèôèöèðîâàííûé ìåòîä Íüþòîíà:xn+1f (xn )=x − 0 0f (x )n(3.13) ýòîì ñëó÷àå ìû âñåãäà óâåðåíû â çíàêå, íå íàäî ëèøíèé ðàç ñ÷èòàòü; ñåðü¼çíàÿïëàòà î÷åíü ïëîõàÿ (ìåäëåííàÿ) ñõîäèìîñòü.Ìåòîä Íüþòîíà î÷åíü áûñòð ïî ñðàâíåíèþ ñ ìåòîäîì ïðîñòîé èòåðàöèè.Ìîäèôèöèðîâàííûé ìåòîä ïðèìåíÿåòñÿ íà ïðàêòèêå: ðåøàåì ñåðü¼çíóþ ïðîáëåìó, ñâÿçàííóþ ñ òåðìîÿäåðíûìè ðåàêöèÿìè. Ñëîæíûå íåëèíåéíûå äèôôåðåíöèàëüíûå óðàâíåíèÿ. Ðåøåíèå àíàëèòè÷åñêè çàòðóäíèòåëüíî, âîçìîæíî òîëüêîèòåðàöèîííîå ðåøåíèå.

Áóäåì ïðèìåíÿòü ìåòîä Íüþòîíà. Áûâàþò î÷åíü áûñòðîòåêóùèå ïðîöåññû, áûâàþò íå î÷åíü, íî íàäî âñ¼ ñ÷èòàòü âìåñòå, íà÷àëüíîåïðèáëèæåíèå âçÿòü áûâàåò òÿæåëî.Ðàññìîòðèì ñèñòåìû:f1 (x1 , x2 ) = 0; f2 (x1 , x2 ) = 0(x∗1 , x∗2 ): fi (x∗1 , x∗2 ) = 0; i = 1, 2.Ãëàäêîñòü ïî x1 , x2 ïðåäïîëàãàåì êàêóþ óãîäíî. (Íåïðåðûâíîñòè, î÷åâèäíî, íåÐåøåíèå õâàòèò.)Ïîâòîðÿåì âûâîä:0 = f1 (x∗1 , x∗2 ) = f1 (x1 , x2 ) − (x∗1 − x1 )∂f1 (x1 , x2 )∂f1 (x1 , x2 )+ (x∗2 − x2 )+ ìàëîå∂x1∂x20 = f2 (x∗1 , x∗2 ) = f2 (x1 , x2 ) − (x∗1 − x1 )∂f2 (x1 , x2 )∂f2 (x1 , x2 )+ (x∗2 − x2 )+ ìàëîå∂x1∂x269Ïðîèçâîäèì çàìåíó:xi → xni ; x∗i → xn+1iÎòáðàñûâàÿ ìàëûå, èìååì ñèñòåìó:f1 (xn1 , xn2 ) + (xn+1− xn1 )1n n∂f1 (xn1 , xn2 )n ∂f1 (x1 , x2 )+ (xn+1=0−x)22∂x1∂x2n n∂f2 (xn1 , xn2 )n ∂f2 (x1 , x2 )+ (xn+1−x)=022∂x1∂x2TTçàïèñûâàòü, ââåä¼ì âåêòîðû f¯ = (f1 , f2 ) , x̄ = (x1 , x2 )"#f2 (xn1 , xn2 ) + (xn+1− xn1 )1×òîáû óäîáíîðèöó:J(x) =Çàìåíà,xi → xni ; x∗i → xn+1i∂f1 (x)∂x1∂f2 (x)∂x1∂f1 (x)∂x2∂f2 (x)∂x1 2(3.14)è ìàò-(3.15)(îïÿòü òàêàÿ æå).f (xn ) + J(xn )(xn+1 − xn ) = 0Ïóñòü ó íàñ åñòüJ −1 (xn ).Òîãäà:xn+1 = xn − J −1 (xn )f (xn ) = 0(3.16).Åñëè îáðàùàòü, òî âàæíî, êàêîé îïðåäåëèòåëü, áëèçîê ëè îí ê íóëþ.Ââîäÿò âåêòîðv̄ n+1 = x̄n+1 − x̄nè ïîëó÷àþò:f (xn ) + J(xn )v n = 0;xn+1 = xn + v n+1Äëÿ ïðîèçâîëüíîãî êîëè÷åñòâà ïåðåìåííûõ ñîâåðøåííî àíàëîãè÷íî.f1 (x1 , x2 , ..., xm ) = 0f2 (x1 , x2 , ..., xm ) = 0...........................fm (x1 , x2 , ..., xm ) = 0Ãëàäêîñòü, îïÿòü-òàêè, âñÿ åñòü.ÌàòðèöàJ = (fij ), fij =∂fi∂xj .

Âåêòîðf¯ = (f1 , ..., fm )T , x = (x1 , ..., xm )TÎïÿòü òåì æå îáðàçîì:x̄n+1 = x̄n − J −1 (x̄n )f (x̄n )70(3.17)Ðèñ. 3.3:Çàìå÷àíèå ïðîv̄ n+1àêòóàëüíî.Î÷åâèäíî, ñëó÷àé îäíîé ïåðåìåííîé ÷àñòíûé ñëó÷àé ýòîé ôîðìóëû.Íåñêîëüêî ñëîâ ïðî ìåòîä ñåêóùèõ.Ïðîèçâîäíóþ ñ÷èòàòü î÷åíü òÿæåëî.Ìåòîä Íüþòîíà:f (x∗ ) = 0,xn+1f (xn )=x − 0 nf (x )nÌíîãîøàãîâûå ìåòîäû ñõîäÿòñÿ ëó÷øå, íî èì íàäî ïðîñòðàíñòâî äëÿ ðàçãîíà.f (xn ) − f (xn−1 )f (x ) ≈xn − xn−10Çàìåíÿåì:n+1xn = 1, 2, 3...; x0 , x1nf (xn )(xn − xn−1 )=x −,f (xn ) − f (xn−1 )nãäå-òî çàäàþòñÿ.Äàííûé ìåòîä íàçûâàåòñÿ äâóøàãîâûì. Èëëþñòðàöèÿ äàííîãî ìåòîäà èçîáðàæåíà íà ðèñóíêå 4.2.Ìû çàìåíÿåì ïðîèçâîäíóþ íà ïîëèíîì ïåðâîé ñòåïåíè, ó êîòîðîé âñåãäà îäèííîëü.

Ìîæíî ñòðîèòü ìíîãîøàãîâûé ìåòîä, íî òàì âîçíèêàþò ñëîæíîñòè ñ íóëÿìè.71Ÿ 5. Ñõîäèìîñòü ìåòîäà Íüþòîíà. Îöåíêà ñêîðîñòèñõîäèìîñòèÏî ïðåæíåìó ðàññìàòðèâàåì:f (x) = 0xãäån+1(3.18)f (xn )=x − 0 n ,f (x )n(3.19)n = 0, 1, 2..., x0 ∈ Ua (x∗ ).Òðàêòóåì ìåòîä Íüþòîíà êàê ïðîñòóþ èòåðàöèþ:xn+1 = S(xn ). S(x) = x −f (x)f 0 (x) . Ãëàäêîñòü: òðåòüÿ ïðîèçâîäíàÿ íåïðåðûâíàÿ äîñòàòî÷íîå óñëîâèå.|S 0 (x)| = q < 1, x ∈ Ua (x∗ ) âîò è ñõîäèìîñòü.S 0 (x) = 1 −Ïîíÿòíî, ÷òî(f 0 (x))2 − f (x)f 00 (x)f (x)f 00 (x)=(f 0 (x))2f 0 (x)f 0 (x)S 0 (x∗ ) = 0. Ýòî óñëîâèå ïîêàçûâàåò, ÷òî ïîãðåøíîñòü íà äâóõ ñî-ñåäíèõ èòåðàöèÿõ ñâÿçàíà êâàäðàòè÷íûì îáðàçîì.

 ïðîñòîé: ñâÿçàíû ëèíåéíûìñîîòíîøåíèåì.zn = xn − x∗ ïîãðåøíîñòü íà èòåðàöèèn.Âíîâü Òåéëîð:zn+1 = S(z n + x∗ ) − S(x∗ ) = [S(x∗ ) + S 0 (x∗ )]zn + 0.5S 00 (x̃)zn2 − S(x∗ ) == 0.5S 00 (x̃)zn2 , x̃ = x∗ + θxn , |θ| < 1M : |0.5S 00 (x̃)| ≤ M .M |zn+1 | ≤ (M |zn |)2 .Ïðèäóìàåì êîíñòàíòóÈëèÒîãäà|zn+1 | ≤ M |zn2 |.vn = M |zn |, vn+1 ≤ vn2Ðåêóððåíòíî:nnvn ≤ v02 ; M |zn | ≤ (M |z0 |)2|zn | ≤Îáîçíà÷èìM |z0 | = q .Åñëèq < 1,.1(M |z0 |)2M(3.20)òî åñòü ñõîäèìîñòü.Êàê ýòî ñâÿçàíî ñ âûáîðîì íà÷àëüíîãî ïðèáëèæåíèÿ:|x0 − x∗ | <721;Mq < 1, |z0 | <1M(3.21)|zn | → 0, n → ∞:1n(M |x0 − x∗ |)2M(3.22)0.5|(f (x)f 00 (x)(f 0 (x))2 )0 | ≤ M(3.23)|xn − x∗ | ≤Ïåðåñ÷èòûâàåì :Óòâåðæäåíèå:Ïóñòü∃Mñîãëàñíî 3.23, è ïóñòü â îêðåñòíîñòèUa (x∗ ), a = a(M )íà÷àëüíîåïðèáëèæåíèå âûáèðàåòñÿ ñ óñëîâèåì 3.21.