1
Wybrane metody przybliżonego
wyznaczania rozwiązań (pierwiastków)
równań algebraicznych
w postaci f (x)
Wykład czwarty cd.
EiT, sem. 2, 2014/2015
1
Wybrane metody przybliżonego
wyznaczania rozwiązań (pierwiastków)
równań algebraicznych
w postaci f (x)
Wykład czwarty cd.
EiT, sem. 2, 2014/2015
2
Metoda siecznych
3
Metoda siecznych
Zakłada się, że występująca w równaniu (1) funkcja
f jest ciągła na zadanym przedziale
b
a, i spełnia w punktach krańcowych warunek
f (x) = 0
(1)
0
b
f
a
f
Należy znaleźć przedział
b
a,
Ustalić liczby ε, δ (większe od błędu zaokrąglenia
wynikającego ze skończonej precyzji zapisu liczb w komputerze)
4
Przebieg obliczeń
Wyznaczamy punkt przecięcia prostej (siecznej) przechodzącej przez
punkty a, f (a) i b, f (b) z osią x
)
a
(
f
)
b
(
f
)
a
b
(
)
b
(
f
b
x
)
(
1
Sprawdzamy, czy
,
)
x
(
f
)
(
1
Jeżeli TAK, to
)
(
x
1
jest rozwiązaniem
*
x
x
)
(
1
Jeżeli NIE, to liczymy dalej, ale najpierw musimy określić, który z punktów
będzie stanowił punkt odniesienia - punkt wykreślania kolejnych siecznych
a
b
x
(1)
f(x)
x
5
Ustalenia
)
(
x
0
Jeżeli
b
x
to
b
f
x
f
)
0
(
)
1
(
0
)
(
)
(
Jeżeli NIE, to
a
x
)
(
0
Wyznaczamy punkt przecięcia prostej (siecznej) przechodzącej przez
punkty
)
x
(
f
,
x
),
x
(
f
,
x
)
(
)
(
)
(
)
(
1
1
0
0
z osią x
6
)
x
(
f
)
x
(
f
)
x
x
(
)
x
(
f
x
x
)
(
)
(
)
(
)
(
)
(
)
(
)
(
0
1
0
1
1
1
2
Sprawdzamy, czy
,
)
x
(
f
)
(
2
Jeżeli TAK, to
)
2
(
x
jest rozwiązaniem
*
)
2
(
x
x
Jeżeli NIE, to liczymy dalej zgodnie z zależnością
)
x
(
f
)
x
(
f
)
x
x
(
)
x
(
f
x
x
)
k
(
)
k
(
)
k
(
)
k
(
)
k
(
)
k
(
)
k
(
1
1
1
k = 2, 3, …,
a
b
x
(1)
x
(2)
f(x)
x
7
f(x)
x
f(b)
f(a)
a
b
0
x
(1)
x
(0)
x
(2)
x
(3)
8
Po każdej iteracji sprawdzamy, czy
)
x
(
f
)
k
(
1
Koniec obliczeń, gdy
)
x
(
f
)
k
(
1
wtedy
*
x
x
)
k
(
1
9
f(x)
x
f(b)
f(a)
a
b
0
Ilustracja graficzna
x
(1)
10
Ilustracja graficzna
f(x)
x
f(b)
f(a)
a
b
0
x
(1)
f (x
(1)
)
·f (b) < 0 x
(0)
= b
x
(0)
│f(x
(1)
)
│ < δ
TAK
koniec obliczeń x
(1)
= x
*
NIE
liczymy dalej
11
Ilustracja graficzna
f(x)
x
f(b)
f(a)
a
b
0
x
(1)
f (x
(1)
)
·f (b) < 0 x
(0)
= b
x
(0)
x
(2)
x
(3)
)
x
(
f
)
x
(
f
)
x
x
(
)
x
(
f
x
x
)
k
(
)
k
(
)
k
(
)
k
(
)
k
(
)
k
(
)
k
(
1
1
1
k = 2, 3, …,
)
a
(
f
)
b
(
f
)
a
b
(
)
b
(
f
b
x
)
(
1
Metoda stycznych
Metoda stycznych
Zakłada się, że występująca w równaniu (1) funkcja
f jest ciągła na zadanym przedziale
b
a, i spełnia w punktach krańcowych warunek
f (x) = 0
(1)
0
b
f
a
f
Należy znaleźć przedział
b
a,
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ń
Ustalamy, który z końców przedziału będzie traktowany jako
)
0
(
x
b
x
lub
a
x
)
(
)
(
0
0
Spełniony musi być warunek
0
0
0
)
x
(
'
'
f
)
x
(
f
)
(
)
(
Obliczenia wykonujemy według wzoru iteracyjnego:
)
x
(
'
f
)
x
(
f
x
x
)
k
(
)
k
(
)
k
(
)
k
(
1
k = 0, 1, 2, …
Po każdej iteracji sprawdzamy, czy
)
x
(
f
)
k
(
1
Koniec obliczeń, gdy
)
x
(
f
)
k
(
1
wtedy
*
x
x
)
k
(
1
Ilustracja graficzna
f (b)
·f ”(b) > 0
b = x
(0)
X
(0)
X
(1)
X
(2)
│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
16
Metoda iteracji prostej
17
Metoda iteracji prostej
Zakłada się, że występująca w równaniu (1) funkcja
f jest ciągła na zadanym przedziale
b
a, i spełnia w punktach krańcowych warunek
f (x) = 0
(1)
0
b
f
a
f
Należy znaleźć przedział
b
a,
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]
18
Przebieg obliczeń
Funkcję f (x) przekształcamy do postaci
)
x
(
F
x
Obliczenia wykonujemy według wzoru iteracyjnego
)
x
(
F
x
)
k
(
)
k
(
1
k = 0, 1, 2, …..
Po każdej iteracji sprawdzamy, czy
)
x
(
f
)
k
(
1
Obliczenia kończymy, gdy
)
x
(
f
)
k
(
1
wtedy
*
x
x
)
k
(
1
Początek obliczeń
2
0
b
a
x
)
(
19
Warunek zbieżności
Jeżeli istnieje taki ułamek q, że
b
x
a
dla
q
)
x
(
'
F
1
to iteracja będzie zbieżna
20
Ilustracja graficzna
x
f(x)
f(x)=x
F(x)
0
a
b
F(x)
x
(0)
x
(1)
│f (x
(1)
)│< δ
TAK kończymy obliczenia x
(1)
= x
*
NIE liczymy dalej
21
Algorytm zbieżny
Algorytm rozbieżny
3
/
1
2
4
)
(
x
x
F
3
/
1
2
4
x
x
3
2
2
2
)
(
x
x
F
3
2
2
2
x
x
22
x
x
2
Algorytm rozbieżny
x
x
F
2
)
(
x =0
*
y=x
y=2x
x
y
0
x
I
(0)
x
II
(0)
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