Jan Tobijasiewicz - Laboratorium Metod Numerycznych 12.03.12r.
Lab 2. Błędy, uwarunkowania, poprawność algorytmów
Wstęp
Podczas zajęć badałem wpływy przybliżeń na poprawność działania algorytmów, oraz
poprawność wykonywanych przez nie obliczeń. Za pomocą programu Matlab i załączonych
do treści laboratorium m-plików, szukałem rozwiązań: równania kwadratowego, układu
równań liniowych oraz całki nieoznaczonej.
Równanie kwadratowe
W tym ćwiczeniu należało znaleźć pierwiastki równania kwadratowego danego wzorem:
Za pomocą metod analitycznych otrzymałem następujące wyniki:
∆= 2
ଶ
− 4
= 12
=
−
± √∆
2
⇒x
ଵ
=
−1 − √3;x
ଶ
=
−1 + √3
Za pomocą załączonego m-pliku można było uzyskać rozwiązania tego równania z różną
dokładnością. M-plik został przeze mnie zmodyfikowany w następujący sposób:
format
long
a2 = 1;
a1 = 2;
a0 = -2;
delta = a1^2 - 4*a2*a0
x1 = zeros(5,1);
x2 = zeros(5,1);
y1 = zeros(5,1);
y2 = zeros(5,1);
x1(1,1) = (-a1 - sqrt(delta))/(2*a2);
x2(1,1) = (-a1 + sqrt(delta))/(2*a2);
y1(1,1) = a2*x1(1,1)^2 + a1*x1(1,1) + a0;
y2(1,1) = a2*x2(1,1)^2 + a1*x2(1,1) + a0;
for
m = 2:5
p_z_delta(m) = round(sqrt(delta)*(10^m))/(10^m);
x1(m,1) = (-a1 - p_z_delta(m))/(2*a2);
x2(m,1) = (-a1 + p_z_delta(m))/(2*a2);
y1(m,1) = a2*x1(m,1)^2 + a1*x1(m,1) + a0;
y2(m,1) = a2*x2(m,1)^2 + a1*x2(m,1) + a0;
end
x1
x2
y1
y2
Oto otrzymane wyniki:
delta = 12
x1 =
-2.732050807568877
-2.730000000000000
-2.732000000000000
-2.732050000000000
-2.732050000000000
x2 =
0.732050807568877
0.730000000000000
0.732000000000000
0.732050000000000
0.732050000000000
y1 =
0
-0.007100000000000
-0.000175999999999
-0.000002797500000
-0.000002797500000
y2 =
-0.000000000000000
-0.007100000000000
-0.000176000000000
-0.000002797500000
-0.000002797500000
Widać, że jedynie dla symbolicznego zapisu sqr(3) matlab poprawnie zinterpretował
wartość y1 oraz y2 jako równe zero. Jeśli przyjąć dokładność y2 jako punkt odniesienia, to w
przypadku przybliżenia wartości
√3 do dwóch miejsc po przecinku to wartość miejsc
zerowych jest aż o 13 rzędów większa niż wartość jaką moglibyśmy już uznać za zero.
Jeśliby użyć tak zaokrąglonej liczby jako warunku do wyjścia z pętli stworzyłoby się
niestabilny algorytm. Widać na tym przykładzie jak łatwo przy zbyt wielkich zaokrągleniach
stracić sens liczby zero.
Układ trzech równań liniowych
W tym ćwiczeniu należało odnaleźć rozwiązania układu równań w postaci:
Należy zauważyć, że w przypadku b) popełniamy spory błąd wykonując odcięcie
zamiast zaokrąglenia. Wartości jakie można otrzymać z obliczeń analitycznych to:
dla przypadku a: x
1
= -174 ; x
2
= 972 ; x
3
= -840
dla przypadku b: x
1
~ -1377,8 ; x
2
~ 7217,5 ; x
3
~ -6663,5
Niedokładność wprowadza nam rozwiniecie dziesiętne ułamka
ଵ
ଷ
zgodnie z poleceniem
ćwiczenia wykonywałem kolejne przybliżenia jego wartości:
1.0.1 - Wyniki oraz błąd bezwzględny obliczeń
Przybliżenie
:
0.33
0.333
0.3333
0.33333
x
1
:
x
2
:
x
3
:
ε
dla x
1
:
ε
dla x
2
:
ε
dla x
3
:
-1377.77…
7217.46…
-6663.49…
691%
642%
693%
-191.4388…
1062.585…
-924.4863…
10.02%
9.32%
10.06%
-175.606…
980.345
-847.834
0.92%
0.85%
0.92%
-174.159…
972.827…
-840.772…
0.09%
0.08%
0.09%
Dokładność otrzymanych wyników określiłem poprzez błąd bezwzględny ε.
=
| −
|
∙ 100%
Gdzie:
- wartość przybliżona,
- wartość dokładna.
Jako wartość dokładną przyjmuje wyliczone analitycznie wartości dla przypadku bez
rozwinięć dziesiętnych. Można zauważyć, że z każdą dodatkową cyfrą znaczącą, wartość
błędu bezwzględnego obniża się o rząd wielkości, pokazuje to jak ważna jest dobór
odpowiedniej precyzji zaokrągleń. Na podanym przykładzie niepoprawne przybliżenie
prowadziło do 6-cio krotnego przekłamania, coś takiego nie jest dopuszczalne w nawet
najprostszych obliczeniach. Na podstawie otrzymanych wyników można też stwierdzić że już
dla 5 cyfr znaczących otrzymuje się wyniki z błędem na poziomie około jednego promila.
Badanie stabilności numerycznej
Ćwiczenie to miało na celu porównaniu metod analitycznych z numerycznymi przy
rozwiązywania całki oznaczonej danej wzorem:
+ 5
ଵ
Gdzie: n – parametr naturalny z przedziału [1,8]
Za pomocą metod symbolicznych w programie matlab obliczyłem dokładne wartości
ośmiu całek:
>>%n=1
>> pretty(int(x/(x + 5),x,0,1))
/ 6 \
1 - 5 log| - |
\ 5 /
>>%n=2
>> pretty(int(x^2/(x + 5),x,0,1))
9
25 log(6) - 25 log(5) - -
2
>>%n=3
>> pretty(int(x^3/(x + 5),x,0,1))
/ 5 \ 137
125 log| - | + ---
\ 6 / 6
>>%n=4
>> pretty(int(x^4/(x + 5),x,0,1))
/ 5 \ 1367
- 625 log| - | - ----
\ 6 / 12
>>%n=5
>> pretty(int(x^5/(x + 5),x,0,1))
/ 5 \ 34187
3125 log| - | + -----
\ 6 / 60
>>%n=6
>> pretty(int(x^6/(x + 5),x,0,1))
/ 5 \ 11395
- 15625 log| - | - -----
\ 6 / 4
>>%n=7
>> pretty(int(x^7/(x + 5),x,0,1))
/ 5 \ 398829
78125 log| - | + ------
\ 6 / 28
>>%n=8
>> pretty(int(x^8/(x + 5),x,0,1))
/ 5 \ 3988283
- 390625 log| - | - -------
\ 6 / 56
W tabeli 1.2 są umieszczone wartości całek w zależności od parametru n, tabela zawiera
również wartości wyliczone za pomocą m-pliku
1.0.2 - Wyniki
Parametr n:
n=1
n=2
n=3
n=4
n=5
n=6
n=7
n=8
Wartość
całki:
0.0884
0.0580
0.0431
0.0343
0.0285
0.0243
0.0212
0.0188
Za pomocą m-pliku otrzymałem diagramy słupkowe(wykresy 1.3) przedstawiające
wartości obliczonych całek, m-plik został przeze mnie zmodyfikowany tak by dla każdej z
metod liczyć przypadki dla n od 1 do 8, należy pamiętać że pierwszy słupek przedstawia
wartość
log
ହ
, kolejne przedstawiają już odpowiednie wartości w zależności od parametru n:
Wartości całek w przypadku pierwszego wzoru liczone były rekurencyjnie zaczynając
od wartości dla n=1 czyli:
1 − 5 log
ହ
. Wzór drugi liczył rekurencyjnie w dół zaczynając od
uproszczonej wartości dla n=8, czyli:
ଵ
. Łatwo zauważyć, że ograniczenie dokładności do 3
cyfr znaczących nie wpłynęło znacznie na poprawność wyników (odnosząc się do „wzór 1
bez ograniczeń” gdzie wartości są liczone z dużą precyzją) w przypadku wzoru nr.2,
natomiast dla pierwszego wzoru wyniki są przekłamane prawie sześciokrotnie. Jest to
spowodowane propagacją błędu zaokrąglenia jaki pojawia się na początku procedury
rekurencyjnej. Ta niedokładność wraz z każdym krokiem staje się coraz większa, w ósmym
kroku wynik różni się o cztery rzędy wielkości! Niemożna jednak powiedzieć, że algorytm
jest niestabilny ponieważ istnieje taka dokładność dla której wyniki są bliskie wzorcowym.
Przy dziewięciu cyfrach znaczących nie widać już różnicy w wynikach otrzymanych za
pomocą wzoru nr.1 i nr.2 (wykresy 1.4)
1.0.3 - Wyniki dla dokładności 10^3
1.4 - Wykresy dla dokładności 10^9
Wnioski
Podczas obliczeń numerycznych należy zwracać uwagę nie tylko na poprawność
stworzonego algorytmu ale też na fakt, że zaprogramowane przez nas operacje nigdy nie będą
się wykonywać z nieskończoną dokładnością. Wykonane przeze mnie ćwiczenia pokazały, że
błędy przybliżeń oraz ich propagacje mogą diametralnie zmienić wyniki przeprowadzonych
działań. Należy w miarę możliwości porównywać otrzymywane wyniki z odrębnym modelem
matematycznym lub innymi dostępnymi danymi, dobrze jest też próbować rozwiązać dany
problem na kilka sposobów i wybrać najoptymalniejszy.