Wybrane metody przybliżonego
wyznaczania rozwiązań (pierwiastków)
równań algebraicznych
w postaci f (x)
Wykład czwarty
EiT, sem. 2, 2014/2015
1
f(x) = 0
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 <�d� , � - zależy od poszukiwanej wartości,
( k+�1)
- zbieżność iteracji, czyli x -� x <� e�, � - zależy od poszukiwanej wartości,
( k+�1) ( k )
- iteracja trwa zbyt długo, warunek k > kmax, koniec obliczeń,
- wartości f ( x >� f ( x , nieprawidłowy algorytm.
( k+�1) ( k )
x( 0 ).
Wybór wartości
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 znalez
ć przedział [�a,b]�
Ustalić liczby �, � (większe od błędu zaokrąglenia
wynikającego ze skończonej precyzji zapisu liczb w komputerze)
5
Przebieg obliczeń
Ustalamy, że a =� a , b =� b
( 0 ) ( 0 )
a +� b
( 0 ) ( 0 )
pierwsza iteracja
x(� =�
0)�
2
Sprawdzamy, czy
f ( x( 0 ) ) <� d� ,
x( 0 ) =� x*
jeżeli TAK, to x jest rozwiązaniem
( 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( 1 ) +� b( 1 )
druga iteracja
x( 1 ) =�
2
Sprawdzamy, czy
f ( x( 1) ) <� d� ,
7
jeżeli TAK, to x jest rozwiązaniem x =� x*
( 1 ) ( 1 )
jeżeli NIE, to sprawdzamy, czy przedział [ a , x ]
( 1 ) ( 1 )
spełnia warunek f (�a )��� f (�x )�<� 0
,
(1 ) ( 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 )
a( 2 ) +� b( 2 )
Następnie
trzecia iteracja
x( 2 ) =�
2
8
Sprawdzamy, czy f ( x( 2 ) ) <� d� ,
jeżeli TAK, to x jest rozwiązaniem
( 2 )
x( 2 ) =� x*
.
Jeżeli nie, to sprawdzamy & . itd.
a( k ) +� b( k )
Algorytm
gdzie k = 0, 1, 2, 3, & ..
x( k ) =�
2
wtedy x( k ) =� x*
Zakończenie obliczeń f ( x( k ) ) <� d�
9
Ilustracja graficzna
f(x)
a(0) +� b(0)
x =� x*
f ( x( 0 ) ) <� d� ,
( 0 )
x(�0)� =�
2
a( 1 ) +� b( 1 ) x( 1 ) =� x*
f ( x( 1) ) <� d� ,
x( 1 ) =�
2
f(b)
b(2)
a(2)
a(1) b(1)
b
a
a(0) x
b(0)
x(1)
x(2)
x(0)
f(a)
%f (x(2))% < � x (2) = x*
10
Karta następstw
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
Regula falsi
12
Metoda: regula falsi
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 znalez
ć przedział [�a,b]�
Ustalić liczby �, � (większe od błędu zaokrąglenia
wynikającego ze skończonej precyzji zapisu liczb w komputerze)
13
Przebieg obliczeń
Wyznaczamy punkt przecięcia prostej przechodzącej przez punkty
a, f (a) i b, f (b) z osią x
f(x)
x(1)
f ( b )��( b -� a ) a
x( 1 ) =� b -�
f ( b ) -� f ( a )
x
b
f ( x(1 ) )�� f (b ) <� 0 to x( p ) =� b x( 0 ) =� a
Jeżeli
Jeżeli NIE, to
x( p ) =� a x( 0 ) =� b
f ( x( 1) ) <� d� ,
Sprawdzamy, czy
x =� x*
Jeżeli TAK, to jest rozwiązaniem
x( 1 )
( 1 )
14
Jeżeli NIE, to
f ( x )��( x -� x )
( k ) ( p ) ( k )
k = 1, 2, 3 ,&
x =� x -�
( k +�1 ) ( k )
f ( x ) -� f ( x )
( p ) ( k )
Koniec obliczeń, gdy
wtedy
f ( x( k+�1) ) <� d�
x =� x*
( k+�1 )
15
Ilustracja graficzna
f(x)
f(b)
x(1)
a
x
b
0
f(a)
16
Ilustracja graficzna
f (x(1)) �f (b) < 0 x(0) = a x(p) = b
f(x)
f(b)
x(0) x(1)
a
x
b
0
x(p)
f(a)
%f(x(1))% < � TAK koniec obliczeń x (1) = x *
NIE liczymy dalej
17
f (x(1)) �f (b) < 0 x(p) = b x(0) = a
Ilustracja graficzna
f(x)
f(b)
x(2)
x(1)
a
x
b
0
x(0)
x(p)
f(a)
18