03 Interpolacja


INTERPOLACJA

Podstawowe zagadnienia interpolacji, tutaj wielomianowej, to:

1. Poszukiwanie wielomianu interpolacyjnego 0x01 graphic
; ma to miejsce wtedy gdy:

nie jest znana analityczna postać funkcji 0x01 graphic
, tylko jej wartości 0x01 graphic
,

analityczna postać funkcji 0x01 graphic
jest zbyt złożona.

2. Obliczanie wartości wielomianu interpolacyjnego w punktach 0x01 graphic
, tzn. obliczanie wartości funkcji 0x01 graphic
między węzłami 0x01 graphic
.

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ć

0x01 graphic
0x01 graphic
(1.1)

gdzie 0x01 graphic
− funkcja interpolująca, 0x01 graphic
− wielomian interpolujący, 0x01 graphic
− stałe, 0x01 graphic
− funkcje bazowe (baza).

Dla określonych 0x01 graphic
należy dobrać takie 0x01 graphic
oraz 0x01 graphic
aby był spełniony określony warunek.

Twierdzenie 1.1, [276] s.25

Istnieje dokładnie jeden wielomian interpolacyjny co najwyżej stopnia 0x01 graphic
, 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 0x01 graphic
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 0x01 graphic
jest ciągła w przedziale skończonym 0x01 graphic
, to dla każdego 0x01 graphic
istnieje taka liczba 0x01 graphic
i wielomian 0x01 graphic
stopnia 0x01 graphic
takie, że

0x01 graphic
(1.2)

gdzie 0x01 graphic
.

___ 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

0x01 graphic
(1.3)

Najczęściej funkcja 0x01 graphic
nie jest dana w postaci jawnej, więc ścisłe obliczenie błędu jest niemożliwe; sama znajomość 0x01 graphic
też jest niewystarczająca. Aby można cokolwiek powiedzieć o błędzie interpolacji, należy mieć dodatkową informację o funkcji 0x01 graphic
. Zwykle na podstawie przesłanek o zjawisku fizycznym, które funkcja 0x01 graphic
opisuje, można taką informację otrzymać. Jest to najczęściej informacja o klasie funkcji 0x01 graphic
.

Twierdzenie 1.3, [276] s.35

Jeżeli funkcja 0x01 graphic
ma w przedziale 0x01 graphic
ciągłą 0x01 graphic
pochodną, a punkty 0x01 graphic
są różne i wraz z 0x01 graphic
należą do przedziału 0x01 graphic
, to

0x01 graphic
(1.4)

gdzie

0x01 graphic
0x01 graphic
(1.5)

oraz

0x01 graphic
(1.6)

___ Twierdzenie 1.3 ___

Ponieważ 0x01 graphic
nie jest znane a priori, w praktyce stosuje się dwa oszacowania wzoru (1.6), oszacowanie w punkcie 0x01 graphic
oraz oszacowanie w przedziale 0x01 graphic
. Niech

0x01 graphic
(1.7)

Podstawiając (1.7) do (1.4) otrzyma się

0x01 graphic
(1.8)

Niech

0x01 graphic
(1.9)

stąd zamiast (1.8) jest

0x01 graphic
(1.10)

4. Interpolacja Lagrange'a i Hermite'a

W zależności od postaci 0x01 graphic
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:

0x01 graphic
− zbiór dowolnych węzłów, 0x01 graphic
,

0x01 graphic
− zbiór wartości funkcji 0x01 graphic
w węzłach 0x01 graphic
,

0x01 graphic
− zbiór wartości 0x01 graphic
−pochodnych funkcji 0x01 graphic
w węzłach, 0x01 graphic
.

W interpolacji Hermite'a żąda się spełnienia warunku, rys. 1.1(a),

0x01 graphic
(1.11)

Jeżeli 0x01 graphic
, to wzór ten przedstawia warunek interpolacji Lagrange'a, rys. 1.1(b).

0x01 graphic

(a)

0x01 graphic

(b)

Rys1.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ć

0x01 graphic
0x01 graphic
(1.12)

gdzie 0x01 graphic
− wielomiany ogólne.

Jednoznaczność zagadnienia interpolacyjnego wielomianami ogólnymi rozstrzyga twierdzenie 1.1, z którego wynika, że obliczenie 0x01 graphic
we wzorze (1.1) sprowadza się do rozwiązania układu 0x01 graphic
równań algebraicznych. Współczynniki 0x01 graphic
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 0x01 graphic
, oraz zbiór wartości funkcji w tych węzłach 0x01 graphic
. Znaleźć wielomian interpolacyjny, gdzie bazą jest (1.2). Funkcja 0x01 graphic
.

Rozwiązanie

Podstawiając we wzorze (1.1) wielomiany ogólne otrzymuje się funkcję interpolacyjną

0x01 graphic
(1)

Stałe 0x01 graphic
wyznacza się z warunku interpolacji (1.11)

0x01 graphic

0x01 graphic
(2)

0x01 graphic

lub w zapisie macierzowym

0x01 graphic
(3)

Wyznacznik główny układu jest wyznacznikiem Vandermonde'a

0x01 graphic
0x01 graphic
(4)

Ponieważ 0x01 graphic
, więc układ (3) ma jedno rozwiązanie; szuka się go z wzorów Cramera

0x01 graphic
0x01 graphic
0x01 graphic
(5)

gdzie

0x01 graphic
0x01 graphic
0x01 graphic
(6)

Według wzoru (1) wielomian interpolacyjny przyjmuje postać

0x01 graphic
(7)

Wielomian interpolacyjny jest rozwiązaniem ścisłym.

___ Przykład 1.1 ___

Przykład 1.2

Niech będzie dany jest zbiór 0x01 graphic
, oraz zbiór wartości funkcji 0x01 graphic
w tych węzłach 0x01 graphic
. Znaleźć wielomian interpolacyjny, gdzie bazą jest (1.2). Obliczyć wartość przybliżoną 0x01 graphic
, błąd interpolacji w punkcie 0x01 graphic
, błąd w przedziale 0x01 graphic
; wartość ścisła 0x01 graphic
.

Rozwiązanie.

Podstawiając we wzorze (1.1) wielomiany ogólne otrzymuje się funkcję interpolacyjną

0x01 graphic
(1)

Stałe 0x01 graphic
wyznacza się z warunku interpolacji (1.11)

0x01 graphic

0x01 graphic
(2)

0x01 graphic

lub w zapisie macierzowym

0x01 graphic
(3)

Wyznacznik główny układu jest wyznacznikiem Vandermonde'a

0x01 graphic
0x01 graphic
(4)

Ponieważ 0x01 graphic
, więc układ (3) ma jedno rozwiązanie; szuka się go z wzorów Cramera

0x01 graphic
0x01 graphic
0x01 graphic
(5)

gdzie

0x01 graphic
0x01 graphic
0x01 graphic
(6)

Według wzoru (1), wielomian interpolacyjny przyjmuje postać

0x01 graphic
(7)

Stąd 0x01 graphic
.

Oszacowanie błędu w punkcie dane jest wzorem (1.8), gdzie

0x01 graphic
(8)

0x01 graphic
(9)

Stąd według (1.8) jest

0x01 graphic
(10)

Dla 0x01 graphic
jest 0x01 graphic
. Oszacowanie błędu w przedziale:

0x01 graphic
(11)

stąd według (1.10) jest

0x01 graphic
(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 0x01 graphic
, oraz zbiór wartości funkcji 0x01 graphic
w tych węzłach 0x01 graphic
. Znaleźć wielomian interpolacyjny, gdzie bazą jest (1.2). Obliczyć wartość przybliżoną 0x01 graphic
, błąd interpolacji w punkcie 0x01 graphic
, błąd w przedziale 0x01 graphic
; wartość ścisła 0x01 graphic
.

___ 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 0x01 graphic
jest równa, [276] s.63,

Lagrange'a 0x01 graphic
działań, w tym 0x01 graphic
mnożeń i dzieleń,

Newtona 0x01 graphic
działań, w tym 0x01 graphic
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 0x01 graphic

0x01 graphic
(1.13)

Wielomian interpolacyjny Lagrange'a ma postać

0x01 graphic
(1.14)

gdzie wielomiany Lagrange'a definiuje się:

0x01 graphic
0x01 graphic
(1.15)

Podstawową własnością wielomianów Lagrange'a jest

0x01 graphic
(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 0x01 graphic
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 0x01 graphic
, oraz zbiór wartości funkcji 0x01 graphic
w tych węzłach 0x01 graphic
. Znaleźć wielomian interpolacyjny Lagrange'a; por. przykład 1.3.

Rozwiązanie

Dla 0x01 graphic
wielomiany Lagrange'a są równe

0x01 graphic

0x01 graphic
(1)

0x01 graphic

Zgodnie z wzorem (1.14) otrzyma się:

0x01 graphic

0x01 graphic
(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 0x01 graphic
, oraz zbiór wartości funkcji 0x01 graphic
w tych węzłach 0x01 graphic
. 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 0x01 graphic
oraz mianownik 0x01 graphic
w wielomianie Legendre'a (1.15) można odpowiednio zapisać, [1036] t.1, s.229,

0x01 graphic
0x01 graphic
(1.19)

Stąd zamiast (1.15) jest

0x01 graphic
(1.20)

Podstawiając (1.19) do (1.14) jest

0x01 graphic
0x01 graphic
(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

0x01 graphic
(1.23)

Współczynnik przed wielomianem 0x01 graphic
ilorazem różnicowym

0x01 graphic
(1.24)

A zatem według (1.23) otrzyma się

0x01 graphic
(1.25)

Porównując ten wzór z ogólna postacią wielomianowego wzoru interpolacyjnego (1.1) jest

0x01 graphic
(1.26)

gdzie 0x01 graphic
, 0x01 graphic
.

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 0x01 graphic
, oraz zbiór wartości funkcji 0x01 graphic
w tych węzłach 0x01 graphic
. Obliczyć wartość przybliżoną 0x01 graphic
według wzoru (1.25); wartość ścisła 0x01 graphic
.

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 0x01 graphic
w wzorze (1.26)

0x01 graphic

0x01 graphic

0x01 graphic

0x01 graphic

0

0x01 graphic

0x01 graphic

1

0x01 graphic

0x01 graphic

0x01 graphic

3

0x01 graphic

Stałe 0x01 graphic
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 0x01 graphic
. Dla uproszczenia rozważań przyjęto 0x01 graphic
we wszystkich węzłach zbioru 0x01 graphic
, rys. 1.1(b), a więc żąda się spełnienia warunku, por. (1.11),

0x01 graphic
0x01 graphic
0x01 graphic
(1.27)

W interpolacji wielomianowej funkcja interpolująca ma postać (1.1); tutaj ze względu na powyższy warunek jest

0x01 graphic
(1.28)

gdzie 0x01 graphic
, natomiast wielomianami Hermite'a są

0x01 graphic
,

0x01 graphic
(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

0x01 graphic
(1.30)

gdzie 0x01 graphic
− wzór (1.17).

Oszacowanie w punkcie 0x01 graphic
oraz oszacowanie w przedziale 0x01 graphic
wymaga określenia

0x01 graphic
(1.31)

oraz

0x01 graphic
(1.32)

Podstawiając te wzory do (1.30) otrzyma się odpowiednio oszacowania błędu w punkcie i w obszarze

0x01 graphic
(1.33)

0x01 graphic
(1.34)

Przykład 1.6

Niech będzie dany jest zbiór węzłów 0x01 graphic
, oraz zbiór wartości funkcji 0x01 graphic
oraz jej pochodnej 0x01 graphic
w tych węzłach, stąd 0x01 graphic
; wszystkie węzły 0x01 graphic
są dwukrotne. Obliczyć wartość przybliżoną 0x01 graphic
według wzoru (1.28) oraz oszacowanie błędu w tym punkcie; wartość ścisła 0x01 graphic
.

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

0x01 graphic

0x01 graphic
,0x01 graphic

0x01 graphic

0x01 graphic

0x01 graphic

0x01 graphic

0x01 graphic

0x01 graphic

0

0x01 graphic

0x01 graphic

0x01 graphic

0x01 graphic

0x01 graphic

0x01 graphic

0x01 graphic

1

0x01 graphic

0x01 graphic

1

0x01 graphic

0x01 graphic

0x01 graphic

0x01 graphic

3

0x01 graphic

0x01 graphic

0x01 graphic

0x01 graphic

0x01 graphic

0x01 graphic

0x01 graphic

Dla powyższych wielkości (1.28) jest równy

0x01 graphic
(1)

Stąd

0x01 graphic
(2)

Dla 0x01 graphic
jest

0x01 graphic
(3)

Błąd interpolacji dla 0x01 graphic
oszacowany w punkcie 0x01 graphic
wynosi, wzór (1.33),

0x01 graphic
(4)

Jak widać, błąd 0x01 graphic
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



Wyszukiwarka

Podobne podstrony:
2011 Lab 03 Interpolacja aproksymacja TZ
Psychologia zachowań interpersonalnych 03, notatki, psychologia
Ćwiczenie 12 Interpretacja RKZ OK 11 03
03 zestaw ćwiczeń ułatwiających prawidłowe kontakty interpersonalne
2019 03 27 Odpowiedź Ministra Infrastruktury na interpelację w sprawie obowiązku opon zimowych
03 Sejsmika04 plytkieid 4624 ppt
Interpretacja treści Księgi jakości na wybranym przykładzie
03 Odświeżanie pamięci DRAMid 4244 ppt
podrecznik 2 18 03 05
od Elwiry, prawo gospodarcze 03
Probl inter i kard 06'03
TT Sem III 14 03
Praktyczna interpretacja pomiarów cisnienia
03 skąd Państwo ma pieniądze podatki zus nfzid 4477 ppt
03 PODSTAWY GENETYKI
Wyklad 2 TM 07 03 09

więcej podobnych podstron