Podręcznik Grafika komputerowa i wizualizacja
Rozdział 4. PRZEKSZTAŁCENIA GEOMETRYCZNE
4.7. Problem dokładności obliczeń w przekształceniach geometrycznych
Problem dokładności obliczeń przy wykorzystaniu komputerów jest znany od kiedy istnieją komputery. Wiadomo, że liczby w komputerze są reprezentowane przez skończony ciąg cyfr. W przypadku liczb całkowitych stosowana jest reprezentacja stałopozycyjna i i jeśli rozpatrzymy arytmetykę binarną, to liczbie takiej odpowiada rozwinięcie dwójkowe o określonej długości słowa. Liczby rzeczywiste reprezentowane są zmiennopozycyjnie w postaci cechy i mantysy. Stosowanie określonej długości słowa do reprezentacji mantysy powoduje powstanie dokładności danej arytmetyki. Oznacza to, że reprezentacja liczb rzeczywistych obarczona jest zawsze pewnym błędem wynikającym z tej arytmetyki. Przeprowadzanie operacji graficznych wymaga często wielokrotnych obliczeń. Błędy reprezentacji (dokładność arytmetyki) mogą w widoczny sposób wpływać na efekt (graficzny !) obliczeń. Stosowane algorytmy powinny być tak realizowane, aby, o ile jest to możliwe, minimalizować te błędy.
Rys.4.29. Rysunek zegara.
Rozpatrzmy przykład zegara, dla którego należy wyznaczyć położenie wskazówek – rysunek 4.29. Zadanie można sformułować w następujący sposób. Jeśli wskazówka minutowa co minutę obraca się o kąt da , to należy wyznaczyć kąty ai kolejnych położeń tej wskazówki.
Najprostszym rozwiązaniem jest algorytm iteracyjny powiększający w każdym kroku bieżący kąt położenia o zadany przyrost. Niestety takie rozwiązanie prowadzi do powstania widocznych na tarczy zegara błędów już po kilkudziesięciu godzinach.
Algorytm naiwny.
i = 0;
a0 = 0;
while ()
{
i = i+1;
ai = ai-1+da;
}
Rys. 4.30. Zegar wskazujący „dokładnie” godzinę drugą po kilkudziesięciu godzinach pracy.
Jeśli przeanalizujemy ten najprostszy algorytm, to okaże się, że wraz z powiększaniem wartości kąta dodajemy błędy. Każda operacja arytmetyczna wykonywana przez komputer jest obarczona błędem wynikającym z reprezentacji liczb w postaci skończonej liczby bitów.
Jeśli repr (x) oznacza reprezentację liczby x , natomiast e błąd reprezentacji to:
repr (x) = x .(1+e ) gdzie |e | < d , d Î (10 -16,10 -7)
repr (x+y) = (x+y ).(1+e )
Jeśli wykonywane są operacje w sposób iteracyjny i jednocześnie bieżąca wartość pewnej wielkości jest obarczona błędem z poprzedniej wartości tej samej wielkości, to błąd całej operacji nie jest tylko problemem bieżącym, ale odzwierciedla całą dotychczasową historię obliczeń. A więc błąd się nakłada wraz z postępowaniem obliczeń. Po wielu powtórzeniach może osiągnąć znaczącą wartość. Kumulowanie się błędu w algorytmie naiwnym dla kolejnych iteracji można przedstawić jako:
i=1 : repr (a1 ) = (0+da ) .(1+e1 )
i=2 : repr (a2 ) = ((0+da ) .(1+e1 ) +da ) .(1+e2 )
i=3 : repr (a3 ) = (((0+da ) .(1+e1 ) +da ) .(1+e2 ) +da ) .(1+e3 )
. . .
Zadanie z zegarem może zostać rozwiązane tak,. aby nie doprowadzić do narastania błędu.
Algorytm poprawiony.
i = 0;
a0 = 0;
da = 2*p/60;
while ()
{
i = i+1;
ai = i*da;
}
Realizując algorytmy graficzne należy zawsze zwracać uwagę na dokładność obliczeń numerycznych. Aby błąd zaokrągleń nie wpłynął na efekt obliczeń i nie zniweczył naszej pracy, psując efekt końcowy.