Interpolacja wielomianowa

Interpolacja wielomianowa, nazywana też interpolacją Lagrange’a, od nazwiska pioniera badań nad interpolacją Josepha Lagrange’a, lub po prostu interpolacją – metoda numeryczna 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},\dots ,x_{n}$ należących do dziedziny $f,$ dla których znane są wartości $y_{0}=f(x_{0}),y_{1}=f(x_{1}),\dots ,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},\dots 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 następujący 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},\dots ,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},\dots ,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},\dots ,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},\dots ,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},\dots ,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\dots ,n},$

taką że dla $x\notin \{x_{0},x_{1},\dots ,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},\dots ,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},\dots ,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 \ldots \cdot (x_{k}-x_{k})\cdot \ldots \cdot (x_{k}-x_{n})}{(x_{i}-x_{0})\cdot (x_{i}-x_{1})\cdot \ldots \cdot (x_{i}-x_{i-1})\cdot (x_{i}-x_{i+1})\cdot \ldots \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},\dots ,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},\dots ,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},\dots ,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,\dots ,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})\ldots (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ć Hermite’a wielomianu
• postać Newtona wielomianu