Wykład 2-Teoria błędów

Metody Numeryczne, Matematyka Finansowa, rok II, st.I

semestr letni 2012/2013

Wykład 1: Wiadomości wstępne. Teoria błędów.

Metody numeryczne są działem matematyki stosowanej. Dotyczą one tworzenia, badania i analizy algorytmów, których celem jest otrzymanie rozwiązań różnorodnych zadań matematycznych, np. z dziedziny algebry liniowej, rachunku całkowego, równań różniczkowych zwyczajnych i cząstkowych, itd.

Metody numeryczne:

• są szybkim i efektywnym narzędziem rozwiązywania problemów,

• są często jedyną alternatywą dla nieistniejących rozwiązań analitycznych.

Jasne jest, że obecnie algorytmy są przeznaczone do stosowania w programach komputerowych i istnieją liczne efektywne programy i biblioteki.

Metody numeryczne mają różne wcielenia: rozwiązywanie zadań matematycznych na kom-puterach to obliczenia naukowe, w których kładzie się nacisk na zastosowanie metod numerycznych; natomiast tworzenie odpowiednich algorytmów i badanie ich własności, optymalności to analiza numeryczna. Oczywiście granice podziału nie są ostre.

Algorytm numeryczny to skończona sekwencja operacji przekształcających dane wejściowe w wyjściowe, przy czym operacja jest rozumiana jako funkcja arytmetyczna lub logiczna albo referencja do innych istniejących algorytmów.

Często algorytm buduje się na podstawie dowodu matematycznego - oczywiście nie chodzi tu o dowód przez zaprzeczenie. Nie każdy jednak konstruktywny dowód prowadzi do efektywnego algorytmu. Może być on bezużyteczny, jeśli okaże się kosztowny, tzn. zmuszający do długotrwa-

łych obliczeń.

W cyklu wykładów zostaną przedstawione wybrane metody numeryczne.

Polecana literatura do wykładu:

1. G.Dahlquist, A.Bjorck - Matody numeryczne, WNT, Warszawa 1983

2. B.D.Demidowicz, I.A.Maron - Metody numeryczne, cz.1, PWN, Warszawa 1965

3. B.D.Demidowicz, I.A.Maron, E.J.Szuwałowa - Metody numeryczne, cz.2, PWN, Warszawa 1965

4. M.Dryja, J. i M.Jankowscy - Przegląd metod i algorytmów numerycznych, t.2, WNT, Warszawa 1988

5. Z.Fortuna, B.Macukow, J.Wąsowski - Metody numeryczne, WNT, Warszawa 1993

6. J. i M.Jankowscy - Przegląd metod i algorytmów numerycznych, t.1, WNT, Warszawa 1988

7. D.Kincaid, W.Cheney - Analiza numeryczna, WNT, Warszawa 2006

8. J.Stoer - Wstęp do metod numerycznych, t.1, PWN, Warszawa 1990

9. J.Stoer, R.Bulirsh - Wstęp do metod numerycznych, t.2, PWN, Warszawa 1990

Teoria błędów

Definicja 1 Liczbą przybliżoną a nazywa się liczbę różniącą się od dokładnej liczby A i zastępującą ją w obliczeniach. W przypadku, gdy a < A liczbę a nazywa się wartością przybliżoną z niedomiarem liczby A. Jeśli a > A, to liczbę a nazywa się wartością przybliżoną z nadmiarem.

Definicja 2 Różnicę pomiędzy liczbą dokładną A i jej przybliżeniem

∆ a = A − a

nazywa się błędem liczby a .

Często znak błędu jest nieznany. Wówczas stosuje się pojęcie błędu bezwzględnego liczby przybliżonej.

Definicja 3 Błędem bezwzględnym ∆ liczby przybliżonej a nazywa się wartość bezwzględną różnicy pomiędzy liczbą dokładną A i liczbą przybliżoną :

∆ = |A − a|.

W praktyce zdarza się najczęściej, że liczba dokładna A nie jest znana. Dlatego zamiast nie-znanego błędu bezwzględnego ∆ wprowadza się jego oszacowanie z góry, tzw. kres górny błędu bezwzględnego.

Definicja 4 Kresem górnym błędu bezwzględnego liczby przybliżonej nazywa się każdą liczbę nie mniejszą od błędu bezwzględnego tej liczby przybliżonej.

Jeśli zatem przez ∆ a oznaczymy kres górny błędu bezwzględnego liczby przybliżonej a przybli-

żającej liczbę dokładną A, to

∆ = |A − a| ¬ ∆ a.

(1)

Zatem

a − ∆ a ¬ A ¬ a + ∆ a.

Często używa się skróconego zapisu A = a ± ∆ a.

Przykład 1 Przybliżamy liczbę π liczbą a = 3 , 14. Ponieważ zachodzi nierówność 3 , 14 < π < 3 , 15, więc |a − π| < 0 , 01, czyli możemy przyjąć ∆ a = 0 , 01.

Jeśli przybliżamy liczbę π liczbą a = 3 , 142, to ponieważ 3 , 14 < π < 3 , 142, więc możemy otrzymać lepsze oszacowanie ∆ a = 0 , 002.

Zauważmy, że wprowadzone pojęcie kresu górnego błędu bezwzględnego liczby przybliżonej obejmuje szeroką klasę liczb. Mianowicie, przez kres górny błędu bezwzględnego liczby a rozumie się dowolny element zbioru nieskończonego liczb nieujemnych ∆ a spełniających nierówność (1). Stąd wynika, że każda liczba większa od kresu górnego błędu bezwzględnego danej liczby przybliżonej również może być nazwana kresem górnym błędu bezwzględnego tej liczby przybliżonej. W praktyce za ∆ a wybiera się możliwie najmniejszą w danych warunkach liczbę spełniającą nierówność (1).

W zapisie liczby przybliżonej, otrzymanej w wyniku pomiaru, zazwyczaj podaje się kres górny jej błędu bezwzględnego. Na przykład: l = 100 cm ± 0 , 5 cm, czyli ∆ l = 0 , 5 cm i dokładna wartość l zawarta jest w granicach 100 − 0 , 5 ¬ l ¬ 100 + 0 , 5 (cm).

Błąd bezwzględny (albo jego kres górny) nie charakteryzuje w pełni dokładności pomiarów czy obliczeń. Jeśli na przykład przy pomiarze długości dwóch wielkości otrzymano wyniki l 1 = 100 , 8 cm ± 0 , 1 cm i l 2 = 5 , 2 cm ± 0 , 1 cm, to niezależnie od tego, że kres górny błędu bezwzględnego jest dla obu długości jednakowy, pomiar pierwszy jest dokładniejszy od drugiego.

Definicja 5 Błędem względnym δ liczby przybliżonej a nazywa się stosunek błędu bezwzględnego ∆ tej liczby do wartości bezwzględnej liczby dokładnej (A 6= 0 ), tj.

∆

δ =

(2)

|A|

Błąd względny często jest wyrażany w %.

Podobnie jak dla błędu bezwzględnego wprowadzamy pojęcie kresu górnego błędu względnego:

Definicja 6 Kresem górnym błędu względnego δa liczby przybliżonej a nazywa się każdą liczbę nie mniejszą od błędu względnego liczby a:

∆

δ =

¬ δ

|A|

(3)

Stąd ∆ ¬ |A|δa i można przyjąć za kres górny błędu bezwzględnego ∆ a = |A|δa. Ponieważ w praktyce jest A ≈ a, zatem przyjmujemy ∆ a = |a|δa.

Podstawowe źródła błędów

1. Niekiedy rozwiązanie zagadnienia postawionego dokładnie jest trudne albo prawie nie-możliwe. Wtedy zagadnienie to zastępuje się bliskim co do wyników zagadnieniem przybliżonym. Powstaje w ten sposób błąd, który można nazwać błędem metody.

2. Często funkcje, które występują we wzorach matematycznych są dane w postaci ciągów nieskończonych lub szeregów. Wiele równań matematycznych można rozwiązać jedynie przez opis procesów nieskończonych, których granice są poszukiwanymi rozwiązaniami.

Jednak na ogół powstaje konieczność zakończenia obliczeń na pewnym wyrazie ciągu.

Oczywiście przerwanie obliczeń powoduje powstanie błędu zwanego błędem obcięcia.

Przykład: R 1 ex 2 dx

1 + x 2 + x 4 + x 6 + x 8 dx.

≈ R 10

3. We wzorach matematycznych mogą występować parametry liczbowe, których wartości daje się określić jedynie w przybliżeniu. Jest to tzw. błąd początkowy.

4. Błąd zaokrąglenia: w obliczeniach może być wykorzystana jedynie skończona ilość cyfr.

5. Błędy działań arytmetycznych: przy wykonywaniu działań na liczbach przybliżonych przenosimy do wyników błędy danych początkowych.

Błąd, który powstaje w obliczeniach w wyniku skumulowania wszystkich rodzajów błędów, nazywamy błędem numerycznym.

Cyfry znaczące

Każdą liczbę można przedstawić w postaci skończonego lub nieskończonego ułamka dziesiętnego. W praktyce mamy przeważnie do czynienia z liczbami przybliżonymi. Są to skończone ułamki dziesiętne:

a = α

m 10 m + αm 110 m−

+ . . . + α

−

m−n+110 m−n+1 ,

αm 6= 0 .

Definicja 7 Cyfrą znaczącą liczby przybliżonej nazywa się każdą różną od zera cyfrę rozwi-nięcia dziesiętnego tej liczby oraz zero, jeśli jest ono zawarte pomiędzy cyframi znaczącymi lub znajduje się na zachowanej pozycji dziesiętnej. Wszystkie pozostałe zera wchodzące w skład liczby przybliżonej służą wyznaczaniu jej pozycji dziesiętnej i nie są zaliczane do cyfr znaczących.

Przykład 2 Liczba 0,002080: trzy pierwsze (od lewej) zera nie są cyframi znaczącymi, ponieważ służą jedynie do wskazania pozycji dziesiętnych innych cyfr. Pozostałe dwa zera są cyframi znaczącymi - pierwsze dlatego,że znajduje się pomiędzy cyframi znaczącymi 2 i 8, a drugie -

ponieważ wskazuje, że w liczbie przybliżonej zachowano pozycję dziesiętną 10 6

− . Gdyby ostat-

nie zero nie było cyfrą znaczącą, to powinno się go nie zapisywać, tzn.: 0,00208. Ta liczba ma trzy cyfry znaczące.

Definicja 8 Mówimy, że liczba przybliżona a ( a = α

m 10 m + αm 110 m− + . . . + α

−

m−n+110 m−n+1)

ma n dokładnych pierwszych cyfr znaczących (licząc od prawej do lewej), jeżeli 1

∆ = |A − a| ¬

· 10 m−n+1 .

(4)

Zaokrąglanie liczb

Aby zaokrąglić liczbę do n cyfr znaczących należy obciąć wszystkie jej cyfry zapisane z prawej strony n-tej cyfry znaczącej lub, jeśli zachodzi potrzeba zachowania tych pozycji dziesiętnych, należy zastąpić je zerami. Przy tym:

1. Jeśli pierwsza z odrzuconych cyfr jest mniejsza od 5, to pozostałych cyfr dziesiętnych liczby nie zmienia się.

2. Jeśli pierwsza z odrzuconych cyfr jest większa od 5, to do ostatniej pozostawionej cyfry dodaje się 1.

3. Jeśli pierwsza z odrzuconych cyfr jest równa 5

(a) a wśród odrzuconych cyfr są cyfry różne od zera, to ostatnią pozostawioną cyfrę zwiększa się o 1,

(b) a pozostałe odrzucone cyfry są zerami, to do ostatniej pozostawionej cyfry dodaje się 1, gdy jest ona nieparzysta, a pozostawia się ją bez zmian, gdy jest ona parzysta.

Jest to reguła cyfry parzystej.

Uwaga 1 Przy zastosowaniu podanych reguł błąd zaokrąglenia nie przewyższa połowy jedności pozycji dziesiętnej, określonej przez ostatnią pozostawioną cyfrę znaczącą.

√

Przykład 3 Zaokrąglamy liczbę

3 = 1 , 732050807568877 ...

• do jednej cyfry znaczącej: 2

• do trzech cyfr znaczących: 1,73

• do pięciu cyfr znaczących: 1,7321

z błędem bezwzględnym mniejszym odpowiednio od: 1 · 100; 1 · 10 2

− ; 1 · 10 − .

Ogólna postać błędu

Niech będzie dana funkcja różniczkowalna u = f ( x 1 , . . . , xn). Oznaczymy przez ∆ xi, i = 1 , . . . , n błędy bezwzględne argumentów tej funkcji. Wtedy błąd bezwzględny funkcji można zapisać w postaci:

∆ u = |f( x 1 + ∆ x 1 , . . . , xn + ∆ xn) − f( x 1 , . . . , xn) |.

Zazwyczaj w praktyce ∆ xi są wielkościami małymi, których kwadratów i wyższych potęg można nie brać pod uwagę. Można zatem przyjąć

∂f

∆ u ≈ |df( x

1 , . . . , xn) | =

∆ x ¬

∆ x

∂x

i=1

czyli

∂f

∆ u ¬ X

∆ x

∂x

(5)

i=1

Oznaczając przez ∆ x , i = 1 , . . . , n kresy górne błędów bezwzględnych argumentów x i

i, a przez

∆ u - kres górny błędu bezwzględnego funkcji u, otrzymujemy

∂f

∆

u =

∆ .

(6)

∂x

i=1

Dzieląc obie strony nierówności (5) przez |u| otrzymujemy oszacowanie błędu względnego funkcji u:

∂f

n ∂

δ ¬ X ∂xi

∆ xi =

ln f ( x 1 , . . . , x

∆ x

∂x

i=1

Stąd za kres górny błędu względnego funkcji u można przyjąć wielkość n

∂

u =

ln u ∆ .

(7)

∂x

i=1

Odejmowanie bliskich wielkości

Rozpatrzmy różnicę dwóch liczb przybliżonych x 1, x 2:

u = x 1 − x 2 .

Wtedy

∆ u = ∆ x + ∆

x 2

oraz

∂

∆

+ ∆

x 1

x 2

u =

ln ( x 1 − x 2) ∆ +

ln ( x 1 − x 2) ∆ =

∆ +

∆

∂x

x 1

∂x

x 2

x 1

x 2

|x 1 − x 2 |

(8)

Zauważmy, że jeśli liczby przybliżone x 1 i x 2 różnią się nieznacznie od siebie, to ich różnica jest wielkością małą. Ze wzoru (8) wynika, że kres górny błędu względnego różnicy może być znaczny nawet wtedy, gdy błędy względne odjemnej i odjemnika są małe. W efekcie możemy utracić nawet wszystkie znaczące cyfry wyniku.

Zapobieganie problemom

√

Przykład 4 Jak należy obliczać dla małych x wartości funkcji f ( x) =

x 2 + 1 − 1? Trzeba

przekształcić wzór funkcji tak, aby uniknąć niebezpiecznego odejmowania, tzn.

√

x 2 + 1 + 1

x 2

f ( x) = ( x 2 + 1 − 1) · √

= √

x 2 + 1 + 1

Uwaga 2 Co robić jeśli jednak istnieje konieczność odjęcia dwóch bliskich liczb i nie można tego uniknąć? Należy obie liczby wziąć z wystarczającą ilością zapasowych cyfr dokładnych.

Jeśli na przykład wiadomo, że przy odejmowaniu liczb x 1 i x 2 ich ostatnie m cyfr znaczących przepadnie, to należy wziąć liczby x 1 i x 2 z n + m dokładnymi cyframi znaczącymi.