Wybrane metody przybliżonego wyznaczania rozwiązań (pierwiastków)
równań algebraicznych w postaci
f (x)
1
f( )⋅ jest funkcją rzeczywistą zmiennej rzeczywistej x, f( )⋅:R∋ x→ f( ) x R
∈ .
Rozwiązanie składa się z dwóch etapów:
- wyboru przedziału izolacji; przedziału, w którym funkcja ciągła, na końcach tego przedziału ma różne znaki, czyli f(a)·f(b) < 0,
- zastosowania algorytmu iteracyjnego do wyszukiwania właściwego rozwiązania.
Metody szukania przedziału [a, b]:
- tabelka,
- oszacowanie przedziału, w którym
f1(x) = f2(x)
2
Warunki gwarantujące znalezienie pierwiastka: 1. różne znaki funkcji na końcach przedziału f ( ) a ⋅ f ( )
b <0,
2. ciągłość funkcji w przedziale [a, b], 3. istnienie pierwszej pochodnej, pochodna nie zmienia znaku w całym przedziale, funkcja jest gładka i monotoniczna,
4. druga pochodna ma stały znak w całym przedziale, tj. nie ma punktów przegięcia, przebieg funkcji albo wklęsły, albo wypukły.
3
Zakończenie procesu poszukiwania rozwiązania:
-
f ( x
, δ - zależy od poszukiwanej wartości, ( k+1 ) <δ
- zbieżność iteracji, czyli x +
ε - zależy od poszukiwanej wartości,
1 − x
<ε ,
( k
)
( k )
- iteracja trwa zbyt długo, warunek k > kmax, koniec obliczeń,
- wartości f ( x +
nieprawidłowy algorytm.
1
> f(x ,
( k
)
( k )
Wybór wartości x .
( 0 )
Metody: bisekcji, regula falsi, siecznych, stycznych, iteracji prostej.
4
Metoda bisekcji – metoda połowienia f (x) = 0
(1)
Zakłada się, że występująca w równaniu (1) funkcja f ( )⋅ jest ciągła na zadanym przedziale
[ a, ] b i spełnia w punktach krańcowych warunek f ( a)⋅ f ( b) < 0
Należy znaleźć przedział [ a, ]
b
Ustalić liczby ε, δ (większe od błędu zaokrąglenia wynikającego ze skończonej precyzji zapisu liczb w komputerze) 5
Ustalamy, że a = a
, b = b
( 0 )
( 0 )
a
+ b
( 0 )
( 0 )
x( =
0 )
2
Sprawdzamy, czy
f ( x
)
0
< δ ,
(
)
0 =
jeżeli TAK, to x
jest rozwiązaniem
x
x *
(
)
( 0 )
6
jeżeli NIE, to sprawdzamy, czy przedział [a, x
] spełnia warunek f ( a)⋅ f ( x
,
(
)
<
0 )
0
( 0 )
jeżeli TAK, to a = a
,
x
= b
( 1 )
( 0 )
( 1 )
jeżeli NIE, to x
= a , b = b
( 0 )
( 1 )
( 1 )
Następnie
a
+ b
( 1 )
( 1 )
x
=
( 1 )
2
Sprawdzamy, czy
f ( x
)
1
< δ ,
( )
7
jest rozwiązaniem
x 1 = x*
( 1 )
( )
jeżeli NIE, to sprawdzamy, czy przedział [ a
, x
]
( 1 )
( 1 )
spełnia warunek f ( a
f x
,
( )
⋅
( )
<
1 )
( ) 0
1
jeżeli TAK, to a
= a , x = b
( 1 )
( 2 )
( 1 )
( 2 )
jeżeli NIE, to x
= a , b = b
( 1 )
( 2 )
( 1 )
( 2 )
Następnie
a
+ b
( 2 )
( 2 )
x
=
( 2 )
2
8
f ( x
)
2
< δ ,
(
)
jeżeli TAK, to x
jest rozwiązaniem
( 2 )
x
.
2 = *
x
( )
Jeżeli nie, to sprawdzamy …. itd.
Algorytm
a
+ b
( k )
( k )
x
=
gdzie k = 0, 1, 2, 3, …..
( k )
2
=
Zakończenie obliczeń
f ( x
)
wtedy
x
x *
( k )
< δ
( k )
9
f(x)
a
+ b
0 =
(0)
(0)
f ( x
)
x
x *
0
< δ
(
x
=
,
(
)
(
)
0)
2
a
+ b
x 1 = x*
( 1 )
( 1 )
x
=
f ( x
)
( )
1
< δ ,
( )
( 1 )
2
f(b)
a
b
(2)
(2)
a
b
(1)
(1)
a
b
a
x
(0)
b(0)
x(1) x
x
(3)
(0)
f(a)
│ f ( x )│ < δ
x
= x*
(3)
(3)
10
START
CZYTAJ: a, b, δ
f (x) = 0
k = 0
x (k) = (a+b)/2
TAK
│f (x (k) )│<δ
x* = x (k)
NIE
NIE
STOP
f (a)·f (x (k)) < 0
TAK
a = x (k)
b = x (k)
k = k + 1
11
3
x − 2 x − 6 = 0
12