Буслов, Яковлев - Численные методы. 1. Исследование функций (947495), страница 4
Текст из файла (страница 4)
Ìîæíî ïîäîáðàòü óçëû òàê, ÷òîáû âåëè÷èíà max |NN +1 (x)| áûëà ìåíüøå, ÷åì ó ëþáîãîäðóãîãî ïîëèíîìà òîé æå ñòåïåíè ñ åäèíè÷íûì ñòàðøèì êîýôôèöèåíòîì (òàêèå ïîëèíîìû, íàèìåíåå îòêëîíÿþùèåñÿ îò íóëÿ, ìíîãî÷ëåíû ×åáûøåâà). Óçëû ðàñïîëîæåíû påäêî â ñåðåäèíå è ñãóùàþòñÿ óêîíöîâ ïðîìåæóòêà.2.1.6 Ñõîäèìîñòü èíòåðïîëÿöèè.
ÏðèìåðûÕîòÿ òåîðåìà Âåéåðøòðàññà è óòâåðæäàåò ïîëíîòó ïîëèíîìîâ, îäíàêî îíà íè÷åãî íå ãîâîðèò îòíîñèòåëüíîòîãî, êàê ñòðîèòü òàêèå ïîëèíîìû pn . Âîçíèêàþò âîïðîñû:141. Êàê âûáèðàòü èíòåðïîëÿöèîííóþ òàáëèöó {xi , fi }?2. Ñõîäèòñÿ ëè â òîì èëè èíîì ñìûñëå ïîñëåäîâàòåëüíîñòü àïïpîêñèìàöèîííûõ ïîëèíîìîâ ê èíòåpïîëèpóåìîé ôóíêöèè?Äëÿ óâåëè÷åíèÿ òî÷íîñòè ìîæíî èñïîëüçîâàòü ñëåäóþùèå ìåòîäû ïîñòðîåíèÿ ïîëèíîìà:1.
Óìåíüøåíèå øàãà ñåòêè, ïðè ïîñòîÿííîé ñòåïåíè N èíòåðïîëÿöèîííîãî ïîëèíîìà.  ýòîé ñèòóàöèèèíòåðïîëÿöèîííûé ïîëèíîì õîðîøî îïèñûâàåò ïîâåäåíèå ôóíêöèè f ∈ C N +1 ëèøü íà íåáîëüøîìïðîìåæóòêå (äëèíû hN ).2. Ðàçóìíîå ðàçìåùåíèå óçëîâ. Îáû÷íî ýòî îçíà÷àåò âûáîð â êà÷åñòâå óçëîâ êîðíåé ìíîãî÷ëåíîâ ×åáûøåâà.3.
Óâåëè÷åíèå ÷èñëà óçëîâ è, òåì ñàìûì, óâåëè÷åíèå ñòåïåíè èíòåðïîëÿöèîííîãî ïîëèíîìà.Èçâåñòíî, ÷òî åñëè y(x) öåëàÿ ôóíêöèÿ (ò.å. ðàçëàãàåòñÿ â ñòåïåííîé ðÿä ñ áåñêîíå÷íûì ðàäèóñîìñõîäèìîñòè íà êîìïëåêñíîé ïëîñêîñòè), òî ïpè ïðîèçâîëüíîì ðàñïîëîæåíèè óçëîâ íà ëþáîì ïðîìåæóòêå[a, b], pN (x) → y(x) ðàâíîìåðíî (ò.å. ïî íîðìå ïðîñòðàíñòâà íåïðåðûâíûõ ôóíêöèé ) ïpè N → ∞ . Îäíàêî,∞åñëè ôóíêöèÿ áåñêîíå÷íî äèôôåðåíöèðóåìà ëèøü â âåùåñòâåííîì ñìûñëå: f ∈ C(−∞,∞), òî ýòî óæå íåãàðàíòèðóåò ñõîäèìîñòè ïîñëåäîâàòåëüíîñòè èíòåðïîëÿöèîííûõ ïîëèíîìîâ ê ôóíêöèè f ïðè óâåëè÷åíèè÷èñëà óçëîâ.Ïpèìåp.f (x) = e0x≤0,1−x0<x.Ïîñòðîèì ïîñëåäîâàòåëüíîñòü èíòåðïîëÿöèîííûõ ïîëèíîìîâ ïî òî÷êàì îòðèöàòåëüíîé ïîëóîñè. Âñå îíèòîæäåñòâåííî ðàâíû íóëþ (pn (x) ≡ 0) è ñõîäèìîñòè ê ôóíêöèè f íåò.
Ïpàâäà óçëû ìû âûáðàëè âåñüìàíåýôôåêòèâíî.Ïðè ðàâíîìåðíîì ðàñïîëîæåíèè óçëîâ òàêæå íå âñåãäà óäàåòñÿ äîáèòüñÿ ñõîäèìîñòè. Ïðè÷èíà çäåñüçàêëþ÷àåòñÿ â òîì, ÷òî â îöåíêó èíòåðïîëÿöèè âõîäèò ïðîèçâîäíàÿ îò èíòåpïîëèpóåìîé ôóíêöèè. Åñëè fíå îáëàäàåò äîñòàòî÷íîé ãëàäêîñòüþ, îöåíêà òåðÿåò ñìûñë.Ïpèìåp Áåpíøòåéíà.y(x) = |x| , x ∈ [−1, 1] .Áåðíøòåéí ïîêàçàë, ÷òî äëÿ ðàâíîìåðíîé ñåòêè, çíà÷åíèÿ pN (x) ìåæäó óçëàìè èíòåðïîëÿöèè íåîãðàíè÷åííî âîçðàñòàþò ïpè N → ∞ â îêðåñòíîñòè òî÷åê -1, 1. Çàìåòèì, ÷òî ôóíêöèÿ |x| íåäèôôåðåíöèðóåìà âíóëå, íî â îêðåñòíîñòè íóëÿ èíòåðïîëÿöèîííûå ïîëèíîìû âûñîêîé ñòåïåíè äîñòàòî÷íî õîðîøî ïåðåäàþòïîâåäåíèå ôóíêöèè ìîäóëü. èçâåñòíîì ñìûñëå îáùåãî ìåòîäà ïîñòðîåíèÿ ïîñëåäîâàòåëüíîñòè èíòåðïîëÿöèîííûõ ïîëèíîìîâ íåò.È îñíîâàíèåì, ÷òîáû óòâåðæäàòü ñòîëü "ïðåíåïðèÿòíåéøåå èçâåñòèå", ÿâëÿåòñÿÒåîðåìà Ôàáåpà (NO GO Theorem).
Ïóñòü xji ïðîèçâîëüíûé èíòåðïîëÿöèîííûé ìàññèâ íà [a, b]:15x00x10x11x20...x21...x22.....xn0xn1xn2.....xnn... ... ... ... ... ...Òîãäà ñóùåñòâóåò òàêàÿ ôóíêöèÿ g ∈ C[a,b]è òàêàÿ òî÷êà x∗ ∈ [a, b] , ÷òî ïîñëåäîâàòåëüíîñòüèíòåðïîëÿöèîííûõ ïîëèíîìîâ, ïîñòðîåííàÿ ïî ñòðîêàì ýòîãî ìàññèâà è ñîâïàäàþùàÿ â íèõ ñ g , íåñòðåìèòñÿ â òî÷êå x∗ ê g(x∗ ) .Òàêèì îáðàçîì, ðàâíîìåðíîé ñõîäèìîñòè, âîîáùå ãîâîðÿ, äîáèòüñÿ íå óäàåòñÿ. Êàê "ïðåîäîëåòü"òåîðåìóÔàáåpà? Íåîáõîäèìî îòêàçàòüñÿ îò ïîòî÷å÷íîé ñõîäèìîñòè è çàìåíèòü åå íà ñõîäèìîñòü â ñðåäíåì. Èìåííî,âåðíî ñëåäóþùåå óòâåðæäåíèå.Ïóñòü Pn (x) ñèñòåìà ìíîãî÷ëåíîâ îðòîãîíàëüíûõ ñ âåñîì ρ ∈ C[a,b] íà ïðîìåæóòêå [a, b] :ZbPn (x)Pm (x)ρdx = δnm ,ρ(x) > 0 ,a(n)à xm êîðíè Pn . Âñå îíè âåùåñòâåííûå è ïðîñòûå è ïðèíàäëåæàò ïðîìåæóòêó (a, b) (ñì.
ãë. "×èñëåííîå(N +1)èíòåãðèðîâàíèå"). Âîçüìåì êîðíè xmîðòîãîíàëüíîãî ïîëèíîìà PN +1 â êà÷åñòâå óçëîâ èíòåðïîëÿöèè.(N +1)Ïî íèì ïîñòðîèì ïîëèíîì pN N -îé ñòåïåíè ïðîõîäÿùèé ÷åðåç N + 1 òî÷êó: f (xm(N +1)) = pN (xm), m =0 , . . . , N . Òîãäà äëÿ ëþáîé íåïðåðûâíîé íà [a, b] ôóíêöèè fZb[f (x) − pN (x)]2 ρ(x)dx −→ 0 .N →∞aÂûáèðàÿ òó èëè èíóþ âåñîâóþ ôóíêöèþ, ïîëó÷àåì ðàçëè÷íûå îðòîãîíàëüíûå ïîëèíîìû. Íàèáîëåå óïîòðåáèòåëüíûìè îðòîãîíàëüíûìè ïîëèíîìàìè ÿâëÿþòñÿ ïîëèíîìû ßêîáè, Ëåæàíäðà, ×åáûøåâà, Ëàãåpðà,Ýðìèòà.2.1.7 ÑïëàéíûÊàê ìû âèäåëè, óâåëè÷åíèå ñòåïåíè èíòåpïîëèpóþùåãî ïîëèíîìà äàëåêî íå âñåãäà ïðèâîäèò ê æåëàåìîìóðåçóëüòàòó.
Çà÷àñòóþ áîëåå ýôôåêòèâíûì ñïîñîáîì èíòåðïîëÿöèè íà ñåòêå {xi , fi }Ni=0 îêàçûâàåòñÿ èñïîëüçîâàíèå ñïëàéíîâ. Äàäèì ñîîòâåòñòâóþùèå îïðåäåëåíèÿ.Ïóñòü x0 < x1 < x2 · · · < xN íåêîòîðûå ÷èñëà. Ðàññìîòðèì êóñî÷íî ïîëèíîìèàëüíóþ ôóíêöèþ Snν(ν ≤ n, ν, n íàòóðàëüíûå), çàäàííóþ íà ïðîìåæóòêå [x0 , xN ] òàêóþ, ÷òî íà êàæäîì ïðîìåæóòêå [xi−1 , xi ]îíà ïðåäñòàâëÿåò ñîáîé íåêîòîðûé ïîëèíîì pin ñòåïåíè n:Snν (x) = pin (x), x ∈ [xi−1 , xi ], i = 1, 2, · · · N ,è, ïðè ýòîì, ðàññìàòðèâàåìàÿ íà âñåì ïðîìåæóòêå [x0 , xN ] ôóíêöèÿ Snν èìååò n − ν íåïðåðûâíûõn−νïðîèçâîäíûõ, òî åñòü Snν ∈ C[x, è, ñëåäîâàòåëüíî, äëÿ ïîëèíîìîâ pin0 ,xN ]âî âñåõ âíóòðåííèõ òî÷êàõx1 , x2 , · · · xN −1 ïðîìåæóòêà [x0 , xN ] âûïîëíåíîdk idk i+1p|=p |x=(xi ) , i = 1, 2, · · · , N − 1 , k = 0, 1, 2, · · · n − ν .x=(x)idxk ndxk n16Îïðåäåëåíèå.
Ôóíêöèÿ Snν (x) íàçûâàåòñÿ ñïëàéíîì ïîðÿäêà n (ñòåïåíè n) äåôåêòà ν, . Òî÷êè xiíàçûâàþòñÿ óçëàìè ñïëàéíà.Î÷åâèäíî, ÷òî äåôåêò ñïëàéíà ν ðàâåí åãî ïîðÿäêó n "ìèíóñ" ÷èñëî åãî íåïðåðûâíûõ ïðîèçâîäíûõ.Ñóùåñòâóåò ëè õîòÿ áû îäèí ñïëàéí? Ðàçóìååòñÿ, äà.  ÷àñòíîñòè, ïîëèíîì n-îé ñòåïåíè åñòü îäíîâðåìåííî ñïëàéí Snν äëÿ âñåõ ν îò 0 äî n .  êà÷åñòâå ïðèìåðà ñïëàéíà òàêæå îòìåòèì, ÷òî S11 ïðåäñòàâëÿåòñîáîé ëîìàííóþ, òî÷êàìè èçëîìà êîòîðîé ÿâëÿþòñÿ óçëû ñïëàéíà.Âñÿêèé ñïëàéíSnν , äî òåõ ïîð ïîêà ìû îò íåãî íè÷åãî íå ïîòðåáîâàëè êðîìå êàê ÿâëÿòüñÿ êó-ñî÷íî ïîëèíîìèàëüíîé ôóíêöèåé, îáëàäàåò íåêîòîðûì ÷èñëîì ñâîáîäíûõ ïàðàìåòðîâ, êîòîðûìè ìû ìîæåì ðàñïîðÿæàòüñÿ ïî ñâîåìó óñìîòðåíèþ.
×åìó ðàâíî ýòî ÷èñëî? Ó íàñ èìååòñÿNïðîìåæóòêîâSnνk = 1, 2, · · · , N . Íà êàæäîì èç ýòèõ ïðîìåæóòêîâ ñïëàéíäîëæåí ïðåäñòàâëÿòünP(k)ñîáîé íåêîòîðûé ïîëèíîì n-ñòåïåíè pkn =aj xj , êîòîðûé èìååò n + 1 ñâîáîäíûé ïàðàìåòð. Òà-∆k = [xk−1 , xk ],j=0êèì îáðàçîì, îáùåå ÷èñëî ñâîáîäíûõ ïàðàìåòðîâ ðàâíî N (n + 1) . Îäíàêî, îäíîâðåìåííî ñ ýòèì, íà ñàìñïëàéí íàëîæåíî íåêîòîðîå êîëè÷åñòâî óñëîâèé ãëàäêîñòè âî âíóòðåííèõ óçëàõ ñïëàéíà x1 , x2 , · · · , xN −1 .Ñïëàéí äîëæåí áûòü íåïðåðûâåí è íåïðåðûâíûìè äîëæíû áûòü n − ν åãî ïðîèçâîäíûõ â N − 1 òî÷êå−1{xi }Ni=1 , òî åñòü èç îáùåãî ÷èñëà ïàðàìåòðîâ N (n + 1) ìû äîëæíû âû÷åñòü ÷èñëî óñëîâèé ãëàäêîñòè,ðàâíîå (N − 1)(n − ν + 1).
 èòîãå, ÷èñëî F äåéñòâèòåëüíî ñâîáîäíûõ ïàðàìåòðîâ ðàâíîF = ν(N − 1) + n + 1 .0Ïóñòü òåïåðü íàì çàäàíà íåêîòîðàÿ èíòåðïîëÿöèîííàÿ òàáëèöà {x0i , yi }Mi=0 (òî÷êè xi ýòî óçëû èí-òåðïîëÿöèè, è îíè âîâñå íå îáÿçàíû ñîâïàäàòü ñ óçëàìè ñïëàéíà xi ), è ìû õîòèì íàéòè ñïëàéí Snν ,êîòîðûé áû ýòîé òàáëèöå óäîâëåòâîðÿë: Snν (x0i ) = yi , i = 0 , 1 , . . . , M . Ñóùåñòâóåò ëè ðåøåíèå òàêîé çàäà÷è èíòåðïîëÿöèè è åäèíñòâåííî ëè îíî? Åñëè ÷èñëî ñâîáîäíûõ ïàðàìåòðîâ ñïëàéíà F = ν(N − 1) + n + 1ñîâïàäàåò ñ ÷èñëîì M + 1 óñëîâèé èíòåðïîëÿöèè (óñëîâèÿ ðàâåíñòâà êîíêðåòíûì çíà÷åíèÿì fi â M + 1óçëå èíòåðïîëÿöèè), òî ìîæíî íàäåÿòüñÿ, ÷òî îòâåò ïîëîæèòåëüíûé, õîòÿ ýòî è íå âñåãäà òàê, è îòâåò, â÷àñòíîñòè, çàâèñèò îò âçàèìíîãî ðàñïîëîæåíèÿ óçëîâ èíòåðïîëÿöèè è óçëîâ ñïëàéíà.
Òàê, íàïðèìåð, åñëèìåæäó äâóìÿ ñîñåäíèìè óçëàìè xi−1 è xi ñïëàéíà Snν íàõîäèòñÿ áîëåå ÷åì n + 1 óçåë èíòåðïîëÿöèè,òî çàäà÷à íåêîððåêòíà, ïîñêîëüêó îò ïîëèíîìà n-îé ñòåïåíè íååñòåñòâåííî òðåáîâàòü, ÷òîáû îí ïðîõîäèëáîëåå ÷åì ÷åðåç n + 1 çàäàííóþ òî÷êó {x0i , fi }. Êðîìå òîãî, íà ïðàêòèêå äâà óñëîâèÿ îáû÷íî ðåçåðâèðóþòïîä ãðàíè÷íûå çíà÷åíèÿ ñïëàéíà èëè åãî ïðîèçâîäíûõ. Ñêàæåì, èíòåðïîëèðóåìàÿ ôóíêöèÿ èçâåñòíà íàì âíåêîòîðîì êîëè÷åñòâå òî÷åê è óäîâëåòâîðÿåò íåêîòîðîìó äèôôåðåíöèàëüíîìó óðàâíåíèþ è åãî ãðàíè÷íûìóñëîâèÿì. Ìîæíî, â ïðèíöèïå, ïîòðåáîâàòü, ÷òîáû ýòèì æå óñëîâèÿì óäîâëåòâîðÿë è èíòåðïîëèðóþùèé å¼ñïëàéí (õîòÿ íèêàêîìó óðàâíåíèþ îí, ðàçóìååòñÿ, íå óäîâëåòâîðÿåò).
Äëÿ íåêîòîðûõ êîíêðåòíûõ ñïëàéíîâ (íàïðèìåð, êóáè÷åñêèé ñïëàéí S31 ) åñòü áîëåå åñòåñòâåííûå ñîîáðàæåíèÿ, ïî êîòîðûì èìååò ñìûñë äâàóñëîâèÿ èñïîëüçîâàòü êàê ãðàíè÷íûå. ×óòü ïîçæå ìû ýòîãî êîñíåìñÿ.Ïàðàáîëè÷åñêèé ñïëàéí S21Äëÿ ïàðàáîëè÷åñêîãî ñïëàéíà ÷èñëî ñâîáîäíûõ ïàðàìåòðîâ F = ν(N − 1) + n + 1 = N + 2 è åãî èñïîëüçóþò,÷òîáû óäîâëåòâîðèòü èíòåðïîëÿöèîííîé òàáëèöå {x0i , fi } ñ N óçëàìè èíòåðïîëÿöèè, îñòàâëÿÿ äâà ïàðàìåòðà ïîä ãðàíè÷íûå óñëîâèÿ, êîòîðûå çàäàþòñÿ â êðàéíèõ óçëàõ ñïëàéíà x0 è xN .
Óçëû èíòåðïîëÿöèè17x0i ðàñïîëàãàþò ìåæäó ñîñåäíèìè óçëàìè ñïëàéíà xi è xi+1 :x0i ∈ (xi , xi+1 ) .(3)Ñïðàâåäëèâà òåîðåìà (ïðèâîäèìàÿ íàìè áåç äîêàçàòåëüñòâà) êîòîðàÿ óòâåðæäàåò, ÷òî ïðè âûïîëíåíèèóñëîâèÿ (3) çàäà÷à èíòåðïîëÿöèè ïàðàáîëè÷åñêèì ñïëàéíîì êîððåêòíà, ò.å. äëÿ ëþáîé èíòåðïîëÿöèîííîéòàáëèöû {x0i , fi }Ni=0 èíòåðïîëèðóþùèé å¼ ñïëàéí ñóùåñòâóåò è åäèíñòâåííåí ïðè ãðàíè÷íûõ óñëîâèÿõ âèäàα1 S(a) + β1 S 0 (a) = γ1 , α2 S(b) + β2 S 0 (b) = γ2 ,αi2 + βi2 6= 0 , i = 1, 2, a = x0 , b = xN .Äëÿ ïàðàáîëè÷åñêîãî ñïëàéíà óçëû èíòåðïîëÿöèè è óçëû ñïëàéíà íå ñîâïàäàþò, è ýòî îáñòîÿòåëüñòâîìîæíî èñïîëüçîâàòü äëÿ ïîâûøåíèÿ òî÷íîñòè èíòåðïîëÿöèè ôóíêöèè f (x). Èìåííî, ïîñêîëüêó ïàðàáîëà íåèìååò òî÷åê ïåðåãèáà, òî åñòåñòâåííî òî÷êè ïåðåãèáà èíòåpïîëèpóåìîé ôóíêöèè f (x) âûáèðàòü â êà÷åñòâåóçëîâ ñïëàéíà, à òî÷êè ëîêàëüíûõ ýêñòðåìóìîâ f (x) â êà÷åñòâå óçëîâ èíòåðïîëÿöèè.Çàäà÷à èíòåðïîëÿöèè êóáè÷åñêèì ñïëàéíîì S31 (x)1Ïóñòü íàì çàäàíà èíòåðïîëÿöèîííàÿ òàáëèöà {xi , yi }N0 è òðåáóåòñÿ íàéòè êóáè÷åñêèé ñïëàéí S3 (x), óçëûêîòîðîãî ñîâïàäàþò ñ óçëàìè èíòåðïîëÿöèè, è êîòîðûé áû ýòîé òàáëèöå óäîâëåòâîðÿë: S31 (xi ) = yi , i =0 , 1 , .
. . , N . Äëÿ ðåøåíèÿ ýòîé çàäà÷è ïðåæäå âñåãî îïðåäåëèì ÷èñëî ñâîáîäíûõ ïàðàìåòðîâ è êîëè÷åñòâîóñëîâèé, êîòîðûì íåîáõîäèìî óäîâëåòâîðèòü.Äëÿ ñïëàéíà Snν ÷èñëî ñâîáîäíûõ ïàðàìåòðîâ F ðàâíîF = ν(N − 1) + n + 1 = 1(N − 1) + 3 + 1 = N + 3 .Ïðè ýòîì íåîáõîäèìî óäîâëåòâîðèòü (N + 1)-ìó óñëîâèþ ðàâåíñòâà ñïëàéíà çíà÷åíèÿì èíòåðïîëÿöèîííîéòàáëèöû. Äâà îñòàâøèõñÿ ñâîáîäíûõ ïàðàìåòðà èñïîëüçóþò ïîä ãðàíè÷íûå çíà÷åíèÿ. Ïåðå÷èñëèì íàèáîëååóïîòðåáèòåëüíûå ãðàíè÷íûå óñëîâèÿ äëÿ êóáè÷åñêîãî ñïëàéíà.00001. S31 (x0 ) = S31 (xN ) = 0 åñòåñòâåííûé (íàòóðàëüíûé) ñïëàéí;00002. S31 (x0 ) = A , S31 (xN ) = B ;3.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
