MetNum.pdf

(3154 KB) Pobierz
Recenzja
AKADEMIA GÓRNICZO-HUTNICZA im. St. Staszica w Krakowie
Wydział Elektrotechniki, Automatyki, Informatyki i Elektroniki
Katedra Automatyki, Laboratorium Informatyki w Zarządzaniu
dr Adrian Horzyk - adiunkt
30-059 Kraków, Al. Mickiewicza 30
http://home.agh.edu.pl/~horzyk
paw. H6/325, C3/214
tel.: 012-617-4319, 3924
e-mail: horzyk@agh.edu.pl
Metody numeryczne
Literatura:
1. Z. Fortuna, B. Macukow, J. Wąsowski, Metody numeryczne , WNT, Warszawa, 1993.
2. J. i M. Jankowscy, Przegląd metod i algorytmów numerycznych , WNT, Warszawa, 1988.
3. A. Kiełbasiński, H. Schwetlick, Numeryczna algebra liniowa , WNT, Warszawa 1992.
1. Numeryczna reprezentacja liczb w maszynie cyfrowej
W maszynie cyfrowej liczby są reprezentowane przez skończoną liczbę cyfr ich rozwinięć pozycyjnych.
Najczęściej stosowaną podstawą tych rozwinięć jest 2 (mówimy wtedy o tzw. arytmetyce/reprezentacji
dwójkowej/binarnej ).
Przedstawienie liczby zależy od jej typu:
a) liczby całkowite – są przedstawiane w sposób stałopozycyjny
b) liczby rzeczywiste – są przedstawiane w sposób zmiennopozycyjny
Reprezentacja stałopozycyjna
Dowolną liczbę całkowitą l możemy przedstawić w postaci rozwinięcia dwójkowego:
l
= =
n
e
2
i
,
(
e
≠
0
dla
l
≠
0
,
i
n
i
0
gdzie s jest znakiem liczby l (tzn. s = +1 lub -1), a e i = 0 lub 1 są jej cyframi dwójkowymi.
W maszynie cyfrowej na reprezentację liczby przeznacza się słowo o skończonej długości np. d +1 bitów
(tj. cyfr dwójkowych). Jeśli tylko n < d , to liczba l jest reprezentowana w rozpatrywanej metryce
i przedstawiana zazwyczaj w postaci:
0
0
e
e
znak
d liczb dwójkowych
W ten sposób mogą być reprezentowane dokładnie liczby całkowite l z przedziału [-2 d +1, 2 d -1]. Dla
współczesnych maszyn cyfrowych , co umożliwia dokładną reprezentację nawet 19 cyfrowych
liczb całkowitych z zakresu [-9 223 372 036 854 775 808, 9 223 372 036 854 775 807]. Przy założeniu,
że argumenty i wynik są reprezentowalne, dodawanie, odejmowanie i mnożenie liczb całkowitych jest
wykonywane dokładnie!
d
∈
( 63
,
)
Reprezentacja zmiennopozycyjna
Dowolną liczbę rzeczywistą
x
≠
0
możemy przedstawić w postaci:
= ,
gdzie s jest znakiem liczby x (tzn. s = +1 lub -1), c jest liczbą całkowitą zwaną cechą , m jest liczbą
rzeczywistą z przedziału [½, 1] nazywana mantysą . Cechę c zapisuje się w sposób stałopozycyjny na d-t
bitach słowa maszyny cyfrowej, pozostałych t bitów słowa przeznacza się na reprezentację mantysy m ,
lecz zamiast na ogół nieskończonego rozwinięcia mantysy
s
⋅
m
⋅
2
c
1
s
7
x
79615144.018.png
AKADEMIA GÓRNICZO-HUTNICZA im. St. Staszica w Krakowie
Wydział Elektrotechniki, Automatyki, Informatyki i Elektroniki
Katedra Automatyki, Laboratorium Informatyki w Zarządzaniu
dr Adrian Horzyk - adiunkt
30-059 Kraków, Al. Mickiewicza 30
http://home.agh.edu.pl/~horzyk
paw. H6/325, C3/214
tel.: 012-617-4319, 3924
e-mail: horzyk@agh.edu.pl
∑
∞
m
=
e
⋅
2
−
i
(
e
=
1
e
=
0
lub
1
dla
i
>
1
−
i
−
1
−
i
i
=
1
zapamiętywanych jest tylko jej t początkowych cyfr dwójkowych odpowiednio zaokrąglonych (do t cyfr):
= ∑
t
m
e
⋅
2
−
i
+
e
⋅
2
−
t
,
( )
t
−
i
−
t
+
1
i
=
1
a wtedy
m
−
m
≤
1
⋅
2
− =
t
2
−
( )
t
+
1
.
2
Liczba rzeczywista x jest reprezentowana trójką ( s, c, m t ) zapamiętywaną słowem w postaci :
e
e
e
e
e
e
znak znak cechy
d-t bitów cechy
t bitów mantysy
Zero ( x = 0) jest zazwyczaj reprezentowane słowem o wszystkich bitach zerowych.
Reprezentację zmiennopozycyjną liczby x będziemy oznaczali przez rd(x) : ( )
rd
x
=
s
⋅
m
⋅
2
c
.
Błąd bezwzględny reprezentacji jest określony jako: ( ) x
~
=
rd −
x
.
Względny błąd reprezentacji ε wyznaczymy (dla
x
≠
0
) na skutek obcięcia i zaokrąglenia mantysy:
()
rd
x
− −
x
2
t
⇔
rd
() ( ε
x
=
x
⋅
1
+
gdzie
≤ ε .
−
t
x
.
Liczba cyfr mantysy decyduje o dokładności zmiennopozycyjnego przedstawiania liczb, a liczba cyfr
cechy określa zakres reprezentowalnych liczb, co oznacza
max
≤ ε . Dla współczesnych maszyn cyfrowych ( )
−
t
2
− ∈
10
−
19 10
,
−
6
1
⋅
2
c
min
≤
x <
2
c
, gdzie
c
=
−
2
d
− t
+
1
,
c
=
2
d
− t
−
1
2
min
max
Liczby, których cecha są reprezentowane zerem, co może powodować utratę dokładności
obliczeń, albowiem względny błąd reprezentacji jest równy 100%. Sytuację taką nazywamy
niedomiarem . Zaś sytuację pojawienia się liczby, której cecha , nazywamy nadmiarem
i konieczne jest przerwanie obliczeń. Obecnie zakres reprezentowanych liczb rzeczywistych jest tak duży
(
c <
c
min
c >
c
max
x ), że problem niedomiaru lub nadmiaru pojawia się bardzo rzadko w praktyce
obliczeniowej. W przypadku jego wystąpienia wystarcza często prosta modyfikacja algorytmu:
Przykład:
Obliczamy z liczby zespolonej
.
⋅
10
−
4932
≤
≤
1
.
⋅
10
4932
z
=
a
+
bi
≠
,0 −
i
=
1
:
klasycznym algorytmem:
z +
=
2
b
2
⎧
b
2
⎪
⎨
a
1
+
gdy
a
≥
b
a
2
przekształconym algorytmem:
z
=
a
2
⎪
⎩
b
1
+
gdy
a
<
b
⎪
b
2
2
t
Liczby rzeczywiste nie są na ogół reprezentowane dokładnie, ale w sposób przybliżony z błędem
względnym
1
79615144.019.png 79615144.020.png 79615144.021.png 79615144.001.png 79615144.002.png 79615144.003.png 79615144.004.png 79615144.005.png 79615144.006.png 79615144.007.png
AKADEMIA GÓRNICZO-HUTNICZA im. St. Staszica w Krakowie
Wydział Elektrotechniki, Automatyki, Informatyki i Elektroniki
Katedra Automatyki, Laboratorium Informatyki w Zarządzaniu
dr Adrian Horzyk - adiunkt
30-059 Kraków, Al. Mickiewicza 30
http://home.agh.edu.pl/~horzyk
paw. H6/325, C3/214
tel.: 012-617-4319, 3924
e-mail: horzyk@agh.edu.pl
W klasycznym algorytmie wystąpi nadmiar (niedomiar), jeśli a lub b są co do modułu większe od
2 c
max
2
1 c
(mniejsze od
⋅ ), zaś przekształcony algorytm pozwala na obliczenie z dla dowolnych a i b
2
min
2
2
z zakresu reprezentowanych liczb.
2. Błędy obliczeń
Przy obliczeniach wykonywanych na maszynach cyfrowych występują cztery podstawowe rodzaje
błędów:
a) błędy wejściowych
b) błędy reprezentacji
c) błędy obcięcia
d) błędy zaokrągleń
Błędy danych wejściowych występują wówczas, gdy dane liczbowe wprowadzane do pamięci lub
rejestrów maszyny cyfrowej odbiegają od dokładnych ich wartości. Błędy takie pojawiają się np. wtedy,
gdy dane wejściowe są wynikiem pomiarów wielkości fizycznych mierzonych z pewnymi błędami
pomiaru.
Błędy reprezentacji występują wówczas, gdy następuje konieczność reprezentacji liczby w maszynie
z wykorzystaniem skończonej długości słów binarnych (nieuniknione jest wtedy zaokrąglanie).
Zaokrąglanie występuje w przypadku reprezentacji wszystkich liczb niewymiernych (tj. o nieskończonym
rozwinięciu dwójkowym) takich, jak 2 , π, e itp.
Błędy obcięcia powstają podczas obliczeń na skutek zmniejszania liczby działań, np. podczas obliczania
= ∞
=
x
n
x
2
x
N
szeregów (sum) nieskończonych, np. wartość wyrażenia
e
x
=
1
+
x
+
+
...
+
+
...
obliczamy
n
!
2
N
!
n
0
dla odpowiednio dobranej liczby N zastępując sumę nieskończoną sumą o N pierwszych składnikach tego
N
x
n
x
2
x
N
rozwinięcia:
∑ =
=
1
+
x
+
+
...
+
. Ze względu na długi czas obliczeń tego rodzaju sum stosujemy
n
!
2
N
!
n
0
niewielkie wartości N . Również podczas obliczania wartości całki oznaczonej jako granicy sum
przybliżających ją dla coraz to gęstszych podziałów, przyjęcie jednej z tych sum jako wartości bliskiej
całce oznaczonej jest błędem obcięcia:
b
1
N
−
1
f(x)
() ( ) h
∑
( )
I
=
∫
y
x
dx
≈
h
y
+
y
=
T
2
n
n
+
1
a
n
=
0
gdzie
y
b
−
a
y n
n+1
h
= jest ilością podziałów
N
a
h
b
x
Przykład dodawania/odejmowania małej i dużej liczby:
Przesunięte mantysy względem tych samych cech powodują brak dodania/odjęcia liczb ze względu na
ograniczoną reprezentację mantysy wyniku (błąd odcięcia).
3
79615144.008.png 79615144.009.png 79615144.010.png
AKADEMIA GÓRNICZO-HUTNICZA im. St. Staszica w Krakowie
Wydział Elektrotechniki, Automatyki, Informatyki i Elektroniki
Katedra Automatyki, Laboratorium Informatyki w Zarządzaniu
dr Adrian Horzyk - adiunkt
30-059 Kraków, Al. Mickiewicza 30
http://home.agh.edu.pl/~horzyk
paw. H6/325, C3/214
tel.: 012-617-4319, 3924
e-mail: horzyk@agh.edu.pl
Błędy zaokrągleń pojawiają się podczas obliczeń na skutek konieczności zaokrąglania obliczonych
wartości ze względu na ograniczoną długość słów binarnych (np. dzielenie dwóch liczb wymiernych
prowadzi często do konieczności zaokrąglenia powstałej w wyniku dzielenia liczby niewymiernej, np.
1
=
0
333333
...
≈
0
333333
lub
1
=
0
166666
...
≈
0
166667
). Błędy te czasami można zmniejszyć
3
6
ustalając umiejętnie sposób i kolejność wykonywanych działań:
Przykład niestabilności numerycznej na przykładzie obliczania ciągu całek oznaczonych:
1
x
n
1
x
n
+
5
x
n
−
1
−
5
x
n
−
1
1
5
x
n
−
1
1
1
x
n
−
1
1
y
=
∫
dx
=
∫
dx
=
∫
x
n
−
1
−
dx
=
∫
x
n
−
1
dx
−
5
∫
dx
=
−
5
y
n
x
+
5
x
+
5
x
+
5
x
+
5
n
n
−
0
0
0
0
0
otrzymujemy zależność rekurencyjną:
y
+
5 1 =
y
1
.
n
n
−
n
1. sposób obliczania dla 3 cyfr znaczących
y
=
1
−
5
y
:
n
n
n
−
1
1
dx
( )
y
= ∫ x
=
ln
+
5
1
0
=
ln
6
−
ln
5
≈
0
182
łąd
ε
≤
5
⋅
10
−
4
0
x
+
5
0
y
= y
1
5
≈
0
090
łąd
ε
≤
25
⋅
10
−
4
1
0
y
= y
1
5
≈
0
050
łąd
ε
≤
125
⋅
10
−
4
2
2
1
y
= y
1
5
≈
0
083
( y 3 > y 2 – nie poprawne! ) błąd
ε
≤
625
⋅
10
−
4
3
3
2
y
= y
1
5
≈
−
0
165
(ujemna wartość – absurd! ) błąd
ε
≤
3125
⋅
10
−
4
4
4
3
Błąd zaokrąglania ε wartości y 0 , którego moduł może sięgać jest przemnażany przez -5 dla
każdego następnego elementu powyższego ciągu. Błąd bardzo szybko rośnie w kolejnych iteracjach!
5
⋅
10
−
4
2. sposób obliczania dla 3 cyfr znaczących
y
=
1
−
1
y
:
n
−
1
5
n
5
n
Przyjmiemy, że
y ≈
y
ponieważ
y
+
5
y
=
1
⇒
y
≈
1
≈
0
017
10
9
9
9
10
9
60
y
= y
1
1
≈
0
019
y
= y
1
1
≈
0
028
y
= y
1
1
≈
0
058
8
45
5
9
5
45
5
6
2
45
5
3
y
= y
1
1
8
≈
0
021
y
= y
1
1
≈
0
034
y
= y
1
1
≈
0
088
7
45
5
4
45
5
5
1
45
5
2
y
= y
1
1
≈
0
025
y
= y
1
1
≈
0
043
y
= y
1
1
≈
0
182
poprawny!!!
6
45
5
7
3
45
5
4
0
45
5
1
4
1
79615144.011.png 79615144.012.png 79615144.013.png 79615144.014.png
AKADEMIA GÓRNICZO-HUTNICZA im. St. Staszica w Krakowie
Wydział Elektrotechniki, Automatyki, Informatyki i Elektroniki
Katedra Automatyki, Laboratorium Informatyki w Zarządzaniu
dr Adrian Horzyk - adiunkt
30-059 Kraków, Al. Mickiewicza 30
http://home.agh.edu.pl/~horzyk
paw. H6/325, C3/214
tel.: 012-617-4319, 3924
e-mail: horzyk@agh.edu.pl
Błąd zaokrąglania ε wartości y 9 jest każdorazowo dzielony przez -5 dla każdego następnego
elementu powyższego ciągu. Błąd bardzo szybko maleje w kolejnych iteracjach!
y =
poprzez obliczanie ciągu y 0 , y 1 , y 2 , ..., gdzie y 0 to dowolnie wybrana liczba dodatnia, na podstawie której
x
wyznaczamy kolejne wyrazy ciągu:
y
=
1
⎜
y
+
x
⎟
dla i = 1, 2, 3, ...
i
2
i
−
y
⎝
⎠
i
−
1
Przykład przenoszenia się błędów podczas obliczeń:
Jeśli
x
1
=
2
31
±
0
02
i
x
2
=
1
42
±
0
03
to jakie jest oszacowanie
x − ?
x
2
Największa możliwa wartość x 1 = 2,33
Najmniejsza możliwa wartość x 2 = 1,39
Największa możliwa – wartość x 1 – x 2 = 0,94
Najmniejsza możliwa wartość x 1 – x 2 = 0,84
Więc
0
84
≤
x
1
−
x
2
≤
0
94
⇒
x
1
−
x
2
=
0
89
±
0
05
Zadanie numeryczne jest źle uwarunkowane , jeśli niewielkie względne zmiany danych powodują duże
względne zmiany wyników:
Przykład dwóch prostych równoległych:
α
x
1
+
α
2
x
2
=
γ
1
β
x
1
+
β
2
x
2
=
γ
2
Małe zaburzenie danych (
α
1
,
α
2
,
β
1
,
β
2
,
γ
,
γ
2
)
powoduje, że proste się przecinają,
a więc zadanie jest źle uwarunkowane.
Zadanie numeryczne jest problemem polegającym na wyznaczeniu wektora wyników w na podstawie
wektora danych a .
Mówimy, że zadanie jest dobrze postawione , jeśli wektor w jest jednoznacznie określony dla przyjętego
wektora danych a .
Niech D oznacza zbiór danych a , dla których zadanie jest dobrze postawione. Na zbiorze D istnieje zatem
odwzorowanie W takie, że w = W(a) . Niech ŵ oznacza obliczony numerycznie wektor wyników. W celu
obliczenia ŵ należy sformułować algorytm obliczeniowy polegający na określeniu ciągu działań, które
trzeba wykonać nad wektorem danych a i wynikami poprzednich działań, przy czym algorytm ten będzie
poprawnie sformułowany wtedy, gdy liczba niezbędnych działań będzie skończona (choć może zależeć
od wektora danych a ).
Algorytm określa odwzorowanie WN takie, że w = WN(a, ε ) . Odwzorowanie WN jest określone
na zbiorze DN D ponieważ nie można uwzględniać przy obliczaniu takich a ∈ D , które powodują
zatrzymanie się maszyny z powodu powstania błędów, np. nadmiaru.
⊆
Mówimy, że algorytm obliczeniowy jest numerycznie stabilny , jeżeli dla dowolnie wybranych danych
a 0 ∈ D istnieje taka dokładność obliczeń ε 0 , że dla ε < ε 0 mamy a 0 ∈ DN (ε) oraz lim ε →0 WN(a 0 , ε ) = W(a 0 ) .
5
Przykład stabilności numerycznej i dobrego uwarunkowania zadania obliczania pierwiastka
⎛
⎞
1
1
1
1
1
79615144.015.png 79615144.016.png 79615144.017.png

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin