Interpolacja wielomianowa

Interpolacja wielomianowa, nazywana też interpolacją Lagrange'a, od nazwiska pioniera badań nad interpolacją Josepha Lagrange'a, lub po prostu interpolacją jest metodą numeryczną przybliżania funkcji tzw. wielomianem Lagrange'a stopnia $n$ przyjmującym w $n+1$ punktach, zwanych węzłami interpolacji, wartości takie same jak przybliżana funkcja.

Interpolacja jest często stosowana w naukach doświadczalnych, gdzie dysponuje się zazwyczaj skończoną liczbą danych do określenia zależności między wielkościami.

Zgodnie z twierdzeniem Weierstrassa dowolną funkcję $y=f(x)$, ciągłą na przedziale domkniętym, można dowolnie przybliżyć za pomocą wielomianu odpowiednio wysokiego stopnia.

Interpolacja liniowa

Interpolacja liniowa

Jest przypadkiem interpolacji wielomianowej dla dwóch punktów pomiarowych $x_{0}$ i $x_{1}$, dla których można utworzyć funkcję liniową, której wykres przechodzi przez punkty $(x_{0},f(x_{0}))$ i $(x_{1},f(x_{1}))$.

Ogólna metoda

Przykład interpolacji wielomianowej.

Metoda interpolacji polega na:

1. wybraniu $n+1$ punktów $x_{0},x_{1},\cdots ,x_{n}$ należących do dziedziny $f$, dla których znane są wartości $y_{0}=f(x_{0}),y_{1}=f(x_{1}),\cdots ,y_{n}=f(x_{n})$
2. znalezieniu wielomianu $W(x)$ stopnia co najwyżej $n$ takiego, że $W(x_{0})=y_{0},W(x_{1})=y_{1},\cdots W(x_{n})=y_{n}$.

Interpretacja geometryczna – dla danych $n+1$ punktów na wykresie szuka się wielomianu stopnia co najwyżej $n$, którego wykres przechodzi przez dane punkty

Znajdowanie odpowiedniego wielomianu

Wielomian przyjmujący zadane wartości w konkretnych punktach można zbudować w ten sposób:

1. Dla pierwszego węzła o wartości $f(x_{0})$ znajduje się wielomian, który w tym punkcie przyjmuje wartość $f(x_{0})$, a w pozostałych węzłach $x_{1},x_{2},\cdots ,x_{n}$ wartość zero.
2. Dla kolejnego węzła znajduje się podobny wielomian, który w drugim węźle przyjmuje wartość $f(x_{1})$, a w pozostałych węzłach $x_{0},x_{2},\cdots ,x_{n}$ wartość zero.
3. Dodaje się wartość ostatnio obliczonego wielomianu do wartości poprzedniego.
4. Dla każdego z pozostałych węzłów znajduje się podobny wielomian, za każdym razem dodając go do wielomianu wynikowego.
5. Wielomian będący sumą wielomianów obliczonych dla poszczególnych węzłów jest wielomianem interpolującym.

Dowód ostatniego punktu i dokładny sposób tworzenia poszczególnych wielomianów opisany jest poniżej w dowodzie istnienia wielomianu interpolującego będącego podstawą algorytmu odnajdowania tego wielomianu.

Wielomian Lagrange'a

Postać Lagrange'a wielomianu to jedna z metod przedstawiania wielomianu, wykorzystywana często w zagadnieniach interpolacji. Dla wielomianu stopnia $n$ wybiera się $n+1$ punktów – $x_{0},x_{1},\cdots ,x_{n}$ i wielomian ma postać:

$w(x)=\sum _{i=0}^{n}y_{i}\prod _{j=0\land j\neq i}^{n}{\frac {x-x_{j}}{x_{i}-x_{j}}}$.

Ponieważ $\prod _{j=0\land j\neq i}^{n}{\frac {x-x_{j}}{x_{i}-x_{j}}}$ jest równy 1 dla $x$ równego $x_{i}$ (licznik i mianownik są równe), 0 zaś dla wszystkich innych $x_{j}$ (licznik jest równy zero), można łatwo za pomocą postaci Lagrange'a interpolować dowolną funkcję:

$L_{f}(x)=\sum _{i=0}^{n}f(x_{i})\prod _{j=0\land j\neq i}^{n}{\frac {x-x_{j}}{x_{i}-x_{j}}}$

Wielomian ten będzie się zgadzał z funkcją $f$ we wszystkich punktach $x_{i}$.

Dowód istnienia wielomianu interpolującego

Niech $x_{0},x_{1},\cdots ,x_{n}$ będą węzłami interpolacji funkcji $\!f$, takimi że znane są wartości $\!f(x_{0})=y_{0},f(x_{1})=y_{1},\cdots ,f(x_{n})=y_{n}$
Można zdefiniować funkcję:

$L_{i}(x)=\prod _{j=0\land j\neq i}^{n}{\frac {x-x_{j}}{x_{i}-x_{j}}},\quad i\in {0,1\cdots ,n}$,

taką że dla $x\notin \{x_{0},x_{1},\cdots ,x_{n}\}$ $L_{i}(x)$ jest wielomianem stopnia $n$ (mianownik jest liczbą, a licznik iloczynem $n$ wyrazów postaci $(x-x_{j\ })$).

Gdy $x_{k}\in \{x_{0},x_{1},\cdots ,x_{n}\}$ i $k=i$:

$L_{i}(x_{k})=L_{i}(x_{i})=\prod _{j=0\land j\neq i}^{n}({\frac {x_{i}-x_{j}}{x_{i}-x_{j}}})=\prod _{j=0\land j\neq i}^{n}(1)=1$.

Gdy $x_{k}\in \{x_{0},x_{1},\cdots ,x_{n}\}$ i $k\not =i$:

$L_{i}(x_{k})=\prod _{j=0\land j\neq i}^{n}{\frac {x_{k}-x_{j}}{x_{i}-x_{j}}}\ ={\frac {(x_{k}-x_{0})\cdot (x_{k}-x_{1})\cdot \cdots \cdot (x_{k}-x_{k})\cdot \cdots \cdot (x_{k}-x_{n})}{(x_{i}-x_{0})\cdot (x_{i}-x_{1})\cdot \cdots \cdot (x_{i}-x_{i-1})\cdot (x_{i}-x_{i+1})\cdot \cdots \cdot (x_{i}-x_{n})}}\ =\ 0\ \$

(licznik = 0 ponieważ występuje element $(x_{k}-x_{k})$).

Niech $\!W(x)$ będzie wielomianem stopnia co najwyżej $n$, określonym jako:

$\!W(x)=y_{0}\cdot L_{0}(x)+y_{1}\cdot L_{1}(x)+y_{2}\cdot L_{2}(x)+\cdots +y_{n}\cdot L_{n}(x)$.

Dla $\!x_{i}\in \{x_{0},x_{1},\cdots ,x_{n}\}$:

$W(x_{i})=y_{0}\cdot L_{0}(x_{i})+y_{1}\cdot L_{1}(x_{i})+\cdots +y_{i}\cdot L_{i}(x_{i})+\cdots +y_{n}\cdot L_{n}(x_{i})$.

Wszystkie składniki sumy o indeksach różnych od $i$ są równe zeru (ponieważ dla $j\not =i\ \ L_{i}(x_{j})=0)$, składnik o indeksie $i$ jest równy:

$L_{i}(x_{i})\cdot y_{i}=1\cdot y_{i}=y_{i}$,

a więc

$\!W(x_{i})=y_{i}$

z czego wynika, że $\!W(x)$ jest wielomianem interpolującym funkcję $\!f(x)$ w punktach $x_{0},x_{1},\cdots ,x_{n}$.

Jednoznaczność interpolacji wielomianowej

Dowód

Zakłada się, że istnieją dwa tożsamościowo różne wielomiany $W_{1}(x)$ i $W_{2}(x)$ stopnia $n$, przyjmujące w węzłach $\!x_{0},x_{1},\cdots ,x_{n}$ takie same wartości.

Niech

$\!W_{3}(x)=W_{1}(x)-W_{2}(x)$

będzie wielomianem. Jest on stopnia co najwyżej $n$ (co wynika z własności odejmowania wielomianów).

Ponieważ $W_{1}(x)$ i $W_{2}(x)$ w węzłach $x_{i}:i\in 0,1,\cdots ,n$ interpolują tę samą funkcję, to $W_{1}(x_{i})=W_{2}(x_{i})$, a więc $W_{3}(x_{i})=0$ (węzły interpolacji są pierwiastkami $W_{3}(x)$).(*)

Ale każdy niezerowy wielomian stopnia $n$ ma co najwyżej $n$ pierwiastków rzeczywistych, a ponieważ z (*) wiadomo, że $\!W_{3}(x)$ ma $n+1$ pierwiastków, to $W_{3}(x)$ musi być wielomianem tożsamościowo równym zeru, a ponieważ:

$\!W_{3}(x)\ =\ W_{1}(x)-W_{2}(x)\ =\ 0$

to

$\!W_{1}(x)\ =\ W_{2}(x)$

co jest sprzeczne z założeniem, że $W_{1}(x)$ i $W_{2}(x)$ są różne.

Błąd interpolacji

Dość naturalne wydaje się przyjęcie, że zwiększenie liczby węzłów interpolacji (lub stopnia wielomianu interpolacyjnego) pociąga za sobą coraz lepsze przybliżenie funkcji $f(x)$ wielomianem $L_{n}(x)$. Idealna byłaby zależność:

$\!\lim _{n\to \infty }L_{n}(x)=f(x)$,

tj. dla coraz większej liczby węzłów wielomian interpolacyjny staje się „coraz bardziej podobny” do interpolowanej funkcji.

Dla węzłów równo odległych tak być nie musi → efekt Rungego.

Można dowieść, że dla każdego wielomianu interpolacyjnego stopnia $n$, przybliżającego funkcję $f(x)$ w przedziale $[a,b]$ na podstawie $n+1$ węzłów, istnieje taka liczba $\!\xi$ zależna od $x$, że dla reszty interpolacji $\!r(x)$:

$\!{\frac {f^{(n+1)}(\xi )}{(n+1)!}}\cdot p_{n}(x)=r(x)$,

gdzie $p_{n}(x)=(x-x_{0})(x-x_{1})\cdots (x-x_{n})$, a $\xi \in (a;b)$ jest liczbą zależną od $x$.

Do oszacowania z góry wartości $r(x)$ można posłużyć się wielomianami Czebyszewa stopnia $n+1$ do oszacowania wartości $p_{n}(x)$ dla $x\in [-1,1]$. Dla przedziału $[a,b]$ wystarczy dokonać przeskalowania wielomianu $p_{n}(x)$

Zobacz też

• postać Newtona wielomianu
• postać Lagrange'a wielomianu
• postać Hermite'a wielomianu