И.О. Арушунян - Конспект лекций (1160471), страница 5
Текст из файла (страница 5)
. . ) + O(h4 ).2h3 hÐîìáåðã(k)hDp (h)(k)Dp+1 (h/2)(k)(k)h/2Dp (h/2)Dp+2 (h/4)(k)Dp+1 (h/4)(k)(k)(k)···h/4Dp (h/4)Dp+2 (h/8)Dp+3 (h/8)(k)Dp+1 (h/8)(k)(k)Dp+2 (h/16)h/8Dp (h/8)(k)Dp+1 (h/16)(k)h/16 Dp (h/16)f 0 (x) −369 Ëåêöèÿ 9.×èñëåííîå èíòåãðèðîâàíèåZbf (x)dxa[a, b] ñ÷èòàåì êîíå÷íûì â R1 .f îáëàäàåò îïðåäåëåííîé ãëàäêîñòüþ.x1 , ..., xn ∈ [a, b] - ôèêñèðîâàíû, óçëû;C1 , ..., Cn - âåñà (êîýôôèöèåíòû).Zbf (x)dx ≈anXCj f (xj ) − êâàäðàòóðíàÿ ôîðìóëàj=1êîýôôèöèåíòû âûáèðàþòñÿ èç êàêèõ-íèáóäü ñîîáðàæåíèé, íàïðèìåð, ÷òîáû ôîðìóëàáûëà òî÷íà äëÿ ìíîãî÷ëåíîâ íàèáîëåå âûñîêîé ñòåïåíè.Îáû÷íî â ïîäèíòåãðàëüíîé ôóíêöèè âûäåëÿþò âåñîâóþ ôóíêöèþZbp(x)f (x)dx ≈anXCj f (xj ),p(x) − âåñ(∗)j=1Ïóñòü (∗) òî÷íà äëÿ f (x) = 1, x, x2 , ..., xm .
Ïðàâàÿ ÷àñòü àääèòèâíà, ñëåäîâàòåëüíî (∗)òî÷íà äëÿ ëþáîãî ìíîãî÷ëåíà ñòåïåíè íå âûøå m.ZbI(f ) :=p(x)f (x)dx;aS(f ) :=nXCj f (xj );j=1R(f ) := I(f ) − S(f ).Äëÿ ìíîãî÷ëåíîâ ñòåïåíè íå âûøå mR(Pm ) = 0.R - ëèíåéíàÿ ôóíêöèÿ. ÐàññìîòðèìR(f − Pm ) = R(f ) − R(Pm ) = R(f ).g(x) - ïðîèçâîëüíàÿ. Îöåíèì |R(g)|:Zb|R(g)| ≤|p(x)| · |g(x)|dx +anXj=137|Cj | · |g(xj )| ≤g(x) îãðàíè÷åíà íà [a, b] ⇒ ìîæíî îöåíèòü max-îìZ b≤Msup |g(xj )|,a x∈[a,b]Zbãäå M =|p(x)|dx +nX|Cj |.j=1aÅñëè p(x) ≥ 0 è âñå Cj ≥ 0ZbnXp(x)dx =ô-ëà ä.á. òî÷íà äëÿ f (x) = 1;Cjj=1aZbp(x)dx⇒ M =2a( p(x) ≡ 1 ⇒ M = 2(b − a) )Îöåíêà ïîãðåøíîñòè:õîòèì îöåíèòü |R(f )| = |R(f − Pm )| ≤ M kf − Pm kC(f äîëæíà áûòü ãëàäêîé ñòîëüêî ðàç, ñêîëüêî íàäî)áûëà îöåíêàkf − Lñ kC ≤çäåñü degLñ = ñ − 1;kf (ñ) k · (b − a)ññ! 22ñ−1degPm = m ⇒ ñ := m + 1kf (m+1) k · (b − a)m+1kf − Pm kC ≤.(m + 1)! 22m+1Òåîðåìà.
f ∈ C m+1 (f m+1 íåïðåðûâíà) è êâàäðàòóðíàÿ ôîðìóëà òî÷íà äëÿ ìíîãî÷ëåíîâñòåïåíè íå âûøå m⇒µZb|R(f )| ≤|p(x)|dx +Xa¶|Cj | ·kf (m+1) k · (b − a)m+1.(m + 1)! 22m+1Åñëè p(x) ≡ 1 è Cj ≥ 0⇒|R(f )| ≤kf (m+1) k · (b − a)m+2.(m + 1)! 22mÑòåïåíü m + 2 è ïðîèçâîäíàÿ íå óëó÷øàåìû, à çíàìåíàòåëü ì.á. óëó÷øåí.Ïîñòðîåíèå êâàäðàòóðíûõ ôîðìóë.38Ðàâíîìåðíîå ðàñïðåäåëåíèå óçëîâ íà îòðåçêå.Ïóñòüa = x1 < x2 < x3 < ... < xn = b è xk+1 − xk = h. ýòîì ñëó÷àå ôîðìóëà íàçûâàåòñÿ ôîðìóëîé çàìêíóòîãî òèïà.Êâàäðàòóðíûå ôîðìóëû òèïà Íüþòîíà-Êîòåñà (ò.ò.
ðàñïîëîæåíû ðàâíîìåðíî ïîîòðåçêó)ïðè n = 1 òî÷êó ïîìåùàåì ïîñåðåäèíå; n = 2 ⇒ x1 = a, x2 = bp(x) ≡ 1Z bZ bXf (x)dx ≈Ln (x)dx =dj f (xj )af (x) =nXaf (xj ) · Φj (x) +j=1{z|ωn (x)f (n) (ξ)n!}Ln (x)Y (x − xi )ξ çàâèñèò îò x(xj − xi )i6=jZ bZ bZ bnXωn (x) (n)f (ξ)dxI(f ) =f (x)dx =f (xj )Φj (x)dx +n!aaaj=1{z}{z} ||Φj (x) =S(f ) = (b − a)XS(f )Cj f (xj ),ãäåCj =1b−aR(f )ZbΦj (x)dx.a1. ïðè ôèêñèðîâàííîì ðàçáèåíèè íåçàâèñèìî îò a è b (äëèíû îòðåçêà) êîýôôèöèåíòûCj çàâèñÿò òîëüêî îò n.! ïðîâåðèòü, ñäåëàâ çàìåíó.2.
âñå Cj ñèììåòðè÷íû îòíîñèòåëüíî ñðåäíåãî Cj = Cn+1−j! äîêàçàòü.Ïðè n ≤ 8 äëÿ ôîðìóë Íüþòîíà-Êîòåñà Cj > 0. Ïðè n > 10 ãàðàíòèðîâàíî åñòüCj ðàçíîãî çíàêà.Z bnXM=dx +|Cj |aåñëè Cj > 0j=1⇒nX|Cj | = 1 =j=1åñëè ∃ i : Ci < 0⇒nXCj ,j=1nX|Cj | ìîæåò áûòü > 1, à ñ ðîñòîì n ì.á. À 1j=1(ïëîõî äëÿ ïîãðåøíîñòè)Ïðèìåðû:39••n=1µ¶Zba+bf (x)dx ≈ (b − a)C1 f (x1 ) = (b − a)f2•Mx1 =aaèíòåãðàë ≈ ïëîùàäè ïðÿìîóãîëüíèêàba+b2!••!!!!!!!!!!!!•Ma = x1Mb = x2a = x1n=2Zbf (x)dx ≈ (b − a)(C1 f (a) + C2 f (b))ab = x2C1 = C2 = 1/2èíòåãðàë ≈ ïëîùàäè òðàïåöèèÝòè êâàäðàòóðû òî÷íû äëÿ ìíîãî÷ëåíîâ ñòåïåíè 0 è 1, âêëþ÷èòåëüíî.|R(f )| ≤(b − a)3 00kf kC8åñëè (b − a) > 1 - íè÷åãî õîðîøåãî.a = x1a + b b = x3x2 =2Ma = x1Mx2 =a+b2n=3µµ¶¶Zba+bf (x)dx ≈ (b − a) C1 f (a) + C2 f+ C3 f (b)2Mb = x3aC1 = C3 = 1/6, C2 = 2/3ôîðìóëà Ñèìïñîíàòî÷íà äëÿ ìíîãî÷ëåíîâ ñòåïåíè 3 (m = 3)⇒n=4|R(f )| ≤(b − a)5 kf (4) kC1536⇒m = 3.Òåîðåìà.
(p(x) ≡ 1) Åñëèn = 2k + 1 ⇒ m = nn = 2k⇒ m=n−140Äîêàçàòåëüñòâî: ïîëüçóåìñÿ ñâîéñòâîì 2 (åñëè ìíîãî÷ëåí P (x) çíàêîïîñòîÿíåí èñèììåòðè÷åí îòíîñèòåëüíî ñåðåäèíû îòðåçêà ⇒ áóäåò âåðíî)µ¶2k+1a+bP (x) = x −, k ∈ Z+2Ïóñòü n = 2k + 1, áåðåì ìíîãî÷ëåí âèäà¶2z+1µa+b, z∈NP (x) = x −2íà íåì êâàäðàòóðíàÿ ôîðìóëà òî÷íà:Z bI(P ) =P (x)dx = 0 ôóíêöèÿ íå÷åòíà îòíîñèò.
ñåðåäèíû îòð.aS(P ) = (b − a)XCj P (xj )C1 = Cn ,C2 = Cn−1è ò.ä. ⇒P (x1 ) = −P (xn ) P (x2 ) = −P (xn−1 )îñòàåòñÿ òîëüêî Ck+1 P (xk+1 ) = 0, ò.ê. P = 0⇒ S(P ) = 0⇒ òî÷íà äëÿ òàêèõ P.a+bn = 2k ⇒ â ò.íèêîãî íåò.2n = 2k + 1 :µ µ¶n¶a+bI(Pn ) = I ã x −+ Qn−12íà êàæäîì èç íèõ ôîðìóëà òî÷íà ⇒ ôîðìóëà òî÷íà ,̈_Zbf (x)dx ≈nXaCj f (xj )j=1èùåì Cj è xj⇒ 2n íåèçâåñòíûõ.2f (x) = 1, x, x , ..., xm õîòèì: m + 1 = 2n⇒ ôîðìóëà áóäåò òî÷íà äëÿ m = 2n − 1.Ñèñòåìà áóäåò íåëèíåéíàÿ.Êâàäðàòóðíàÿ ôîðìóëà ÃàóññàZbp(x)f (x)dx ≈anXj=141Cj f (xj )(∗∗)Ëåììà.
Ïóñòü x1 , ..., xn óçëû (∗∗) è (∗∗) òî÷íà äëÿ ìíîãî÷ëåíîâ ñòåïåíè 2n − 1Zb⇒ωn (x)Pn−1 (x) · p(x)dx = 0a/ degPn−1 ≤ n − 1 /Äîêàçàòåëüñòâî. deg ωn (x)Pn−1 (x) ≤ 2n − 1Zb⇒ωn (x)Pn−1 (x) · p(x)dx =anXCj ωn (xj )Pn−1 (xj ) = 0j=1÷.ò.ä. ,̈_ωn (x) îðòîãîíàëüíà âñåì ìíîãî÷ëåíàì ìåíüøåé ñòåïåíè â ñêàëÿðíîì ïðîèçâåäåíèèZbf (x)g(x)dx.(f, g) =aÄëÿ ∀ n òàêîé ìíîãî÷ëåí ∃ (è ∀ p(x) - èíòåãðèð. è çíàêîîïðåä.) è èìååò n êîðíåé∈ (a, b).Óòâåðæäåíèå.
∀ n∃ ìíîãî÷ëåí Hn (x) ñòåïåíè n òàêîé, ÷òîZbp(x)Pn−1 (x)Hn (x) = 0∀ Pn−1 : degPn−1 ≤ n − 1aó Hn (x) ∃ n êîðíåé ∈ (a, b).(á/ä) ,̈^Íóëè ýòîé ôóíêöèè ðàçóìíî âçÿòü â êà÷åñòâå xj .Ïî p(x) ñòðîèì Hn (x), áåðåì åå íóëè - óçëû êâàäðàòóðíîé ôîðìóëû, áåðåì Ln ïî ýòèìóçëàì, èíòåãðèðóåì è ïîëó÷àåì Cj .10ZËåêöèÿ 10.bf (x)dx ≈anXCj f (xj ) − òî÷íà äëÿ ìíîãî÷ëåíîâ äî ñòåïåíè 2n − 1 âêëþ÷èòåëüíî.j=1Åñëè ôîðìóëà ∃, òî {xj } äîëæíû áûòü íóëÿìè îðòîãîíàëüíîãî ìíîãî÷ëåíàZbωn (x)P<n (x)dx = 0, ωn (x) =anY(x − xj ).j=1Ó ïðîèçâîëüíîãî îðòîãîíàëüíîãî ìíîãî÷ëåíà ñòåïåíè n ∃n íóëåé, êîòîðûå ëåæàò íàêàêîì-òî îòðåçêå.42Çàôèêñèðóåì n, xj âûáåðåì íóëÿìè îðòîãîíàëüíîãî ìíîãî÷ëåíà (ñ÷èòàåòñÿ, ÷òîýòîò ìíîãî÷ëåí çàáåñïëàòíî âñå ñâîè íóëè ïîêàæåò), Cj ïîäáèðàåì òàê, ÷òîáû ôîðìóëàáûëà òî÷íà äëÿ ìíîãî÷ëåíà äî ñòåïåíè 2n − 1 âêëþ÷èòåëüíî.Óòâåðæäåíèå. Ôîðìóëà òî÷íà äëÿ ìíîãî÷ëåíîâ ñòåïåíè 2n − 1.Q2n−1 (x) = ωn (x)Pn−1 (x) + Zn−1 (x) (äåëèòñÿ ñ îñòàòêîì)ÏîäñòàâëÿåìZZb|aωn (x)Pn−1 (x)dx +{z}bZn−1 dx ≈zX=0}|{ XCj ωn (xj )Pn−1 (xj ) +Cj Zn−1 (xj )aj=0xjP- íóëè îðòîãîíàëüíîãî ìíîãî÷ëåíà ⇒âCj ωn (xj )Pn−1 (xj ) âñå ñëàãàåìûå = 0.ZRbbZn−1 dx ≈aaωn (x)Pn−1 (x)dx = 0,XCj Zn−1 (xj )jò.ê.
ôîðìóëà òî÷íà äëÿ ìíîãî÷ëåíîâ äî 2n − 1 ⇒ ÷.ò.ä.(âìåñòî ≈ áóäåò =)Z 1Xf (t)dt ≈dj f (xj )−1óçëû äîëæíû óäîâëåòâîðÿòü óðàâíåíèþdn 2(t − 1)n = 0.dtnÂñå êîýôôèöèåíòû êâàäðàòóðíîé ôîðìóëû Ãàóññà > 0.Òåîðåìà. Âñå Cj > 0.µ¶2ωn (x)Äîêàçàòåëüñòâî. Âîçüìåì fk (x) =- ìíîãî÷ëåí ñòåïåíè 2n−2 è ïîäñòàâèìx − xkâ êâàäðàòóðíóþ ôîðìóëó:Zb0<fk (x)dx =anXCj fk (xj ) = / = 0, j 6= k/ = Ck (|{z}... )2 , ⇒ Ck > 0 ÷.ò.ä.j=16=0! Äîêàçàòü, ÷òî óçëû êâ.ô-ëû Ãàóññà ñèììåòðè÷íû îòíîñèòåëüíî ñåðåäèíû îòðåçêàè êîýôôèöèåíòû ïðè ñèììåòðè÷íûõ óçëàõ ðàâíû (Cj = Cn+1−j ).µZb|Rn (f )| ≤p(x)dx +aX¶|Cj | min kf − P2n−1 kC ≤ 2(b − a)) min kf − P2n−1 kC2n−12n−143Zbp(x)f (x)dx ≈anXCj f (xj ).j=1Åñëè p > 0 ï.â. íà îòðåçêå, (àíàëîãè÷íî òîìó, ÷òî ãîâîðèëè âûøå) Cj > 0, âåññèììåòðè÷åí îòíîñèòåëüíî ñåðåäèíû îòðåçêà ⇒ êîýôôèöèåíòû òîæå ðàâíû|Rn (f )| ≤ 2|Rn (f )| ≤ 2RbaRbap(x)dx min kf − P2n−1 kC ,2n−1¡ b−a ¢2n (2n)kf kCp(x)dx 2 2n−1.2(2n!)(íå îáÿçàòåëüíî → 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)Z bI(f ) =f (x)dx.aÏóñòü a = x0 < x1 < ... < xn = bZxkf (x)dx, k = 1, NIk (f ) =xk−1èIk (f ) ≈ Sk =nXxk − xk−12j=1µ· dj fxk−1 + xk xk − xk−1+tj22(áåðåì 1 ïîðÿäîê äëÿ âñåõ)Ñ÷èòàåì çàäàííîé ôîðìóëó:Z1F (t)dt ≈−1nXdj F (tj )j=1ñäåëàåì çàìåíó è èñïîëüçóåì ýòó ôîðìóëó[xk−1 , xk ] ↔ [−1, 1] x =xk−1 + xk xk − xk−1+t.2244¶µÏóñòü |Rk (f )| ≤ D ·qconstS(f ) =NXxk − xk−12Sk =k=1¶m+1max |f (m) |[xk−1 ,xk ]NnXxk − xk−1 X2k=1µdj fj=1¶xk−1 + xk xk − xk−1+tj .22Ñóììàðíàÿ ïîãðåøíîñòü|R(f )| ≤ DN µXk=1Ïóñòü xk − xk−1 = hmax |f(m)[xk−1 ,xk ]¶m+1¶ µxk − xk−1.(x)| ·2|R(f )| ≤ D · Am (b − a)hm ,ãäå D = D2−(m+1) , à Am = kf (n) kC .Ñîñòàâíàÿ ôîðìóëà òðàïåöèé.Zµbf (x)dx ≈ haf (x0 )f (xN )+ f (x1 ) + ...
+ f (xN −1 ) +22¶.ôîðìóëà Ñèìïñîíàôîðìóëà Ãàóññà×| × ×| × ×| × ×| × ×| × ×|| × ×| × ×| × ×| × ×| × ×|(ïðèìåðíî òî æå ñàìîå)Åñëè áîëüøîå ÷èñëî àðèôìåòè÷åñêèõ îïåðàöèé ⇒ âîçðàñòàåò ïîãðåøíîñòü.Àäàïòèâíûå êâàäðàòóðíûå àëãîðèòìû.Ïóñòü ïîãðåøíîñòü èìååò âèä Chm , íàäî ñ÷èòàòü ñ òî÷íîñòüþ ε. Êàê âûáðàòü ÷èñëîîòðåçêîâ?Ih - ñîñòàâíàÿ êâàäðàòóðíàÿ ôîðìóëà (îòðåçîê ðàçáèò íà îòðåçêè äëèíû h)I − Ih = Chm + O(hm+1 ),I − Ih/2 = C̃(h/2)m + O(hm+1 ),/C = C̃/Ih/2 − Ih + O(hm+1 )1-àÿ ôîðìóëà Ðóíãå äëÿ ÷èñë.
èíòåãðèðîâ.1 − 2−mÑ÷èòàåì I äëÿ h, äëÿ h/2 ⇒ íàõîäèì Chm è Chm ∨ ε, åñëè < ⇒ âñå õîðîøî; åñëè > ⇒óìåíüøàåì øàã â 2 ðàçà.Ïîäñòàâëÿåì ïîëó÷åííîå Chm :Chm =Ih/2 − Ih+O(hm+1 )I = Ih,h/2 + O(hm+1 ) = Ih +−m1−2|{z}2-àÿ ôîðìóëà ÐóíãåM- ýêñòðàïîëÿöèÿ: âåëè÷èíà M âñåãäà âíå îòðåçêà ñ êîíöàìè â Ih/2 , Ih .4511Ëåêöèÿ 11.Èòåðàöèîííûå ìåòîäû ðåøåíèÿ ñèñòåì ëèíåéíûõ àëãåáðàè÷åñêèõóðàâíåíèé.Ax = b b ∈ RNÒî÷íûå ìåòîäû îáû÷íî òðåáóþò O(N 3 ) îïåðàöèé.  îòäåëüíûõ ñëó÷àÿõ, êàê íàïðèìåðâ ñëó÷àå òðåõäèàãîíàëüíîé ìàòðèöû A, O(N 2 ).Õîòèì ïîñòðîèòü ìåòîä, êîòîðûé íå òðåáóåò îáðàùåíèÿ ìàòðèöû.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
