Interpolacja wielomianowa

Interpolacja wielomianowa, nazywana też interpolacją Lagrange’a, od nazwiska pioniera badań nad interpolacją Josepha Lagrange’a lub po prostu interpolacją – metoda numeryczna 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 funkcjaSzablon:R.

Interpolacja jest często stosowana w naukach doświadczalnych, gdzie dysponuje się zazwyczaj skończoną liczbą danych określających badane zależności.

Zgodnie z twierdzeniem Weierstrassa dowolną funkcję $y=f(x),$ ciągłą na przedziale domkniętym $[x_0,x_n]\in R^1$ można dowolnie przybliżyć za pomocą wielomianu odpowiednio wysokiego stopniaSzablon:R.

Interpolacja liniowa

Interpolacja liniowa

Szablon:Osobny artykuł Taka interpolacja jest szczególnym, najprostszym 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 te punkty (rys. obok).

Ogólne sformułowanie metody

Przykład interpolacji wielomianowej.

Metoda interpolacji funkcji $f$ polega na:

1. wybraniu $n+1$ punktów (węzłów interpolacji) $x_0,x_1,\dots ,x_n$ należących do dziedziny $f,$ dla których znane są wartości $y_0=f(x_0),y_1=f(x_1),\dots ,y_n=f(x_n);$
2. zbudowaniu wielomianu $\phi (x)$ stopnia co najwyżej $n$ takiego, że $\phi (x_0)=y_0,\phi (x_1)=y_1,\dots ,\phi (x_n)=y_n.$

Interpretacja geometryczna – dla danych $n+1$ rzędnych funkcji $f$ szuka się wielomianu stopnia co najwyżej $n,$ którego wykres przechodzi przez te rzędne (rys. obok).

• Uogólniony wielomian interpolacyjny

Skorzystamy z wielomianu o postaci ogólnej Szablon:Wzór

utworzonej z pewnego zbioru funkcji ${\phi }_i(x),$ które są liniowo niezależne i tworzą bazę interpolacji Szablon:Wzór

Współczynniki $a_i$ dobierzemy w taki sposób, aby spełnione były warunki Szablon:Wzór

w których $x_i$ oznaczają współrzędne danych węzłów interpolacji funkcji $f(x).$ Po uwzględnieniu (1) otrzymujemy układ równań Szablon:Wzór

lub w zapisie macierzowymSzablon:R Szablon:Wzór

Na podstawie (1) i (5) otrzymujemy Szablon:Wzór

O jakości interpolacji decydują:

• wybór bazy $𝐁(x)$ oraz
• wybór położenia węzłów $x_i.$

• Interpolacja Lagrange’a

Najprostszą bazę interpolacji można utworzyć z jednomianów Szablon:Wzór

W tym przypadku otrzymuje się macierz Szablon:Wzór

o strukturze VandermondaSzablon:R i dzięki temu zawsze istnieje rozwiązanie problemu jeżeli tylko $x_i\ne x_j$ gdy $i\ne j.$

Korzystając ze wzoru (6) i bazy (7), możemy utworzyć taką funkcję ${\varphi }_k(x),$ która spełnia warunki ${\varphi }_k(x_i)={\delta }_{ik},i=0,1,\dots ,n.$ Wystarczy obliczyć współczynniki $a_i^{(k)},$ rozwiązując układ równań (4) z prawą stroną

$F_k=[f(x_1)=0,f(x_2)=0,\dots ,f(x_k)=1,\dots ,f(x_n)=0{]}^T.$

Wielomian taki zaproponował Lagrange w postaci

$L_k(x)=\frac{\mathrm{\Pi }(x-x_i)}{\mathrm{\Pi }(x_k-x_i)},$

gdzie $\mathrm{\Pi }$ jest iloczynem, w którym $i=0,1,\dots ,n$ i $i\ne k.$

Wielomian Lagrange’a

Wielomian Lagrange’a to szczególna postać wielomianu, wykorzystywana często w zagadnieniach interpolacji. Dla wielomianu stopnia $n$ wybiera się $n+1$ punktów – $x_0,x_1,\dots ,x_n$ i wielomian ma postać:

$w(x)=\sum _{i=0}^n{y}_i\cdot \prod _{j=0\wedge j\ne i}^n\frac{x-x_j}{x_i-x_j}.$

Ponieważ $\prod _{j=0\wedge j\ne i}^n\frac{x-x_j}{x_i-x_j}=\{\begin{array}{c}1\text{gdy}x=x_i,\\ 0\text{gdy}x=x_j.\end{array}$

Dzięki temu interpolowaną funkcję $f(x)$ można przedstawić w postaci wielomianu

$L_f(x)=\sum _{i=0}^{n}f(x_i)\cdot \prod _{j=0\wedge j\ne i}^n\frac{x-x_j}{x_i-x_j},$

który spełnia warunki

$L_f(x_i)=f(x_i),i=0,1,\dots ,n.$

Dowód istnienia wielomianu interpolującego

Niech $x_0,x_1,\dots ,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,\dots ,f(x_n)=y_n.$
Można zdefiniować funkcję:

$L_i(x)=\prod _{j=0\wedge j\ne i}^n\frac{x-x_j}{x_i-x_j},i\in 0,1\dots ,n$

taką, że dla $x\notin \{x_0,x_1,\dots ,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,\dots ,x_n\}$ i $k=i:$

$L_i(x_k)=L_i(x_i)=\prod _{j=0\wedge j\ne i}^n\left(\frac{x_i-x_j}{x_i-x_j}\right)=\prod _{j=0\wedge j\ne i}^n(1)=1.$

Gdy $x_k\in \{x_0,x_1,\dots ,x_n\}$ i $k\ne i:$

$L_i(x_k)=\prod _{j=0\wedge j\ne i}^n\frac{x_k-x_j}{x_i-x_j}=\frac{(x_k-x_0)\cdot (x_k-x_1)\cdot \dots \cdot (x_k-x_k)\cdot \dots \cdot (x_k-x_n)}{(x_i-x_0)\cdot (x_i-x_1)\cdot \dots \cdot (x_i-x_{i-1})\cdot (x_i-x_{i+1})\cdot \dots \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{L}_0(x)+y_1{L}_1(x)+y_2{L}_2(x)+\dots +y_n{L}_n(x).$

Dla $x_i\in \{x_0,x_1,\dots ,x_n\}:$

$W(x_i)=y_0{L}_0(x_i)+y_1{L}_1(x_i)+\dots +y_i{L}_i(x_i)+\dots +y_n{L}_n(x_i).$

Wszystkie składniki sumy o indeksach różnych od $i$ są równe zeru (ponieważ dla $j\ne i{L}_i(x_j)=0$), składnik o indeksie $i$ jest równy:

$L_i(x_i)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)$ na zbiorze punktów $x_0,x_1,\dots ,x_n.$

Jednoznaczność interpolacji wielomianowej

Dowód

Zakłada się, że istnieją dwa różne wielomiany $W_1(x)$ i $W_2(x)$ stopnia $n,$ przyjmujące w węzłach $x_0,x{}_1,\dots ,x_n$ takie same wartości.

Niech

$W_3(x)=W_1(x)-W_2(x).$

$W_3(x)$ jest wielomianem 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,\dots ,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

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ść:

$\underset{n\to \mathrm{\infty }}{\lim }{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)\dots (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).$

Funkcje sklejane

Interpolacje funkcji $f(x),x\in [x_0,x_n]\subset R$ za pomocą wielomianów n-tego stopnia, w tym również wielomianów Lagrange’a, mają istotną wadę. Polega ona na tym, że ze wzrostem liczby węzłów interpolacji, przybliżanie wartości funkcji, pomiędzy jej kolejnymi węzłami, odbywa się przez tworzenie kombinacji liniowej z fragmentów kolejnych $n$ wielomianów, które to fragmenty wraz ze wzrostem liczby $n,$ upodabniają się do siebie i niewiele się różnią. Sytuację pogarsza złożoność obliczania wartości tych wielomianów. W sumie powoduje to wzrost niestabilności algorytmów obliczeniowych. Można generalnie stwierdzić, że przyczyną tego stanu rzeczy jest fakt, że nośnikiem funkcji aproksymujących jest cały przedział $[x_0,x_n].$

Złożoności obliczeniowej można uniknąć w bardzo prosty sposób, budując sklejane funkcje aproksymujące o jak najkrótszych nośnikach. Przy czym nie ma potrzeby posługiwania się wielomianami wysokich stopni.

W przypadku, gdy funkcja interpolująca nie musi być różniczkowalna, można ją zbudować przez „sklejenie” odcinków prostoliniowych. W tym przypadku baza interpolacji składa się z prostych funkcji Szablon:Wzór

W każdym przedziale międzywęzłowym $[x_i,x_{i+1}],i=0,1,\dots ,n-1$ funkcja $f(x)$ jest interpolowana przez dwie funkcje

${\psi }_i(x)=\frac{x_{i+1}-x}{x_{i+1}-x_i}\mathrm{i}{\psi }_{i+1}(x)=\frac{x-x_i}{x_{i+1}-x_i},x\in [x_i,x_{i+1}],i=0,1,\dots ,n-1.$

Funkcje te przez odwzorowanie $x=(1-\xi )x_i+\xi x_{i+1}$ przedziału $[x_i,x_{i+1}]$ na przedział $[0,1],$ przyjmują postać standardową

${\overline{\psi }}_i(\xi )=1-\xi ,{\overline{\psi }}_{i+1}(\xi )=\xi ,\xi \in [0,1],i=0,1,\dots ,n-1.$

Różniczkowalność funkcji interpolującej $\phi (x)$ można uzyskać budując przykładowo bazę sklejoną z wielomianów 3-go stopnia

${\phi }_0(x)=\{\begin{array}{c}0\text{gdy}x⩽x_0,\\ 1-{\xi }^2(3-2\xi )+{\beta }_0\xi (1-\xi {)}^2,\xi =\frac{x-x_0}{x_1-x_0},x\in [x_0,x_1],\end{array}$

${\beta }_0=\frac{f(x_1)-f(x_0)}{x_1-x_0},$

${\phi }_i(x)=\{\begin{array}{c}{\xi }^2(3-2\xi )-{\beta }_i{\xi }^2(1-\xi ),\xi =\frac{x-x_{i-1}}{x_i-x_{i-1}},x\in [x_{i-1},x_i],\\ 1-{\xi }^2(3-2\xi )+{\beta }_i\xi (1-\xi {)}^2,\xi =\frac{x-x_i}{x_{i+1}-x_i},x\in [x_i,x_{i+1}],\end{array}$

${\beta }_i=\frac{f(x_{i+1})-f(x_{i-1})}{x_{i+1}-x_{i-1}},i=1,2,\dots ,n-1,$

${\phi }_n(x)=\{\begin{array}{c}{\xi }^2(3-2\xi )-{\beta }_n{\xi }^2(1-\xi ),\xi =\frac{x-x_{n-1}}{x_n-x_{n-1}},x\in [x_{n-1},x_n],\\ 0\text{gdy}x⩾x_n,\end{array}$

${\beta }_n=\frac{f(x_n)-f(x_{n-1})}{x_n-x_{n-1}}.$

Dzięki wprowadzeniu dodatkowych członów z mnożnikami ${\beta }_i$ wielomian interpolujący

$\phi (x)=a_0{\phi }_0(x)+a_1{\phi }_1(x)+\dots +a_n{\phi }_n(x)$

nie tylko spełnia warunki

$\phi (x_i)=f(x_i),i=0,1,\dots ,n,$

ale również przybliża średnie wartości pochodnych we wszystkich węzłach interpolacji. Pominięcie tych członów $({\beta }_i=0,i=0,1,\dots ,n)$ daje interpolację co prawda różniczkowalną, ale taką, że ${\phi }^{\text{'}}(x_i)=0,i=0,1,\dots ,n.$

Stosowanie baz zbudowanych z uogólnionych wielomianów sklejanych o krótkich nośnikach, złożonych tylko z dwu sąsiednich przedziałów, w sposób zdecydowany poprawia stabilność obliczeń interpolacyjnych.

Opisana koncepcja tworzenia baz sklejanych daje się bez trudu uogólnić na interpolację dwu- i trójwymiarową co stanowi podstawę metody elementów skończonychSzablon:R.

Zobacz też

• postać Hermite’a wielomianu
• postać Newtona wielomianu