INTERPOLACJA
Podstawowe zagadnienia interpolacji, tutaj wielomianowej, to:
1. Poszukiwanie wielomianu interpolacyjnego
; ma to miejsce wtedy gdy:
nie jest znana analityczna postać funkcji
, tylko jej wartości
,
analityczna postać funkcji
jest zbyt złożona.
2. Obliczanie wartości wielomianu interpolacyjnego w punktach
, tzn. obliczanie wartości funkcji
między węzłami
.
1. Podział interpolacji
I podział
Rodzaje interpolacji przejrzyście podano w [291]. W zależności od bazy podział interpolacji jest następujący:
wielomianowa,
funkcjami sklejanymi (szczególna postać wielomianu),
wymierna,
trygonometryczna,
inna.
II podział
Istnieje też inny podział wzorów interpolacyjnych, [352] s.106:
globalnego typu; prowadzi do modeli 1-elementowych. Ogólna charakterystyka reprezentacji globalnego typu jest następująca:
funkcja interpolacyjna uwzględnia informacje z całej funkcji lub całego zbioru danych dyskretnych,
w celu zmniejszenia błędu interpolacji stosuje się wysoki stopień wielomianu interpolacyjnego, ale prowadzi to do zjawiska Runge'go.
lokalnego typu; prowadzi do modeli wielo-elementowych. Ogólna charakterystyka:
funkcja interpolacyjna uwzględnia informacje z pewnej części funkcji lub podzbioru danych dyskretnych; nie zmienia to całej funkcji interpolacyjnej a zmienia ją tylko w pewnym przedziale,
łatwo można zmienić interpolację w przedziałach szczególnie interesujących,
funkcja interpolacyjna w przedziale może być wielomianem niskiego stopnia i dlatego nie występuje zjawisko Runge'go.
specyficzną postać wzoru interpolacyjnego tworzą funkcje sklejane. Ta postać wzoru (wielomianu) jest niskiego stopnia. Informacje w funkcjach sklejanych nie są ani lokalnego ani globalnego typu. Funkcje sklejane zapewniają gładkość wysokiego stopnia w każdym punkcie przedziału.
2. Uzasadnienie wyboru wzoru interpolacyjnego
Wybierając wzór interpolacyjny zwraca się uwagę na następujące kryteria:
dokładność rozwiązania zagadnienia interpolacji,
łatwość analizy i przekształceń,
koszt obliczenia wartości,
stabilność numeryczną oraz.
Uwzględniając w/w kryteria, największe zastosowanie znalazła interpolacja wielomianowa oraz funkcjami sklejanymi; te dwie postacie interpolacji będą dalej rozważane.
3. Interpolacja wielomianowa
Spośród wielu postaci wzoru interpolacyjnego, [248] s.256, wybrano wielomiany interpolacyjne, a wśród nich te, które są oparte o funkcje bazowe odpowiednich przestrzeni funkcyjnych. Przez to wielomiany interpolacyjne automatycznie spełniają niektóre warunki interpolacji. Dodatkowym powodem wyboru wielomianu interpolacyjnego jest to, że w niektórych jego postaciach współczynniki interpolacji mają sens fizyczny lub w prosty sposób można podać ich interpretację fizyczną.
W przypadku interpolacji wielomianowej, funkcja interpolująca ma postać
(1.1)
gdzie
− funkcja interpolująca,
− wielomian interpolujący,
− stałe,
− funkcje bazowe (baza).
Dla określonych
należy dobrać takie
oraz
aby był spełniony określony warunek.
Twierdzenie 1.1, [276] s.25
Istnieje dokładnie jeden wielomian interpolacyjny co najwyżej stopnia
, który spełnia warunek interpolacji.
___ Twierdzenie 1.1 ___
Z tego twierdzenia wynika, że na tych samych węzłach można zbudować tylko jeden wielomian interpolacyjny stopnia co najwyżej
bez względu na metodę wyznaczania tego wielomianu, a zatem − bez względu na jego postać.
Błąd interpolacji wielomianowej
Twierdzenie 1.2, [276] s.34
Jeżeli funkcja
jest ciągła w przedziale skończonym
, to dla każdego
istnieje taka liczba
i wielomian
stopnia
takie, że
(1.2)
gdzie
.
___ Twierdzenie 1.2 ___
Twierdzenia 1.1 i 1.2 są podstawowymi twierdzeniami zagadnienia interpolacji wielomianowej.
Z wzoru (1.2) wynika, że błąd interpolacji jest równy
(1.3)
Najczęściej funkcja
nie jest dana w postaci jawnej, więc ścisłe obliczenie błędu jest niemożliwe; sama znajomość
też jest niewystarczająca. Aby można cokolwiek powiedzieć o błędzie interpolacji, należy mieć dodatkową informację o funkcji
. Zwykle na podstawie przesłanek o zjawisku fizycznym, które funkcja
opisuje, można taką informację otrzymać. Jest to najczęściej informacja o klasie funkcji
.
Twierdzenie 1.3, [276] s.35
Jeżeli funkcja
ma w przedziale
ciągłą
pochodną, a punkty
są różne i wraz z
należą do przedziału
, to
(1.4)
gdzie
(1.5)
oraz
(1.6)
___ Twierdzenie 1.3 ___
Ponieważ
nie jest znane a priori, w praktyce stosuje się dwa oszacowania wzoru (1.6), oszacowanie w punkcie
oraz oszacowanie w przedziale
. Niech
(1.7)
Podstawiając (1.7) do (1.4) otrzyma się
(1.8)
Niech
(1.9)
stąd zamiast (1.8) jest
(1.10)
4. Interpolacja Lagrange'a i Hermite'a
W zależności od postaci
rozróżnia się kilka rodzajów interpolacji wielomianowej, a wśród nich najważniejszymi są interpolacja Lagrange'a i Hermite'a; interpolacja Lagrange'a jest szczególnym przypadkiem interolacji Hermite'a. Niech będą dane:
− zbiór dowolnych węzłów,
,
− zbiór wartości funkcji
w węzłach
,
− zbiór wartości
−pochodnych funkcji
w węzłach,
.
W interpolacji Hermite'a żąda się spełnienia warunku, rys. 1.1(a),
(1.11)
Jeżeli
, to wzór ten przedstawia warunek interpolacji Lagrange'a, rys. 1.1(b).
(a) |
(b) |
Rys. 1.1. Warunek interpolacji: (a) − Lagrange'a, (b) − Hermite'a |
5. Interpolacja wielomianami ogólnymi
Interpolacja ta ma ogólną postać (1.1) gdzie funkcje bazowe mają postać
(1.12)
gdzie
− wielomiany ogólne.
Jednoznaczność zagadnienia interpolacyjnego wielomianami ogólnymi rozstrzyga twierdzenie 1.1, z którego wynika, że obliczenie
we wzorze (1.1) sprowadza się do rozwiązania układu
równań algebraicznych. Współczynniki
tworzą wyznacznik Vandermode'a. Szczegóły interpolacji wielomianami ogólnymi są podane w przykładach.
Przykład 1.1
Niech będzie dany zbiór węzłów
, oraz zbiór wartości funkcji w tych węzłach
. Znaleźć wielomian interpolacyjny, gdzie bazą jest (1.2). Funkcja
.
Rozwiązanie
Podstawiając we wzorze (1.1) wielomiany ogólne otrzymuje się funkcję interpolacyjną
(1)
Stałe
wyznacza się z warunku interpolacji (1.11)
(2)
lub w zapisie macierzowym
(3)
Wyznacznik główny układu jest wyznacznikiem Vandermonde'a
(4)
Ponieważ
, więc układ (3) ma jedno rozwiązanie; szuka się go z wzorów Cramera
(5)
gdzie
(6)
Według wzoru (1) wielomian interpolacyjny przyjmuje postać
(7)
Wielomian interpolacyjny jest rozwiązaniem ścisłym.
___ Przykład 1.1 ___
Przykład 1.2
Niech będzie dany jest zbiór
, oraz zbiór wartości funkcji
w tych węzłach
. Znaleźć wielomian interpolacyjny, gdzie bazą jest (1.2). Obliczyć wartość przybliżoną
, błąd interpolacji w punkcie
, błąd w przedziale
; wartość ścisła
.
Rozwiązanie.
Podstawiając we wzorze (1.1) wielomiany ogólne otrzymuje się funkcję interpolacyjną
(1)
Stałe
wyznacza się z warunku interpolacji (1.11)
(2)
lub w zapisie macierzowym
(3)
Wyznacznik główny układu jest wyznacznikiem Vandermonde'a
(4)
Ponieważ
, więc układ (3) ma jedno rozwiązanie; szuka się go z wzorów Cramera
(5)
gdzie
(6)
Według wzoru (1), wielomian interpolacyjny przyjmuje postać
(7)
Stąd
.
Oszacowanie błędu w punkcie dane jest wzorem (1.8), gdzie
(8)
(9)
Stąd według (1.8) jest
(10)
Dla
jest
. Oszacowanie błędu w przedziale:
(11)
stąd według (1.10) jest
(12)
___ Przykład 1.2 ___
W razie niepowodzenia przedstawienia funkcji interpolacyjnej w postaci wielomianu interpolacyjnego w całym przedziale można użyć szczególnych wielomianów takich jak wielomiany Czebyszewa, funkcje sklejane, [352] s.109, lub np. wykorzystać funkcje przedziałami wielomianowe.
Przykład 1.3
Niech będzie dany jest zbiór
, oraz zbiór wartości funkcji
w tych węzłach
. Znaleźć wielomian interpolacyjny, gdzie bazą jest (1.2). Obliczyć wartość przybliżoną
, błąd interpolacji w punkcie
, błąd w przedziale
; wartość ścisła
.
___ Przykład 1.3 ___
Podstawową wadą interpolacji wielomianami ogólnymi jest słabe uwarunkowanie macierzy głównej. Niedogodność tę usuwają kolejne rodzaje interpolacji.
6. Wielomiany interpolacyjne Lagrange'a i Newtona
Czasochłonność obliczeń mierzyć można liczbą działań niezbędnych do wykonania obliczeń według danego wzoru. Liczba działań arytmetycznych potrzebna do obliczenia wartości wielomianu interpolacyjnego stopnia
jest równa, [276] s.63,
Lagrange'a
działań, w tym
mnożeń i dzieleń,
Newtona
działań, w tym
mnożeń i dzieleń.
Ponieważ czasy dodawania i odejmowania są niewielkie to o czasie obliczeń decydują mnożenia i dzielenia. Jak wynika z powyższego porównania wzór interpolacyjny Newtona jest wzorem wygodnym do wyznaczenia wartości i numerycznie szybkim.
6.1. Wielomian interpolacyjny Lagrange'a
I postać
Interpolacja Lagrange'a jest dana wzorem (1.11) dla
(1.13)
Wielomian interpolacyjny Lagrange'a ma postać
(1.14)
gdzie wielomiany Lagrange'a definiuje się:
(1.15)
Podstawową własnością wielomianów Lagrange'a jest
(1.16)
Postać wzoru (1.14) jest przejrzysta. Poza tym, porównując ten wzór z ogólną postacią wzoru interpolującego (1.1), stałe
a więc, stałe te mają interpretację fizyczną. Stąd, ten wzór jest szeroko stosowany obliczeniach numerycznych. Jest on jednak niewygodny szczególnie wtedy, gdy istnieje potrzeba zmiany liczby węzłów. Wtedy do wyznaczenia wielomianu interpolacyjnego należy powtarzać obliczenia od początku. Oznacza to, że zmiana liczby węzłów powoduje bezużyteczność wielomianu uprzednio wyznaczonego. Tę dużą niedogodność usuwa wielomian interpolacyjny Newtona. Tutaj zmiana liczby węzłów powoduje dołączenie lub odjęcie do wielomianu uprzednio wyznaczonego dodatkowego czynnika.
Przykład 1.4
Niech będzie dany jest zbiór
, oraz zbiór wartości funkcji
w tych węzłach
. Znaleźć wielomian interpolacyjny Lagrange'a; por. przykład 1.3.
Rozwiązanie
Dla
wielomiany Lagrange'a są równe
(1)
Zgodnie z wzorem (1.14) otrzyma się:
(2)
Wzór (2) należy porównać z odpowiednim wzorem przykładu 1.2.
___ Przykład 1.4 ___
Przykład 1.5
Niech będzie dany jest zbiór
, oraz zbiór wartości funkcji
w tych węzłach
. Znaleźć wielomian interpolacyjny Lagrange'a. Wynik porównać z rozwiązaniem w przykładzie 1.3.
___ Przykład 1.5 ___
6.2. Wielomian interpolacyjny Newtona
Wzór interpolacyjny Newtona:
usuwa wadę wzoru interpolacyjny Lagrange'a: tutaj zmiana liczby węzłów powoduje dołączenie lub odjęcie do wielomianu uprzednio wyznaczonego dodatkowego czynnika,
jest szybszy numerycznie.
Wzorem wyjściowym jest (1.14). Licznik
oraz mianownik
w wielomianie Legendre'a (1.15) można odpowiednio zapisać, [1036] t.1, s.229,
(1.19)
Stąd zamiast (1.15) jest
(1.20)
Podstawiając (1.19) do (1.14) jest
(1.21)
Ten wzór jest zamiennie zamiast (1.14), a ponadto jest wzorem wyjściowym do wzoru interpolującego Newtona.
Według (1.21) via (1.19) jest
(1.23)
Współczynnik przed wielomianem
ilorazem różnicowym
(1.24)
A zatem według (1.23) otrzyma się
(1.25)
Porównując ten wzór z ogólna postacią wielomianowego wzoru interpolacyjnego (1.1) jest
(1.26)
gdzie
,
.
Jest to pierwszy wzór interpolacyjny Newtona, [276] s.50. Natomiast drugi − bazuje na ilorazach różnicowych wstecznych [276] s.54. Wzór (1.26) spełnia warunek interpolacji Lagrange'a.
Przykład 1.5
Niech będzie dany jest zbiór
, oraz zbiór wartości funkcji
w tych węzłach
. Obliczyć wartość przybliżoną
według wzoru (1.25); wartość ścisła
.
Rozwiązanie
Ilorazy różnicowe najpierw tworzy się według tabeli 4.1.8, tutaj ma ona poniższą postać.
Tabela 1. Idea tworzenia stałych
w wzorze (1.26)
|
|
|
|
0 |
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
3 |
|
|
|
Stałe
we wzorze (1.25) są zamarkowane w tabeli 1.
___ Przykład 1.5 ___
1.4. Interpolacja Hermite'a
[248] s.65, [1036] s.231, [858] s.54
W tej interpolacji słuszny jest wzór (1.11) dla
. Dla uproszczenia rozważań przyjęto
we wszystkich węzłach zbioru
, rys. 1.1(b), a więc żąda się spełnienia warunku, por. (1.11),
(1.27)
W interpolacji wielomianowej funkcja interpolująca ma postać (1.1); tutaj ze względu na powyższy warunek jest
(1.28)
gdzie
, natomiast wielomianami Hermite'a są
,
(1.29)
Dalej podano przykład zastosowania interpolacji Hermite'a. Jest on tak dobrany, aby wszystkie obliczenia można było wykonać nawet na kalkulatorze.
Błąd interpolacji Hermite'a
Słuszne są wszystkie twierdzenia podane dla interpolacji Lagrange'a. Odpowiednikiem wzoru (1.4) jest
(1.30)
gdzie
− wzór (1.17).
Oszacowanie w punkcie
oraz oszacowanie w przedziale
wymaga określenia
(1.31)
oraz
(1.32)
Podstawiając te wzory do (1.30) otrzyma się odpowiednio oszacowania błędu w punkcie i w obszarze
(1.33)
(1.34)
Przykład 1.6
Niech będzie dany jest zbiór węzłów
, oraz zbiór wartości funkcji
oraz jej pochodnej
w tych węzłach, stąd
; wszystkie węzły
są dwukrotne. Obliczyć wartość przybliżoną
według wzoru (1.28) oraz oszacowanie błędu w tym punkcie; wartość ścisła
.
Rozwiązanie
Występujące wielkości w (1.28) podano najpierw w postaci ogólnej, a następnie wyliczono ich wartości; wyniki umieszczono w tabeli 1.
Tabela 1
|
|
|
|
|
|
|
|
0 |
|
|
|
|
|
|
|
1 |
|
|
1 |
|
|
|
|
3 |
|
|
|
|
|
|
|
Dla powyższych wielkości (1.28) jest równy
(1)
Stąd
(2)
Dla
jest
(3)
Błąd interpolacji dla
oszacowany w punkcie
wynosi, wzór (1.33),
(4)
Jak widać, błąd
i mieści się w przedziale oszacowania (4).
___ Przykład 1.6 ___
Literatura
[248] A. Ralston, A first course in numerical analysis, McGraw-Hill, NY,Sydney, 1965.
[276] Z. Fortuna, B. Macukow, J. Wąsowski, Metody numeryczne, WNT, Warszawa, 1993.
[291] B. Sendow, Stare i nowe w metodach numerycznych, PWN, 1976.
[352] J.R. Rice, Numerical methods, software, and analysis: IMSL Refrence Edition, Mc Graw-Hill Book Company, N.Y., 1983.
[858] B. Bożek, Metody obliczeniowe i ich komputerowa realizacja, AGH, 2005.
[1036] G.M. Fichtenholtz, Rachunek różniczkowy i całkowy, PWN, Warszawa, 1999
[295] J.M. Jankowscy, Przegląd metod i algorytmów numerycznych, WNT, Warszawa, 1981.
- 8 -
Interpolacja