Interpolacja wielomianowa

Interpolacja wielomianowa, nazywana też interpolacją Lagrange'a, od nazwiska pioniera badań nad interpolacją Josepha Lagrange'a, 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.

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

Spis treści

1 Ogólna metoda
2 Dowód istnienia wielomianu interpolującego
3 Jednoznaczność interpolacji wielomianowej
4 Błąd interpolacji
5 Zobacz też

[edytuj] Ogólna metoda

wybieramy $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)$ - są to tzw. węzły interpolacji
znajdujemy wielomian W(x) stopnia n+1 taki, że $W(x_0)=y_0,W(x_1)=y_1,\cdots ,W(x_n)=y_n$ .

[edytuj] 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 \and j\ne i}^n \frac{x-x_j}{x_i-x_j}\ \ \ \ \$ , $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\ })$ )

$x\in \{x_0,x_1,\cdots ,x_n\}, k\not=i$ :

$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$

$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 (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 (x_i-x_n) }\ =\ 0\ \$

Niech $\! W(x)$ będzie wielomianem stopnia $n + 1$ , 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 ideksach różnych od i są równe zeru, składnik i indeksie i jest równy:

$L_i(x_i)\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$ . Wielomiany interpolacyjne tej postaci nazywane są wielomianami interpolacyjnymi Lagrange'a.

[edytuj] Jednoznaczność interpolacji wielomianowej

Dowód

Załóżmy, że istnieją dwa 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$ $x \in 0,1,\cdots ,n$ interpolują tą samą funckję, 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ć wielomian tożsamościowo równy zeru. A ponieważ

$\! W_3(x)\ =\ W_1(x) - W_2(x)\ =\ 0$

$\! W_1(x)\ =\ W_2(x)$

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

[edytuj] Błąd interpolacji

Dość naturalnym wydawało by się zwiększanie ilości węzłów (równoważnie stopnia wielomianu interpolacyjnego) w celu coraz lepszego przybliżenia funkcji f(x) wielomianem $L n (x)$ . "Wymarzona" 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ównoodległych tak być nie musi.

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

$\frac{f^{(n+1)}(\xi)}{(n+1)!}\cdot p_n(x)\le 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)$