1 - Praktyka metod numerycznych

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 przybliz· onego 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, - inz· ynieria - przemys÷ samochodowy i lotniczy, loty kosmiczne, - informatyka - konstruowanie nowych procesorów, gra…ka komputerowa, optymalizacja 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 przybliz· onych. ¾ W obrebie klasycznych metod numerycznych moz· emy wyróz· ni´c m.in. takie ¾ zagadnienia jak: ² analiza b÷edów zaokragle´ ¾ ¾ n; ² interpolacja ² aproksymacja ² rozwiazywanie równa´n nieliniowych (czyli znajdowanie miejsc zerowych ¾ funkcji) ² ca÷kowanie i róz· niczkowanie numeryczne ² rozwiazywanie uk÷adów równa´n liniowych ¾ ² obliczanie warto´sci w÷asnych i wektórów w÷asnych macierzy ² rozwiazywanie zagadnie´n dla równa´n róz· niczkowych zwyczajnych i czastkowych ¾ ¾ 1

Metody numeryczne to jednocze´snie 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´s´c po d÷ugim okresie czuwania; skutki: zabici i ranni; przyczyny: wojskowe nierozumienie arytmetyki komputerowej, - katastrofa rakiety Ariane 5 tuz· po starcie; skutki: strata $500mln; przyczyny: posrednio - b÷edy ¾ programistyczne, a bezpo´srednio - nadmiar zmiennoprzecinkowy, - 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¾z· enia. ¾

2. Podstawowe pojecia ¾

2.1. Elementy teorii b÷edów ¾ 2.1.1. Rodzaje b÷edów ¾

Na wyniki oblicze´n numerycznych moz· e wp÷yna´ ¾c wiele rodzajów b÷edów. ¾ Moz· na je podzieli´c na kilka grup: 1. B÷edy ¾ zagadnienia (uproszczenia modelu matematycznego) - przy matematycznym formu÷owaniu zadania w wiekszo´ sci zastosowa´n trzeba idealizowa´c realne ¾ zjawiska. Bardzo trudno przewidzie´c skutki pewnych b÷edów tego typu. ¾ 2. B÷edy z obecno´scia¾ w obliczeniach wyników ¾ ¾ danych wej´sciowych - sa¾ zwiazane pomiarów posiadajacych tylko pewna¾ ograniczona¾ dok÷adno´s´c albo podlegaja¾ ¾ cych pewnym zak÷óceniom. Moga¾ sie¾ róniez· pojawi´c na skutek konieczno´sci zaokraglenia niewymiernych parametrów liczbowych. Wiekszo´ s´c moz· liwe do os¾ ¾ zacowania. 3. B÷edy - bardzo wiele zagadnie´n moz· na rozwiaza´ ¾ obciecia ¾ ¾ c dok÷adnie tylko za pomoca¾ procesów niesko´nczonych, pojawiaja¾ sie¾ one, gdy obliczenia ko´nczy sie¾ przed osiagni warto´sci granicznej. Nietrudno je oszacowa´c. ¾ eciem ¾ n - spowodowane zaokraglaniem 4. B÷edy wyników oblicze´n, sa¾ zwiazane ¾ ¾ ¾ oblicze´ z precyzja¾ danej maszyny (zalez· a¾ od procesora i jezyka programowania). Cza¾ sami moga¾ by´c bardzo dotkliwe w skutkach, ale moz· na je zbada´c. ”5.” B÷edy ¾ cz÷owieka i b÷edy ¾ maszynowe - w kaz· dych obliczeniach moga¾ pojawi´c sie¾ b÷edy ¾ powstajace ¾ na skutek pomy÷ek, b÷edy ¾ pisarskie, b÷edy ¾ w programie, b÷edy ¾ przy wprowadzaniu danych, itp.. Niemoz· liwe do przewidzenia. B÷ad ¾ ca÷kowity oblicze´n powstaje w wyniku skumulowania wszystkich rodzajów b÷edów. ¾ Niech x oznacza warto´s´c przybliz· ona¾ pewnej wielko´sci, której warto´scia¾ dok÷adna¾ ¹. jest x bezwzglednym ¢x warto´sci x nazywamy norme¾ DEFINICJA 1. B÷edem ¾ ¾ róz·nicy pomiedzy warto´scia¾ przybliz·ona¾ x i warto´scia¾ dok÷adna¾ x ¹, tj. ¾ ¢x = kx ¡ x ¹k :

(1)

Poniewaz· b÷ad nie charakteryzuje w pe÷ni dok÷adno´sci oblicze´n, ¾ bezwzgledny ¾ to czesto w zagadnieniach numerycznych korzysta sie¾ z b÷edu ¾ ¾ wzglednego: ¾ 2

wzglednym ± x warto´sci przybliz·onej x nazywamy DEFINICJA 2. B÷edem ¾ ¾ ¹, stosunek b÷edu ¢x tej warto´sci do normy warto´sci dok÷adnej x ¾ bezwzglednego ¾ tj. ±x =

kx ¡ x ¹k ; k¹ xk

(2)

o ile x ¹ 6= 0. B÷ad moz· na równiez· wyraz· a´c procentowo, tzn. ± % = ± ¢ 100%. ¾ wzgledny ¾

2.1.2. Przenoszenie sie¾ b÷edów ¾ n arytmetycznych wyraz·aja¾ sie¾ TWIERDZENIE 3. B÷edy ¾ wyników dzia÷a´ nastepuj wzorami: ¾ acymi ¾ (i) dla dodawania i odejmowania - je´sli y = x1 § x2 , to ¢y = ¢x1 + ¢x2 oraz ± y =

jx1 j ± x1 + jx2 j ± x1 ; y

(ii) dla mnoz·enia - je´sli y = x1 ¢ x2 , to ¯ ¯ ¯ ¯ ¯y¯ ¯y¯ ¯ ¯ ¢y = ¯ ¯ ¢x1 + ¯¯ ¯¯ ¢x2 oraz ± y = ± x1 + ± x1 ; x1 x2

(iii) dla dzielenia - je´sli y = x1 =x2 , x2 6= 0, to ¢y =

jx1 j ¢x2 + jx2 j ¢x1 oraz ± y = ± x1 + ± x2 : x22

UWAGA: Róz· nica dwóch liczb bardzo bliskich sobie moz· e mie´c bardzo ma÷a¾ dok÷adno´s´c wzgledn ¾ a, ¾ np. niech x1 = 0:5764 §

1 1 ¢ 10¡4 i x2 = 0:5763 § ¢ 10¡4 ; 2 2

wówczas x1 ¡ x2 = 0:0001 oraz ¢x1 ¡x2 = 0:0001 czyli b÷ad róz· nicy jest tak samo duz· y, jak otrzymana róz· nica, a ¾ bezwzgledny ¾ stad ¾ ± x1 ¡x2 = 100%. Podstawowe zadanie teorii b÷edów moz· na sformu÷owa´c nastepuj wyz¾ ¾ aco: ¾ naczy´c b÷ad ¾ danej funkcji, gdy znane sa¾ b÷edy ¾ wszystkich jej argumentów. Niech zatem bedzie dana funkcja róz· niczkowalna y = f (x1 ; x2 ; :::; xn ). Przypu´s´cmy, ¾ z· e znane sa¾ b÷edy argumentów tej funkcji j¢xi j ; i = 1; :::; n. ¾ bezwzgledne ¾ jest postaci: TWIERDZENIE 4. Ogólny wzór na przenoszenie sie¾ b÷edów ¾ ¯ n ¯ X ¯ @f ¯ ¯ ¯ ¢y = (3) ¯ @xi ¯ ¢xi , i=1 3

czyli b÷ad ¢y aproksymuje sie¾ za pomoca¾ róz·niczki zupe÷nej funkcji ¾ bezwzgledny ¾ f. warto´sci funkcji jest równy b÷edowi bezwzgledWNIOSEK 5. B÷ad ¾ wzgledny ¾ ¾ ¾ nemu jej logarytmu naturalnego, tzn. ¯ ¯ ¯ n ¯ @f ¯ n ¯ X X ¯ ¯ @ ¯ @xi ¯ ¯ ¢x . ¯ ±y = ln y ¯ ¢xi = ¯ ¯ i ¯ ¯ y ¯ @xi i=1 i=1 UWAGA: Poszczególne cze´ ¾sci tw.3 sa¾ szczególnymi przypadkami tw. 4 i wn.

5.

PRZYK×AD: Oszacowa´c b÷ad ¾ obliczenia objeto´ ¾ sci kuli, je´sli jej promie´n wynosi r = 2:1cm § 0:05cm, a ¼ = 3:14. Traktujac ¾ r i ¼ jako wielko´sci zmienne obliczamy pochodne czastkowe (V = 43 ¼r3 ) ¾ 4 @V @V = r3 = 12: 35, = 4¼r2 = 55: 39: @¼ 3 @r Na mocy wzoru (3) b÷ad objeto´ ¾ bezwzgledny ¾ ¾ sci 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 z de…nicji: ¾ wzgledny ¾ ±V =

2:967 ¼ 0:07652 czyli ± % = 7:65%: 38: 77

2.2. Komputerowa reprezentacja liczb Komputery komunikuja¾ sie¾ z uz· ytkownikami w uk÷adzie dziesiatkowym, ale ¾ wykonuja¾ dzia÷ania w uk÷adzie dwójkowym. Oczywi´scie dzia÷ania moga¾ by´c wykonywane jedynie na liczbach rzeczywistych przedstawionych za pomoca¾ sko´nczonej ilo´sci cyfr, nie wiekszej niz· pewna ustalona liczba. ¾ W uk÷adzie dziesiatkowym kaz· da liczba rzeczywista x 6= 0 moz· e by´c przed¾ stawiona w reprezentacji zmiennopozycyjnej (zmiennoprzecinkowej), tzn. x = m ¢ 2c , gdzie liczbe¾ m nazywamy mantysa,¾ za´s c - cecha¾ lub wyk÷adnikiem. Reprezentacja jest znormalizowana, gdy 1 · jmj < 1. 2 4

Ograniczenia na m i c w komputerach sa¾ wyznaczone przez d÷ugo´s´c s÷owa maszynowego. Jego cze´ ¾s´c jest przeznaczona na mantyse, ¾ a cze´ ¾s´c na ceche, ¾ a mianowicie zwykle: s

c1

...

cl

m1

...

mk

gdzie kolejne bity zawieraja¾ nastepuj ¾ ace ¾ informacje: s - znak liczby (1 oznacza ujemno´s´c), c1 ; :::; cl - cyfry cechy, m1 ; :::; mk - cyfry mantysy. PRZYK×AD: W komputerze, w którym d÷ugo´s´c 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´s´c takiej liczby jest wyznaczana ze wzoru ½ (¡1)s 2c¡127 (1:m) dla 0 < c < 255 : (¡1)s 2¡126 (0:m) dla c = 0, m 6= 0 Oznacza to, z· e rozwaz· any komputer moz· e wykonywa´c dzia÷ania na liczbach o warto´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´n numerycznych, wiec uz· ywa sie¾ arytmetyki o podwójnej dok÷ad¾ czesto ¾ no´sci (tzn. Double) - liczba jest reprezentowana wtedy przez podwójne s÷owo maszynowe (mamy wówczas podzia÷ 1 + 11 + 51). DEFINICJA 6. Je´sli liczba rzeczywista x daje sie¾ zapisa´c w postaci zmiennopozycyjnej w danym komputerze, to mówimy, z·e x jest liczba¾ maszynowa. ¾ Zatem liczba maszynowa x moz· e by´c dok÷adnie przedstawiona w tym komputerze. Wiekszo´ s´c liczb rzeczywistych nie daje sie¾ dok÷adnie przedstawi´c w ¾ postaci liczb maszynowych. Bez wzgledu ¾ na to, czy taka liczba pojawi sie¾ jako wprowadzana dana, czy jako wynik oblicze´n, to powstaje b÷ad ¾ wynikajacy ¾ z przybliz· enia tej liczby przez najbliz· sza¾ jej liczbe¾ maszynowa. ¾ Oznaczmy przez rd(x) liczbe¾ maszynowa, nazy¾ która jest jej najbliz· sza.liczbie x. rd(x) bedziemy ¾ wa´c reprezentacja¾ maszynowa¾ liczby x. PRZYK×AD: Rozwaz· my znów typ rzeczywisty Float w jezyku C. Poniewaz· ¾ 23 cyfry binarne mantysy odpowiadaja¾ 7 cyfrom dziesietnym, to taka reprezenacja ¾ oferuje 7-cyfrowa¾ precyzje¾ zmiennopozycyjna. ¾ Np. 0 101100110:::0 11000010 8 bitów jest Pierwszy bit z lewej jest 0, wiec ¾ liczba jest dodatnia. Nastepne ¾ równowaz· ne liczbie dziesietnej ¾ 1 ¢ 27 + 1 ¢ 26 + 1 ¢ 21 = 194: Ostatnie 23 bity wskazuja, ¾ z· e mantysa wynosi 1 ¢ 2¡1 + 1 ¢ 2¡3 + 1 ¢ 2¡4 + 1 ¢ 2¡7 + 1 ¢ 2¡8 = 0:69921875 5

W konsekwencji, rozwaz· ana liczba maszynowa reprezentuje liczbe¾ dziesietn ¾ a¾ +0:69921875 ¢ 2194¡127 = +1: 031 864 747 ¢ 1020 = x: Jednak, nastepn ¾ a¾ liczba¾ maszynowa¾ jest 0 101100110:::01 11000010 = +1: 031 864 923 ¢ 1020 za´s poprzednia¾ 0 101100101:::1 11000010 = 1: 031 864 571 ¢ 1020 ; a to oznacza, z· e pierwsza z rozwaz· anych liczb maszynowych reprezentuje nie tylko liczbe¾ x, ale równiez· wiele liczb, które sa¾ miedzy nia¾ a sasiednimi liczbami ¾ ¾ maszynowymi. UWAGA: Oczywi´scie zbiór liczb maszynowych M Ã R, jest zbiorem sko´nczonym i ograniczonym. Z powyz· szego przyk÷adu wynika, z· e wszystkie liczby rzeczywiste x z pewnego przedzia÷u sa¾ przybliz· ane tylko przez jedna¾ najbliz· sza¾ im liczbe¾ maszynowa¾ x¤ . Bedzie ona oddalona nie wiecej z odleg÷o´sci a1 i a2 miedzy ¾ ¾ ¾ niz· o po÷owe¾ wiekszej ¾ dwoma liczbami maszynowymi po÷oz· onymi w pobliz· u x. Liczby maszynowe sa¾ roz÷oz· one nierówno na osi liczbowej, tzn. sa¾ po÷oz· one ge´ ¾sciej w pobliz· u 0 i coraz rzadziej w kierunku kra´nców zakresu. Im liczba wieksza, tym ma ¾ wiekszy wyk÷adnik, zatem odleg÷o´s´c miedzy kolejnymi coraz wiekszymi co do ¾ ¾ ¾ warto´sci bezwzglednej liczbami maszynowymi ro´snie, a przeciez· miedzy kole¾ ¾ jnymi potegami liczby 2 jest zawsze ta sama ilo´s´c liczb maszynowych. ¾ DEFINICJA 7. Epsilon maszynowy "m jest to graniczna warto´s´c b÷edu ¾ wzglednego przybliz·enia zmiennoprzecinkowego. ¾ Praktycznie oznacza to, z· e dane bed ¾ ace ¾ konkretnego typu rzeczywsitego nie moga¾ by´c pamietane przez komputer z dok÷adno´scia¾ wieksz ¾ ¾ a¾ niz· "m . Intuicyjnie: 1 + "m jest najmniejsza¾ liczba¾ wieksz ¾ a¾ od 1, która¾ komputer potra… odróz· ni´c od 1. Bardziej uogólniajac: ¾ rd(x) = x (1 + "m )

2.3. Zaokraglenie i obciecie ¾ ¾ liczby DEFINICJA 8. Cyfra¾ znaczac ¾ a¾ warto´sci przybliz· onej liczby rzeczywistej nazywamy kaz·da¾ zachowana¾ cyfre¾ rozwiniecia tej liczby róz·na¾ ¾ dziesietnego ¾ od 0 oraz 0, je´sli jest ono zawarte miedzy cyframi znaczacymi lub znajduje ¾ ¾ sie¾ na zachowanej pozycji. Mówimy, z·e liczba przybliz·ona ma n poprawnych (dok÷adnych) cyfr znaczacych, jez·eli b÷ad tej liczby nie przewyz·sza ¾ bezwzgledny ¾ ¾ po÷owy jedno´sci pozycji, okre´slonej przez n-ta¾ cyfre¾ znaczac ¾ a, ¾ liczac ¾ od lewej. ¹ = 35:97 jej przybliz· enie x = 36:00 PRZYK×AD: Dla liczby dok÷adnej x posiada 4 cyfry znaczace, ale tylko 3 cyfry sa¾ poprawne, gdyz· ¢x = 0:03 < ¾ 0:05 = 12 ¢ 10¡1 (± x = 8: 3 ¢ 10¡4 ). 6

UWAGA: (i) Poczatkowe zera s÷uz· a jedynie do wskazania pozycji dziesiet¾ ¾ nych innych cyfr. Ko´ncowe zera sa¾ cyframi znaczacymi, poniewaz· wskazuja, ¾ ¾ z· e w liczbie przybliz· onej zachowano dana¾ pozycje. ¾ (ii) Liczba cyfr znaczacych daje bezpo´srednio pojecie ¾ ¾ o wielko´sci b÷edu ¾ wzgled¾ nego, liczba cyfr poprawnych - po´srednio o wielko´sci b÷edu ¾ bezwzglednego. ¾ REGU×A ZAOKRAGLANIA: ¾ Aby zaokragli´ nalez· y odrzuci´c wszystkie jej ¾ c liczbe¾ do n cyfr znaczacych, ¾ cyfry zapisane z prawej strony n-tej cyfry znaczacej. Przy tym je´sli odrzuca sie¾ ¾ co do modu÷u warto´s´c: (i) mniejsza¾ niz· 12 ¢ 10¡n , to n-ta¾ cyfre¾ pozostawia sie¾ bez zmian; (ii) wieksz ¾ a¾ niz· 12 ¢ 10¡n , to do n-tej cyfry dodaje sie¾ 1; sie¾ o 1, je´sli jest nieparzysta, a po(iii) równa¾ 12 ¢ 10¡n , to n-ta¾ cyfre¾ zwiesza ¾ zostawia sie¾ bez zmian, gdy jest parzysta (dla jednakowej czesto´ ujem¾ sci b÷edów ¾ nych i dodatnich). PRZYK×AD: Zaokraglanie do 4 cyfr znaczacych: ¾ ¾ liczba 3:1497 ¡3:1497 3:1435 3:1425

odrzucony fragment 0:7 ¢ 10¡3 0:7 ¢ 10¡3 0:5 ¢ 10¡3 0:5 ¢ 10¡3

zaokraglenie ¾ 3:150 ¡3:150 3:144 3:142

b÷ad ¾ bezwzgledny ¾ 0:3 ¢ 10¡3 0:3 ¢ 10¡3 0:5 ¢ 10¡3 0:5 ¢ 10¡3

UWAGA: (i) Wiekszo´ s´c komputerów, w których wykonuje sie¾ zaokraglenie, ¾ ¾ tylko zwieksza albo tylko zmniejsza liczbe¾ o 12 ¢ 10¡n w przypadku (iii), gdyz· ¾ jest to technicznie ÷atwiejsze. (ii) B÷ad zaokraglenia nie przewyz· sza po÷owy jedno´sci pozycji dziesiet¾ bezwzgledny ¾ ¾ ¾ nej, okre´slonej przez ostatnia¾ pozostawiona¾ cyfre¾ znaczac ¾ a, ¾ tzn. jx ¡ x ¹j ·

1 ¢ 10¡n . 2

2.4. Uwarunkowanie zadania, algorytmy i zbiez· no´s´c Dowolne zadanie obliczeniowe moz· na przedstawi´c jako pewne odwzorowanie © : Rn ! Rm postaci w = © (d) ; T

T

gdzie d = [d1 ; :::; dn ] jest wektorem danych, a w = [w1 ; :::; wm ] - wektorem wyników. Oczywi´scie w praktyce dysponujemy jedynie reprezentacjami maszynowymi danych rd(di ) dla i = 1; :::; n zle uwarunkowane, je´sli ma÷e DEFINICJA 9. Mówimy, z·e zadanie jest ´ wzgledne zmiany danych powoduja¾ odpowiednio duz·e wzgledne zmiany wyników. ¾ ¾ W przeciwnym razie, mówimy, z·e zadanie jest dobrze uwarunkowane. Wska´ znikiem uwarunkowania bedziemy nazywa´c pewna¾ wielko´s´c charak¾ teryzujac ¾ a¾ wzrost zmian wyniku w stosunku do zmian danych. PRZYK×AD: Klasycznym przyk÷adem zadania ´zle uwarunkowanego jest równanie P (x) ´ (x ¡ 1)(x ¡ 2):::(x ¡ 20) = 0; 7

posiadajace ¾ 20 pierwiastków rzeczywistych x = 1; 2; :::; 20. Je´sli zak÷ócimy np. zmieniwspó÷czynnik przy x19 jedynie o 10¡7 , to w konsekwencji rowiazania ¾ 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´sla, jak rozwiazanie tego zadania ¾ jest wraz· liwe na ma÷e zaburzenia danych, a wska´znik uwarunkowania jest miara¾ tej wraz· liwo´sci. Teoretyczna de…nicja wska´znika uwarunkowania jest niepraktyczna i zwykle i przyjmuje sie¾ go jako najmniejsza¾ z liczb · (d), dla których zachodzi ± w · · (d) ¢ ± d : PRZYK×AD: Rozwaz· my zadanie obliczania iloczynu skalarnego: © (u; v) =

n X

ui vi ;

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´ sci 2%¤ spowodowa÷y zaburzenie wyniku wielko´sci 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 powyz· szego moz· na wywnioskowa´c, z· e uwarunowanie zadania zalez· y od warto´sci danych. W ogólnej teorii metod numerycznych nalez· y zdecydowanie odróz· ni´c trzy nastepuj ¾ ace ¾ pojecia: ¾ 1. Zadanie obliczeniowe w = © (d); 2. Algorytm A (d) obliczenia wyniku zadania © czyli procedura, opisujaca ¾ sko´nczony ciag ¾ kroków, które nalez· y wykona´c w podanej kolejno´sci, aby znale´z´c rozwiazanie problemu lub przybliz· enie rozwiazania. ¾ ¾ 3. Numeryczna realizacja fl(A(d)) algorytmu A - polega na zastapieniu ¾ liczb wystepuj w A (d) ich reprezentacjami maszynowymi i wykonaniu op¾ acych ¾ 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 f l(A1(a; b)) = f l(a ¢ a ¡ b ¢ b) = fl [fl(a ¢ a) ¡ f l(b ¢ b)] ; f l(A2(a; b) = f l [(a + b) ¢ (a ¡ b)] = fl [fl(a + b) ¢ f l(a ¡ b)] : Mozna wykaza´c, z· e ¯ 2 ¯¶ µ ¯ a + b2 ¯ ¢ ¡ 2 2 ¯ ¯ "m ; f l(A1(a; b)) = a ¡ b (1 + ± 1 ) , gdzie j± 1 j · 1 + ¯ 2 a ¡ b2 ¯ ¢ ¡ f l(A2(a; b)) = a2 ¡ b2 (1 + ± 2 ) , gdzie j± 2 j · 3"m ; 8

co implikuje, z· e algorytm A1 ma gorsze w÷asno´sci numeryczne niz· algorytm A2. W przypadku, gdy kwadraty obu liczb sa¾ bliskie, moz· e doj´s´c do silnego wzrostu ± 2 jest niewraz· liwy na warto´sci ± 1 , podczas gdy b÷ad b÷edu ¾ wzgledny ¾ ¾ wzglednego ¾ danych a i b. Jeste´smy oczywi´scie 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 moz· liwe, jest stabilno´s´c. DEFINICJA 10. Mówimy, z·e algorytm jest stabilny, je´sli posiada nastepu¾ jac ¾ a¾ w÷asno´s´c: ma÷e b÷edy ¾ powsta÷e w pewnym kroku algorytmu nie sa¾ powiek¾ szane w innych krokach oraz nie powoduja¾ powaz·nego ograniczenia dokadno´sci wszystkich oblicze´ n. W przeciwnym razie, mówimy, z·e algorytm jest niestabilny. Innymi s÷owami: algorytm stabilny gwarantuje uzyskanie wyniku z b÷edem ¾ wzglednym tego samego rzedu spowodowany jedynie ¾ ¾ wielko´sci, co b÷ad ¾ wzgledny ¾ zaburzeniami danych i b÷edem reprezentacji maszynowej. ¾ Niektóre algorytmy sa¾ stabilne zawsze (bez wzgledu ¾ na dane wej´sciowe), za´s stabilno´s´c innych zalez· y od wyboru danych wej´sciowych. po wykonab÷edem zaokraglenia i En b÷edem DEFINICJA 11. Niech " bedzie ¾ ¾ ¾ ¾ niu n kroków algorytmu. Je´sli jEn j ¼ Cn", gdzie C jest pewna¾ sta÷a¾ niezalez·na¾ od n, to mówimy, z·e wzrost b÷edu ¾ jest liniowy. Je´sli jEn j ¼ kn ", dla pewnego k > 1, to wzrost b÷edu ¾ jest wyk÷adniczy. Liniowy wzrost b÷edu i gdy C oraz " sa¾ ma÷e, ¾ jest zwykle nie do unikniecia ¾ to wyniki sa¾ ogólnie akceptowalne. Wzrostu wyk÷adniczego powinno sie¾ unika´c, gdyz· prowadzi do nieakceptowalnych niedok÷adno´sci. W konsekwencji, algorytm, który charakteryzuje sie¾ liniowym wzrostem b÷edu, jest stabilny, za´s ago¾ rytm z wyk÷adniczym wzrostem jest niestabilny. Oczywi´scie, aby unikna´ moz· na uz· ywa´c wiek¾c efektów b÷edu ¾ zaokraglenia, ¾ ¾ szej precyzji oblicze´n (podwójnej lub rozszerzonej), o ile maszyna lub oprogramowanie oferuja¾ taka¾ moz· liwo´s´c. Nalez· y jednak pamieta´c, z· e im wyz· sza precyzja oblicze´n, tym bardziej sa¾ one czaso- i pamiecio-ch÷onne. ¾ Podsumowujac ¾ ta¾ cze´ ¾s´c rozwaz· a´n, moz· emy stwierdzi´c, z· e b÷ad ¾ jego nuemrycznej realizacji algorytmu zalez· y od 3 czynników: - uwarunkowania zadania, którego miara¾ jest wska´znik uwarunkowania ·, - stabilno´sci algorytmu, - stosowanej arytmetyki zmiennopozycyjnej, która jest charakteryzowana przez epsilon maszynowy "m .

9