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