str 1

W3

Interpolacja

Sformułowanie zadania interpolacyjnego

Danych jest n+1 różnych punktów x0, x1, ... , xn z przedziału [a,b], które nazywamy wę złami interpolacji, oraz wartości pewnej funkcji y = f(x) w tych punktach y0 = f(x0) , y1 = f(x1) , .... , yn = f(xn).

Zadanie interpolacji polega na znalezieniu funkcji F, zwanej funkcją interpolują cą, która w węzłach xi , i = 0, 1, ... ,n , pokrywa się z funkcją f F(xi) = f(xi) dla i = 0, 1, ... , n .

Rozważamy zadanie interpolacji liniowej, tj. zadanie w którym funkcja interpolująca przedstawiana jest w postaci kombinacji liniowej

n

F(x) =

aj⋅φj(x)

∑

j = 0

gdzie φj , j = 0,1, ... ,n są funkcjami określonymi na przedziale [a,b]. Poszukiwanymi są tutaj współczynniki kombinacji liniowej aj , j = 0, 1, ... ,n. Pytania o istnienie i jednoznaczność funkcji interpolującej sprowadzają się do tego, czy układ równań liniowych n

a

∑ j⋅φj(xi) = yi dla i = 0,1, .... , n (*) j = 0

ma rozwiązanie oraz, czy to rozwiązanie jest jedyne.

 φ0



(x0) φ1(x0) . . φn(x0) 

 φ



0(x1) φ1(x1) . . φn(x1)

Oznaczymy A = 





.

.

. .

.







 φ0(xn) φ1(xn) . . φn(xn) 

Odpowiedź na powyższe pytania zależy od wyznacznika macierzy A. Jeżeli det(A) ≠ 0 , to układ (*) ma jednoznaczne rozwiązanie. Znalezienie tego rozwiązania daje funkcję interpolującą.

Interpolacja Lagrange'a

Zadanie intepolacyjne Lagrange'a polega na znalezieniu wielomianu Ln , stopnia nie wyższego niż n, spełniającego warunki interpolacji

Ln(xi) = f(xi) dla i = 0,1, ... ,n .

Wielomian Ln nazywamy wielomianem interpolacyjnym Lagrange'a funkcji f opartym na wę złach x0, x1, ... , xn .

str 2

W3

TWIERDZENIE. Zadanie interpolacyjne Lagrange'a na jednoznaczne rozwiązanie.

Wielomian interpolacyjny Ln można przedstawić w postaci

n

Ln(x) =

aj⋅φj(x)

∑

,

j = 0

gdzie układ funkcji φ0, φ1, ... , φn stanowi bazę przestrzeni Wn (przestrzeni wielomianów stopnia nie wyższego niż n).

Rozpatrzymy

(a) bazę naturalną : 1, x , x2, ... , x n

j−1

(b) bazę wielomianów Newtona : p0(x) = 1, pj(x) =

(x − xk)

∏

, j = 1, ... , n

k = 0

W przypadku (a) mamy do czynienia z postacią naturalną wielomianu interpolacyjnego n

j

Ln(x) =

a

∑ j⋅x

j = 0

W przypadku (b) współczynniki

a0 = y0 oraz aj = f 0,1, ... ,j , j = 1, ... ,n

są ilorazami róż nicowymi określonymi poniżej.

Wyrażenia

y1 − y0

yn − yn−1

f 0 , 1 =

, . . . . , f n−1 , n =

x1 − x0

xn − xn−1

nazywamy ilorazami róż nicowymi 1 -go rzę du. Analogicznie definiujemy ilorazy róż nicowe 2 -go rzę du f 1 , 2 − f0 , 1

f n−1 , n − fn−2 , n−1

f 0 , 1 , 2 =

, . . . . f n−2 , n−1 , n =

x2 − x0

xn − xn−2

Ogólnie iloraz róż nicowy rzę du k tworzymy z ilorazów różnicowych rzędu k-1 za pomoca wzoru rekurencyjnego

f i+1 , .... , i+k − fi , .... , i+k−1

f i , i+1 , .... , i+k =

xi+k − xi

Wobec tego

Ln(x) = y0 + f 0, 1 p1(x) + f 0, 1, 2 p2(x) + .... + f 0,1, ... , n pn(x) Jest to tzw. postać Newtona wielomianu interpolacyjnego.

str 3

W3

Dla n =1 (2 węzły) L

=

+

⋅( − )

1(x)

y0

f 0 , 1 x x0

Dla n =2 (3 węzły) L

=

+

⋅( − ) +

⋅( − )⋅( − )

2(x)

y0

f 0 , 1 x x0

f 0 , 1 , 2 x x0

x

x1

Algorytm obliczania n-tego ilorazu różnicowego można zapisać w postaci tablicy trójkątnej

 x0

y0







x

 1

y1

f 0 , 1







x2

y2

f 1 , 2

f 0 , 1 , 2







.

.

.

.

.







.

.

.

.

. . .





xn−1 yn−1 fn−2 ,n−1 fn−3 ,n−2 ,n−1 . . . .







x

 n

yn

f n−1 , n

f n−2 , n−1 , n

. . . . f 0 , 1 , .. , n 

W celu oszacowania błę du interpolacji możemy posłużyć się twierdzeniem TWIERDZENIE. Jeżeli funkcja f jest klasy Cn+1([a,b]), to dla a ≤ x ≤ b Mn+1

f (x) − Ln(x) ≤

⋅ (x − x0)⋅(x − x1)⋅....⋅(x − xn)

(n + 1)!

gdzie M

= max

n+1

a x

≤ b

≤ | f (n+1) (x)|.

W sformułowanym zadaniu interpolacyjnym wyznaczamy wielomian w oparciu o dane wartości funkcji f w (n+1) różnych węzłach. Powstaje pytanie, czy wielomian ten będzie coraz lepiej przybliżał funkcję f wraz ze zwiększeniem liczby węzłów ?

Oczywiście, większa liczba zmierzonych wartości funkcji zawiera w sobie dokładniejszą informację o tej funkcji.

W przypadku stosowania wielomianów jako funkcji interpolujących, często występuje zjawisko pogarszania się przybliżenia przy zwiększaniu się liczby węzłów interpolacyjnych.

Dokładniej oznacza to, że ciąg ( Ln ) wielomianów interpolacyjnych nie będzie zbieżny do funkcji f na przedziale [a,b]. Problemy te nie występują, gdy do interpolacji będziemy stosować funkcje kawałkami "sklejane" z wielomianów niskich stopni.