Teoria błędów w analizie ...

[ Pobierz całość w formacie PDF ]
˜
sle/teaching/an-tbl.pdf
Analiza numeryczna
Stanisław Lewanowicz
Pa¹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
6
=0mo»emy przedstawi¢ w postaci
sko«czonego rozwini¦cia dwójkowego
(1)
l=s
n
X
e
i
2
i
;
i=0
gdzies=sgnl;ae
i
2
f0;1g (i=0;1;:::;n; e
n
=1). W komputerze na reprezentacj¦ liczby przezna-
cza si¦ słowo o sko«czonej długo±ci np.d+1bitów. Liczbaljest reprezentowalna w wybranej arytmetyce,
je±li tylkon<d.
Dokładnie
reprezentowane s¡ liczby z przedziału[-2
d
+1;2
d
-1](najwi¦ksza liczba
dodatnia:
11
¢
¢¢
1
|{z}
d
razy
). Przy zało»eniu, »e argumenty działania i jego wynik s¡ reprezentowalne, dodawanie,
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
6
=0mo»emy przedstawi¢ jednoznacznie
w postaci
x=s
¢
m
¢
2
c
;
gdzies=sgnx,cjest liczb¡ całkowit¡, zwan¡
cech¡
liczbyx, amjest liczb¡ rzeczywist¡ z przedziału
[
1
2
;1), nazywan¡
mantys¡
tej liczby.dbitów słowa maszynowego ((
d
+1)-szy bit zawiera informacj¦ o
znaku liczby) dzieli si¦ na dwie cz¦±ci. Cech¦c(wraz ze znakiem!) zapisuje si¦ w sposób stałopozycyjny
(por. (1)) nad-tbitach słowa. Zakładamy, »ecnale»y do przedziału liczb, które mo»na przedstawi¢
w ten sposób. Pozostałychtbitów słowa przeznacza si¦ na reprezentacj¦ mantysym. Ogólnie bior¡c,
zamiast niesko«czonego rozwini¦cia mantysy
m=
1
X
e
-i
2
-i
(e
-1
=1; e
-i
2
f0;1g (i>1))
i=1
zapami¦tuje si¦ cyfry
zaokr¡glenia mantysy
, o sko«czonym rozwini¦ciu
m
t
=
t
X
e
¤
-i
2
-i
; gdzie e
¤
-i
2
f0;1g:
i=1
Zaokr¡glenie symetryczne
(ang.
symmetric rounding
):
m
t
=rd(m):=
t
X
e
-i
2
-i
+e
-(t+1)
2
-t
:
i=1
Twierdzenie 1.1
Bł¡d zaokr¡glenia mantysy nie przekracza
1
2
2
-t
:
jm-m
t
j
·
1
2
2
-t
:
Analiza numeryczna
/
Poj¦cia teorii bł¦dów
2
Reprezentacj¦ liczby
xstanowi zatem trójka(s;c;m
t
), zapami¦tywana w jednym słowie. Zero jest
zwykle reprezentowane przez słowo zło»one z samych zerowych bitów. Reprezentacj¦ zmiennopozycyjn¡
liczbyxb¦dziemy oznacza¢ symbolem rd(x), gdzie
rd(x):=s
¢
m
r
t
¢
2
c
:
Twierdzenie 1.2 (Bł¡d reprezentacji zmiennopozycyjnej liczby rzeczywistej)
Dla
x
6
=0
za-
chodzi nierówno±¢
¯
¯
¯
¯
rd(x)-x
x
¯
¯
¯
¯
·
2
-t
:
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:
X:=(-D;D); gdzieD:=2
c
max
; c
max
:=2
d-t-1
-1:
Niedomiar zmiennopozycyjny
wyst¦puje wówczas, gdy jxj<
1
2D
.
Mamy do czynienia z
nadmiarem zmiennopozycyjnym
, je±li jxj
¸
D.
Zbiór reprezentacji arytmetyki zmiennopozycyjnej
definiujemy jako obraz zbioruXw odwzoro-
waniu rd , czyliX
fl
:=rd(X).
Zmiennopozycyjne działania arytmetyczne
. Dla danych liczb zmiennopozycyjnycha;bi działania
¦2
f+;-;
£
;=g, zakładaj¡c, »ea
¦
b
2
X
fl
oraz ja
¦
bj
¸
1
2D
, definiujemy
fl
(a
¦
b):=rd(a
¦
b):
Bł¡d zmiennopozycyjnego działania arytmetycznego
:
fl
(a
¦
b)=(a
¦
b)(1+"
¦
); gdzie "
¦
="
¦
(a;b);j"
¦
j
·
2
-t
:
Definicja 1.3
Mówimy, »e liczba
~x
2
X
fl
przybli»a liczb¦
x
2
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±¢
j~x-xj
·
p2
-t
jxj:
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
j±
i
j
·
2
-t
(
i=1;2;:::;n
), to zachodzi równo±¢
(2)
n
Y
(1+±
i
)=1+¾
n
;
i=1
gdzie
¾
n
¼
P
n
i=1
±
i
:
Je±li
n2
-t
<2
, to jest prawdziwe oszacowanie
(3)
j¾
n
j
·
°
n
;
gdzie
°
n
:=
n2
-t
1-
1
2
n2
-t
:
Je±li
n2
-t
<0:1
, to
j¾
n
j
·
°
n
·
n(1:06
¢
2
-t
)=n2
-t
1
¼
n2
-t
;
gdzie
t
1
:=t-log
2
(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¦ podstawieniay:=x-sinxi przypu±¢my, »e w pewnym kroku
oblicze« jest ona wykonywana dlax=
1
30
. Załó»my, »e komputer pracuje w dziesi¦ciocyfrowej arytmetyce
dziesi¦tnej. Otrzymamy wówczas
x:=0:3333333333
£
10
-1
sinx:=0:3332716084
£
10
-1
x-sinx:=0:0000617249
£
10
-1
x-sinx:=0:6172490000
£
10
-5
Dla porównania wynik dokładny:x-sinx:=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 gro¹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¡k¢k, okre±lon¡ w przestrzeni
R
n
, o nast¦puj¡cych własno±ciach (
x
,
y
oznaczaj¡ dowolne wektory z
R
n
,
®
-dowoln¡ liczb¦ rzeczywist¡):
k
x
k
>0
dla
x
6
=0;
k
®x
k
=j®j
¢k
x
k
;
k
x+y
k·k
x
k
+
k
y
k
:
Definicja 3.2
Normy wektorowe Holdera wektora
x=[x
1
;x
2
;:::;x
n
]
T
2
R
n
definiujemy nast¦puj¡-
cymi wzorami:
k
x
k
1
:=
n
X
jx
k
j (
norma pierwsza
);
Ã
n
X
!
1=2
k
x
k
2
:=
x
2
k
(
norma euklidesowa
);
k=1
k
x
k
1
:=max
1
·
k
·
n
jx
k
j (
norma maksymalna
):
4
Reprezentacja
fl
wektorów
Przyjmuj¡c dla wektorax
2
R
n
reprezentacj¦
rd(x):=(rd(x
1
);:::;rd(x
n
))
T
;
otrzymujemy:
k
x-rd(x)
k
2
·
2
-t
k
x
k
2
;
lub, w równowa»nej postaci,
rd(x)=diag(1+²
i
)x (j²
i
j
·
2
-t
);
gdzie diag(c
i
)
2
R
n
£
n
oznacza macierz przek¡tniow¡, o elementachc
1
;:::;c
n
na przek¡tnej głównej.
Takie samo oszacowanie zachodzi dla innych norm Holdera.
k=1
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
¹le uwarunkowanym
. Wielko±ci charakteryzuj¡ce wpływ za-
burze« danych na odkształcenia rozwi¡zania nazywamy
wska¹nikami uwarunkowania
zadania.
Przykład 5.2
W wypadku zadania obliczenia warto±ci funkcjifw punkciex, je±lixzostanie lekko
zaburzone o wielko±¢h, a wi¦c je±li jh=xj b¦dzie wzgl¦dnym zaburzeniemx, to
jf(x)j
¼
jhf
0
(x)j
jf(x)j
=
jxf
0
(x)j
jhj
jxj
:
jf(x)j
Tak wi¦c czynnikC(x):=jxf
0
(x)j=jf(x)j mo»na traktowa¢ jako
wska¹nik uwarunkowania
dla tego
zadania. Je±liC(x)jest małe, to wzgl¦dna zmiana wyniku równie» b¦dzie mała — zadanie jest dobrze
uwarunkowane. Je±liC(x)jest du»e, mała zmiana argumentuxmo»e wywoła¢ (bardzo) du»e wzgl¦dne
odkształcenie wyniku — wówczas mamy do czynienia z zadaniem ¹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 arytmetycefljest 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±cinliczbx
1
;x
2
;:::;x
n
. Mo»na
wykaza¢, »e
fl
(
¢¢¢
((x
1
+x
2
)+x
3
)+
¢¢¢
+x
n
)=~x
1
+~x
2
+
¢¢¢
+~x
n
;
gdzie
~
x
i
=x
i
(1+±
i
)(i=1;2;:::;n);
1+±
i
:=
n
Y
(1+²
j
)(i=1;2;:::;n);
j=i
²
1
:=0; j²
i
j
·
2
-t
(i=2;3;:::;n):
Na mocy tw. 1.4
j±
1
j
·
°
n-1
; j±
i
j
·
°
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.
jf(x+h)-f(x)j
[ Pobierz całość w formacie PDF ]