Ответы на экзаменационные вопросы (1163657), страница 5
Текст из файла (страница 5)
Ôîðìóëà òî÷íà äëÿ ìíîãî÷ëåíîâ ñòåïåíè 2n − 1.Q2n−1 (x) = ωn (x)Pn−1 (x) + Zn−1 (x) (äåëèòñÿ ñ îñòàòêîì)ÏîäñòàâëÿåìZZb|aωn (x)Pn−1 (x)dx +}{zbZn−1 dx ≈azX=0{ X}|Cj Zn−1 (xj )Cj ωn (xj )Pn−1 (xj ) +j=0RbxjP- íóëè îðòîãîíàëüíîãî ìíîãî÷ëåíà ⇒ a ωn (x)Pn−1 (x)dx = 0,âCj ωn (xj )Pn−1 (xj ) âñå ñëàãàåìûå = 0.ZbaZn−1 dx ≈XCj Zn−1 (xj )jò.ê. ôîðìóëà òî÷íà äëÿ ìíîãî÷ëåíîâ äî 2n − 1 ⇒ ÷.ò.ä.(âìåñòî ≈ áóäåò =)Z1f (t)dt ≈X−1dj f (xj )óçëû äîëæíû óäîâëåòâîðÿòü óðàâíåíèþdn 2(t − 1)n = 0.dtnÂñå êîýôôèöèåíòû êâàäðàòóðíîé ôîðìóëû Ãàóññà > 0.Òåîðåìà. Âñå Cj > 0.¶µωn (x) 2- ìíîãî÷ëåí ñòåïåíè 2n − 2 è ïîäñòàâèì âÄîêàçàòåëüñòâî. Âîçüìåì fk (x) =x − xkêâàäðàòóðíóþ ôîðìóëó:Z0<abfk (x)dx =nXj=1Cj fk (xj ) = / = 0, j 6= k/ = Ck (|{z}... )2 , ⇒ Ck > 0 ÷.ò.ä.6=0! Äîêàçàòü, ÷òî óçëû êâ.ô-ëû Ãàóññà ñèììåòðè÷íû îòíîñèòåëüíî ñåðåäèíû îòðåçêà èêîýôôèöèåíòû ïðè ñèììåòðè÷íûõ óçëàõ ðàâíû (Cj = Cn+1−j ).µZ|Rn (f )| ≤bp(x)dx +aX¶|Cj | min kf − P2n−1 kC ≤ 2(b − a)) min kf − P2n−1 kC2n−12n−130Zbp(x)f (x)dx ≈anXCj f (xj ).j=1Åñëè p > 0 ï.â.
íà îòðåçêå, (àíàëîãè÷íî òîìó, ÷òî ãîâîðèëè âûøå) Cj > 0, âåñ ñèììåòðè÷åíîòíîñèòåëüíî ñåðåäèíû îòðåçêà ⇒ êîýôôèöèåíòû òîæå ðàâíûRb|Rn (f )| ≤ 2 p(x)dx min kf − P2n−1 kC ,2n−1a¡ b−a ¢2n (2n)bRkfkC.|Rn (f )| ≤ 2 p(x)dx 2 2n−12(2n!)a(íå îáÿçàòåëüíî → 0 ïðè n → ∞)Ïóñòü f ∈ C[a, b]. Ïî òåîðåìå Âåéåðøòðàññà îíà ïðèáëèæàåòñÿ ìíîãî÷ëåíîì. Òîãäàmin kf − P2n−1 kC → 0 ïðè n → ∞.2n−1ÃRb!2 p(x)dx − const .a(õîðîøî, åñëè ôóíêöèÿ: ïðèáëèæàåòñÿ ìíîãî÷ëåíàìè) åñëè f áåñêîíå÷íî äèôôåðåíöèðóåìà,(2n)òî kfkC íå ìîæåò ïåðåáèòü âñå îñòàëüíîå(ñ ðîñòîì n)12Ñîñòàâíûå êâàäðàòóðíûå ôîðìóëû.Îöåíêà ãëàâíîãî ÷ëåíà ïîãðåøíîñòè.Âîçüìåì îòðåçîê [a, b] è ðàçîáüåì åãî íà ìíîãî îòðåçêîâ. Íà êàæäîì èç ñîñòàâëÿþùèõîòðåçêîâ ïîñòðîèì êâàäðàòóðó, âû÷èñëèì ïðèáëèæåííûå çíà÷åíèÿ èíòåãðàëîâ íà ýòèõìàëåíüêèõ îòðåçêàõ, à ïîòîì âñå ñëîæèì - Ýòî è åñòü ñîñòàâíàÿ êâàäðàòóðíàÿ ôîðìóëà.Íàïðèìåð, ñîñòàâíàÿ êâàäðàòóðà ñ ðàâíîìåðíûì ðàçáèåíèåì îòðåçêà [a, b] è èñïîëüçîâàíèåìêâàäðàòóðû Ãàóññà íà êàæäîì ñîñòàâëÿþùåì îòðåçêå ïî òðåì óçëàì.Äëÿ ñîñòàâíîé ôîðìóëû ïðÿìîóãîëüíèêîâ ìîæíî ïðèâåñòè ïðîñòóþ èëëþñòðàöèþy = (x+1)sin x350230025010200150–2100–4500 2 2.2 2.4 2.6 2.83x3.2 3.4 3.6 3.84312x3456ZbI(f ) =f (x)dx.aÏóñòü a = x0 < x1 < ...
< xn = bZIk (f ) =èIk (f ) ≈ Sk =xknXxk − xk−12j=1Ñ÷èòàåì çàäàííîé ôîðìóëó:f (x)dx, k = 1, Nxk−1µ· dj fxk − xk−1xk−1 + xktj+22¶(áåðåì 1 ïîðÿäîê äëÿ âñåõ)Z1F (t)dt ≈nX−1dj F (tj )j=1ñäåëàåì çàìåíó è èñïîëüçóåì ýòó ôîðìóëó[xk−1 , xk ] ↔ [−1, 1] x =µÏóñòü |Rk (f )| ≤ D ·qconstS(f ) =xk − xk−12NXSk =k=1¶m+1xk − xk−1xk−1 + xkt.+22max |f (m) |[xk−1 ,xk ]nNXxk − xk−1 X2k=1µdj fj=1¶xk − xk−1xk−1 + xktj .+22Ñóììàðíàÿ ïîãðåøíîñòü|R(f )| ≤ DN µX[xk−1 ,xk ]k=1Ïóñòü xk − xk−1 = hmax |f(m)¶¶ µxk − xk−1 m+1.(x)| ·2|R(f )| ≤ D · Am (b − a)hm ,ãäå D = D2−(m+1) , à Am = kf (n) kC .Ñîñòàâíàÿ ôîðìóëà òðàïåöèé.Zµbf (x)dx ≈ haf (xN )f (x0 )+ f (x1 ) + ...
+ f (xN −1 ) +22¶.ôîðìóëà Ñèìïñîíàôîðìóëà Ãàóññà×| × ×| × ×| × ×| × ×| × ×|| × ×| × ×| × ×| × ×| × ×|(ïðèìåðíî òî æå ñàìîå)Åñëè áîëüøîå ÷èñëî àðèôìåòè÷åñêèõ îïåðàöèé ⇒ âîçðàñòàåò ïîãðåøíîñòü.3213Ïðàâèëî Ðóíãå ïðàêòè÷åñêîé îöåíêèïîãðåøíîñòè ÷èñëåííîãî èíòåãðèðîâàíèÿ.Àëãîðèòìû ñ àâòîìàòè÷åñêèì âûáîðîì øàãà.èç Ëåêöèè 9:Àäàïòèâíûå êâàäðàòóðíûå àëãîðèòìû.Ïóñòü ïîãðåøíîñòü èìååò âèä Chm , íàäî ñ÷èòàòü ñ òî÷íîñòüþ ε. Êàê âûáðàòü ÷èñëîîòðåçêîâ?Ih - ñîñòàâíàÿ êâàäðàòóðíàÿ ôîðìóëà (îòðåçîê ðàçáèò íà îòðåçêè äëèíû h)I − Ih = Chm + O(hm+1 ),I − Ih/2 = C̃(h/2)m + O(hm+1 ),ChmIh/2 − Ih + O(hm+1 )=1 − 2−m/C = C̃/1-àÿ ôîðìóëà Ðóíãå äëÿ ÷èñë.
èíòåãðèðîâ.Ñ÷èòàåì I äëÿ h, äëÿ h/2 ⇒ íàõîäèì Chm è Chm ∨ ε, åñëè < ⇒ âñå õîðîøî; åñëè > ⇒óìåíüøàåì øàã â 2 ðàçà.Ïîäñòàâëÿåì ïîëó÷åííîå Chm :Ih/2 − Ih+O(hm+1 )I = Ih,h/2 + O(hm+1 ) = Ih +−m1−2}{z|2-àÿ ôîðìóëà ÐóíãåM- ýêñòðàïîëÿöèÿ: âåëè÷èíà M âñåãäà âíå îòðåçêà ñ êîíöàìè â Ih/2 , Ih .Ïî ýòîìó âîïðîñó íàäî ÷èòàòü [1] 17.14Òåîðåìà ×åáûøåâà. Åäèíñòâåííîñòü ìíîãî÷ëåíàíàèëó÷øåãî ðàâíîìåðíîãî ïðèáëèæåíèÿ.Ïðèìåðûíàèëó÷øåãîðàâíîìåðíîãîïðèáëèæåíèÿ.R - ëèíåéíîå íîðìèðîâàííîå ïðîñòðàíñòâî (íàïðèìåð, ïðîñòðàíñòâî íåïðåðûâíûõ ôóíêöèéíà îòðåçêå C[a, b] ñ íîðìîé kf (x)kC[a,b] = max |f (x)|);x∈[a,b]g1 , ..., gn ∈ R - çàäàííûé íàáîð ëèíåéíî íåçàâèñèìûõ ýëåìåíòîâ (íàïðèìåð, ìíîãî÷ëåíîâ1, x, x2 , ...xn−1 );òðåáóåòñÿ íàéòè ýëåìåíò íàèëó÷øåãî ïðèáëèæåíèÿ :°°°°°°°°nnXX°°°°0 °°.°°f −f−cg=infcgjjjj°° c1 ,...cn °°°°°°j=1j=1Òåîðåìà. Ýëåìåíò íàèëó÷øåãî ïðèáëèæåíèÿ ñóùåñòâóåò äëÿ ëþáîé ôóíêöèè f ∈ R.(Äîêàçàòåëüñòâî â ìàò.
àíàëèçå, åñòü è â êíèãå [1])33Åñëè ïðîñòðàíñòâî ñòðîãî íîðìèðîâàííîå, ò.å.kf + gk = kf k + kgk, f 6= 0, g 6= 0 ⇒ f = αg, α = const,òî ýëåìåíò íàèëó÷øåãî ïðèáëèæåíèÿ åäèíñòâåííûé.Åñëè f ∈/ R, òî ýëåìåíòîâ íàèëó÷øåãî ïðèáëèæåíèÿ ìîæåò íå áûòü, à ìîæåò áûòüáåñêîíå÷íî ìíîãî. Íàïðèìåð, äëÿ ôóíêöèè y = sign x ∈/ C[−1, 1] ñóùåñòâóåò áåñêîíå÷íîìíîãî ìíîãî÷ëåíîâ ïåðâîé ñòåïåíè íàèëó÷øåãî ïðèáëèæåíèÿ â íîðìå C[−1, 1] :y6¡¡¡¡ ´´¾¡ ´ ©¡´´©©¡´©© ³³´©³³³¡©³´©³0 ³¡³´³©•©´³¡©³x´³©¡³©´³³©´³³³ ©©´ ¡© ´ ¡©©´´ ¡¡´¡´¡¡¡Åñëè ïðîñòðàíñòâî íå òîëüêî íîðìèðîâàííîå, íî è ãèëüáåðòîâî, òî çàäà÷à ïîñòðîåíèÿýëåìåíòà íàèëó÷øåãî ïðèáëèæåíèÿ°°2°°nnnXXX°°°f −f −c0j gj °cj gj , f −cj gj °° = c1inf,...cn°°j=1j=1j=1ñâîäèòñÿ ê ðåøåíèþ ñèñòåìû ëèíåéíûõ óðàâíåíèénnXX∂Φ= 0, k = 1, ..., n; Φ(c1 , ..., cn ) = f −cj gj , f −cj gj ,∂ckj=1j=1êîòîðóþ ìîæíî çàïèñàòü â âèäånXcj (gj , gk ) = (f, gk ), k = 1, ..., n; [(gj , gk )] − ìàòðèöà Ãðàìà.j=1Ðàññìàòðèâàåòñÿ çàäà÷à ïîñòðîåíèÿ ìíîãî÷ëåíànPj=0aj xj íàèëó÷øåãî ïðèáëèæåíèÿ äëÿôóíêöèè f (x) â íîðìå C[a, b] - ìíîãî÷ëåíà íàèëó÷øåãî ðàâíîìåðíîãî ïðèáëèæåíèÿ íàîòðåçêå.
Îòêëîíåíèå îáîçíà÷àåòñÿEn (f ) = kf − Q0n k ≤ kf − Qk, ∀Q. ëþáîì êóðñå, åñëè âñòðå÷àåòñÿ "èìåííàÿ" òåîðåìà, òî ê ýêçàìåíó íàäî ó÷èòü ååíàèçóñòü.  ýòîì âîïðîñå - äâå òàêèõ òåîðåìû.34Òåîðåìà Âàëëå-Ïóññåíà. Ïóñòü ñóùåñòâóþò n + 2 òî÷êè x0 < ... < xn+1 îòðåçêà[a, b] òàêèå, ÷òîsign((f (xi ) − Qn (xi ))(−1)i ) = const,ò.å. ïðè ïåðåõîäå îò òî÷êè xi ê ñëåäóþùåé òî÷êå xi+1 âåëè÷èíà f (x) − Qn (x) ìåíÿåò çíàê.ÒîãäàEn (f ) ≥ µ = min |f (xi ) − Qn (xi )|.i=0,...,n+1Òåîðåìà ×åáûøåâà.
×òîáû ìíîãî÷ëåí Qn (x) áûë ìíîã÷ëåíîì íàèëó÷øåãîïðèáëèæåíèÿ íåïðåðûâíîé ôóíêöèè f (x), íåîáõîäèìî è äîñòàòî÷íî ñóùåñòâîâàíèÿíà [a, b] ïî êðàéíåé ìåðå m = n + 2 òî÷åê x0 < ... < xn+1 òàêèõ, ÷òîf (xi ) − Qn (xi ) = α(−1)i kf − Qn k,ãäå i = 0, ..., n + 1, α = 1 (èëè α = −1) îäíîâðåìåííî äëÿ âñåõ i.Òî÷êè x0 , ..., xn+1 , óäîâëåòâîðÿþùèå óñëîâèÿì òåîðåìû, ïðèíÿòî íàçûâàòü òî÷êàìè÷åáûøåâñêîãî àëüòåðíàíñà.èç Ëåêöèè 7: Íåîáõîäèìîñòü.
- áåç äîêàçàòåëüñòâà. Äîñòàòî÷íîñòü.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 − Q0n kC ≤ f − Qn kC ⇒ kf − Q0n kC = kf − Qn kC .β = kf − Qn kC .Åäèíñòâåííîñòü ÌÍÐÏ.Ïðåäïîëîæèì, ∃ Q1n , Q2n : , Q1n (x) 6= Q2n (x) :kf −Q1n|kf − Q1n kC = kf − Q2n kC = En (f ),11+ Q2n≤ kf − Q1n kC + kf − Q2n kC = En (f )22 } 2{zÌÍÐϯ¯ 1¯¯ Qn (xi ) + Q2n (xi )¯− f (xi )¯¯ = En (f )¯2|(Q1n (xi ) − f (xi )) + (Q2n (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 .(ãäå-òî èñï.
íåïðåðûâíîñòü).35Çàìå÷àòåëüíûì ÿâëÿåòñÿ òî, ÷òî ìíîã÷ëåí íàèëó÷øåãî ðàâíîìåðíîãî ïðèáëèæåíèÿÿâëÿåòñÿ èíòåðïîëÿöèîííûì ìíîãî÷ëåíîì ïî íåêîòîðûì òî÷êàì, êîòîðûå íàõîäÿòñÿ ìåæäóòî÷êàìè àëüòåðíàíñà (åñòü n + 1 ïåðåñå÷åíèé íåïðåðûâíîé ôóíêöèè f (x) ìíîãî÷ëåíîìQ0n (x).)Ïðèìåðû.• Ïóñòü [a, b] = [−1, 1] è f (x) - íå÷åòíàÿ. Òîãäà ìíîãî÷ëåí íàèëó÷øåãî ðàâíîìåðíîãîïðèáëèæåíèÿ - íå÷åòíûé. Åñëè f (x) - ÷åòíàÿ, òî è ìíðï - ÷åòíûé.• f (x) = xn+1 + a1 xn + ...
+ an+1 ; èùåòñÿ ìíðï Q0n (x). Ïîëó÷èì f (x) − Q0n (x) - ìíîãî÷ëåí,íàèìåíåå óêëîíÿþùèéñÿ îò íóëÿ íà îòðåçêå - ò.å. ïðèâåäåííûé ìíîãî÷ëåí ×åáûøåâàñòåïåíè n + 1.• Òàê æå, êàê ìíîãî÷ëåí ×åáûøåâà "óâèâàåòñÿ" âîêðóã îñè àáñöèè, òàê è ìíîãî÷ëåííàèëó÷øåãî ðàâíîìåðíîãî ïðèáëèæåíèÿ âåäåò ñåáÿ âîêðóã äîñòàòî÷íî ãëàäêîéôóíêöèè. Òî÷êè àëüòåðíàíñà ñãóùàþòñÿ ê êîíöàì îòðåçêà è ðàçðÿæàþòñÿ âñåðåäèíå. Îöåíêà ïîãðåøíîñòè ìíðï ïðàêòè÷åñêè òàêàÿ æå, êàê ó èíòåðïîëÿöèîííîãîìíîãî÷ëåíà ïî íóëÿì ìíîãî÷ëåíà ×åáûøåâà íà ýòîì îòðåçêå.15Äèñêðåòíîå ïðåîáðàçîâàíèå Ôóðüå.Áûñòðîå ïðåîáðàçîâàíèå Ôóðüå.èç Ëåêöèè 7:Äèñêðåòíîå ïðåîáðàçîâàíèå Ôóðüåf (x) - ïåðèîäè÷åñêàÿ ñ ïåðèîäîì 1.f (x) =+∞Xak exp(2πikx), i2 = −1,X|ak | < ∞.k=−∞lÂîçüìåì ôèêñèðîâàííîå N > 0 è ðàññìîòðèì ýòîò ðÿä â òî÷êàõ ñåòêè xl = , l ∈ Z, f (xl ) =Nfl .k2 − 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=−∞Ak =fl =NP−1k=0k=0+∞Pk=−∞ak+jNl) − îáð.
ïðåîáð. ÔóðüåNl = 0, ..., N − 1.Ak exp(2πikÂâåäåì ñêàëÿðíîå ïðîèçâåäåíèå(f, g) =N −11 Xfk ḡk .Nk=036gk : gk (xl ) = exp(2πikxl ) - îðòîíîðìèðîâàííàÿ ñèñòåìà.−1k−j1 NPl)exp(2πiNN l=0k = j : (gk , gj ) = 1k 6= j : (gk , gj ) = 0 äëÿ ñàìîñòîÿòåëüíîé ïðîâåðêè(gk , gj ) =Aj = (f, gj ) =N −1l1 Xfl exp(−2πij ) − ïðÿìîå ïðåîáð. ÔóðüåNNl=0(f0 , f1 , ..., fN −1 ) ⇔ (A0 , A1 , ..., AN −1 ).Äëÿ îñóùåñòâëåíèÿ ïðåîáðàçîâàíèé òðåáóåòñÿ O(N 2 ) àðèôìåòè÷åñêèõ îïåðàöèé.Åñëè N = p1 p2 ñîñòàâíîå ÷èñëî p1 , p2 6= 1 , òî êîëè÷åñòâî àðèôìåòè÷åñêèõ îïåðàöèéìîæíî óìåíüøèòü.k = k1 + k2 p1 ; j = j2 + p2 j1 ;¶µ−1k1 NP=fj exp −2πiAk = A(k1 , k2 ) =NN j=0¶µ1 −1 pP2 −1(k1 + p1 k2 )(j2 + p2 j1 )1 pP=°fj +p j exp −2πi=p1 p2N j1 =0 j2 =0 2 2 11k1 j1k1 p/2 j1 p/1 k2 j2 p/1 p/2 k2 j1k1 j2+ k2 j2= k2 j1 ++++p1 p2p1p/1¶ p/2p/1 p2µp1 p/2p1 p22 −1kj21 pP,A(1) (k1 , k2 ) exp −2π=°Np2 j2 =1¶µ1 −1k1 j11 pP(1).(åñòü îïå÷àòêè)exp −2πãäå A (k1 , k2 ) =p1p1 j1 =1Äëÿ âû÷èñëåíèÿ 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 ).Äðóãîå èçëîæåíèå ýòîãî æå âîïðîñà (íå ïî Ëåêöèÿì)Åñëè f (x) - ïåðèîäè÷åñêàÿ ñ ïåðèîäîì 1 ôóíêöèÿ, òî äëÿ íåå åñòü ðàçëîæåíèå â ðÿäÔóðüå∞Xf (x) =aq exp{2πiqx},Fq=−∞ïðè÷åì äëÿ íåïðåðûâíûõ êóñî÷íî-äèôôåðåíöèðóåìûõ ôóíêöèé ýòî ðÿä ñõîäèòñÿ∞P|aq | < ∞.q=−∞Äàëåå áóäåì ðàññìàòðèâàòü îòðåçîê [0, 1].
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
