Буслов, Яковлев - Численные методы. 1. Исследование функций (947495), страница 3
Текст из файла (страница 3)
Âîçíèêàåò âîïðîñ: êàê ñòðîèòü èíòåðïîëÿöèîííûé ïîëèíîìk=0pN (x), âåäü åñòü ñâîáîäà âûáîðà áàçèñà â H èëè, ÷òî òî æå ñàìîå, ñâîáîäà ôîðìû çàïèñè? Áðàòü âêà÷åñòâå ϕk (x) ñîáñòâåííî ñòåïåíè xk çà÷àñòóþ îêàçûâàåòñÿ íåóäîáíûì.  ÷àñòíîñòè, íàïðèìåð, íàîòðåçêå [a, b] = [0, 1] ñòåïåííûå ôóíêöèè âûñîêèõ ïîðÿäêîâ âåäóò ñåáÿ âåñüìà ñõîæèì îáðàçîì: ñòåïåíè xiè xj "ïî÷òè ëèíåéíî çàâèñèìû"(îíè î÷åíü ïîõîæè äpóã íà äpóãà), ïpè ýòîì ïîëó÷àåòñÿ ïî÷òè âûðîæäåííàÿìàòðèöà Φ. Çàäà÷à íàõîæäåíèÿ êîýôôèöèåíòîâ ak ïðè ñòåïåíÿõ x îêàçûâàåòñÿ ïëîõî îáóñëîâëåííîé.Íåáîëüøîå âàðüèðîâàíèå âõîäíûõ äàííûõ (çíà÷åíèé fi ) ïðèâîäèò ê çíà÷èòåëüíûì èçìåíåíèÿì âåëè÷èíNWak . Åñëè æå â H =xi âûáðàòü äpóãîé áàçèñ, òî ýòî áóäåò îòâå÷àòü òîìó, ÷òî âìåñòî îïðåäåëèòåëÿi=0Âàíäåðìîíäà ( det Φ) è ñàìîé ìàòðèöû Φ, íåîáõîäèìîé äëÿ îòûñêàíèÿ êîýôôèöèåíòîâ ak â çàäà÷åf (xk ) = a0 + a1 xk + a2 x2k + . .
. + aN xNk , k = 0 , 1 , ... , N ,ìû áóäåì èìåòü íåêîòîðóþ äðóãóþ çàäà÷óf (xk ) = b0 p0 (xk ) + b1 p1 (xk ) + . . . + bN pN (xk ) , k = 0 , 1 , . . . , N ,10(2)NNPPãäå pk ∈ H. Êîýôôèöèåíòû bk îïðåäåëÿþòñÿ èç ðàâåíñòâà f (x) =bi pi (x) =aj xk , ïpè ýòîì pi (x) =i=0j=0PCik xk , òî åñòüNNN XNNXXXX¡¢Cik xk =bi Cik xk =ak xk ,f (x) =bii=0k=0 i=0k=0k=0èëè â ìàòðè÷íîé ôîðìåCT b = a .Òàêèì îáðàçîì, åñëè det C 6= 0, òî íîâàÿ çàäà÷à (2) òàê æå ðàçðåøèìà åäèíñòâåííûì îáðàçîì. Íåâûðîæäåííîñòü C ýêâèâàëåíòíà òîìó, ÷òî {pk (x)}Nk=0 îáðàçóþò áàçèñ â H (ñëåäñòâèå ëèíåéíîé àëãåáðû).
 ÷àñòíîñòè,åñëè ïîëèíîìû {pk (x)}Nk=0 ⊂ H òàêîâû, ÷òî deg pk = k , òî îíè àâòîìàòè÷åñêè ëèíåéíî íåçàâèñèìû èîáðàçóþò áàçèñ â H, ñëåäîâàòåëüíî, çàäà÷à èíòåðïîëÿöèè ðàçðåøèìà åäèíñòâåííûì îáðàçîì.Èíòåðïîëÿöèîííûé ïîëèíîì â ôîðìå ËàãðàíæàÎäèí èç âîçìîæíûõ ïîäõîäîâ ê ðåøåíèþ çàäà÷è èíòåðïîëÿöèè ìíîãî÷ëåíàìè, ñîñòîèò â òîì, ÷òîáû ìàòðèöà Φ èìåëà ïî âîçìîæíîñòè ïðîñòîé âèä. Èìåííî, ðàññìîòðèì çàäà÷ó èíòåðïîëÿöèè: ïóñòü äàíà èíòåðïîëÿöèîííàÿ òàáëèöà {xk , fk }Nk=0 . Òðåáóåòñÿ íàéòè ïîëèíîì pN (x) ñòåïåíè N , óäîâëåòâîðÿþùèé ýòîéòàáëèöå.Ââåäåì áàçèñ â H ={Lk (x)}Nk=0 , òî åñòüNWi=0xi , â êîòîðîì ìàòðèöà Φ ïðåäñòàâëÿåò ñîáîé åäèíè÷íóþ, îáîçíà÷èì åãîLk (xi ) = δki ; Φ = I .Îòñþäà pN (x) =NPk=0ak Lk (x) èfi = pN (xi ) =NXak Lk (xi ) = ai ,k=0èëèp(x) =NXfk Lk (x) .k=0Êàê ïîñòðîèòü ëàãðàíæåâû ïîëèíîìû Lk (x)? Ïîñêîëüêó Lk (xi ) = 0 ïpè i 6= k , òî òàêîé ïîëèíîì Lk (x)Qèìååò N êîðíåé è, ñëåäîâàòåëüíî, ÿâëÿåòñÿ ïîëèíîìîì ñòåïåíè N .
Òàêèì îáðàçîì, Lk (x) = Ck(x − xi ),i6=kQ1ïðè÷åì Lk (xk ) = 1 , ïîýòîìó Ck =(xk −xi ) , ñëåäîâàòåëüíî,i6=kLj (x) =Y x − xk.xj − xkk6=jÎêîí÷àòåëüíî, ðåøåíèå çàäà÷è èíòåðïîëÿöèè ïðèíèìàåò âèäp(x) =NXj=0fjY x − xk.xj − xkk6=jÈíòåðïîëÿöèîííûé ïîëèíîì â ôîðìå ÍüþòîíàÈíòåðïîëÿöèîííûé ïîëèíîì ñòåïåíè N , ïðîõîäÿùèé ÷åðåç çàäàííûå (N +1) òî÷êó {xi , fi }Ni=0 , åäèíñòâåííåí.
Îäíàêî çàïèñü åãî â ôîðìå Ëàãðàíæà ìîæåò äëÿ íåêîòîðûõ çàäà÷ îêàçàòüñÿ íåóäîáíîé. Ýòî ñâÿçàíîñ òåì îáñòîÿòåëüñòâîì, ÷òî âñå Ëàãðàíæåâû ïîëèíîìû Lk (x) èìåþò îäíó è òó æå ñòåïåíü N .  ÷àñòíîñòè, åñëè ê èíòåðïîëÿöèîííîé ñåòêå {xi , fi } äîáàâëÿòü íîâûå òî÷êè, òî íåëüçÿ âîñïîëüçîâàòüñÿ ðàíååïîñòðîåííûìè ëàãðàíæåâûìè ïîëèíîìàìè. Ïðèõîäèòñÿ äëÿ áîëåå âûñîêèõ ñòåïåíåé èõ ñòðîèòü çàíîâî.11Áóäåì ðåøàòü çàäà÷ó èíòåðïîëÿöèè âûáðàâ â H íîâûé áàçèñ {Nk (x)}Nk=0 :N0 (x) = 1 ; Nk (x) =Y(x − xi ) , k = 1 , . .
. , N .i<k òîì, ÷òî ýòî äåéñòâèòåëüíî áàçèñ â H ëåãêî óáåäèòüñÿ, ïîñêîëüêó deg Nk (x) = k , è òåì ñàìûì íüþòîíîâûìíîãî÷ëåíû Ni ëèíåéíî íåçàâèñèìû. Èòàê, áóäåì èñêàòü èíòåðïîëÿöèîííûé ïîëèíîì p(x) â âèäåp(x) =NXak Nk (x) .k=0Òàêîå ïðåäñòàâëåíèå ðåøåíèÿ è ÿâëÿåòñÿ çàïèñüþ èíòåðïîëÿöèîííîãî ïîëèíîìà â ôîðìå Íüþòîíà. Çàìåòèì, ÷òî Nk (xj ) = 0 ïpè j < k . Ñàìè êîýôôèöèåíòû ak íàõîäèì èç ñèñòåìû: p(xj ) = fj , j = 0 , . .
. , N ,èëèa0 = f0 ,a0 + a1 (x1 − x0 ) = f1 , ...mPak Nk (xl ) = fm , k=0...NPak Nk (xN ) = fN .k=0Ýòî òðåóãîëüíàÿ ñèñòåìà. Èç ïåðâîãî óðàâíåíèÿ îïðåäåëÿåòñÿ a0 , çàòåì, çíàÿ a0 , èç âòîðîãî óðàâíåíèÿîïðåäåëÿåì a1 , è òàê äàëåå.Ìîæíî ðåøèòü òó æå çàäà÷ó è áîëåå "ýëåãàíòíî". Ââåäåì, òàê íàçûâàåìûå, ðàçäåëåííûå ðàçíîñòè.Ðàçäåëåííûå ðàçíîñòè 0-ãî ïîðÿäêà ýòî ïðîñòî çíà÷åíèÿ ôóíêöèè fi = f (xi ).
Ðàçäåëåííûå ðàçíîñòèáîëåå âûñîêèõ ïîðÿäêîâ îïðåäåëÿþòñÿ ðåêóððåíòíî:1 ïîðÿäêà fij = f (xi , xj ) =fi −fjxi −xj2 ïîðÿäêà fijk = f (xi , xj , xk ) =;fij −fjkxi −xk;........................k ïîðÿäêà fβ0 ,β1 ...βk =fβ0 β1 ...βk−1 −fβ1 β2 ...βkx0 −xk.Íåòðóäíî âèäåòü, ÷òî ðàçäåëåííûå ðàçíîñòè èìåþò ðàçìåðíîñòü ñîîòâåòñòâóþùèõ ïðîèçâîäíûõ. Ðåøåíèå çàäà÷è èíòåðïîëÿöèè äàåòñÿ ñëåäóþùèì âûðàæåíèåìp(x) =NXf012 ...
k Nk (x) .k=0×òîáû óáåäèòüñÿ â ñïðàâåäëèâîñòè ýòîãî ïðåäñòàâëåíèÿ, ðàññìîòðèì ðàçäåëåííûå ðàçíîñòè èíòåðïîëÿöèîííîãî ïîëèíîìà p(x), â êîòîðûõ â êà÷åñòâå ïåðâîãî èç àðãóìåíòîâ âûñòóïàåò ñàìà ïåðåìåííàÿ x, à îñòàëüíûìè ÿâëÿþòñÿ òî÷êè èíòåðïîëÿöèè. Ñòåïåíü ýòîãî ïîëèíîìà ðàâíà N . Ðàçíîñòü p(x) − p(x0 ) = p(x) − f0îáðàùàåòñÿ â íîëü â òî÷êå x0 è, ñëåäîâàòåëüíî, äåëèòñÿ íà x − x0 . Òàêèì îáðàçîì ðàçäåëåííàÿ ðàçíîñòüpx0 =p(x)−p(x0 ),x−x0ðàññìàòðèâàåìàÿ êàê ôóíêöèÿ x, ÿâëÿåòñÿ ïîëèíîìîì ñòåïåíè N − 1.
Àíàëîãè÷íî, âòîðàÿ12ðàçäåëåííàÿ ðàçíîñòü px01 =px0 −p01x−x1åñòü ïîëèíîì ïî x ñòåïåíè N − 2 , ðàçäåëåííàÿ ðàçíîñòü N -ãîïîðÿäêà px012...N −1 óæå íå çàâèñèò îò x è ÿâëÿåòñÿ êîíñòàíòîé, è ðàçíîñòè áîëåå âûñîêîãî ïîðÿäêàòîæäåñòâåííî ðàâíû íóëþ. Òàêèì îáðàçîì,p(x) = p0 + (x − x0 )px0 = p0 + (x − x0 )[p01 + (x − x1 )px01 ] =p0 + (x − x0 )p01 + (x − x0 )(x − x1 )[p012 + (x − x3 )px012 ] = . .
. ==NXp012...kk−1Y(x − xi ) .i=0k=0Îñòàëîñü çàìåòèòü, ÷òî ïîñêîëüêó â óçëàõ èíòåðïîëÿöèè xi çíà÷åíèÿ èíòåðïîëÿöèîííîãî ïîëèíîìà ðàâíûòàáëè÷íûì çíà÷åíèÿì fi , òî è f01...k = p01...k .2.1.4 Ïîãðåøíîñòü èíòåðïîëÿöèèÏóñòü f (x) íåêîòîðàÿ ôóíêöèÿ è {xi , fi }Ni=0 èíòåðïîëÿöèîííàÿ òàáëèöà, êîòîðîé ýòà ôóíêöèÿ óäîâëåòâîðÿåò (òî åñòü f (xi ) = fi ). Ïî ýòîé æå èíòåðïîëÿöèîííîé ñåòêå ìîæíî ïîñòðîèòü è èíòåðïîëÿöèîííûéïîëèíîì pN (x). Âîçíèêàåò åñòåñòâåííûé âîïðîñ: íàñêîëüêî ðàçëè÷àþòñÿ ìåæäó ñîáîé ôóíêöèÿ f (x) è ïîëèíîì pN (x), óäîâëåòâîðÿþùèå îäíîé è òîé æå òàáëèöå? Åñëè íèêàêèõ ñâîéñòâ ãëàäêîñòè íå ïîòðåáîâàòüîò ôóíêöèè f , òî è ñêàçàòü íè÷åãî îïðåäåëåííîãî íåëüçÿ.
Îäíàêî, ïðè äîñòàòî÷íîé ãëàäêîñòè ôóíêöèè f ,ìîæíî îöåíèòü ðàçíîñòü f (x) − pN (x), èìåííî, ñïðàâåäëèâàÒåîðåìà. Ïóñòü f ∈ C N +1 [a, b] è pN èíòåðïîëÿöèîííûé ïîëèíîì, óäîâëåòâîðÿþùèå îäíîé è òîé æåñåòêå çíà÷åíèé {xi , fi }Ni=0 , òîãäà äëÿ ëþáîé òî÷êè x ∈ [a, b] ñóùåñòâóåò òàêàÿ òî÷êà ξ(x), ÷òîf (x) − pN (x) =f N +1 (ξ(x))NN +1 (x) ,(N + 1)!ãäå NN +1 (x) = (x − x0 )(x − x1 ) . . .
(x − xN ).Äîêàçàòåëüñòâî. Ïðåäñòàâèì ïîãðåøíîñòü â âèäåf (x) − pN (x) = NN +1 (x)r(x) .Òàêîå ïðåäñòàâëåíèå åñòåñòâåííî, ïîñêîëüêó è ðàçíîñòü f − pNè NN +1 â òî÷êàõ xi , i = 0, 1, . . . , Nîáðàùàþòñÿ â íîëü:[(x) − pN (x)]|x=xi = 0 ,i = 0, 1, ... , N .Ïðè ýòîì r(x) ∈ C[a,b] .
Ââåäåì òàêæå âñïîìîãàòåëüíóþ ôóíêöèþq(ξ) = f (ξ) − pN (ξ) − NN +1 (ξ)r(x) .Çäåñü x ïàpàìåòp, ξ ∈ [a, b] . Î÷åâèäíî, ÷òî q(ξ) = 0 â òî÷êàõ ξ = x0 , x1 , . . ., xN , x. Äàëåå, åñëèf ∈ C N +1 , òî è q ∈ C N +1 . Íàïîìíèì, ÷òî äëÿ ôóíêöèè, ïðèíàäëåæàùåé C 1 , ìåæäó äâóìÿ êîðíÿìè èìååòñÿïî êðàéíåé ìåðå îäèí íóëü ïðîèçâîäíîé. Ñëåäîâàòåëüíî, ìåæäó êðàéíèìè èç N + 2 íóëÿìè ôóíêöèè q(ξ)ëåæèò õîòÿ áû îäèí íóëü (N + 1)-îé ïðîèçâîäíîé.
Âûïèøåì ýòó ïðîèçâîäíóþ:q N +1 (ξ) = f N +1 (ξ) − (N + 1)!r(x) .Ïóñòü îíà îáðàùàåòñÿ â íóëü â òî÷êå ξ(x) : q(ξ(x)) = 0, ñëåäîâàòåëüíî, â ýòîé òî÷êå ξ(x) âûïîëíåíîr(x) =f N +1 (ξ(x)),(N + 1)!13îòêóäà óòâåðæäåíèå òåîðåìû ñëåäóåò íåïîñðåäñòâåííî.Çàìå÷àíèå. Ïðèâåäåííûì ðàññóæäåíèåì î êîðíÿõ âñïîìîãàòåëüíîé ôóíêöèè q ìîæíî âîñïîëüçîâàòüñÿòîëüêî, åñëè x 6= xi , òàê êàê ïpè x = xi ôóíêöèÿ q(x) èìååò ëèøü N + 1 êîðåíü.
Îäíàêî ïðè x = xióñëîâèÿ òåîðåìû âûïîëíåíû àâòîìàòè÷åñêè, ïîñêîëüêó f (xi ) = pN (xi ) è NN +1 (xi ) = 0.Èç óñëîâèÿ òåîðåìû ñëåäóåò àïðèîðíàÿ îöåíêà· N +1¸||f N +1 ||C|f(ξ)||f (x) − pN (x)| ≤ max|NN +1 (x)| ≤|NN +1 (x)| .(N + 1)!(N + 1)!ξ∈[a,b]√Ïpèìåp. Îöåíèòü ïîãðåøíîñòü ôóíêöèè y = x íà ïðîìåæóòêå [100,144] ñ óçëàìè 100, 121, 144 ñïîìîùüþ èíòåðïîëÿöèîííîãî ïîëèíîìà âòîðîé ñòåïåíè (â ôîðìå Ëàãðàíæà èëè Íüþòîíà ýòî âñå pàâíî,ïîñêîëüêó ýòî îäèí è òîò æå ïîëèíîì, ðàçíèöà ìîæåò âîçíèêíóòü òîëüêî, åñëè âû÷èñëåíèå êîýôôèöèåíòîâïðîèñõîäèò íå òî÷íî, à ñ íåêîòîðîé ïîãðåøíîñòüþ).Ðåøåíèå.
Äëÿ òîãî, ÷òîáû îöåíèòü ïîãðåøíîñòü, âîâñå íåò íåîáõîäèìîñòè ñòðîèòü ñàì èíòåðïîëÿöèîííûé ïîëèíîì, äîñòàòî÷íî âîñïîëüçîâàòüñÿ ïîëó÷åííîé îöåíêîé. Èòàê N = 2, y 0 =51 − 12,2x3y 00 = − 14 x− 2 ,5y 000 = 38 x− 2 , ñëåäîâàòåëüíî, max |y 000 | ≤ 38 (100)− 2 = 38 10−5 , îòêóäà|pN (x) − y(x)| ≤3 −5 110max |(x − 100)(x − 121)(x − 144)| < 3 · 10−3 .83!Òàêèì îáðàçîì, äàæå íå ñ÷èòàÿ ñàì èíòåðïîëÿöèîííûé ïîëèíîì pN (x), ìû îöåíèëè ïîãðåøíîñòü.2.1.5 Îöåíêà NN +1 (x).Ïpè ïðîèçâîëüíîì ðàñïîëîæåíèè óçëîâ îöåíèòü ìîäóëü NN +1 äîâîëüíî ñëîæíî.
Äëÿ ðàâíîìåðíîé ñåòêèñèòóàöèÿ âûãëÿäèò ïðîùå. Ïðîâåäåì ãðóáóþ îöåíêó. Ïóñòü x ∈ [xk−1 , xk ], òîãäà|x0 − x| ≤ kh , |x1 − x| ≤ (k − 1)h , . . . , |xk−1 − x| ≤ h ,|xk − x| ≤ h , |xk+1 − x| ≤ 2h , . . . , |xN − x| ≤ (N − k + 1)h ,îòêóäà |NN +1 | ≤ (N − k + 1)!k!hN +1 , è||f − pn ||C ≤ ||f N +1 ||Ck!(N + 1 − k)! N +1h,(N + 1)!|{z}k1/CN+1òî åñòü |f − pN | = O(hN +1 ) .  ýòîé ñèòóàöèè ãîâîðÿò, ÷òî èíòåðïîëÿöèîííûé ìíîãî÷ëåí pN (x) èìååòïîãðåøíîñòü O(hN +1 ).Çàìå÷àíèå.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
