skrot MN w2


Metody numeryczne
skrót wykładu
dr inż. Anna Barcz
Zakład Matematyki Stosowanej
kontakt: pokój 28
abarcz@wi.zut.edu.pl
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


Wyszukiwarka

Podobne podstrony:
skrot MN w3
skrot MN w4
skrot MN w1
skrot MN w5
skrot MN w6
MB w2
zj w2
Mac Dre All?mn?y
skrot prospektu arka bz wbk akcji
The Leader And The?mned
w2 2
MN w1 Minimum funkcji
SD przykłady do w2
Skrót ustawy z 13 czerwca 2013 r o gospodarce opakowaniami i odpadami opakowaniowymi
DROGI w2 w3 tyczenie
w2
W2?
metody numeryczne i w2

więcej podobnych podstron