Wybrane metody przybliżonego
wyznaczania rozwiązań (pierwiastków)
równań algebraicznych
w postaci f (x)
Wykład czwarty cd.
1
EiT, sem. 2, 2014/2015
Metoda siecznych
2
Metoda siecznych
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)
3
Przebieg obliczeń
Wyznaczamy punkt przecięcia prostej (siecznej) przechodzącej przez
punkty a, f (a) i b, f (b) z osią x
f(x)
x(1)
a
f ( b )��( b -� a )
x( 1 ) =� b -�
x
b
f ( b ) -� f ( a )
f ( x( 1) ) <� d� ,
Sprawdzamy, czy
x( 1 ) =� x*
Jeżeli TAK, to jest rozwiązaniem
x( 1 )
Jeżeli NIE, to liczymy dalej, ale najpierw musimy określić, który z punktów
4
będzie stanowił punkt odniesienia - punkt wykreślania kolejnych siecznych
Ustalenia
x( 0 )
Jeżeli
f (x(1))�� f (b) <� 0 to x(0) =� b
Jeżeli NIE, to x( 0 ) =� a
Wyznaczamy punkt przecięcia prostej (siecznej) przechodzącej przez
punkty
z osią x
x , f ( x ), x , f ( x )
( 0 ) ( 0 ) ( 1 ) ( 1 )
5
f(x)
f ( x )��( x -� x )
( 1 ) ( 1 ) ( 0 )
x(1)
x =� x -�
a
( 2 ) ( 1 )
f ( x ) -� f ( x )
( 1 ) ( 0 )
x
b
x(2)
Sprawdzamy, czy f ( x( 2 ) ) <� d� ,
Jeżeli TAK, to x(2) jest rozwiązaniem
x(2) =� x*
Jeżeli NIE, to liczymy dalej zgodnie z zależnością
f ( x )��( x -� x )
( k ) ( k ) ( k -�1 )
k = 2, 3, & ,
x =� x -�
( k +�1 ) ( k )
f ( x ) -� f ( x )
( k ) ( k -�1 )
6
f(x)
f(b)
x(2)
x(1)
a
x
b
0
x(3)
x(0)
f(a)
7
f ( x( k+�1) ) <� d�
Po każdej iteracji sprawdzamy, czy
Koniec obliczeń, gdy
f ( x( k+�1) ) <� d�
wtedy
x =� x*
( k+�1 )
8
Ilustracja graficzna
f(x)
f(b)
x(1)
a
x
b
0
f(a)
9
Ilustracja graficzna
f (x (1)) �f (b) < 0 x(0) = b
f(x)
f(b)
x(1)
a
x
b
0
x(0)
f(a)
%f(x(1))% < � TAK koniec obliczeń x (1) = x *
NIE liczymy dalej
10
f (x(1)) �f (b) < 0 x(0) = b
Ilustracja graficzna
f(x)
f(b)
x(2) x(3)
x(1)
a
x
b
0
x(0)
f ( b )��( b -� a )
x( 1 ) =� b -�
f ( b ) -� f ( a )
f(a)
f ( x )��( x -� x )
( k ) ( k ) ( k -�1 )
x =� x -�
k = 2, 3, & ,
( k +�1 ) ( k )
f ( x ) -� f ( x )
( k ) ( k -�1 )
11
Metoda stycznych
Metoda stycznych
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)
Funkcja f (x) musi mieć określoną i ciągłą pierwszą i drugą pochodną w przedziale [a, b]
Przebieg obliczeń
x(0)
Ustalamy, który z końców przedziału będzie traktowany jako
x =� a lub x =� b
( 0 ) ( 0 )
f ( x( 0 ) )�� f ''( x( 0 ) ) >� 0
Spełniony musi być warunek
Obliczenia wykonujemy według wzoru iteracyjnego:
f ( x )
( k )
k = 0, 1, 2, &
x =� x -�
( k +�1 ) ( k )
f '( x )
( k )
f ( x( k+�1) ) <� d�
Po każdej iteracji sprawdzamy, czy
x( k+�1 ) =� x*
f ( x( k+�1) ) <� d�
Koniec obliczeń, gdy wtedy
f (b)�f  (b) > 0 b = x(0)
Ilustracja graficzna
X(0)
X(2) X(1)
%f (x(1)) %< � TAK kończymy obliczenia x(1) = x*
NIE liczymy dalej
%f (x (2))% < � TAK kończymy obliczenia x (2) = x*
NIE liczymy dalej
Metoda iteracji prostej
16
Metoda iteracji prostej
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)
Funkcja f (x) musi mieć określoną i ciągłą pierwszą i drugą pochodną w przedziale [a, b]
17
Przebieg obliczeń
Funkcję f (x) przekształcamy do postaci x =� F( x )
Obliczenia wykonujemy według wzoru iteracyjnego
x =� F( x )
k = 0, 1, 2, & ..
( k+�1 ) ( k )
Po każdej iteracji sprawdzamy, czy
f ( x( k+�1) ) <� d�
f ( x( k+�1) ) <� d�
wtedy
x( k+�1 ) =� x*
Obliczenia kończymy, gdy
a +� b
x =�
Początek obliczeń
( 0 )
2
18
Warunek zbieżności
Jeżeli istnieje taki ułamek q, że
F'( x ) Ł� q <�1 dla a Ł� x Ł� b
to iteracja będzie zbieżna
19
Ilustracja graficzna
f(x)
F(x)
f(x)=x
F(x)
x
a b
0
x(1) x(0)
%f (x(1))%< � TAK kończymy obliczenia x (1) = x *
NIE liczymy dalej
20
Algorytm zbieżny Algorytm rozbieżny
x =� 4 -� 2x1/ 3
x =� 2 -� 23 x -� 2
1/ 3
F(x) =� 4 -� 2x
3
F(x) =� 2 -� 2 x -� 2
21
Algorytm rozbieżny
x =� 2x
y
F(x) =� 2x
y=2x
y=x
xII
(0)
xI
0 x
(0)
*=0
x
22
Zestawienie wyników
Wynik Liczba iteracji
Bisekcja 2,1875 4
Regula falsi 2,173 3
Siecznych 2,18 3
Stycznych 2,175 3
Iteracji prostej 2,1859 3