str 1
W5
Interpolacja
Interpolacja Lagrange'a (uzupełnienia)
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 .
TWIERDZENIE. Zadanie interpolacyjne Lagrange'a na jednoznaczne rozwiązanie.
DOWÓD. Szukany wielomian zapiszemy w postaci n
j
L
=
⋅ (**) n(x)
a
∑ j x
j = 0
Zadanie interpolacji
Ln(xi) = yi dla i = 0, 1, ... ,n
prowadzi do układu n+1 równań liniowych Va = y z 1
x
( )2
( )n
0
x0
. .
x0
a0
y0
1 x
(x )2 . . (x )n
a
1
y
1
V
1
1
1
=
, a =
, y =
.
.
.
.
. .
.
.
.
a
y
1
x ( )2
( )n
n
n
n
xn
. .
xn
Macierz Vandermonde'a jest macierzą nieosobliwą dla układu róŜnych węzłów. Zatem układ Va = y ma dokładnie jedno rozwiązanie. Istnieje wielomian postaci (**) i jest on wyznaczony jednoznacznie.
Wielomian interpolacyjny Ln moŜna przedstawić w postaci n
L
=
⋅φ
,
n(x)
a j j(x)
∑
j = 0
gdzie układ funkcji φ , φ , ... , φ stanowi bazę przestrzeni W (przestrzeni wielomianów stopnia 0
1
n
n
nie wyŜszego niŜ n).
Rozpatrzymy bazę wielomianów tworzących :
n
(x − x )
k
l
, j = 0,1, ... ,n
j(x) = ∏
(x − )
j
xk
k = 0(k≠ j)
Z2007/8
str 2
W5
x − x
x − x
Dla n = 1 (2 w
1
0
ęzły) l0(x) =
l1(x) =
x −
−
0
x1
x1
x0
Z
a
u
w
a
Ŝ
m
y ,Ŝe aj = yj , j = 0, 1, ... ,n , więc
n
L
=
⋅
n(x)
yj lj(x)
∑
j = 0
Jest to tzw. postać Lagrange'a wielomianu interpolacyjnego.
x − x
x − x
Dla n =1 (2 w
1
0
ęzły) L
=
⋅ +
⋅
1(x)
y0
y1
x −
−
0
x1
x1
x0
Dla n =2 (3 węzły)
(x − x )⋅( − )
( − )⋅( − )
( − )⋅( − )
1
x
x2
x
x0 x
x2
x
x0 x
x1
L
=
⋅ +
⋅ +
⋅
2(x)
(
y0
y1
y2
x −
)⋅( − )
( − )⋅( − )
( − )⋅( − )
0
x1
x0
x2
x1
x0 x1
x2
x2
x0
x2
x1
Zadanie. Znaleźć wielomian interpolacyjny Lagrange'a dla funkcji określonej tablicą wartości f(0) = 1, f(2) = 3, f(3) = 2.
Postać Newtona
0 1
2 3 1
2
L
=
+ ⋅( −
− ⋅( − ⋅( −
2(x)
1
1 x
0)
x
0) x
2)
3
3 2
1
−
2
−
3
Postać Lagrange'a
(x − 2)⋅(x − 3)
( − )⋅(x − 3)
(x − 0)⋅(x − 2)
L
=
⋅
x
0
+
⋅ +
⋅
2(x)
1
3
2
(0 − 2)⋅(0 − 3)
(2 − 0)⋅(2 − 3)
(3 − 0)⋅(3 − 2)
W praktycznych obliczeniach najczęściej stosuje się postać Newtona. W tym przypadku łatwo oblicza się wartości wielomianu w dowolnym punkcie (wystarczy trochę zmodyfikować schemat Hornera).
Ponadto, w łatwy sposób, moŜna dołączyć dodatkowy węzeł, gdyŜ
Ln(x) = Ln-1(x) + f 0, 1, ... , n pn(x),
gdzie Ln-1 jest wielomianem interpolacyjnym funkcji f opartym na węzłach x0, x1, ... , xn-1.
Otrzymywanie postaci naturalnej poprzez rozwiązywanie układu równań z macierzą Vandermonde'a nie jest zalecana ze względu na duŜy koszt i złe uwarunkowanie tej macierzy. Natomiast postać Lagrande'a ma duŜe znaczenie teoretyczne. Jest ona wykorzystywana przy wyprowadzeniu wielu formuł obliczeniowych opartych na wielomianowych przybliŜeniach, np. wielu wzorów całkowania numerycznego.