Adam Szustalewicz Matematyka obliczeniowa 2002/2003 w.5 04.11.02
Wykład 5: Elementy arytmetyki zmiennopozycyjnej
Literatura:
1. G. Dahlquist, A. Björck, Metody numeryczne, PWN, Warszawa 1983.
1. Kilka definicji
Oznaczmy: x  wartość dokładna wielkości.
x  wartość przybliżona tej wielkości.
Ü
DEF.
bÅ‚ad bezwzgledny wartoÅ›ci x ´(x) = x - x ,
Ü Ü Ü
x-x
Ü
bÅ‚ad wzgledny wartoÅ›ci x (dla x = 0) µ(x) = .
Ü Ü
x
Uwagi (por. [Dahlquist], rozdz. 1)
1. W wypadku gdy x, x nie sa liczbami rzeczywistymi (moga to być wektory, macierze, . . . ) i gdy dys-
Ü
ponujemy norma ||.|| tych wielkości, możemy moduły powyższych błedów przyjać np. jako ||x - x|| i
Ü
||x-x||
Ü
.
||x||
2. BÅ‚ad bezwzgledny ´(x) wartoÅ›ci x ma swój znak; może być dodatni, ujemny, . . . Czesto jednak nie znamy
Ü Ü
dokładnej wartości x, a dysponujemy jedynie wartościa przybliżona x. Dlatego ważnym jest odróżnianie
Ü
samego bÅ‚edu bezwzglednego od dodatniego oszacowania ´ > 0 z góry jego moduÅ‚u. Zapis
x = x Ä… ´
Ü
oznacza wtedy, że
x - ´ d" x d" x + ´
Ü Ü
tzn. |x - x| d" ´ .
Ü
3. Podobnie jest z błedem wzglednym. Dla liczb różnych od zera zapis
x - x
Ü
= µ(x) jest równoważny x = x(1 + µ(x)) .
Ü Ü Ü
x
Ten ostatni jest najwygodniejszy, a najczeÅ›ciej posÅ‚ugujemy sie oszacowaniem µ z góry moduÅ‚u bÅ‚edu
wzglednego |µ(x)|. Zachodzi
Ü
|µ(x)| d" µ 1 .
Ü
Jak oszacować |µ(x)| jeżeli nie znamy x? Okazuje sie, że najczeÅ›ciej możemy postapić tak:
Ü
|´(x)| |´(x)| |x| |´(x)| |x + x - x| |´(x)| |x| + |x - x| |´(x)| |´(x)|
Ü Ü Ü Ü Ü Ü Ü Ü Ü Ü
= = d" d" 1 +
|x| |x| |x| |x| |x| |x| |x| |x| |x|
Ü Ü Ü Ü Ü
i
|´(x)| |´(x)|
Ü Ü
jeżeli 1 , to H" |µ(x)| .
Ü
|x| |x|
Ü Ü
Na wykładach wcześniejszych mówiliśmy o znormalizowanej reprezentacji zmiennopozycyjnej liczb w kompu-
terze  floating point representation (fl) (por. np. wykł. 1, 4). Dla liczby różnej od zera pozwala ona odrzucić
poczatkowe zera liczby poprzez odpowiednie wyskalowanie liczby (dobranie cechy) tak, by spełnić dodatkowe
1
warunki stawiane mantysie (np. dla układu dwójkowego: d" |mantysa| < 1) . Dlatego możemy mówić o
2
cyfrach znaczacych liczby.
DEF. cyframi znaczacymi liczby nazywamy cyfry pozostałe po odrzuceniu stojacych na poczatku zer.
1
Adam Szustalewicz Matematyka obliczeniowa 2002/2003 w.5 04.11.02
2. Działania arytmetyczne, propagacja błedów
Oznaczmy przez rd(x) reprezentacje komputerowa liczby x. Możemy napisać:
rd(x) = x(1 + µ(x))
z oszacowaniem na µ(x) z zadania 1.
Przyjmuje sie, że komputery wykonuja poszczególne działania arytmetyczne w arytmetyce zmie-
nnopozycyjnej w sposób  optymalny , tzn., wynikiem operacji na argumentach a, b przechowywanych
już w pamieci komputera jest poprawnie zaokraglony dokładny wynik działania:
fl(a + b) = rd(a + b) .
Piszac komende
x = 0.6 " z
(zakładamy, że zmienna z przechowuje już swoja wartość), otrzymujemy zależność:
x = rd( rd(0.6) " z ) czyli x = ( 0.6 " (1 + µ1) " z ) " (1 + µ2) .
Dalej możemy napisać:
x = 0.6 " (1 + µ3) " z " (1 + µ2)
gdzie
µ3 = 2µ
1
a wielkoÅ›ci µ1, µ2, µ maja wielkoÅ›ci szacowane jak w zadaniu 1.
=
DEF. Symbol oznacza, że przy mnożeniu przez siebie nawiasów (1 + µ1)(1 + µ2) możemy wykorzystać
1
fakt, że wielkoÅ›ci µ1, µ2 sa maÅ‚e i zaniedbać ich iloczyny pozostawiajac w szacowaniach jedynie pierwsze ich
potegi.
DEF. Mówimy, że algorytm jest numerycznie poprawny jeśli jego wynik daje sie zinterpretować jako
nieco zaburzony wynik otrzymany dla nieco zaburzonych argumentów.
Przykład: należy policzyć różnice kwadratów a2 - b2 .
Możemy to wykonać na dwa sposoby: zgodnie z napisana formuła, albo zamieniajac wzór na iloczyn:
(a + b)(a - b) . Popatrzmy jak wygladaja szacowania tworzacych sie błedów:
1. w pierwszym wypadku otrzymujemy
(a2(1 + µ1) - b2(1 + µ2))(1 + µ3) = a2 - b2 + a2µ1 - b2µ2 + (a2 - b2)µ3 + . . .
a2µ1 - b2µ2
=
(a2 - b2) 1 + µ3 +
1
(a2 - b2)
i moduł współczynnika zaburzajacego dokładna wartość wyniku można szacować przez
a2|µ1| + b2|µ2|
1 + |µ3| + .
|a2 - b2|
ZakÅ‚adajac, że poszczególne bÅ‚edy sa na poziomie eps maszynowego µ (por. zad. 3 z wykÅ‚. 4), oszacowanie
modułu współczynnika błedu ma postać
a2 + b2
1 + µ + µ
|a2 - b2|
i może być duże.
2
Adam Szustalewicz Matematyka obliczeniowa 2002/2003 w.5 04.11.02
2. W drugim wypadku otrzymujemy
=
(a + b)(1 + µ1)(a - b)(1 + µ2)(1 + µ3) (a + b)(a - b)(1 + µ1 + µ2 + µ3)
1
i jak widzimy, współczynnik zaburzajacy dokładna wartość wyniku można szacować przez
1 + 3µ
Wniosek: Należy stosować drugi algorytm. Jest to algorytm numerycznie poprawny bo w tym
wypadku wynik numeryczny jest równy dokładnemu wynikowi arytmetycznemu zaburzonemu
czynnikiem na poziomie (1 + 3µ).
Przykład: Dwa algorytmy obliczania długich sum
1. Algorytm Gilla  Möllera
u=0; p=0;
for i=1:n
s=u+Ai;
p=u-s+Ai+p;
u=s;
end
s=s+p;
2. Algorytm Kahana
s=A1; c=0;
for i=2:n
y=Ai-c;
t=s+y;
c=(t-s)-y;
s=t;
end
3. Zadania
1. Wyznaczyć oszacowanie moduÅ‚u bÅ‚edu wzglednego µ(x) powstajacego podczas zapamietywania liczby w
komputerze z t-cyfrowa mantysa i z arytmetyka:
" dwójkowa,
" dziesietna.
2. Powinniśmy obliczyć f(x), ale dysponujemy jedynie x. Oszacować |f(x) - f(x)| jeśli znamy oszacowanie
Ü Ü
|f (t)| na interesujacym nas zbiorze. Oszacować bład wzgledny.
"
3. Oszacować wartość x jeÅ›li dysponujemy x = 4.00 i wiemy, że |´(x)| d" 0.005 .
Ü Ü
4. Zmodyfikować zadanie 2 dla f = f(x, y), a potem dla f = f(x1, x2, . . . , xn).
"
"
5. Jakie jest oszacowanie błedu gdy liczymy a - b ? Jak policzyć to  lepiej ?
6. Wzory na piewiastki równania kwadratowego ax2 + bx + c = 0 można znacznie uprościć. Prosze
spróbować ułożyć postepowanie  optymalne .
7. Udowodnić, z
e w arytmetyce komputerowej nie obowiazuja prawa
(a + b) + c = a + (b + c) ani a(b + c) = ab + ac .
Dobrać wartości parametrów i algorytmy obliczania wartości obu stron tak, aby róz
nice pomiedzy war-
tościami obu stron, liczonymi na komputerze były jak najwieksze.
I dla chetnych: Proponuje dobrać wartości zmiennych a, b, c tak, aby różnice miedzy obiema
stronami były jak najwieksze. Moz
e być MATLAB lub typy float, double . . . w C.
8. Przetestować skuteczność podanych wyżej algorytmów sumowania na odpowiednio dobranych przykła-
dach.
* * *
3