1. Metoda połowienia i jej własności
Załóżmy, że poszukujemy rozwiązania równania f(x)=0 na przedziale *a, b+. Załóżmy ponadto,
że funkcja jest ciągła na tym przedziale oraz istnieje w nim dokładnie jeden pierwiastek.
Punkty a oraz b (a<b), wybieramy tak, aby był spełniony warunek f(a)f(b)<0. Spełnienie
tej nierówności przy założeniu ciągłości funkcji gwarantuje nam, że w przedziale (a, b)
znajduje się co najmniej jeden pierwiastek równania f(x)=0. W kolejnych krokach
połowimy nasz przedział i sprawdzamy, w której części przedziału znajduje się nasz
pierwiastek.
Algorytm metody połowienia
1. Wyznaczamy punkt c=(a+b)/2 i obliczmy wartośd f(c) Jeśli f(c)=0, to znaleźliśmy
rozwiązanie. W przeciwnym przypadku przechodzimy do punktu 2.
2. Jeśli f(a)f(c)<0, to podstawiamy b=c i przechodzimy do punktu 3. W przeciwnym
razie podstawiamy a=c i przechodzimy do punktu 3.
3. Sprawdzamy, czy b-a<ε, gdzie ε jest zadaną dokładnością obliczeo. Jeśli ten warunek jest
spełniony, to kooczymy obliczenia. Jeśli nie, to wracamy do punktu 1.
2. Metoda siecznych i jej własności
W tej metodzie wyznaczamy kolejne przybliżenie wykorzystując dwa wcześniejsze.
Metoda ta nie zawsze jest zbieżna. Punkty, od których zaczynamy iteracje musza byd
odpowiednio blisko rozwiązania. Zauważmy, że wyrażenie:
jest przybliżeniem odwrotności pochodnej w punkcie x
n-1
. Wzór na kolejne przybliżenia dla
tej metody można łatwo wyprowadzid samemu. W tym celu przybliżamy wartośd funkcji
w rozwiązaniu:
Następnie przybliżamy pochodną ilorazem różnicowym:
Łącząc powyższe wzory uzyskujemy:
Wyznaczając z powyższego równania x
n
otrzymujemy poszukiwany wzór.
Jako kryterium zakooczenia iteracji można tutaj przyjmowad różnice dwóch kolejnych
przybliżeo |x
n
- x
n-1
| lub |f(x
n
)|. Jednakże oba kryteria zatrzymania iteracji mogą
prowadzid do fałszywych wyników. Można zmodyfikowad kryterium z modułem różnicy
kolejnych przybliżeo dodając warunek |x
n
- x
n-1
| >= |x
n-1
- x
n-2
| . Wtedy będziemy przerywad
iteracje jeśli |x
n
- x
n-1
| < ε (ten składnik zapobiega zbyt szybkiemu przerwaniu iteracji) i
|x
n
- x
n-1
| >= |x
n-1
- x
n-2
| (spełnienie tej nierówności oznacza dominowanie błędów
zaokrągleo).
3. Metoda Newtona dla pojedynczego równania i układu równao (w tym jej własności)
a) dla pojedynczego równania
Rozważmy rozwinięcie funkcji f(x) w szereg Taylora w punkcie x
0
+ ε, gdzie f(x
0
)=0.
Jeśli pominiemy czynniki rzędu drugiego i wyższe to:
Korzystając z f(x
0
+ε)=0 możemy wyznaczyd poprawkę:
Stąd otrzymamy wzór iteracyjny postaci:
Jest to metoda Newtona nazywana także metodą stycznych.
Warunkiem koniecznym zbieżności jest, aby f’(x) ≠0, a warunkiem wystarczającym, aby
W tej metodzie ważny jest dobór punktu startowego.
W przypadku złego doboru punktu startowego metoda będzie rozbieżna (jest to metoda
zbieżna lokalnie!)
Konstrukcja warunku przerwania iteracji jest analogiczna jak w metodzie siecznych.
Metoda ta jest szybciej zbieżna niż opisywane dotąd metody (rząd 2 dla pierwiastków
pojedynczych i 1 dla pierwiastków wielokrotnych).
b) dla układu równao
Rozważamy jak poprzednio układ równao (nieliniowych) F(x)=0. Możemy ją w analogiczny
sposób jak w przypadku pojedynczego równania korzystając z rozwinięcia w szereg
Taylora funkcji wielu zmiennych F(x) i obcięciu go na składniku liniowym. Zakładając, że
pochodna F’(x) jest ciągła w x* (gdzie F(x*)=0) a pochodna F’(x*) jest nieosobliwa)
otrzymujemy metodę
która jest lokalnie zbieżna. Wadą tej metody jest koniecznośd odwracania macierzy w
każdym kroku.
4. Metoda iteracji prostych dla pojedynczego równania i układu równao (w tym jej
własności)
a) dla pojedynczego równania
Zapiszmy równanie f(x)=0 w następującej postaci: f(x)+x=0+x.
Stąd otrzymujemy równanie f(x) + x = ϕ(x) = x
z nową funkcją ϕ(x). Oczywiście funkcję ϕ(x) można wyznaczyd przekształcając odpowiednio
funkcję f(x) np. równanie
f(x) = 2x
3
+3x
2
+x -5 = 0
przekształcamy do postaci
W ten sposób otrzymujemy metodę iteracyjną x
n+1
= ϕ(x
n
).
Jeśli funkcja ϕ(x) jest różniczkowalna to metoda ta jest zbieżna, gdy spełniony jest warunek:
|ϕ'(x)|<1.
Jeśli funkcja ϕ(x) nie jest różniczkowalna to metoda ta jest zbieżna, gdy:
gdzie x* jest rozwiązaniem równania f(x)=0. Im wypisany wyżej ułamek (pochodna dla
funkcji różniczkowalnej) jest mniejsza, tym metoda jest szybciej zbieżna.
Jako kryterium zakooczenia iteracji można tutaj przyjmowad różnice dwóch kolejnych
przybliżeo |x
n
- x
n-1
| lub |f(x
n
)|, podobnie jak w przypadku metody siecznych.
b) dla układu równao
Przekształcamy układ równao F(x)=0 analogicznie jak dla pojedynczego równania do postaci
Warunkiem wystarczającym zbieżności jest
gdzie elementy macierzy D wyznaczamy ze wzoru
dla i, j=1,…,n.
Metoda jest zbieżna, jeżeli promieo spektralny macierzy D(x*) jest mniejszy od 1, gdzie
5. Podobieostwa i różnice pomiędzy metodami omawianymi na wykładzie
a) kryterium stopu
* bisekcja: b-a< ε
* inne metody - różnica dwóch kolejnych przybliżeo |x
n
- x
n-1
| lub |f(x
n
)|
b) zbieżnośd
*metoda siecznych - nie zawsze zbieżna
*Newtona - Warunkiem koniecznym zbieżności jest, aby f’(x) ≠0, a warunkiem
wystarczającym, aby
Metoda ta jest szybciej zbieżna niż inne.
*iteracji - Jeśli funkcja ϕ(x) jest różniczkowalna to metoda ta jest zbieżna, gdy
spełniony jest warunek: |ϕ'(x)|<1.
Jeśli funkcja ϕ(x) nie jest różniczkowalna to metoda ta jest zbieżna, gdy:
c) inne
*metoda Newtona i siecznych - ważny dobór punktu startowego
*bisekcja wymaga przedziału
*metoda Newtona i iteracji używana do rozwiązywania układów równao
nieliniowych
6. Kryteria stopu w poznanych metodach - ich wady i zalety
a) bisekcji
- Sprawdzamy b-a< ε jeśli warunek zachodzi to mamy rozwiązanie
- błędne jest sprawdzanie warunek |f(c)|< ε bo może generowad błędy
b) metoda siecznych, Newtona i iteracji prostych :
- różnica dwóch kolejnych przybliżeo |x
n
- x
n-1
| lub |f(x
n
)|
-> może generowad błędy dlatego wprowadza się modyfikacje.
- |x
n
- x
n-1
| ε - zapobiega zbyt szybkiemu przerwaniu iteracji
- |x
n
- x
n-1
| ≥ |x
n-1
- x
n-2
| - spełnione -> dominowanie błędów zaokrągleo
- Metoda Newtona szybciej zbieżna od innych
7. Kwadratura Newtona-Cotesa i jej własności
Założenia:
x
i
= a+ h
i
, h>0, i=0, 1,…, n, gdzie n wyznaczone jest z zależności b-a=nh.
Funkcję f(x) przybliżamy wielomianem interpolacyjnym Lagrange’a opartym na węzłach x
i
.
f (x)dx=
L(x)dx +r[ f ], gdzie r[f+ oznacza błąd metody
Uzyskujemy :
f (x)dx=
r[ f ]
Jeśli p(x)=1
*metoda trapezów - wielomian pierwszego stopnia
A 0=
A1=
f (x)dx=
* metoda Simsona - wielomian drugiego stopnia
A 0=
A1=
A 2 =
f (x)dx=
- Kwadratur wyższych rzędów nie muszą dawad dokładniejszych wyników.
W oparciu o pochodną wysokiego rzędu możemy szacowad błędy.
W praktyce stosuje się kwadratury złożone niższych rzędów, bo pozwalają zredukowad błąd
kwadratury, który jest zależny od odległości pomiędzy kolejnymi węzłami.
Cechy:
- przedział *a, b+ podzielony na podprzedziały
-kwadratury niskich rzędów lepsze
-przybliżenie całki to suma przybliżeo na podprzedziałach.
- W przypadku kwadratur Newtona-Cotesa punkty, w których dana jest wartośd funkcji są
zadane (na nich budowany jest wielomian interpolacyjny).
- Kwadratura jest rzędu n, jeśli jest dokładna dla wszystkich wielomianów stopnia
mniejszego od n oraz istnieje wielomian stopnia n, dla którego nie jest dokładna.
-Kwadratury Newtona-Cotesa oparte na n+1 są rzędu n+2 dla n parzystych i rzędu n+1 dla n
nieparzystych.
8. Metoda Romberga i jej własności
Wykorzystuje ekstrapolacje Richardsona do eliminacji w błędzie kwadratury składników przy
najwyższych potęgach w oparciu o wyniki dla niższych potęg
Idea metody
Dzielimy przedział *a, b] na
równych części. Niech
Wzór złożony trapezów :
Błąd :
Kwadratura
-Ze zbieżności T
0,m
wynika ze zbieżnośd T
m,0
, który na większości przypadków zbiega szybciej.
- Trudno wskazad, która kwadratura jest najlepsza. To będzie zależało od tego, co nas
najbardziej interesuje(minimalizacja błędu, nakład obliczeo)
9. Kwadratury Gaussa i ich własności
10. Podobieostwa i różnice pomiędzy kwadraturami Newtona-Cotesa i Gaussa
Podobieostwa
- Mamy przedziały *a,b+
- Całki przybliżany z tego samego wzoru
f (x)dx=
Różnice
- W Newtonie-Cotesie są metody trapezów i Simsona w Gaussie np. kwadratura Gaussa-
Jacobiego/Czybyszewa
- W Newtonie-Cotesie funkcje przybliżamy wielomianem interpolacyjnym Lagrange'a, a w
Gaussie wielomianem ortogonalnym.
- W N-C błąd zależny od odległości między kolejnymi węzłami w Gaussie błąd ze wzrostem
liczby węzłów
- Różnica w stosunku do kwadratur Newtona-Cotesa polega na tym, że w Gaussie dobieramy
współczynniki Ai, i węzły xi.
- Różne rzędy kwadratur n+1 węzłów daje rząd n+2, a w Gaussie n+1 daje rząd 2n+1
11. Kryteria wyboru kwadratury
- Trudno wskazad, która kwadratura jest najlepsza. To będzie zależało od tego, co nas
najbardziej interesuje (minimalizacja błędu, nakład obliczeo, itp.).
- Różnica w stosunku do kwadratur Newtona-Cotesa polega na tym, że w Gaussie dobieramy
współczynniki A
i
, i węzły x
i
.
- Funkcja p(x) - w zależności czy chcemy zminimalizowad błąd czy go zupełnie wyeliminowad / czy
chcemy międ dużo do liczenia czy nie/ jak bardzo chcemy mied dokładny wynik. W zależności czy
granice całkowania należą do przedziału czy nie.