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

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

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

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

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

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

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

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ój-wymiarową co stanowi podstawę metody elementów skończonych[3].

Zobacz też

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

Przypisy

  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.

Media użyte na tej stronie

Interpolation example polynomial.svg
IIllustration of polynomial interpolation of a data set. The same data set is used for other interpolation algorithms in the Interpolation.