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