Metody numeryczne
skrót wykładu
dr inż. Anna Barcz
Zakład Matematyki Stosowanej
kontakt: pokój 28
[e-mail]
konsultacje: środa 12.15 - 14.00
Metody numeryczne Szczecin - 2009-10-08 1
Zagadnienia
Działania na macierzach.
Rozkład w szereg Taylora.
Schemat Hornera.
Obliczanie rzędu macierzy.
Przeliczanie liczb (system dwójkowy/system dziesiętny).
Reprezentacja liczb (cecha, matysa).
Nadmiar, niedomiar, błąd bezwzględny i błąd względny.
Klasyfikacja błędów.
Stabilność i uwarunkowanie algorytmu.
Metody numeryczne Szczecin - 2009-10-08 2
Literatura
'
Kincaid D., Cheney W.: Analiza numeryczna, WNT,
Warszawa, 2006
'
Fortuna Z., Macukow B., WÄ…sowski J.: Metody
numeryczne, WNT, Warszawa, 1993
'
Popov O.: Metody numeryczne i optymalizacja,
WIPS,Szczecin, 2003
'
Bożek B.: Metody obliczeniowe i ich komputerowa
realizacja, Wydawnictwo AGH, Kraków, 2005
'
Jankowscy J. i M.: Przegląd metod i algorytmów
numerycznych, WNT, Warszawa, 1988
'
Palczewski A.: Równania różniczkowe zwyczajne, WNT,
Warszawa, 2004
Metody numeryczne Szczecin - 2009-10-08 3
Czym jest analiza numeryczna?
Analiza numeryczna obejmuje:
tworzenie, badanie i analizÄ™
algorytmów, których celem jest otrzymywanie rozwiązań
numerycznych różnorodnych zadań matematycznych.
Analiza numeryczna = matematyka obliczeń naukowych
Metody numeryczne Szczecin - 2009-10-08 4
Co już trzeba wiedzieć?
Jaką funkcję nazywany ciągłą i jakie własności ma taka funkcja?
lim f śą xźą= f śącźą
Mówimy, że funkcja f jest ciągła w c, jeśli
x Śąc
Funkcja ciągła f w przedziale [a,b] przyjmuje w nim wszystkie
wartości zawarte między f(a) i f(b).
Pochodną funkcji f w c (jeśli istnieje) określamy wzorem
f śą xźą- f śącźą
'
f śącźą=lim
x-c
x Śą c
C śą!źą , C1śą!źą , Cnśą!źą , ‹Ä… ,C"śą!źą
Zbiory
Metody numeryczne Szczecin - 2009-10-08 5
Co już trzeba wiedzieć?
Jak wygląda wzór Taylora i jak go zastosować?
n
1
śąk źą
f śąxźą= f śącźąśą x-cźąkƒÄ…Rnśą xźą
"
k !
k=0
1
śąnƒÄ…1źą
Rnśą xźą= f śąÄąźąśą x-cźąnƒÄ…1
śąnƒÄ…1źą!
śąnƒÄ…1źą
f "Cn[a ,b] , f istnieje wśąa ,bźą
Twierdzenie o wartości średniej => wzór Taylora dla n=0
f śąxƒÄ…hźą- f śą x-hźą
'
f śąxźąH"
2Å"h
Metody numeryczne Szczecin - 2009-10-08 6
Co już trzeba wiedzieć?
Co nieco o wektorach i macierzach
Wektor określony w przestrzeni Rn
 uporządkowany zbiór liczb rzeczywistych.
Układ wektorów x1, x2,..., xn jest liniowo zależny, jeśli istnieją skalary
c1, c2, ..., cn nie wszystkie równe zeru i spełniona jest równość:
n
c Å"x =0
"
j j
j=1
n
Przykład: x1 jako liniowa kombinacja pozostałych wektorów
x1= b Å"x
"
j j
j=2
Przestrzeń wektorowa o wymiarze n 
zbiór wszystkich n-wymiarowych wektorów.
Metody numeryczne Szczecin - 2009-10-08 7
Co już trzeba wiedzieć?
Jak dodawać, odejmować, mnożyć i transponować macierze?
Zanim zaczniesz wykonywać operacje arytmetyczne
sprawdz
rozmiary macierzy!
dim C
dim A dim B
-
+
*
n x n n x n n x n n x n n x n
n x p m x q X X X
n x p n x p n x p n x p X
n x p p x n X X n x n
n x p p x m X X n x m
Uwaga:
AÅ"B`"BÅ"A
Transpozycja  wzajemna wymiana wierszy i kolumn
AT
Metody numeryczne Szczecin - 2009-10-08 8
Co już trzeba wiedzieć?
Jak obliczyć rząd macierzy?
Wyznacznik k-tego rzędu, składający się z elementów macierzy
położonych na skrzyżowaniu k wierszy i k kolumn nazywa się
minorem k-tego rzędu.
RzÄ…d macierzy A
 najwyższy rząd różnych od zera minorów macierzy A.
Przykład: Znalez
ć rząd macierzy A
1 1 2
9 minorów I-go rzędu,
4 minory II-go rzędu,
A=
2 1 4
1 minor III-go rzędu
śą źą
3 0 6
Metody numeryczne Szczecin - 2009-10-08 9
Co już trzeba wiedzieć?
Jak odróżnić macierz osobliwą od nieosobliwej?
Uwaga: dotyczy macierzy kwadratowych
Macierz nieosobliwa
det A`"0
det A=0
Macierz osobliwa
Macierz nieosobliwa ma macierz odwrotnÄ…, oznaczanÄ… przez A-1.
AÅ"A-1=A-1Å"A=E
1
ęą
A-1= A
det A
Metody numeryczne Szczecin - 2009-10-08 10
Co już trzeba wiedzieć?
Co to jest schemat Hornera?
f śąxźą=a0ƒÄ…a1 xƒÄ…‹Ä…ƒÄ…an-1 xn-1ƒÄ…an xn
Liczba operacji: 2n-1 mnożeń, n dodawań
f śąxźą=a0ƒÄ…śąa1ƒÄ…x śąa2ƒÄ…‹Ä…ƒÄ…xśąan-1ƒÄ…xśąanźąźą‹Ä…źąźą
Liczba operacji: n mnożeń, n dodawań
an an-1 ‹Ä… a1 a0
z0 z0bn-1 ‹Ä… z0b1 z0b0
bn-1 bn-2 ‹Ä… b0 b-1
Metody numeryczne Szczecin - 2009-10-08 11
Numeryczna reprezentacja liczb
Przeliczanie liczby dziesiętnej na liczbę binarną
139 : 2 = 69 reszta 1 (1=z0)
69 : 2 = 34 reszta 1 (1=z1)
34 : 2 = 17 reszta 0 (0=z2)
17 : 2 = 8 reszta 1
8 : 2 = 4 reszta 0
4 : 2 = 2 reszta 0
2 : 2 = 1 reszta 0
1 : 2 = 0 reszta 1 (1=z7)
1 1 2
2 1 4=0
#"#"
3 06
13910 = 100010112
Metody numeryczne Szczecin - 2009-10-08 12
Numeryczna reprezentacja liczb
Przeliczanie ułamka dziesiętnego na ułamek binarny
0,8125 * 2 = 1,625 (1=z-1)
0,625 * 2 = 1,25 (1=z-2)
0,25 * 2 = 0,5 (0=z-3)
0,5 * 2 = 1,0 (1=z-4)
0,0 * 2 = 0,0
1 1 2
0,812510 = 0,11012
2 1 4=0
#"#"
3 06
Metody numeryczne Szczecin - 2009-10-08 13
Numeryczna reprezentacja liczb
Zapis stałopozycyjny
Dowolną liczbę całkowitą l możemy przedstawić w postaci
rozwinięcia dwójkowego
n
en`"0 dla l`"0
l=s ei 2i
"
i=0
gdzie:
s  znak liczby (s=+1 lub s=-1),
ei  cyfry dwójkowe (ei=0 lub ei=1).
Jeśli na reprezentację liczby przeznaczymy d+1 bitów to możemy
dokładnie reprezentować liczby całkowite z przedziału
)#-2dƒÄ…1, 2d-1*#
Metody numeryczne Szczecin - 2009-10-08 14
Numeryczna reprezentacja liczb
Zapis zmiennopozycyjny
Dowolną liczbę rzeczywistą możemy przedstawić w postaci
x`"0
x=sÅ"2cÅ"m
gdzie:
s  znak liczby (s=+1 lub s=-1),
c  liczba całkowita  cecha,
m  liczba rzeczywista z przedziału <0.5, 1>  mantysa
Cechę zapisuje się w sposób stałopozycyjny na d-t bitach słowa.
Mantysę na pozostałych t bitach.
sc ed-t-1 ed-t-2 ... e0 e-1 e-2 ... e-t
s
cecha
mantysa
Metody numeryczne Szczecin - 2009-10-08 15
Numeryczna reprezentacja liczb
Zapis zmiennopozycyjny
W idealnej sytuacji mantysa:
"
e-1=1, e-i=0 lub 1 dla iÄ…1
m= e-iÅ"2-i
"
i=1
A tak naprawdÄ™:
t
mt= e-iÅ"2-iƒÄ…e-śątƒÄ…1źąÅ"2-t
"
i=1
BÅ‚Ä…d:
1Å"2
-t
#"m-mt#"Ä…Ä…
2
Metody numeryczne Szczecin - 2009-10-08 16
Elementy teorii błędu obliczeń
Błąd bezwzględny
x
różnica pomiędzy rzeczywistą (dokładną) wartością
x
ęą
i jej przybliżoną wartością
ęą
­Ä…x=x-x
Błąd względny
#"x-x#"
ęą
ºÄ…x=
#"x#"
Metody numeryczne Szczecin - 2009-10-08 17
Numeryczna reprezentacja liczb
Zapis zmiennopozycyjny
x`"0
dla błąd względny
fl śą xźą-x
Ä…Ä…2-t
#" #"
x
co jest równoznaczne relacji
flśą xźą=x śą1ƒÄ…Ïąźą
#"ÏÄ…#"Ä…Ä…2-t
fl(x)  reprezentacja zmiennopozycyjna liczby x  liczba maszynowa
Nie każda liczba rzeczywista jest liczbą maszynową!
Metody numeryczne Szczecin - 2009-10-08 18
Numeryczna reprezentacja liczb
Zapis zmiennopozycyjny
Liczba cyfr mantysy decyduje o dokładności przedstawienia liczb,
liczba cyfr cechy określa zakres reprezentowanych liczb.
c")#cmin ,cmax*#
Jeżeli założymy, że cecha gdzie
1
mt" ,1
i mantysa to
cmax=-cmin=2d -t-1
)# *#
2
możemy reprezentować liczby spełniające zależność
1
min max
2c Ä…Ä…#"x#""Ä…2c
2
Metody numeryczne Szczecin - 2009-10-08 19
Numeryczna reprezentacja liczb
Zapis zmiennopozycyjny
NIEDOMIAR  reprezentowany jako zero
Działanie, którego wynik jest różny od zera, ale ma zbyt małą cechę.
NADMIAR  reprezentowany jako nieskończoność
Działanie, którego wynik ma zbyt dużą cechę.
Nieskończoność traktowana jest jak bardzo duża liczba i wynikiem
xƒÄ…" , xÅ"" , "/ x ƒÄ…"
działań jest
Jeśli nieskończoność jest argumentem działania, które nie ma
sensu, to wykonanie programu jest automatycznie przerwane.
Metody numeryczne Szczecin - 2009-10-08 20
Numeryczna reprezentacja liczb
Działania arytmetyczne na liczbach zmiennopozycyjnych
W dobrze zaprojektowanym komputerze wyniki czterech działań na
liczbach maszynowych spełniają związek
flśą x ° yźą=śą x ° yźąśą1ƒÄ…Ïąźą , #"ÏÄ…#"Ä…Ä…2-t
gdy x i y nie sÄ… liczbami maszynowymi otrzymujemy
flśą fl śą xźą° flśą yźąźą=śą xśą1ƒÄ…ÏÄ…1źą° yśą1ƒÄ…ÏÄ…2źąźąśą1ƒÄ…ÏÄ…3źą , #"ÏÄ…i#"Ä…Ä…2-t
Metody numeryczne Szczecin - 2009-10-08 21
Elementy teorii błędu obliczeń
Stabilność i uwarunkowanie algorytmu
Algorytm numeryczny nazywamy niestabilnym
jeśli małe błędy popełnione na jakimś etapie obliczeń
rosną w następnych etapach i poważnie zniekształcają
ostateczne wyniki. Przy badaniu stabilności
wykorzystuje sie błędy względne.
Algorytm numeryczny jest z
le uwarunkowany
jeśli małe zmiany danych początkowych wywołują duże
zmiany wyników. Dla pewnych typów zadań można
określić wskaz
nik uwarunkowania. Jeśli jest on duży to
zadanie jest z
le uwarunkowane.
Uwarunkowanie jest cechÄ… samego zadania i nie jest
zwiÄ…zane z metodÄ… jego rozwiÄ…zania.
Metody numeryczne Szczecin - 2009-10-08 22
Elementy teorii błędu obliczeń
błąd całkowity
błąd wejścia błąd metody błąd zaokrąglenia
błąd urwania procedury iteracyjnej błąd dyskretyzacji
Metody numeryczne Szczecin - 2009-10-08 23
Elementy teorii błędu obliczeń
błąd wejścia
'
niedokładność pomiarów,
'
przeoczenia, błędne odczyty, błędy drukarskie,
'
brak możliwości przedstawienia przez skończoną liczbę
cyfr znaczÄ…cych, np.
1
Ćą ,e ,
10
2
Metody numeryczne Szczecin - 2009-10-08 24
Elementy teorii błędu obliczeń
błąd wejścia dla podstawowych działań arytmetycznych
błąd bezwzględny
ąśą xą yźą=ąśą xźąąąśą yźą
ąśą xyźą= y ąśąxźąƒÄ…x ąśą yźąƒÄ…ąśą xźąąśą yźą
x 1 x
Ä… = ąśąxźą- ąśą yźąƒÄ…R
śą źą
y y
y2
Metody numeryczne Szczecin - 2009-10-08 25
Elementy teorii błędu obliczeń
błąd wejścia dla podstawowych działań arytmetycznych
błąd względny
x ąrelśąxźąą y ąrel śą yźą
ąrelśą xą yźą=
xÄ… y
Ä…relśą xyźą=Ä…relśą xźąƒÄ…Ä…relśą yźąƒÄ…Ä…relśą xźąąrelśą yźą
Ä…rel x =Ä…relśą xźą-Ä…relśą yźąƒÄ…R
śą źą
y
Metody numeryczne Szczecin - 2009-10-08 26
Elementy teorii błędu obliczeń
błąd wejścia dla podstawowych działań arytmetycznych
Mały błąd względny danych wejściowych podczas mnożenia i
dzielenia powoduje mały błąd względny wyniku.
Mały błąd względny danych wejściowych podczas dodawania i
odejmowania może stać się duży, jeśli
#" #"
xÄ… y j"#"x#"ƒÄ…#"y#"
Niebezpieczeństwo kasowania pozycji!
Metody numeryczne Szczecin - 2009-10-08 27
Elementy teorii błędu obliczeń
Odejmowanie bliskich wielkości (kasowanie)
1. UNIKAĆ!
2. przekształcać
Przykład:
problem dla małych x
x2
y= x2ƒÄ…1-1 Śą
ćą
x2ƒÄ…1ƒÄ…1
ćą
x3 - x5 ƒÄ… x7 -‹Ä…
y=x-sinx Śą
3! 5! 7!
Metody numeryczne Szczecin - 2009-10-08 28
Elementy teorii błędu obliczeń
błąd metody
'
konieczność przybliżania wartości ciągłych,
'
nie zależy od błędów wejścia i zaokrąglenia
'
konieczność reprezentowania procesów nieskończonych
x3 x5 x7
sin x=x- ƒÄ… - ƒÄ…‹Ä…
3! 5! 7!
Metody numeryczne Szczecin - 2009-10-08 29
Elementy teorii błędu obliczeń
błąd metody / błąd urwania procedury iteracyjnej
'
kontrola liczby kroków iteracji, urwanie po określonej
liczbie cykli iteracji, również wtedy gdy nie została
jeszcze osiągnięta żądana dokładność,
'
śledzenie przebiegu rozwiązania na ekranie,
'
wykorzystanie znanych właściwości rozwiązania
problemu,
'
zbadanie możliwości skalowania zmiennych lub funkcji,
'
przeprowadzanie większej liczby testów, zmieniając
długość kroku, warunek stopu, wartości startowe, itd.
Metody numeryczne Szczecin - 2009-10-08 30
Elementy teorii błędu obliczeń
błąd metody / błąd dyskretyzacji
1 1
0.5 0.5
0 0
T=1
-0.5 -0.5
-1 -1
0 1 2 3 4 0 1 2 3 4
t t
1 1
0.5 0.5
0 0
T=0.5
-0.5 -0.5
-1 -1
0 1 2 3 4 0 1 2 3 4
t t
1 1
0.5 0.5
0 0
T=0.5
-0.5 -0.5
-1 -1
0 1 2 3 4 0 1 2 3 4
t t
Metody numeryczne Szczecin - 2009-10-08 31
*
f(t)
f (t)
*
f(t)
f (t)
*
f(t)
f (t)
Elementy teorii błędu obliczeń
błąd metody / błąd zaokrąglenia
dotyczÄ… liczb rzeczywistych!
Dysponujemy maszyną z ograniczoną długością siatki, np.
Realizujmy dodawanie:
9,2654
ƒÄ…7,6125
16,4279
zaokrąglenie symetryczne odrzucenie (obcięcie)
16,428 16,427
Metody numeryczne Szczecin - 2009-10-08 32
Elementy teorii błędu obliczeń
błąd metody / błąd zaokrąglenia
'
wyrównywanie rzędów przy dodawaniu i odejmowaniu
1. porównanie rzędów,
2. przesunięcie w prawo mantysy o mniejszej wartości
bezwzględnej tak aby wyrównać rzędy
Przykład: dodawanie dwóch liczb, dysponujemy pięciopozycyjnym
przedstawieniem mantysy
162,4ƒÄ…1,769Śą
0,1624Å"103ƒÄ…0,1769Å"101Śą
0,1624Å"103ƒÄ…0,0017Å"103=0,1641Å"103
0,164169Å"103
wynik dokładny
Metody numeryczne Szczecin - 2009-10-08 33