Numerické metody
4. přednáška, 12. března 2014
Jiří Zelinka
Jiří Zelinka Numerické metody 4. přednáška, 12. března 2014 1 / 14
Opakování
Newtonova metoda
xi+1 = xi −
f (xi )
f (xi )
Fourierovy podmínky
Metoda sečen
xi+1 = xi −
xi − xi−1
f (xi ) − f (xi−1)
f (xi )
Metoda regula falsi
xi+1 = xi −
xi − xs
f (xi ) − f (xs)
f (xi ),
kde s = s(i) je největší index takový, že f (xi )f (xs) < 0.
Jiří Zelinka Numerické metody 4. přednáška, 12. března 2014 2 / 14
Quasi Newtonova 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, 12. března 2014 3 / 14
Iterační funkce:
g(x) = x ±
f 2
(x)
f (x) − f (x ± f (x))
Poznámka:
Quasi Newtonova metoda se také někdy nazývá Steffensenova
- viz dále.
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á quasi Newtonovou 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, 12. března 2014 4 / 14
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, 12. března 2014 5 / 14
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+γk)(xk−ξ), k = 0, 1, 2, . . . , |C| < 1, lim
k→∞
γk = 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, 12. března 2014 6 / 14
Důkaz:
Korektnost výrazu pro velká k:
xk+2 − 2xk+1 + xk = (xk+2 − ξ) − 2(xk+1 − ξ) + (xk − ξ) =
= (xk+1 − ξ)(C + γk+1) − 2(xk − ξ)(C + γk) + (xk − ξ) =
= (xk −ξ)(C +γk)(C +γk+1)−2(xk −ξ)(C +γk)+(xk −ξ) =
= (xk − ξ)(C2
− 2C + 1 + τk) = (xk − ξ) (C − 1)2
+ τk
ˆxk−ξ = xk−ξ−
(xk+1 − xk)2
xk+2 − 2xk+1 + xk
= (xk−ξ)−
(xk+1 − ξ − (xk − ξ))2
(xk − ξ) ((C − 1)2 + τk)
=
= (xk−ξ)−
(xk − ξ)2
(C − 1 + γk)2
(xk − ξ) ((C − 1)2 + τk)
= (xk−ξ) 1 −
(C − 1 + γk)2
(C − 1)2 + τk
a odtud
lim
k→∞
ˆxk − ξ
xk − ξ
= lim
k→∞
1 −
(C − 1 + γk)2
(C − 1)2 + τk
= 0.
Jiří Zelinka Numerické metody 4. přednáška, 12. března 2014 7 / 14
Geometrická interpretace
Položme
ε(xk) = xk −xk+1 = xk −ξ −(xk+1 −ξ) = (xk −ξ)(1+C +γk)
ε(xk+1) = xk+1 − xk+2 = (xk+1 − ξ)(1 + C + γk+1) =
= (xk − ξ)(C + γk)(1 + C + γk+1) ≈ ε(xk)(C + γk)
−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
x
2
x
3
x
4
x
5x^2
Jiří Zelinka Numerické metody 4. přednáška, 12. března 2014 8 / 14
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
.
Jiří Zelinka Numerické metody 4. přednáška, 12. března 2014 9 / 14
Steffensenova metoda
Buď g iterační funkce pro rovnici x = g(x). Položme
yk = g(xk), zk = g(yk),
xk+1 = xk −
(yk − xk)2
zk − 2yk + xk
.
V tomto případě je tedy ε(xk) = xk − yk, ε(yk) = yk − zk.
Tato iterační metoda se nazývá Steffensenova a může být
popsána iterační funkcí ϕ:
xk+1 = ϕ(xk),
kde
ϕ(x) =
xg(g(x)) − g2
(x)
g(g(x)) − 2g(x) + x
, g2
(x) = (g(x))2
.
Jiří Zelinka Numerické metody 4. přednáška, 12. března 2014 10 / 14
ϕ(xk) =
xkg(g(xk)) − g2
(xk)
g(g(xk)) − 2g(xk) + xk
=
xkg(yk) − (yk)2
g(yk) − 2yk + xk
=
=
xkzk − (yk)2
zk − 2yk + xk
=
xk(zk − 2yk + xk) − (yk − xk)2
zk − 2yk + xk
=
= xk −
(yk − xk)2
zk − 2yk + xk
Jiří Zelinka Numerické metody 4. přednáška, 12. března 2014 11 / 14
Věta
1 ϕ(ξ) = ξ implikuje g(ξ) = ξ.
2 Jestliže g(ξ) = ξ, g (ξ) existuje a g (ξ) = 1, pak
ϕ(ξ) = ξ.
Věta
Nechť funkce g má spojité derivace až do řádu p + 1 včetně
v okolí bodu x = ξ. Nechť iterační metoda xk+1 = g(xk) je
řádu p pro bod ξ.
Pak pro p > 1 je iterační metoda xk+1 = ϕ(xk) řádu 2p − 1.
Pro p = 1 je tato metoda řádu alespoň 2 za předpokladu
g (ξ) = 1.
Jiří Zelinka Numerické metody 4. přednáška, 12. března 2014 12 / 14
Müllerova metoda
Müllerova metoda je zobecněním metody sečen. Metoda sečen
v podstatě znamená, že pro dané aproximace xk, xk−1 bodu ξ
aproximujeme funkci f přímkou procházející body
[xk−1, f (xk−1)], [xk, f (xk)] a za další aproximaci bodu ξ
vezmeme průsečík této přímky s osou x. Müllerova metoda
užívá tři aproximace xk−2, xk−1, xk a křivku y = f (x)
aproximujeme parabolou určenou těmito body. Průsečík této
paraboly s osou x, který je nejbližší k xk, vezmeme za další
aproximaci xk+1. Touto metodou lze najít i násobné
a komplexní kořeny.
Jiří Zelinka Numerické metody 4. přednáška, 12. března 2014 13 / 14
xk−2, xk−1, xk jsou již vypočtené aproximace. Sestrojme
polynom
P(x) = a(x − xk)2
+ b(x − xk) + c
procházející body [xk−2, f (xk−2)], [xk−1, f (xk−1)], [xk, f (xk)],
t.j. splňující podmínky P(xi
) = f (xi
), i = k − 2, k − 1, k. Z
nich plyne
c = f (xk)
b =
(xk−2 − xk)2
[f (xk−1) − f (xk)] − (xk−1 − xk)2
[f (xk−2) − f (xk
(xk−2 − xk)(xk−1 − xk)(xk−2 − xk−1)
a =
(xk−2 − xk) [f (xk−1) − f (xk)] − (xk−1 − xk) [f (xk−2) − f (xk)]
(xk−2 − xk)(xk−1 − xk)(xk−1 − xk−2)
Jiří Zelinka Numerické metody 4. přednáška, 12. března 2014 14 / 14
xk+1 − xk =
−2c
b ±
√
b2 − 4ac
.
Znaménko u odmocniny vybereme tak, aby bylo shodné se
znaménkem b. Tato volba znamená, že jmenovatel zlomku
bude v absolutní hodnotě největší a tedy výsledná hodnota
xk+1 bude nejbližší xk. Je tedy
xk+1 = xk −
2c
b + (signb)
√
b2 − 4ac
.
Jiří Zelinka Numerické metody 4. přednáška, 12. března 2014 14 / 14