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
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)
Sz: pierwiastek f(x) = 0 z dokładnością eps
a
x
b
)
(x
f
×
×
2
x
1
x
2
1
b
a
x
+
=
0
)
(
1
<
x
f
0
)
(
2
>
x
f
n
n
n
x
eps
x
x
→
<
−
−1
jeżeli
- przybliżona wartość pierwiastka
Z:
f(x) – funkcja ciągła w przedziale domkniętym [a, b]
0
)
(
)
(
<
⋅ b
f
a
f
Metoda iteracji prostej
)
(
0
)
(
x
g
x
x
f
=
→
=
a
x
b
)
(x
f
∗
x
→
a
x
b
)
(x
g
∗
x
x
Zamiana równania f(x) = 0 na x = g(x) nie zawsze jest procesem jednoznacznym !
−
=
+
=
−
=
→
=
−
−
1
5
5
5
0
5
2
3
3
3
x
x
x
x
x
x
x
x
Sz: pierwiastek f(x) = 0 z dokładnością eps
Z: f(x) – funkcja ciągła w przedziale domkniętym [a, b]
0
)
(
)
(
<
⋅ b
f
a
f
Zbieżność metody iteracji prostej
*
*
k
k
k
k
x
x
x
x
x
x
∆ =
− →
=
−∆
1
1
1
1
*
*
( )
k
k
k
k
k
x
x
x
x
x
x
g x
+
+
+
+
∆
=
−
→
=
−∆
=
( )
( *)
( *) ...
k
k
g x
g x
x g x
′
=
− ∆
+
1
*
( *)
( *)
k
k
x
x
g x
x g x
+
′
−∆
=
− ∆
1
( *)
k
k
x
g x
x
+
′
∆
=
∆
− zbieżność liniowa
*
( *)
x
g x
=
( *)
1
g x
′
<
− warunek zbieżności
n
n
n
x
eps
x
x
→
<
−
−1
jeżeli
- przybliżona wartość pierwiastka
Metoda Newtona (stycznych)
a
x
b
)
(x
f
1
x
=
2
x
3
x
x = b – pierwsze przybliżenie
Z: f(x) – funkcja ciągła w przedziale domkniętym [a, b]
0
)
(
)
(
<
⋅ b
f
a
f
Sz: pierwiastek f(x) = 0 z dokładnością eps
k
k
k
h
x
x
+
=
+1
n
n
n
x
eps
x
f
x
f
→
<
−
⋅
0
)
(
)
(
jeżeli
- przybliżona wartość pierwiastka
Warunki zakończenia obliczeń:
Wzór iteracyjny metody Newtona (stycznych)
)
(
)
(
1
k
k
k
k
x
f
x
f
x
x
′
−
=
+
)
(
)
(
)
(
2
)
(
)
(
2
2
1
k
k
k
k
k
k
k
x
f
x
f
x
f
x
f
x
f
x
x
′′
−
′
′
−
=
+
Wzór iteracyjny metody metoda Halley’a
Możliwe przypadki
0
)
(
0
)
(
>
′′
>
a
f
a
f
0
)
(
0
)
(
<
′′
<
a
f
a
f
a
x
b
)
(x
f
a
x
b
)
(x
f
0
)
(
0
)
(
>
′′
>
b
f
b
f
0
)
(
0
)
(
<
′′
<
b
f
b
f
a
x
b
)
(x
f
a
x
b
)
(x
f
0
)
(
)
(
>
′′
⋅
a
f
a
f
0
)
(
)
(
>
′′
⋅
b
f
b
f
a - pierwsze przybliżenie
b - pierwsze przybliżenie
Z: nie zmienia znaku w przedziale [a,b]
)
(x
f ′′