Algorytmy i struktury danych

1.

ALGORYTMY I STRUKTURY
DANYCH
W-1
Jan Sikora
WSEI, Lublin 2023
1

2. Źródło: B. Pańczyk E. Łukasik J. Sikora T. Guziak Metody Numeryczne w przykładach Wydawca: Politechnika Lubelska

2

3. Błędy obliczeń numerycznych

W teorii metod numerycznych zasadniczą rolę odgrywa zrozumienie
ograniczeń danej metody, co jest z kolei ściśle związane z określeniem błędu
obliczeniowego. Na dzisiejszym wykładzie przedstawimy podstawowe definicje
i problemy dotyczące obliczeń numerycznych.
Przez zadanie numeryczne rozumiemy jasny i jednoznaczny opis powiązania
funkcjonalnego między danymi wejściowymi (zmienne niezależne) i danymi
wyjściowymi (szukanymi wynikami).
Algorytm dla danego zadania numerycznego jest z definicji pełnym opisem
poprawnie określonych operacji przekształcających dopuszczalne dane
wejściowe na dane wyjściowe.
„Operacje” oznaczają tu działania arytmetyczne i logiczne. Dla danego
zadania numerycznego można rozważać wiele różnych algorytmów. Algorytmy
te mogą dawać wyniki o bardzo różnej dokładności.
3

4. Podstawowe pojęcia szacowania błędów

Mówiąc o błędach numerycznych należy poznać podstawowe pojęcia z nimi
związane, które krótko omówione zostaną na dzisiejszym wykładzie.
4

5. Źródła błędów

Do źródeł błędów można zaliczyć:
a) błędy danych wejściowych (gdy wykorzystujemy dane zaokrąglone,
pochodzące np. z wcześniejszych obliczeń lub gdy dane wejściowe
są wynikiem pomiarów wielkości fizycznych obarczonych błędami
pomiarowymi),
b) błędy zaokrągleń w czasie obliczeń (związane z odpowiednią
reprezentacją liczby),
c) błędy obcięcia (gdy proces obliczania granicy jest przerywany przed
osiągnięciem wartości granicznej - np. ograniczenie szeregu
nieskończonego do skończonej liczby składników, aproksymacja
pochodnej za pomocą ilorazu różnicowego, obliczanie wartości całki
oznaczonej jako granicy sum przybliżających ją podziałów itp.),
d) uproszczenie modelu matematycznego (przyjęcie założeń
upraszczających),
e) błędy programisty.
5

6. Błędy względne i bezwzględne

x . Wówczas:
Załóżmy, że wartość x jest reprezentowana jako ~
błąd bezwzględny reprezentacji jest równy ~
x x.
~
x x
100%, x 0.
błąd względny [%] reprezentacji jest równy
x
Przyjmijmy, że zapis x ~
x x . Wartość
x oznacza, że ~
max x ~
x nazywamy maksymalnym błędem bezwzględnym lub
błędem granicznym.
Mówiąc o liczbie cyfr istotnych w ułamku dziesiętnym nie uwzględnia
się zer na początku tego ułamka, gdyż określają one tylko pozycję kropki
dziesiętnej. Natomiast cyfry ułamkowe są to wszystkie cyfry po kropce
dziesiętnej, także ewentualne zera.
1
x x 10 t , to mówimy, że ~
x ma t poprawnych cyfr
Jeśli ~
2
ułamkowych. Cyfry istotne występujące aż do pozycji t-tej po kropce
nazywamy cyframi znaczącymi.
6

7. Błędy obliczeń numerycznych

Przykład 1.1.
W kolejnych przykładach podano liczby odpowiednich cyfr:
0.00147
12.34
0.001234 +/- 0.000004
0.001234 +/- 0.000006
– 5 cyfr ułamkowych,
– 2 cyfry ułamkowe,
– 5 cyfr poprawnych,
– 4 cyfry poprawne,
3 cyfry istotne,
4 cyfry istotne,
3 cyfry znaczące,
2 cyfry znaczące.
7

8. Przenoszenie się błędów (+/-)

Przenoszenie się błędów numerycznych najlepiej zobrazuje przykład 1.2.
Niech x_1=2.31 +/- 0.02,
x_2=1.42 +/- 0.03.
8

9. Przenoszenie się błędów (+/-)

Obliczmy różnicę:
x1 x2 : 2.33 -1.39 = 0.94, 2.29 -1.45 = 0.84,
czyli:
x1 x2 = 0.89 0.05.
Ogólnie mamy:
(~
x ) (~
x ) x x ~
x (~
x ).
1
1
2
2
1
2
1
1
2
2
Zatem:
x1 x2 ~
x1 ~
x2 ( 1 2 ) ,
gdzie:
1, 2 są maksymalnymi błędami bezwzględnymi.
Błąd bezwzględny sumy i różnicy jest więc równy: 1 2 .
9

10. Przenoszenie się błędów (*//)

W przypadku obliczania iloczynu lub ilorazu przenoszenie się błędów
przedstawimy za pomocą błędów względnych.
Niech r będzie rzeczywistym błędem względnym, tzn.
~
x x rx x (1 r ) .
Weźmy:
~
x x (1 r ), ~
x x (1 r ) .
1
1
1
2
2
2
Wówczas:
~
x
x (1 r1 )
~
~
x1 x2 x1 x2 (1 r1 )(1 r2 ), ~1 1
.
x2
x2 (1 r2 )
Błąd względny iloczynu jest zatem równy:
(1 r1 )(1 r2 ) 1 1 r1 r2 r1r2 1 r1 r2 ,
jeśli tylko r1 1, r2 1.
10

11. Przenoszenie się błędów (*//)

Błąd względny ilorazu jest równy:
(1 r1 )
1 r1 1 r2 r1 r2
1
r1 r2 , jeśli r2 1.
(1 r2 )
1 r2
1 r2
11

12. Reprezentacja stałopozycyjna

Reprezentacja stałopozycyjna operuje na ustalonej liczbie cyfr ułamkowych –
wszystkie liczby rzeczywiste skraca się do t cyfr ułamkowych.
Długość słowa maszynowego jest zwykle stała (np. s cyfr), więc dopuszcza się
tylko liczby z przedziału:
10 , 10 .
s t
s t
12

13. Reprezentacja zmiennopozycyjna

Reprezentacja zmiennopozycyjna operuje natomiast na ustalonej liczbie cyfr
istotnych.
W przypadku reprezentacji stałopozycyjnej liczbę całkowitą l przedstawiamy za
pomocą rozwinięcia dwójkowego w postaci: