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),\dots ,\,\varphi _{n}(x)],\quad \mathbf {A} =(a_{0},\,a_{1},\dots ,\,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,\dots ,\,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 \to \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 {}$ oraz
• 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},\dots ,\,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}\;{}$ gdy ${}\;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,\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 {\Pi (x-x_{i})}{\Pi (x_{k}-x_{i})}},$

gdzie $\Pi$ jest iloczynem, w którym $i=0,\,1,\dots ,\,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}}\;x=x_{i},\\\;0\quad {\text{gdy}}\;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)+\ldots +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})+\ldots +y_{i}L_{i}(x_{i})+\ldots +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})\ldots (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

$\varphi _{0}(x)={\begin{cases}\;0\quad {\text{gdy}}\quad x\leqslant x_{0},\\\;{\frac {x_{1}-x}{x_{1}-x_{0}}}\quad {\text{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 {\text{gdy}}\quad x\in (x_{i-1},\,x_{i})\\\;{\frac {x_{i+1}-x}{x_{i+1}-x_{i}}}\quad {\text{gdy}}\quad x\in (x_{i},\,x_{i+1})\end{cases}}\right\}\quad i=1,\,2,\dots ,\,n-1,$ $\varphi _{n}(x)={\begin{cases}\;{\frac {x-x_{n-1}}{x_{n}-x_{i-1}}}\quad {\text{gdy}}\quad x\in (x_{n-1},\,x_{n}),\\\;0\quad {\text{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,\dots ,\,n-1$ funkcja $f(x)$ jest interpolowana przez dwie funkcje

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

${\bar {\psi }}_{i}(\xi )=1-\xi ,\quad {\bar {\psi }}_{i+1}(\xi )=\xi ,\quad \xi \in [0,\,1],\quad i=0,\,1,\dots ,\,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 {\text{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,\dots ,\,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 {\text{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 interpolują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,\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 $\varphi ^{'}(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ńczonych.

Zobacz też

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