Interpolacja wielomianowa

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

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]

Information icon.svg 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:

  • 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)
  • 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:

  • 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.
  • Dla kolejnego węzła znajduje sie 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.
  • Dodaje się wartość ostatnio obliczonego wielomianu do wartości poprzedniego
  • Dla każdego z pozostałych węzłów znajduje się podobny wielomian, za każdym razem dodając go do wielomianu wynikowego
  • 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.

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}\ \ \ \ \ , 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 (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\ \


(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

Załóżmy, ż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ć wielomian tożsamościowo równy 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]