Mariusz PYRZ
SIMR (PW), Instytut Pojazdów
Metody numeryczne w mechanice
Interpolacja wielomianowa
5.
Problem interpolacji
Rozwa\
amy n+1 ró\
nych punktów x0, x1, & , xn (węzłów).
Znamy wartości pewnej funkcji y=f(x) w tych punktach (ale nie samą funkcję!)
y0 = f (x0), y1 = f (x1), ..., yn = f (xn)
Problem: Znalez
ć funkcję g(x) o znanej postaci (wielomian, funkcja
trygonometryczna, & ) która w węzłach xi przybiera wartości yi
g(xi ) = yi i = 0,1, ..., n
Zadaniem funkcji interpolacyjnej jest określenie przybli\
onych wartości
funkcji w punktach nie będących węzłami i oszacowanie błędu tego
przybli\
enia.
2
M.Pyrz Metody numeryczne w mechanice  Interpolacja wielomianowa 12.2011
Interpolacja
Zastosowania:
- Interpolacja wielomianowa jest wa\
nym etapem w budowaniu wielu metod
obliczeniowych;
- jest wykorzystywana w Metodzie Elementów Skończonych (słu\
ącej do rozwiązywania
równań ró\
niczkowych cząstkowych)
- interpolacja za pomocą funkcji sklejanych i spline ów szeroko stosowana w narzędziach
komputerowego wspomagania projektowania
3
M.Pyrz Metody numeryczne w mechanice  Interpolacja wielomianowa 12.2011
Interpolacja wielomianowa
n
Poszukujemy wielomianu
Pn (x) = a0 + a1x + a2x2 + ...+ anxn =
"a xi
i
i=0
tak aby
Pn(xi ) = yi i = 0,1, ..., n
2 n
a0 + a1x0 + a2x0 + ...+ anx0 = y0
układ n+1 równań liniowych
2 n
a1 + a1x1 + a2x1 +...+ anx1 = y1
o n+1 nieznanych
...
współczynnikach ai
2 n
a0 + a1xn + a2xn + ...+ anxn = yn
a0 + a1xn + a2xn + ...+ anxn = yn
Rozwiązanie jest jednoznaczne je\
eli macierz nie jest szczególna
(det [matrice] <>0)
2 n
�ł łł a0 y0
1 x0 x0 ... x0 �ł łł �ł łł
uwaga: macierze tego typu
�ł1 x1 x1 ... x1 śł
�ła śł �ł śł
2 n
staja się z
le uwarunkowane
y1
1
�ł śł
�ł śł �ł śł
wraz ze wzrostem n , nale\
y zatem
=
�ł... ... ... ... ... śł
�ł śł �ł śł
... ... unikać interpolowania za pomocą
wielomianów wy\
szego stopnia
�ł śł
�ła śł �ł śł
2 n
�ł
n
�ł �ł �ł �ł
�ł1 xn xn ... xn śł �ł śł �ł yn śł
�ł
4
M.Pyrz Metody numeryczne w mechanice  Interpolacja wielomianowa 12.2011
Interpolacja wielomianowa
Mo\
na wykazać, \
e wyznacznik macierz współczynników jest ro\
ny od zera
je\
eli
(xi - xj ) `" 0
"
0d" jZnaczy to inaczej, \
e je\
eli punkty xi są ró\
ne to istnieje jednoznacznie
określony wielomian interpolacyjny Pn taki, \
e
Pn (xi ) = yi i = 0,1, ..., n
Obliczone współczynniki ai (uzyskane rozwiązując otrzymany układ równań
liniowych) mo\
na wstawić do wyra\
enia
liniowych) mo\
na wstawić do wyra\
enia
n
Pn (x) = a0 + a1x + a2x2 + ...+ anxn =
"a xi
i
i=0
Po przegrupowaniu wyrazów otrzymujemy
n
Pn (x) = y0L0(x) + y1L1(x) + ...+ ynLn (x) =
"L (x) yi
i
i=0
Wielomiany Li są stopnia n i mają właściwość Li (xj ) = �ij
Jawna postać Li jest podana za pomocą wzorów Lagrange a
5
M.Pyrz Metody numeryczne w mechanice  Interpolacja wielomianowa 12.2011
Wielomiany Lagrange a
n
Pn (x) = y0L0(x) + y1L1(x) + ...+ ynLn (x) =
"L (x) yi
i
i=0
Wielomiany Lagrange a
Joseph-Louis Lagrange
n
(1736-1813)
�ł �ł
x - xj
Lk (x) =
�ł �ł
"�ł xk - xj �ł
j=0
�ł łł
j`"k
Wielomiany Li są stopnia n i mają właściwość
0 si i `" j
ńł
Li (xj ) =
�ł
ół1 si i = j
stąd
n
Pn(xj ) =
"L (xj ) yi =yi
i
i=0
6
M.Pyrz Metody numeryczne w mechanice  Interpolacja wielomianowa 12.2011
Wielomiany Lagrange a  błąd interpolacji
Załó\
my, \
e funkcja f(x) jest regularna i mo\
na obliczyć jej (n+1)-tą pochodną
Niech x0< x1< & < xn oznaczają punkty z dziedziny funkcji f(x)
Błąd interpolacji �n (x) = f (x) - Pn (x)
Mo\
na wykazać, \
e
"x "[x0, xn ], "�x = � (x)"[x0, xn ]
(n+1)
n
f (�x )
�n (x) =
"(x - xj )
(n +1)!
j=0
(n+1)
Mn+1 = sup f (x)
Je\
eli mo\
na znalez
ć górną granice pochodnej
x0 d"xd"xn
to mo\
na oszacować błąd aproksymacji
Mn+1 n
"x "[x0, xn] �n (x) d"
"(x - xj )
(n +1)!
j=0
7
M.Pyrz Metody numeryczne w mechanice  Interpolacja wielomianowa 12.2011
Interpolacja iteracyjna
Pomysł: Obliczyć przybli\
enie funkcji f(x) iteracyjnie stosując rosnącą liczbę
węzłów interpolacji (wówczas wzrasta dokładność) bez przeliczania całego
wielomianu
Cel:
Wyznaczyć wielomian interpolacyjny Pn(x) bazujący na (n+1) węzłach x0,x1,& ,xn
na podstawie wielomianu Pn-1(x) zbudowanego na n węzłach x0,x1,& , xn-1
P (x) - P (x) < �
Pk +1(x) - Pk (x) < �
W praktyce dołączyć nale\
y kryterium zatrzymania
W praktyce dołączyć nale\
y kryterium zatrzymania
Wielomian Newtona
Pn = a0 + a1(x - x0) + ...+ an (x - x0)...(x - xn-1)
Pn = Pn-1 + an (x - x0)...(x - xn-1)
Procedura rekurencyjna pozwala na określenie współczynników
ai=f [x0,x1,& ,xi ], zwanych ilorazami ró\
nicowymi.
8
M.Pyrz Metody numeryczne w mechanice  Interpolacja wielomianowa 12.2011
Ilorazy ró\
nicowe
Rekurencyjna definicja ilorazów ró\
nicowych (pierwszego rzędu, drugiego rzędu, & )
f [xi ]- f [xj ] f [xi, xj ]- f [xj , xk ]
f [xi ] = f (xi ) f [xi, xj ] = f [xi, xj , xk ] =
xi - xj xi - xk
f [xn, xn-1,..., x1] - f [xn-1,..., x1, x0]
... f [xn, xn-1,..., x1, x0] =
xn - x0
f [x0] f [x1] f [x2] f [x3] ...
� � � � � �
Rekurencyjne obliczenia
f [x1, x0] f [x2, x1] f [x3, x2]
Ilorazów ró\
nicowych
� � � �
f [x2, x1, x0] f [x3, x2, x1]
� �
f [x3, x2, x1, x0]
9
M.Pyrz Metody numeryczne w mechanice  Interpolacja wielomianowa 12.2011
Wielomiany Newton a
Pn = a0 + a1(x - x0) + ...+ an (x - x0)...(x - xn-1)
W którym występują następujące współczynniki
a0 = f [x0] = f (x0) a1 = f [x1, x0] a2 = f [x2, x1, x0]
Sir Isaac Newton
(1643-1727)
... ai = f [xi, xi-1,..., x1, x0] ...
... an = f [xn, xn-1,..., x1, x0]
Błąd interpolacji
�n (x) = f (x) - Pn (x)
Mn+1 n
"x "[x0, xn] �n (x) d"
"(x - xj )
(n +1)!
j=0
(n+1)
Mn+1 = sup f (x)
x0 d"xd"xn
10
M.Pyrz Metody numeryczne w mechanice  Interpolacja wielomianowa 12.2011
Pozostałe zagadnienia interpolacji
Interpolacja funkcjami sklejanymi
Funkcje i powierzchnie Bezier Spline y
11
M.Pyrz Metody numeryczne w mechanice  Interpolacja wielomianowa 12.2011