Н.И. Ионкин - Электронные лекции (2008) (1135232), страница 7
Текст из файла (страница 7)
Íàéäåì íàèëó÷aøåå ñðåäíåâêàäðàòè÷íîå ïðèáëèæåíèå äëÿ f(x). Ðàññìîòðèì ôóíêöèþÏðèìåð:n = 0, φ0 (x) ∈ H :ZbF (C0 ) =(f (x) − C0 φ0 (x))2 dx =aZbZb2f (x)dx − 2C0=af (x)φ0 (x)dx +a2Zb(2.23)φ20 (x)dx =a= ||f (x)|| − 2C0 (f, φ0 ) +C02 (φ0 , φ0 ).Ìèíèìóì ýòîé ôóíêöèè ïî ïåðåìåííîéC0 =C02C0íàõîäèòñÿ â âåðøèíå ïàðàáîëû:(f, φ0 )= C0 .φ0 , φ0φ(x) = C0 φ0 (x) - íàèëó÷øåå ñðåäíåêâàäðàòè÷íîå ïðèáëèæåíèå. ÏóñòüRb1φ0 (x) ≡ 1 ⇒ φ(x) = C0 φ0 (x) = C0 = b−af (x)dx. Ïåðåéäåì òåïåðü ê ïîÒîãäàañòðîåíèþôóíêöèéφ(x) â ïðîèçâîëüíîì ñëó÷àå.
Ðàññìîòðèì ñèñòåìó ëèíåéíî-íåçàâèñèìûõ{φi }n0 (áóäåì íàçûâàòü èõ áàçèñíûìè). Ìèíèìèçèðóåì èíòåãðàë2.7. Íàèëó÷øåå ñðåäíåêâàäðàòè÷íîå ïðèáëèæåíèå ôóíêöèé51(êâàäðàò íîðìû):Zb(f (x) −nXCk φk (x))2 dx = F (C0 , C1 , . . . , Cn ) =k=0aZb2f (x)dx − 2=nXZb= (f, f ) − 2nXf (x)φk (x)dx +Ckk=0anXCk (fk , Ck ) +i=0Ckk=0anXCkk=0nXnXZbCll=0φk (x)φl (x)dx =aCl (φk , φl ).l=0(2.24)Íåîáõîäèìîå óñëîâèå ñóùåñòâîâàíèÿ ìèíèìóìà:δF (C0 , C1 , . . .
, Cn )= 0, k = 0, n.δCkÏîëó÷èì ñèñòåìó óðàâíåíèé:nXCl (φk , φl ) = (f, φk ), k = 0, n(2.25)l=0Ìàòðèöà ýòîé ñèñòåìû G ÿâëÿåòñÿ ìàòðèöåé Ãðàììà:(φ0 , φ0 ) (φ1 , φ0 )...(φn , φ0 )Òàê êàê{φi }n0(φ0 , φ1 )(φ1 , φ1 )...........(φ0 , φn )(φ1 , φn ) ...(φn , φn ).(φn , φ1 ) . . . ëèíåéíî íåçàâèñèìû, òîñòåìû ñóùåñòâóåò è åäèíñòâåííî⇒detG 6= 0 ⇒äëÿ ëþáûõ ôóíêöèé(2.26)ðåøåíèå ýòîé ñè-{φi }n0 ëèíåéíî-íåçàâèñèìûõ ñóùåñòâóåò è åäèíñòâåííî íàèëó÷øåå ñðåäíåêâàäðàòè÷íîå ïðèáëèæåíèå ôóíêöèèÇàìå÷àíèå.f.Åñëè ñèñòåìà îðòîíîðìèðîâàíà:Rbφk (x)φl (x)dx = δkl ⇒ Ck =a(f, φk ) îáîáùåííûå êîýôôèöèåíòû ÔóðüåÇàìå÷àíèå.Åñëè ñèñòåìà ñîñòîèò èç ñëåäóþùèõ ôóíêöèé:1, x, x2 , . .
. , xnèRβρ(x)φk (x)φl (x) = ρ(x) > 0, òî âûáèðàÿ α, β è ραìîæíî ïîëó÷èòü îáîáùåííûå ìíîãî÷ëåíû ßêîáè, ×åáûøåâà, Ëåæàíäðà èçàäàíà âåñîâàÿ ôóíêöèÿ:ò.ä.Ïóñòü{φi }n0 îðòîíîðìèðîâàííàÿ ñèñòåìà. Òîãäà íàèìåíüøåå îòêëîíå-Ãëàâà 2. Èíòåðïîëèðîâàíèå è ïðèáëèæåíèå ôóíêöèé52íèå:Zb(f (x) −nXZb2Ck φk (x)) dx =k=0a−2nXaCk (f, φk ) +k=0Zb⇒f 2 (x)dx−nXCk2 ≥ 0 ⇒(2.27)k=0f 2 (x)dx = ||f ||2 ≥nXCk2 ,k=0a íåðàâåíñòâî Áåññåëÿ. Åñëè æå ñèñòåìà - îðòíîðìèðîâàííûé áàçèñ, òî ìûïîëó÷àåì ðàâåíñòâî Ïàðñåâàëÿ:||f ||2 =nPk=0Åñëè ôóíêöèÿ çàäàíà òàáëè÷íî, ò.å.:ôóíêöèè{φi }N0Ck2 .f (xi ) = fi , i = 0, Nè çàäàíû áàçèñíûåòî åå ñðåäíåêâàäðàòè÷íîå ïðèáëèæåíèå:||f −NXNNXX1Ck φk || = ( (fi −Ck φk (xi ))2 ) 2 ,i=0k=0(f, g) =NXk=0fi gi ,k=0NX1||f ||2 = (fi2 ) 2 ,(2.28)i=0F (C0 , C1 , .
. . , Cn ) = ||f −NXCk φk || =k=0= ||f ||2 − 2NXCk (f, φk ) +k=0 ãäåCkíàõîäÿòñÿ èç ñèñòåìû (2.26).N XNXk=0 l=0Ck Cl (φk , φl ),Ãëàâà 3Ðåøåíèå íåëèíåéíûõóðàâíåíèé è ñèñòåìóðàâíåíèé3.1ÂâåäåíèåÏóñòü çàäàíà ôóíêöèÿóðàâíåíèåf (x) = 0.f (x), x ∈ R, f (x)íåïðåðûâíà, è íåîáõîäèìî ðåøèòüÏðîöåññ ðàçáèâàåòñÿ íà 2 ýòàïà: 1)ëîêàëèçàöèÿ êîðíÿè 2)ïîñòðîåíèå èòåðàöèîííîãî ìåòîäà íàõîæäåíèÿ êîðíÿ.Îïðåäåëåíèå 16. Ua (x∗ ) = {x : |x − x∗ | = a} a-îêðåñòíîñòü êîðíÿ x∗ .Ñïîñîáû ëîêàëèçàöèè êîðíÿ:1. Ðàçîáüåì[a, b]:a ≤ x0 < x1 < . .
. < xn ≤ bÅñëèÅñëèf (xi−1 )f (xi ) < 0, òî íà [xi−1 , xi ] åñòü õîòÿ áû îäèí êîðåíü.f (xi−1 )f (xi ) > 0, òî íà [xi−1 , xi ] ëèáî íåò êîðíåé, ëèáî èõòàì÷åòíîå ÷èñëî.2. Ìåòîä áèñåêöèè(äåëåíèÿ ïîïîëàì).f (x) ∈ C[a, b]; f (a) < 0, f (b) > 0x0 = a+b2 .x∗ ∈ (x0 , b) è ò.ä.ÂîçüìåìÅñëèf (x0 ) > 0,òîx∗ ∈ (a, x0 ); f (x0 ) < 0=> ñëó÷àå ñèñòåìû íåëèíåéíûõ óðàâíåíèéf1 (x1 , . . .
, xm ) = 0...fm (x1 , . . . , xm ) = 0åå ìîæíî ïðåäñòàâèòü â âèäå→− →f (−x ) = 0,(x1 , x2 , . . . , xm )T .53ãäå→−−f = (f1 , f2 , . . . , fm )T , →x =Ãëàâà 3. Ðåøåíèå íåëèíåéíûõ óðàâíåíèé è ñèñòåì óðàâíåíèé543.2Ìåòîä ïðîñòîé èòåðàöèèÈòàê, ìû ðåøàåì óðàâíåíèåf (x) = 0,Ua (x∗ ).è êîðåíü ëîêàëèçîâàí íàãäå(3.1)Çàìåíèì ýòî óðàâíåíèå íà ýêâèâàëåíòíîå:x = S(x) :(3.2)S(x) = x + r(x)f (x),(3.3)r(x) çíàêîïîñòîÿííàÿ{xn }: x0 ∈ Ua (x∗ ),ôóíêöèÿ íàUa (x∗ ).Ïîñòðîèì ïîñëåäîâàòåëü-íîñòüxn+1 = S(xn ), n = 0, 1, .
. .Îïðåäåëåíèå 17. S(x)Ëèïøèöà) ñq = const > 0(3.4) Ëèïøèöíåïðåðûâíà (óäîâëåòâîðÿåò óñëîâèþíà(a, b),åñëè∀x1 , x2 ∈ (a, b)|S(x1 ) − S(x2 )| ≤ q|x1 − x2 |.Óòâåðæäåíèå 7. Åñëè S(x) óäîâëåòâîðÿåò óñëîâèþ Ëèïøèöà ñ 0 < q < 1íà Ua (x∗ ) è |x − x0 | < a, òî ìåòîä ïðîñòîé èòåðàöèè (3.4) äëÿ ðåøåíèÿóðàâíåíèÿ (3.1) ñõîäèòñÿ (ñî ñêîðîñòüþ ãåîìåòðè÷åñêîé ïðîãðåññèè ñ çíàìåíàòåëåì q ).Äîêàçàòåëüñòâî.|x0 − x∗ | < a,|xn+1 − x∗ | = |S(xn ) − S(x∗ )| ≤ q|xn − x∗ | ⇒⇒ |xn − x∗ | ≤ q n a.limn→∞ q n = 0,òàê êàê0 < q < 1.Òàêèì îáðàçîì, ìåòîä ñõîäèòñÿ, ïðè÷åìñî ñêîðîñòüþ ãåîìåòðè÷åñêîé ïðîãðåññèè ñ çíàìåíàòåëåìÇàìå÷àíèå.ÅñëèS(x)äèôôåðåíöèðóåìà íàUa (x∗ ),òîq.q=|S 0 (x)|supx∈Ua (x∗ )Çàìå÷àíèå.
Äîïóñòèì, ÷òî f (x)∃M1 = supx∈Ua (x∗ ) |f 0 (x)|.äèôôåðåíöèðóåìà èf 0 (x) > 0íàUa (x∗ )èÒîãäà çàïèøåì ìåòîä ïðîñòîé èòåðàöèè â íåñêîëüêî èíîé ôîðìå:xn+1 − xn+ f (xn ) = 0, τ > 0τ(xn+1 = S(xn ), S(x) = x − τ f (x)).÷òîáû∃S 0 (x) = 1 − τ f 0 (x) íà Ua (x∗ ). Äëÿ ñõîäèìîñòè ìåòîäà,q = supx∈Ua (x∗ ) |1 − τ f 0 (x)| < 1. Ò.å. ÷òîáû 0 < τ < M213.2.1Ìåòîä Ýéòêåíà (óñêîðåíèå ñõîäèìîñòè)Çíà÷èòÏóñòüxn − x∗ ∼= Aq n ,ãäåAèqíåîáõîäèìî, íåêîòîðûå êîíñòàíòû.
Òîãäà:xn−1 − x∗xn − x∗xn+1 − x∗= Aq n−1= Aq n= Aq n+13.3. Ìåòîä Íüþòîíà è ìåòîä ñåêóùèõ55è(xn+1 − xn )2= A2 q 2n (q − 1)2= Aq n−1 (q − 1)2 .(xn+1 − 2xn + xn−1 )Îòêóäà:(xn+1 − xn )2= Aq n+1 = xn+1 − x∗ .xn+1 − 2xn + xn−1Òî åñòü,x∗ ∼= xn+1 −(xn+1 − xn )2.xn+1 − 2xn + xn−1(3.5)Òàê êàê ïîëó÷àåòñÿ íåòî÷íî, òî â êà÷åñòâå ñëåäóþùåé èòåðàöèè ìû äîëæíûâçÿòüx∗ (ýòî íå ñàì êîðåíü, íî ÷òî-òî áëèçêîå ê íåìó).
Ïîýòîìó ýòîò ñïîñîáïîçâîëÿåò óâåëè÷èòü ñêîðîñòü ñõîäèìîñòè.3.3Ìåòîä Íüþòîíà è ìåòîä ñåêóùèõÏóñòü îïÿòü ìû ðåøàåì óðàâíåíèåf (x) = 0,Ua (x∗ ), è ïóñòü f (x) ∈ C 1 (Ua (x∗ )),ðàçëîæèâ f (x∗ ) ïî Òåéëîðó, ïîëó÷èì:êîðåíü ëîêàëèçîâàí íàíàUa (x∗ ).Òîãäà,ïðè÷åìf 0 (x) 6= 00 = f (x∗ ) = f (x) + f 0 (x)(x∗ − x) + o(x∗ − x) ≈ f (x) + f 0 (x)(x∗ − x).Âìåñòîxïîäñòàâèìxn ,âìåñòîx∗xn+1 .Ïîëó÷èì:0 = f (xn ) + f 0 (xn )(xn+1 − xn ) =⇒ xn+1 = xn −Âçÿâx0 ∈ Ua (x∗ ),f (xn )f 0 (xn )ïîëó÷èì ìåòîä Íüþòîíà:xn+1 = xn −f (xn ), n = 0, 1, 2, . . . , x0 ∈ Ua (x∗ ).f 0 (xn )(3.6)Îäíàêî, ñ÷èòàòü íà êàæäîé èòåðàöèè ïðîèçâîäíóþ íåñêîëüêî çàòðàòíî, àíà íåáîëüøîì èíòåðâàëå îíà ìåíÿåòñÿ, êàê ïðàâèëî, íå ñèëüíî, ïîýòîìóïðîèçâîäíóþ ìîæíî âû÷èñëèòü òîëüêî íà ïåðâîé èòåðàöèè.
Ïîëó÷àåìäèôèöèðîâàííûé ìåòîä Íüþòîíà:xn+1 = xn −f (xn ), n = 0, 1, 2, . . . , x0 ∈ Ua (x∗ ).f 0 (x0 )ìî-(3.7)Ìîäèôèöèðîâàííûé ìåòîä Íüþòîíà ñõîäèòñÿ ìåäëåííåå ìåòîäà Íüþòîíà,íî áûñòðåå ìåòîäà ïðîñòîé èòåðàöèè.Ãëàâà 3. Ðåøåíèå íåëèíåéíûõ óðàâíåíèé è ñèñòåì óðàâíåíèé563.3.1Ìåòîä Íüþòîíà äëÿ ñèñòåìû óðàâíåíèéÐàññìîòðèì ñèñòåìó:(f1 (x1 , x2 ) = 0f2 (x1 , x2 ) = 0Ïóñòü(x∗1 , x∗2 ) åå ðåøåíèå. Ðàçëîæèìf1è.f2(3.8)â îêðåñòíîñòè êîðíÿ:∂f1 (x1 , x2 ) ∗∂f1 (x1 , x2 ) ∗(x1 − x1 ) +(x2 − x2 ) + .
. .∂x1∂x2∂f2 (x1 , x2 ) ∗∂f2 (x1 , x2 ) ∗0 = f2 (x∗1 , x∗2 ) = f2 (x1 , x2 ) +(x1 − x1 ) +(x2 − x2 ) + . . .∂x1∂x20 = f1 (x∗1 , x∗2 ) = f1 (x1 , x2 ) +Çàìåíÿÿxiíàxnièx∗iíàxn+1iïîëó÷àåì:∂f1 (xn1 , xn2 ) n+1(x2 − xn2 ) = 0∂x1∂x2∂f2 (xn1 , xn2 ) n+1∂f2 (xn1 , xn2 ) n+1(x1 − xn1 ) +(x2 − xn2 ) = 0f2 (xn1 , xn2 ) +∂x1∂x2f1 (xn1 , xn2 ) +Îáîçíà÷èì∂f1 (xn1 , xn2 )(xn+1− xn1 ) +1xn = (xn1 , xn2 )T , f = (f1n , f2n )T ,nI(x ) =n∂f1 (xn1 ,x2 )∂xn1 n∂f2 (x1 ,x2 )∂x1n∂f1 (xn1 ,x2 )∂xn2 n∂f2 (x1 ,x2 )∂x2!.(3.9)Òîãäà óðàâíåíèå ìîæíî çàïèñàòü â âèäåf (xn ) + I(xn )(xn+1 − xn ) = 0.Åñëè∀n ∃I −1 (xn ),òîxn+1 = xn − I −1 (xn )f (xn ), n = 0, 1, 2, . .
. , x0Çàìå÷àíèå.vãðåøíîñòüI −1 (xn ) íå= x− xn èÑ÷èòàòün+1(3.10)n+1çàäàíî.(3.11)î÷åíü óäîáíî, ïîýòîìó îáû÷íî ââîäÿò ïîðåøàþò íà êàæäîé èòåðàöèè ñëåäóþùååóðàâíåíèå:I(xn )v n+1 = −f (xn ).Çàìå÷àíèå. ñëó÷àå ñèñòåìû òàêæå ìîæíî ïðèìåíèòü ìîäèôèöèðîâàííûéìåòîä Íüþòîíà:xn+1 = xn − I −1 (x0 )f (xn ).Îäíàêî, â ýòîì ñëó÷àå ñêîðîñòü ñõîäèìîñòè çíà÷èòåëüíî ìåíüøå. ñëó÷àå ñèñòåìû èç m óðàâíåíèé:f1 (x1 , x2 , . . . , xm ) = 0f (x , x , . .
. , x ) = 02 12m...fm (x1 , x2 , . . . , xm ) = 0òàêæå ìîæíî èñïîëüçîâàòü ìåòîä Íüþòîíà, â ýòîì ñëó÷àåi, j = 1, m.Ñèñòåìà â ýòîì ñëó÷àå ïðèíèìàåò òîò æå âèä:f (xn ) + I(xn )(xn+1 − xn ) = 0.I(xn )ij =∂fi (xn )∂xj ,3.4. Ñõîäèìîñòü ìåòîäà Íüþòîíà. Îöåíêà ñêîðîñòè ñõîäèìîñòè3.3.2Ìåòîä ñåêóùèõ (õîðä)Çàïèøåì ìåòîä Íüþòîíà äëÿ óðàâíåíèÿxn+1 = xn −Íî57f 0 (xn ) ≈f (x) = 0:f (xn ).f 0 (xn )f (xn )−f (xn−1 ). Òàêèì îáðàçîì ïîëó÷àåì ìåòîä ñåêóùèõ:xn −xn−1xn+1 = xn −(xn − xn−1 )f (xn ), n = 1, 2, 3, .
. . .f (xn ) − f (xn−1 )(3.12)Ìåòîä ñåêóùèõ ÿâëÿåòñÿ äâóõøàãîâûì(çàâèñèò îò 2õ ïðåäûäóùèõ èòåðàöèé). Äëÿ òîãî, ÷òîáû âîñïîëüçîâàòüñÿ èì, íàì íóæíî óæå 2 íà÷àëüíûõïðèáëèæåíèÿ (x0 èx1 ) èõ ìîæíî ïîëó÷èòü ìåòîäîì ïðîñòîé èòåðàöèèèëè ìåòîäîì Íüþòîíà.3.4Ñõîäèìîñòü ìåòîäà Íüþòîíà. Îöåíêà ñêîðîñòè ñõîäèìîñòèÈòàê, ïðè ðåøåíèèf (x) = 0ñòðîèòñÿ ïîñëåäîâàòåëüíîñòüxn+1 = xn −Ïóñòü äàëååf (x){xn }:f (xn ), x0 ∈ Ua (x∗ ).f 0 (xn )èìååò ñòîëüêî ïðîèçâîäíûõ, ñêîëüêî íåîáõîäèìî äëÿïðîâåäåíèÿ âûêëàäîê.È ïóñòüS(x) = x −S 0 (x) = 1 −f (x)f 0 (x) ,f 0 (x)f 0 (x)−f (x)f 00 (x)(f 0 (x))2=f (x)f 00 (x)(f 0 (x))2S 0 (x∗ ) = {f (x∗ ) = 0} = 0.Åñëè ïîòðåáîâàòü îòx∗ |S 0 (x)| ≤ q < 1.S(x) íóæíîé ãëàäêîñòè, òî â íåêîòîðîé îêðåñòíîñòèÒàêèì îáðàçîì â ýòîé îêðåñòíîñòè ìåòîä ñõîäèòñÿ(õîòÿáû ñî ñêîðîñòüþ ïðîñòîé èòåðàöèè).Ââåäåì ïîãðåøíîñòüzn :zn = xn − x∗ .Òîãäà:zn+1 = xn+1 − x∗ = S(zn + x∗ ) − S(x∗ ) == S(x∗ ) + zn S 0 (x∗ ) + 0.5(zn )2 S 00 (fxn ) − S(x∗ ) == 0.5(zn )2 S 00 (fxn ),ÅñëèS(x)ãäåäîñòàòî÷íî ãëàäêàÿ, òîxfn = x∗ + θzn , |θ| ≤ 1.∃M :1 00|S (fxn )| ≤ M ⇒ zn+1 ≤ M zn2 ⇒ M zn+1 ≤ (M zn )2 ⇒2n⇒ M zn ≤ (M z0 )2 .(3.13)Ãëàâà 3.
Ðåøåíèå íåëèíåéíûõ óðàâíåíèé è ñèñòåì óðàâíåíèé58×òîáû ìåòîä ñõîäèëñÿ, íåîáõîäèìî, ÷òîáû|x0 − x∗ | <Òîãäà|xn − x∗ | ≤|M z0 | = q < 1,òî åñòü ÷òîáû1.M1 2nq .MÒàêèì îáðàçîì, ñïðàâåäëèâî ñëåäóþùååÓòâåðæäåíèå 8. Åñëè ∃M :0 1 f (x)f 00 (x) < M ∀x ∈ Ua (x∗ ),2 (f 0 (x))2(3.14)1,M(3.15)|x0 − x∗ | <òî èòåðàöèîííûé ìåòîä Íüþòîíà ñõîäèòñÿ è äëÿ íåãî ñïðàâåäëèâà îöåíêà:n1(M |x0 − x∗ |)2 .(3.16)|xn − x∗ | ≤MÇàìå÷àíèå.(n ≈ 3; 4).Çàìå÷àíèå.Åñëè ìåòîä Íüþòîíà ñõîäèòñÿ, òî îí ñõîäèòñÿ î÷åíü áûñòðîÍà÷àëüíîå ïðèáëèæåíèå îêàçûâàåò ñèëüíîå âëèÿíèå íà ñõîäè-ìîñòü (åãî íàäî âûáèðàòü â ñîîòâåòñòâèè ñ (3.15)).Çàìå÷àíèå. ñëó÷àå ìîäèôèöèðîâàííîãî ìåòîäà ÍüþòîíàS(xn ) = xn −S 0 (x∗ ) = 1 −f (xn )f 0 (x0 )f 0 (x∗ )f 0 (x0 )6= 0x0 ê x∗ , òåì áëèæåS 0 (x∗ ) ê 0.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
