2013-10-26
METODY NUMERYCZNE
Wykład 2.
Analiza błędów w metodach numerycznych
1
Met.Numer. wykład 2
Po co wprowadzamy liczby w formacie
zmiennoprzecinkowym (floating point)?
" Przykład 1. W jaki sposób można zapisać liczbę 256.78 na
5-ciu miejscach?
.
2 5 6 7 8
Jak można zapisać najmniejszą liczbę w tym formacie?
0 0 0 . 0 0
Jak można zapisać największą liczbę w tym formacie?
9 9 9 . 9 9
2
Met.Numer. wykład 2
Po co wprowadzamy liczby w formacie
zmiennoprzecinkowym (floating point)?
" Przykład 2. W jaki sposób można zapisać liczbę 256.786
na 5-ciu miejscach?
zaokrąglenie (rounded off)
2 5 6 . 7 9
urwanie (chopped)
2 5 6 . 7 8
Wniosek: Błąd jest mniejszy niż 0.01
3
Met.Numer. wykład 2
1
2013-10-26
Jaki błąd popełniamy?
Błąd bezwzględny
x - xo
wielkość dokładna lub rzeczywista xo
Błąd względny - xo
x
xo
Obliczenia:
x - xo 256.79 - 256.786
�t = �100% = �100% = 0.001558%
xo 256.786
4
Met.Numer. wykład 2
Jaki błąd popełniamy?
Względne błędy wielkości małych są duże.
Porównajmy:
x - xo 256.79 - 256.786
�t = �100% = �100% = 0.001558%
xo 256.786
x - xo 3.55 - 3.546
�t = �100% = �100% = 0.11280%
xo 3.546
Błędy bezwzględne są jednakowe:
x - xo = 256.786 - 256.79 = 3.546 - 3.55 = 0.004
5
Met.Numer. wykład 2
Jak utrzymać błędy względne na podobnym
poziomie?
Można przedstawić liczbę w postaci:
znak � mantysa �10wykł
lub
znak � mantysa � 2wykł
czyli
256.78 zapisujemy jako + 2.5678�102
0.003678 zapisujemy jako+ 3.678�10-3
- 256.78 zapisujemy jako - 2.5678�102
6
Met.Numer. wykład 2
2
2013-10-26
Co zyskujemy stosując zapis
zmiennoprzecinkowy?
Zwiększa się zakres liczb, które możemy zapisać
Jeżeli użyjemy tylko 5 miejsc do zapisu liczby (dodatniej o
dodatnim wykładniku) to najmniejsza liczba zapisana to 1 a
największa 9.999�109.
9 9 9 9 9
wykładnik
mantysa
Zakres możliwych do zapisania liczb zwiększył się od 999.99 do
9.999�109.
7
Met.Numer. wykład 2
Co tracimy stosując zapis
zmiennoprzecinkowy?
Dokładność (precyzję).
Dlaczego?
Liczba 256.78 będzie przedstawiona jako 2.5678�102 i na pięciu
miejscach:
2 5 6 8 2
wykładnik
mantysa
Wystąpi błąd zaokrąglenia.
8
Met.Numer. wykład 2
Przykład do samodzielnego rozwiązania
1. Proszę przedstawić liczbę 576329.78 na sześciu miejscach
stosując: a) metodą zaokrąglenia b) urywania (chopping)
wykładnik
mantysa
2. Proszę oszacować błąd bezwzględny i względny obu metod
3. Porównać z przypadkiem gdy dysponujemy jedynie pięcioma
miejscami. Wyciągnąć wnioski
9
Met.Numer. wykład 2
3
2013-10-26
Arytmetyka zmiennoprzecinkowa-
system dziesiętny
wykładnik będący
Postać liczby liczbą całkowitą
� � m�10e
znak liczby (-1 lub +1)
mantysa (1)10d"m<(10)10
Przykład
� = -1
- 2.5678�102
m = 2.5678
e = 2
10
Met.Numer. wykład 2
Arytmetyka zmiennoprzecinkowa-
system dwójkowy
wykładnik będący
Postać liczby liczbą całkowitą
�� m� 2e
znak liczby (0 dla
mantysa (1)2d"m<(2)2
dodatniej lub 1 dla
ujemnej liczby)
Przykład
� = 0
m = 1011011
(1.1011011)2 � 2(101)2
e = 101
1 nie jest zapisywane
11
Met.Numer. wykład 2
Przykład
Mamy słowo 9-bitowe
pierwszy bit odpowiada znakowi liczby,
drugi bit  znakowi wykładnika,
następne cztery bity kodują mantysę,
ostatnie trzy bity zapisują wykładnik
znak liczby mantysa
wykładnik
znak wykładnika
Znajdz
liczbę (w postaci dziesiętnej), która jest przedstawiona w
podany sposób.
12
Met.Numer. wykład 2
4
0
0
2013-10-26
Rozwiązanie przykładu
0 0 1 0 1 1 1 0 1
(1.1011) �(101) = (1.1011) � 25 = (54)10
2 2 2
nie jest
Dla zapisu liczby 54.75 trzeba mieć
zapisywane
7 miejsc dla mantysy.
(54.75) = (110110.11) = (1.1011011) � 25
10 2 2
E" (1.1011) �(101)
2 2
13
Met.Numer. wykład 2
Co to jest � maszyny cyfrowej?
Dla każdej maszyny cyfrowej definiuje się parametr epsilon �
określający dokładność obliczeń:
� = N- t
gdzie: N=2 (w zapisie dwójkowym), N=10 (w zapisie
dziesiętnym), t jest liczbą bitów w mantysie liczby
� jest tym mniejsze im więcej bitów przeznaczono na
reprezentowanie mantysy M
Epsilon � można traktować jako parametr charakteryzujący
dokładność obliczeniową maszyny (im mniejsze � tym większa
dokładność).
Podwójna precyzja (Fortran) �DP = �2
14
Met.Numer. wykład 2
Co to jest � maszyny cyfrowej?
Epsilon � jest to najmniejsza liczba, która po dodaniu do 1.000
produkuje liczbę, którą można przedstawić jako różną od
1.000.
w
Przykład: słowo dziesięciobitowe
x = M � N
0 0 0 0 0 0 0 0 0 0
= (1)
10
wykładnik
mantysa
znak liczby
znak wykładnika
następna
0 0 0 0 0 0 0 0 0 1
= (1.0001) = (1.0625)
2 10
liczba
"mach =1.0625 -1 = 2-4
15
Met.Numer. wykład 2
5
2013-10-26
Pojedyncza precyzja w formacie IEEE-754
(Institute of Electrical and Electronics Engineers)
32 bity dla pojedynczej precyzji
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
znak
wykładnik mantysa (m)
(s)
(e )
Liczba = (-1)s �(1.m) � 2e'-127
2
16
Met.Numer. wykład 2
Przykład
1 1 0 1 0 0 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Mantissa (m)
Sign
Biased
(s)
Exponent (e )
s
Value = (-1) �(1.m) � 2e'-127
2
1
2
= (-1) �(1.10100000) � 2(10100010) -127
2
= (-1)�(1.625)� 2162-127
= (-1)�(1.625)� 235 = -5.5834�1010
17
Met.Numer. wykład 2
Wykładnik dla 32-bitowego standardu IEEE-754
8 bitów wykładnika oznacza
2
0 d" e d" 255
Ustalone przesunięcie wykładnika wynosi 127 a
zatem
-127 d" e d" 128
2
W istocie 1 d" e d" 254
2
Liczby e = 0 i 2 są zarezerwowane dla
e = 255
przypadków specjalnych
Zakres wykładnika -126 d" e d" 127
18
Met.Numer. wykład 2
6
2013-10-26
Reprezentacja liczb specjalnych
2 same zera
e = 0
2
e = 255 same jedynki
s m Reprezentuje
2
e
0 same zera same zera 0
1 same zera same zera -0
0 same same zera
"
jedynki
1 same same zera
- "
jedynki
0 lub 1 same różne od NaN
jedynki zera
19
Met.Numer. wykład 2
Format IEEE-754
Największa liczba
(1.1........1) � 2127 = 3.40�1038
2
Najmniejsza liczba
(1.00......0) � 2-126 = 2.18�10-38
2
Epsilon maszyny cyfrowej
�mach = 2-23 = 1.19 �10-7
20
Met.Numer. wykład 2
Analiza błędów
Jeżeli nie znamy wielkości dokładnej xo możemy
obliczać błąd bezwzględny przybliżenia (ang.
approximate error) jako różnicę wartości uzyskanych
w kolejnych przybliżeniach :
xn - xn-1
Błąd względny �a :
xn - xn-1
�a =
xn
21
Met.Numer. wykład 2
7
2013-10-26
Przykład
Dla f (x) = 7e0.5x x = 2 znajdz

w
2 dla
a) f (2) h = 0.3
2
f (2) dla h = 0.15
b)
c) błąd przybliżenia
Rozwiązanie
f (x + h) - f (x)
f ' (x) H"
h
a) h = 0.3
f (2 + 0,3) - f (2) 7e0,5(2,3) - 7e0,5(2)
f '(2) H" = = 10,265
0,3 0,3
22
Met.Numer. wykład 2
Przykład (cd)
b) h = 0.15
f (2 + 0,15) - f (2) 7e0,5(2,15) - 7e0,5(2)
f '(2) H" = = 9,880
0,15 0,15
xn - xn-1
c) �a =
xn
9,880 -10,265
�a = H" -0,0389
9,8800
Błąd procentowy 3,89%
23
Met.Numer. wykład 2
Błąd względny jako kryterium zakończenia
procedury iteracyjnej
Jeżeli błąd względny jest mniejszy lub równy od pewnej
określonej wcześniej liczby to dalsze iteracje nie są konieczne
| �a | d" �s
Jeżeli wymagamy przynajmniej m cyfr znaczących w wyniku to
| �a |d" 0.5�102-m
24
Met.Numer. wykład 2
8
2013-10-26
Podsumowanie przykładu
| �a |d" 0.5�102-m
�a
2 m
f (2)
h
0.3 10.265 N/A 0
0.15 9.8800 0.03894 1
0.10 9.7559 0.01271 1
0.01 9.5378 0.02286 1
0.001 9.5164 0.00225 2
Wartość dokładna 9.514
25
Met.Numer. wykład 2
y
ródła błędów w obliczeniach
numerycznych
1. Błędy wejściowe (błędy danych wejściowych)
2. Błędy obcięcia (ang. truncation error)
3. Błędy zaokrągleń (ang. round off error)
Błędy wejściowe występują wówczas gdy dane wejściowe
wprowadzone do pamięci komputera odbiegają od
dokładnych wartości tych danych.
Błędy obcięcia są to błędy wynikające z procedur
numerycznych przy zmniejszaniu liczby działań.
Błędy zaokrągleń są to błędy, których na ogół nie da się
uniknąć. Powstają w trakcie obliczeń i można je zmniejszać
ustalając umiejętnie sposób i kolejność wykonywania
zadań.
26
Met.Numer. wykład 2
Błędy wejściowe
y
ródła błędów wejściowych:
" dane wejściowe są wynikiem pomiarów wielkości
fizycznych
" skończona długość słów binarnych i konieczność
wstępnego zaokrąglania
" wstępne zaokrąglanie liczb niewymiernych
Przybliżanie liczb, których nie można wyrazić
dokładnie dokonuje się poprzez:
" urywanie (ang. chopping)
" zaokrąglanie (ang. rounding)
27
Met.Numer. wykład 2
9
2013-10-26
Przykład:
Ą H" 3,14159265359
Ą H" 3,1415
Ą H" 3,1416
urywanie
zaokrąglanie
Zaokrąglanie prowadzi do mniejszego błędu niż
urywanie.
28
Met.Numer. wykład 2
Błąd obcięcia
Spowodowany jest użyciem przybliżonej formuły
zamiast pełnej operacji matematycznej:
" przy obliczaniu sum nieskończonych szeregów
" przy obliczaniu wielkości będących granicami
(całka, pochodna)
x
x 2
2
W = F " x = Fdx
"
lim +"
" x 0 x
1 x
1
praca
29
Met.Numer. wykład 2
Szereg Taylora
Jeżeli funkcja jest ciągła i wszystkie pochodne f ,
f  ,& fn istnieją w przedziale [x, x+h] to wartość
funkcji w punkcie x+h można obliczyć jako:
2 2 2 2 2
f (x)h2 f (x)h3
2
f (x + h)= f (x)+ f (x)h + + +L
2! 3!
Szereg Maclaurina jest to rozwinięcie wokół x=0
2 3
2 2 2 2 2 2
f (0 + h)= f (0)+ f (0)h + f (0)h + f (0)h +L+
2! 3!
30
Met.Numer. wykład 2
10
2013-10-26
Przykłady
Typowe rozwinięcia w szereg wokół zera
x2 x4 x6
cos(x) = 1- + - +L
2! 4! 6!
x3 x5 x7
sin(x) = x - + - +L
3! 5! 7!
x2 x3
ex = 1+ x + + +L
2! 3!
31
Met.Numer. wykład 2
Błąd obcięcia w szeregu Taylora
2 n
(n)
2
f (x + h)= f (x)+ f (x)h + f ''(x)h +L+ f (x)h + Rn(x)
2! n!
reszta
hn+1 (n+1)
Rn(x) = f (c)
(n + 1)!
x < c < x + h
32
Met.Numer. wykład 2
Przykład
Rozwinięcie w szereg ex wokół x=0
x2 x3 x4 x5
ex =1+ x + + + + +L
2! 3! 4! 5!
Im większa ilość wyrazów jest uwzględniana w
rozwinięciu, tym błąd obcięcia jest mniejszy i możemy
znalez
ć tym dokładniejszą wartość wyrażenia
Pytanie: Ile należy uwzględnić wyrazów aby otrzymać
przybliżoną wartość liczby e z błędem mniejszym niż 10-6?
12 13 14 15
e1 = 1+1+ + + + +L
2! 3! 4! 5!
1 1 1 1
H" 2 + + + +
2 6 24 120
33
Met.Numer. wykład 2
11
2013-10-26
Rozwiązanie
hn+1 (n+1)
x = 0, h = 1, f (x) = ex Rn(x) = f (c)
(n +1)!
1n+1 (n+1)
Rn(0)= f (c)
(n +1)!
(1)n+1
= ec
(n +1)!
ale
x < c < x + h
1 e
< Rn(0) <
0 < c < 0 +1
(n +1)! (n +1)!
0 < c < 1
34
Met.Numer. wykład 2
Rozwiązanie
e
<10-6 założony poziom
(n +1)!
błędu
(n +1)!>106 e
(n +1)!>106 � 3
n e" 9
Co najmniej 9 wyrazów musimy zastosować aby otrzymać
wartość błędu na poziomie 10-6
35
Met.Numer. wykład 2
Przykład tragicznego błędu zaokrąglenia
25 lutego 1991 w Dhahran, Arabia Saudyjska, zginęło 28
amerykańskich żołnierzy w wyniku ataku irackiej rakiety Scud.
System obrony Patriot nie wykrył zagrożenia. Dlaczego?
System oblicza powierzchnię, którą powinien skanować na
podstawie prędkości obiektu i czasu ostatniej detekcji. Zegar
wewnętrzny był ustawiony na pomiar co 1/10 sekundy. Długość
słowa 24 bity. Z powodu zaokrągleń błąd bezwzględny wyniósł
9.5 10-8 s a po 100 godzinach:
9.5�"10-8 �10� 60� 60�100 = 0.34 sec
Przesunięcie obliczone na tej podstawie 687 m. Obiekt jest
uznany poza zakresem gdy przesunięcie wynosi 137 m
36
Met.Numer. wykład 2
12
2013-10-26
Działania arytmetyczne
1. Dodawanie i odejmowanie
Aby dodać lub odjąć dwie znormalizowane liczby w
zapisie zmiennoprzecinkowym, wykładniki w
powinny być zrównane poprzez odpowiednie
przesunięcie mantysy.
Przykład: Dodać 0,4546"105 do 0,5433"107
przesuwamy
0,0045"107+0,5433 "107=0,5478 "107
Wniosek: Tracimy pewne cyfry znaczące
37
Met.Numer. wykład 2
Działania arytmetyczne
2. Mnożenie
Przykład: Pomnożyć 0,5543"1012 przez 0,4111"10-15
Mnożymy mantysy i wykładniki w dodajemy.
0,5543"1012"0,4111 "10-15=0,2278273 "10-3=0,2278"10-3
3. Dzielenie
Przykład: Podzielić 0,1000"105 przez 0,9999"103
0,1000"105/0,9999 "103=0,1000 "102
Za każdym razem tracimy pewne cyfry znaczące co jest z
ródłem
błędu
38
Met.Numer. wykład 2
Kolejność działań
(a+b)-c`"(a-c)+b brak przemienności, łączności
a(b-c) `"(ab-ac) brak rozdzielności mnożenia
względem dodawania
Przykład: a= 0,5665"101, b=0,5556"10-1,
c=0,5644"101
(a+b)=0,5665"101+0,5556"10-1
=0,5665"101+0,0055"101=0,5720"101
(a+b)-c=0,5720"101-0,5644"101=0,7600"10-1
(a-c)=0,5665"101-0,5644"101=0,0021"101=0,2100"10-1
(a-c)+b=0,2100"10-1+0,5556"10-1=0,7656"10-1
39
Met.Numer. wykład 2
13
2013-10-26
Wnioski z dotychczasowych rozważań
" W wielu przypadkach można uniknąć błędów
wejściowych i błędów obcięcia.
" W trakcie obliczeń pojawiają się nowe błędy (błędy
zaokrągleń), których nie da się uniknąć.
" Błędy zaokrągleń można zmniejszyć ustalając
umiejętnie sposób i kolejność wykonywania działań.
40
Met.Numer. wykład 2
Propagacja błędów
140
120
funkcja
100 y = f(x)
u(y)
80
styczna dy
u(y) = u(x)
60 dy/dx
dx
40
u(x)
20
0
024
x
41
Met.Numer. wykład 2
Metoda różniczki zupełnej
Dla wielkości złożonej y=f(x1,x2,...xn) gdy niepewności
maksymalne "x1 , "x2 , ... "xn są małe w porównaniu z
wartościami zmiennych x1,x2, ... xn niepewność
maksymalną wielkości y wyliczamy z praw rachunku
różniczkowego:
"y "y "y
" y = " x1 + " x2 + ... + " xn
"x1 "x2 "xn
42
Met.Numer. wykład 2
14
y
2013-10-26
Przykład
Oszacować błąd pomiaru gęstości � kuli o masie m i promieniu R
m
�(m, R) =
(4 3)ĄR3
"� "�
błąd bezwzględny
"� = "m + "R
"m "R
"� 1 "� - 3
ale
=
=
"m (4 3)ĄR3 "R 3)ĄR4
(4
błąd względny
�� = �m + 3�R
43
Met.Numer. wykład 2
Błędy działań arytmetycznych
Błąd sumy
A = a ą "a B = b ą "b
błędy bezwzględne składników sumy
A + B = a + b ą "a ą "b = a + b ą "(a + b)
błąd bezwzględny sumy
Zatem błąd bezwzględny sumy (różnicy) jest równy sumie
błędów składników.
"(a ą b) = "a + "b
44
Met.Numer. wykład 2
Błędy działań arytmetycznych
"a + "b
Błąd względny sumy
�a+b =
a + b
Błąd względny różnicy
"a + "b
�a-b =
a - b
Błąd względny różnicy może być duży nawet gdy błędy względne
odjemnej i odjemnika są małe. Należy unikać odejmowania
prawie równych liczb przybliżonych!
Zjawisko zwane redukcją cyfr znaczących
Szczególnie istotne przy obliczeniach ilorazów różnicowych
przybliżających pochodne funkcji, pierwiastków równania
kwadratowego przy dominującym współczynniku przy
pierwszej potędze, itp.
45
Met.Numer. wykład 2
15
2013-10-26
Koncepcja zera
Tracimy dokładny sens liczby 0 jeśli dokonujemy
obliczeń numerycznych
x2 + 2x - 2 = 0
pierwiastkami są
-1ą 3
0,7320�10o
w przybliżeniu
-0.2732 �101
Sprawdzić, że po podstawieniu rozwiązań przybliżonych nie
otrzymujemy dokładnie liczby zero
Powinno się zatem unikać odejmowania bliskich sobie liczb i
warunek w pętli nie powinien być ustawiany  do zera ,
if a-b<�
46
Met.Numer. wykład 2
Wnioski praktyczne
Przy obliczeniach numerycznych korzystne jest:
" ponowne rozwiązanie tego samego zagadnienia inną
metodą lub taką samą metodą, ale z inną
kolejnością operacji
" ponowne rozwiązanie zagadnienia przy nieznacznej
zmianie danych wejściowych
47
Met.Numer. wykład 2
Zadania i algorytmy numeryczne
" Zadanie numeryczne wymaga jasnego i
niedwuznacznego opisu powiązania funkcjonalnego
między danymi wejściowymi czyli  zmiennymi
niezależnymi zadania i danymi wyjściowymi, tj.
szukanymi wynikami.
" Zadanie numeryczne jest problemem polegającym na
wyznaczeniu wektora wyników w na podstawie wektora
danych a
zadanie dobrze
postawione
odwzorowanie W
r r
a w = W (a)
w
jednoznaczne
D
przyporządkowanie
48
Met.Numer. wykład 2
16
2013-10-26
Zadania i algorytmy numeryczne
" Algorytm numeryczny jest pełnym opisem poprawnie
określonych operacji przekształcających wektor
dopuszczalnych danych wejściowych (zbiór DN) na
wektor danych wyjściowych.
" Algorytm jest poprawnie sformułowany gdy liczba
niezbędnych działań będzie skończona
DN )" D `" "
w = WN(a,�)
odwzorowanie WN
wektor wyniku
zależy od
a
dokładności
obliczeniowej �
DN
w
maszyny cyfrowej
49
Met.Numer. wykład 2
Przykłady algorytmów
Dana jest liczba zespolona a=x+iy. Obliczyć 1/a2
Algorytm I:
t = y / x (tangens fazy liczby a)
1.
2
2.
a = x2 + y2 (kwadrat modułu liczby a)
1 1
1 1 1- t2 ś# - 2t2
3.
Re�# ś# = Im�# =
ś# ź# ś# ź#
a2 / a /2 1+ t2 a2 / a /2 1+ t2
�# # �# #
Zadanie jest dobrze postawione, jeżeli: x2 + y2 `" 0
D = R2
czyli: -{(0,0)}
Algorytm jest poprawnie sformułowany (11 niezbędnych działań)
50
Met.Numer. wykład 2
Przykłady algorytmów
Nie dla każdej pary danych (x,y)`"0 można znalez
ć rozwiązanie
zadania stosując algorytm I.
1. Wystąpi nadmiar liczb zmiennopozycyjnych (dla x=0 ale
także z powodu zaokrąglenia do zera)
2. Nadmiar może nastąpić może już w pierwszym
kroku gdy x=10-25 i y=1025 z powodu dzielenia y/x
3. Dla x=0, istniejącego dla y`"0 rozwiązania nie można
wyznaczyć stosując ten algorytm. Wzrost dokładności
obliczeń nie zmieni tego faktu.
Algorytm I nie jest numerycznie stabilny
51
Met.Numer. wykład 2
17
2013-10-26
Przykłady algorytmów
Dana jest liczba zespolona a=x+iy. Obliczyć 1/a2
Algorytm II:
1 x2 - y2
1.
r = Re�# ś# =
ś# ź#
a2 x2 + y2
�# #
1 - 2xy
2. u = Im�# ś# =
ś# ź#
a2 x2 + y2
�# #
Algorytm II jest poprawnie sformułowany (9 niezbędnych
działań)
Algorytm II jest numerycznie stabilny co wynika z ciągłości
wzorów dla
x2 + y2 `" 0
52
Met.Numer. wykład 2
Uwarunkowanie zadania i stabilność
algorytmów
Algorytm obliczeniowy jest numerycznie stabilny, jeżeli dla
dowolnie wybranych danych
a0 " D
istnieje taka dokładność obliczeń �0, że dla �<�0 mamy
a0 " DN( � )
oraz limWN(a0,�) = W (a0)
�0
Algorytm obliczeniowy jest numerycznie stabilny wtedy, gdy
zwiększając dokładność obliczeń można wyznaczyć ( z dowolną
dokładnością) dowolne istniejące rozwiązanie zadania.
53
Met.Numer. wykład 2
Uwarunkowanie zadania i stabilność
algorytmów
Uwarunkowaniem zadania nazywamy cechę, która mówi jak
bardzo wynik dla zaburzonego wektora danych różni się od
wyniku dla dokładnego wektora danych czyli:
W(a + �a) W(a)
Wskaz
nik uwarunkowania zadania B(a) jest to liczba, dla której
jest spełniony warunek:
�w �a
d" B(a)
w a
�w = WN(a,�) -W (a)
54
Met.Numer. wykład 2
18
2013-10-26
Wskaz
nik uwarunkowania zadania
" Przyjmijmy względny błąd wielkości x
~
x - x
~
x
" Względny błąd wielkości f(x)
~)
f (x) - f (~) f '(~)(x - x
x x
H"
f (~) f (~)
x x
" Wskaz
nik uwarunkowania:
~f '(~)
x x
f (~)
x
55
Met.Numer. wykład 2
Wskaz
nik uwarunkowania zadania
" Przykład
f (x) = x
" Wskaz
nik uwarunkowania:
1
~f '(~) x 2 x 1
x x
= =
f (~) 2
x
x
zadanie dobrze uwarunkowane
56
Met.Numer. wykład 2
Wskaz
nik uwarunkowania zadania
" Przykład
10
f (x) =
1- x2
" Wskaz
nik uwarunkowania:
~f '(~) 2x2
x x
=
f (~)
x
1- x2
zadanie z
le uwarunkowane w pobliżu x=1 i x=-1
57
Met.Numer. wykład 2
19
2013-10-26
Schemat Hornera
Przykład wzoru rekurencyjnego
Aby obliczyć wartość wielomianu:
p(x) = xn + a1xn-1 +...+ an-1x + an
w danym punkcie z, korzystamy ze schematu:
p1 = z + a1
p2 = zp1 + a2
pn = zpn-1 + an
p(z) = pn
co odpowiada obliczaniu wartości wyrażenia:
z{z[z...(z + a1) + a2]+ ...+ an-1}+ an
58
Met.Numer. wykład 2
Schemat Hornera
Schemat Hornera umożliwia znaczne zmniejszenie liczby działań
arytmetycznych.
W schemacie Hornera wykonujemy n-1 mnożeń i n dodawań.
Obliczając bezpośrednio:
zz...z + a1z...z + ...+ an-1z + ao
n razy n-1 razy
wykonujemy (n-1)(n+2)/2 mnożeń i n dodawań.
Oszacowanie wielkości błędów zaokrągleń jest identyczne dla
obu metod
59
Met.Numer. wykład 2
Schemat Hornera
Przykład: oblicz p(z) = a0z3 + a1z2 + a2z + a3
p(z) = ((a0z + a1)z + a2)z + a3
w schemacie Hornera
dla obliczeń ręcznych:
a0 a1 a2 a3
zb0 zb1 zb2
b0 b1 b2 b3 p(z)=b3
Zadanie: Oblicz p(8) dla p(x)=2x3+x+7
2 0 1 7
16 128 1032
p(8)=1039
8 16 129 1039
60
Met.Numer. wykład 2
20