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 ${\displaystyle n}$ przyjmującym w ${\displaystyle n+1}$ punktach, zwanych węzłami interpolacji, wartości takie same jak przybliżana funkcja^[1].

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ę ${\displaystyle y=f(x),}$ ciągłą na przedziale domkniętym ${\displaystyle [x_{0},\,x_{n}]\in R^{1}}$ można dowolnie przybliżyć za pomocą wielomianu odpowiednio wysokiego stopnia^[2].

Interpolacja liniowa

 Osobny artykuł: Interpolacja liniowa.

Taka interpolacja jest szczególnym, najprostszym przypadkiem interpolacji wielomianowej dla dwóch punktów pomiarowych ${\displaystyle x_{0}}$ i ${\displaystyle x_{1},}$ dla których można utworzyć funkcję liniową, której wykres przechodzi przez te punkty (rys. obok).

Ogólne sformułowanie metody

Metoda interpolacji funkcji ${\displaystyle f}$ polega na:

1. wybraniu ${\displaystyle n+1}$ punktów (węzłów interpolacji) ${\displaystyle x_{0},x_{1},\dots ,x_{n}}$ należących do dziedziny ${\displaystyle f,}$ dla których znane są wartości ${\displaystyle y_{0}=f(x_{0}),\,y_{1}=f(x_{1}),\dots ,\,y_{n}=f(x_{n});}$
2. zbudowaniu wielomianu ${\displaystyle \varphi (x)}$ stopnia co najwyżej ${\displaystyle n}$ takiego, że ${\displaystyle \varphi (x_{0})=y_{0},\,\varphi (x_{1})=y_{1},\dots ,\,\varphi (x_{n})=y_{n}.}$

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

• Uogólniony wielomian interpolacyjny

Skorzystamy z wielomianu o postaci ogólnej

${\displaystyle \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 ${\displaystyle \varphi _{i}(x),}$ które są liniowo niezależne i tworzą bazę interpolacji

${\displaystyle \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 ${\displaystyle a_{i}}$ dobierzemy w taki sposób, aby spełnione były warunki

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

(3)

w których ${\displaystyle x_{i}}$ oznaczają współrzędne danych węzłów interpolacji funkcji ${\displaystyle f(x).}$ Po uwzględnieniu (1) otrzymujemy układ równań

${\displaystyle {\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^[1]

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

(5)

Na podstawie (1) i (5) otrzymujemy

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

(6)

O jakości interpolacji decydują:

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

• Interpolacja Lagrange’a

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

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

(7)

W tym przypadku otrzymuje się macierz

${\displaystyle \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^[1] i dzięki temu zawsze istnieje rozwiązanie problemu jeżeli tylko ${\displaystyle x_{i}\neq x_{j}\;{}}$ gdy ${\displaystyle {}\;i\neq j.}$

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

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

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

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

Wielomian Lagrange’a

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

${\displaystyle 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ż ${\displaystyle \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ę ${\displaystyle f(x)}$ można przedstawić w postaci wielomianu

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

${\displaystyle L_{f}(x_{i})=f(x_{i}),\quad i=0,\,1,\dots ,\,n.}$

Dowód istnienia wielomianu interpolującego

Niech ${\displaystyle x_{0},x_{1},\dots ,x_{n}}$ będą węzłami interpolacji funkcji ${\displaystyle f}$ takimi, że znane są wartości: ${\displaystyle f(x_{0})=y_{0},\,f(x_{1})=y_{1},\dots ,\,f(x_{n})=y_{n}.}$
Można zdefiniować funkcję:

${\displaystyle 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 ${\displaystyle x\notin \{x_{0},x_{1},\dots ,x_{n}\}}$ ${\displaystyle L_{i}(x)}$ jest wielomianem stopnia ${\displaystyle n}$ (mianownik jest liczbą, a licznik iloczynem ${\displaystyle n}$ wyrazów postaci ${\displaystyle (x-x_{j})}$).

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

${\displaystyle 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 ${\displaystyle x_{k}\in \{x_{0},x_{1},\dots ,x_{n}\}}$ i ${\displaystyle k\neq i{:}}$

${\displaystyle 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 ${\displaystyle (x_{k}-x_{k})}$).

Niech ${\displaystyle W(x)}$ będzie wielomianem stopnia co najwyżej ${\displaystyle n,}$ określonym jako:

${\displaystyle W(x)=y_{0}L_{0}(x)+y_{1}L_{1}(x)+y_{2}L_{2}(x)+\ldots +y_{n}L_{n}(x).}$

Dla ${\displaystyle x_{i}\in \{x_{0},x_{1},\dots ,x_{n}\}{:}}$

${\displaystyle 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 ${\displaystyle i}$ są równe zeru (ponieważ dla ${\displaystyle j\neq i\ \ L_{i}(x_{j})=0}$), składnik o indeksie ${\displaystyle i}$ jest równy:

${\displaystyle L_{i}(x_{i})y_{i}=1\cdot y_{i}=y_{i},}$

a więc

${\displaystyle W(x_{i})=y_{i},}$

z czego wynika, że ${\displaystyle W(x)}$ jest wielomianem interpolującym funkcję ${\displaystyle f(x)}$ na zbiorze punktów ${\displaystyle x_{0},\,x_{1},\dots ,\,x_{n}.}$

Jednoznaczność interpolacji wielomianowej

Dowód

Zakłada się, że istnieją dwa różne wielomiany ${\displaystyle W_{1}(x)}$ i ${\displaystyle W_{2}(x)}$ stopnia ${\displaystyle n,}$ przyjmujące w węzłach ${\displaystyle x_{0},x\,_{1},\dots ,\,x_{n}}$ takie same wartości.

Niech

${\displaystyle W_{3}(x)=W_{1}(x)-W_{2}(x).}$

${\displaystyle W_{3}(x)}$ jest wielomianem stopnia co najwyżej ${\displaystyle n}$ (co wynika z własności odejmowania wielomianów).

Ponieważ ${\displaystyle W_{1}(x)}$ i ${\displaystyle W_{2}(x)}$ w węzłach ${\displaystyle x_{i},\;i\in 0,1,\dots ,n}$ interpolują tę samą funkcję, to ${\displaystyle W_{1}(x_{i})=W_{2}(x_{i}),}$ a więc ${\displaystyle W_{3}(x_{i})=0}$ (węzły interpolacji są pierwiastkami ${\displaystyle W_{3}(x)).\qquad {}}$(*)

Ale każdy niezerowy wielomian stopnia ${\displaystyle n}$ ma co najwyżej ${\displaystyle n}$ pierwiastków rzeczywistych, a ponieważ z (*) wiadomo, że ${\displaystyle W_{3}(x)}$ ma ${\displaystyle n+1}$ pierwiastków, to ${\displaystyle W_{3}(x)}$ musi być wielomianem tożsamościowo równym zeru, a ponieważ:

${\displaystyle W_{3}(x)=W_{1}(x)-W_{2}(x)=0}$

to

${\displaystyle W_{1}(x)=W_{2}(x),}$

co jest sprzeczne z założeniem, że ${\displaystyle W_{1}(x)}$ i ${\displaystyle 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 ${\displaystyle f(x)}$ wielomianem ${\displaystyle L_{n}(x).}$ Idealna byłaby zależność:

${\displaystyle \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 ${\displaystyle n,}$ przybliżającego funkcję ${\displaystyle f(x)}$ w przedziale ${\displaystyle [a,b]}$ na podstawie ${\displaystyle n+1}$ węzłów, istnieje taka liczba ${\displaystyle \xi }$ zależna od ${\displaystyle x,}$ że dla reszty interpolacji ${\displaystyle r(x){:}}$

${\displaystyle {\frac {f^{(n+1)}(\xi )}{(n+1)!}}\cdot p_{n}(x)=r(x),}$

gdzie ${\displaystyle p_{n}(x)=(x-x_{0})(x-x_{1})\ldots (x-x_{n}),}$ a ${\displaystyle \xi \in (a;b)}$ jest liczbą zależną od ${\displaystyle x.}$

Do oszacowania z góry wartości ${\displaystyle r(x)}$ można posłużyć się wielomianami Czebyszewa stopnia ${\displaystyle n+1}$ do oszacowania wartości ${\displaystyle p_{n}(x)}$ dla ${\displaystyle x\in [-1,1].}$ Dla przedziału ${\displaystyle [a,b]}$ wystarczy dokonać przeskalowania wielomianu ${\displaystyle p_{n}(x).}$

Funkcje sklejane

Interpolacje funkcji ${\displaystyle 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 ${\displaystyle n}$ wielomianów, które to fragmenty wraz ze wzrostem liczby ${\displaystyle 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ł ${\displaystyle [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

${\displaystyle \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}}}$ ${\displaystyle \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,}$ ${\displaystyle \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 ${\displaystyle [x_{i},\,x_{i+1}],\;\;i=0,\,1,\dots ,\,n-1}$ funkcja ${\displaystyle f(x)}$ jest interpolowana przez dwie funkcje

${\displaystyle \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 ${\displaystyle x=(1-\xi )x_{i}+\xi x_{i+1}}$ przedziału ${\displaystyle [x_{i},\,x_{i+1}]}$ na przedział ${\displaystyle [0,\,1],}$ przyjmują postać standardową

${\displaystyle {\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 ${\displaystyle \varphi (x)}$ można uzyskać budując przykładowo bazę sklejoną z wielomianów 3-go stopnia

${\displaystyle \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}}}$

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

${\displaystyle \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}}}$

${\displaystyle {}\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,}$

${\displaystyle \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}}}$

${\displaystyle {}\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 ${\displaystyle \beta _{i}}$ wielomian interpolujący

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

nie tylko spełnia warunki

${\displaystyle \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 ${\displaystyle (\beta _{i}=0,\;\;i=0,\,1,\dots ,\,n)}$ daje interpolację co prawda różniczkowalną, ale taką, że ${\displaystyle \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^[3].

Zobacz też

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

Przypisy