Metody Numeryczne
Wykład 2
Iwona Wróbel
[e-mail]
Metody Numeryczne IL, Wykład 2  p.1/15
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/15
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/15
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/15
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/15
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/15
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/15
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/15
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/15
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/15
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/15
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/15
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/15
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/15
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/15