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 przyjmującym w 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ę ciągłą na przedziale domkniętym można dowolnie przybliżyć za pomocą wielomianu odpowiednio wysokiego stopnia[2].

Interpolacja liniowa

edytuj
 
Interpolacja liniowa
Osobny artykuł: Interpolacja liniowa.

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

Ogólne sformułowanie metody

edytuj
 
Przykład interpolacji wielomianowej.

Metoda interpolacji funkcji   polega na:

  1. wybraniu   punktów (węzłów interpolacji)   należących do dziedziny   dla których znane są wartości  
  2. zbudowaniu wielomianu   stopnia co najwyżej   takiego, że  

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

  • Uogólniony wielomian interpolacyjny

Skorzystamy z wielomianu o postaci ogólnej

 
(1)

utworzonej z pewnego zbioru funkcji   które są liniowo niezależne i tworzą bazę interpolacji

 
(2)

Współczynniki   dobierzemy w taki sposób, aby spełnione były warunki

 
(3)

w których   oznaczają współrzędne danych węzłów interpolacji funkcji   Po uwzględnieniu (1) otrzymujemy układ równań

 
(4)

lub w zapisie macierzowym[1]

 
(5)

Na podstawie (1) i (5) otrzymujemy

 
(6)

O jakości interpolacji decydują:

  • wybór bazy   oraz
  • wybór położenia węzłów  
  • Interpolacja Lagrange’a

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

 
(7)

W tym przypadku otrzymuje się macierz

 
(8)

o strukturze Vandermonda[1] i dzięki temu zawsze istnieje rozwiązanie problemu jeżeli tylko   gdy  

Korzystając ze wzoru (6) i bazy (7), możemy utworzyć taką funkcję   która spełnia warunki   Wystarczy obliczyć współczynniki   rozwiązując układ równań (4) z prawą stroną

 

Wielomian taki zaproponował Lagrange w postaci

 

gdzie   jest iloczynem, w którym   i  

Wielomian Lagrange’a

edytuj

Wielomian Lagrange’a to szczególna postać wielomianu, wykorzystywana często w zagadnieniach interpolacji. Dla wielomianu stopnia   wybiera się   punktów –   i wielomian ma postać:

 

Ponieważ  

Dzięki temu interpolowaną funkcję   można przedstawić w postaci wielomianu

 

który spełnia warunki

 

Dowód istnienia wielomianu interpolującego

edytuj

Niech   będą węzłami interpolacji funkcji   takimi, że znane są wartości:  
Można zdefiniować funkcję:

 

taką, że dla     jest wielomianem stopnia   (mianownik jest liczbą, a licznik iloczynem   wyrazów postaci  ).

Gdy   i  

 

Gdy   i  

 

(licznik = 0, ponieważ występuje element  ).

Niech   będzie wielomianem stopnia co najwyżej   określonym jako:

 

Dla  

 

Wszystkie składniki sumy o indeksach różnych od   są równe zeru (ponieważ dla  ), składnik o indeksie   jest równy:

 

a więc

 

z czego wynika, że   jest wielomianem interpolującym funkcję   na zbiorze punktów  

Jednoznaczność interpolacji wielomianowej

edytuj

Dowód

Zakłada się, że istnieją dwa różne wielomiany   i   stopnia   przyjmujące w węzłach   takie same wartości.

Niech

 

  jest wielomianem stopnia co najwyżej   (co wynika z własności odejmowania wielomianów).

Ponieważ   i   w węzłach   interpolują tę samą funkcję, to   a więc   (węzły interpolacji są pierwiastkami  (*)

Ale każdy niezerowy wielomian stopnia   ma co najwyżej   pierwiastków rzeczywistych, a ponieważ z (*) wiadomo, że   ma   pierwiastków, to   musi być wielomianem tożsamościowo równym zeru, a ponieważ:

 

to

 

co jest sprzeczne z założeniem, że   i   są różne.

Błąd interpolacji

edytuj

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   wielomianem   Idealna byłaby zależność:

 

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   przybliżającego funkcję   w przedziale   na podstawie   węzłów, istnieje taka liczba   zależna od   że dla reszty interpolacji  

 

gdzie   a   jest liczbą zależną od  

Do oszacowania z góry wartości   można posłużyć się wielomianami Czebyszewa stopnia   do oszacowania wartości   dla   Dla przedziału   wystarczy dokonać przeskalowania wielomianu  

Funkcje sklejane

edytuj

Interpolacje funkcji   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   wielomianów, które to fragmenty wraz ze wzrostem liczby   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ł  

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

 
 
 
(a)

W każdym przedziale międzywęzłowym   funkcja   jest interpolowana przez dwie funkcje

 

Funkcje te przez odwzorowanie   przedziału   na przedział   przyjmują postać standardową

 

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

 

 

 

 

 

 

Dzięki wprowadzeniu dodatkowych członów z mnożnikami   wielomian interpolujący

 

nie tylko spełnia warunki

 

ale również przybliża średnie wartości pochodnych we wszystkich węzłach interpolacji. Pominięcie tych członów   daje interpolację co prawda różniczkowalną, ale taką, że  

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ż

edytuj

Przypisy

edytuj
  1. a b c J. Legras, Praktyczne metody analizy numerycznej, WNT, Warszawa 1974.
  2. B.P. Demidowicz, I.A. Maron, Metody numeryczne, cz. 2, PWN, Warszawa 1965.
  3. M.J. Ciałkowski, K. Magnucki, Zarys metody elementów skończonych, Wyd. Politechniki Poznańskiej, Poznań 1982.