Metody numeryczne: Obliczenia wzoru interpolacyjnego

Obliczenia wzoru interpolacyjnego

Czym jest interpolacja?

Najogólniej rzecz biorąc, interpolacja polega na przybliżaniu funkcji. Aby jednak dokładnie zrozumieć czym jest, a czym nie jest interpolacja, należy powiedzieć kilka słów więcej. Owszem, ona przybliża funkcję - jednak robi to w szczególny sposób - zachowuje bowiem równość wartości w wybranych punktach (zwanych węzłami) pomiędzy funkcją którą chcemy przybliżyć (interpolowaną), a funkcją przybliżającą (interpolującą) f(x)

Zazwyczaj zależy nam dodatkowo, aby w punktach które nie są węzłami przybliżenie było również jak najlepsze. Jako funkcje interpolujące najczęściej wykorzystuje się wielomiany algebraiczne, trygonometryczne lub funkcje wymierne.

Zastosowanie interpolacji

Interpolacja zdecydowanie nie należy do tej części matematyki z którą spotykamy się na co dzień, jednak dla każdego matematyka (a także ludzi innych zawodów) stanowi ona nieocenione narzędzie. Oto najpopularniejsze zastosowania interpolacji:

zastępowanie skomplikowanego wzoru funkcji prostszym (np. wielomianem)
obliczanie wartości stablicowanej funkcji w punkcie różnym od danych (szczególnie przydatne w przypadku tablic matematycznych, pozwala to także na zmniejszenie rozmiaru tablic)
rozwiązywanie równań (interpolacja odwrotna)
wiele innych metod numerycznych opiera się na metodach interpolacyjnych, np. różniczkowanie i całkowanie numeryczne

Zbieżność interpolacji, wybór węzłów interpolacji

Na pewno każdy, kto zmierzył się już raz z zagadnieniem interpolacji w praktyce, zadał sobie następujące pytanie: czy ilość węzłów ma wpływ na jakość przybliżenia funkcji interpolującej? Odpowiedz jest szczególnie istotna w przypadku gdy węzły oraz wartości w węzłach zdobywamy na drodze eksperymentu, gdyż wiemy, czy warto dokonać większej liczby pomiarów. W przypadku gdy mamy już wszystkie niezbędne dane, możemy zadecydować jak wiele z nich należy użyć.
Okazuje się, że w przypadku węzłów równoodległych, wraz ze wzrostem liczby węzłów, pojawia się zjawisko Rungego - na obrzeżach przedziału w którym przeprowadzamy interpolację pojawiają się znaczne różnice pomiędzy wartością wielomianu interpolacyjnego, a wartością żądaną. W przypadku węzłów dowolnych natomiast, funkcja Lagrange'a jest jednostajnie zbieżna. Błędne przybliżenia pojawiają się również podczas interpolacji funkcji, której wykres znacznie się różni od wykresu wielomianu interpolacyjnego.
Aby zminimalizować błąd interpolacji najlepiej jako węzły przyjąć węzły Czebyszewa:

W przedziale <a, b> wartości węzłów Czebyszewa uzyskujemy dzięki następującemu przekształceniu:

Przegląd metod interpolacyjnych

Wzór interpolacyjny Lagrange'a

Jedną z najpopularniejszych i najprostszych metod interpolacyjnych jest metoda Lagrange'a. Jest to metoda, która zawsze pozwala nam na znalezienie jednoznacznie określonej funkcji interpolującej będącej wielomianem.
Mając dane n+1 węzłów wraz z ich wartościami, szukamy wielomianu W_n(x) stopnia co najwyżej n, który przyjmuje zadane wartości dla zadanych węzłów.
Oznaczając przez

Wzór interpolacyjny Langrange'a możemy zapisać jako:

Obie zapisane powyżej postacie wzoru Lagrange'a są równoważne, stosujemy je jednak w różnych przypadkach.

Przykład:
Mając dane węzły 0, 1, 3, 8 wraz z wartościami 2, 6, -1, 8 obliczamy wielomian interpolacyjny:

Błąd metody Lagrange'a obliczamy za pomocą wzorów:

gdzie

Zalety:	Wady:
- Przydatna w obliczeniach ręcznych	- Nie posiada istotnych wad

Iteracyjna metoda Aitkena

Istnieje metoda obliczania wartości wielomianu Lagrange'a w zadanym punkcie, bez obliczania samego wielomianu interpolacyjnego. Służy do tego iteracyjna metoda Aitkena.
Oznaczmy przez

wielomian który w węzłach

(

) przyjmuje wartości

Co można uogólnić jako:

Aby obliczyć wartość wielomianu interpolacyjnego opartego na n węzłach w dowolnym punkcie a różnym od węzłów, należy obliczyć wartość

. Wszystkie wyniki niezbędnych obliczeń wygodnie jest umieścić w macierzy trójkątnej wraz z węzłami oraz ich wartościami (schemat taki nazywamy schematem Aitkena). Rozwiązanie takie jest dogodne zarówno podczas rachunków ręcznych, jak i maszynowych, gdyż podczas obliczania każdej wartości zawsze korzystamy z wartości położonych na lewo w tym samym rzędzie i powyższych.

Przykład:
Wykorzystując wartości wraz z węzłami z poprzedniego rozdziału, obliczymy wartość tej funkcji dla argumentu 4:
Układamy odpowiednią macierz obliczając kolejno

Stąd

, co jest wartością funkcji Lagrange'a w punkcie

Zalety:	Wady:
- Wygodna w obliczeniach - Łatwo dodać kolejne węzły	- Nie posiada istotnych wad

Wzór interpolacyjny Newtona dla nierównych odstępów argumentu

Kolejną metodą wyprowadzania wielomianu interpolacyjnego jest metoda Newtona. Wielomian utworzony za jej pomocą, jest tożsamy z wielomianem Lagrange'a.
Wprowadźmy pojęcie ilorazu różnicowego. Wyrażenie:

nazywamy ilorazem różnicowym rzędu n.
Podczas dalszych obliczeń, niezbędne staną się wartości ilorazów kolejnych różnicowych:

, ...,

. Aby je obliczyć, wygodnie jest utworzyć następującą tabelkę:

Tak jak poprzednio, przyjmując oznaczenie

wielomian interpolacyjny który przyjmuje postać:

jest nazywany wzorem interpolacyjnym Newtona z ilorazami różnicowymi. Błąd podczas stosowania powyższej metody jest identyczny jak ten w przypadku interpolacji Lagrange'a.

Zalety:	Wady:
- Wygodna w obliczeniach - Łatwo dodać kolejne węzły	- Nie posiada istotnych wad

Wzory interpolacyjny Newtona dla równoodległych wartości argumentu

W niżej przedstawionej metodzie, po raz pierwszy założymy, że węzły tworzą ciąg arytmetyczny (o różnicy h), co znacznie uprości wzory interpolacyjne: Podobnie jak przy poprzedniej metodzie, i tym razem należy wprowadzić dodatkowe oznaczenia: Mając dane wartości funkcji

w punktach

, ...

, różnicą progresywną rzędu pierwszego nazywamy wyrażenie:

Ogólnie różnice progresywne definiujemy jako:

Analogicznie definiujemy różnice wsteczne:

dla

Uogólniając:

Warto zauważyć, że

Korzystając z powyższych oznaczeń, możemy skorzystać z następujących wzorów:
Wzór

nazywamy pierwszym wzorem interpolacyjnym Newtona. Można go znacznie uprościć, wprowadzając zmienną

dzięki której otrzymujemy:

Wzór ten nazywamy często wzorem interpolacyjnym Newtona na interpolację w przód. Stosujemy go, gdy używamy początkowej części tablicy. Dla danych znajdujących się na końcu, istnieje inny wzór w którym wykorzystuje się różnice wsteczne:

Jest to drugi wzór interpolacyjny Newtona. Podobnie jak poprzednio przyjmując

, oraz przekształcając ten wzór otrzymujemy wzór interpolacyjny Newtona na interpolację wstecz:

Błędy dla wcześniej przedstawionych wzorów obliczamy za pomocą następujących wzorów: Dla pierwszego wzoru Newtona:

oraz dla drugiego wzoru Newtona:

Zalety:	Wady:
- W przypadku węzłów równoodległych, powyższe wzory są wygodne podczas obliczeń ręcznych - Łatwo dodać kolejne składniki do wzorów	- Nie posiada istotnych wad

Interpolacja Taylora

Przedstawię teraz bardzo prostą i popularną metodę do przybliżania funkcji w punkcie, mając dane wartości kolejnych pochodnych w tym punkcie.
Jeśli interpolowana funkcja f(x) jest określona w otoczeniu punktu x0 i posiada n kolejnych pochodnych w tym otoczeniu, to możemy ją przybliżyć za pomocą wzoru Taylora:

Funkcja którą w ten sposób uzyskamy, w punkcie x0 będzie miała równą wartość oraz równe n kolejnych pochodnych w stosunku do f(x).
Przykład:
Przeprowadźmy interpolację funkcji

dla

.
Dla

mamy:

Dla

mamy:

Dla

mamy:

Na wykresie zostały przedstawione otrzymane funkcje:

Rozmiar błędy metody Taylora możemy obliczyć z następującego wzoru:

Zalety:	Wady:
- Duża dokładność przybliżenia w otoczeniu punktu x₀ - Łatwo dodać kolejne składniki do wzorów	- Przybliża wartości interpolowanej funkcji jedynie w otoczeniu punktu x₀

Interpolacja Padé

Interpolacja Padé jest odpowiednikiem interpolacji Taylora, zatem również zachowuje ona równość kolejnych pochodnych. W tym przypadku jednak funkcją interpolującą jest funkcja wymierna postaci:

Zbiór takich funkcji oznaczamy

, gdzie p oznacza stopień licznika, q stopień mianownika i

. Gdy

, to otrzymujemy wielomian interpolacyjny Taylora. Aby wyznaczyć współczynniki funkcji

należy rozwiązań poniższy układ

równań:

.........................................

gdzie

występuje po prawej stronie p razy, a współczynniki

, ...,

należą do rozwinięcia Maclaurina funkcji interpolowanej:

Przykład:
Podobnie jak poprzednio, tym razem również przeprowadźmy interpolację funkcji

dla

. Wyprowadźmy funkcje

Podczas obliczeń, założyliśmy, że

, a następnie wszystkie współczynniki zostały tak przemnożone, aby uzyskać współczynniki całkowite. Oto wykresy uzyskanych funkcji.
Jak widać, w otoczeniu punktu

, funkcje interpolacyjne bardzo dobrze przybliżają funkcję

. Porównajmy zatem różnice pomiędzy wymiernymi funkcjami interpolacyjnymi Padé, a wielomianami interpolacyjnymi Taylora.

Na rysunku zostały przedstawione wykresy następujących funkcji:
- kolor czarny - interpolacja Taylora, n=1
- kolor bordowy - interpolacja Taylora, n=3
- kolor granatowy - interpolacja Taylora, n=5
- kolor niebieski - interpolacja Padé,

- kolor czerwony - interpolacja Padé,

- kolor zielony - interpolacja Padé,

Z przedstawionego porównania wynika, że w tym wypadku dla wartości większych od zera interpolacja Padé oraz interpolacja Taylora dają przybliżone wyniki, jednak poniżej zera, interpolacja Padé jest znacznie bardziej skuteczna, szczególnie gdy licznik wraz z mianownikiem mają ten sam stopień. Gdy stopień licznika jest niższy niż mianownika, powstaje asymptota co w jej otoczeniu znacząco pogarsza jakość przybliżenia.

Zalety:	Wady:
- Duża dokładność przybliżenia w otoczeniu punktu x₀	- Przybliża wartości interpolowanej funkcji jedynie w otoczeniu punktu x₀

Interpolacja odwrotna

We wszystkich dotąd przedstawionych metodach, zajmowaliśmy się szukaniem wartości dla argumentu innego niż te, na których opieraliśmy naszą interpolację. Interpolacja odwrotna ma na celu znalezienie takiego argumentu, dla którego interpolowana funkcja przyjmie żądaną wartość. Inaczej mówiąc, mając funkcję interpolującą

, szukaliśmy wartości

, dla danego

. Tym razem zajmiemy się szukaniem

, dla zadanego

.
Mając daną funkcję

, z danymi węzłami oraz wartościami w węzłach, postępujemy następująco:
Dzięki założeniu, że funkcja

spełnia założenia o funkcji odwrotnej na przedziale

, możemy napisać,

, gdzie

jest funkcją odwrotną do

. Następnie przyjmujemy za węzły interpolacji argumenty funkcji g(y) (a więc wartości funkcji

), a za wartości funkcji w węzłach wartości funkcji

(argumenty

).
Teraz możemy przeprowadzić interpolację dowolną wcześniej przedstawioną metodą (najlepiej metodą iteracyjną Aitkena), w celu znalezienia szukanego argumentu

, dla zadanej wartości.

Zalety:	Wady:
- Metoda bardzo pomocna przy rozwiązywaniu równań postaci - Brak narzuconej metody wyznaczania funkcji interpolującej lub obliczania jej wartości	- Nie posiada istotnych wad

Interpolacja funkcjami sklejanymi

Szczególnie popularnym rodzajem interpolacji jest interpolacja funkcjami sklejanymi. Główną cechą wyróżniającą ten rodzaj interpolacji, jest podział przedziału na którym znajdują się węzły, na mniejsze podprzedziały, a następnie użycie na każdym z nich wielomianu interpolacyjnego odpowiednio niskiego stopnia. Wyznaczenie sklejanej funkcji interpolującej nie sprawia problemu (także, gdy węzłów jest bardzo dużo), tak jak późniejsze obliczanie jej wartości, co na pewno wpłynęło znacząco na jej popularność. Gdy odstępy między węzłami wynoszą h, to moduł błędu metody jest rzędu O(h⁴).

Funkcje sklejane stopnia pierwszego

Najprostszym przypadkiem funkcji sklejanych są funkcje sklejane stopnia pierwszego. Niech nasza interpolowana funkcja przyjmuje w węzłach

wartości odpowiednio

.
Wprowadźmy teraz funkcję która będzie podstawą dla dalszych obliczeń:

Jak można zauważyć, funkcja ta, w węźle xi przyjmuje wartość 1, w sąsiednich węzłach wartość 0, natomiast w każdym z przedziałów

jest funkcją liniową. Dzięki takiej definicji funkcję interpolującą można zapisać następująco:

Co zawsze jednoznacznie określa daną funkcję. Funkcje sklejane stopnia pierwszego w większości przypadków nie dadzą nam najlepszego przybliżenia funkcji interpolowanej. Znajdą jednak zastosowanie wszędzie tam, gdzie potrzebne jest liniowe przejście pomiędzy kolejnymi wartościami w węzłach.
Przykład:
Stwórzmy interpolacyjną funkcję sklejaną stopnia pierwszego, która przyjmuje w węzłach 0, 1,3, 8 wartości odpowiednio 2. 6, -1, 8. Obliczamy funkcje

Wzór funkcji

przyjmuje postać

a jej wykres wygląda następująco:

Zalety:	Wady:
- Dzięki temu, że jest to łamana, może okazać się przydatna w problemach innej klasy niż inne funkcje interpolujące - Wyznaczenie funkcji oraz obliczenie wartości w dowolnym punkcie jest bardzo szybkie	- Słabo przybliża funkcję interpolowaną