1
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
Wybrane metody przybliżonego
wyznaczania rozwiązań (pierwiastków)
równań algebraicznych
w postaci f (x)
Wykład czwarty
EiT, sem. 2, 2014/2015
2
f
jest funkcją rzeczywistą zmiennej rzeczywistej x,
R
R
x
f
x
f :
.
f(x) = 0
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
f
1
(x) = f
2
(x)
3
Warunki gwarantujące znalezienie pierwiastka:
1. różne znaki funkcji na końcach przedziału
0
b
f
a
f
,
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.
4
Zakończenie procesu poszukiwania rozwiązania:
-
)
k
(
x
(
f
1
, δ - zależy od poszukiwanej wartości,
- zbieżność iteracji, czyli
,
x
x
)
k
(
)
k
(
1
ε - zależy od poszukiwanej wartości,
- iteracja trwa zbyt długo, warunek k > k
max
, koniec obliczeń,
- wartości
,
x
(
f
x
(
f
)
k
(
)
k
(
1
nieprawidłowy algorytm.
Wybór wartości
.
x
)
( 0
Metody: bisekcji, regula falsi, siecznych, stycznych, iteracji prostej.
5
Metoda bisekcji
– metoda połowienia
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)
6
Przebieg obliczeń
Ustalamy, że
)
(
)
(
b
b
,
a
a
0
0
2
0
0
0
)
(
)
(
b
a
x
Sprawdzamy, czy
,
)
x
(
f
)
(
0
jeżeli TAK, to
)
(
x
0
jest rozwiązaniem
*
x
x
)
(
0
pierwsza iteracja
7
jeżeli NIE, to sprawdzamy,
czy przedział [a,
)
(
x
0
] spełnia warunek
0
0
)
(
x
f
a
f
,
jeżeli TAK, to
)
(
)
(
)
(
b
x
,
a
a
1
0
1
jeżeli NIE, to
)
(
)
(
)
(
b
b
,
a
x
1
1
0
Następnie
2
1
1
1
)
(
)
(
)
(
b
a
x
Sprawdzamy, czy
,
)
x
(
f
)
(
1
druga
iteracja
8
jeżeli TAK, to
)
(
x
1
jest rozwiązaniem
*
x
x
)
(
1
jeżeli NIE, to sprawdzamy, czy przedział [
)
(
a
1
,
)
(
x
1
]
spełnia warunek
0
1
1
)
(
)
(
x
f
a
f
,
jeżeli TAK, to
)
(
)
(
)
(
)
(
b
x
,
a
a
2
1
2
1
jeżeli NIE, to
)
(
)
(
)
(
)
(
b
b
,
a
x
2
1
2
1
Następnie
2
2
2
2
)
(
)
(
)
(
b
a
x
trzecia iteracja
9
Sprawdzamy, czy
,
)
x
(
f
)
(
2
jeżeli TAK, to
)
(
x
2
jest rozwiązaniem
*
x
x
)
(
2
.
Jeżeli nie, to sprawdzamy …. itd.
Algorytm
2
)
k
(
)
k
(
)
k
(
b
a
x
gdzie k = 0, 1, 2, 3, …..
Zakończenie obliczeń
)
x
(
f
)
k
(
wtedy
*
x
x
)
k
(
10
a
b
f(x)
x
f(a)
f(b)
x
(0)
a
(1)
b
(1)
a
(0)
b
(0)
2
)
0
(
)
0
(
0
b
a
x
,
)
x
(
f
)
(
0
*
x
x
)
(
0
2
1
1
1
)
(
)
(
)
(
b
a
x
,
)
x
(
f
)
(
1
*
x
x
)
(
1
x
(1)
a
(2)
b
(2)
x
(2)
Ilustracja graficzna
│f (x
(2)
)│ < δ
x
(2)
= x
*
11
Karta następstw
START
CZYTAJ: a, b,
δ f (x) = 0
k = 0
x (k) = (a+b)/2
│f (x (k) )│<δ
TAK
x
*
= x (k)
STOP
NIE
f (a)
·f (x (k)) < 0
NIE
a = x (k)
TAK
b = x (k)
k = k + 1
12
Regula falsi
13
Metoda: regula falsi
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)
14
Przebieg obliczeń
Wyznaczamy punkt przecięcia prostej 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
Jeżeli
a
x
b
x
to
)
b
(
f
)
x
(
f
)
(
)
p
(
)
(
0
1
0
Jeżeli NIE, to
b
x
a
x
)
(
)
p
(
0
Sprawdzamy, czy
,
)
x
(
f
)
(
1
Jeżeli TAK, to
)
(
x
1
jest rozwiązaniem
*
x
x
)
(
1
a
b
x
(1)
f(x)
x
15
Jeżeli NIE, to
)
x
(
f
)
x
(
f
)
x
x
(
)
x
(
f
x
x
)
k
(
)
p
(
)
k
(
)
p
(
)
k
(
)
k
(
)
k
(
1
k = 1, 2, 3 ,…
Koniec obliczeń, gdy
)
x
(
f
)
k
(
1
wtedy
*
x
x
)
k
(
1
16
f(x)
x
f(b)
f(a)
a
b
0
Ilustracja graficzna
x
(1)
17
Ilustracja graficzna
f(x)
x
f(b)
f(a)
a
b
0
x
(1)
f (x
(1)
)
·f (b) < 0 x
(0)
= a x
(p)
= b
x
(p)
│f(x
(1)
)
│ < δ
TAK
koniec obliczeń x
(1)
= x
*
NIE
liczymy dalej
x
(0)
18
Ilustracja graficzna
f(x)
x
f(b)
f(a)
a
b
0
x
(1)
f (x
(1)
)
·f (b) < 0 x
(p)
= b x
(0)
= a
x
(p)
x
(2)
x
(0)