Numerické metody
3. přednáška, 8. března 2019
Jiří Zelinka
Jiří Zelinka Numerické metody 3. přednáška, 8. března 2019 1 / 17
Opakování
Metoda pevného bodu, prostá iterační metoda
Tato metoda se používá pro rovnici x = g(x)
Funkce g je spojitá na I = [a, b]
Řešení ξ této rovnice nazýváme pevným bodem funkce
g
Iterační proces
Zvolíme x0 ∈ I a položíme x1 = g(x0)
Obecně xk+1 = g(xk)
Funkce g se nazývá iterační funkce
Jiří Zelinka Numerické metody 3. přednáška, 8. března 2019 2 / 17
Řád metody
lim
k→∞
|xk+1 − ξ|
|xk − ξ|p = lim
k→∞
|ek+1|
|ek|p = C ≡ 0,
p - řád metody
Věta: Nechť funkce g má v okolí bodu ξ derivace až do řádu
p ≥ 1 včetně. Iterační metoda xk+1 = g(xk), k = 0, 1, . . . je
řádu p tehdy a jen tehdy, když platí
ξ = g(ξ), g(j)
(ξ) = 0, 1 ≤ j < p, g(p)
(ξ) = 0.
Jiří Zelinka Numerické metody 3. přednáška, 8. března 2019 3 / 17
Klasifikace pevných bodů
Pevný bod ξ funkce g se nazývá
přitahující (atraktivní) pevný bod, jestliže existuje
takové okolí V tohoto bodu ξ, že pro každou počáteční
aproximaci x0 ∈ V posloupnost iterací {xk}∞
k=0 konverguje
k bodu ξ.
odpuzující (repulzivní) pevný bod, jestliže existuje
takové okolí U bodu ξ, že pro každou počáteční
aproximaci x0 ∈ U, x0 = ξ, existuje takové k, že xk ∈ U.
Určení typu pevných bodů:
Nechť g ∈ C[a, b], g : [a, b] → [a, b] a nechť g má v bodě ξ
derivaci.
Je-li |g (ξ)| < 1, pak ξ je přitahující pevný bod.
Je-li |g (ξ)| > 1, pak ξ je odpuzující pevný bod.
Jiří Zelinka Numerické metody 3. přednáška, 8. března 2019 4 / 17
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.
Jiří Zelinka Numerické metody 3. přednáška, 8. března 2019 5 / 17
Věta
Nechť f ∈ C2
[a, b]. Nechť ξ ∈ [a, b] je kořenem rovnice
f (x) = 0 a f (ξ) = 0. Pak existuje δ > 0 tak, že posloupnost
{xk}∞
k=0 generovaná Newtonovou metodou konverguje k bodu
ξ pro každou počáteční aproximaci x0 ∈ [ξ − δ, ξ + δ] ⊆ [a, b].
Řád Newtonovy metody je roven 2 pro jednoduchý kořen ξ.
Odhad chyby:
a) |xk+1 − ξ| ≤ M
2m
(xk − ξ)2
b) |xk+1 − ξ| ≤ M
2m
(xk+1 − xk)2
Konec opakování
Jiří Zelinka Numerické metody 3. přednáška, 8. března 2019 6 / 17
Příklady
Výpočet odmocniny m
√
a:
f (x) = xm
− a, f (x) = m xm−1
,
Newtonova metoda:
xk+1 = xk −
xm
k − a
m xm−1
k
Výpočet převrácené hodnoty 1
a
bez dělení:
Jak volit funkci f ?
Jiří Zelinka Numerické metody 3. přednáška, 8. března 2019 7 / 17
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 3. přednáška, 8. března 2019 8 / 17
Fourierovy podmínky
1.3 1.4 1.5 1.6 1.7 1.8 1.9 2
−1
0
1
2
3
4
5
6
x
y
x0
x1
x2
Jiří Zelinka Numerické metody 3. přednáška, 8. března 2019 9 / 17
Problémy:
ξ – inflexní bod, např. funkce arctan x
−3 −2 −1 0 1 2 3
−1.5
−1
−0.5
0
0.5
1
1.5
x
y
x0
x1
x2
Nevhodná volba iterace: f (xk) = 0.
Vícenásobný kořen: f (ξ) = f (ξ) = 0
→ pomalá konvergence
Jiří Zelinka Numerické metody 3. přednáška, 8. března 2019 10 / 17
Historická poznámka
Gaston Maurice Julia, 1893 – 1978
Pro funkci f (x) = x3
− 1 řešil se studenty problém, pro které
reálné počáteční iterace metoda selže, t.j. xk = 0.
DÚ: Totéž v komplexním oboru – nikdo nevyřešil.
Důsledek: článek o 199 stranách Mémoire sur l’iteration des
fonctions rationelles, Journal de Math. Pure et Appl., 1918
Jiří Zelinka Numerické metody 3. přednáška, 8. března 2019 11 / 17
Juliova množina
Jiří Zelinka Numerické metody 3. přednáška, 8. března 2019 12 / 17
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 3. přednáška, 8. března 2019 13 / 17
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 3. přednáška, 8. března 2019 14 / 17
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.
Příklad
Výpočet 3
√
10:
Pozor! Při pokusu o co nejpřesnější výpočet může dojít k
nedefinovanému výrazu typu 0/0.
Jiří Zelinka Numerické metody 3. přednáška, 8. března 2019 15 / 17
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 3. přednáška, 8. března 2019 16 / 17
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
Jiří Zelinka Numerické metody 3. přednáška, 8. března 2019 17 / 17