Metody Numeryczne
Wykład 4
Interpolacja
Iwona Wróbel
[e-mail]
Metody Numeryczne IL, Wykład 4  p.1/11
Interpolacja
Sformułowanie problemu:
Mając dane
xi " R, dla i = 0, 1, . . . , n (węzły interpolacji)
fi = f(xi), gdzie f jest funkcją interpolowaną (nieznaną funkcją,
której wartości są znane tylko w skończonej liczbie punktów)
znalez
ć funkcję interpolującą p(x) taką, że
p(xi) = f(xi), dla i = 0, 1, . . . , n.
Funkcja p(x) może mieć dowolną postać, w szczególności może być
wielomianem lub kawałkami wielomianem.
Metody Numeryczne IL, Wykład 4  p.2/11
Interpolacja wielomianowa
Funkcja interpolująca p(x) jest wielomianem.
Niech n będzie przestrzenią wielomianów stopnia nie wyższego niż
n, czyli wielomianów postaci a0 + a1x + . . . + anxn.
Metody Numeryczne IL, Wykład 4  p.3/11
Interpolacja wielomianowa
Funkcja interpolująca p(x) jest wielomianem.
Niech n będzie przestrzenią wielomianów stopnia nie wyższego niż
n, czyli wielomianów postaci a0 + a1x + . . . + anxn.
Twierdzenie. Jeśli węzły x0, x1, . . . , xn są parami różne (xi = xj dla

i = j, i, j = 0, . . . , n), to dla dowolnych wartości fi = f(xi) istnieje

dokładnie jeden wielomian pn " n, taki, że
pn(xi) = f(xi), dla i = 0, 1, . . . , n.
Metody Numeryczne IL, Wykład 4  p.3/11
Postać Lagrange a
Wielomian interpolacyjny jest wyznaczony jednoznacznie, ale można
go przedstawić na różne sposoby (w różnych bazach) i wyznaczać
różnymi algorytmami.
Postać Lagrange a:
n
pn(x) = fili(x),
i=0
gdzie
n
x - xj
li(x) = .
xi - xj
j=0
j =i
Wielomian interpolacyjny pn(x) przedstawiony jest w bazie
{l0(x), . . . , ln(x)}.
Metody Numeryczne IL, Wykład 4  p.4/11
Warunek interpolacyjny pn(xk) = f(xk) jest spełniony. Mamy
n
xk - xj
li(xk) = =
xi - xj
j=0
j =i
Metody Numeryczne IL, Wykład 4  p.5/11
Warunek interpolacyjny pn(xk) = f(xk) jest spełniony. Mamy
n
xk - xj 0 gdy k = i,

li(xk) = =
xi - xj
1 gdy k = i,
j=0
j =i
Metody Numeryczne IL, Wykład 4  p.5/11
Warunek interpolacyjny pn(xk) = f(xk) jest spełniony. Mamy
n
xk - xj 0 gdy k = i,

li(xk) = =
xi - xj
1 gdy k = i,
j=0
j =i
a stąd
n
pn(xk) = fili(xk) = fk.
i=0
Metody Numeryczne IL, Wykład 4  p.5/11
Postać Newton a
Postać Newtona wielomianu interpolacyjnego:
pn(x) = c0 + c1(x-x0) + c2(x-x0)(x-x1) + . . . + cn(x-x0). . .(x-xn-1).
Metody Numeryczne IL, Wykład 4  p.6/11
Postać Newton a
Postać Newtona wielomianu interpolacyjnego:
pn(x) = c0 + c1(x-x0) + c2(x-x0)(x-x1) + . . . + cn(x-x0). . .(x-xn-1).
Wielomian pn(x) jest przedstawiony w bazie
{1, x - x0, (x - x0)(x - x1), . . . , (x - x0). . .(x - xn-1)}.
Metody Numeryczne IL, Wykład 4  p.6/11
Postać Newton a
Postać Newtona wielomianu interpolacyjnego:
pn(x) = c0 + c1(x-x0) + c2(x-x0)(x-x1) + . . . + cn(x-x0). . .(x-xn-1).
Wielomian pn(x) jest przedstawiony w bazie
{1, x - x0, (x - x0)(x - x1), . . . , (x - x0). . .(x - xn-1)}.
Mamy: pn(x0) = c0 = f(x0), Pozostałe współczynniki c1, . . . , cn:
c1 = f0,1, c2 = f0,1,2, . . ., cn = f0,1,...,n, gdzie f0,1,...,n dla k = 1, . . . , n
są ilorazami różnicowymi.
Metody Numeryczne IL, Wykład 4  p.6/11
Ilorazy różnicowe pierwszego rzędu:
f(xj+1) - f(xj)
fj,j+1 = dla j = 0, . . . , n - 1.
xj+1 - xj
Metody Numeryczne IL, Wykład 4  p.7/11
Ilorazy różnicowe pierwszego rzędu:
f(xj+1) - f(xj)
fj,j+1 = dla j = 0, . . . , n - 1.
xj+1 - xj
Ilorazy różnicowe drugiego rzędu:
fj+1,j+2 - fj,j+1
fj,j+1,j+2 = dla j = 0, . . . , n - 2.
xj+2 - xj
Metody Numeryczne IL, Wykład 4  p.7/11
Ilorazy różnicowe pierwszego rzędu:
f(xj+1) - f(xj)
fj,j+1 = dla j = 0, . . . , n - 1.
xj+1 - xj
Ilorazy różnicowe drugiego rzędu:
fj+1,j+2 - fj,j+1
fj,j+1,j+2 = dla j = 0, . . . , n - 2.
xj+2 - xj
Ilorazy różnicowe k-tego rzędu:
fj+1,...,j+k - fj,...,j+k-1
fj,j+1,...,j+k =
xj+k - xj
dla j = 0, . . . , n - k.
Metody Numeryczne IL, Wykład 4  p.7/11
Schemat ilorazów różnicowych
Ilorazy różnicowe wyznacza się na podstawie następującej tabeli:
x0 f0
f0,1
x1 f1 f0,1,2
f1,2
x2 f2 . . . . . . f0,...,n
. . .
fn-2,n-1,n
. . . . . .
fn-1,n
xn fn
Metody Numeryczne IL, Wykład 4  p.8/11
Oszacowanie błędu interpolacji
Twierdzenie. Jeśli f " Cn+1([a, b]) oraz pn " n jest wielomianem
interpolacyjnym dla f opartym na parami różnych węzłach
x0, . . . , xn " [a, b], to dla każdego x " [a, b] zachodzi oszacowanie
Mn+1
|f(x) - pn(x)| d" |(x - x0)(x - x1) . . . (x - xn)|,
(n + 1)!
gdzie
Mn+1 = max |f(n+1)(x)|.
x"[a,b]
Metody Numeryczne IL, Wykład 4  p.9/11
Oszacowanie błędu interpolacji
Twierdzenie. Jeśli f " Cn+1([a, b]) oraz pn " n jest wielomianem
interpolacyjnym dla f opartym na parami różnych węzłach
x0, . . . , xn " [a, b], to dla każdego x " [a, b] zachodzi oszacowanie
Mn+1
|f(x) - pn(x)| d" |(x - x0)(x - x1) . . . (x - xn)|,
(n + 1)!
gdzie
Mn+1 = max |f(n+1)(x)|.
x"[a,b]
Uwaga. W przypadku, gdy funkcja f jest nieznana (np. gdy są to dane
z pomiaru, sporządzonego w skończonej liczbie punktów), nie da się
oszacować Mn+1.
Metody Numeryczne IL, Wykład 4  p.9/11
Oszacowanie błędu interpolacji
Twierdzenie. Jeśli f " Cn+1([a, b]) oraz pn " n jest wielomianem
interpolacyjnym dla f opartym na parami różnych węzłach
x0, . . . , xn " [a, b], to dla każdego x " [a, b] zachodzi oszacowanie
Mn+1
|f(x) - pn(x)| d" |(x - x0)(x - x1) . . . (x - xn)|,
(n + 1)!
gdzie
Mn+1 = max |f(n+1)(x)|.
x"[a,b]
Uwaga. W przypadku, gdy funkcja f jest nieznana (np. gdy są to dane
z pomiaru, sporządzonego w skończonej liczbie punktów), nie da się
oszacować Mn+1.
Można jednak tak dobrać węzły x1, . . . , xn, aby zminimalizować
wielkość
rn = max |(x - x0)(x - x1) . . . (x - xn)|.
x"[a,b]
Metody Numeryczne IL, Wykład 4  p.9/11
Wielomiany i węzły Czebyszewa
Zrobił to P. Czebyszew (w 1857 r.). Dowiódł on, że dla [a, b] = [-1, 1]
wartość rn osiąga minimum, gdy
2i + 1
xi = cos Ą i = 0, 1, . . . , n.
2n + 2
Punkty te noszą nazwę węzłów Czebyszewa. Są one pierwiastkami
wielomianu
Tn+1(x) = cos((n + 1) arccos x),
zwanego wielomianem Czebyszewa.
Wielomiany Czebyszewa spełniają związek rekurencyjny
T0(x) = 1, T1(x) = x, Tk(x) = 2xTk-1(x) - Tk-2(x), k = 2, 3, . . ..
Metody Numeryczne IL, Wykład 4  p.10/11
Wielomiany i węzły Czebyszewa
Mamy:
max |Tn(x)| = 1
x"[-1,1]
oraz
(x - x0)(x - x1) . . . (x - xn) = 2-nTn+1.
Dla węzłów Czebyszewa:
Mn+1
|f(x) - pn(x)| d"
2n(n + 1)!
Węzły Czebyszewa w dowolnym przedziale [a, b]:
a + b b - a 2i + 1
xi = - cos Ą i = 0, 1, . . . , n.
2 2 2n + 2
Metody Numeryczne IL, Wykład 4  p.11/11