Metody numeryczne
skrót wykładu
dr inż. Anna Barcz
Zakład Matematyki Stosowanej
kontakt: pokój 28
[e-mail]
konsultacje: środa 12.00-14.00
1
Metody numeryczne, II rok INFORMATYKA, Szczecin - 2009-10-08
Zagadnienia
Zadnie interpolacji.
Macierz Vandermonda.
Zjawisko Rungego.
Błąd interpolacji wielomianowej.
2
Metody numeryczne, II rok INFORMATYKA, Szczecin - 2009-10-08
Przybliżanie funkcji  ZADANIE INTERPOLACJI
Zadanie interpolacji:
wyznacz funkcję g(x), która w punktach xi, tzw. węzłach, przyjmuje
ustalone wartości yi, czyli spełnia warunek interpolacji
g śąxiźą= yi , 0ąąiąąn.
Pojęcia do zapamiętania:
'
węzły
'
funkcja interpolująca
3
Metody numeryczne, II rok INFORMATYKA, Szczecin - 2009-10-08
Przybliżanie funkcji  ZADANIE INTERPOLACJI
Funkcje interpolujące:
'
wielomiany algebraiczne,
'
wielomiany trygonometryczne,
'
wielomiany ortogonalne,
'
funkcje sklejane.
4
Metody numeryczne, II rok INFORMATYKA, Szczecin - 2009-10-08
Przybliżanie funkcji  ZADANIE INTERPOLACJI
Postacie wielomianu algebraicznego
'
postać naturalna (rozwinięcie potęgowe)
n
wśą xźą= ak xk
"
k=0
obliczanie całek, pochodnych i działań na wielomianach
5
Metody numeryczne, II rok INFORMATYKA, Szczecin - 2009-10-08
Przybliżanie funkcji  ZADANIE INTERPOLACJI
Postacie wielomianu algebraicznego
'
postać Newtona
n
wśą xźą= bk pkśą xźą
"
k=0
gdzie:
df
p0śą xźą=1
df
pk śąxźą=śąx-x0źąśą x-x1źą�ąśąx-xk-1źą
dla k=1,2 ,�ą,n
6
Metody numeryczne, II rok INFORMATYKA, Szczecin - 2009-10-08
INTERPOLACJA WIELOMIANOWA
Dana jest funkcja f(x) i wielomian
pśą xźą=a0�ąa1 x�ąa2 x2�ą�ą�ąan xn
Zadanie interpolacji  znalez
ć wielomian p możliwie najniższego
stopnia taki, że dla danych n+1 punktów (xi , yi ) jest
pśą xiźą= yi , 0ąąiąąn.
Mówimy wtedy, że wielomian p interpoluje wartości yk w węzłach xk.
7
Metody numeryczne, II rok INFORMATYKA, Szczecin - 2009-10-08
INTERPOLACJA WIELOMIANOWA
Twierdzenie
Istnieje dokładnie jeden wielomian interpolacyjny
stopnia co najwyżej n (ne"0), który
w punktach x0, x1, ... , xn przyjmuje wartości y0, y1, ..., yn.
8
Metody numeryczne, II rok INFORMATYKA, Szczecin - 2009-10-08
INTERPOLACJA WIELOMIANOWA
Dowód
Założenia:
'
dane jest n+1 węzłów, w których znane są wartości pewnej funkcji
y=f(x),
'
węzły interpolacji są rozmieszczone dowolnie w przedziale ,
x0'
Szukany wielomian ma postać:
W śąxźą=a0�ąa1 x�ąa2 x2�ą�ą�ąan xn
n
9
Metody numeryczne, II rok INFORMATYKA, Szczecin - 2009-10-08
INTERPOLACJA WIELOMIANOWA
Korzystając z warunków
f śąx0źą= y0 , f śą x1źą= y1 , �ą , f śą xnźą= yn
otrzymujemy:
2
a0�ąa1 x0�ąa2 x0�ą�ą�ąan xn= y0
0
2
a0�ąa1 x1�ąa2 x1�ą�ą�ąan xn= y1
1
�ą
a0�ąa1 xn�ąa2 x2�ą�ą�ąan xn= yn
n n
n+1 równań, n+1 niewiadomych, poszukujemy współczynników a0, a1, ... , an
10
Metody numeryczne, II rok INFORMATYKA, Szczecin - 2009-10-08
INTERPOLACJA WIELOMIANOWA
W postaci macierzowej
1 x0 x2 x3 �ą xn a0
y0
0 0 0
2 n
1 x1 x1 x3 �ą x1 �" a1 = y1
1
�ą �ą �ą �ą �ą �ą �ą �ą
[ ][ ]
[ ]
yn
1 xn x2 x3 �ą xn an
n n n
V�"A=Y
V  macierz Vandermonde'a,
11
Metody numeryczne, II rok INFORMATYKA, Szczecin - 2009-10-08
INTERPOLACJA WIELOMIANOWA
xi`"x
i`" j
Jeżeli założymy, że dla to
j
det śąV źą= śąxi-x źą`"0
"
j
0ąą j"ąiąąn
Układ równań ma dokładnie jedno rozwiązanie.
12
Metody numeryczne, II rok INFORMATYKA, Szczecin - 2009-10-08
INTERPOLACJA WIELOMIANOWA
Wartości współczynników według twierdzenia Cramera:
n
1
ai= y Dij
"
j
D
j=0
D  wyznacznik macierzy Vandermonde'a,
Dij  dopełnienia algebraiczne elementów i-tej kolumny macierzy A
KONIEC DOWODU
13
Metody numeryczne, II rok INFORMATYKA, Szczecin - 2009-10-08
INTERPOLACJA WIELOMIANOWA
Wzór interpolacyjny Lagrange'a
n
śąx-x0źąśą x-x1źą�ąśąx-x źąśą x-x źą�ąśą x-xnźą
j-1 j�ą1
W śąxźą= y
"
n j
śąx -x0źąśąx -x1źą�ąśą x -x źąśąx -x źą�ąśą x -xnźą
j=0
j j j j-1 j j�ą1 j
Wielomian Lagrange'a jest jedynym wielomianem stopnia co najwyżej n.
W sposób jawny zależy liniowo od zadanych wartości funkcji yj.
14
Metody numeryczne, II rok INFORMATYKA, Szczecin - 2009-10-08
INTERPOLACJA WIELOMIANOWA
Wzór interpolacyjny Newtona
Funkcja f(x) jest określona za pomocą węzłów x0, x1, ... , xn i wartości
xi`"x
funkcji w tych węzłach f(x0), f(x1), ... , f(xn). Dodatkowo
j
i`" j
�ą xi=xi�ą1-xi
dla i różnice nie są na ogół stałe.
15
Metody numeryczne, II rok INFORMATYKA, Szczecin - 2009-10-08
INTERPOLACJA WIELOMIANOWA
Wzór interpolacyjny Newtona
Ilorazy różnicowe pierwszego rzędu
f śą x1źą- f śą x0źą
f [ x0 , x1]=
x1-x0
f śą x2źą- f śą x1źą
f [ x1 , x2]=
x2-x1
�ą�ą�ą�ą
f śą xnźą- f śą xn-1źą
f [ xn-1 , xn]=
xn-xn-1
16
Metody numeryczne, II rok INFORMATYKA, Szczecin - 2009-10-08
INTERPOLACJA WIELOMIANOWA
Wzór interpolacyjny Newtona
Ilorazy różnicowe drugiego rzędu
f [ x1 , x2]- f [ x0 , x1]
f [ x0 , x1 , x2]=
x2-x0
�ą�ą�ą�ą
f [ xn-1 , xn]- f [ xn-2 , xn-1]
f [ xn-2 , xn-1 , xn]=
xn-xn-2
17
Metody numeryczne, II rok INFORMATYKA, Szczecin - 2009-10-08
INTERPOLACJA WIELOMIANOWA
Wzór interpolacyjny Newtona
Ilorazy różnicowe rzędu n
f [ xi�ą1 , xi�ą2 ,�ą, xi�ąn]- f [ xi , xi�ą1 ,�ą, xi�ąn-1]
f [ xi , xi�ą1 ,�ą, xi�ąn]=
xi�ąn-xi
n=1,2 ,�ą i=0,1,2 ,�ą
18
Metody numeryczne, II rok INFORMATYKA, Szczecin - 2009-10-08
INTERPOLACJA WIELOMIANOWA
Wzór interpolacyjny Newtona
Tablica ilorazów różnicowych dla 4 węzłów
x0 f śą x0źą f [ x0 , x1] f [ x0 , x1 , x2] f [ x0 , x1 , x2 , x3]
x1 f śą x1źą f [ x1 , x2] f [ x1 , x2 , x3]
x2 f śąx2źą f [ x2 , x3]
x3 f śą x3źą
19
Metody numeryczne, II rok INFORMATYKA, Szczecin - 2009-10-08
INTERPOLACJA WIELOMIANOWA
Wzór interpolacyjny Newtona z ilorazami różnicowymi
W śąxźą= f śą x0źą�ą f [ x0 , x1]�ą0śą xźą�ą f [ x0 , x1 , x2]�ą1śą xźą�ą
n
�ą�ą f [ x0 , x1 ,�ą, xn]�ąn-1śą xźą
�ą0śąxźą=śąx-x0źą
�ą1śąxźą=śą x-x0źąśą x-x1źą
�ą�ą�ą
�ąn-1śąxźą=śą x-x0źąśą x-x1źą�ąśą x-xn-1źą
20
Metody numeryczne, II rok INFORMATYKA, Szczecin - 2009-10-08
INTERPOLACJA WIELOMIANOWA
Błąd interpolacji wielomianowej
Twierdzenie
p"ąąn
Jeśli , a wielomian interpoluje
f "Cn�ą1[a , b]
wartości funkcji f w n+1 różnych punktach x0, x1, ... , xn przedziału
�ąx"śąa , bźą
x"[a ,b]
[a,b], to dla każdego istnieje takie , że
n
1
śąn�ą1źą
f śąxźą- pśąxźą= f śą�ąxźą śą x-xiźą
"
śąn�ą1źą!
i=0
21
Metody numeryczne, II rok INFORMATYKA, Szczecin - 2009-10-08
INTERPOLACJA WIELOMIANOWA
Błąd interpolacji wielomianowej
Mn+1 - kres górny modułu (n+1) pochodnej funkcji f na przedziale [a,b]
n�ą1
M = sup #" f śą xźą#"
n�ą1
x"[a , b]
n
1
#" f śą xźą- pśą xźą#"ąą M śą x-xiźą
"
n�ą1
śąn�ą1źą!
i=0
22
Metody numeryczne, II rok INFORMATYKA, Szczecin - 2009-10-08
INTERPOLACJA WIELOMIANOWA
Błąd interpolacji wielomianowej
Przykład
Ocenić z jaką dokładnością można obliczyć wartość ln(100,5) przy użyciu wzoru
interpolacyjnego Lagrange'a, jeżeli dane są wartości ln(100), ln(101), ln(102) i
ln(103).
śą4źą
f śąxźą=ln x , n=3, a=100, b=103, f =-6
Dane
x4
Obliczenia
6
4
M = sup #" f śą xźą#"=
4
x"[100,103]
1004
#"ln100,5-W śą100,5źą#"ąą1006�"4 !�"0,5�"0,5�"1,5�"2,5H"2,344�"10-9
4
23
Metody numeryczne, II rok INFORMATYKA, Szczecin - 2009-10-08