REPREZENTACJA LICZBY, BA

DY,
ALGORYTMY W OBLICZENIACH
MATEMATYKA STOSOWANA I METODY NUMERYCZNE
Budownictwo, studia I stopnia, semestr III
rok akademicki 2011/2012
Instytut L-5, Wydział Inżynierii Lądowej, Politechnika Krakowska
Adam Wosatko
Ewa Pabisek
MATEMATYKA STOSOWANA I METODY NUMERYCZNE REPREZENTACJA LICZBY, BA

DY, ALGORYTMY W OBLICZENIACH
Pojęcie metody numerycznej
Metoda numeryczna
Algorytm
1
Uporządkowany zestaw czynności zmierzających do osiągnięcia celu,
np. przepis kulinarny.
2
Logiczny ciąg operacji, na skutek których dane wejściowe zostają
przetworzone w wyniki.
Metoda numeryczna
SkoÅ„czona liczba najprostszych dziaÅ‚aÅ„ arytmetycznych (+, -, · , /)
i logicznych określona za pomocą odpowiedniego algorytmu.
Pierwsze metody numeryczne powstały znacznie wcześniej niż komputery!
Dane (liczbowe) Algorytm metody numerycznej Wyniki (liczbowe)
MATEMATYKA STOSOWANA I METODY NUMERYCZNE REPREZENTACJA LICZBY, BA

DY, ALGORYTMY W OBLICZENIACH
Reprezentacja liczby
Pojęcie liczby
Liczba
Dawniej: intuicyjnie rozumiana jako miernik wielkości zbioru
np. przedmiotów.
Dziś: pojęcie abstrakcyjne, podstawowy obiekt matematyczny.
Czy liczba różni się od cyfry?
Liczba składa się z cyfr, tak jak słowo składa się z liter, np. w systemie
dziesiętnym 198819 składa się z cyfr arabskich 1, 8 i 9.
Mówimy: liczba prętów zbrojeniowych, cyfra 5, ilość piasku, ilość stali.
Nie powinniśmy mówić: ilość cegieł, cyfra 14, liczba arabska.
MATEMATYKA STOSOWANA I METODY NUMERYCZNE REPREZENTACJA LICZBY, BA

DY, ALGORYTMY W OBLICZENIACH
Reprezentacja liczby
Reprezentacja liczby
Reprezentacja liczby
to sposób zapisu wartości liczby za pomocą znaków, w szczególności cyfr.
Przykład:
Słownie: sto czterdzieści trzy
Cyfry arabskie, system dziesiętny: 143
system dwójkowy (binarny): 10001111
Cyfry rzymskie: CXLIII
Cyfry starożytnego Egiptu:
jak to liczba?
Zazwyczaj liczba jest reprezentowana przez skończoną liczbę cyfr.
Skończoność zapisu za pomocą cyfr powoduje, że nie dla każdej liczby
1
jest on dokładny, np. Ą = 3.14159 . . . , = 0.16667 . . . .
6
MATEMATYKA STOSOWANA I METODY NUMERYCZNE REPREZENTACJA LICZBY, BA

DY, ALGORYTMY W OBLICZENIACH
Reprezentacja liczby
Reprezentacja liczby rzeczywistej
Zapis zmiennopozycyjny  notacja naukowa
LiczbÄ™ rzeczywistÄ… można zapisać w postaci: L = m · pc,
gdzie: m  mantysa liczby L, p  podstawa systemu pozycyjnego,
c  cecha liczby L.
Przykład:
3472.254 = 0.3472254 · 104 =0.3472254e+04
Liczba cyfr znaczÄ…cych (LCZ)
Liczba cyfr występująca w zapisie liczby, bez uwzględniania tzw. lewych zer
Przykład:
Dla 0.005665, 0.5665, 566.5, 5665000 mamy LCZ = 4.
Cecha c określa rząd wielkości liczby.
Przykład:
0.768344e-01-0.768332e-01=0.000012e-01
Spadek LCZ z 6 do 2 obniżenie dokładności obliczeń.
MATEMATYKA STOSOWANA I METODY NUMERYCZNE REPREZENTACJA LICZBY, BA

DY, ALGORYTMY W OBLICZENIACH
Błędy operacji arytmetycznych
Definicja błędu
Inżynier ma czynienia z błędem, gdy wynik obliczeń (lub pomiaru)
odbiega od wyniku dokładnego czyli PRAWIE ZAWSZE (!!!).
Definicja - błąd bezwzględny
"x = | x - X |
x - wartość dokładna (ścisła), X - wartość przybliżona,
"x - błąd bezwzględny
Definicja - błąd względny
"x x-X
x = = | |
x
| x|
x - błąd względny
MATEMATYKA STOSOWANA I METODY NUMERYCZNE REPREZENTACJA LICZBY, BA

DY, ALGORYTMY W OBLICZENIACH
Błędy operacji arytmetycznych
Błąd bezwzględny i względny
Przykład
Wartość błędu bezwzględnego "x zależy
od rzędu wielkości rozpatrywanych liczb.
Przykład:
x 1.0101 101.01 10101 1010100
X 0.99901 99.901 9990.1 999010
"x 0.01109 1.109 110.90 11090
x 0.010979 0.010979 0.010979 0.010979
Bardziej obiektywną ocenę dokładności reprezentacji liczb
daje wartość błędu względnego x.
MATEMATYKA STOSOWANA I METODY NUMERYCZNE REPREZENTACJA LICZBY, BA

DY, ALGORYTMY W OBLICZENIACH
Błędy operacji arytmetycznych
Podstawowe z
ródła błędów
Wszystkie zagadnienia rozwiÄ…zywane metodami numerycznymi
są na ogół obarczone pewnymi błędami.
Błędy te można podzielić na:
1
błędy wejściowe (początkowe)
2
błędy obcięcia
3
błędy zaokrągleń
4
błędy modelu
5
błędy metody
MATEMATYKA STOSOWANA I METODY NUMERYCZNE REPREZENTACJA LICZBY, BA

DY, ALGORYTMY W OBLICZENIACH
Błędy operacji arytmetycznych
Błędy początkowe
Błędy danych wejściowych
Dane liczbowe wprowadzone do pamięci (komputera) odbiegają
od dokładnych wartości tych danych.
Błędy pomiaru  wynikają z pomiarów wielkości fizycznych,
np. błąd odczytu wskazań przyrządów,
niedoskonałość metody pomiarowej, itp.
Błędy reprezentacji  wynikają ze sposobu zapisu wartości liczby.
Przykład:
1
= 0.210 = 0.(0011)2 <" 0.001100112
=
5
1
= 0.(3)10 = 0.(01)2 <" 0.333333310 <" 0.010101012
= =
3
MATEMATYKA STOSOWANA I METODY NUMERYCZNE REPREZENTACJA LICZBY, BA

DY, ALGORYTMY W OBLICZENIACH
Błędy operacji arytmetycznych
Błędy obcięcia
Błędy obcięcia
Powstają podczas zmniejszenia liczby działań
(teoretycznie nieskończonych), np. przy obliczaniu sumy szeregu.
Przykład:
f (x) = ex dla x = 5.0
Wzór sumacyjny Wynik dokładny n Wynik przybliżony
n xi
5 9.14166667e+01
i=0 i!
10 1.46380601e+02
15 1.48379580e+02
1.48413159e+02 20 1.48413147e+02
MATEMATYKA STOSOWANA I METODY NUMERYCZNE REPREZENTACJA LICZBY, BA

DY, ALGORYTMY W OBLICZENIACH
Błędy operacji arytmetycznych
Błędy zaokrągleń
Błędy zaokrągleń
Pojawiają się podczas wykonywania obliczeń.
Wynikają z ograniczonej reprezentacji liczb w pamięci komputera.
Błędy te możemy zmniejszyć ustalając sposób i kolejność działań lub
precyzję obliczeń (nie zawsze można).
Przykład:
0.2e+00 + 0.1e+17 - 0.1e+17 = 0
0.1e+17 - 0.1e+17 + 0.2e+00 = 0.2e+00
MATEMATYKA STOSOWANA I METODY NUMERYCZNE REPREZENTACJA LICZBY, BA

DY, ALGORYTMY W OBLICZENIACH
Inne rodzaje błędów
Błędy modelu i błędy metody
Błędy modelu
Wyniki obliczeń określają zachowanie się pewnego rzeczywistego układu
fizycznego, chemicznego, itp. Podczas budowania modelu fizycznego (np.
konstrukcji) i matematycznego pomija się część efektów  uznaje się je za
niestotne dla rozwiązania. Przyjęty model stanowi przybliżenie
rzeczywistości. W wyniku obliczeń (numerycznych) mogą pojawić się
jakieś jego niezgodności z zachowaniem układu rzeczywistego, które są
następstwem pomyłek (czyli tzw.  grubych błędów ).
Błędy metody
Metody numeryczne, za pomocą których wykonywane są obliczenia,
bardzo często są metodami przybliżonymi. Zatem realizacja danego
algorytmu może prowadzić do błędu metody. Nie dotyczy to metod
dokładnych.
MATEMATYKA STOSOWANA I METODY NUMERYCZNE REPREZENTACJA LICZBY, BA

DY, ALGORYTMY W OBLICZENIACH
Cechy algorytmów
Kiedy algorytm jest poprawny?
Poszukiwanie rozwiązania problemu czy zadania za pomocą określonej
metody numerycznej ma sens, gdy wiadomo, że to rozwiązanie istnieje
i jest jednoznaczne.
W przeciwnym wypadku możemy doprowadzić do obliczeń bez końca,
co przy zastosowaniu komputera skutkuje zawieszeniem jego działania.
W celu wykonania obliczeń i uzyskania wyniku należy sformułować
poprawny algorytm. Algorytm poprawnie sformułowany jest wtedy,
gdy liczba operacji (działań) będzie skończona.
Dane (liczbowe) Algorytm metody numerycznej Wyniki (liczbowe)
MATEMATYKA STOSOWANA I METODY NUMERYCZNE REPREZENTACJA LICZBY, BA

DY, ALGORYTMY W OBLICZENIACH
Cechy algorytmów
Algorytm numerycznie niestabilny
Algorytm numerycznie niestabilny
Niewielkie błędy wynikające z obliczeń numerycznych (np. zaokrąglenia)
na jakimś etapie rosną tak, że w kolejnych etapach znacznie
zniekształcają wyniki końcowe.
Przykład:
Obicz wartość funkcji: ex wykorzystując rozwinięcie w
szereg
n xi
x x2 x3
ex = 1 + + + + · · · ex H"
1! 2! 3! i=0 i!
Wyniki:
Lp. x n suma szeregu wartość ścisła
1 +5 22 148.413159 148.413159
2 -5 22 6.73795e-3 6.73795e-3
3 +15 50 3.2690e+06 3.2690e+06
4 -15 50 3.0590e-07 3.0590e-07
5 -35 80 48734.921 1.80485e-35
MATEMATYKA STOSOWANA I METODY NUMERYCZNE REPREZENTACJA LICZBY, BA

DY, ALGORYTMY W OBLICZENIACH
Cechy algorytmów
Algorytm numerycznie stabilny
Algorytm numerycznie stabilny
algorytm, który dla nieco zaburzonych danych zwraca nieco zaburzone
wyniki. Zwiększenie dokładności obliczeń pozwala wyznaczyć dowolne
istniejące rozwiążanie.
Przykład: Obicz wartość funkcji: ex zmieniając algorytm dla x < 0
|x| |x|3 |x|5
x2 x4 x6
s1 = 1 + + + + · · · s2 = + + + · · ·
2! 4! 6! 1! 3! 5!
a następnie: ex = s1 - s2
Wyniki:
Lp. x n suma szeregu wartość ścisła
1 -5 22 148.413159 148.413159
2 -15 50 3.0590e-07 3.0590e-07
5 -35 80 1.80485e-35 1.80485e-35
Nie dopuszczamy do sytuacji, kiedy w wyniku kumulacji poszczególnych
błędów możemy uzyskać wysoce przekłamany wynik.
MATEMATYKA STOSOWANA I METODY NUMERYCZNE REPREZENTACJA LICZBY, BA

DY, ALGORYTMY W OBLICZENIACH
Cechy algorytmów
Cechy dobrego algorytmu
Niezawodność, zbieżność
Zawsze daje wyniki  niezależnie od danych.
Stabilność
Zaburzenia w trakcie realizacji (występowanie błędów)
nie wpływają na wynik końcowy.
Szybkość
Wynik uzyskuje się możliwie jak najszybciej (optymalnie szybko).
Można spotkać metody (algorytmy) numeryczne które są szybkie, ale nie
sÄ… stabilne i... odwrotnie.
MATEMATYKA STOSOWANA I METODY NUMERYCZNE REPREZENTACJA LICZBY, BA

DY, ALGORYTMY W OBLICZENIACH
Uwarunkowanie zadania
ZÅ‚e uwarunkowanie zadania
To jak bardzo wynik W (a + ´a) różni siÄ™ od W (a) zależy od rodzaju
zadania i cechÄ™ tÄ… nazywamy uwarunkowaniem zadania.
Zadanie jest z
le uwarunkowane, jeśli małe zmiany danych początkowych
wywołują duże zmiany wyników czyli występuje duża wrażliwość
rozwiązania zadania na małe zmiany danych początkowych.
Przykład: Rozwiązanie układu równań liniowych A x = B:

5 -331 x1 3.5 x1 331.7
= = !!!
6 -397 x2 5.2 x2 5.0

5 -331 x1 3.5 x1 298.6
= = !!!
6 -397 x2 5.1 x2 4.5
Wskaz
nikiem uwarunkowania zadania jest wielkość:
n
cond(A) = ||A|| · ||A-1|| , gdzie: ||A||" = max |aij|.
j=1
1 i m
Zadanie jest dobrze uwarunkowane jeśli cond(A) jest małe.
Dla przykładu:
MATEMATYKA STOSOWANA I METODY NUMERYCZNE REPREZENTACJA LICZBY, BA

DY, ALGORYTMY W OBLICZENIACH
cond(A) = 403 · 728 = 293384 zadanie z
le uwarunkowane