Лекции (1163663), страница 4

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 4)

. . < xn = b; f (x) : f (xi ) = fi - èçâåñòíû.Îïðåäåëåíèå. S(f, x) : - êóáè÷åñêèé ñïëàéí, åñëè1. S, S 0 , S 00 - íåïðåðûâíû íà [a, b];2. S(f, xi ) = fi ;3. íà [xi , xi+1 ] S - ìíîãî÷ëåí, degS = 3.[x1 , x2 ], ..., [xn−1 , xn ] - n − 1 îòðåçêîâ(4n − 4) - íåèçâåñòíûõ (êîýôôèöèåíòîâ).Áåðåì [xi , xi+1 ] : S = si (x) : si (xi ) = fi , si (xi+1 ) = fi+1 - âñåãî 2n − 2 óñëîâèé(èñïîëüçîâàëè 2. è S ∈ C[a, b] èç 1.)i = 1, n − 2 s0i (xi+1 ) = s0i+1 (xi )2n − 4 óñëîâèéi = 1, n − 2s00i (xi+1 ) = s00i+1 (xi )⇒ âñåãî 4n − 6 óñëîâèé.Íåäîñòàþùèå óñëîâèÿ ìîãóò áûòü âûáðàíû ðàçëè÷íûìè ñïîñîáàìè:40 . s01 (x1 ) = f 0 (x1 ), s0n−1 (xn ) = f 0 (xn ).

-  ýòîì ñëó÷àå ñïëàéí íàçûâàåòñÿ ïðàâèëüíûì.(Ìèíóñ: ìîæåì íå çíàòü f 0 (.), åå ìîæåò íå ∃òü).400 . s001 (x1 ) = s00n−1 (xn ) = 0. -  ýòîì ñëó÷àå ñïëàéí íàçûâàåòñÿ íàòóðàëüíûì.27Ñòðîèì íàòóðàëüíûé ñïëàéí. Ðàññìàòðèâàåòñÿ îòðåçîê [xi , xi+1 ]si (x) = f (xi ) + s0i (xi )(x − xi ) + s00i (xi )Îáîçíà÷åíèÿhi = xi+1 − xi ,zi = s00i (xi ),zn = sn−1 (xn ).(x − xi )2(x − xi )3+ s000(x)ii26(0)i = 1, n − 1i = 1, n − 1Áóäåì âûðàæàòü âñå êîýôôèöèåíòû ÷åðåç zi è hi .1s0i (x) = s0i (xi ) + s00i (xi )(x − xi ) + (x − xi )22(1)s00i (x) = s00i (xi ) + s000i (xi )(x − xi )(2)x := xi ⇒ s00i (xi+1 ) = s00i (xi ) + s000i (xi ) · hi| {z } | {z }zi+1zi(íåïðåðûâíîñòü âòîðîé ïðîèçâîäíîé)si (xi ) =zi+1 − zihiÎñòàëîñü s0i (xi )!sn−1 (xn−1 ) =zn − zn−1hn−1â (0) x := xi+1 ⇒fi+1 = fi +s0i (xi )hi.zi+ h2i +2µzi+1 − zi6hi¶h3ifi+1 − fi zi+1 hi zi hi−−hi63òåïåðü íàäî ïîëó÷èòü ñèñòåìó äëÿ zis0i (xi ) =s0i (xi ) + zi hi +(3)zi+1 − zi 2hi = s0i+1 (xi+1 )2hi(4)ïîäñòàâèì (3) â (4), i çàìåíÿåì íà i + 1µhi zi + 2(hi + hi+1 )zi+1 + hi+1 zi+2 = 6fi+2 − fi+1 fi+1 − fi−hi+1hi¶i = 1, n − 2(5)Íàòóðàëüíûé ñïëàéí:z1 = zn = 028(6)⇒ ñèñòåìà ñ òðåõäèàãîíàëüíîé ìàòðèöåé2(h1 + h2 )h20h22(h2 + h3 )h30h32(h3 + h4 )......···...

0... 0... 0... ···Äëÿ ðåøåíèÿ çàäà÷è èñïîëüçóåòñÿ ìåòîä ïðîãîíêè, òðåáóþùèé 8n + O(1) îïåðàöèé.(! Íàðèñîâàí âèä ñèñòåìû äëÿ ïðàâèëüíîãî ! ñïëàéíà)Òåîðåìà 3.(îá îöåíêå ïîãðåøíîñòè) (á/ä)Ïóñòü f ∈ C 4 [a, b]. Òîãäà äëÿ ïðàâèëüíîãî ñïëàéíà:kS − f kC = O(h4 ), ãäå h = max hi ;iäëÿ íàòóðàëüíîãî ñïëàéíà:kS − f kC = O(h2 ), ãäå h = max hi .iÑïëàéí ìîæíî äèôôåðåíöèðîâàòü 3 ðàçà (âíå òî÷åê xi )max |S (k) (x) − f (k) (x)| ≤ Bk · h4−k , k = 0, 1, 2, 3.[a,b]7 Ëåêöèÿ 7.Ìåòîä íàèìåíüøèõ êâàäðàòîâÏî çàäàííîìó íàáîðó òî÷åê îòðåçêà è çíà÷åíèé ôóíêöèè â ýòèõ òî÷êàõ(ti , yi ), ., i = 1, ..., mñòðîèì ôóíêöèþ y(t), îïðåäåëåííóþ âî âñåõ òî÷êàõ.Áåðåì áàçèñ ϕ1 (t), ..., ϕn (t). Ïðèáëèæåííîå çíà÷åíèå ôóíêöèè èùåì â âèäåy(t) =nXCj ϕj (t).j=1Íàèáîëåå ïîïóëÿðíûå íàáîðû áàçèñíûõ ôóíêöèéϕj (t) = tj−1 , ϕj (t) = sin jt, ϕj (t) = eλj t .Ðàññìàòðèâàåòñÿ ñëó÷àé m > n.

Ñîñòàâèì âåêòîð (íåâÿçîê)~r : ri =nXCj ϕj (ti ) − yij=129è áóäåì âûáèðàòü êîýôôèöèåíòû èç óñëîâèÿ ìèíèìóìà íîðìû!2  12Ã nmX Xk~rk2 = Cj ϕj (ti ) − yi  .i=1j=1Ìèíèìóì äîñòèãàåòñÿ òàì, ãäå∂ ¡ 2¢k~rk2 = 0, k = 1, ..., n.∂CkÄèôôåðåíöèðóåìn∂ X(Cj ϕj (ti ) − yi )2 = ...

= 0∂Ck j=1îïå÷àòêàè ïîëó÷àåì ñèñòåìó ëèíåéíûõ óðàâíåíèéà m!nmXXXϕj (ti )ϕk (ti ) Cj =yi ϕk (ti )j=1èëèi=1~ = ~qPCi=1Pkj =qk =mPϕj (ti )ϕk (ti )i=1mPyi ϕk (ti ).i=1Ïðèìåð n = 2. Èùåì y(t) = C1 +C2 t, áàçèñíûå ôóíêöèè - ìíîãî÷ëåíû ϕj (t) = tj−1mPmP = Pm?ÃÃ?ÃÃ?ÃÃ?ÃÃÃÃ?i=1mPtit2ii=1i=1mPyi~q =  i=1mPti yi-t1 t2 t2 . . .

tmtii=1P = ΦT Φϕ1 (t1 ) ϕ1 (t2 )Φ= ···ϕ1 (tm )......···...ϕn (t1 )ϕn (t2 ) ···ϕn (tm ) m×ny1~ = ~y ( ñëîâ íåò )~q = ΦT  ...  ΦCymTΦ = U ΣVñèíãóëÿðíîå ðàçëîæåíèå30Ìíîãî÷ëåíû íàèëó÷øåãî ðàâíîìåðíîãî ïðèáëèæåíèÿÇàäàíà f (x) íà îòðåçêå [a, b] - îãðàíè÷åííàÿ ôóíêöèÿ (èìåþùàÿ êîíå÷íóþ íîðìó)kf kC = sup |f (x)|.x∈[a,b]Ðàññìàòðèâàåòñÿ ìíîæåñòâî ìíîãî÷ëåíîâ ñòåïåíè ≤ nQn (x) = an xn + ... + a0Òðåáóåòñÿ íàéòè Q0n (x) : ∀ Qn (x) kf − Q0n kC ≤ kF − QkC .

Òàêîé ìíîãî÷ëåí íàçûâàåòñÿÌÍÐÏ.Òåîðåìà 1. Åñëè f îãðàíè÷åíà, òî ÌÍÐÏ ñóùåñòâóåò (áåç äîêàçàòåëüñòâà).Îáîçíà÷èìEn (f ) = kf − Q0n kC .defÒåîðåìà ×åáûøåâà. Qn (x) - ÌÍÐÏ ⇔ ∃ x0 < ... < xn+1 ∈ [a, b] : ÷òîf (xi ) − Qn (xi ) = (−1)i αkf − Qn kC , i = 0, ..., n + 1,α = 1 èëè −1 äëÿ âñåõ òî÷åê.Îïðåäåëåíèå. {xi } - òî÷êè àëüòåðíàöèè.Íåîáõîäèìîñòü. - áåç äîêàçàòåëüñòâà. Äîñòàòî÷íîñòü.sign[(f (xi ) − Qn (xi ))(−1)i ] = const.En (f ) ≥mini=0,...,n+1|f (xi ) − Qx (xi )| = β.Åñëè β = 0 - î÷åâèäíî.β > 0: Ïóñòü kQ0n − f k = En (f ) < βsign(Qn (xi ) − Q0n (xi )) = sign((Qn (xi ) − f (xi )) − (Q0n (xi ) − f (xi )) = sign(Qn (xi ) − f (xi )){z}|ìåíÿåò çíàê n+2 ðàçà ⇒ ó ìíîãî÷ëåíà Qn (x)−Q0n (x) èìååòñÿ n+1 êîðåíü - ïðîòèâîðå÷èå.β = kf − Qn kC .kf − Q0n kC ≤ f − Qn kC ⇒ kf − Q0n kC = kf − Qn kC .Åäèíñòâåííîñòü ÌÍÐÏ.Ïðåäïîëîæèì, ∃ Q1n , Q2n : , Q1n (x) 6= Q2n (x) :kf − Q1n kC = kf − Q2n kC = En (f ),1+ Q2n1kf −≤ kf − Q1n kC + kf − Q2n kC = En (f )2 } 22| {zÌÍÐϯ 1¯¯ Qn (xi ) + Q2n (xi )¯¯¯ = En (f )−f(x)i¯¯221|(Qn (xi ) − f (xi )) + (Qn (xi ) − f (xi ))| = 2En (f )Q1n (xi ) − f (xi ) = Q2n (xi ) − f (xi ), i = 0, ..., n + 1⇒ Q1n (xi ) = Q2n (xi ) â n + 2 òî÷êàõ⇒ Q1n ≡ Q2n .Q1n31(ãäå-òî èñï.

íåïðåðûâíîñòü).Äèñêðåòíîå ïðåîáðàçîâàíèå Ôóðüåf (x) - ïåðèîäè÷åñêàÿ ñ ïåðèîäîì 1.+∞Xf (x) =ak exp(2πikx), i2 = −1,X|ak | < ∞.k=−∞Âîçüìåì ôèêñèðîâàííîå N > 0 è ðàññìîòðèì ýòîò ðÿä â òî÷êàõ ñåòêè xl =Z, f (xl ) = fl .l,l ∈Nk2 − k1 = kN : k2 xl − k1 xl = kN xl = kl ⇒ exp(2πik1 xl ) = exp(2πik2 xl )+∞NP−1Pf (xl ) =ak exp(2πikx) =Ak exp(2πikx)k=−∞+∞PAk =fl =NP−1k=0ak+jNk=−∞l) − îáð. ïðåîáð.

ÔóðüåNl = 0, ..., N − 1.Ak exp(2πikk=0Ââåäåì ñêàëÿðíîå ïðîèçâåäåíèå(f, g) =N −11 Xfk ḡk .N k=0gk : gk (xl ) = exp(2πikxl ) - îðòîíîðìèðîâàííàÿ ñèñòåìà.−1k−j1 NPexp(2πil)N l=0Nk = j : (gk , gj ) = 1k 6= j : (gk , gj ) = 0 äëÿ ñàìîñòîÿòåëüíîé ïðîâåðêè(gk , gj ) =N −11 XlAj = (f, gj ) =fl exp(−2πij ) − ïðÿìîå ïðåîáð. ÔóðüåN l=0N(f0 , f1 , ..., fN −1 ) ⇔ (A0 , A1 , ..., AN −1 ).Äëÿ îñóùåñòâëåíèÿ ïðåîáðàçîâàíèé òðåáóåòñÿ O(N 2 ) àðèôìåòè÷åñêèõ îïåðàöèé.32Åñëè N = p1 p2 ñîñòàâíîå ÷èñëî p1 , p2 6= 1 , òî êîëè÷åñòâî àðèôìåòè÷åñêèõ îïåðàöèéìîæíî óìåíüøèòü.k = k1 + k2 p1 ; j = j2 + p2 j1 ;µ¶−1k1 NPfj exp −2πiAk = A(k1 , k2 ) ==N j=0N¶µ1 −1 pP2 −11 pP(k1 + p1 k2 )(j2 + p2 j1 )°==fj +p j exp −2πiN j1 =0 j2 =0 2 2 1p1 p2k1 j2 k1 p/2 j1 p/1 k2 j2 p/1 p/2 k2 j1k1 j11+++ k2 j2+= k2 j1 +p1 p2p1 p/2p/1 p2µp/1 ¶p/2p1p1 p2p−12P1kj2°=A(1) (k1 , k2 ) exp −2π,p2 j2 =1Nµ¶1 −11 pPk1 j1(1)ãäå A (k1 , k2 ) =exp −2π.(åñòü îïå÷àòêè)p1 j1 =1p1Äëÿ âû÷èñëåíèÿA(1) (k1 , k2 ) òðåáóåòñÿ O(p21 p2 ) äåéñòâèé.

Äëÿ A(k1 , k2 ) − O(p1 p22 ). Åñëè√3p1 , p2 ∼ N ïîëó÷èì îáùåå êîëè÷åñòâî O(N 2 ).Åñëè N = 2m ïîëó÷èòñÿ êîëè÷åñòâî àðèôìåòè÷åñêèõ îïåðàöèé O(N log2 N ).8 Ëåêöèÿ 8.×èñëåííîå äèôôåðåíöèðîâàíèå.Äàíî x0 è íàáîð x1 , ..., xn , {f (xi )}|i=1,...,n .Òðåáóåòñÿ ïîñòðîèòü ôîðìóëó äëÿ âû÷èñëåíèÿ ïðèáëèæåííîãî çíà÷åíèÿ f (k) (x0 ).Êîëè÷åñòâî xi è èõ ðàñïîëîæåíèå îòíîñèòåëüíî x0 íàçûâàåòñÿ øàáëîí.Ñòàíäàðòíûå ïîäõîäû ê ðåøåíèþ çàäà÷è:(k)1.

f (k) (x0 ) ≈ Ln (x0 ) - äèôôåðåíöèðîâàíèå èíòåðïîëÿöèîííîãî ìíîãî÷ëåíà;(k)2. f (k) (x0 ) ≈ Sn (x0 ) - äèôôåðåíöèðîâàíèå ñïëàéíà (íå ðàññìàòðèâàåòñÿ);3. ìåòîä íåîïðåäåëåííûõ êîýôôèöèåíòîâf(k)(x0 ) ≈nXCi f (xi ).i=1Êîýôôèöèåíòû ïîäáèðàþòñÿ òàê, ÷òîáû ôîðìóëà áûëà òî÷íà äëÿ ìíîãî÷ëåíîâíàèáîëåå âûñîêîé ñòåïåíè. ñëó÷àå ïåðâîãî ïîäõîäà äîëæíî áûòü k ≤ n − 1. Âñå ôîðìóëû èçâåñòíû. Äîáàâèòüíå÷åãî.33Ðàññìàòðèâàåòñÿ òðåòèé ïîäõîä.mPf (x) =a j xj ;j=0Ã!(k) ¯¯m¯P¯aj xj¯j=0¯=mPmPCii=0j=0x=x0j(j − 1)...(j − k + 1)xj−k=0aj xj aj xj , îïå÷àòêànP1=1Ci xji , j = 0, ..., m.Çàäà÷à k = n -? ñëó÷àå ðàâíîìåðíîéñåòêè ïîëó÷èòñÿ ôîðìóëànPCj f (xj )h hj=1(k)f (x0 ) ≈|| |hkx1 x2 x3 .

. .|x0| |. . . xn−1xnÐàññìàòðèâàåòñÿ ñëó÷àé k = 11. x1 = x0 , x2 = x0 + hf (x0 + h) − f (x0 )(1)|= D+ (h)dfhx0³´(1)D+ (h)f (x0 ) - ðàçíîñòíîå îòíîøåíèå "âïåðåä"Ôîðìóëà òî÷íà äëÿ ìíîãî÷ëåíîâ äî 1-é ñòåïåíè âêëþ÷èòåëüíî.2. x1 = x0 − h, x2 = x0³(1)D− (h)f´(x0 ) =f (x0 ) − f (x0 − h).h3. x1 = x0 − h, x2 = x0 , x3 = x0 + h³´f (x0 + h) − f (x0 − h)(1)D0 (h)f (x0 ) =.2hÐàññìàòðèâàåòñÿ ñëó÷àé k = 2n = 3, x0 − h, x0 , x0 + hf (x0 + h) − 2f (x0 ) + f (x0 − h)D(2) (h)f (x0 ) =h2³´f (x0 + h) − 2f (x0 ) + f (x0 − h)D(h)f(x0 + h) − D− (h)f (x0 )−(1)(1)=D+ D− (h)(f ) (x0 ) =hh2Çàäà÷à. ( íóæíû äîïîëíèòåëüíûå òî÷êè)³´(1)(1)• D+ D+ (h)(f ) (x0 ) =?34(1)• D0³´(1)D0 (h)(f ) (x0 ) =?Ïîãðåøíîñòü ôîðìóëû ïðèáëèæåííîãî âû÷èñëåíèÿ ïðîèçâîäíîé ôóíêöèè ïîëó÷àåòñÿïðè ïîìîùè ôîðìóëû Òåéëîðàf (x + h) − f (x)1h2h= (f (x) + hf 0 (x) + f 00 (x) + ...

− f (x)) = f 0 (x) + f 00 (ξ);hh222f (x + h) − f (x − h)1hh2=(f (x) + hf 0 (x) + f 00 (x) + ... − f (x) + hf 0 (x) −+ ...) =2h 22h222000000000hhf (ξ1 ) + f (ξ2 )f (ξ)= f 0 (x) + f 000 (ξ1 ) + f 000 (ξ2 ) = f 0 (x) + αh2 , α ==.1212126Ïðè ðåàëüíûõ âû÷èñëåíèÿõ íà ÝÂÌ ñëåäóåò ó÷èòûâàòü âëèÿíèå ïîãðåøíîñòåéîêðóãëåíèÿ. Âñåãäà âìåñòî f (x) ïîëó÷àåòñÿ f˜(x)|f − f˜| ≤ ε ∼ 10−8 99K 10−16 .Ïîâåäåíèå ïîãðåøíîñòè âû÷èñëåíèÿ ïðîèçâîäíîé ôóíêöèè R(h) ñ èñïîëüçîâàíèåìîäíîñòîðîííåé ðàçíîñòè ïîêàçàíî íà ðèñóíêå.R(h)r6¡¡¡C · h¡¡¡¡¡¡¡2ε¡¡h0 ¡¡¡hhR(h) = C · h +2εhoptÌèíèìàëüíîå çíà÷åíèå R(h), êàê ñóììû äâóõ âûïóêëûõ âíèç ôóíêöèé, ïîëó÷àåòñÿ,êîãäà ñëàãàåìûå ðàâíû.r1εε, R(hopt = O(ε 2 ).R0 = C − 2 = 0 ⇒ hopt =hCÄëÿ öåíòðàëüíîé ðàçíîñòè ïîëó÷àåòñÿεR(h) = c1 h2 +hεC1 h − 2 = 02h√2hopt = 3 ε, Ropt = O(ε 3 ).35Äëÿ ôîðìóëû âû÷èñëåíèÿ k -òîé ïðîèçâîäíîé ïî ôîðìóëå ñ ïîðÿäêîì àïïðîêñèìàöèèp ïîëó÷èòñÿmPCj f (xj )f (k) ≈j=1hkC2 εR(h) = C1 hp + khp1hopt ∼ ε p+k , Ropt ∼ ε p+kÏðàâèëî Ðóíãå îöåíêè ïîãðåøíîñòåé(k)f (k) (x) − Dp (h)f (x) = chp + O(hp+1 )(k)f (k) (x) − Dp (qh)f (x) = c̃(qh)p + O(hp+1 )c ≈ c̃ ïðè äîñòàòî÷íî ãëàäêîé ôóíêöèè f .(k)chp =(k)Dp (h)f (x) − Dp (qh)f (x)+ O(hp+1 )qp − 1(I)h(I) - ïåðâîå ïðàâèëî Ðóíãå: áåðåì ε > 0, ε ¿ 1, âû÷èñëÿåì D(h), D( ), èç (I) íàõîäèì2chp ; åñëè chp < ε µ- ïðîèçâîäíàÿíàéäåíà ñ íóæíîé òî÷íîñòüþ, èíà÷å óìåíüøàåì øàã¶phhè ò.ä.âäâîå D( ) ⇒ c42(II) ïðàâèëî Ðóíãå - ïîâûøåíèå ïîðÿäêà àïïðîêñèìàöèèf (x + h) − f (x − h)= Ch2 + O(h4 )2hf (x + h/2) − f (x − h/2)f 0 (x) −= C(h/2)2 + O(h4 )2hf (x + h/2) − f (x − h/2) f (x + h) − f (x − h)f 0 (x) −−2h2h2Ch =+ O(h4 ) =1 − 1/441= (2f (x + h/2) − 2f (x − h/2) − f (x + h) + f (x − h)) + O(h4 )32hf(x+h)−f(x−h)21f 0 (x) =+ · ( .

Характеристики

Список файлов лекций