Rozwiązywanie numeryczne równań nieliniowych
Wybrane metody znajdowania miejsc zerowych
funkcji jednej zmiennej
1. Metoda połowienia przedziału (bisekcji)
2. Metoda iteracji prostej
3. Metoda Newtona (stycznych)
4. Metoda Halley a
Metoda połowienia przedziału (bisekcji)
Z: f(x)  funkcja ciągła w przedziale domkniętym [a, b]
f (a) Å" f (b) < 0
Sz: pierwiastek f(x) = 0 z dokładnością eps
f (x)
f (x1) < 0
x1
a + b
x1 =
× × x
2
x2
a f (x2) > 0
b
jeżeli xn - xn-1 < eps xn - przybliżona wartość pierwiastka
Metoda iteracji prostej
Z: f(x)  funkcja ciągła w przedziale domkniętym [a, b]
f (a) Å" f (b) < 0
Sz: pierwiastek f(x) = 0 z dokładnością eps
f (x) = 0 x = g(x)
g(x)
f (x) x

x x
a a
b b
x"
x"
Zamiana równania f(x) = 0 na x = g(x) nie zawsze jest procesem jednoznacznym !
Å„Å‚
x = x3 - 5
ôÅ‚
ôÅ‚x 3
x3 - x - 5 = 0 = x + 5
òÅ‚
5
ôÅ‚
x =
ôÅ‚
ół x2 -1
Zbieżność metody iteracji prostej
"xk = x *-xk xk = x *-"xk
"xk +1 = x *-xk +1 xk +1 = x *-"xk +1 = g(xk )
2
g(xk ) = g(x*) -"xk g (x*) + ...
2
x *-"xk +1 = g(x*) - "xk g (x*) x* = g(x*)
2
"xk +1 = g (x*)"xk
- zbieżność liniowa
2
g (x*) <1 - warunek zbieżności
Metoda Newtona (stycznych)
Z: f(x)  funkcja ciągła w przedziale domkniętym [a, b]
f (a) Å" f (b) < 0
Sz: pierwiastek f(x) = 0 z dokładnością eps
f (x)
x
a x2 = x1
x3
b
xk +1 = xk + hk
x = b  pierwsze przybliżenie
Warunki zakończenia obliczeń:
jeżeli
f (xn) Å" f (xn - eps) < 0 xn - przybliżona wartość pierwiastka
jeżeli xn - xn-1 < eps xn - przybliżona wartość pierwiastka
Wzór iteracyjny metody Newtona (stycznych)
f (xk )
xk +1 = xk -
2
f (xk )
Wzór iteracyjny metody metoda Halley a
2
2 f (xk ) f (xk )
xk +1 = xk -
2 2 2
2 f (xk )2 - f (xk ) f (xk )
Możliwe przypadki
2 2
f (x)
Z: nie zmienia znaku w przedziale [a,b]
f (a) > 0 f (a) < 0
2 2 2 2
f (a) > 0 f (a) < 0
f (x) f (x)
x x
2 2
f (a) Å" f (a) > 0
a a
b b
a - pierwsze przybliżenie
f (b) >0 f (b) < 0
f (x) f (x)
2 2 2 2
f (b) >0 f (b) < 0
2 2
f (b) Å" f (b) > 0
x x
a a
b b
b - pierwsze przybliżenie