Interpolacja wielomianowa

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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[edytuj | edytuj kod]

 Osobny artykuł: 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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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 \and j\ne i}^n \frac{x-x_j}{x_i-x_j}.

Ponieważ \prod_{j=0 \and j\ne 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 \and j\ne 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[edytuj | edytuj kod]

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}, \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 \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\} i k\not=i:

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)).


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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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ż[edytuj | edytuj kod]