Численные методы. Ионкин (2012) (v1.1) (косяки есть), страница 7
Описание файла
PDF-файл из архива "Численные методы. Ионкин (2012) (v1.1) (косяки есть)", который расположен в категории "". Всё это находится в предмете "численные методы" из 7 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст 7 страницы из PDF
(x − xn−1 )f (x0 , . . . , xn )52Nn (xi ) = f (xi ), i = 0, . . . , n.Ìû äîëæíû ïîêàçàòü, ÷òî ýòîì ñëó÷àå ïîëèíîì áóäåò èíòåðïîëÿöèîííûì.Nn (xi ) = f (xi ) = f (x0 ) + (xi − x0 )f (x0 , x1 ) + (xi − x0 )(x2 − x1 )f (x0 , x1 , x2 ) + · · ·+(xi − x0 )(xi − x1 ) . . . (xi − xi−1 )f (x0 , . . . , xi ) = f (xi )Äàííîå òîæäåñòâî ñîâïàäàåò ñ ïîëèíîìîì Ëàãðàíæà, òîëüêî îòëè÷àåòñÿ âíåøíèì âèäîì.  íåêîòîðûõ çàäà÷àõ âèä ïîëèíîìà â ôîðìå Ëàãðàíæà íå óäîáåí.Ïîãðåøíîñòü èíòåðïîëÿöèîííîãî ïîëèíîìà Íüþòîíà:ΨNn (x)Ïðèf (n+1) (ξ)=w(x)(n + 1)!Mn+1 = sup | f (x)n+1| ⇒| ΨNn (x) |≤Mn+1(n+1)!| w(x) |.Òàì, ãäå óçëû óâåëè÷èâàþòñÿ (íàïðèìåð ïðè ðàáîòå ñ òàáëèöàìè Áðàäèñà)îáû÷íî èñïîëüçóþò èíòåðïîëÿöèîííûé ïîëèíîì Íüþòîíà. 5.
Èíòåðïîëÿöèðîâàíèå ñ êðàòíûìè óçëàìè. Ïîëèíîìû ÝðìèòàÓçëû îáîçíà÷èì êàê{xi }m0 .Ïóñòü ñóùåñòâóþòf (x0 ), . . . , f (xm )00f (x0 ), . . . , f (xm ) . . . f a0 −1 (x0 ), . . . , f am −1 (xm ),ãäåai ∈ N -êðàòíîñòü óçëàxi :Hn(i) (xk ) = f (i) (xk )Ñóììà êðàòíîñòåé(2.10)a0 + · · · + am = n + 1 ⇒Hn (x) =m aXk −1Xck,i (x)f (i) (xk )(2.11)k=0 i=0Ïîñòðîèì ïîëèíîì Ýðìèòàêðàòíîé.H3â çàäàííûõ òî÷êàx⇒H3 (x0 ) = f (x0 )H3 (x1 ) = f (x1 )H3 (x2 ) = f (x2 )00H3 (x1 ) = f (x1 )53x0 , x1 , x2 .Òî÷êàx1ÿâëÿåòñÿÎáùèé âèä ïîëèíîìà Ýðìèòà òðåòüåé ñòåïåíè:0H3 (x) = c0 (x)f (x0 ) + c1 (x)f (x1 ) + c2 (x)f (x2 ) + b1 (x)f (x1 )Ïðèc0 (x0 ) = 1, c1 (x0 ) = 0, c2 (x0 ) = 0, b1 (x0 ) = 0c0 (x1 ) = 0, c1 (x1 ) = 1, c2 (x1 ) = 0, b1 (x1 ) = 0c0 (x2 ) = 0, c1 (x2 ) = 0, c2 (x2 ) = 1, b1 (x2 ) = 00000c0 (x1 ) = 0, c1 (x1 ) = 1, c2 (12 ) = 0, b1 (x1 ) = 1H3 óäîâëåòâîðÿåò íà÷àëüíûì óñëîâèÿì.Ïóñòü x1 äâóêðàòíûé êîðåíü â c0 , c2 :Òîãäàc0 = k(x − x2 )(x − x1 )2c0 (x0 ) = 1 = k(x0 − x2 )(x0 − x1 )2 ⇒c0 (x) =Àíàëîãè÷íî:(x − x1 )2 (x − x2 )(x0 − x1 )2 (x0 − x2 )(x − x1 )2 (x − x0 )c2 (x) =(x2 − x1 )2 (x2 − x0 )(b1 (x) = k1 (x − x0 )(x − x1 )(x − x2 )b1 (x) = (x − x1 )(k1 (x − x0 )(x − x2 ))00b1 (x) = (k1 (x − x0 )(x − x2 )) + (x − x1 )(k1 (x − x0 )(x − x2 ))0b1 (x1 ) = 1 = k(x1 − x0 )(x1 − x2 )b1 (x) =(x − x0 )(x − x1 )(x − x2 )(x1 − x0 )(x1 − x2 )c1 (x) = (x − x0 )(x − x2 )(ax + b)c1 (x1 ) = 1 = (x1 − x0 )(x1 − x2 )(ax1 + b) ⇒1(ax1 + b) =(x1 − x0 )(x1 − x2 )0c1 (x) = a(x − x0 )(x − x2 ) + (ax + b)(2x − x0 − x2 )0c1 (x) = 0 = a(x1 − x0 )(x1 − x2 ) + (ax1 + b)(ax1 − x0 − x2 )Ïîäñòàâëÿÿ(ax1 + b):a=−2x1 − x0 − x2(x1 − x0 )2 (x1 − x2 )254(2.12)b=c1 (x) =1(2x1 − x0 − x2 )x1(1 +)(x1 − x0 )(x1 − x2 )(x1 − x0 )(x1 − x2 )(x1 − x0 )(x − x2 )(2x1 − x0 − x2 )(x − x1 )(1 −)(x1 − x0 )(x1 − x2 )(x1 − x0 )(x1 − x2 )Òàêèì îáðàçîì âñå êîýôôèöèåíòû îäíîçíà÷íî íàõîäÿòñÿ â ÿâíîì âèäå.Îöåíêà ïîãðåøíîñòèH3 (x), x0 , x1 , x2 òàê æå, êàê äåëàëè äëÿ Ëàãðàíæà.g(s) = f (s) − H3 (s) − Kω(s)ω(s) = (x − x0 )(x − x1 )2 (x − x2 )x0 ≤ s ≤ x2 , x ∈ [x0 , x2 ],ÊîíñòàíòóKáóäåì âûáèðàòü:g(x) = 0 = f (x) − H3 (x) − Kω(x)K=f (x) − H3 (x)ω(x)Äàëüíåéøèé àëãîðèòì ïîëíîñòüþ ñîâïàäàåò, íî õèòðîñòü âîêðóã òåîðåìû Ðîëëÿ.g(x).
Îíà èìååò ïî êðàéíåé ìåðå 4 íóëÿ íà [x0 , x2 ]: 3 âî ìíîæèòåëÿõ è îäíî g(x) = 0.000Ãëàäêîñòè õâàòàåò. Ïðèìåíèì òåîðåìó Ðîëëÿ ó g íå ìåíåå 3 íóëåé, ó g 000íå ìåíåå 2, ó g íå ìåíåå 1, íî ýòîãî ìàëî, ω(s) ïîëèíîì ÷åòâ¼ðòîé ñòåïåíè.0Íî èç-çà êðàòíîñòè óçëà x1 : åñòü åù¼ g (x1 ) = 0, òàê ÷òî ó ïðîèçâîäíîé 4 íóëÿ.(4)Ó ÷åòâ¼ðòîé íîëü åñòü: ∃ξ , g(ξ) = 0.Ðàññìîòðèì×åòûðåæäû äèôôåðåíöèðóåì:g (4) (s) = f (4) (s) − 4!KÎáîçíà÷èìM4 = sup |f (4) (x)|x0 ≤x≤x2Òîãäà|f (x) − H3 (x)| = |ΨH3 (x)| ≤M4M4|ω(x)| =|(x − x0 )(x − x1 )2 (x − x2 )|4!4!Åñëè ÷òî-òî îáðàùàåòñÿ â íîëü, ïðèáëèæåíèå áóäåò òî÷íûìÀíàëîãè÷íî:f (n+1) (ξ)ΨHn (x) =(x − x0 )a0 (x − x1 )a1 ...(x − xm )am(n + 1)!55Mn+1 = sup |f (n+1) (x)|x|ΨHn (x)| ≤Mn+1|ω(x)|(n + 1)!Ïðèä¼òñÿ ñ÷èòàòü îãðîìíîå êîëè÷åñòâî ýòèõ èíòåãðàëîâ, à àíàëèòè÷åñêè ýòîñëîæíî! À ÷èñëåííî ëó÷øå áû ïîòî÷íåå çäåñü ïîìîãóò ôîðìóëû Ãàóññà.Çàäà÷à 1:Íåîáõîäèìî èç ïîëèíîìà Ëàãðàíæà ïðåäåëüíûì ïåðåõîäîì ïîëó÷èòü ïîëèíîìÝðìèòà.x0 , x1 , x2óçëû,x3ôèêòèâíûé,x3 → x1 .Äîêàçàòü, ÷òîÐåøåíèå:lim L3 (x) = H3 (x).x3 →x1Ïî çàäàííûì òðåì òî÷êàì ìîæíî îäíîçíà÷íî ïîñòðîèòü ïîëèíîìL3 (x) =L3 (x):(x − x0 )(x − x1 )(x − x2 )f (x0 ) + ...(x0 − x1 )(x0 − x2 )(x0 − x3 )Îñóùåñòâèì ïðåäåëüíûé ïåðåõîä îòx1êx3 :(x − x1 )2 (x − x2 )2L3 (x) →f (x0 ) + ...
= H3(x0 − x1 )2 (x0 − x2 )2 6. Èñïîëüçîâàíèå Ïîëèíîìà Ýðìèòà äëÿ îöåíêèïîãðåøíîñòè êâàäðàòóðíîé ôîðìóëû ÑèìïñîíàÏðåäâàðèòåëüíûå çàìå÷àíèÿ:Çàáåãàÿ âïåð¼ä: ïîëó÷èòñÿ ïÿòûé ïîðÿäîê äëÿ ÷àñòè÷íîãî îòðåçêà è ÷åòâ¼ðòûé- äëÿ âñåãî îòðåçêà. À òðàïåöèÿ - òîëüêî âòîðîé ïîðÿäîê.ÎïðåäåëåííûéèíòåãðàëRbf (x) dxâû÷èñëÿåìïðèáëèæ¼ííîêâàäðàòóðíîéaôîðìóëîé Ñèìïñîíà. Äëÿ ýòîãî ðàçáèâàåì îòðåçîê íàa ≤ x0 < x1 < ... < xN ≤ bòàê, ÷òîn÷àñòè÷íûõ îòðåçêîâxi − xi−1 = h.Zxif (x) dx =h(fi−1 + 4fi− 12 + fi ),6xi−1fi = f (xi ),fi−1/2 = f (xi−1 + 0.5h) ôîðìóëà Ñèìïñîíà íà ÷àñòè÷íîì îòðåçêå.56(2.13)Çàìåíÿåì ïîäûíòåãðàëüíîåf (x)ïîëèíîìîì, â íàøåì ñëó÷àå ïàðàáîëîé.
Ïî-ãðåøíîñòü èíòåãðàë îò ïîãðåøíîñòè! Èç ýòèõ ñîîáðàæåíèé âûõîäèò 4-é ïîðÿäîê,à ìû ïîëó÷èì 5-é.Ôîðìóëà òî÷íà äëÿ ïîëèíîìîâ äî òðåòüåé ñòåïåíè:f (x) = a0 + a1 x + a2 x2 + a3 x3 äîx2Îñòà¼òñÿôîðìóëà Ëàãðàíæà òî÷íà, ôîðìóëà Ñèìïñîíà òî÷íà ïî ïîñòðîåíèþ.x3 .Õîòèì ïîêàçàòü:Zxix4i − x4i−1=x dx =43xi−1=(x2i − x2i−1 )(x2i + x2i−1 ) (xi − xi−1 )(xi + xi−1 )(x2i + x2i−1 )==44h= (xi + xi−1 )(x2i + x2i−1 )4Òåïåðü ñâîäèì ôîðìóëó Ñèìïñîíà ê ýòîìó.Çàïèñûâàåì:h 3(xi−1 + 4x3i−1/2 + x3i ) =6hxi + xi−1 3((xi−1 + xi+1 )(x2i−1 − xi xi−1 + x2i ) + 4() )=62(xi + xi+1 )(x2i + 2xi xi−1 + x2i−1 )h= ((xi−1 + xi )(x2i−1 + xi xi−1 + x2i ) +)=622xi−1 − 2xi xi−1 + 2x2i + x2i + 2xi xi−1 + x2i−1h= (xi + xi−1 )()=62h= (xi + xi−1 )3(x2i−1 + x2i ) =12Zxih= (xi + xi−1 )(x2i + x2i−1 ) =x3 dx4xi−1Ýòîò ôàêò ïðèãîäèòñÿ äëÿ ïîëó÷åíèÿ òî÷íîé îöåíêè.
Îíà áóäåò òî÷íà äëÿH3 (x),òàê êàê ýòî ïîëèíîì òðåòüåé ñòåïåíè.ÐàññìîòðèìH3 (x)â óçëàõxi−1 , xi−1/2 , xi :H3 (xi−1 ) = f (xi−1 ); H3 (xi−1/2 ) = fi−1/2 ;0H3 (xi ) = fi ; H30 (xi−1/2 ) = fi−1/257Ìû çíàåì î ñóùåñòâîâàíèè è åäèíñòâåííîñòè, íî â ÿâíîì âèäå îí íàì íå íóæåí.Íóæíà òîëüêî ïîãðåøíîñòü è ôàêò òîãî, ÷òî îí òðåòüåé ñòåïåíè.ΨH3 (x)f (4) (ξ)=(x − xi−1 )(x − xi−1/2 )2 (x − xi )4!f (x) = H3 (x) + ΨH3 (x)Ïîäñòàâëÿåì:ZZxi f (x) dx =xi−1Zxi H3 (x) dx +xi−1xi ΨH3 (x) dx =xi−1h= (H3 (xi−1 ) + 4H3 (xi−1/2 ) + H3 (xi )) +6Zxi ΨH3 (x) dx =xi−1=h(fi−1 + 4fi−1/2 + fi ) + Ψi (f )6Òîãäà ïîãðåøíîñòü:ZxiΨi (f ) =hΨH3 (x) dx − (fi−1 + 4fi−1/2 + fi )6xi−1M4 = sup |f (4) (x)|xÏåðåïèøåì ôóíêöèþ, ÷òîáû áûëà íåîòðèöàòåëüíàÿ, óáðàâ ìîäóëü:M4|Ψi (f )| ≤4!Zxi(x − xi−1 )(x − xi−1/2 )2 (xi − x) dxxi−1Çàäà÷à 1:RxiÄîêàçàòü(x − xi−1 )(x − xi−1/2 )2 (xi − x) dx =xi−1h5120 .Ðåøåíèå:Ïóñòüx = xi−1 + th, 0 ≤ x ≤ 1 ⇒dx = hdt, x − xi−1 = th1xi − x = h(1 − t), (x − xi− 21 )2 = (t − )2 ⇒2xZi(x − xi−1 )(x − xi− 21 )2 (xi − x)dx =xi−1585Z1=h1t(1 − t)(t − )2 dt = h52Z1th55 24(2t − t − t = )dt =44120300Îöåíèì ïîãðåøíîñòü íà âñåì îòðåçêå[a, b].Íàäî îöåíèâàòü ïîëèíîìîì Ýðìè-òà, à íå Ëàãðàíæà.
Âòîðîé äàë áû ãðóáóþ îöåíêó. Íî íà âñ¼ì îòðåçêå òîëüêî4:Zbf (x) dx −Ψh (f ) =NXΨi (f )i=1ah b−a,|Ψh (f )| ≤ ( )42 180hN = b − a. 7. Íàèëó÷øåå ñðåäíåêâàäðàòè÷íîå ïðèáëèæåíèåôóíêöèéH = L2 [a, b](ãèëüáåðòîâî ïðîñòðàíñòâî):∀f ∈ L2 [a, b] :Rbf 2 (x) dx < ∞aÂâåäåì íîðìó:Zb∀f, g ∈ L2 : (f, g) =f (x)g(x) dx; ||f ||L2vu buZu= t f 2 (x) dxaa ýòîì ïðîñòðàíñòâå è ñòðîèòñÿ íàèëó÷øåå ñðåäíåêâàäðàòè÷íîå ïðèáëèæåíèå.Òåïåðü ñòàâèì çàäà÷ó:φ0 (x), φ1 (x), ..., φn (x) ∈ L2Rb∀i : φ2i (x) dx < ∞Ïóñòüóñëîâèþ- çàäàííûån + 1 ôóíêöèè, óäîâëåòâîðÿþùèåaÏóñòü òàêæå âñå ôóíêöèè ëèíåéíî íåçàâèñèìû.Îáîáù¼ííûì ìíîãî÷ëåíîì íàçîâåì ìíîãî÷ëåí, èìåþùèé âèä:φ(x) = c0 φ0 (x) + ... + cn φn (x) =nXk=0ãäåck , k = 0, 1, ..., n- âåùåñòâåííûå ÷èñëà.59ck φk (x)(2.14)Íåîáõîäèìî ñðåäè âñåõ îáîáù¼ííûõ ìíîãî÷ëåíîâ âèäà 2.14 íàéòè òàêîénPck φk (x),φ(x) =êîòîðûé ìèíèìèçèðóåò íîðìók=0||f − φ||L2 = min ||f − φ||L2φ(x)φè åñòü íàèëó÷øåå ñðåäíåêâàäðàòè÷íîå ïðèáëèæåíèåfïî ñèñòåìå{φi (x)}n0 .Ìû äîêàæåì, ÷òî îíî âñåãäà ñóùåñòâóåò è åäèíñòâåííî.×òîáû ïîíÿòü, ðàññìîòðèì ïðèìåð.
Ïóñòün = 0, φ0 (x) ∈ L2 .Òîãäàφ(x) =c0 φ0 (x)ZbF (c0 ) =(f (x) − c0 φ0 (x))2 dx −a−2c0f (x)φ0 (x) dx + c20aòàêîé ÷òî:Zbφ20 (x) dxa êâàäðàòè÷íàÿ ôóíêöèÿ îòíîñèòåëüíîc0 ,f 2 (x) dx−aZbäîñòèãàåòñÿ âZbx0 .Ïàðàáîëà ââåðõ, ïîýòîìó åå ìèíèìóì0F (c0 ) = 0.Ñëåäîâàòåëüíî:ZbZbf (x)φ0 (x) dx = 2c02c0aaRbc0 =φ20 (x) dx ⇒f (x)φ0 (x) dxaRb=φ20 (x) dx(f, φ0 )(φ0 , φ0 )aφ(x) = c̄0 φ0 (x).φ0 (x) = 1:ÒîãäàÅñëèÎíà ñóùåñòâóåò è åäèíñòâåííà.Rbc0 =f (x) dxab−aRbφ(x) = c0 × 1 = ñðåäíååçíà÷åíèå èíòåãðàëà=f (x) dxab−aÏðîñìîòðåëè âåñü ìåõàíèçì.
Äàëüøå ïîíèìàåì, ÷òî â ñëó÷àå áîëüøåãî êîëè÷åñòâà ïåðåìåííûõ ïðîöåññ áóäåò àíàëîãè÷åí, ïîðîäèòñÿ ñèñòåìà äëÿ íàõîæäåíèÿ60ci :{φi (x)}n0Zbφ2i (x) dx < ∞,aòî åñòüφi (x) ∈ L2 [a, b].ZbZb2(f (x) − φ(x)) dx =F (c0 , c1 , ..., cn ) =a(f (x) −nXck φk (x))2 dxk=0a ìèíèìèçèðóåì ýòîò èíòåãðàë.∂F∂ckÌèíèìóì äîñòèãàåòñÿ, ãäåZbF (c0 , c1 , ..., cn ) == 0, k = 0, ..., nf 2 (x) dx − 2+ckk=0= (f, f ) − 2Zbckk=0anXnXnXl=0nXf (x)φk (x) dx+aZbφk (x)φl (x) dx =clack (f, φk ) +k=0nXckk=0nXcl (φk , φl )l=0F (c0 , c1 , ...., cn ) =Zb=f 2 (x) dx − 2anXk=0Zbckf (x)φk (x) dx +ckk=0a= (f, f ) − 2nXnXck (f, φk ) +k=0nXk=0cknXZbcll=0nXφk (x)φl (x) dx =acl (φk , φl )l=0Ðàññìîòðèì òåïåðü ñèñòåìó:δF (c0 , ...., cn )= 0,δcknXcl (φk , φl ) = (f, φk ),l=0Ïðèk = 0:61k = 0, 1, ...., nk = 0, 1, ...., nc0 (φ0 , φ0 ) + c1 (φ0 , φ1 ) + ....
+ cn (φ0 , φn ) = (f, φ0 ) c (φ , φ ) + c (φ , φ ) + .... + c (φ , φ ) = (f, φ )0 101 11n 1n1........c0 (φn , φ0 ) + c1 (φn , φ1 ) + .... + cn (φn , φn ) = (f, φn )(2.15)c̄i = (fi , φi )(2.16)Âûïèøåì ìàòðèöó ñèñòåìû:(φ0 , φ0 ) (φ0 , φ1 ) (φ1 , φ0 ) (φ1 , φ1 ) ........(φn , φ0 ) (φn , φ1 ).... (φ0 , φn ).... (φ1 , φn ) = G(φ0 , ...., φn );........ .... (φn , φn )|G| > 0Ïîëó÷èëè ìàòðèöó Ãðàìà. Åå ãëàâíîå ñâîéñòâî - åñëè ñèñòåìà ïîñòðîåíà íàìàòðèöå Ãðàìà, òî ñèñòåìà íå âûðîæäåíà. Òàêèì îáðàçîì, ìû äîêàçàëè, ÷òî ïðèìåíèì êðèòåðèé îïðåäåëåííîñòè ñèñòåìû (ò.ê. ìàòðèöà âûðîæäåííàÿ).c̄0 , c̄1 , ...., c̄n .nPÈ òîãäà φ̄(x) =c̄i φi (x) - áóäåò íàèëó÷øèì ñðåäíåêâàäðàòè÷íûì ïðèáëèæåÈ ìû íàõîäèìi=0íèåì.Òàêèì îáðàçîì ñðåäíåêâàäðàòè÷íîå ïðèáëèæåíèå ñóùåñòâóåò è åäèíñòâåííî.÷òä.Åñëè ñèñòåìà{φi (x)}n0- îðòîíîðìèðîâàííàÿ, òî ìàòðèöà Ãðàììà - åäèíè÷íàÿ.È òîãäà âû÷èñëåíèÿ áóäóò îñóùåñòâëÿòüñÿ ïî ôîðìóëàì 2.16 è êîýôôèöèåíòûáóäóò íàçûâàòüñÿ êîýôôèöèåíòàìè Ôóðüå - îíè íàõîäÿòñÿ ãîðàçäî ïðîùå.Ïî âîçìîæíîñòè äëÿ ËÍÇ ñèñòåì ïðîâîäÿò îðòîãîíàëèçàöèþ è îðòîíîðìèðîâàíèå.