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

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

Interpolacja liniowa

Interpolacja liniowa

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 $\,\varphi (x)\,$ stopnia co najwyżej $\,n\,$ takiego, że $\,\varphi (x_{0})=y_{0},\,\varphi (x_{1})=y_{1},\dots ,\,\varphi (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

$\varphi (x)=a_{0}\varphi _{0}(x)+a_{1}\varphi _{1}(x)+\,\ldots ,\,a_{n}\varphi _{n}(x)=\mathbf {B} (x)\mathbf {A} ,\quad x\in [x_{0}\,x_{n}]$

(1)

utworzonej z pewnego zbioru funkcji $\,\varphi _{i}(x),$ które są liniowo niezależne i tworzą bazę interpolacji

$\mathbf {B} (x)=[\varphi _{0}(x),\,\varphi _{1}(x)],\ldots ,\,\varphi _{n}(x)],\quad \mathbf {A} =(a_{0},\,a_{1},\,\ldots ,\,a_{n})^{T}.$

(2)

Współczynniki $\,a_{i}\,$ dobierzemy w taki sposób, aby spełnione były warunki

$\varphi (x_{i})=f(x_{i}),\quad i=0,\,1,\,\ldots ,\,n,$

(3)

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ń

${\begin{bmatrix}\varphi _{0}(x_{0})&\varphi _{1}(x_{0})&\ldots &\varphi _{n}(x_{0})\\\varphi _{0}(x_{1})&\varphi _{1}(x_{1})&\ldots &\varphi _{n}(x_{1})\\\ldots &\ldots &\ldots &\ldots \\\varphi _{0}(x_{n})&\varphi _{1}(x_{n})&\ldots &\varphi _{n}(x_{n})\\\end{bmatrix}}{\begin{bmatrix}a_{0}\\a_{1}\\\vdots \\a_{n}\end{bmatrix}}={\begin{bmatrix}f(x_{0})\\f(x_{1})\\\vdots \\f(x_{n})\end{bmatrix}}$

(4)

lub w zapisie macierzowym

$\mathbf {VA} =\mathbf {F} \quad \rightarrow \quad \mathbf {A} =\mathbf {V^{-1}F} =\mathbf {LF} .$

(5)

Na podstawie (1) i (5) otrzymujemy

$\varphi (x)=\mathbf {B} (x)\mathbf {LF} .$

(6)

O jakości interpolacji decydują:

• wybór bazy $\,\mathbf {B} (x)\quad i$
• wybór położenia węzłów $\,x_{i}.$

• Interpolacja Lagrange'a

Najprostszą bazę interpolacji można utworzyć z jednomianów

$\mathbf {B} (x)=(1,\,x,\,x^{2},\,\ldots ,\,x^{n}).$

(7)

W tym przypadku otrzymuje się macierz

$\mathbf {V} ={\begin{bmatrix}1&x_{0}&x_{0}^{2}&\ldots &x_{0}^{n}\\1&x_{1}&x_{1}^{2}&\ldots &x_{1}^{n}\\\ldots &\ldots &\ldots &\ldots \\1&x_{n}&x_{n}^{2}&\ldots &x_{n}^{n}\end{bmatrix}}$

(8)

o strukturze Vandermonda i dzięki temu zawsze istnieje rozwiązanie problemu jeżeli tylko $\,x_{i}\neq x_{j}\quad gdy\quad i\neq j.$

Korzystając ze wzoru (6) i bazy (7), możemy utworzyć taką funkcję $\,\phi _{k}(x),$ która spełnia warunki $\,\phi _{k}(x_{i})=\delta _{ik},\;i=0,\,1,\,\ldots ,\,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,\,\ldots ,\,f(x_{k})=1,\,\ldots ,\,f(x_{n})=0]^{T}.$

Wielomian taki zaproponował Lagrange w postaci

$L_{k}(x)={\frac {\Pi (x-x_{i})}{\Pi (x_{k}-x_{i})}},$

gdzie $\,\Pi \,$ jest iloczynem, w którym $\,i=0,\,1,\,\ldots ,\,n\quad i\quad i\neq 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\land j\neq i}^{n}{\frac {x-x_{j}}{x_{i}-x_{j}}}.$

Ponieważ $\,\prod _{j=0\land j\neq i}^{n}{\frac {x-x_{j}}{x_{i}-x_{j}}}\;=\;{\begin{cases}\;1\quad {\text{gdy}}\quad x=x_{i},\\\;0\quad {\text{gdy}}\quad x=x_{j}.\end{cases}}$
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\land j\neq i}^{n}{\frac {x-x_{j}}{x_{i}-x_{j}}},$

który spełnia warunki

$\,L_{f}(x_{i})=f(x_{i}),\quad 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\land j\neq i}^{n}{\frac {x-x_{j}}{x_{i}-x_{j}}},\quad 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\land j\neq i}^{n}\left({\frac {x_{i}-x_{j}}{x_{i}-x_{j}}}\right)=\prod _{j=0\land j\neq i}^{n}(1)=1.$

Gdy $x_{k}\in \{x_{0},x_{1},\dots ,x_{n}\}$ i $k\neq i{:}$

$L_{i}(x_{k})=\prod _{j=0\land j\neq i}^{n}{\frac {x_{k}-x_{j}}{x_{i}-x_{j}}}={\frac {(x_{k}-x_{0})\cdot (x_{k}-x_{1})\cdot \ldots \cdot (x_{k}-x_{k})\cdot \ldots \cdot (x_{k}-x_{n})}{(x_{i}-x_{0})\cdot (x_{i}-x_{1})\cdot \ldots \cdot (x_{i}-x_{i-1})\cdot (x_{i}-x_{i+1})\cdot \ldots \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)+\cdots +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})+\cdots +y_{i}L_{i}(x_{i})+\cdots +y_{n}L_{n}(x_{i}).$

Wszystkie składniki sumy o indeksach różnych od $i$ są równe zeru (ponieważ dla $j\neq 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).\qquad$(*)

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

$\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})\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 nie wiele 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

$\varphi _{0}(x)={\begin{cases}\;0\quad gdy\quad x\leqslant x_{0},\\\;{\frac {x_{1}-x}{x_{1}-x_{0}}}\quad gdy\quad x\in (x_{0},\,x_{1}),\end{cases}}$ $\left.\varphi _{i}(x)={\begin{cases}\;{\frac {x-x_{i-1}}{x_{i}-x_{i-1}}}\quad gdy\quad x\in (x_{i-1},\,x_{i})\\\;{\frac {x_{i+1}-x}{x_{i+1}-x_{i}}}\quad gdy\quad x\in (x_{i},\,x_{i+1})\end{cases}}\right\}\quad i=1,\,2,\,\ldots ,\,n-1,$ $\varphi _{n}(x)={\begin{cases}\;{\frac {x-x_{n-1}}{x_{n}-x_{i-1}}}\quad gdy\quad x\in (x_{n-1},\,x_{n}),\\\;0\quad gdy\quad x\geqslant x_{n}.\end{cases}}$

(a)

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

$\psi _{i}(x)={\frac {x_{i+1}-x}{x_{i+1}-x_{i}}}\quad i\quad \psi _{i+1}(x)={\frac {x-x_{i}}{x_{i+1}-x_{i}}},\quad x\in [x_{i},\,x_{i+1}],\quad i=0,\,1,\,\ldots ,\,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ą

${\bar {\psi }}_{i}(\xi )=1-\xi ,\quad {\bar {\psi }}_{i+1}(\xi )=\xi ,\quad \xi \in [0,\,1],\quad i=0,\,1,\,\ldots ,\,n-1.$

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

$\varphi _{0}(x)={\begin{cases}\;0\quad gdy\quad x\leqslant x_{0},\\\;1-\xi ^{2}(3-2\xi )+\beta _{0}\xi (1-\xi )^{2},\quad \xi ={\frac {x-x_{0}}{x_{1}-x_{0}}},\quad x\in [x_{0},\,x_{1}],\\\end{cases}}$

$\qquad \qquad \qquad \beta _{0}={\frac {f(x_{1})-f(x_{0})}{x_{1}-x_{0}}},$

$\varphi _{i}(x)={\begin{cases}\;\xi ^{2}(3-2\xi )-\beta _{i}\xi ^{2}(1-\xi ),\quad \xi ={\frac {x-x_{i-1}}{x_{i}-x_{i-1}}},\quad x\in [x_{i-1},\,x_{i}],\\\;1-\xi ^{2}(3-2\xi )+\beta _{i}\xi (1-\xi )^{2},\quad \xi ={\frac {x-x_{i}}{x_{i+1}-x_{i}}},\quad x\in [x_{i},\,x_{i+1}],\\\end{cases}}$

$\qquad \qquad \qquad \beta _{i}={\frac {f(x_{i+1})-f(x_{i-1})}{x_{i+1}-x_{i-1}}},\quad i=1,\,2,\,\ldots ,\,n-1,$

$\varphi _{n}(x)={\begin{cases}\;\xi ^{2}(3-2\xi )-\beta _{n}\xi ^{2}(1-\xi ),\quad \xi ={\frac {x-x_{n-1}}{x_{n}-x_{n-1}}},\quad x\in [x_{n-1},\,x_{n}],\\\;0\quad gdy\quad x\geqslant x_{n},\end{cases}}$

$\qquad \qquad \qquad \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 interpojujący

$\varphi (x)=a_{0}\varphi _{0}(x)+a_{1}\varphi _{1}(x)+\ldots +a_{n}\varphi _{n}(x)$

nie tylko spełnia warunki

$\varphi (x_{i})=f(x_{i}),\quad i=0,\,1,\,\ldots ,\,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,\,\ldots ,\,n)\,$ daje interpolację co prawda różniczkowalną, ale taką, że $\,\varphi ^{'}(x_{i})=0,\;\;i=0,\,1,\,\ldots ,\,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ój-wymiarową co stanowi podstawę metody elementów skończonych.

Zobacz też

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