Metody numerycznego znajdowania miejsc
zerowych funkcji jednej zmiennej
Metody nieinkluzyjne:
• Metoda iteracji prostej.
• Metoda stycznych (Newtona).
• Metoda siecznych
Metody inkluzyjne:
• Metoda połowienia (bisekcji).
• Metoda fałszywej linii (regula falsi).
• Metoda Pegaza.
Metody znajdowania zer wielomianów
y
x
x*
Pierwiastek
pojedynczy
Pierwiastek
wielokrotny
parzystego
rzędu
)
(
*)
(
)
(
)
(
*)
(
)
(
0
*)
(
x
g
x
x
x
f
x
g
x
x
x
f
x
f
n
x* jest pierwiastkiem pojedynczym
x* jest pierwiastkiem wielokrotnym
rzędu n
Pierwiastek
wielokrotny
nieparzystego
rzędu
x*
x*
Twierdzenia.
1. Niech fC
n
[a,b]. Wtedy x*[a,b] jest pierwiastkiem
n-
krotnym f wtedy i tylko wtedy gdy
f(x*)=f’(x*)=...=f
(n-1)
(x*)=0 i f
(n)
(x*)0.
2. Jeżeli x* jest pierwiastkiem n-krotnym f i f jest
odpowiednio wysokiej klasy to x* jest pierwiastkiem
pojedynczym funkcji
g(x)=f(x)/f’(x).
3. Jeżeli f jest ciągła w [a,b] i f(a)f(b)<0 to f ma
przynajmniej jeden pierwiastek w [a,b] (twierdzenie
Bolzano).
Ogólny schemat metod iteracyjnego znajdowania
zer funkcji
1. Przekształcamy równanie f(x)=0 do postaci
x=(x)
poprzez podstawienie
(x)=x-g(x)f(x)
gdzie g jest funkcją ciągłą i g0.
Punkt x* taki, że równanie jest spełnione nazywa się punktem stałym.
Często postać x=f(x) równania jest jego postacią „naturalną”; wtedy
mówimy o metodzie iteracji prostej (przykład z mechaniki kwantowej:
SCF).
2. Tworzymy ciąg kolejnych przybliżeń x
(0)
,x
(1)
,...,x
(p)
,... (w założeniu zbieżny do
x*) taki, że
x
(p+1)
=(x
(p)
)
gdzie x
(0)
jest przybliżeniem początkowym. Taka procedura jest nazywana
procedurą iteracyjną a funkcja funkcją iteracyjną.
3. Procedurę iteracyjną kończymy jeżeli kolejne przybliżenia x* różnią się
odpowiednio mało (zbieżność) lub wykonaliśmy maksymalną zadaną liczbę
kroków (brak zbieżności).
Twierdzenie o istnieniu punktu stałego:
Równania x=(x) posiada przynajmniej jedno rozwiązanie w przedziale
I=[a,b], jeżeli
(i) jest funkcją ciągłą w I,
(ii) (x)I dla wszystkich x I.
Twierdzenie o jednoznaczności punktu stałego:
Równanie x=(x) posiada co najwyżej jedno rozwiązanie w przedziale I jeżeli
pierwsza pochodna f jest w tym przedziale ograniczona w sensie
Lipschitza, tj. istnieje taka stała L, że dla każdego x
1
i x
2
z przedziału I
mamy
|’(x
1
)-’(x
2
)|L|x
1
-x
2
|, 0<L<1
Jeżeli spełnia warunki zawarte w obu twierdzeniach, to równanie x=(x)
ma jedno i tylko jedno rozwiązania w I (istnienie i jednoznaczność).
y
x
(0
)
x
x
(1
)
x
(2
)
y
x
(0
)
x
x
(1
)
x
(2
)
y
x
(0
)
x
x
(1
)
x
(2
)
y
x
(0
)
x
x
(1
)
x
(2
)
Zbieżność
jednostajna
(0<’(x)<1)
Zbieżność
oscylacyjna
(0>’(x)>-1)
Rozbieżność (|’(x)|
>1)
Metoda iteracyjna ma rząd zbieżności r, jeżeli
1
0
,
*
*
)
(
)
1
(
M
x
x
M
x
x
r
p
p
Numeryczne szacowanie rzędu zbieżności
)
1
(
)
(
)
(
)
1
(
log
log
p
p
p
p
x
x
x
x
r
Metoda iteracji prostej jest na ogół rzędu pierwszego.
dla odpowiednio dużych p.
Metoda Newtona (metoda Newtona-Raphsona, metoda
stycznych)
y
x
(0
)
x
x
(1
)
x
(2
)
)
(
)
(
)
(
)
1
(
)
0
(
)
0
(
)
0
(
)
0
(
)
0
(
)
0
(
)
0
(
)
0
(
'
'
*
)
(
'
)
*
(
)
(
)
*
(
*)
(
0
p
p
p
p
x
f
x
f
x
x
x
f
x
f
x
x
x
f
x
x
x
f
x
x
x
f
x
f
Metoda Newtona jest zawsze zbieżna dla funkcji wypukłych i
monotonicznych (f’(x)0 i f’’’(x)>0 dla każdego x)
Metoda Newtona jest zbieżna kwadratowo dla pierwiastków
pojedynczych a liniowo dla pierwiastków wielokrotnych.
Tłumiona metoda Newtona (pewniejsza zbieżność)
)
(
)
(
)
(
)
1
(
'
2
p
p
k
p
p
x
f
x
f
x
x
k jest najmniejszą liczbą całkowitą nieujemną taką, że
)
(
)
1
(
p
p
x
f
x
f
Zmodyfikowana metoda Newtona do znajdowania pierwiastków
wielokrotnych
)
(
)
(
)
(
)
1
(
'
p
p
p
p
x
f
x
f
r
x
x
jeżeli znamy rząd pierwiastka
(r).
)
(
)
(
)
(
)
(
2
)
(
2
)
(
)
(
)
1
(
'
''
'
'
p
p
p
p
p
p
p
p
x
f
x
f
x
f
x
f
x
f
x
f
x
x
jeżeli nie znamy rzędu
pierwiastka.
W tym przypadku oryginalne równanie f(x)=0 zastępujemy równaniem
f(x)/f’(x)=0.
Metoda siecznych
(nazywana również metodą regula falsi)
)
p
(
)
p
(
)
p
(
)
p
(
)
p
(
)
p
(
)
p
(
x
f
x
f
x
f
x
x
x
x
1
1
1
1
62
1
2
5
1
.
/
r
y
x
(0
)
x
x
(1
)
x
(2
)
Rząd zbieżności metody siecznych wynosi
Metoda siecznych nie musi być zawsze zbieżna.
Dla pierwiastków wielokrotnych f(x) zastępujemy przez
x
f
x
f
x
f
x
f
x
h
2
Metoda fałszywej linii (regula falsi)
(nazywana również uproszczoną metodą regula
falsi)
)
p
(
)
p
(
)
q
(
)
p
(
)
q
(
)
p
(
)
p
(
x
f
x
f
x
f
x
x
x
x
1
1
1
1
1. Start z x
(0)
i x
(1)
takich, że f(x
(0)
)f(x
(1)
)<0 (funkcja ma
różne znaki).
2. Do obliczenia następnego x stosujemy zmodyfikowany
wzór metody siecznych
gdzie q jest największą liczbą całkowitą nie większą niż p-2
taką, że f(x
(p)
)f(x
(q)
)<0 (tj. funkcja ma różne znaki w x
(p)
i x
(q)
a zatem pierwiastek musi zawierać się w przedziale [x
(p)
,x
(q)
]
jeżeli funkcja jest ciągła
Metoda ma gwarantowaną zbieżność dla funkcji ciągłych ale jej
rząd w ogólności wynosi 1 (wolna zbieżność).
Metoda Pegaza – ilustracja graficzna
y
x
(0)
x
x
(1)
x
(2)
f
(0)
f*
(0)
f
(1)
f
(1)
+f
(2)
f
(2)
)
(
)
(
)
(
)
(
)
(
f
f
f
f
*
f
2
1
2
0
0
Metoda Pegaza - algorytm
1. Startujemy jak w metodzie fałszywej linii z takich x(0) i x(1), że
f(x
(0)
)f(x
(1)
)<0.
2. Obliczamy punkt x
(2)
zgodnie z algorytmem metody siecznych.
Jeżeli |f(x(2))|<, kończymy proces iteracyjny.
3. Jeżeli f(x
(1)
)f(x
(2)
)<0 (pierwiastek leży pomiędzy x
(1)
i x
(2)
)
wstawiamy x
(0)
=x
(1)
i x
(1)
=x
(2)
i przechodzimy do następnego
kroku.
4. Jeżeli f(x
(0)
)f(x
(2)
)<0 (pierwiastek leży pomiędzy x
(0)
i x
(2)
)
zastępujemy we wzorze metody siecznych f
(0)
przez f*
(0)
=f
(0)
f
(2)
/
(f
(1)
+f
(2)
), wyliczamy x
(2)
jeszcze raz i wstawiamy x
(1)
=x
(2)
.
5. Sprawdzamy, czy |x
(2)
-x
(1)
|<. Jeżeli tak, to za rozwiązanie
przyjmujemy x
(1)
, jeżeli f(x
(1)
)<f(x
(2)
) a x
(2)
w przeciwnym
przypadku.
Rząd zbieżności metody Pegaza wynosi 1.642.
Metoda połowienia (bisekcji)
y
x
(0)
x
x
(1)
x
(2)
1. Startujemy z takich x
(0)
i x
(1)
, że f(x
(0)
)f(x
(1)
)<0.
2. Obliczamy x
(2)
=(x
(0)
+x
(1)
)/2. Jeżeli |f(x
(2)
)|< kończymy proces
iteracyjny.
3. Jeżeli f(x
(0)
)f(x
(2)
)<0 wstawiamy x
(1)
=x
(2)
, w przeciwnym
przypadku x
(0)
=x
(1)
, x
(1)
=x
(2)
.
Metoda bisekcji jest rzędu pierwszego.
Inne metody znajdowania zer
1. Metoda Andersona-Björcka (rząd zbieżności od 1.682
do 1.710, inkluzyjna) – jak metoda Pegaza ale z inną
formułą obliczania f*
(0)
; f*
(0)
=f
(0)
(1-f
(2)
/f
(1)
) jeżeli 1-
f
(2)
/f
(2)
>0 i f
(0)
/2 w przeciwnym przypadku.
2. Metoda Kinga (rząd zbieżności od 1.710 do 1.732,
inkluzyjna) – w odróżnieniu od metody Pegaza po
każdej iteracji metody siecznych następuje iteracja z
modyfikacją f
(0)
.
3. Metoda Andersona-Björcka-Kinga (rząd zbieżności od
1.710 do 1.732, inkluzyjna) – formuła Andersona-
Björcka obliczania f*
(0)
ze schematem iteracyjnym
Kinga.
4. Metoda Illinois (rząd zbieżności 1.442, inkluzyjna) –
jak metoda Pegaza ale f*
(0)
=f
(0)
/2.
Znajdowanie wszystkich pierwiastków
równań algebraicznych (wielomianów)
n
n
x
x
a
x
a
x
a
a
)
x
(
P
)
x
(
f
2
2
1
0
Metoda Mullera
• Lokalizujemy pierwiastek o najmniejszym module (x*
1
).
• Po znalezieniu jego przybliżonej wartości dzielimy
wielomian przez (x-x*
1
), ignorujemy resztę z dzielenia a
następnie szukamy następnego pierwiastka aż do rzędu n.
• Po znalezieniu przybliżeń wszystkich pierwiastków
porządkujemy je od nowa od wartości najmniejszej do
największej i powtarzamy cykl (procedura Wilkinsona).
• Przybliżenia poszczególnych pierwiastków poprawiamy
stosując jakąkolwiek metodę szybko zbieżną (np. Newtona).
Do efektywnego znajdowania dobrych przybliżeń
pierwiastków bardzo dobrze nadaje się metoda
iteracji Mullera, w której wielomian interpoluje się
odcinkami paraboli. Pozwala to na lokalizację
zarówno pierwiastków rzeczywistych jak i
zespolonych.