Praktyka metod numerycznych
I rok informatyki, studia mgr uzupe�niajace zaoczne
�
sem.zimowy 2002/03
1. Wstep
�
METODY NUMERYCZNE - dzia� matematyki stosowanej zajmujacy sie
� �
opracowywaniem i badaniem metod przyblizonego rozwiazywania problemów
�
�
obliczeniowych w modelach matematycznych innych dziedzin nauki.
Przyk�adowe zastosowania:
- medycyna - tomogra& a komputerowa, opracowywanie nowych leków,
- chemia - konstruowanie nowych czasteczek, opracowywanie nowych kosme-
�
tyków,
- inzynieria - przemys� samochodowy i lotniczy, loty kosmiczne,
�
- informatyka - konstruowanie nowych procesorów, gra& ka komputerowa, opty-
malizacja funkcjonowania sieci komputerowych,
- ekonomia - optymalizacja parametrów makroekonomicznych, wybór opcji na
gie�dzie,
- kryminologia - rozpoznawanie odcisków palców,
- inne - prognoza pogody, cyfrowa technologia audio-video,
- wojsko - tajne/poufne.
Badania teoretyczne koncentruja� sie� na tworzeniu technik obliczeniowych
oraz obejmuja analize b�edów i kosztów metod przyblizonych.
� � �
�
Wobrebie klasycznych metod numerycznych mozemy wyróznić m.in. takie
�
� �
zagadnienia jak:
� analiza b�edów zaokragleń;
� �
� interpolacja
� aproksymacja
� rozwiazywanie równań nieliniowych (czyli znajdowanie miejsc zerowych
�
funkcji)
� ca�kowanie i rózniczkowanie numeryczne
�
� rozwiazywanie uk�adów równań liniowych
�
� obliczanie wartości w�asnych i wektórów w�asnych macierzy
� rozwiazywanie zagadnieńdlarównańrózniczkowych zwyczajnych i czastkowych
� �
�
1
Metody numeryczne to jednocześnie sztuka wyboru metody rozwiazania,
�
która jest  najlepiej dostosowana do danego zadania.
Skutki niefrasobliwego stosowania algorytmów numerycznych:
- podczas wojny w Kuwejcie antyrakieta Patriot traci�a celność po d�ugim okresie
czuwania; skutki: zabici i ranni; przyczyny: wojskowe nierozumienie arytmetyki
komputerowej,
- katastrofa rakiety Ariane 5 tuz po starcie; skutki: strata $500mln; przy-
�
czyny: posrednio - b�edy programistyczne, a bezpośrednio - nadmiar zmienno-
�
przecinkowy,
- zatoniecie platformy wiertniczej Sleipner koncernu Statoil na Morzu Pó�noc-
�
nym; skutki: wstrzas sejsmiczny 3 stopnia w skali Richtera, strata $700mln;
�
przyczyny: z�e oszacowanie b�edów w programie liczacym napre�zenia.
�
�
2. Podstawowe pojecia
�
2.1. Elementy teorii b�edów
�
2.1.1. Rodzaje b�edów
�
Na wyniki obliczeń numerycznych moze wp�yna�ć wiele rodzajów b�edów.
�
�
Mozna je podzielić na kilka grup:
�
1. B�edy zagadnienia (uproszczenia modelu matematycznego) - przy matematy-
�
cznym formu�owaniu zadania w wiekszości zastosowań trzeba idealizować realne
�
zjawiska. Bardzo trudno przewidzieć skutki pewnych b�edów tego typu.
�
2. B�edy danych wejściowych - sazwiazane z obecnościa� w obliczeniach wyników
� � �
pomiarów posiadajacych tylko pewna� ograniczona� dok�adność albo podlegaja-
� �
cych pewnym zak�óceniom. Moga sie róniez pojaw�c na skutek konieczności
� �
�
zaokraglenia niewymiernych parametrów liczbowych. Wiekszość mozliwe do os-
� �
�
zacowania.
3. B�edy obciecia - bardzo wiele zagadnień mozna rozwiazać dok�adnie tylko za
� � �
�
pomoca� procesów nieskończonych, pojawiaja� sie� one, gdy obliczenia kończy sie�
przed osiagnieciem wartości granicznej. Nietrudno je oszacować.
� �
4. B�edy obliczeń - spowodowane zaokraglaniem wyników obliczeń, sa� zwiazane
� � �
z precyzja� danej maszyny (zaleza� od procesora i jezyka programowania). Cza-
�
�
sami moga bżc bardzo dotkliwe w skutkach, ale mozna je zbadać.
�
�
 5. B�edy cz�owieka i b�edy maszynowe - wkazdych obliczeniach moga� pojaw�c
� �
�
sie� b�edy powstajace na skutek pomy�ek, b�edy pisarskie, b�edy w programie,
� � � �
b�edy przy wprowadzaniu danych, itp.. Niemozliwe do przewidzenia.
�
�
B�ad ca�kowity obliczeń powstaje w wyniku skumulowania wszystkich rodza-
�
jów b�edów.
�
Niech x oznacza wartość przyblizona� pewnej wielkości, której wartościa� dok�adna�
�
jest x.
ą
DEFINICJA 1. B�edem bezwzglednym óx wartości x nazywamy norme
� � �
róznicy pomiedzy wartościa przyblizona x i wartóscia dok�adna x, tj.
� � � � � ą
� �
óx = kx Ą xk : (1)
ą
Poniewaz b�ad bezwzgledny nie charakteryzuje w pe�ni dok�adności obliczeń,
� �
�
to czesto w zagadnieniach numerycznych korzysta sie z b�edu wzglednego:
� � � �
2
DEFINICJA 2. B�edem wzglednym ąx wartości przyblizonej x nazywamy
� �
�
stosunek b�e�du bezwzglednego óx tej wartości do normy wartości dok�adnej x,
� ą
tj.
kx Ą xk
ą
ąx = ; (2)
kxk
ą
o ile x =0.
ą 6
B�ad wzgledny mozna równiez wyrazać procentowo, tzn. ą% = ą ó 100%.
� �
� � �
2.1.2. Przenoszenie sie� b�edów
�
TWIERDZENIE 3. B�edy wyników dzia�ań arytmetycznych wyrazaja sie
� � �
�
nastepujacymi wzorami:
� �
(i) dla dodawania i odejmowania - jeśli y = x1 ż x2, to
jx1j ąx1 + jx2j ąx1
óy =óx1 +óx2 oraz ąy = ;
y
(ii) dla mnozenia - jeśli y = x1 ó x2, to
�
Ż Ż Ż Ż
Ż Ż Ż Ż
y y
Ż Ż Ż Ż
óy = óx1 + óx2 oraz ąy = ąx1 + ąx1;
Żx1 Ż Żx2 Ż
(iii) dla dzielenia - jeśli y = x1=x2, x2 =0, to
6
jx1j óx2 + jx2jóx1
óy = oraz ąy = ąx1 + ąx2:
x2
2
UWAGA: Róznica dwóch liczb bardzo bliskich sobie moze mieć bardzo ma�a�
� �
dok�adność wzgledna, np. niech
� �
1 1
x1 =0:5764 ż ó 10Ą4 i x2 =0:5763 ż ó 10Ą4;
2 2
wówczas
x1 Ą x2 =0:0001 oraz óx1Ąx2 =0:0001
czyli b�ad bezwzgledny róznicy jest tak samo duzy, jak otrzymana róznica, a
� �
� � �
stad ąx1Ąx2 = 100%.
�
Podstawowe zadanie teorii b�edów mozna sformu�ować nastepujaco: wyz-
� � �
�
naczyć b�ad danej funkcji, gdy znane sab�edy wszystkich jej argumentów. Niech
� � �
zatem bedzie dana funkcja rózniczkowalna y = f (x1;x2; :::; xn). P rzypśsćmy,
�
�
ze znane sa� b�edy bezwzgledne argumentów tej funkcji jóxij;i =1; :::; n.
� �
�
TWIERDZENIE 4. Ogólny wzór na przenoszenie sie� b�e�dów jest postaci:
Ż Ż
n
X
Ż Ż
@f
Ż Żóxi ,(3)
óy =
Ż@xi Ż
i=1
3
czyli b�ad bezwzgledny óy aproksymuje sie za pomoca rózniczki zupe�nej funkcji
� � � �
�
f.
WNIOSEK 5. B�ad wzgledny wartości funkcji jest równy b�edowi bezwzgled-
� � � �
nemu jej logarytmu naturalnego, tzn.
Ż Ż
Ż Ż
n @f n
Ż Ż
X
Ż
Ż @xi
Żó = X Ż @
Ż
ąy = Ż Ż
xi
Ż@xi ln yŻ óxi .
Ż Ż
y
i=1 i=1
UWAGA: Poszczególne cze�ści tw.3 sa� szczególnym%2ł przypadkami tw. 4 i wn.
5.
PRZYK�AD: Oszacować b�ad obliczenia objetości kuli, jeśli jej promień
� �
wynosi r =2:1cm ż 0:05cm, a ź =3:14. Traktujac r i ź jako wielkości zmienne
�
4
obliczamy pochodne czastkowe (V = źr3)
�
3
@V 4 @V
= r3 =12: 35, =4źr2 =55: 39:
@ź 3 @r
Na mocy wzoru (3) b�ad bezwzgledny objetości kuli wynosi
� � �
Ż Ż Ż Ż
Ż@V Ż Ż@V Ż
Ż Ż Ż Żór = 8442:2 ó 0:0016 + 4300:8 ó 0:05 = 0:1976 + 2:769 = 2:967:
óV = óź +
Ż Ż Ż Ż
@ź @r
Zatem
V =38:77cm3 ż 2:967cm3;
a b�ad wzgledny z de& nicji:
� �
2:967
ąV = ź 0:07652 czyli ą% =7:65%:
38:77
2.2. Komputerowa reprezentacja liczb
Komputery komunikuja sie z uzytkownikami w uk�adzie dziesiatkowym, ale
� � �
�
wykonuja� dzia�ania w uk�adzie dwójkowym. Oczywiście dzia�ania moga� bżc
wykonywane jedynie na liczbach rzeczywistych przedstawionych za pomocaskońc-
�
zonej ilości cyfr, nie wiekszej niz pewna ustalona liczba.
�
�
W uk�adzie dziesiatkowym kazda liczba rzeczywista x =0 moze być przed-
� 6
� �
stawiona w reprezentacji zmiennopozycyjnej (zmiennoprzecinkowej),
tzn.
x = m ó 2c ,
m � �
gdzie liczbe� nazywamy mantysa, z�s c - cecha lub wyk�adnikiem. Reprezen-
tacja jest znormalizowana, gdy
1
�jmj < 1.
2
4
Ograniczenia na m i c w komputerach sa� wyznaczone przez d�ugość s�owa
maszynowego. Jego cze�ść jest przeznaczona na mantyse, a cze�ść na ceche, a
� �
mianowicie zwykle:
s c1 ... cl m1 ... mk
gdzie kolejne bity zawieraja� nastepujace informacje: s - znak liczby (1 oznacza
� �
ujemność), c1; :::; cl - cyfry cechy, m1; :::; mk - cyfry mantysy.
PRZYK�AD: W komputerze, w którym d�ugość s�owa maszynowego wynosi
32 bity, na ceche� przeznaczonych jest l = 8 bitów, natomiast na mantyse� -
k =23, tzn. liczba jest reprezentowana wówczas nastepujaco:
�
s c1 ... c8 m1 ... m23
Wartość takiej liczby jest wyznaczana ze wzoru
�
(Ą1)s2cĄ127(1:m) dla 0 :
(Ą1)s2Ą126(0:m) dla c =0, m =0
6
Oznacza to, ze rozwazany komputer moze wykonywać dzia�ania na liczbach
� � �
o wartósci bezwzglednej z zakresu (oko�o) 1:5 ó 10Ą45:::3:4 ó 1038. Ten zakres
�
(typ Float w C lub Single w Pascalu) jest czesto niewystarczajacy dla pewnych
� �
obliczeń numerycznych, wiec czesto uzywa sie� arytmetyki o podwójnej dok�ad-
� �
�
ności (tzn. Double) - liczba jest reprezentowana wtedy przez podwójne s�owo
maszynowe (mamy wówczas podzia� 1+11+51).
DEFINICJA 6. Jeśli liczba rzeczywista x daje sie� zapis�c w postaci zmi-
ennopozycyjnej w danym komputerze, to mówimy, ze x jest liczbamaszynowa.
� �
�
Zatem liczba maszynowa x moze być dok�adnie przedstawiona w tym kom-
�
puterze. Wiekszość liczb rzeczywistych nie daje sie dok�adnie przedstawić w
� �
postaci liczb maszynowych. Bez wzgledu na to, czy taka liczba pojawi sie� jako
�
wprowadzana dana, czy jako wynik obliczeń, to powstaje b�ad wynikajacy z
� �
przyblizenia tej liczby przez najblizsza jej liczbe maszynowa. Oznaczmy przez
� � �
� �
rd(x) liczbe� maszynowa, która jest jej najblizsza.liczbie x. rd(x) bedziemy nazy-
� �
�
wać reprezentacja� maszynowa� liczby x.
PRZYK�AD: Rozwazmy znów typ rzeczywisty Float w jezyku C. Poniewaz
�
� �
23 cyfry binarne mantysy odpowiadaja� cyfrom dziesietnym, to taka reprezenacja
7 �
oferuje 7-cyfrowa precyzje zmiennopozycyjna. Np.
� � �
0 101100110:::0 11000010
Pierwszy bit z lewej jest 0, wiec liczba jest dodatnia. Nastepne 8 bitów jest
� �
równowazne liczbie dziesietnej
�
�
1 ó 27 +1ó 26 +1ó 21 =194:
Ostatnie 23 bity wskazuja, ze mantysa wynosi
�
�
1 ó 2Ą1 +1ó 2Ą3 +1ó 2Ą4 +1ó 2Ą7 +1ó 2Ą8 =0:69921875
5
W konsekwencji, rozwazana liczba maszynowa reprezentuje liczbe� dziesietna�
�
�
+0:69921875 ó 2194Ą127 =+1:031 864747 ó 1020 = x:
Jednak, nastepna liczba maszynowa jest
� � � �
0 101100110:::01 11000010 =+1: 031864923 ó 1020
zaś poprzednia
�
0 101100101:::1 11000010 =1:031 864571 ó 1020;
a to oznacza, ze pierwsza z rozwazanych liczb maszynowych reprezentuje nie
� �
tylko liczbe x, ale równiez wiele liczb, które sa miedzy nia a sasiednimi liczbami
� � � � �
�
maszynowymi.
UWAGA: Oczywiście zbiór liczb maszynowych M � R, jest zbiorem skońc-
zonym i ograniczonym.
Zpowyzszego przyk�adu wynika, ze wszystkie liczby rzeczywiste x z pewnego
� �
przedzia�u sa przyblizane tylko przez jedna najblizsza imliczbe maszynowa xń.
� � � � �
� �
Bedzie ona oddalona nie wiecej niz o po�owe� wiekszej z odleg�ości a1 i a2 miedzy
� � � �
�
dwoma liczbami maszynowymi po�ozonymi w poblizu x. Liczby maszynowe
� �
sa roz�ozone nierówno na osi liczbowej, tzn. sa po�ozone geściej w poblizu
� � �
� � �
0 i coraz rzadziej w kierunku krańców zakresu. Im liczba wieksza, tym ma
�
wiekszy wyk�adnik, zatem odleg�ość miedzy kolejnymi coraz wiekszymi co do
� � �
wartości bezwzglednej liczbami maszynowymi rośnie, a przeciez miedzy kole-
� �
�
jnymi potegami liczby 2 jest zawsze ta sama ilość liczb maszynowych.
�
DEFINICJA 7. Epsilon maszynowy "m jest to graniczna wartość b�edu
�
wzglednego przyblizenia zmiennoprzecinkowego.
�
�
Praktycznie oznacza to, ze dane bedace konkretnego typu rzeczywsitego nie
� �
�
mogabyć pamietane przez komputer z dok�adnościawiekszaniz "m. Intuicyjnie:
� � � � �
�
1+"m jest najmniejsza� liczba� wieksza� od1, która� komputer potra& odróznić od
�
�
1. Bardziej uogólniajac:
�
rd(x) =x (1 + "m)
2.3. Zaokraglenie i obciecie liczby
� �
DEFINICJA 8. Cyfra znaczaca wartósci przyblizonej liczby rzeczy-
� � � �
wistej nazywamy kazda�zachowanacyfre�rozwiniecia dziesietnego tej liczby rózna�
� � �
� �
od 0 oraz 0, j�sli jest ono zawarte miedzy cyframi znaczacymi lub znajduje
� �
sie na zachowanej pozycji. Mówimy, ze liczba przyblizona ma n poprawnych
�
� �
(dok�adnych) cyfr znaczacych, jezeli b�ad bezwzgledny tej liczby nie przewyzsza
� � �
� �
po�owy jedności pozycji, okr�slonej przez n-ta cyfre znaczaca, liczac od lewej.
� � � � �
ą
PRZYK�AD: Dla liczby dok�adnej x = 35:97 jej przyblizenie x = 36:00
�
posiada 4 cyfry znaczace, ale tylko 3 cyfry sa poprawne, gdyz óx = 0:03 <
� �
�
1
0:05 = ó 10Ą1 (ąx =8:3 ó 10Ą4).
2
6
UWAGA: (i) Poczatkowe zera s�uza jedynie do wskazania pozycji dziesiet-
� �
�
nych innych cyfr. Końcowe zera sa� cyframi znaczacymi, poniewaz wskazuja, ze
� �
� �
w liczbie przyblizonej zachowano dana pozycje.
� �
�
(ii) Liczba cyfr znaczacych daje bezpośrednio pojecie o wielkości b�edu wzgled-
� � � �
nego, liczba cyfr poprawnych - pośrednio o wielkości b�edu bezwzglednego.
� �
REGU�A ZAOKRAGLANIA:
�
Aby zaokraglić liczbe� do n cyfr znaczacych, nalezy odrzucić wszystkie jej
� �
�
cyfry zapisane z prawej strony n-tej cyfry znaczacej. Przy tym jeśli odrzuca sie
� �
co do modu�u wartość:
1
(i) mniejsza� niz ó 10Ąn, to n-ta� cyfre� pozostawia sie� bez zmian;
�
2
1
(ii) wieksza niz ó 10Ąn, to do n-tej cyfry dodaje sie 1;
� � �
�
2
1
(iii) równa� ó 10Ąn, to n-ta� cyfre� zwiesza sie� o 1, j�sli jest nieparzysta, a po-
�
2
zostawia sie� bez zmian, gdy jest parzysta (dla jednakowej czestości b�edów ujem-
� �
nych i dodatnich).
PRZYK�AD: Zaokraglanie do 4 cyfr znaczacych:
� �
liczba odrzucony fragment zaokraglenie b�ad bezwzgledny
� � �
3:1497 0:7 ó 10Ą3 3:150 0:3 ó 10Ą3
Ą3:1497 0:7 ó 10Ą3 Ą3:150 0:3 ó 10Ą3
3:1435 0:5 ó 10Ą3 3:144 0:5 ó 10Ą3
3:1425 0:5 ó 10Ą3 3:142 0:5 ó 10Ą3
UWAGA: (i) Wiekszość komputerów, w których wykonuje sie� zaokraglenie,
� �
1
tylko zwieksza albo tylko zmniejsza liczbe o ó 10Ąn w przypadku (iii), gdyz
� �
�
2
jest to technicznie �atwiejsze.
(ii) B�ad bezwzgledny zaokraglenia nie przewyzsza po�owy jedności pozycji dziesiet-
� � � �
�
nej, określonej przez ostatnia pozostawiona cyfre znaczaca, tzn.
� � � � �
1
jx Ą xj � ó 10Ąn .
ą
2
2.4. Uwarunkowanie zadania, algorytmy i zbiezność
�
Dowolne zadanie obliczeniowe mozna przedstawić jako pewne odwzorowanie
�
�: Rn ! Rm postaci
w =�(d) ;
gdzie d =[d1; :::; dn]T jest wektorem danych, a w =[w1; :::; wm]T - wektorem
wyników. Oczywiście w praktyce dysponujemy jedynie reprezentacjami maszynowymi
danych rd(di) dla i =1;:::; n
DEFINICJA 9. Mówimy, ze zadanie jest z
le uwarunkowane, j�sli ma�e
�
wzgledne zmiany danych powoduja� odpowiednio duze wzgledne zmiany wyników.
� �
�
W przeciwnym razie, mówimy, ze zadanie jest dobrze uwarunkowane.
�
Wskaz
nikiem uwarunkowania bedziemy nazywać pewna wielkósć charak-
� �
teryzujaca� wzrost zmian wyniku w stosunku do zmian danych.
�
PRZYK�AD: Klasycznym przyk�adem zadania z
le uwarunkowanego jest rów-
nanie
P(x) � (x Ą 1)(x Ą 2):::(x Ą 20) = 0;
7
posiadajace 20 pierwiastków rzeczywistych x =1; 2;:::;20. J�sli zak�ócimy np.
�
wspó�czynnik przy x19 jedynie o 10Ą7, to w konsekwencji rowiazania zmieni-
�
aja sie drastycznie. Tym razem wielomian P bedzie mia� 5 par pierwiastków
� � �
zespolonych i 1 rzeczywisty x = Ą20:847.
Innymi s�owy: uwarunkowanie zadania określa, jak rozwiazanie tego zadania
�
jest wrazliwe na ma�e zaburzenia danych, a wskaz
nik uwarunkowania jest miara
�
�
tej wrazliwości. Teoretyczna de& nicja wskaz
nika uwarunkowania jest nieprak-
�
tyczna i zwykle i przyjmuje sie go jako najmniejsza z liczb �(d), dla których
� �
zachodzi
ąw � �(d) ó ąd:
PRZYK�AD: Rozwazmy zadanie obliczania iloczynu skalarnego:
�
n
X
�(u;v) = uivi;
i=1
dla:
Ł ń Ł ń
(i) u = 1 2 3 , v = 2ń 6 Ą5 ;
Ł Ł ń
(ii) u = 1:02 2:04 2:96 , v = 2 6 Ą5 .
W przypadku (i) mamy w = Ą1, a w (ii) w = Ą0:52. Zatem zaburzenie jednego
z wektorów wielkości 2% spowodowa�y zaburzenie wyniku wielkości 48%. Gdyby
Ł ń
wektor v = 2 6 5 , to zaburzenie wyniku by�oby mniejsze niz 3%, a zatem
�
porównywalne z zaburzeniami danych.
UWAGA: Na podstawie powyzszego mozna wywnioskować, ze uwarunowanie
� � �
zadania zalezy od wartości danych.
�
W ogólnej teorii metod numerycznych nalezy zdecydowanie odróznić trzy
� �
nastepujace pojecia:
� � �
1. Zadanie obliczeniowe w =�(d);
2. Algorytm A(d) obliczenia wyniku zadania � czyli procedura, opisujaca
�
skończony ciag kroków, które nalezy wykonać w podanej kolejności, aby znalez
ć
�
�
rozwiazanie problemu lub przyblizenie rozwiazania.
� �
�
3. Numeryczna realizacja fl(A(d)) algorytmu A - polega na zastapieniu
�
liczb wystepujacych w A(d) ich reprezentacjami maszynowymi i wykonaniu op-
� �
eracji arytmetycznych w arytmetyce zmiennopozycyjnej oferowanej przez dana�
maszyne.
�
PRZYK�AD: Zadanie �(a;b) =a2 Ą b2, algorytmy: A1(a; b) =a ó a Ą b ó b,
A2(a; b) =(a + b) ó (a Ą b) i ich realizacja numeryczna
fl(A1(a; b)) = fl(a ó a Ą b ó b) =fl [fl(a ó a) Ą fl(b ó b)] ;
fl(A2(a;b) = fl [(a + b) ó (a Ą b)] = fl [fl(a + b) ó fl(a Ą b)]:
Mozna wykazać, ze
�
� Ż Ż
Ą ó Ża2 + b2 Żś
fl(A1(a; b)) = a2 Ą b2 (1 + ą1), gdzie ją1j � 1+Ż Ż "m;
Ża Ą b2 Ż
2
Ą ó
fl(A2(a; b)) = a2 Ą b2 (1 + ą2), gdzie ją2j �3"m;
8
co implikuje, ze algorytm A1 ma gorsze w�asności numeryczne niz algorytm A2.
� �
W przypadku, gdy kwadraty obu liczb sa� bliskie, moze dojść do silnego wzrostu
�
b�edu wzglednego ą1, podczas gdy b�ad wzgledny ą2 jest niewrazliwy na wartości
� � � �
�
danych a i b.
Jesteśmy oczywiście zainteresowani wybieraniem takich metod, które daja�
dok�adne wyniki. Jednym z warunków, które nak�ada sie na algorytm, o ile jest
�
to mozliwe, jest stabilność.
�
DEFINICJA 10. Mówimy, ze algorytm jest stabilny, jeśli posiada nastepu-
�
�
jaca w�asnósć: ma�e b�edy powsta�e w pewnym kroku algorytmu nie sa powiek-
� � � � �
szane w innych krokach oraz nie powoduja� powaznego ograniczenia dokadności
�
wszystkich obliczeń. W przeciwnym razie, mówimy, ze algorytm jest niesta-
�
bilny.
Innymi s�owami: algorytm stabilny gwarantuje uzyskanie wyniku z b�edem
�
wzglednym tego samego rzedu wielkości, co b�ad wzgledny spowodowany jedynie
� � � �
zaburzeniami danych i b�edem reprezentacji maszynowej.
�
Niektóre algorytmy sa stabilne zawsze (bez wzgledu na dane wejściowe), zaś
� �
stabilność innych zalezy od wyboru danych wejściowych.
�
DEFINICJA 11. Niech " bedzie b�edem zaokraglenia i En b�edem po wykona-
� � � �
niu n kroków algorytmu. Jeśli jEnj źCn", gdzie C jest pewna sta�a niezalezna
� � �
�
od n, to mówimy, ze wzrost b�edu jest liniowy. J�sli jEnj źkn", dla pewnego
� �
k >1, to wzrost b�edu jest wyk�adniczy.
�
Liniowy wzrost b�edu jest zwykle nie do unikniecia i gdy C oraz " sa ma�e,
� � �
to wyniki sa� ogólnie akceptowalne. Wzrostu wyk�adniczego powinno sie� unikać,
gdyz prowadzi do nieakceptowalnych niedok�adności. W konsekwencji, algo-
�
rytm, który charakteryzuje sie� liniowym wzrostem b�edu, jest stabilny, zaś ago-
�
rytm z wyk�adniczym wzrostem jest niestabilny.
Oczywiście, aby uniknać efektów b�edu zaokraglenia, mozna uzywać wiek-
� � � �
� �
szej precyzji obliczeń (podwójnej lub rozszerzonej), o ile maszyna lub opro-
gramowanie oferuja� taka� mozliwość. Nalezy jednak pamietać, ze im wyzsza
� � � �
precyzja obliczeń, tym bardziej sa one czaso- i pamiecio-ch�onne.
� �
Podsumowujac ta� cze�ść rozwazań, mozemy stwierdzić, ze b�ad jego nuem-
� �
� � �
rycznej realizacji algorytmu zalezy od 3 czynników:
�
- uwarunkowania zadania, którego miara� jest wsk�znik uwarunkowania �,
- stabilności algorytmu,
- stosowanej arytmetyki zmiennopozycyjnej, która jest charakteryzowana przez
epsilon maszynowy "m.
9