Metody numeryczne
Interpolacja, część I
Janusz Szwabiński
[e-mail]
nm_slides-2.tex  Metody numeryczne  Janusz Szwabiński  8/10/2002  22:40  p.1/55
Literatura (uzupełnienie)
1. K. A. Ross, Ch. R. B. Wright,  Matematyka dyskretna
2. P. Wróblewski,  Algorytmy, struktury danych i techniki
programowania
3. Z. Fortuna, B. Macukow, J. Wąsowski,  Metody
numeryczne
4. G. M. Fichtenholz,  Rachunek różniczkowy i całkowy
5. A. Mostowski, M. Stark,  Elementy algebry wyższej
nm_slides-2.tex  Metody numeryczne  Janusz Szwabiński  8/10/2002  22:40  p.2/55
Interpolacja, część I
1. Zagadnienie interpolacyjne
2. Interpolacja wielomianowa

Wzór interpolacyjny Lagrange a

Metoda Aitkena

Metoda Neville a

Oszacowanie błędu wzoru interpolacyjnego

Wzór interpolacyjny Newtona

Zbieżność procesów interpolacyjnych
3. Interpolacja wymierna

Sformułowanie zagadnienia

Odwrotności ilorazów różnicowych
nm_slides-2.tex  Metody numeryczne  Janusz Szwabiński  8/10/2002  22:40  p.3/55
Zagadnienie interpolacyjne (1)


- węzły interpolacji





- wartości funkcji interpolowanej




- funkcja interpolująca







nm_slides-2.tex  Metody numeryczne  Janusz Szwabiński  8/10/2002  22:40  p.4/55
Zagadnienie interpolacyjne (2)
1
0,5
0
-1 0 1
x
nm_slides-2.tex  Metody numeryczne  Janusz Szwabiński  8/10/2002  22:40  p.5/55
y
Interpolacja wielomianowa (1)

Definicja Wyznacznikiem Vandermonde a stopnia nazywa się
wyznacznik





















.
.
.







Twierdzenie 1











nm_slides-2.tex  Metody numeryczne  Janusz Szwabiński  8/10/2002  22:40  p.6/55
Interpolacja wielomianowa (2)

Definicja Układ równań liniowych o niewiadomych
















.
.
.







nazywamy układem Cramera, jeśli








nm_slides-2.tex  Metody numeryczne  Janusz Szwabiński  8/10/2002  22:40  p.7/55
Interpolacja wielomianowa (3)
Twierdzenie 2 Układ Cramera ma dokładnie jedno
rozwiązanie:















gdzie macierz powstaje z macierzy przez zastąpienie  tej




kolumny przez , , .
nm_slides-2.tex  Metody numeryczne  Janusz Szwabiński  8/10/2002  22:40  p.8/55
Interpolacja wielomianowa (4)




- zbiór wielomianów stopnia



Twierdzenie 3 Dla dowolnych punktów węzłowych









dla



istnieje dokładnie jeden wielomian taki, że








interpolacja wielomianowa jest zagadnieniem
jednoznacznym.
nm_slides-2.tex  Metody numeryczne  Janusz Szwabiński  8/10/2002  22:40  p.9/55
Interpolacja wielomianowa (5)






Dowód Mamy punktów węzłowych . Szukamy
wielomianu interpolującego w postaci








przy czym







Stąd








.
.
.








nm_slides-2.tex  Metody numeryczne  Janusz Szwabiński  8/10/2002  22:40  p.10/55
Interpolacja wielomianowa (6)
Dowód (ciąg dalszy) Macierz tego układu (niewiadomymi są


współczynniki !) ma postać






.










.
.










jest wyznacznikiem Vandermonde a






Ponieważ dla ,







układ równań jest układem Cramera
nm_slides-2.tex  Metody numeryczne  Janusz Szwabiński  8/10/2002  22:40  p.11/55
Interpolacja wielomianowa (7)
Dowód (ciąg dalszy)

istnieje dokładnie jedno rozwiązanie





















gdzie są kolejnymi dopełnieniami algebraicznymi


elementów  tej kolumny macierzy .
nm_slides-2.tex  Metody numeryczne  Janusz Szwabiński  8/10/2002  22:40  p.12/55
Wzór interpolacyjny Lagrange a (1)




































- wielomiany stopnia
Ponieważ















gdy ,









gdy .
nm_slides-2.tex  Metody numeryczne  Janusz Szwabiński  8/10/2002  22:40  p.13/55
Wzór interpolacyjny Lagrange a (2)














Z warunku otrzymujemy





















nm_slides-2.tex  Metody numeryczne  Janusz Szwabiński  8/10/2002  22:40  p.14/55
Wzór interpolacyjny Lagrange a (3)
































gdzie








Twierdzenie o jednoznaczności

wielomian Lagrange a jest jedynym wielomianem


interpolacyjnym stopnia
nm_slides-2.tex  Metody numeryczne  Janusz Szwabiński  8/10/2002  22:40  p.15/55
Wzór interpolacyjny Lagrange a (4)
Przykład Szukamy wielomianu interpolacyjnego, który
przechodzi przez następujące punkty węzłowe:


-2 1 2 4


3 1 -3 8








































nm_slides-2.tex  Metody numeryczne  Janusz Szwabiński  8/10/2002  22:40  p.16/55
Wzór interpolacyjny Lagrange a (5)
Przykład
FUNCTION LAGRANGE(x,xa,ya) RESULT (wnx)
implicit none
double precision,dimension(:) :: xa,ya !punkty wezlowe
double precision :: x,wnx,om,w
integer :: i,j
wnx=0.0
om=1.0
do i=1,size(xa)
om=om*(x-xa(i))
w=1.0
do j=1, size(xa)
if(i .ne. j) w=w*(xa(i)-xa(j))
end do
wnx=wnx+ya(i)/(w*(x-xa(i)))
end do
wnx=wnx*om
END FUNCTION
nm_slides-2.tex  Metody numeryczne  Janusz Szwabiński  8/10/2002  22:40  p.17/55
Metoda Aitkena (1)





- wielomian stopnia pierwszego






przechodzący przez ,





- wielomian stopnia drugiego przechodzący






przez , ,







- wielomian stopnia przechodzący









przez ,
nm_slides-2.tex  Metody numeryczne  Janusz Szwabiński  8/10/2002  22:40  p.18/55
Metoda Aitkena (2)








































































nm_slides-2.tex  Metody numeryczne  Janusz Szwabiński  8/10/2002  22:40  p.19/55
Metoda Aitkena (3)
Schemat Aitkena:






















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







nm_slides-2.tex  Metody numeryczne  Janusz Szwabiński  8/10/2002  22:40  p.20/55
Metoda Aitkena (4)
Przykład Obliczyć metodą Aitkena wartość wielomianu







interpolacyjnego dla punktu , jeśli wielomian ten

przechodzi przez następujące punkty węzłowe:


0 1 3


1 3 2
Schemat Aitkena dla tego zadania ma postać:
0 1











1 3













3 2


nm_slides-2.tex  Metody numeryczne  Janusz Szwabiński  8/10/2002  22:40  p.21/55
Metoda Neville a (1)






- wielomian stopnia przechodzący








przez ,



Twierdzenie 4 Wielomian daje się przedstawić

wzorem rekurencyjnym






















nm_slides-2.tex  Metody numeryczne  Janusz Szwabiński  8/10/2002  22:40  p.22/55
Metoda Neville a (2)




Dowód Niech będzie prawą stroną powyższego równania.






Pokażemy, że ma własności wielomianu .






Widzimy, że stopień jest . Ponadto, zgodnie z definicją








wielomianów i mamy























a dla





















Zatem rzeczywiście ma cechy , co na mocy

twierdzenia o jednoznaczności kończy dowód.
nm_slides-2.tex  Metody numeryczne  Janusz Szwabiński  8/10/2002  22:40  p.23/55
Metoda Neville a (3)
Schemat Neville a:





































nm_slides-2.tex  Metody numeryczne  Janusz Szwabiński  8/10/2002  22:40  p.24/55
Metoda Neville a (4)
Przykład Zastosować metodę Neville a do poprzedniego
przykładu:


0 1 3


1 3 2





Schemat Neville a dla ma postać:

0 1




















1 3













3 2
nm_slides-2.tex  Metody numeryczne  Janusz Szwabiński  8/10/2002  22:40  p.25/55
Oszacowanie błędu wzoru interpolacyjnego (1)






Niech będzie funkcją razy różniczkowalną oraz







Twierdzenie 5














gdzie

















nm_slides-2.tex  Metody numeryczne  Janusz Szwabiński  8/10/2002  22:40  p.26/55
Oszacowanie błędu wzoru interpolacyjnego (2)
Twierdzenie 6 (Rolle a) Niech 1) funkcja będzie określona na




przedziale domkniętym ; 2) istnieje pochodna skończona





przynajmniej w przedziale otwartym ; 3) na końcach






przedziału funkcja przyjmuje wartości . Wówczas



między i można znalez
ć taki punkt ( ), że







nm_slides-2.tex  Metody numeryczne  Janusz Szwabiński  8/10/2002  22:40  p.27/55
Oszacowanie błędu wzoru interpolacyjnego (3)
Dowód (twierdzenia 5)

Wprowadz
my funkcję pomocniczą ( - pewna stała)
























Współczynnik dobieramy tak, aby pierwiastkiem funkcji


był również punkt , różny od węzłów interpolacji. Stąd













Mianownik w ostatnim wzorze jest różny od zera dla wszystkich








( ).
nm_slides-2.tex  Metody numeryczne  Janusz Szwabiński  8/10/2002  22:40  p.28/55
Oszacowanie błędu wzoru interpolacyjnego (4)
Dowód (ciąg dalszy)









ma w sumie miejsc zerowych , , , , .
Twierdzenia Rolle a





ma w każdym z podprzedziałów położonych między
pierwiastkami co najmniej jedno miejsce zerowe









w przedziale jest co najmniej




miejsc zerowych






co najmniej miejsc zerowych drugiej pochodnej
.
.
.
nm_slides-2.tex  Metody numeryczne  Janusz Szwabiński  8/10/2002  22:40  p.29/55
Oszacowanie błędu wzoru interpolacyjnego (5)
Dowód (ciąg dalszy)


istnieje co najmniej jeden punkt w przedziale












taki, że
Ponieważ





















więc
























nm_slides-2.tex  Metody numeryczne  Janusz Szwabiński  8/10/2002  22:40  p.30/55
Oszacowanie błędu wzoru interpolacyjnego (6)
Dowód (ciąg dalszy)
Stąd wynika



















zatem















gdzie

















nm_slides-2.tex  Metody numeryczne  Janusz Szwabiński  8/10/2002  22:40  p.31/55
Oszacowanie błędu wzoru interpolacyjnego (7)






Przykład Niech . Załóżmy, że znamy wartości
dokładne naszej funkcji w punktach










Wówczas


















Stąd np. dla mamy





















nm_slides-2.tex  Metody numeryczne  Janusz Szwabiński  8/10/2002  22:40  p.32/55
Wzór interpolacyjny Newtona
Metody Aitkena i Neville a:

wyznaczanie wartości wielomianu interpolacyjnego w danym
punkcie

niepraktyczne, jeśli punktów jest dużo
nm_slides-2.tex  Metody numeryczne  Janusz Szwabiński  8/10/2002  22:40  p.33/55
Ilorazy różnicowe (1)
Definicja Ilorazami różnicowymi pierwszego rzędu nazywamy
wyrażenia


























.
.
.


















nm_slides-2.tex  Metody numeryczne  Janusz Szwabiński  8/10/2002  22:40  p.34/55
Ilorazy różnicowe (2)
Definicja Ilorazami różnicowymi drugiego rzędu nazywamy
wyrażenia













.
.
.


















nm_slides-2.tex  Metody numeryczne  Janusz Szwabiński  8/10/2002  22:40  p.35/55
Ilorazy różnicowe (3)

Definicja Ilorazem różnicowym rzędu nazywamy






















dla oraz
nm_slides-2.tex  Metody numeryczne  Janusz Szwabiński  8/10/2002  22:40  p.36/55
Ilorazy różnicowe (4)





Ilorazy różnicowe
rzędu 1 rzędu 2 rzędu 3 rzędu 4











































nm_slides-2.tex  Metody numeryczne  Janusz Szwabiński  8/10/2002  22:40  p.37/55
Wzór Newtona (1)
Twierdzenie 7





















przy czym .
nm_slides-2.tex  Metody numeryczne  Janusz Szwabiński  8/10/2002  22:40  p.38/55
Wzór Newtona (2)



Dowód Dla mamy







zatem twierdzenie jest prawdziwe. Załóżmy teraz, że jest ono




prawdziwe dla pewnego . Aby pokazać prawdziwość







dla zauważmy najpierw, że różnica jest
wielomianem, który można przedstawić w postaci











gdzie jest najwyższym współczynnikiem (czyli

współczynnikiem przy najwyższej potędze ) wielomianu




.
nm_slides-2.tex  Metody numeryczne  Janusz Szwabiński  8/10/2002  22:40  p.39/55
Wzór Newtona (3)
Dowód (ciąg dalszy)
Według założenia indukcyjnego, najwyższymi współczynnikami



wielomianów oraz są odpowiednio








i . Ze wzoru Neville a wynika















zatem















Na mocy zasady indukcji matematycznej twierdzenie jest więc
udowodnione.
nm_slides-2.tex  Metody numeryczne  Janusz Szwabiński  8/10/2002  22:40  p.40/55
Wzór Newtona (4)
Przykład Szukamy wielomianu interpolacyjnego dla funkcji
określonej tablicą wartości:


0 2 3 4 6


1 3 2 5 7
Tworzymy tablicę ilorazów różnicowych dla tej funkcji:
nm_slides-2.tex  Metody numeryczne  Janusz Szwabiński  8/10/2002  22:40  p.41/55
Wzór Newtona (5)
Przykład (ciąg dalszy)







0 1
1



2 3


-1



3 2 2



3



4 5
1
6 7
nm_slides-2.tex  Metody numeryczne  Janusz Szwabiński  8/10/2002  22:40  p.42/55
Wzór Newtona (6)
Przykład (ciąg dalszy)



































nm_slides-2.tex  Metody numeryczne  Janusz Szwabiński  8/10/2002  22:40  p.43/55
Zbieżność procesów interpolacyjnych (1)
Definicja Mówimy, że metoda interpolacyjna jest zbieżna do





funkcji w punkcie , gdy















gdzie to funkcja interpolująca (niekoniecznie wielomian).
nm_slides-2.tex  Metody numeryczne  Janusz Szwabiński  8/10/2002  22:40  p.44/55
Zbieżność procesów interpolacyjnych (2)
1
y=|x|
W2(x)
W4(x)
W6(x)
W10(x)
0,5
0
-1 0 1
x
nm_slides-2.tex  Metody numeryczne  Janusz Szwabiński  8/10/2002  22:40  p.45/55
y
Interpolacja wymierna (1)




Mamy punktów węzłowych













Wartość funkcji przybliżamy funkcją wymierną
























spełniającą warunek









nm_slides-2.tex  Metody numeryczne  Janusz Szwabiński  8/10/2002  22:40  p.46/55
Interpolacja wymierna (2)
Uwaga, pułapka!
Z









można wnioskować, że














określa współczynniki , .
nm_slides-2.tex  Metody numeryczne  Janusz Szwabiński  8/10/2002  22:40  p.47/55
Interpolacja wymierna (3)



Przykład Niech oraz


0 1 2


1 2 2































Zakładając, że jest parametrem, oraz że , otrzymamy






nm_slides-2.tex  Metody numeryczne  Janusz Szwabiński  8/10/2002  22:40  p.48/55
Interpolacja wymierna (4)
Przykład (ciąg dalszy)
czyli















Dla mamy , a po uproszczeniu otrzymujemy











A zatem funkcja nie rozwiązuje zadania interpolacji.
nm_slides-2.tex  Metody numeryczne  Janusz Szwabiński  8/10/2002  22:40  p.49/55
Odwrotności różnic ilorazowych (1)
Definicja Odwrotnościami ilorazów różnicowych nazywamy
wielkości



































przy czym niektóre z nich mogą być nieskończone ze względu
na zerowanie się mianowników.
nm_slides-2.tex  Metody numeryczne  Janusz Szwabiński  8/10/2002  22:40  p.50/55
Odwrotności różnic ilorazowych (2)
Spełniona jest następująca własność:











































Stąd wynika




















nm_slides-2.tex  Metody numeryczne  Janusz Szwabiński  8/10/2002  22:40  p.51/55
Odwrotności różnic ilorazowych (3)
a zatem
























































co prowadzi do




















nm_slides-2.tex  Metody numeryczne  Janusz Szwabiński  8/10/2002  22:40  p.52/55
Odwrotności różnic ilorazowych (4)
Ostatecznie, dla naszego wyrażenia wymiernego otrzymujemy



















































nm_slides-2.tex  Metody numeryczne  Janusz Szwabiński  8/10/2002  22:40  p.53/55
Odwrotności różnic ilorazowych (5)




można więc przedstawić w postaci następującego
ułamka łańcuchowego:























nm_slides-2.tex  Metody numeryczne  Janusz Szwabiński  8/10/2002  22:40  p.54/55
Odwrotności różnic ilorazowych (6)
Przykład Mamy daną tabelę odwrotności ilorazów
różnicowych:




0 0


1 -1



2 -3


3 9

































nm_slides-2.tex  Metody numeryczne  Janusz Szwabiński  8/10/2002  22:40  p.55/55