3. Interpolacja
3.1. Ogólne sformułowanie zagadnienia interpolacji
~
Niech R oznacza przestrzeń liniową wszystkich funkcji f : ha; bi !R, a R niech będzie jej n +1-wymiarową
podprzestrzeniÄ… liniowÄ… wyznaczonÄ… przez ukÅ‚ad liniowo niezależnych funkcji Á0; Á1; :::; Án 2 R. Wynika stÄ…d, że
~
każdÄ… funkcjÄ™ f 2 R można przedstawić w postaci kombinacji liniowej f = a0Á0 + a1Á1 + ::: + anÁn. Niech
na R będzie określonych n +1 funkcjonałów liniowych l0; l1; :::; ln. Zagadnienie interpolacji można sformułować
~ ~
następująco: dla dowolnego elementu f 2 R wyznaczyć taki element f 2 R, że
Å‚ ´
~
lk f = lk (f) ; k =0; 1; :::; n .(9)
~interpoluje f względem układu funkcjonałów l0; l1; :::; ln.
Mówimy wtedy, że f
~jest
Ponieważ f kombinacją liniową liniowo niezależnych funkcji, to wyznaczenie elementu interpolującego sprowadza
~
siÄ™ do znalezienia n +1 liczb a0; a1; :::; an takich, byfunkcja f = a0Á0 + a1Á1 + ::: + anÁn speÅ‚niaÅ‚a warunki (9). Z
liniowości l0; l1; :::; ln wynika, że trzeba rozwiązać układ równań liniowych:
a0lk (Á0) +a1lk (Á1) +::: + anlk (Án) =lk (f) ; k =0; 1; :::; n .
Zatem istnienie i jednoznaczność rozwiązania zagadnienia interpolacyjnego zależy od wartości wyznacznika
Å» Å»
Å» Å»
l0 (Á0) l0 (Á1) ::: l0 (Án)
Å» Å»
Å» Å»
l1 (Á0) l1 (Á0) ::: l1 (Án)
Å» Å»
D = .
Å» Å»
::: ::: ::: :::
Å» Å»
Å» Å»
ln (Á0) ln (Á1) ::: ln (Án)
Oczywiście dokładnie jedno rozwiązanie istnieje, jeśli D =0.
6
Alternatywne podejście do zagadnienia interpolacji
Zagadnienie interpolacji można sformułować inaczej następująco: na przedziale domkniętym [a; b] danych jest n+1
w punktów x0; x1; :::; xn, które nazywamy węzłami interpolacji, oraz wartości pewnej funkcji f(x) w tych punktach
f (x0) =y0, f (x1) =y1, ..., f (xn) =yn . (10)
~
Należy znalez
ć funkcję rzeczywistą f(x), zwaną funkcją interpolującą, określonej klasy, która w węzłach przyjmuje
~
takie same wartości jak f(x). Geometrycznie oznacza to poszukiwanie krzywej y = f(x) pewnego określonego typu,
przechodzącej przez zadany układ punktów (xi; yi) ; i =0; 1; :::; n.
Otrzymany wzór interpolacyjny wykorzystuje się zazwyczaj do obliczania przybliżonych wartości danej funkcji
f(x) w punktach różnych od węzłów interpolacji wewnątrz przedziału interpolacji lub poza nim, wtedy mówi sięotzw.
zadaniu ekstrapolacji.
Funkcji interpolującej poszukuje się jako funkcji pewnej z góry określonej postaci, np. wielomian algebraiczny,
wielomian trygonometryczny, funkcja wymierna, itp.
Interpolacja byłaniegdyś jedną z podstawowych metod numerycznych, obecnie straciła nieco na znaczeniu. Jednak
wzory interpolacyjne sÄ…podstawÄ… dla wielu metod stosowanych w innych zagadnieniach numerycznych, zatem w sensie
teoretycznym ma dość szerokie zastosowanie.
3.2. Przykłady zagadnień interpolacyjnych
Przedstawimy teraz najczęściej spotykane typy interpolacji wyodrębnione ze względu na postać funkcji interpolu-
jÄ…cej
PRZYKA
AD 1. Interpolacja Taylora
Funkcje bazowe: 1; x; x2; :::; xn
Funkcjonały liniowe lk(f) =f(k)(x0); k =0; 1; :::; n
Jest to przykład interpolacji wielomianem Taylora, gdy znamy wartości funkcji i jej n pierwszych pochodnych tylko w
1 węz
le.
PRZYKA
AD 2. Interpolacja Lagrange a
Funkcje bazowe: 1; x; x2; :::; xn
Funkcjonały liniowe lk(f) =f(xk); k =0; 1; :::; n
Jest to przykład interpolacji wielomianem algebraicznymi stopnia n, gdy znamy wartości funkcji w n +1 węzłach.
1
PRZYKA
AD 3. Interpolacja Hermite a
Funkcje bazowe: 1; x; x2; :::; xn
FunkcjonaÅ‚y liniowe lt;s(f) =f(s)(xt); t =0; 1; :::; m; s =0; 1; :::; ®t
Jest to przykÅ‚ad interpolacji wielomianem algebraicznym stopnia n = m + ®0 + ®1 + ::: + ®m, gdy znamy wartoÅ›ci
funkcji i jej pochodnych w m +1 wÄ™zÅ‚ach (w każdym ®t pochodnych). Interpolacja Lagrange a i Taylora sÄ… szczegól-
nymi przypadkami interpolacji Hermite a: interpolacja Lagrange a, jeÅ›li m = n i ®t = 0 dla wszystkich t oraz
interpolacja Taylora, jeÅ›li m =0 i ®0 = n.
PRZYKA
AD 4. Interpolacja wielomianami trygonometrycznymi
Funkcje bazowe: 1; cos x; sin x; cos 2x; sin 2x; :::; cos mx; sin mx
Funkcjonały liniowe lk(f) =f(xk); k =0; 1; :::; n =2m
Pm
Postać wielomianu interpolacyjnego Wn(x) =a0 + (ak cos kx + bk sin kx)
k=1
PRZYKA
AD 5. Interpolacja wykładnicza
Funkcje bazowe: ec0x; ec1x; :::; ecnx; c0; :::; cn 2 R; ci = cj dla i = j
6 6
Funkcjonały liniowe lk(f) =f(xk); k =0; 1; :::; n
Pn
Postać wielomianu interpolacyjnego Wn(x) = akeckx
k=0
PRZYKA
AD 6. Interpolacja Padé
Funkcję f(x) przybliża się funkcją wymierną postaci:
a0 + a1x + ::: + apxp
W (x) = .
b0 + b1x + ::: + bqxq
Jest to pewien odpowiednik interpolacji Taylora, gdyż funkcjonały liniowe są postaci lk(f) =f(k)(x0), k =0; 1; :::; n.
Takie zagadnienie mieści się w alternatywnym sformułowaniu zagadnienia interpolacji, ale nie da się opisać ogólnym
podejściem. Zatem nie można badać istnienia rozwiązania tego zagadnienia za pomocą wyznacznika D.
3.3. Interpolacja wielomianowa
TWIERDZENIE 15. (tw. aproksymacyjne Weierstrassa) Jeśli f : R ! [a; b] jest ciągła na [a; b], to dla danego
" >0 istnieje wielomian W , zded
ðniowany na [a; b] taki, że
jf(x) Ä„ W(x)j <" dla wszystkich x 2 [a; b] .
Twierdzenie powyższe jest bardzo ważne z teoretycznego punktu widzenia, ale nie daje efektywnej metody dla
obliczeń numerycznych. W tej części rozważymy zagadnienia znajdowania wielomianu algebraicznego, który jest
 bliski danej funkcji. Najważniejszym powodem rozważania klasy wielomianów w przybliżaniu funkcji jest fakt, że
pochodne i całki dowolnego wielomianu są łatwe do określenia i są również wielomianami.
3.3.1. Interpolacja Taylora
Wielomian Wn-tego stopnia, który najlepiej przybliża funkcję f w otoczeniu punktu x0 posiada n pochodnych w
(n)
tym punkcie takich, że Wn (x0) =f(n)(x0). Precyzyjnie mówiąc, jest to wielomian Taylora dla funkcji f w punkcie
x0 (czyli suma częściowa szeregu Taylora powstającego z rozwinięcia funkcji f w otoczeniu punktu x0):
(x Ä„ x0)2 (x Ä„ x0)n
Wn(x) =f (x0) +f0 (x0)(x Ä„ x0) +f00 (x0) + ::: + f(n) (x0) ; (11)
2! n!
przy czym
(x Ä„ x0)n+1
f(x) Ä„ Wn(x) =Rn(x) =f(n+1) ((x)) ; (12)
(n +1)!
gdzie (x) leży między x a x0.
Z interpolacją Taylora mamy do czynienia, gdy znamy wartość funkcji i jej n pochodnych w 1 węz
le. Powoduje to
ograniczenie użycia takiego przybliżenia do sytuacji, gdy interesuje nas tylko dostatecznie małe otoczeniu punktu x0.
3.3.2. Interpolacja Lagrange a
Rozważmy teraz zagadnienie określenia wielomianu 1-go stopnia, który przybliży funkcję f, dlaktórej f(x0) =y0 i
f(x1) =y1, czyli znalezienia prostej łączącej punkty (x0; y0) i (x1; y1). Wykorzystując równanie prostej przechodzącej
przez dwa punkty, otrzymamy
x Ä„ x1 x Ä„ x0
W1(x) = y0 + y1.
x0 Ä„ x1 x1 Ä„ x0
2
Nie jest to może oczywiste, ale W1 jest jedynym wielomianem 1-go stopnia, który spełnia warunki interpolacyjne (10).
Wynika to z poniższego
LEMAT 16. Istnieje dokładnie jeden wielomian interpolacyjny stopnia co najwyżej 1 Ą go, który w punktach x0 i
x1 (x1 = x2) przyjmuje wartości y0 i y1.
6
DÓWÓD: Załóżmy, że dane węzły interpolacji x0; x1 są położone w przedziale [a; b] w sposób dowolny. Poszuki-
wany wielomian jest postaci Wn(x) =a1x+a0. Korzystając z warunków (10) otrzymujemy układ 2 równań liniowych
z 2 niewiadomymi a0 i a1, którego macierz wspólczynników jest postaci:
· ¸
1 x0
A =
1 x1 .
Wyznacznik macierzy A jest równy
D =det A = x1 Ä„ x0 =0 ,
6
przy uwzględnieniu założenia, że x0 = x1, co oznacza, na podstawie tw.Cramera, że istnieje dokładnie jedno rozwiązanie
6
rozważanego układu równańi kończy dowód. Ą
Aby uogólnić idęe liniowej interpolacji, rozważmy konstrukcję wielomianu stopnia n-tego, którego wykres prze-
chodzi przez n +1 różnych punktów (x0; f (x0)), (x1; f (x1)), ..., (xn; f (xn)). Wielomian liniowy był skonstruowany
przy pomocy współczynników
x Ä„ x1 x Ä„ x0
L0(x) = i L1(x) = .
x0 Ä„ x1 x1 Ä„ x0
Jeśli x = x0, to L0(x0) =1 oraz L1(x0) =0, jeśli x = x1, to L0(x1) =0 oraz L1(x1) =1.
W ogólnym przypadku potrzebujemy skonstruować, dla każdego k = 0; 1; :::; n, współczynnik Lk(x) taki, że
Lk(xi) =0 dla i = k oraz Lk(xk) =1. Wówczas
6
(x Ą x0) ::: (x Ą xkĄ1)(x Ą xk+1) ::: (x Ą xn)
Lk(x) = : (13)
(xk Ą x0) ::: (xk Ą xkĄ1)(xk Ą xk+1) ::: (xk Ą xn)
Przyjmijmy następujące oznaczenie:
n
Y
!n(x) =(x Ä„ x0) ::: (x Ä„ xn) = (x Ä„ xi);
i=0
wówczas
! (x)
Qnn
Lk(x) = (13 )
(x Ä„ xk) (xk Ä„ xi)
i=0;i6=k
Wielomian interpolacyjny ze współczynnikami postaci (13) jest nazywany wielomianem interpolacyjnym Lagrange a
i zde
ðniowany przez poniższe twierdzenie:
TWIERDZENIE 17. Jeśli f jest funkcją, której wartości są dane wróżnych punktach x0; x1; :::; xn, to istnieje
dokładnie jeden wielomian Wn stopnia co najwyżej n-tego taki, że
f(xk) =Wn(xk) dla każdego k =0; 1; :::; n;
dany wzorem
n n
X Y
x Ä„ xi
Wn(x) := f(xk) : (14)
xk Ä„ xi
k=0 i=0;i6=k
Zbadajmy teraz kwestiędokładności, z jaką wielomian interpolacyjny przybliża funkcję interpolowaną. Spróbujemy
odpowiedzieć na pytanie, jak dalece ten wielomian przybliża funkcję f w punktach leżacych w przedziale [a; b], różnych
od węzłów. W tym celu trzeba na funkcję f nałożyć dodatkowe ograniczenia, a mianowicie musimy założyć, że w
rozpatrywanym przedziale ha; bi istniejÄ… pochodne f0(x); f00(x); :::; f(n+1)(x) funkcji f(x). Przyjmijmy oznaczenie,
że
Rn(x) =f(x) Ä„ Wn(x)
TWIERDZENIE 18. Jeśli x0; x1; :::; xn są węzłami interpolacji oraz funkcja f 2 Cn+1 [a; b], to dla każdego
x 2 [a; b] istnieje liczba (x) taka, że
!n(x)
Rn(x) =f(n+1) ((x)) : (15)
(n +1)!
3
DOWÓD: Zauważmy najpierw, że jeśli x = xi dla i =0; 1; :::; n, to f (xi) =Wn (xi) i wybierając (xi) dowolnie
w (a; b) otrzymujemy Rn (x) =0. Jésli x = xi dla dowolnego i =0; 1; :::; n, to zde
ðniujmy funkcjÄ™ g dla t 2 [a; b]
6
jako
n
Y
(t Ä„ xj)
g(t) =f(t) Ä„ Wn(t) Ä„ Rn(x) .
(x Ä„ xj)
j=0
Ponieważ f 2 Cn+1 [a; b], Wn 2 C1 [a; b] i x = xi dla dowolnego i, to wynika stąd, że g 2 Cn+1 [a; b]. Dla t = xi
6
n
Y
(xi Ä„ xj)
g (xi) =f (xi) Ä„ Wn (xi) Ä„ Rn (xi) =0 .
(x Ä„ xj)
j=0
Ponadto
n
Y
(x Ä„ xj)
g(x) =f (x) Ä„ Wn (x) Ä„ Rn (x) = f (x) Ä„ Wn (x) Ä„ Rn (x) =0 .
(x Ä„ xj)
j=0
Wówczas, g 2 Cn+1 [a; b] i g ... w n +2::: punktach x; x0; x1; :::; xn. Na podstawie uogólnionego tw. Rolle a istnieje
punkt x 2 (a; b), dla którego g(n+1)(x) =0. Obliczenie g(n+1) w punkcie x daje
Å»
0 1Å»
n
Å»
dn+1 @Y (t Ä„ xj)
(n+1)
Å»
AÅ» .
0 =g(n+1) (x) =f(n+1)(x) Ä„ Wn (x) Ä„ Rn(x) (16)
dtn+1 j=0 (x Ä„ xj)
Å»
t=x
(n+1)
PonieważQ jest wielomianem stopnia co najwyżej n, to jego (n +1)-sza pochodna Wn musi być równa 0.
Wn
n
Również ((t Ą xj) = (x Ą xj)) jest wielomianem stopnia n +1, więc
j=0
à !
n
Y
(t Ä„ xj) 1
Qn
= tn+1 +
(x Ä„ xj) (x Ä„ xj)
j=0
j=0
+(wielomian zmiennej t stopnia niższego niż n +1) ,
czyli
n
dn+1 Y (t Ä„ xj) (n +1)!
Qn
= .
dtn+1 j=0 (x Ä„ xj) (x Ä„ xj)
j=0
Równanie (16) otrzymuje teraz postać
(n +1)!
0 =f(n+1)(x) Ä„ 0 Ä„ Rn(x) Qn
(x Ä„ xj)
j=0
skąd otrzymujemy (15), co kończy dowód. Ą
Wzór (15) ma bardzo ważne znaczenie teoretyczne, gdyż wielomiany Lagrange a sąużywane w metodach różniczkowa-
nia i całkowania numerycznego.
UWAGA: (i) Praktyczne użycie wzoru (15) jest ograniczone tylko do tych funkcji, dla których znane są oszacowania
pochodnych (trygonometrycznych, logarytmicznych czy wykładniczych). Jeżeli przyjmiemy
Å»
Å»
Mn+1 = supŻf(n+1)(x)Ż ;
Å» Å»
x2[a;b]
to
Mn+1
jRn(x)j · j!n(x)j : (17)
(n +1)!
(ii) Zauważmy, że postać błędu interpolacji Lagrange a jest podobny jak w przypadku interpolacji Taylora. Różnica
tkwi między czynnikami (x Ą x1) ::: (x Ą xn) a (x Ą x0)n.
3.3.3. Interpolacja iterowana
Jednym z praktycznych utrudnień stosowania interpolacji Lagrange a jest fakt, że ze względu na sposób oszacow-
ania błędu nie można określić stopnia wielomianu interpolacyjnego zapewniającego żądaną dokładność, dopóki nie
zostaną zakończone obliczenia. Przy czym znalezienie wielomianu i-tego stopnia nie zmniejsza kosztu znalezienia
4
wielomianu stopnia i +1-szego. Naszym celem będzie określenie metody obliczania wielomianu interpolacyjnego tak,
aby wykorzystywać poprzednie obliczenia.
JeÅ›li wielomian Lagrange a pokrywajÄ…cy siÄ™ z funkcjÄ… f w k różnych punktach xm1; xm2; :::; xmk (0 · mi · n)
oznaczymy przez Wm1;m2;:::;mk, to poniższe tweirdzenie opisuje metodę rekurencyjnego generowania wielomianów
interpolacyjnych Lagrange a:
TWIERDZENIE 19. Niech x0; x1; :::; xn będąwęzłami interpolacji funkcji f. Jeśli
(x Ą xj)W0;1;:::;jĄ1;j+1;:::;k(x) Ą (x Ą xi)W0;1;:::;iĄ1;i+1;:::;k(x)
W (x) = ; (18)
xi Ä„ xj
to W jest wielomianem interpolacyjnym Lagrange a stopnia niewiększego niż k, który przybliża funkcję f w k +1
punktach x0; x1; :::; xk.
Praktyczne zastosowanie powyższego twierdzenia obrazuje następująca tablica:
x0 y0
x1 y1 W0;1
x2 y2 W1;2 W0;1;2
; (19)
x3 y3 W2;3 W1;2;3 W0;1;2;3
::: ::: ::: ::: ::: :::
xn yn WnĄ1;n WnĄ2;nĄ1;n WnĄ3;nĄ2;nĄ1;n ::: W0;1;:::;n
w której pierwsze dwie kolumny zawierają węzły i wartósci funkcji interpolowanej. W praktyce buduje się kolejne
wiersze takiej tablicy i ostatni z wielomianów jest szukanym wielomianem interpolacyjnym n-tego stopnia. Obliczenia
mozna przerwaćwcześniej, jeśli przy zadanej tolerancji dokładności, zwiększanie stopnia wielomianu interpolacyjnego
nie prowadzi do poprawy wyników. Dokonuje sie tego porównując kolejne wartości leżące na głównej przekątnej
macierzy (19), które reprezentują wartósci wielomianów interpolacyjnych stopni 1; 2; :::; n. PowŹzsza procedura jest
nazywana metodÄ… Neville a.
Bardzo podobny algorytm oferuje metoda Aitkena, w której konstruuje się tablicę postaci:
x0 y0
x1 y1 W0;1
x2 y2 W0;2 W0;1;2
; (20)
x3 y3 W0;3 W0;1;3 W0;1;2;3
x4 y4 W0;4 W0;1;4 W0;1;2;4 W0;1;2;3;4
::: ::: ::: ::: ::: ::: :::
przy pomocy wzoru:
W0;1;:::;kĄ1;k(x)(xm Ą x) Ą W0;1;:::;kĄ1;m(x)(xk Ą x)
W0;1;:::;k;m(x) = : (21)
xm Ä„ xk
3.3.4. Ilorazy różnicowe
Techniki interpolacji iterowanej sąużyteczne przy obliczaniu wartości wielomianów interpolacyjch coraz wyższego
stopnia w okreslonym punkcie i wszystkie wartości pośrednie używane w obliczeniach zależą od tego punktu, więc taki
schemat nie może być używany przy szukaniu postaci wielomianu interpolacyjnego.
Metody określania postaci wielomianu interpolacyjnego na podstawie stablicowanych danych są znane jako metody
ilorazów różnicowych i wykorzystywane są również jako podstawa technik różniczkowania i całkowania numerycznego,
a także przy numerycznym rozwiązywaniu równańróżniczkowych.
Najpierw wprowadzimy pojęcie ilorazu różnicowego, de
ðniowanego indukcyjnie:
DEFINICJA 20. Iloraz różnicowy rzędu zerowego funkcji f w punkcie xi jest równy wartości funkcji w tym
punkcie, tzn.
f [xi] :=f (xi) :
Iloraz różnicowy rzędu pierwszego funkcji f w punktach xi i xi+1 de
ðniujemy jako
f (xi+1) Ä„ f (xi)
f [xi; xi+1] := :
xi+1 Ä„ xi
Natomiast, gdy mamy określone ilorazy różnicowe rzędu k Ą 1-ego
f [xi; xi+1; xi+2; :::; xi+kĄ1] oraz f [xi+1; xi+2; :::; xi+kĄ1; xi+k] ;
5
to iloraz różnicowy k-tego rzędu funkcji f jest dany wzorem
f [xi; xi+1; :::; xi+kĄ1; xi+k] :=
f [xi+1; xi+2; :::; xi+kĄ1; xi+k] Ą f [xi; xi+1; xi+2; :::; xi+kĄ1]
= :
xi+k Ä„ xi
Ilorazy różnicowe można wygodnie zapisywać w tablicy trójkątnej (podobnej jak przy schemacie Neville a czy
Aitkena). Istotną własność ilorazów różnicowych podaje poniższe twierdzenie będące pewnym uogólnieniem tw. o
wartości średniej:
TWIERDZENIE 21. Przypuśćmy, że f 2 Cn [a; b] i x0; x1; :::; xn 2 [a; b]. Wówczas istnieje liczba 2 (a; b) taka,
że
f(n) ()
f [x0; x1; :::; xn] = :
n!
Do dlaszych rozważań potrzebna nam będzie jeszcze jedna własność ilorazów różnicowych, a mianowicie:
LEMAT 22. Iloraz różnicowy n-tego rzędu funkcji f można wyrazić nastepującym wzorem:
n
X
f(xj)
Qn
f [x0; x1; :::; xn] =
(xj Ä„ xl)
l=0;l=j
6
j=0
Załóżmy teraz, że Wn(x) jest wielomianem interpolacyjnym Lagrange a postaci (14) spełniającym warunki (10).
Można go zapisać w pozornie bardziej skomplikowanej formie
Wn(x) = W0(x) +[W1(x) Ą W0(x)] +[W2(x) Ą W1(x)] + ::: +[Wn(x) Ą WnĄ1(x)] =
n
X
= W0(x) + [Wk(x) Ą WkĄ1(x)] .
k=1
Oczywiście różnica Wk(x) Ą WkĄ1(x) jest wielomianem k-tego stopnia, który można przedstawić w postaci
Wk(x) Ą WkĄ1(x) =A (x Ą x0)(x Ą x1) ::: (x Ą xkĄ1) =A!kĄ1(x) (22)
gdzie A jest pewną stałą. Podstawmy x = xk i uwzględnijmy, że Wk (xk) =f (xk) =yk, wówczas
yk Ą WkĄ1 (xk) =A!kĄ1 (xk) .
Zatem, korzystajÄ…c ze wzoru (14), otrzymamy
PkĄ1 !kĄ1(xk)
yj (xkĄxj)ąkĄ1(xj )
yk Ą WkĄ1 (xk) yk j=0 !
A = = Ä„ =
!kĄ1 (xk) !kĄ1 (xk) !kĄ1 (xk)
k
X X
yk kĄ1 yj yj
= + = . (23)
!kĄ1 (xk) (xj Ą xk) !kĄ1(xj) !k (xj)
Ä… Ä…
j=0 j=0
Z(22) i (23) mamy
k
X
yj
Wk(x) Ą WkĄ1(x) = !kĄ1(x) . (24)
!k (xj)
Ä…
j=0
Korzystamy teraz z lem.22 dla i =0 i wzoru(24):
k k
X X
f (xj) yj
f [x0; x1; :::; xk] = = = A
Qk
!k(xj)
Ä…
(xj Ä„ xl)
j=0 l=0;l=j j=0
6
dla k =1; 2; :::; n, skÄ…d
Wk(x) Ą WkĄ1(x) =f [x0; x1; :::; xk] !kĄ1(x) .
Zatem otrzymujemy nastepującą postać:
Wn(x) =f [x0] +f [x0; x1] (x Ä„ x0) +f [x0; x1; x2] (x Ä„ x0)(x Ä„ x1) +:::
+ f [x0; x1; :::; xn] (x Ą x0)(x Ą x1) ::: (x Ą xnĄ1) ;
6
albo krócej
n
X
Wn(x) =f [x0] + f [x0; x1; :::; xk] !kĄ1(x): (25)
k=1
Wzór (25) jest znany jako wzór interpolacyjny Newtona z ilorazami różnicowymi. Zatem współczynnikami tego
wielomianu są elementy leżące na głównej przekątnej w tablicy ilorazów róznicowych.
UWAGA: (i) Dla obu wersji interpolacji wielomianowej, tak Lagrange a, jak i Newtona można rozważyć przy-
padek, gdy węzły x0; x1; :::; xn są równoodległe. Wówczas otrzymamy prostsze wzory interpolacyjne, wykorzystujące
dwumian Newtona oraz tzw. różnice skończone (progresywne, centralne lub wsteczne). W zależności od tego, w której
części przedziału interesuje nas zastosowanie interpolacji, rozważa się różne wersje tych uproszczonych wzorów, tzn.
wzory interpolacyjne Gaussa, Stirlinga lub Bessela. Patrz np. F-M-W lub D-M.
(ii) Porównanie kosztu obliczeniowego przedstawionych wersji interpolacji wielomianowej wygląda nastepująco:
+ ó
1 5
Lagrange n2 + n +1 n2 +4n +2
2 2
1 3
Newton n2 +3n n2 + n
2 2
3 5 1 1
Neville, Aitken n2 + n +1 n2 + n
2 2 2 2
3.3.5. Zbieżność procesów interpolacyjnych. Optymalny dobór węzłów interpolacji
Niech f(x) oznacza funkcję interpolowaną, zaś Wn(x) - wielomian interpolacyjny n-tego stopnia spełniający
warunki (10).
DEFINICJA 23. Mówimy, że proces interpolacyjny jest zbieżny do funkcji f(x) w punkcie x, gdy
~
lim Wn(~ =f(~ .
x) x)
n!1
Jeżeli ciąg fWn(x)g jest jednostajnie zbieżny na przedziale [a; b] do funkcji f(x), tomówimy, że proces interpolacyjny
jest jednostajnie zbieżny na przedziale [a; b].
UWAGA: Istnieją przykłady funkcji, dla których proces interpolacyjny z równoodległymi węzłami nie jest zbieżny.
Występuje wtedy tzw. zjawisko Rungego, które polega na nieograniczonym wzroście maksymalnego błędu interpo-
lacji przy wzroście liczby węzłów interpolacji (przy czym maksymalne błędy występują zawsze w pobliżu krańców
przedziału interpolacji).
Z wzoru (15) wynika, że błąd Rn(x) interpolacji Lagrange a jest iloczynem trzech czynników, z których:
- f(n+1) (x) zależy od własności funkcji f (na co nie mamy wpływu);
1
- zależy od liczby węzłów;
(n+1)!
- !n(x) zależy wyłącznie od doboru węzłów interpolacji.
Jeśli węzły interpolacji wybierzemy niewłaściwie, to może sięzdarzyć, że kres górny Rn(x) będzie bardzo duży, np.
w przypadku interpolacji w punktach bliskich jednemu z krańców przy węzłach skoncentrowanych w pobliżu drugiego
z krańców przedziału interpolacji. Gdy liczba węzłów n +1 jest zadana, wielkość błędu interpolacji zależy tylko od
!n(x) - czyli chodzi o wybór takich węzłów, bywielomian !n(x) miał jak najmniejsze maksimum w przedziale [a; b].
Najlepsze w omawianym sensie są węzłyinterpolacji zw. węzłami Czebyszewa, obliczane według wzoru
µ Å›
b Ä„ a 2i +1 b + a
xi = cos ź + ; i =0; 1; :::; n . (26)
2 2n +2 2
Å‚
2i+1
Wartości cos ź są pierwiastkami wielomianu Czebyszewa Tn+1(x), który jest zde
ðniowany wprost jako
2n+2
Tn(x) =cos(n arccos x) :
ub rekurencyjnie nastepujÄ…co:
T0(x) = 1
T1(x) = x
Tn(x) = 2xTnĄ1(x) Ą TnĄ2(x) dla n =2; 3; :::
Węzły te nie są rozmieszczone równomiernie na przedziale [a; b], lecz zagęszczone przy krańcach przedziału. W tym
przypadku mamy
(b Ä„ a)n+1
j!n(x)j · ,
22n+1
7
co implikuje, że wybierając węzływedług wzoru (26) otrzymamy następujące oszacowanie błędu
Mn+1 (b Ä„ a)n+1
jRn(x)j · ó . (27)
(n +1)! 22n+1
Na ogół taki dobór węzłów nie gwarantuje, by błąd bezwzględny interpolacji był dowolnie mały przy dostatecznie
dużym n. Tak wyznaczony wielomian interpolacyjny daje tylko najmniejszą wartość oszacowania (17).
3.4. Interpolacja funkcjami sklejanymi
Alternatywnym podejściem do przybliżania dowolnej funkcji na domkniętym przedziale jest podział tego przedzi-
ału na podprzedziały i skonstruowanie różnych wielominaów interpolacyjnych na każdym z nich. Mówimy wtedy o
interpolacji przedziałami wielomianowej lub interpolacji funkcjami sklejanymi. Jest ona bardziej wskazana, zwłaszcza
gdy liczba danych węzłów interpolacji jest względnie duża (np. co najmniej 30 Ą 40), dane sązwiązane z pewną znaną
lub nieznaną funkcją, której pochodne są duże lub nie istnieją, dane pochodzą z naturalnego lub  niematematycznego
z
ródła (np. granica państwa lub pro
ðl samolotu).
Najprostszymtypemtakiej interpolacji jest użycie funkcji liniowych, co sprowadza się do połączenia odcinkami
punktów danych tablicą wartósci funkcji. Stosowana jest tylko, gdy mamy do czynienia z dostatecznie małymi pod-
przedziałami w przypadku przybliżania funkcji trgonometrycznych i logarytmicznych. Jednak, tak skonstruowana
funkcja nie jest różniczkowalna w krańcach podprzedziałów, czyli w geometrycznym sensie, nie jest dostatecznie
 gładka .
W przypadku użycia funkcji kwadratowych pojawiają się dwa problemy. Po pierwsze - brakuje jednego warunku,
który umożliwi jednoznaczne wyznaczenie paraboli przechodzącej przez dwa sąsiednie punkty, z czym mozna sobie
poradzić, wymagając, aby otrzymana funkcja interpolująca miałaciągłą pochodną (geometrycznie daje to jednocześnie
gwarancję, że wykres nie będzie posiadał  ostrzy ). Po drugie - nie można zapewnić, by pochodna funkcji interpolującej
pokrywała sie z pochodna funkcji interpolowanej w krańcach przedziału interpolacji.
Najbardziej użyteczną interpolacją tego typu jest interpolacja funkcjami sklejanymi stopnia trzeciego, której dokonuje
się tak, by funkcja interpolująca była dwukrotnie różniczkowalna w sposób ciągły, a zatem zapewnia dostateczną jej
gładkość.
DEFINICJA 24. Niech funkcja f będzie określona na [a; b] oraz a = x0 stopnia trzeciego (prościej: splajnem sześciennym) nazywamy funkcję S, któraspełnia nastepujące warunki:
(a) S jest wielomianem stopnia trzeciego na przedziale [xj; xj+1], oznaczanym Sj, dlakażdego j =0; 1; :::; n Ą 1;
(b) S(xj) =f(xj) dla każdego j =0; 1; :::; n;
(c) Sj+1(xj+1) =Sj(xj+1) dla każdego j =0; 1; :::; n Ą 2;
0 0
(d) Sj+1(xj+1) =Sj(xj+1) dla każdego j =0; 1; :::; n Ą 2;
00 00
(e) Sj+1(xj+1) =Sj (xj+1) dla każdego j =0; 1; :::; n Ą 2;
(f) spełniony jest jedne z poniższych warunków brzegowych
(i) wolne: S00(x0) =S00(xn) =0, albo
(ii) zwiÄ…zane: S0(x0) =f0(x0) oraz S0(xn) =f0(xn).
UWAGA: Oba typy warunków brzegowych sa wystarczające do jednoznacznego wyznaczenia funkcji sklejanej. W
pierwszym przypadku, splajny krańcowe są po prostu zdegenerowane - mówimy wówczas o splajnie naturalnym. Drugi
typ oferruje jednak bardziej dokładne przybliżenie, gdyż zawiera w/
ecej informacji o funkcji, jednak potrzebujemy
wtedy albo wartości pochodnych w krańcach przedziału albo ich przybliżenia.
Aby skonstruować funkcję sklajaną stopnia trzeciego, trzeba obliczyćwspółczynniki wielomianów stopnia trzeciego
postaci:
Sj(x) =aj + bj(x Ą xj) +cj(x Ą xj)2 + dj(x Ą xj)3 dla każdego j =0; 1; :::; n Ą 2; (28)
wykorzystujÄ…c warunki (b)Ä„(f).
Wyprowadzenie wzorów pominiemy, jako że choć proste, to jednak stosunkowo czasochłonne. Jeśli przyjmiemy
oznaczenie
hj = xj+1 Ą xj dla każdego j =0; 1; :::; n Ą 1;
to współczynniki we wzorze (28) otrzymuje się następująco:
aj = f(xj) dla każdego j =0; 1; :::; n Ą 1; (29)
8
i dalej, poprzez rozwiązanie poniższego układu równań liniowych:
3 3
hjĄ1cjĄ1 +2(hjĄ1 + hj) cj + hjcj+1 = (aj+1 Ą aj) Ą (aj Ą ajĄ1) dla każdego j =1; 2; :::; n Ą 1;
hj hjĄ1
(30)
oraz
1 hj
bj = (aj+1 Ą aj) Ą (2cj + cj+1) dla każdego j =0; 1; :::; n Ą 1;
hj 3
cj+1 Ä„ cj
dj = dla każdego j =0; 1; :::; n Ą 1: (31)
3hj
Jedynym problemem, który tylko pozostaje jest kwestia rozwiązalności układu n Ą 1 równań liniowych (30) z n +1
niewiadomymi. W zależności od typu warunków brzegowych, otrzymuje się inne dwa dodatkowe równania ( zerowe
i n-te), a mianowicie: dla warunków wolnych
c0 =0 oraz cn =0;
i dla warunków związanych
3
2h0c0 + h0c1 = (a1 Ä„ a0) Ä„ 3f0(a)
h0
3
hnĄ1cnĄ1 +2hncn = 3f0(b) Ą (an Ą anĄ1):
hnĄ1
Można udowodnić, że oba tak skonstruowane układy rownań liniowych majądokładnie jedno rozwiązanie. UWAGA: (i)
Błąd interpolacji splajnami sześciennymi jest proporcjonalny do maksimum czwartej potęgi odległości między węzłami,
tzn jest rzędu O(maxj h4).
j
(ii) Warunki związane daja większą dokładność interpolacji, gdyż zawierają w/
ecej informacji o funkcji, ale jed-
nocześnie wymagają znajomości wartości pochodnej w krańcach przedziału.
3.5. Interpolacja Hermite a
Wielomiany interpolacyjne, które teraz rozważymy są uogólnieniem jednocześnie wielomianów Taylora i Lagrange a.
Niech bÄ™dÄ… dane: n +1 wÄ™złów x0; x1; :::; xn 2 [a; b] i n +1 nieujemnych liczb caÅ‚kowitych ®0; ®1; :::; ®n oraz niech
® =max f®0; :::; ®ng i f 2 C® [a; b] Wielomian interpolacyjny Hermite a H(x), przybliżajÄ…cy funkcjÄ™ f jest wielo-
Pn.
mianem stopnia co najwyżej m = ®i + n, taki że:
i=0
(s)
Hm (xt) =f(s)(xt) dla t =0; 1; :::; n oraz s =0; 1; :::; ®t. (32)
Przypomnijmy, że jeÅ›li n =0, to wielomian Hermite a redukuje siÄ™ do wielomianu Taylora stopnia ®0 w punkcie x0,
natomiast gdy ®t =0 dla wszystkich t =0; 1; :::; n, to wielomian Hermite a jest wielomianem Lagrange a opartym na
węzłach x0; x1; :::; xn.
Aby uproÅ›cić omówienie, rozważymy tylko sytuacjÄ™, gdy ®t = 1 dla wszystkich t = 0; 1; :::; n. Wówczas dla
wielomian Hermite a jest  zgodny z funkcja f, którąprzybliża w tym sensie, że pokrywająsięichwartości w węzłach
oraz wartości ich pochodnych. Zatem w punktach o współrzędnych (xt; f (xt)) wielomian i funkcja interpolowana
majÄ… te same styczne.
TWIERDZENIE 25. Jeśli f 2 C1 [a; b] i x0; x1; :::; xn 2 [a; b] są dane, to jedynym wielomianem spełniającym
warunki (32) dla ®t =1, t =0; 1; :::; n jest wielomian stopnia co najwyżej 2n +1dany wzorem:
n n
X X
^
H2n+1(x) = f(xt)Hn;t(x) + f0(xt)Hntj(x);
t=0 t=0
gdzie
^
Hn;t(x) =[1 Ä„ 2(x Ä„ xt)L0(xt)] L2(x) oraz Hn;t(x) =(x Ä„ xt)L2(x);
t t t
a Lt oznacza t-ty współczynnik wielomianu Lagrange a stopnia n zde
ðniowany wzorem (13) lub (13 ).
Ponadto, jeśli f 2 C(2n+2) [a; b], to
(x Ä„ x0)2 ::: (x Ä„ xn)2
f(x) Ä„ H2n+1(x) = f(2n+2)()
(2n +2)!
dla pewnego 2 (a; b).
9