Numerické metody
4. přednáška, 15. března 2019
Jiří Zelinka
Jiří Zelinka Numerické metody 4. přednáška, 15. března 2019 1 / 16
Opakování
Newtonova metoda, metoda tečen
Uvažujme rovnici f (x) = 0. Zvolme x0 a řešení hledáme na
tečně k f v bodě x0 jako její průsečík s osou x.
−1 −0.5 0 0.5 1
−1
−0.8
−0.6
−0.4
−0.2
0
0.2
0.4
0.6
0.8
1
x
y
x0
x1
x2
xk+1 = xk − f (xk )
f (xk )
Iterační funkce:
g(x) = x − f (x)
f (x)
Podobně pokračujeme dál: xk+1 je průsečík tečny k funkci f v
bodě xk s osou x.
Newtonova metoda je metoda druhého řádu pro jednoduchý
kořen ξ.
Jiří Zelinka Numerické metody 4. přednáška, 15. března 2019 2 / 16
Fourierovy podmínky
Věta
Nechť f ∈ C2
[a, b] a nechť rovnice f (x) = 0 má v intervalu
jediný kořen ξ. Nechť f , f nemění znaménka na intervalu
[a, b], přičemž f (x) = 0, ∀x ∈ [a, b]. Nechť počáteční
aproximace x0
je ten z krajních bodů a, b, v němž znaménko
funkce je stejné jako znaménko f na intervalu [a, b]. Pak
posloupnost {xk}∞
k=0 určená Newtonovou metodou konverguje
monotonně k bodu ξ.
Jiří Zelinka Numerické metody 4. přednáška, 15. března 2019 3 / 16
Metoda sečen
Derivaci v bodě xk u Newtonovy metody nahradíme směrnicí
sečny v bodech [xk−1, f (xk−1)] a [xk, f (xk)].
f (xk) ≈
f (xk) − f (xk−1)
xk − xk−1
, i = 1, 2, . . .
Výsledná iterační metoda
xk+1 = xk −
xk − xk−1
f (xk) − f (xk−1)
f (xk), i = 1, 2, . . .
Jiří Zelinka Numerické metody 4. přednáška, 15. března 2019 4 / 16
1 1.2 1.4 1.6 1.8 2
−1
0
1
2
3
4
5
x
y
x0
x1
x2
x3
x4
Jiří Zelinka Numerické metody 4. přednáška, 15. března 2019 5 / 16
Pozor! Při pokusu o co nejpřesnější výpočet může dojít k
nedefinovanému výrazu typu 0/0.
Věta
Nechť rovnice f (x) = 0 má kořen ξ a nechť derivace f , f
jsou spojité v okolí bodu ξ, přičemž f (ξ) = 0. Posloupnost
určená metodou sečen konverguje ke kořenu ξ, pokud zvolíme
počáteční aproximace x0, x1 dostatečně blízko bodu ξ
a metoda je řádu (1 +
√
5)/2
.
= 1,618.
Jiří Zelinka Numerické metody 4. přednáška, 15. března 2019 6 / 16
Metoda regula falsi
Předpokládejme f (a)f (b) < 0, f ∈ C[a, b]. Použijeme metodu
sečen, přitom vybíráme iterace tak, aby ve dvou po sobě
jdoucích měla f opačné znaménko:
xk+1 = xk −
xk − xs
f (xk) − f (xs)
f (xk), k = 0, 1, . . . ,
kde s = s(k) je největší index takový, že f (xk)f (xs) < 0,
přitom f (x0)f (x1) < 0 (tj. např. x0 = a, x1 = b).
Poznámka: pokud je funkce f konvexní nebo konkávní na
[a, b], je xs jeden z krajní bodů intervalu.
Řád metody: 1
Jiří Zelinka Numerické metody 4. přednáška, 15. března 2019 7 / 16
Metoda regula falsi
1 1.2 1.4 1.6 1.8 2
−1
0
1
2
3
4
5
x
y
x0
x1
x2
x3
x4
Konec opakování
Jiří Zelinka Numerické metody 4. přednáška, 15. března 2019 8 / 16
Kvazinewtonova metoda (plus/minus)
Tečnu u Newtonovy metody nahradíme sečnou procházející
bodem [xk, f (xk)] a bodem [xk + f (xk), f (xk + f (xk))],
respektive bodem [xk − f (xk], f (xk − f (xk))]. Přitom pokud je
bod xk blízko hledaného kořene ξ, pak hodnota f (xk) je blízká
nule a sečna procházející uvedenými body je blízká tečně
vedené bodem xk.
f (xk) ≈
f (xk) − f (xk ± f (xk))
xk − (xk ± f (xk))
=
f (xk) − f (xk ± f (xk))
f (xk)
xk+1 = xk−f (xk)
f (xk)
f (xk) − f (xk ± f (xk))
= xk±
f 2
(xk)
f (xk) − f (xk ± f (xk))
Jiří Zelinka Numerické metody 4. přednáška, 15. března 2019 9 / 16
Iterační funkce:
g(x) = x ±
f 2
(x)
f (x) − f (x ± f (x))
Poznámka:
Kvazinewtonova metoda se také někdy nazývá Steffensenova viz
příště.
Věta
Nechť f ∈ C1
[a, b], ξ ∈ [a, b] nechť je řešením rovnice
f (x) = 0 a f (ξ) = 0. Pak existuje ε > 0 tak, že posloupnost
{xk}∞
k=0 generovaná kvazinewtonovou metodou konverguje
k bodu ξ pro každou počáteční aproximaci
x0
∈ [ξ − ε, ξ + ε] ∩ [a, b]. Pokud má funkce f v okolí bodu ξ
spojitou druhou derivaci, je řád metody alespoň 2.
Důkaz: L’Hospitalovo pravidlo.
Jiří Zelinka Numerické metody 4. přednáška, 15. března 201910 / 16
Iterační metody pro násobné kořeny
Kořen ξ násobnosti M
f (ξ) = 0, f (ξ) = 0, . . . , f (M−1)
(ξ) = 0, f (M)
(ξ) = 0
Věta
Nechť kořen ξ má násobnost M > 1. Pak modifikovaná
Newtonova metoda
xk+1 = xk − M
f (xk)
f (xk)
je metoda druhého řádu.
Jiří Zelinka Numerické metody 4. přednáška, 15. března 201911 / 16
Násobnost kořene zpravidla neznáme =⇒ univerzální volba:
u(x) =
f (x)
f (x)
Funkce u má stejné kořeny jako funkce f , ale násobnosti 1,
takže můžeme použít Newtonovu metodu pro funkci u.
Tento postup nefunguje pro funkci, která má všechny derivace
nulové – např. f (x) = e− 1
x2
.
Pro tuto funkci selhávají i kriteria zastavení konvergence:
|xk+1 − xk| < ε,
|xk+1 − xk|
|xk+1|
< ε, |f (xk)| < ε
Jiří Zelinka Numerické metody 4. přednáška, 15. března 201912 / 16
Urychlení konvergence – Aitkenova δ2
-metoda
Věta
Nechť je dána posloupnost {xk}∞
k=0, xk = ξ, k = 0, 1, 2, . . .,
lim
k→∞
xk = ξ, a nechť tato posloupnost splňuje podmínky
xk+1−ξ = (C+o(1))(xk−ξ), k = 0, 1, 2, . . . , |C| < 1, lim
k→∞
o(1) = 0
Pak posloupnost
ˆxk = xk −
(xk+1 − xk)2
xk+2 − 2xk+1 + xk
je definována pro všechna dostatečně velká k a platí
lim
k→∞
ˆxk − ξ
xk − ξ
= 0,
tj. posloupnost {ˆxk} konverguje k limitě ξ rychleji než
posloupnost {xk}.
Jiří Zelinka Numerické metody 4. přednáška, 15. března 201913 / 16
Důkaz:
Korektnost výrazu pro velká k:
xk+2 − 2xk+1 + xk = (xk+2 − ξ) − 2(xk+1 − ξ) + (xk − ξ) =
= (xk+1 − ξ)(C + o(1)) − 2(xk − ξ)(C + o(1)) + (xk − ξ) =
= (xk − ξ)(C + o(1))2
− 2(xk − ξ)(C + o(1)) + (xk − ξ) =
= (xk − ξ)(C2
− 2C + 1 + o(1)) = (xk − ξ) (C − 1)2
+ o(1)
ˆxk − ξ = xk − ξ −
(xk+1 − xk )2
xk+2 − 2xk+1 + xk
= (xk − ξ) −
(xk+1 − ξ − (xk − ξ))2
(xk − ξ) ((C − 1)2 + o(1))
=
= (xk − ξ) −
(xk − ξ)2(C − 1 + o(1))2
(xk − ξ) ((C − 1)2 + o(1))
= (xk − ξ) 1 −
(C − 1 + o(1))2
(C − 1)2 + o(1)
a odtud
lim
k→∞
ˆxk − ξ
xk − ξ
= lim
k→∞
1 −
(C − 1 + o(1))2
(C − 1)2 + o(1)
= 0.
Jiří Zelinka Numerické metody 4. přednáška, 15. března 201914 / 16
Geometrická interpretace
Položme
ε(xk) = xk −xk+1 = xk −ξ−(xk+1 −ξ) = (xk −ξ)(1−C +o(1))
ε(xk+1) = xk+1 − xk+2 = (xk+1 − ξ)(1 − C + o(1)) =
= (xk − ξ)(C + o(1))(1 − C + o(1)) = ε(xk)(C + o(1))
−0.05 0 0.05 0.1 0.15 0.2 0.25 0.3 0.35
−0.05
0
0.05
0.1
0.15
0.2
0.25
x2x3x4x5
x^
2
ε(x2)
ε(x3)
Jiří Zelinka Numerické metody 4. přednáška, 15. března 201915 / 16
Rovnice přímky:
y − ε(xk) =
ε(xk) − ε(xk+1)
xk − xk+1
(x − xk)
Průsečík s osou x (y = 0) je bod ˆxk
ˆxk = xk −
ε(xk)(xk − xk+1)
ε(xk) − ε(xk+1)
= xk −
(xk+1 − xk)2
xk+2 − 2xk+1 + xk
.
Vyjádření pomocí diferencí:
∆xk = xk+1 − xk
∆2
xk = ∆xk+1 − ∆xk = xk+2 − 2xk+1 + xk
∆3
xk = ∆2
xk+1 − ∆2
xk
...
ˆxk = xk −
(∆xk)2
∆2xk
Jiří Zelinka Numerické metody 4. přednáška, 15. března 201916 / 16