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