Wprowadzenie do
metod
numerycznych
Izabela Baran
Wioleta Wróbel
Artur Rumelczyk
Wprowadzenie do
metod
numerycznych
Izabela Baran
Wioleta Wróbel
Artur Rumelczyk
Wprowadzenie do metod
numerycznych
1.
Metody Numeryczne
2.
Analiza błędów
3.
Algorytm obliczeń
4.
Schemat Hornera
5.
Rozwijanie funkcji
w ułamkach łańcuchowych
6.
Sumowanie szeregów
potęgowych
Metody Numeryczne
Metody numeryczne są działem matematyki stosowanej
zajmującym się opracowaniem metod przybliżonego
rozwiązywania problemów matematycznych, których albo
nie można rozwiązać metodami dokładnymi, albo metody
dokładne posiadają tak dużą złożoność obliczeniową, że są
praktycznie nieużyteczne.
Cecha charakterystyczna metod numerycznych:
- wykonywanie obliczeń na liczbach przybliżonych.
- rozwiązania zagadnień są wyrażone liczbami
przybliżonymi.
- wielkość błędu w procesie obliczeń numerycznych jest
zawsze kontrolowana.
Analiza błędów
Analiza błędów to usystematyzowane
badanie błędów pomiarowych. Badanie narzędzi
pomiarowych i wyników pomiarów. Analiza błędów
pozwala na obiektywną ocenę ich dokładności.
Rodzaje błędów:
1.
Błędy początkowe,
2.
Błąd nieunikniony (błąd modelu),
3.
Błąd metody,
4.
Błąd obcięcia,
5.
Błąd zaokrągleń,
Analiza błędów c.d.
Dwa pojęcia określania wielkości błędu:
Błąd bezwzględny = | wartość przybliżona - wartość dokładna |
| wartość przybliżona - wartość dokładna |
Błąd względny = ──────────────────────────
|wartość dokładna |
Wartość błędu bezwzględnego zależy od rzędu wielkości rozpatrywanych liczb.
Bardziej obiektywną ocenę dokładności reprezentacji liczb daje wartość błędu
względnego .
Błędy początkowe
Dane liczbowe wprowadzone do pamięci (komputera)
odbiegają od dokładnych wartości tych danych.
Błąd pomiaru – wynikają z pomiarów wielkości fizycznych,
np. błąd odczytu wskazań przyrządów, niedoskonałość
metody pomiarowej, itp.
Błąd reprezentacji – wynikają ze sposobu zapisu wartości
liczby.
Przykład:
Błąd nieunikniony (błąd modelu)
Błąd modelu zwykle wiąże się z przyjęciem
złych parametrów początkowych lub
brzegowych przy jego tworzeniu. Może się też
okazać, iż przyjęto zbyt daleko idące
uproszczenia nieoddające dobrze warunków
rzeczywistych, w jakich odbywa się dane
zjawisko. Mimo tego na ogół buduje się
modele w miarę proste, a następnie
przeprowadza analizę wrażliwości, tzn.
sprawdza, jak duży wpływ ma dany
pojedynczy czynnik na jego funkcjonowanie.
Błąd metody
Błąd metody wiąże się z przyjęciem mało
dokładnych parametrów dla tej metody (zbyt
rzadki podział obszaru ciągłego na skończone
odcinki) lub z zastosowaniem zbyt mało
dokładnej metody (mimo dokładnych
parametrów).
Metod numerycznych dla danego zagadnienia
jest na ogół bardzo dużo. Wybór powinien być
dokonany z uwagi na przewidywaną
postać rzeczywistego zachowania się zjawiska.
Nie dotyczy to metod dokładnych.
Błąd obcięcia
Błąd obcięcia wystąpi, gdy rozwijając daną
funkcję w szereg odrzucamy nieskończoną liczbę
wyrazów od pewnego miejsca, zachowując
jedynie pewną początkową ich liczbę.
Przykład: np. przy obliczaniu sumy szeregu.
Błąd zaokrągleń
Błąd zaokrągleń wynikają z faktu, że
obliczenia wykonujemy na liczbach o
skończonym rozwinięciu pozycyjnym. Wiąże
się z reprezentacją ułamków dziesiętnych
nieskończonych (należy przy tym pamiętać, iż
komputer prowadzi obliczenia z właściwą dla
danego typu liczbowego precyzją, natomiast
pokazywać graficznie wyniki może z
dokładnością żądaną przez użytkownika –
wtedy na potrzeby formatu prezentacji
zaokrągla z daną dokładnością.)
Algorytm obliczeń
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)
Algorytm obliczeń
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:
Oblicz wartość funkcji: wykorzystując rozwinięcie
w szereg
Wyniki:
Algorytm obliczeń
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ązanie.
Przykład:
Oblicz wartość funkcji: zmieniając algorytm dla x < 0
a następnie: = s1 - s2
Wyniki:
Nie dopuszczamy do sytuacji, kiedy w wyniku kumulacji błędów możemy uzyskać wysoce
przekłamany wynik
Algorytm obliczeń
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.
Schemat Hornera
Schemat Hornera sposób obliczania
wartości
wielomianu dla danej wartości
argumentu wykorzystujący minimalną
liczbę mnożeń,
jest to również algorytm dzielenia
wielomianu przez dwumian (x-a).
Schemat Hornera c.d.
Obliczymy wartość wielomianu postaci:
f(x) = x
4
+ 5x
3
- 6x
2
- 7x + 6
dla x
0
= 2 korzystając z algorytmu Hornera.
Przedstawmy nasz wielomian w alternatywnej
postaci dokonując odpowiednich przekształceń:
f(x) = x
4
+ 5x
3
- 6x
2
- 7x + 6 =
= x (x
3
+ 5x
2
- 6x - 7) + 6 =
= x (x (x
2
+ 5x - 6) - 7) + 6 =
= x (x (x (x+5) - 6) - 7) + 6
Schemat Hornera c.d.
Mamy więc :
Wartość wielomianu przy powyższych założeniach wynosi 24.
Ponadto otrzymaliśmy następującą równość:
f(x)= (x
4
+ 5x
3
- 6x
2
- 7x + 6 )=
= (x
3
+ 7x
2
+ 8x + 9)(x-2) + 24
Czyli f(2)=24
x
0
= 2
a
0
=
1
b
0
= 1
a
1
=
5
b
1
=b
0
* x
0
+ a
1
= 1*2 + 5
= 7
a
2
=
-6
b
2
=b
1
* x
0
+ a
2
= 7*2 - 6 =
8
a
3
=
-7
b
3
=b
2
* x
0
+ a
3
= 8*2 - 7 =
9
a
4
=
6
b
4
=b
3
* x
0
+ a
4
= 9*2 + 6
= 24
Schemat Hornera c.d.
Współczynniki:
1
x
4
+
5
x
3
- 6
x
2
-
7
x +
6
: (x-2)
Jeśli jest (x-2) to naszym mnożnikiem jest 2 jeśli było by (x + 2)
naszym mnożnikiem było by -2
1
5
-6
-7
6
2
2
14 + (-
6)
16
18
1
7
8
9
24
Przepisuje
my
Mnożymy
W
yn
.
M
no
że
ni
a
Dodawani
e
Rozwijanie funkcji
w ułamkach łańcuchowych
Zajmijmy się na początek podstawowymi
definicjami. Przez ułamek łańcuchowy,
zapisywany jako
będziemy rozumieli liczbę postaci:
Rozwijanie funkcji
w ułamkach łańcuchowych
Gdzie liczba jest liczbą całkowitą ( a więc może być
ujemna, zero lub dodatnia) zaś są liczbami
naturalnymi. Jest to tak zwany ułamek łańcuchowy
w postaci kanonicznej lub regularnej lub prostej .
Jest to postać wyróżniona – w takim piętrowym ułamku,
wszystkie liczniki zawierają wyłącznie cyfrę 1.
Oczywiście w sensie ogólnym tak być nie musi – mamy
wówczas do czynienia z ułamkiem niekanonicznym lub
złożonym. Teoria ułamków niekanonicznych jest co
najmniej tak samo, jeśli nie bardziej ciekawa jak
ułamków kanonicznych. Jednak w naszych
rozważaniach nie będziemy o nich wspominać.
Rozwijanie funkcji
w ułamkach łańcuchowych
Skoro mamy definicję, spróbujmy zapisać w
tej postaci jakąś liczbę. wiele przykładów jest
bardzo prostych, inne wymagają pewnego
nakładu pracy:
Rozwijanie funkcji
w ułamkach łańcuchowych
Ułamek łańcuchowy nieskończony definiujemy
jako granicę ciągu ułamków skończonych
(granica ta zawsze istnieje):
Rozwijanie funkcji
w ułamkach łańcuchowych
Niektóre funkcje trygonometryczne można
wyrazić w postaci ułamków łańcuchowych:
Sumowanie szeregów potęgowych
Szereg, w matematyce wyrażenie będące
sumą nieskończonego ciągu wyrażeń a
n
,
symbolicznie zapisywane w ogólnej postaci:
Sumowanie szeregów potęgowych c.d.
Gdy wyrażenia w ciągu są liczbami, to szereg
jest szeregiem liczbowym (np. szereg
geometryczny, gdzie kolejne wyrazy tworzą ciąg
geometryczny).
Jeżeli wyrażenia określone są przez funkcje (np.
kolejne potęgi, jak w przypadku szeregu
potęgowego), to mamy do czynienia z szeregiem
funkcyjnym (np. szereg Taylora, szereg
Maclaurina, szereg Fouriera, szereg
Laurenta itd.).
Szereg potęgowy – szereg
funkcyjny postaci:
gdzie współczynniki
są liczbami rzeczywistymi lub zespolonymi.
Sumowanie szeregów potęgowych c.d.
Dodawanie i odejmowanie na szeregach
potęgowych.
Niech szeregi będą zbieżne w swoich kołach
zbieżności przedstawiają odpowiednio
funkcje f(x) i g(x).
Sumowanie szeregów potęgowych c.d.
Przy powyższych oznaczeniach funkcję
przedstawiał będzie szereg
zbieżny w mniejszym z kół zbieżności.
Sumowanie szeregów potęgowych c.d.
Dziękujemy za
uwagę
Izabela Baran
Wioleta Wróbel
Artur Rumelczyk