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$$n$ przyjmującym w $n+1$$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)$$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}$$x_{0}$ i $x_{1}$$x_{1}$, dla których można utworzyć funkcję liniową, której wykres przechodzi przez punkty $(x_{0},f(x_{0}))$$(x_0,f(x_0))$ i $(x_{1},f(x_{1}))$$(x_1,f(x_1))$.

Ogólna metoda

Przykład interpolacji wielomianowej.

Metoda interpolacji polega na:

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

Interpretacja geometryczna – dla danych $n+1$$n+1$ punktów na wykresie szuka się wielomianu stopnia co najwyżej $n$$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})$$f(x_0)$ znajduje się wielomian, który w tym punkcie przyjmuje wartość $f(x_{0})$$f(x_0)$, a w pozostałych węzłach $x_{1},x_{2},\cdots ,x_{n}$$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})$$f(x_1)$, a w pozostałych węzłach $x_{0},x_{2},\cdots ,x_{n}$$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$$n$ wybiera się $n+1$$n+1$ punktów – $x_{0},x_{1},\cdots ,x_{n}$$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}}}$$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}}}$$\prod _{{j=0\land j\neq i}}^{n}{\frac {x-x_{j}}{x_{i}-x_{j}}}$ jest równy 1 dla $x$$x$ równego $x_{i}$$x_{i}$ (licznik i mianownik są równe), 0 zaś dla wszystkich innych $x_{j}$$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}}}$$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$$f$ we wszystkich punktach $x_{i}$$x_{i}$.

Dowód istnienia wielomianu interpolującego

Niech $x_{0},x_{1},\cdots ,x_{n}$$x_0,x_1,\cdots ,x_n$ będą węzłami interpolacji funkcji $\!f$$\!f$, takimi że znane są wartości $\!f(x_{0})=y_{0},f(x_{1})=y_{1},\cdots ,f(x_{n})=y_{n}$$\! 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}$$L_i(x)=\prod_{j = 0 \and j\ne 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}\}$$x\notin \{x_0,x_1,\cdots ,x_n\}$ $L_{i}(x)$$L_i(x)$ jest wielomianem stopnia $n$$n$ (mianownik jest liczbą, a licznik iloczynem $n$$n$ wyrazów postaci $(x-x_{j\ })$$(x-x_{j\ })$).

Gdy $x_{k}\in \{x_{0},x_{1},\cdots ,x_{n}\}$$x_k\in \{x_0,x_1,\cdots ,x_n\}$ i $k=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$$L_i(x_k)=L_i(x_i)=\prod_{j = 0 \and j\ne i}^n (\frac{x_i-x_j}{x_i-x_j})=\prod_{j = 0 \and j\ne i}^n (1) = 1$.

Gdy $x_{k}\in \{x_{0},x_{1},\cdots ,x_{n}\}$$x_k\in \{x_0,x_1,\cdots ,x_n\}$ i $k\not =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\ \$$L_i(x_k)=\prod_{j = 0 \and j\ne 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})$$(x_k-x_k)$).

Niech $\!W(x)$$\! W(x)$ będzie wielomianem stopnia co najwyżej $n$$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)$$\! 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}\}$$\! 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})$$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$$i$ są równe zeru (ponieważ dla $j\not =i\ \ L_{i}(x_{j})=0)$$j\not=i\ \ L_i(x_j)=0)$, składnik o indeksie $i$$i$ jest równy:

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

a więc

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

z czego wynika, że $\!W(x)$$\! W(x)$ jest wielomianem interpolującym funkcję $\!f(x)$$\! f(x)$ w punktach $x_{0},x_{1},\cdots ,x_{n}$$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)$$W_1(x)$ i $W_{2}(x)$$W_2(x)$ stopnia $n$$n$, przyjmujące w węzłach $\!x_{0},x_{1},\cdots ,x_{n}$$\! x_0,x_1,\cdots ,x_n$ takie same wartości.

Niech

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

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

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

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

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

to

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

co jest sprzeczne z założeniem, że $W_{1}(x)$$W_1(x)$ i $W_{2}(x)$$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)$$f(x)$ wielomianem $L_{n}(x)$$L_n(x)$. Idealna byłaby zależność:

$\!\lim _{n\to \infty }L_{n}(x)=f(x)$$\! \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$$n$, przybliżającego funkcję $f(x)$$f(x)$ w przedziale $[a,b]$$[a,b]$ na podstawie $n+1$$n+1$ węzłów, istnieje taka liczba $\!\xi$$\! \xi$ zależna od $x$$x$, że dla reszty interpolacji $\!r(x)$$\! r(x)$:

$\!{\frac {f^{(n+1)}(\xi )}{(n+1)!}}\cdot p_{n}(x)=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})$$p_n(x)=(x-x_0)(x-x_1)\cdots (x-x_n)$, a $\xi \in (a;b)$$\xi \in (a;b)$ jest liczbą zależną od $x$$x$.

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

Zobacz też

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