Metody Numeryczne
Wykład 2
Wyznaczanie zer funkcji
Iwona Wróbel
[e-mail]
Metody Numeryczne IL, Wykład 2  p.1/37
Program
Sformułowanie problemu
Metoda Newtona
Metoda siecznych
Metoda Halley a
Metoda bisekcji
Warunki stopu
Zbieżność metod iteracyjnych
Pewne zastosowania
Metody Numeryczne IL, Wykład 2  p.2/37
Niech f : R R.
Problem: znalez
ć ą " R, takie, że
f(ą) = 0.
Uzasadnienie:
W praktyce rzadko mamy do czynienia z funkcjami, których miejsca
zerowe da się znalez
ć używając skończonej liczby operacji
arytmetycznych.
W pewnych przypadkach (w obecności błędów zaokrągleń) obliczenia
numeryczne dają dokładniejsze wyniki niż obliczenia analityczne.
Mogą też wymagać mniejszej liczby operacji arytmetycznych.
Metody iteracyjne: startując z danego przybliżenia początkowego x0
tworzymy ciąg kolejnych przybliżeń {xk}, taki, że xk ą przy k ".
Metody Numeryczne IL, Wykład 2  p.3/37
Metoda Newtona (stycznych)
Niech f : R R będzie funkcją różniczkowalną oraz niech x0 " R
będzie danym przybliżeniem początkowym, takim, że f (x0) = 0.

Idea metody Newtona (k-ty krok):
W punkcie (xk, f(xk)) prowadzimy styczną p(x) do wykresu funkcji f.
Kolejne przybliżenie xk+1 jest miejscem zerowym tej stycznej.
Metody Numeryczne IL, Wykład 2  p.4/37
3
2.5
2
1.5
1
0.5
0
-0.5
-1
-1.5 -1 -0.5 0 0.5 1 1.5 2 2.5 3 3.5
Metody Numeryczne IL, Wykład 2  p.5/37
3
2.5
2
1.5
1
0.5
0
-0.5
-1
-1.5 -1 -0.5 0 0.5 1 1.5 2 2.5 3 3.5
Metody Numeryczne IL, Wykład 2  p.6/37
3
2.5
2
1.5
1
0.5
0
-0.5
-1
-1.5 -1 -0.5 0 0.5 1 1.5 2 2.5 3 3.5
Metody Numeryczne IL, Wykład 2  p.7/37
3
2.5
2
1.5
1
0.5
0
-0.5
-1
-1.5 -1 -0.5 0 0.5 1 1.5 2 2.5 3 3.5
Metody Numeryczne IL, Wykład 2  p.8/37
3
2.5
2
1.5
1
0.5
0
-0.5
-1
-1.5 -1 -0.5 0 0.5 1 1.5 2 2.5 3 3.5
Metody Numeryczne IL, Wykład 2  p.9/37
Styczna p(x) do wykresu funkcji f w punkcie xk:
p(x) = f(xk) + f (xk)(x - xk).
Kolejne przybliżenie xk+1 obliczamy ze wzoru:
0 = f(xk) + f (xk)(xk+1 - xk)
i dostajemy
f(xk)
xk+1 = xk - for k = 0, 1, . . . .
f (xk)
Uwaga. Metoda nie zadziała, gdy f (xk) = 0 dla pewnego k. Dzieje się
tak, gdy styczna w k-tym kroku jest równoległa do osi OX.
Metody Numeryczne IL, Wykład 2  p.10/37
Metoda siecznych
Niech f : R R oraz niech x0, x1 " R będą danymi przybliżeniami
początkowymi, takimi, że f(x0) = f(x1).

Idea metody siecznych:
Przez punkty (xk-1, f(xk-1)) oraz (xk, f(xk)) prowadzimy sieczną.
Kolejne przybliżenie xk+1 jest miejscem zerowym tej siecznej.
Metody Numeryczne IL, Wykład 2  p.11/37
3
2.5
2
1.5
1
0.5
0
-0.5
-1
-1.5 -1 -0.5 0 0.5 1 1.5 2 2.5 3 3.5
Metody Numeryczne IL, Wykład 2  p.12/37
3
2.5
2
1.5
1
0.5
0
-0.5
-1
-1.5 -1 -0.5 0 0.5 1 1.5 2 2.5 3 3.5
Metody Numeryczne IL, Wykład 2  p.13/37
3
2.5
2
1.5
1
0.5
0
-0.5
-1
-1.5 -1 -0.5 0 0.5 1 1.5 2 2.5 3 3.5
Metody Numeryczne IL, Wykład 2  p.14/37
Metodę siecznych można wyprowadzić z metody Newtona zastępując
f(xk)-f(xk-1)
f (xk) ilorazem różnicowym . Dostajemy
xk-xk-1
xk - xk-1
xk+1 = xk - f(xk) dla k = 0, 1, . . . .
f(xk) - f(xk-1)
Uwaga. Brak konieczności obliczania pochodnych zmniejsza koszt
każdego kroku.
Pytanie: co tracimy?
Odpowiedz
: prędkość. W ogólnym przypadku metoda siecznych jest
wolniejsza niż metoda Newtona  wymaga większej liczby kroków do
osiągnięcia tej samej dokładności.
Uwaga. Nie musi to oznaczać, że czas wykonania metody Newtona
jest mniejszy.
Metody Numeryczne IL, Wykład 2  p.15/37
Metoda Halley a
Niech f : R R będzie klasy C2(R) oraz niech x0 " R będzie danym
przybliżeniem początkowym.
Wykorzystując rozwinięcie funkcji f(x) w szereg Taylora w otoczeniu
punktu xk otrzymujemy przybliżenie p(x) funkcji f(x):
1
p(x) = f(xk) + f (xk)(x - xk) + f (xk)(x - xk)2.
2
Następnie przyjmujemy:
1
0 = f(xk) + f (xk)(xk+1 - xk) + f (xk)(xk+1 - xk)2.
2
Metody Numeryczne IL, Wykład 2  p.16/37
Metoda Halley a
Po przekształceniu:
f(xk)
xk+1 = xk - .
1
f (xk) + f (xk)(xk+1 - xk)
2
Wartość xk+1 po prawej stronie przybliżamy metodą Newtona
otrzymując wzór określający metodę Halley a:
f(xk)
xk+1 = xk - dla k = 0, 1, . . . .
f(xk)
(f (xk) - f (xk)2f (xk))
Idea metody Halley a:
Kolejne przybliżenie xk+1 jest miejscem zerowym hiperboli
przybliżającej funkcję f(x) w punkcie xk.
Metody Numeryczne IL, Wykład 2  p.17/37
Warunki stopu
|xk+1 - xk| < �,
|xk+1 - xk| < �|xk|,
(warunek Gill a) |xk+1 - xk| < �|xk| + �,
|f(xk)| < � (stosować ostrożnie; można znalez
ć nieistniejące
miejsce zerowe),
gdzie � i � określają dokładność (przykładowo � = 10-10 i � = 10-20
lub � = 10-13 i � = 10-25).
Metody Numeryczne IL, Wykład 2  p.18/37
Metoda bisekcji
Twierdzenie. Niech [a, b] �" R oraz niech f będzie funkcją ciągłą w
przedziale [a, b] taką, że f(a)f(b) < 0. Wtedy istnieje co najmniej jedno
ą, (a < ą < b) takie, że f(ą) = 0.
Algorytm:
1) przyjmujemy: a0 = a, b0 = b, k = 0,
2) dzielimy przedział [ak, bk] na połowę punktem t = (a + b)/2,
3) jeśli f(ak)f(t) < 0, to f ma zero w [ak, t] i podstawiamy:
ak+1 = ak, bk+1 = t,
4) jeśli f(ak)f(t) > 0, to f ma zero w [t, bk] i podstawiamy: ak+1 = t,
bk+1 = bk,
5) jeśli f(ak)f(t) = 0, to f(t) = 0 i kończymy obliczenia,
6) jeśli bk+1 - ak+1 < �, to kończymy obliczenia,
7) k = k + 1, wróć do 2
Metody Numeryczne IL, Wykład 2  p.19/37
8
6
4
2
a
b
0
-2
-4
-5 -4 -3 -2 -1 0 1 2 3 4 5
Metody Numeryczne IL, Wykład 2  p.20/37
8
6
4
2
a (a+b)/2
b
0
-2
-4
-5 -4 -3 -2 -1 0 1 2 3 4 5
Metody Numeryczne IL, Wykład 2  p.21/37
8
6
4
2
a (a+b)/2
b
0
-2
-4
-5 -4 -3 -2 -1 0 1 2 3 4 5
Metody Numeryczne IL, Wykład 2  p.22/37
8
6
4
2
a (a+b)/2
a (a+b)/2
b
b
0
-2
-4
-5 -4 -3 -2 -1 0 1 2 3 4 5
Metody Numeryczne IL, Wykład 2  p.23/37
8
6
4
2
a (a+b)/2
b
0
-2
-4
-5 -4 -3 -2 -1 0 1 2 3 4 5
Metody Numeryczne IL, Wykład 2  p.24/37
8
6
4
2
a (a+b)/2
a (a+b)/2
b
b
0
-2
-4
-5 -4 -3 -2 -1 0 1 2 3 4 5
Metody Numeryczne IL, Wykład 2  p.25/37
8
6
4
2
a (a+b)/2
b
0
-2
-4
-5 -4 -3 -2 -1 0 1 2 3 4 5
Metody Numeryczne IL, Wykład 2  p.26/37
8
6
4
2
a (a+b)/2
a (a+b)/2
b
b
0
-2
-4
-5 -4 -3 -2 -1 0 1 2 3 4 5
Metody Numeryczne IL, Wykład 2  p.27/37
8
6
4
2
a (a+b)/2
b
0
-2
-4
-5 -4 -3 -2 -1 0 1 2 3 4 5
Metody Numeryczne IL, Wykład 2  p.28/37
Metoda bisekcji
Uwagi implementacyjne:
punkt środkowy t lepiej jest obliczać jako t = a + (b - a)/2, a nie
t = (a + b)/2 (w obliczeniach numerycznych lepiej jest obliczać
nową wielkość dodając do niej małą poprawkę),
zmianę znaku wartości funkcji lepiej sprawdzić za pomocą
nierówności sgn f(ak) = sgn f(t), a nie f(ak)f(t) < 0, żeby

uniknąć mnożenia wartości funkcji i ewentualnego nadmiaru lub
niedomiaru.
Metody Numeryczne IL, Wykład 2  p.29/37
Metoda bisekcji
W metodzie bisekcji można z góry określić maksymalną liczbę iteracji
potrzebną do uzyskania zadanej dokładności �.
W k-tym kroku mamy:
1
bk - ak = (bk-1 - ak-1) =
2
Metody Numeryczne IL, Wykład 2  p.30/37
Metoda bisekcji
W metodzie bisekcji można z góry określić maksymalną liczbę iteracji
potrzebną do uzyskania zadanej dokładności �.
W k-tym kroku mamy:
1 1
bk - ak = (bk-1 - ak-1) = (bk-2 - ak-2)
2 22
Metody Numeryczne IL, Wykład 2  p.30/37
Metoda bisekcji
W metodzie bisekcji można z góry określić maksymalną liczbę iteracji
potrzebną do uzyskania zadanej dokładności �.
W k-tym kroku mamy:
1 1
bk - ak = (bk-1 - ak-1) = (bk-2 - ak-2)
2 22
1
= . . . = (b0 - a0)
2k
Metody Numeryczne IL, Wykład 2  p.30/37
Metoda bisekcji
W metodzie bisekcji można z góry określić maksymalną liczbę iteracji
potrzebną do uzyskania zadanej dokładności �.
W k-tym kroku mamy:
1 1
bk - ak = (bk-1 - ak-1) = (bk-2 - ak-2)
2 22
1
= . . . = (b0 - a0)
2k
Aby określić, ile kroków potrzeba do znalezienia pierwiastka z
dokładnością �, wystarczy rozwiązać nierówność:
1
(b - a) d" �.
2k
Metody Numeryczne IL, Wykład 2  p.30/37
Metoda bisekcji
W metodzie bisekcji można z góry określić maksymalną liczbę iteracji
potrzebną do uzyskania zadanej dokładności �.
W k-tym kroku mamy:
1 1
bk - ak = (bk-1 - ak-1) = (bk-2 - ak-2)
2 22
1
= . . . = (b0 - a0)
2k
Aby określić, ile kroków potrzeba do znalezienia pierwiastka z
dokładnością �, wystarczy rozwiązać nierówność:
1
(b - a) d" �.
2k
Dostajemy:
b - a
k e" log2 .
�
Metody Numeryczne IL, Wykład 2  p.30/37
Krotność miejsc zerowych
Liczbę ą nazywamy m-krotnym pierwiastkiem równania f(x) = 0, gdy
f(x) = (x - ą)mg(x),
przy czym g(ą) = 0.

Jeżeli m = 1, to ą jest pierwiastkiem pojedynczym.
Jeżeli m > 1, to ą jest pierwiastkiem wielokrotnym.
Metody Numeryczne IL, Wykład 2  p.31/37
Zbieżność metod iteracyjnych
Jak szybko xk ą przy k "?
Definicja. Wykładnikiem zbieżności metody iteracyjnej nazywamy
największą liczbę p e" 1 taką, że
|ek+1| d" C|ek|p
gdzie ek = xk - ą jest błędem w k-tym kroku, a C pewną stałą
(nieujemną).
Metody Numeryczne IL, Wykład 2  p.32/37
Zbieżność metod iteracyjnych
Jak szybko xk ą przy k "?
Definicja. Wykładnikiem zbieżności metody iteracyjnej nazywamy
największą liczbę p e" 1 taką, że
|ek+1| d" C|ek|p
gdzie ek = xk - ą jest błędem w k-tym kroku, a C pewną stałą
(nieujemną).
Uwaga. Im większa wartość p, tym szybciej metoda jest zbieżna.
Metody Numeryczne IL, Wykład 2  p.32/37
Wykładnik zbieżności
Metody Numeryczne IL, Wykład 2  p.33/37
Wykładnik zbieżności
Metoda Newtona: p = 2 (zbieżność kwadratowa)
Metody Numeryczne IL, Wykład 2  p.33/37
Wykładnik zbieżności
Metoda Newtona: p = 2 (zbieżność kwadratowa)
"
1+ 5
Metoda siecznych: p = H" 1.61 (zbieżność ponadliniowa)
2
Metody Numeryczne IL, Wykład 2  p.33/37
Wykładnik zbieżności
Metoda Newtona: p = 2 (zbieżność kwadratowa)
"
1+ 5
Metoda siecznych: p = H" 1.61 (zbieżność ponadliniowa)
2
Metoda Halley a: p = 3 (zbieżność sześcienna)
Metody Numeryczne IL, Wykład 2  p.33/37
Wykładnik zbieżności
Metoda Newtona: p = 2 (zbieżność kwadratowa)
"
1+ 5
Metoda siecznych: p = H" 1.61 (zbieżność ponadliniowa)
2
Metoda Halley a: p = 3 (zbieżność sześcienna)
Uwaga!!! Powyższe wartości są prawdziwe jedynie dla zer
jednokrotnych! W przypadku miejsc zerowych wielokrotnych
wyżej wymienione metody są wolniej zbieżne.
Metody Numeryczne IL, Wykład 2  p.33/37
Wykładnik zbieżności
Metoda Newtona: p = 2 (zbieżność kwadratowa)
"
1+ 5
Metoda siecznych: p = H" 1.61 (zbieżność ponadliniowa)
2
Metoda Halley a: p = 3 (zbieżność sześcienna)
Uwaga!!! Powyższe wartości są prawdziwe jedynie dla zer
jednokrotnych! W przypadku miejsc zerowych wielokrotnych
wyżej wymienione metody są wolniej zbieżne.
Metoda bisekcji: p = 1 (zbieżność liniowa)
Uwaga. Wykładnik zbieżności metody bisekcji nie zależy od krotności
zer. Dlaczego?
Metody Numeryczne IL, Wykład 2  p.33/37
Przykład
Metoda Newtona:
f(xk)
xk+1 = xk - dla k = 0, 1, . . . .
f (xk)
Wykładnik zbieżności:
|ek+1| d" C|ek|p,
gdzie ek = xk - ą, C - stała.
Metody Numeryczne IL, Wykład 2  p.34/37
Przykład
Metoda Newtona:
f(xk)
xk+1 = xk - dla k = 0, 1, . . . .
f (xk)
Wykładnik zbieżności:
|ek+1| d" C|ek|p,
gdzie ek = xk - ą, C - stała.
Dla funkcji f(x) = (x - 1)2 otrzymujemy:
(xk - 1)2 xk + 1
xk+1 = xk - =
2(xk - 1) 2
Metody Numeryczne IL, Wykład 2  p.34/37
Przykład
Metoda Newtona:
f(xk)
xk+1 = xk - dla k = 0, 1, . . . .
f (xk)
Wykładnik zbieżności:
|ek+1| d" C|ek|p,
gdzie ek = xk - ą, C - stała.
Dla funkcji f(x) = (x - 1)2 otrzymujemy:
(xk - 1)2 xk + 1
xk+1 = xk - =
2(xk - 1) 2
oraz
xk + 1 xk - 1 ek
ek+1 = xk+1 - 1 = - 1 = = ,
2 2 2
co oznacza, że zbieżność jest liniowa (wykładnik zbieżności wynosi 1).
Metody Numeryczne IL, Wykład 2  p.34/37
Pewne zastosowania
"
1. Jak obliczyć a, gdzie a > 0?
Metody Numeryczne IL, Wykład 2  p.35/37
Pewne zastosowania
"
1. Jak obliczyć a, gdzie a > 0?
(szybko, z dużą dokładnością i bez obliczania pierwiastków)
Metody Numeryczne IL, Wykład 2  p.35/37
Pewne zastosowania
"
1. Jak obliczyć a, gdzie a > 0?
(szybko, z dużą dokładnością i bez obliczania pierwiastków)
"
Stosujemy metodę Newtona dla funkcji, której pierwiastkiem jest a, a
mianowicie:
f(x) = x2 - a.
Metody Numeryczne IL, Wykład 2  p.35/37
Pewne zastosowania
"
1. Jak obliczyć a, gdzie a > 0?
(szybko, z dużą dokładnością i bez obliczania pierwiastków)
"
Stosujemy metodę Newtona dla funkcji, której pierwiastkiem jest a, a
mianowicie:
f(x) = x2 - a.
Mamy
f(xk) x2 - a x2 + a
k k
xk+1 = xk - = xk - = ,
f (xk) 2xk 2xk
Metody Numeryczne IL, Wykład 2  p.35/37
Pewne zastosowania
"
1. Jak obliczyć a, gdzie a > 0?
(szybko, z dużą dokładnością i bez obliczania pierwiastków)
"
Stosujemy metodę Newtona dla funkcji, której pierwiastkiem jest a, a
mianowicie:
f(x) = x2 - a.
Mamy
f(xk) x2 - a x2 + a
k k
xk+1 = xk - = xk - = ,
f (xk) 2xk 2xk
a wzór iteracyjny ma postać:
1 a
xk+1 = xk + dla k = 0, 1, . . . .
2 xk
Metody Numeryczne IL, Wykład 2  p.35/37
Pewne zastosowania
"
1. Jak obliczyć a, gdzie a > 0?
(szybko, z dużą dokładnością i bez obliczania pierwiastków)
"
Stosujemy metodę Newtona dla funkcji, której pierwiastkiem jest a, a
mianowicie:
f(x) = x2 - a.
Mamy
f(xk) x2 - a x2 + a
k k
xk+1 = xk - = xk - = ,
f (xk) 2xk 2xk
a wzór iteracyjny ma postać:
1 a
xk+1 = xk + dla k = 0, 1, . . . .
2 xk
Metoda nie zadziała, gdy przybliżeniem pocz"
ątkowym jest x0 = 0. Dla
"
innych przybliże" iteracja zbiega do a or - a. Dla jakich x0 metoda
ń
jest zbieżna do a?
Metody Numeryczne IL, Wykład 2  p.35/37
Uwaga. stosując metodę Newtona dla funkcji
f(x) = xp - a,
"
p
otrzymamy algorytm obliczania a.
Metody Numeryczne IL, Wykład 2  p.36/37
Uwaga. stosując metodę Newtona dla funkcji
f(x) = xp - a,
"
p
otrzymamy algorytm obliczania a.
2. Jak obliczyć a-1 (dla a = 0) bez dzielenia?

Metody Numeryczne IL, Wykład 2  p.36/37
Metoda Newtona nie zawsze jest zbieżna. Jeżeli jednak
1) f jest funkcją klasy C2([a, b]) ,
2) f(a) f(b) < 0,
3) f i f nie zmieniają znaku w [a, b],
to przyjmując x0 takie, że f(x0) f (x0) > 0 zapewniamy zbieżność tej
metody.
Metoda siecznych, podobnie jak metoda stycznych, nie zawsze jest
zbieżna. Jeżeli jednak
1) f jest funkcją klasy C2([a, b]) ,
2) f(a) f(b) < 0,
3) f i f nie zmieniają znaku w [a, b],
to przyjmując x0 i x1 takie, że f(x0)f (x0) > 0 i f(x1)f (x1) > 0
zapewniamy zbieżność metody.
Metody Numeryczne IL, Wykład 2  p.37/37