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 fC

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 g0.
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.