PRZYBLI ONE METODY
ROZWI ZYWANIA
RÓWNA
Metody kolejnych przybli e
Metody kolejnych przybli e
Twierdzenie 1. (Bolzano  Cauchy ego)
Je eli funkcja F(x) jest ci gła w przedziale domkni tym
[a,b] i F(a)Å"F(b) < 0, to mi dzy punktami a i b znajduje si
co najmniej jeden pierwiastek równania F(x) = 0.
Twierdzenie 2.
Je eli w przedziale [a, b] spełnione s zało enia twierdzenia 1.
i dodatkowo sgn F 2 (x) = const dla x"[a,b], to przedział ten
jest przedziałem izolacji pierwiastka równania F(x) = 0.
3
Metody kolejnych przybli e
Przebieg funkcji mi dzy punktami a i b
4
Metody kolejnych przybli e
Przykład
Sprawdzić czy podany przedział jest przedziałem izolacji
jednego pierwiastka równania F(x) = 0.
F(x) = x3 - 3x2 - 2x + 5
[a,b] = [1,2]
5
Metody kolejnych przybli e
=13 - 3Å"12 - 2Å"1+ 5
F(a) = F(1) =1
= 23 - 3Å" 22 - 2Å" 2 + 5=-3
F(b) = F(2)
Poniewa :
F(1) Å" F(2) < 0
to wiadomo, e pomi dzy punktami a i b znajduje si co
najmniej jeden pierwiastek równania F(x) = 0.
6
Metody kolejnych przybli e
d F(x)
2
F (x) = = 3x2 - 6x - 2
d x
= 3Å"12 - 6Å"1- 2
2 2 =-5
F (a) = F (1)
= 3Å" 22 - 6Å" 2 - 2
2 2 =-2
F (b) = F (2)
2
sgn F (x) = const dla x"[a,b]
Poniewa :
czyli funkcja ma stały znak w przedziale [a,b],
to przedział [a, b] jest przedziałem izolacji jednego pierwiastka
równania F(x) = 0.
7
Metoda bisekcji
Metoda bisekcji
Niech [a,b] b dzie przedziałem izolacji pierwiastka równania
F(x) = 0.
Jako pierwsze dwa wyrazy ci gu przybli e przyjmuje si :
x1 = a x2 = b
Kolejne przybli enia wynikaj ze wzoru:
xi-1 + xk
xi = , k "[1,(i - 2)], i > 2
2
9
Metoda bisekcji
k dobierane jest tak, aby:
xi - xi-1 H" xi - xk
F(xi-1)F(xi) < 0
10
Metoda bisekcji
11
Metoda bisekcji
Poniewa kolejne przybli enia znajduj si ka dorazowo w
przedziałach izolacji, oraz
xi+1 - xi < xi - xi-1
Metoda jest zbie na
12
Metoda bisekcji
Zaleta metody: prostota
Wada metody: wolna zbie no ć procesu iteracyjnego
13
Metoda bisekcji
Algorytm
x1 = a
x2 = b
i =1,2,...,m
Å„Å‚
ôÅ‚
x1 + x2
ôÅ‚
x =
2
ôÅ‚
ôÅ‚y = F(x)
òÅ‚
ôÅ‚y1 = F(x1)
ôÅ‚
ôÅ‚je eli y Å" y1 > 0 to x1 = x
ôÅ‚w przeciwnym wypadku x2 = x
ół
14
Metoda bisekcji
Przykład
Dla funkcji i przedziału izolacji z poprzedniego przykładu
obliczyć metod bisekcji pierwiastek równania F(x) = 0 z
dokÅ‚adno ci µ.
[a,b] = [1,2]
F(x) = x3 - 3x2 - 2x + 5
x1 = a =1 x2 = b = 2
µ = 0.1
F(xi ) <µ
15
Metoda bisekcji
1. iteracja
x1 =1 x2 = 2
x1 + x2 1+ 2
x = ==1.5
2 2
y = F(x) = F(1.5) =-1.375
F(x) >µ
=1
y1 = F(x1) = F(1)
x2 = x =1.5
< 0
y Å" y1 = -1.375
16
Metoda bisekcji
2. iteracja
x1 =1 x2 =1.5
x1 + x2 1+1.5
x = ==1.25
2 2
y = F(x) = F(1.25) =-0.234
F(x) >µ
=1
y1 = F(x1) = F(1)
x2 = x =1.25
< 0
y Å" y1 = -0.234
17
Metoda bisekcji
3. iteracja
x1 =1 x2 =1.25
x1 + x2 1+1.25
x = ==1.125
2 2
y = F(x) = F(1.125) = 0.376
F(x) >µ
=1
y1 = F(x1) = F(1)
x1 = x =1.125
> 0
y Å" y1 = 0.376
18
Metoda bisekcji
4. iteracja
x1 =1.125 x2 =1.25
x1 + x2 1.125 +1.25
x = ==1.1875
2 2
y = F(x) = F(1.1875) = 0.069
F(x) <µ
Pierwiastek:
x =1.1875
19
Metoda ci ciw
Metoda ci ciw
Rozwi zanie równania F(x) =0 jest przybli one ci giem miejsc
zerowych ci ciw poprowadzonych mi dzy punktami
stanowi cymi ko ce kolejnych przedziałów izolacji.
21
Metoda ci ciw
22
Metoda ci ciw
Równanie ci ciw, mo na zapisać w postaci:
y - F(xi-1) x - xi-1
=
F(xk ) - F(xi-1) xk - xi-1
xk  drugi kraniec przedziału izolacji [xi-1,xk]
Czyli pierwsz ci ciw prowadzimy miedzy punktami:
(a, F(a)) (b, F(b))
23
Metoda ci ciw
Dla y = 0:
xk - xi-1
xi = xi-1 - F(xi-1)
F(xk ) - F(xi-1)
"
"
"
"
24
Metoda ci ciw
Zało enie:
W przedziale [a,b], lub w kolejnym przedziale izolacji znak
drugiej pochodnej funkcji F(x) nie zmienia si .
Wyrazy ci gu " daj przybli enie pierwiastka
"
"
"
z niedomiarem lub nadmiarem.
25
Metoda ci ciw
Przybli enie z niedomiarem:
2 2 2
F (x) < 0 F (x) < 0
2 2 2 lub
F (x) > 0 F (x) > 0
wtedy:
xi < xi+1 < xi+2 < ... < x*
26
Metoda ci ciw
Przybli enie z nadmiarem:
2 2 2
F (x) < 0 F (x) > 0
2 2 2 lub
F (x) > 0 F (x) < 0
wtedy:
xi > xi+1 > xi+2 > ... > x*
Przy czym dwie s siednie warto ci ci gu przybli e zwi zane
s wzorem "
"
"
"
27
Metoda ci ciw
2 2
F (x) > 0 F (x) < 0
2 2 2 2
F (x) > 0 F (x) < 0
Oszacowanie pierwiastka z niedomiarem
28
Metoda ci ciw
2 2
F (x) > 0 F (x) < 0
2 2 2 2
F (x) < 0 F (x) > 0
Oszacowanie pierwiastka z nadmiarem
29
Metoda ci ciw
Ci g {xi} jest monotoniczny i ograniczony, posiada wi c granic :
lim xi = g
i"
czyli:
xk - g
= g
= g - F(g)
lim{xi}
i"
F(xk ) - F(g)
st d wynika:
g = x*
F(g) = 0
co dowodzi zbie no ci metody.
30
Metoda ci ciw
xk  punkt stały p ku ci ciw
Lewy lub prawy kraniec przedziału [a,b], czyli xk = a lub xk = b
.
2 2 2
F (x) Å" F (x) > 0
xk = b
x"[a,b],
xk = a
x"[a,b], 2 2 2
F (x) Å" F (x) < 0
31
Metoda ci ciw
Przykład
Dla funkcji i przedziału izolacji z poprzedniego przykładu
obliczyć metod ci ciw pierwiastek równania F(x) = 0 z
dokÅ‚adno ci µ.
F(x) = x3 - 3x2 - 2x + 5
[a,b] = [1,2]
µ = 0.1
2
F (x) = 3x2 - 6x - 2
2 2
F (x) = 6x - 6
32
Metoda ci ciw
Okre lenie punktu p ku ci ciw xk:
a + b 1+ 2
z = ==1.5
2 2
2 2 =-4.25
F (z) = F (1.5)
2 2 2 2 = 6
F (z) = F (1.5)
2 2 2
F (z) Å" F (z) < 0
xk = a =1 F(xk ) =1
x1 = b = 2 F(x1) =-3
33
Metoda ci ciw
1. iteracja
xk - x1
x2 = x1 - F(x1)
=1.25
F(xk ) - F(x1)
=-0.234
F(x2) = F(1.25)
F(x) >µ
34
Metoda ci ciw
2. iteracja
xk - x2
x3 = x2 - F(x2)
=1.202
F(xk ) - F(x2)
=-0.0017576
F(x3) = F(1.202)
F(x) <µ
Pierwiastek:
x =1.202
35
Metoda stycznych
(Newtona)
Metoda stycznych
Rozwi zanie równania F(x) = 0 w przedziale [a,b] jest
przybli one ci giem miejsc zerowych stycznych do
funkcji F(x).
37
Metoda stycznych
38
Metoda stycznych
Równanie stycznej w punkcie xi-1:
2
y - F(xi-1) = F (xi-1)(x - xi-1)
Dla y = 0:
F(xi-1)
xi = xi-1 - , i >1
2
F (xi-1)
39
Metoda stycznych
Wybór pierwszego przybli enia x1 = a lub x1 = b:
2 2 2
F (x) Å" F (x) > 0
x1 = b
x1 = a
2 2 2
F (x) Å" F (x) < 0
Je eli druga pochodna w przedziale izolacji nie ma stałego
znaku, to proces iteracyjny mo e być rozbie ny
40
Metoda stycznych
2 2
F (x) > 0 F (x) < 0
2 2 2 2
F (x) < 0 F (x) > 0
Wybór pierwszego przybli enia w metodzie stycznych
41
Metoda stycznych
2 2
F (x) > 0 F (x) < 0
2 2 2 2
F (x) > 0 F (x) < 0
Wybór pierwszego przybli enia w metodzie stycznych c. d.
42
Metoda stycznych
Przykład
Dla funkcji i przedziału izolacji z poprzedniego przykładu
obliczyć metod stycznych pierwiastek równania F(x) = 0
z dokÅ‚adno ci µ.
F(x) = x3 - 3x2 - 2x + 5
[a,b] = [1,2]
µ = 0.1
2
F (x) = 3x2 - 6x - 2
2 2
F (x) = 6x - 6
43
Metoda stycznych
a + b 1+ 2
z = ==1.5
2 2
x1 = a =1
2 2 2
F (z) Å" F (z) < 0
F(x1) =1
2
F (x1) =-5
44
Metoda stycznych
1. iteracja
F(x1)
x2 = x1 -
=1.2
2
F (x1)
F(x2) = 0.008
Mo na przerwać obliczenia!
F(x) <µ
2
F (x2) =-4.88
45
Metoda stycznych
2. iteracja
F(x2)
x3 = x2 -
=1.202
2
F (x2)
F(x3) =-0.00176
F(x) <µ
46
Metoda stycznych
- inny wariant
Metoda stycznych  inny wariant
48
Metoda stycznych  inny wariant
F(xi-1)
xi = xi-1 - , x1 = a lub x1 = b, i >1
2
F (x1)
49
Metoda stycznych  inny wariant
Przykład
Dla funkcji i przedziału izolacji z poprzedniego przykładu
obliczyć metod stycznych pierwiastek równania F(x) = 0
z dokÅ‚adno ci µ.
F(x) = x3 - 3x2 - 2x + 5
[a,b] = [1,2]
µ = 0.1
2
F (x) = 3x2 - 6x - 2
2 2
F (x) = 6x - 6
50
Metoda stycznych  inny wariant
a + b 1+ 2
z = ==1.5
2 2
x1 = a =1
2 2 2
F (z) Å" F (z) < 0
F(x1) =1
2
F (x1) =-5
51
Metoda stycznych  inny wariant
1. iteracja
F(x1)
F(x2) = 0.008
x2 = x1 -
=1.2
2
F (x1)
Mo na przerwać obliczenia!
F(x) <µ
2. iteracja
F(x2)
x3 = x2 -
=1.202
F(x3) = 0.0001935
2
F (x1)
52