Utrata cyfr znaczących

Z Wikipedii

Masz nowe wiadomości (różnica z poprzednią wersją).

Utrata cyfr znaczących

Jest zjawiskiem pojawiającym się w obliczeniach komputerowych, konsekwencją zapisu liczb rzeczywistych w komputerze. Występuje ona podczas odejmowania liczb, których różnica jest znaczenie mniejsza niż każda z tych liczb.

Rozważmy dwie takie, bliskie sobie, liczby: x i y

Są one dane w postaci $rd(z)=(+/-)m_t\cdot 2^c$

gdzie $m t$ jest mantysą - liczbą długości t taką, że $m\in (0,\frac{1}{2}>$ , a c cechą - dowolną liczbą całkowitą

 rd(x) = +/-  0 . 1

 rd(y) = +/-  0 . 1
         --------------------------------------------------
       -      0 . 0 0 0 0 0 0 ...

W wyniku odejmowania bliskich liczb powstaje liczba zawierająca na pierwszych n-i pozycjach zera, na pozostałych (przynajmniej jedną)jedynki - musi ona być znormalizowana, tj. przedstawiona w postaci:

$rd(x-y)=(+/-)m_t\cdot 2^c$

gdzie $m\in (0,\frac{1}{2}>$

Aby otrzymać mantysę spełniającą ten warunek, należy "obciąć" początkowe zera w liczbie x-y (poprzez pomożenie przez $2 n - i$ ) - wtedy jednak "zabraknie liczb z tyłu" - tych kilka ostanich niezerowych cyfr x-y przesunie się na pierwszą pozycję, i jeżeli i<t komputer nie będzie wiedział czym zapełnić pozostałe miejsca w mantysie (właściwe zostały wcześniej odrzucone, przez zaokrąglenie x i y!). Co gorsze, przyjęcie, że te "brakujące pozycje" zapełnimy np.zerami, jest tak samo dobre jak zapełnienie ich losowymi liczbami - w obu wypadkach będą to "śmiecie" nie mające wiele wspolnego z rzeczywistym (lub choćby do niego zbliżonym) wynikiem...

x = 0,

Mamy bład względny różnicy x i y:

$|d(z)|<=|d(x)| + |d(y)| => \frac{|d(x)|+|d(y)|}{|x-y|}$

Gdy róznica |x-y| dąży do zera, błąd względny z rośnie nieograniczenie.

Jako przykład zadania źle uwarunkowanego niech posłuży nam prosta funcja:

$f(x)=\sqrt[2]{x+9}-3$

Prosta funcja której wartości każdy potrafi policzyć... Nie każdy! Komputer nie potrafi! Przynajmniej w pewnej sytuacji: zauważ, że dla x w pobliżu zera wartość pod pierwiastkiem jest bardzo bliska 3 - może wystąpić (i występuje!) utrata cyfr znaczących.

Prostym sposobem na poradzenie sobie z tym problemem jest przekształcenie wzoru naszej funkcji:

$f(x)= (\sqrt[2]{x+9}-3)*\frac{\sqrt[2]{x+9}+3}{\sqrt[2]{x+9}+3} = \frac{x+9-9}{\sqrt[2]{x+9}+3}=\frac{x}{\sqrt[2]{x+9}+3}$

Mamy więc wzór algebraicznie równoważny, a nie zawierający operacji odejmowania - teraz nawet dla x bliskich 3 nie stracimy dokładności wyniku!

Innym przykładem na to, że nawet najprostsze algorytmy mogą być źle uwarunkowane jest "szkolny" algorytm obliczania pierwiastków równania kwadratowego

$x_1 = \frac{-b-\sqrt[2]{b^2 - 4ac}}{2a}$ $x_2 = \frac{-b+\sqrt[2]{b^2 - 4ac}}{2a}$

W sposobie obliczenia jednego z pierwiastków jest odejmowanie - jeżeli ktoś "złośliwie" dobierze nam współczynniki wielomianu, wartość $- b$ i $\sqrt[2]{b^2 - 4ac}$ mogą być dość bliskie - nastąpi utrata cyfr znaczących!

Z pomocą mogą nam przyjść Wzory Viète'a - obliczymy dobrze uwarunkowany pierwiastek "wprost", drugi otrzymamy z tychże wzorów!

Źródło: "http://pl.wikipedia.org../../../u/t/r/Utrata_cyfr_znacz%C4%85cych.html"

Kategoria: Algorytmy

Utrata cyfr znaczących

Z Wikipedii

Views

nawigacja

techniczne

zmiany

Szukaj