Metody numeryczne

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'astopnia 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.

Ogólna metoda

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

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