P4180004
2.3.2. NUMERYCZNA POPRAWNOŚĆ ALGORYTMU
Za numerycznie poprawne uważa się algorytmy, które spełniają pewne realistyczne wymagania co do wartości wnoszonych przez nie błędów. Nie chodzi na ogół o to, aby utrzymać te błędy na poziomie eps czy jakiejś niewielkiej krotności eps , ale o to, aby te błędy pozostawały w praktycznie akceptowalnym stosunku do błędów wnoszonych przez dane. Dla użytkownika wyników obliczeń na ogół obojętne jest bowiem źródło ich błędów, liczy się tylko ich sumaryczna wartość. Za realistyczne należy zatem uznać wymaganie, aby błędy wnoszone przez algorytm były małe dla tych danych, dla których małe są błędy wnoszone przez dane. Wymaganie to leży u podstaw następującego określenia numerycznej poprawności: algorytm jest numerycznie poprawny, jeżeli dla dokładnych danych dostarcza rozwiązań będących dokładnymi rozwiązaniami zadania dla „nieco” zaburzonych danych [J1 ].
Przykład 2.8. Algorytm obliczania wartości wyrażenia y - x+ x\ jest numerycznie poprawny, ponieważ:
y - [*? 0+rii)+*2 (i+ ^2)] 0+n.) a zgodnie z regułą (2. lOa):
+t1i+tU + *22(1 + t1i+tO] zaś zgodnie z regułą (2. lOb):
|
/ i | v |
2 |
/ i j y2 | |
|
y ~ |
.T+2n' + 2,1*J. |
+ |
H1 + 2Th + 2T,*J. |
Z tego ostatniego wyrażenia wynika, że skutek błędów zaokrągleń wyników podnoszenia do kwadratu i sumowania jest taki sam jak skutek zaburzenia danych na poziomie eps.
Metoda badania numerycznej poprawności algorytmu, zastosowana w przykładzie 2.8, nie zawsze prowadzi do rozstrzygnięcia. Jeżeli nie udaje się wyznaczyć zastępczych zaburzeń danych, których skutek byłby równoważny wpływowi na wynik błędów zaokrągleń, to nie można stąd wyciągać wniosku, że algorytm jest numerycznie niepoprawny. Można jedynie domniemywać, że tak jest i podjąć próbę potwierdzenia tej hipotezy na drodze poszukiwania takiego przykładu danych w zbiorze D, dla którego błąd spowodowany zaokrągleniami rośnie nie-ograniczenie, chociaż błąd pochodzący od danych jest ograniczony.
Wyszukiwarka
Podobne podstrony:
SNC03613 Gatunki śniegu W meteorologii za pokrywę śnieżną uważa się śnieg, pokrywający co najmniej p
IMG52 (5) I CEBULI METODA 2Wy/CŁA Za początek kiełkowania uważa się moment ułożenia nasion nś podło
kat C 80 158 158 PODRĘCZNIK KATEGORIA C Za oś pojedynczą uważa się oś oddaloną od osi sąsiedniej o w
Polityka Rachunkowości c. Za koszty proste uważa się ogół poniesionych w danym okresie
Wady drewna Za wady drewna uważa się takie cechy wrodzone lub nabyte, które pomniejszają jego przyda
Za małego przedsiębiorcę uważa się przedsiębiorcę, któiy w co najmniej jednym z dwóch ostatnich lat
Za spedycję właściwą uważa się wykonywanie następujących czynności: -
Za odrębny obiekt uważa się w zasadzie każdy samodzielny obiekt inżynierii lądowej lub wodnej wraz z
5. porty - za część wybrzeża uważa się wysunięte najdalej w morze stałe
Ĺ‚yĹĽwiarstwo jpeg - ml. - Za ojczyznę łyżwiarstwa uważa się Holandię. Ma wiolu bardzo starych obraz
16. W statystyce międzynarodowej za granicę ubóstwa uważa się sytuację, gdy
powietrzu. Za przodka ptaków uważa się praptaka - archeopteryksa. Z końcem kredy, z przyczyn nie wyj
§21 II. NAGRODY ZA OSIĄGNIĘCIA DYDAKTYCZNE Za osiągnięcia dydaktyczne uważa się (Regulamin
III.NAGRODY ZA OSIĄGNIĘCIA ORGANIZACYJNE §27 Za osiągnięcia organizacyjne uważa się (Regulamin
więcej podobnych podstron