Ответы на экзаменационные вопросы (1163657), страница 6
Текст из файла (страница 6)
Äëÿ äðóãîãî îòðåçêà [a, b] âñå ðåçóëüòàòû ìîãóòáûòü ïîëó÷åíû ïðè ïîìîùè ñòàíäàðòíîé çàìåíû ïåðåìåííîé.Ïóñòü íà [0, 1] çàäàíà ðàâíîìåðíàÿ ñåòêà xl = lh, l = 0, 1, ..., N − 1; N h = 1.  óçëàõ ñåòêèôîðìóëà (F) ïðåâðàùàåòñÿ â ðÿä Ôóðüåf (xl ) =N−1XAq exp{2πiqxl },q=037DFãäå ñîáðàëèñü ïîäîáíûå ÷ëåíû Aq =∞Ps=−∞aq+sN çà ñ÷åò ðàâåíñòâ exp{2πiq1 x} = exp{2πiq2 x}ïðè q2 xl − q1 xl = kN, k− öåëîå.Èñïîëüçîâàíèå ôîðìóëû (DF) âî âñåõ òî÷êàõ îòðåçêà [a, b] è åñòü òðèãîíîìåòðè÷åñêàÿèíòåðïîëÿöèÿ. Îñòàåòñÿ ïîêàçàòü, êàê îïðåäåëèòü êîýôôèöèåíòû Aq ïî çàäàííûì â óçëàõñåòêè çíà÷åíèÿì ôóíêöèè fl . Äëÿ ýòîãî ïðèìåíÿåòñÿ äèñêðåòíîå ïðåîáðàçîâàíèå Ôóðüå.Ðàç çàäà÷à äèñêðåòíàÿ, çíà÷èò êîíå÷íîìåðíàÿ, ò.å.
íàäî ðàññìîòðåòü ïðîñòðàíñòâîâåêòîðîâ. Âûáåðåì ïðîñòðàíñòâî âåêòîðîâ {y0 , y1 , ..., yN −1 } ðàçìåðíîñòè N.Âîçüìåì â ýòîì ïðîñòðàíñòâå êàêîé-íèáóäü îðòîíîðìèðîâàííûé áàçèñy (0) , y (1) , ..., y (N −1) , ñîñòîÿùèé èç N − 1 âåêòîðîâ.Ïðÿìîå ïðåîáðàçîâàíèå Ôóðüå äåëàåòñÿ òàê: óìíîæèì âåêòîð y ñêàëÿðíî íà âñå áàçèñíûåôóíêöèè(y, y (0) ) = d0 , (y, y (1) ) = d1 , ..., (y, y (N −1) ) = dN −1 ,(ïðÿìîå ïðåîáðàçîâàíèå Ôóðüå)ïîëó÷èì âåêòîð d = {d0 , d1 , ..., dN −1 }, êîòîðûé íàçûâàåòñÿ îáðàçîì Ôóðüå âåêòîðà y.Èç îðòîíîðìèðîâàííîñòè áàçèñà (y (i) , y (j) ) = δij ïîëó÷àåì ñïðàâåäëèâîñòü ðàçëîæåíèÿ yïî áàçèñíûì ôóíêöèÿì:âåêòîðíî y =N−1Xdm y (m) è ïîêîìïîíåíòíî yk =m=0N−1X(m)dm yk(îáðàòíîå ïðåîáðàçîâàíèå) .m=0Ïî îáðàçó Ôóðüå ìîæíî íàéòè ñàì âåêòîð ïî ýòèì ôîðìóëàì.
Ýòî íàçûâàåòñÿ îáðàòíûìïðåîáðàçîâàíèåì Ôóðüå.Áûñòðîå äèñêðåòíîå ïðåîáðàçîâàíèå Ôóðüå.Ïðîñòðàíñòâî âåêòîðîâ {y0 , y1 , ..., yN −1 } èìååò øèðîêî èçâåñòíûé îðòîíîðìèðîâàííûéáàçèñy (q) (xl ) = exp{−2πiqxl }, xl = l/N, N h = 1, 0 ≤ l ≤ N − 1.Áûñòðîå ïðåîáðàçîâàíèå Ôóðüå òðåáóåò ìåíüøå àðèôìåòè÷åñêèõ îïåðàöèé äëÿ ñâîåéðåàëèçàöèè, ÷åì O(N 2 ). Ýòî âîçìîæíî â ñëó÷àå, êîãäà N ñîñòàâíîå ÷èñëî. Èäåÿ áûñòðîãîïðåîáðàçîâàíèÿ Ôóðüå çàêëþ÷àåòñÿ â âûíåñåíèè çà ñêîáêó ïîâòîðÿþùåãîñÿ ìíîæèòåëÿ óðàçíûõ ñëàãàåìûõ! Åñëè N = p1 p2 , òî ìîæíî ðåàëèçîâàòü ïðÿìîå è îáðàòíîå ïðåîáðàçîâàíèåÔóðüå çà O(p21 p2 + p1 p22 ).
Åñëè N = 2r , òî àñèìïòîòèêà êîëè÷åñòâà àðèôìåòè÷åñêèõ äåéñòâèéáóäåò O(N log2 N ). Èìåííî ýòîò ñëó÷àé â ñî÷åòàíèè ñ âûáðàííûì áàçèñîì ïîëó÷èë íàçâàíèåáûñòðîãî äèñêðåòíîãî ïðåîáðàçîâàíèÿ Ôóðüå.Ôîðìóëû âû÷èñëåíèÿ êîýôôèöèåíòîâ áûñòðîãî ïðåîáðàçîâàíèÿ Ôóðüå çàïîìíèòüòðóäíî. Æåëàòåëüíî çàïîìíèòü ñïîñîá èõ âû÷èñëåíèÿ (õîòÿ áû áåç ôîðìóë). Èòàê, íàäîâû÷èñëèòü A0 , A1 , ..., AN −1 , èëè â äðóãîé ôîðìå (N = 2r , r = log2 N )·1A00...00 , A00...01 , A00...10 , ..., Aq0 q1 ...qr−1 , ..., A111...1 , q∀ =0| {z }røòóêò.å. èíäåêñ ïðåäñòàâèëè â äâîè÷íîé ôîðìå. Çíà÷åíèÿ ôóíêöèè çàäàþò "íà÷àëüíûå óñëîâèÿ"A(0) (j0 , j1 , ..., jr−1 ) = fl = f (xl ),l = 0, 1, ..., N ·− 1,1l|äåñÿòè÷íàÿ = jr−1 jr−2 . . .
j0 |äâîè÷íàÿ , j∀ =038ò.å. àðãóìåíòû ó A(0) - äâîè÷íûé èíäåêñ, íî â îáðàòíîì ïîðÿäêå. Äàëåå ïî ðåêóððåíòíûìôîðìóëàì âû÷èñëÿþòñÿA(m) (q0 , ..., qm−1 ; jm , ..., jr−1 ) =½¾1m−1P1 P−mkexp −2πijm 2qk 2 × A(m−1) (q0 , ..., qm−2 ; jm−1 , ..., jr−1 ), m = 1, ..., r=2 jm =0k=0ò.å. ïîêà èíäåêñû j∗ íå âûòåñíÿòñÿ èíäåêñàìè q∗ . Çàòåì ïîëàãàåìAq0 q1 ...qr−1 = A(r) (q0 , q1 , ..., qr−1 ).Ñìîòðèì íà ôîðìóëó è "ëåãêî" âèäèì, ÷òî êîëè÷åñòâî îïåðàöèé O(N · r).16Èíòåðïîëÿöèÿ è ïðèáëèæåíèå ñïëàéíàìè.Äàííûå: [a, b] : a = x1 < x2 < .
. . < xn = b; f (x) : f (xi ) = fi - èçâåñòíû.Îïðåäåëåíèå. Ïîëèíîìèàëüíûì ñïëàéíîì m-ãî ïîðÿäêàìíîãî÷ëåííàÿ íà îòðåçêàõ [xi , xi+1 ] ôóíêöèÿ êëàññà C (m−1) .íàçûâàåòñÿêóñî÷íî-Ñïëàéíû áûâàþò èíòåðïîëÿöèîííûå è àïïðîêñèìàöèîííûå èëè ëîêàëüíûå.Àïïðîêñèìàöèîííûå ñïëàéíû â ðàìêàõ êóðñà íå ðàññìàòðèâàþòñÿ. Èíòåðïîëÿöèîííûåñïëàéíû ñòðîÿòñÿ èç óñëîâèé ñîâïàäåíèÿ ñ çàäàííûìè çíà÷åíèÿìè f (xi ).Àïïðîêñèìàöèîííûå ñïëàéíû ñòðîÿòñÿ èç äðóãèõ ñîîáðàæåíèé (íàïðèìåð, íàèëó÷øåãîïðèáëèæåíèÿ â êàêîé-íèáóäü íîðìå) è îáû÷íî íå ñîâïàäàþò ñ çàäàííûìè f (xi ).Äàëåå ðå÷ü èäåò òîëüêî îá èíòåðïîëÿöèîííûõ ñïëàéíàõ.
Íàèáîëåå óïîòðåáèòåëüíûêóñî÷íî-êóáè÷åñêèå ñïëàéíû.Îïðåäåëåíèå. S(f, x) : - êóáè÷åñêèé ñïëàéí, åñëè1. S, S 0 , S 00 - íåïðåðûâíû íà [a, b];2. S(f, xi ) = fi ;3. íà [xi , xi+1 ]S - ìíîãî÷ëåí, degS = 3.Âîçüìåì (îò ôîíàðÿ) íàáîð òî÷åê {[xi , f (xi )]}|i=1,...,6 = [0, 0], [1, 1], [2, 4], [3, 3], [4, 4], [5, 7] èïîñìîòðèì, êàê âûãëÿäÿò ñïëàéíû.Êóñî÷íî-ëèíåéíûé ñïëàéí - ýòî ïðîñòî êóñî÷íî-ëèíåéíàÿ èíòåðïîëÿöèÿ è âñ¼.39x−2 + 3 x6−xx−8 + 3 x1 degree15êóñî÷íî-ëèíåéíûé ñïëàéí10x<1x<2x<3x<4otherwisey5–2024x68–5–10–15 êóñî÷íî-êâàäðàòè÷íûõ ñïëàéíàõ ãëàâíóþ ðîëü èãðàþò ñåðåäèíû îòðåçêîâ. Ýòèñïëàéíû â ïðîãðàììó ýêçàìåíà íå âõîäÿò.ïàðàáîëè÷åñêèé ñïëàéí894 x211892074 21180295xx+−11891189 11893826 212980 16520xx−+−1189118911891858 222545 11900xx+−1189118911892190 226612 14224xx+−1189118911895486 2128827 54860xx−+−118911891189123x<25x<27x<29x<2otherwise15x<2 degree10y5–2024x68–5–10–15Ñïîñîá ïîñòðîåíèÿ êóáè÷åñêèõ ñïëàéíîâ âõîäèò â ïðîãðàììó ýêçàìåíà.
Åãî íàäî çíàòüõîðîøî!40êóáè÷åñêèé ñïëàéí178 331xx+2092091950 2 472 3650 101xx −x+−209209112093618 2 24 36774 9217xx +x−+−1120920920998 372 2744 5741xx −x+−209112091964 3960 26008 4109xx −x+−20920920920915x<13 degree10x<2y5x<3–2x<4024x68–5otherwise–10–15Èñïîëüçîâàíèå èíòåðïîëÿöèîííûõ ñïëàéíîâ âûñîêèõ ñòåïåíåé ïðèìåíÿåòñÿ, êîãäàýòè ñïëàéíû íàäî äèôôåðåíöèðîâàòü ìíîãî ðàç äëÿ ïîëó÷åíèÿ ïðèáëèæåííûõ ôîðìóëâû÷èñëåíèÿ ïðîèçâîäíûõ âûñîêèõ ïîðÿäêîâ (âûøå 3).  ðàìêàõ êóðñà ñïîñîáû ïîñòðîåíèÿòàêèõ ñïëàéíîâ íå èçó÷àþòñÿ.Èç ñðàâíåíèÿ êàðòèíîê âèäíî, ÷òî íà îòðåçêå èíòåðïîëÿöèè x ∈ [0, 5] ñïëàéíû î÷åíüïîõîæè (êðîìå êóñî÷íî ëèíåéíîãî). Çà ãðàíèöàìè ýòîãî îòðåçêà ñïëàéíû âåäóò ñåáÿ êàêõîòÿò.Ïîâåäåíèå ñïëàéíà çà ãðàíèöàìè îòðåçêà èíòåðïîëÿöèè çàâèñèò îò ñïîñîáà âûáîðàãðàíè÷íûõ óñëîâèé.
Íà ãðàôèêàõ ïîêàçàíî ïîâåäåíèå íàòóðàëüíûõ ñïëàéíîâ.ñïëàéí ïÿòîé ñòåïåíè3222 5123277 276923xx −x+199553991039910142583 2 26586 3 13293 4 10071 513293 56007xx +x −x +x−+−19955399139913991019955 39910912 53365737 2 148830 3 30561 4688371 3452313xx −x +x −x+−1535399139913991039910199556387 56485483 2 179544 3 24168 43744678 11324517xx +x −x +x−+−1995539913991399103991019955276 53456277 2 69000 3 6900 4841746 8559003xx −x +x −x+−39913991399139910399103991−41x<1x<2x<3x<4otherwise5 degree1510y50–224x68–5–10–15Äàëåå öèòèðóåòñÿ ïî ëåêöèÿì.Èìååì [x1 , x2 ], ..., [xn−1 , xn ] - n − 1 îòðåçêîâ, íà êàæäîì èç êîòîðûõ ñïëàéí èìååò âèäPi (x) = a1,i + a2,i (x − xi ) + a3,i (x − xi )2 + a4,i (x − xi )3 .Äëÿ ïîñòðîåíèÿ ñïëàéíà òðåáóåòñÿ íàéòè (4n − 4) - íåèçâåñòíûõ (êîýôôèöèåíòîâ).Èç îïðåäåëåíèÿ êóáè÷åñêîãî ñïëàéíà äëÿ îòðåçêà [xi , xi+1 ] ïîëó÷èì S = si (x) : si (xi ) =fi , si (xi+1 ) = fi+1 - âñåãî 2n − 2 óñëîâèé (èñïîëüçîâàëè 2.
è S ∈ C[a, b] èç 1.)Èç óñëîâèÿ 1 îïðåäåëåíèÿ ïîëó÷èì åù¼s0i (xi+1 ) = s0i+1 (xi )s00i (xi+1 )=s00i+1 (xi )i = 1, n − 2 i = 1, n − 22n − 4 óñëîâèé⇒ âñåãî 4n − 6 óñëîâèé.Íåäîñòàþùèå 2 óñëîâèÿ (ãðàíè÷íûå) ìîãóò áûòü âûáðàíû ðàçëè÷íûìè ñïîñîáàìè:40 . s01 (x1 ) = f 0 (x1 ), s0n−1 (xn ) = f 0 (xn ). -  ýòîì ñëó÷àå ñïëàéí íàçûâàåòñÿ ïðàâèëüíûì.(Ìèíóñ: ìîæåì íå çíàòü f 0 (.), åå ìîæåò íå ∃òü). Ïðàâèëüíûé ñïëàéí åùå íàçûâàþòôóíäàìåíòàëüíûì.400 . s001 (x1 ) = s00n−1 (xn ) = 0.
-  ýòîì ñëó÷àå ñïëàéí íàçûâàåòñÿ íàòóðàëüíûì. Òàêèåãðàíè÷íûå óñëîâèÿ äëÿ ñïëàéíà íàçûâàþò åñòåñòâåííûìè.Ðàññìîòðèì îòðåçîê [xi , xi+1 ]. Íà ýòîì îòðåçêå ñïëàéí èìååò âèäsi (x) = f (xi ) + s0i (xi )(x − xi ) + s00i (xi )(x − xi )3(x − xi )2+ s000(x)ii62Ââåäåì îáîçíà÷åíèÿhi = xi+1 − xi ,zi = s00i (xi ),42i = 1, n − 1i = 1, n − 1.(0)Âûðàçèì âñå çíà÷åíèÿ si (xi ), s0i (xi ), s00i (xi ), s000i (xi ) ÷åðåç fi , zi è hi .
Ïðîäèôôåðåíöèðóåì (0)äâà ðàçà12(1)s0i (x) = s0i (xi ) + s00i (xi )(x − xi ) + s000i (xi ) (x − xi )2s00i (x) = s00i (xi ) + s000i (xi )(x − xi )Ïîëîæèì x = xi(2)⇒ s00i (xi+1 ) = s00i (xi ) + s000i (xi ) · hi| {z } | {z }zizi+1îòêóäà ïîëó÷àåìs000i (xi ) =zi+1 − zihi.Ïîäñòàâèì ïîëó÷åííîå âûðàæåíèå â (0) è ïîëîæèì x = xi+1 ⇒¶µzi+1 − zizi 20h3ifi+1 = fi + si (xi )hi + hi +6hi2îòêóäà ïîëó÷èì âûðàæåíèå äëÿs0i (xi ) =fi+1 − fi zi+1 hi zi hi−−36hi(3)Èç (1) è óñëîâèÿ íåïðåðûâíîñòè ïåðâîé ïðîèçâîäíîé ñïëàéíà â òî÷êå xi+1 , ò.å.
èç ðàâåíñòâàs0i (xi+1 ) = s0i+1 (xi+1 ), ïîëó÷èì óðàâíåíèås0i (xi ) + zi hi +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−hihi+1¶i = 1, n − 2(5)Ïîäðîáíîñòè âûâîäà ãðàíè÷íûõ óðàâíåíèé äëÿ ïðàâèëüíîãî ñïëàéíà îïóñòèì è íàðèñóåììàòðèöó çàäà÷è. ⇒ ñèñòåìà ñ òðåõäèàãîíàëüíîé ìàòðèöåé2(h1 + h2 )h20... 0h22(h2 + h3 )h3...
0 ...0h2(h+h)0334......... ······Äëÿ ðåøåíèÿ çàäà÷è èñïîëüçóåòñÿ ìåòîä ïðîãîíêè, òðåáóþùèé 8n + O(1) îïåðàöèé. ñëó÷àå íàòóðàëüíîãî ñïëàéíà ñèñòåìà óðàâíåíèé (5) äîïîëíÿåòñÿ ãðàíè÷íûìèóñëîâèÿìèz1 = zn = 0(6)è òàêæå ïîëó÷àåòñÿ çàäà÷à ñ òðåõäèàãîíàëüíîé ìàòðèöåé.Òåîðåìà 3.(îá îöåíêå ïîãðåøíîñòè) (á/ä)43Ïóñòü 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]Ýêñòðåìàëüíûå ñâîéñòâà ñïëàéíîâ ñëîâàìè ôîðìóëèðóþòñÿ ñëåäóþùèì îáðàçîì:• Êóñî÷íî-ëèíåéíûå ñïëàéíû - ýòî ïðîñòî êóñî÷íî-ëèíåéíàÿ èíòåðïîëÿöèÿ.
Îêàçûâàåòñÿðåøåíèå çàäà÷è ïîñòðîåíèÿ òàêîãî ñïëàéíà ìîæíî ñôîðìóëèðîâàòü â âèäåýêñòðåìàëüíîé çàäà÷è: íà ìíîæåñòâå êóñî÷íî-äèôôåðåíöèðóåìûõ ôóíêöèé s(x),óäîâëåòâîðÿþùèõ óñëîâèÿìZ bs(xi ) = f (xi ), I1 (s) =(s0 (x))2 ds < ∞aíàéòè ôóíêöèþ, ðåàëèçóþùóþ inf I1 (s).s• Êóñî÷íî-ïàðàáîëè÷åñêèå ñïëàéíû ïðèìåíÿþòñÿ äëÿ ïðèáëèæåíèÿ ôóíêöèè íàçàäàííîì êëàññå (ñì. îïðåäåëåíèå ñïëàéíà!) íàèáîëåå ãëàäêîé êóñî÷íî-êâàäðàòè÷íîéôóíêöèåé.• Àíàëîãè÷íî, êóáè÷åñêèå ñïëàéíû ïðèìåíÿþòñÿ äëÿ ïðèáëèæåíèÿ ôóíêöèè íàçàäàííîì êëàññå (ñì. îïðåäåëåíèå ñïëàéíà!) íàèáîëåå ãëàäêîé êóñî÷íî-êóáè÷åñêîéôóíêöèåé.
Ñëåäóþùàÿ âàðèàöèîííàÿ çàäà÷à:- "íà ìíîæåñòâå íåïðåðûâíûõ,íåïðåðûâíî-äèôôåðåíöèðóåìûõ è äâàæäû êóñî÷íî íåïðåðûâíî-äèôôåðåíöèðóåìûõôóíêöèé s(x), óäîâëåòâîðÿþùèõ óñëîâèÿìZ bs(xi ) = f (xi ),I2 (s) =(s00 (x))2 ds < ∞aíàéòè ôóíêöèþ, ðåàëèçóþùóþ inf I2 (s) ", äàåò ðåøåíèå - íàòóðàëüíûésêóáè÷åñêèé ñïëàéí. Îáîñíîâàíèå ýòîãî ôàêòà åñòü â êíèãå Í.Ñ.Áàõâàëîâà.17Íîðìû âåêòîðîâ è ìàòðèö.Ïîä÷èíåííûå è ñîãëàñîâàííûå íîðìû.èç Ëåêöèè 2: (íå ðåäàêòèðîâàëîñü)Íîðìû âåêòîðîâ. Íîðìû ìàòðèö.
Âîçìóùåíèÿ.Ïóñòü Ax = b - ëèíåéíàÿ ñèñòåìà, A - êâàäðàòíàÿ ìàòðèöà. Åñòåñòâåííî âîçíèêàþòâîïðîñû:441. Êàê îøèáêè â A è b âëèÿþò íà x ?2. Êàê îøèáêè â âû÷èñëåíèÿõ ïî âûáðàííîìó àëãîðèòìó (ìåòîäó) âëèÿþò íà x ?Íîðìû âåêòîðîâ.Îïðåäåëåíèå.k.k : Rn → Rn1) kxk ≥ 0, kxk = 0 ⇔ x = 0,2) kαxk = |α|kxk, α ∈ R,3) kx + yk ≤ kxk + kyk.Ïðèìåðû íîðì:1. Àáñîëþòíàÿ íîðìà (1-íîðìà,l1 -íîðìà) kxk1 =Pi|xi |2. Åâêëèäîâà íîðìà (2-íîðìà, l2 −íîðìà) kxk2 = (x, x)1/2 = (xT x)1/2 =¡Px2i¢1/23.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
