http://www.ii.uni.wroc.pl/Üsle/teaching/an-tbl.pdf
Analiza numeryczna
Stanisław Lewanowicz
Paz
dziernik 2007 r.
Podstawowe pojęcia teorii błędów w analizie numerycznej
Definicje, twierdzenia
1 Stałopozycyjna i zmiennopozycyjna reprezentacja liczb
Liczby całkowite (typu integer). Dowolną liczbę całkowitą l = 0 możemy przedstawić w postaci

skończonego rozwinięcia dwójkowego
n
(1) l = s ei2i,
i=0
gdzie s = sgn l, a ei " {0, 1} (i = 0, 1, . . . , n; en = 1). W komputerze na reprezentacjÄ™ liczby przezna-
cza się słowo o skończonej długości np. d+1 bitów. Liczba l jest reprezentowalna w wybranej arytmetyce,
jeśli tylko n < d. Dokładnie reprezentowane są liczby z przedziału [-2d + 1, 2d - 1] (największa liczba
dodatnia: 11 · · · 1). Przy zaÅ‚ożeniu, że argumenty dziaÅ‚ania i jego wynik sÄ… reprezentowalne, dodawanie,
d razy
odejmowanie i mnożenie liczb całkowitych (typu integer) jest wykonywane dokładnie. Zobaczymy, że
nie jest tak, ogólnie biorąc, w wypadku liczb rzeczywistych (typu real).
Liczby rzeczywiste (typu real). Dowolną liczbę rzeczywistą x = 0 możemy przedstawić jednoznacznie

w postaci
x = s · m · 2c,
gdzie s = sgn x, c jest liczbą całkowitą, zwaną cechą liczby x, a m jest liczbą rzeczywistą z przedziału
1
[ , 1), nazywaną mantysą tej liczby. d bitów słowa maszynowego ((d+1)-szy bit zawiera informację o
2
znaku liczby) dzieli się na dwie części. Cechę c (wraz ze znakiem!) zapisuje się w sposób stałopozycyjny
(por. (1)) na d - t bitach słowa. Zakładamy, że c należy do przedziału liczb, które można przedstawić
w ten sposób. Pozostałych t bitów słowa przeznacza się na reprezentację mantysy m. Ogólnie biorąc,
zamiast nieskończonego rozwinięcia mantysy
"
m = e-i2-i (e-1 = 1; e-i " {0, 1} (i > 1))
i=1
zapamiętuje się cyfry zaokrąglenia mantysy, o skończonym rozwinięciu
t
mt = e" 2-i, gdzie e" " {0, 1}.
-i -i
i=1
ZaokrÄ…glenie symetryczne (ang. symmetric rounding):
t
mt = rd (m) := e-i2-i + e-(t+1)2-t.
i=1
1
Twierdzenie 1.1 BÅ‚Ä…d zaokrÄ…glenia mantysy nie przekracza 2-t:
2
1
| m - mt |d" 2-t.
2
Analiza numeryczna / Pojęcia teorii błędów 2
Reprezentację liczby x stanowi zatem trójka (s, c, mt), zapamiętywana w jednym słowie. Zero jest
zwykle reprezentowane przez słowo złożone z samych zerowych bitów. Reprezentację zmiennopozycyjną
liczby x będziemy oznaczać symbolem rd (x), gdzie
rd (x) := s · mr · 2c.
t
Twierdzenie 1.2 (BÅ‚Ä…d reprezentacji zmiennopozycyjnej liczby rzeczywistej) Dla x = 0 za-

chodzi nierówność
rd (x) - x
d" 2-t.
x
Inaczej mówiÄ…c, zachodzi równość rd (x) = x(1 + µ), gdzie µ jest pewnÄ… liczbÄ… o wartoÅ›ci bezwzglÄ™dnej
nieprzekraczajÄ…cej 2-t.
Zbiór X liczb reprezentowalnych w arytmetyce zmiennopozycyjnej określamy następująco:
max
X := (-D, D), gdzie D := 2c , cmax := 2d-t-1 - 1.
1
Niedomiar zmiennopozycyjny występuje wówczas, gdy |x| < .
2D
Mamy do czynienia z nadmiarem zmiennopozycyjnym, jeśli |x| e" D.
Zbiór reprezentacji arytmetyki zmiennopozycyjnej definiujemy jako obraz zbioru X w odwzoro-
waniu rd , czyli Xfl := rd (X).
Zmiennopozycyjne działania arytmetyczne. Dla danych liczb zmiennopozycyjnych a, b i działania
1
" {+, -, ×, /}, zakÅ‚adajÄ…c, że a b " Xfl oraz |a b| e" , definiujemy
2D
fl(a b) := rd (a b).
Błąd zmiennopozycyjnego działania arytmetycznego:
fl(a b) = (a b)(1 + µ ), gdzie µ = µ (a, b), |µ | d" 2-t.
Ü
Definicja 1.3 Mówimy, że liczba x " Xfl przybliża liczbę x " X z błędem względnym na poziomie błędu
(względnego) reprezentacji, jeśli dla niewielkiej stałej p (np. rzędu jedności) zachodzi nierówność
Ü
|x - x| d" p2-t|x|.
Tak więc obliczony wynik działania arytmetycznego jest dokładnym wynikiem, zaburzonym na poziomie
błędu reprezentacji. Następujące twierdzenie umożliwia upraszczanie wyrażeń dla oszacowań błędów,
powstających w trakcie realizacji algorytmów obliczeniowych.
Twierdzenie 1.4 JeÅ›li |´i| d" 2-t (i = 1, 2, . . . , n), to zachodzi równość
n
(2) (1 + ´i) = 1 + Ãn,
i=1
n
gdzie Ãn H" ´i. JeÅ›li n2-t < 2, to jest prawdziwe oszacowanie
i=1
n2-t
(3) |Ãn| d" Å‚n, gdzie Å‚n := .
1
1 - n2-t
2
Jeśli n2-t < 0.1, to
1
|Ãn| d" Å‚n d" n (1.06 · 2-t) = n2-t H" n2-t,
gdzie t1 := t - log2(1.06) = t - 0.08406.
Analiza numeryczna / Pojęcia teorii błędów 3
2 Utrata cyfr znaczÄ…cych
Przykład 2.1 Rozważmy instrukcję podstawienia y := x - sin x i przypuśćmy, że w pewnym kroku
1
obliczeń jest ona wykonywana dla x = . Załóżmy, że komputer pracuje w dziesięciocyfrowej arytmetyce
30
dziesiętnej. Otrzymamy wówczas
x := 0.3333333333 × 10-1
sin x := 0.3332716084 × 10-1
x - sin x := 0.0000617249 × 10-1
x - sin x := 0.6172490000 × 10-5
Dla porównania wynik dokÅ‚adny: x - sin x := 0.6172496579716 . . . × 10-5. Tak wiÄ™c wynik obliczony ma
o 4 cyfry dokładne mniej, niż dane!
Mamy tu do czynienia z ze zjawiskiem nazywanym utratą cyfr znaczących. Może być ono uważane za
piętę Achillesową obliczeń zmiennopozycyjnych, i  wobec tego  powinno się go unikać za wszelką cenę!!
Przy tym groz
ne są nie tylko rozległe zniszczenia wywołane przez pojedyncze działania (odejmowania,
w gruncie rzeczy), lecz również powtarzające się wielokrotnie małe wstrząsy. W obu wypadkach wynik
końcowy może być katastrofalny.
3 Normy wektorowe
Definicja 3.1 NormÄ… wektorowÄ… nazywamy nieujemnÄ… funkcjÄ™ rzeczywistÄ… · , okreÅ›lonÄ… w przestrzeni
Rn, o następujących własnościach (x, y oznaczają dowolne wektory z Rn, ą -dowolną liczbę rzeczywistą):
x > 0 dla x = 0;

Ä…x = |Ä…| · x ;
x + y d" x + y .
Definicja 3.2 Normy wektorowe Höldera wektora x = [x1, x2, . . . , xn]T " Rn definiujemy nastÄ™pujÄ…-
cymi wzorami:
n
x := |xk| (norma pierwsza);
1
k=1
1/2
n
x := x2 (norma euklidesowa);
2
k
k=1
x := max |xk| (norma maksymalna).
"
1d"kd"n
4 Reprezentacja fl wektorów
PrzyjmujÄ…c dla wektora x " Rn reprezentacjÄ™
rd (x) := (rd (x1), . . . , rd (xn))T ,
otrzymujemy:
x - rd (x) d" 2-t x ,
2 2
lub, w równoważnej postaci,
rd (x) = diag (1 + )x (| | d" 2-t),
i i
gdzie diag (ci) " Rn×n oznacza macierz przekÄ…tniowÄ…, o elementach c1, . . . , cn na przekÄ…tnej głównej.
Takie samo oszacowanie zachodzi dla innych norm Höldera.
Analiza numeryczna / Pojęcia teorii błędów 4
5 Uwarunkowanie zadania
Definicja 5.1 Jeśli niewielkie względne zmiany danych zadania powodują duże względne zmiany jego
rozwiÄ…zania, to zadanie takie nazywamy z
le uwarunkowanym. Wielkości charakteryzujące wpływ za-
burzeń danych na odkształcenia rozwiązania nazywamy wskaz
nikami uwarunkowania zadania.
Przykład 5.2 W wypadku zadania obliczenia wartości funkcji f w punkcie x, jeśli x zostanie lekko
zaburzone o wielkość h, a więc jeśli |h/x| będzie względnym zaburzeniem x, to
|f(x + h) - f(x)| |hf (x)| |xf (x)| |h|
H" = .
|f(x)| |f(x)| |f(x)| |x|
Tak więc czynnik C(x) := |xf (x)|/|f(x)| można traktować jako wskaz
nik uwarunkowania dla tego
zadania. Jeśli C(x) jest małe, to względna zmiana wyniku również będzie mała  zadanie jest dobrze
uwarunkowane. Jeśli C(x) jest duże, mała zmiana argumentu x może wywołać (bardzo) duże względne
odkształcenie wyniku  wówczas mamy do czynienia z zadaniem z
le uwarunkowanym!
6 Algorytmy numerycznie poprawne
Ogólnie biorąc, przy numerycznym rozwiązywaniu zadania w miejsce dokładnych danych pojawią się
dane zaburzone przez błędy reprezentacji. Z drugiej strony, nawet jeśli znamy dokładne rozwiązanie dla
tych danych, to w arytmetyce fl jest ono reprezentowane tylko w sposób przybliżony. Z tych względów
za numerycznie najwyższej jakości uznamy takie algorytmy, dla których ob-
liczone rozwiązanie jest mało zaburzonym rozwiązaniem dokładnym dla mało
zaburzonych danych.
Algorytmy o powyższej własności nazywamy numerycznie poprawnymi.
Wariant sytuacji, gdy obliczone rozwiązanie jest rozwiązaniem dokładnym (a więc nieza-
burzonym) dla mało zaburzonych danych, wiąże się z pojęciem algorytmu numerycznie
bardzo poprawnego.
Przez  małe zaburzenia rozumiemy tu zaburzenia na poziomie błędu reprezentacji.
Przykład 6.1 Rozważmy zadanie sumowania w naturalnej kolejności n liczb x1, x2, . . . , xn. Można
wykazać, że
Ü Ü Ü
fl(· · · ((x1 + x2) + x3) + · · · + xn) = x1 + x2 + · · · + xn,
gdzie
Ü
xi = xi(1 + ´i) (i = 1, 2, . . . , n),
n
1 + ´i := (1 + ) (i = 1, 2, . . . , n),
j
j=i
:= 0; | | d" 2-t (i = 2, 3, . . . , n).
1 i
Na mocy tw. 1.4
|´1| d" Å‚n-1, |´i| d" Å‚n+1-i (i = 2, 3, . . . , n).
Oznacza to, że obliczony wynik jest równy dokładnej sumie nieco zaburzonych danych  algorytm
sumowania jest więc numerycznie bardzo poprawny.