Numerické metody
3. přednáška, 5. března 2014
Jiří Zelinka
Jiří Zelinka Numerické metody 3. přednáška, 5. března 2014 1 / 16
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, 5. března 2014 2 / 16
Podmínky konvergence
1 Pro každé x ∈ I platí g(x) ∈ I
2 Existuje L, 0 ≤ L < 1, že pro každé x, y ∈ I platí
|g(x) − g(y)| ≤ L|x − y|.
nebo:
Pro každé x ∈ I platí |g (x)| ≤ L < 1.
Pak x0 ∈ I může být libovolné, iterační proces konverguje.
Jiří Zelinka Numerické metody 3. přednáška, 5. března 2014 3 / 16
Řád metody
lim
k→∞
|xk+1 − ξ|
|xk − ξ|p = lim
k→∞
|ek+1|
|ek|p = C ≡ 0,
p - řád metody
Jiří Zelinka Numerické metody 3. přednáška, 5. března 2014 4 / 16
Volba iterační funkce
f (x) = 0 −→ g(x) = x
g(x) = x −
f (x)
k
g(x) = x −
f (x)
h(x)
Příklad
Výpočet 3
√
10: f (x) = x3
− 10, x ∈ I = [2, 3]
Položíme g(x) = x − x3−10
k
, hledáme k tak, aby g byla
kontrakce.
Jiří Zelinka Numerické metody 3. přednáška, 5. března 2014 5 / 16
1 Do I se musí zobrazit extremální hodnoty g, ty mohou
být v krajních bodech nebo v lokálních extrémech:
2 ≤ g(2) = 2 +
2
k
≤ 3 ⇒ k ≥ 2
2 ≤ g(3) = 3 −
17
k
≤ 3 ⇒ k ≥ 17
Lokální extrém:
g (x) = 1 − 3x2
k
= 0, extrém je v bodě k/3, leží v I pro
k ≤ 27, hodnota g v tomto bodě leží v I.
2 |g (x)|L < 1: g (x) = 1 − 3x2
k
.
Extrémy mohou být v krajních bodech intervalu I nebo v
lokálních extrémech (ten je v 0):
−1 < 1 −
3 · 22
k
< 1 ⇒ k > 6
−1 < 1 −
3 · 32
k
< 1 ⇒ k > 13.5
Jiří Zelinka Numerické metody 3. přednáška, 5. března 2014 6 / 16
Konec opakování
Jiří Zelinka Numerické metody 3. přednáška, 5. března 2014 7 / 16
Newtonova metoda
Uvažujme opět 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
x
0
x1
x
2
Podobně pokračujeme dál: xi+1 je průsečík tečny k funkci f v
bodě xi s osou x.
Jiří Zelinka Numerické metody 3. přednáška, 5. března 2014 7 / 16
Rovnice tečny:
y = f (xi )(x − xi ) + f (xi )
y = 0 ⇒ xi+1 = xi −
f (xi )
f (xi )
Máme tedy iterační funkci
g(x) = x −
f (x)
f (x)
Newtonova metoda se také nazývá metoda tečen.
Jiří Zelinka Numerické metody 3. přednáška, 5. března 2014 8 / 16
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ůkaz
Ukážeme, že na [ξ − δ, ξ + δ] je funkce g(x) = x − f (x)
f (x)
kontrakcí.
Důsledek:
Newtonova metoda je metoda druhého řádu pro jednoduchý
kořen ξ.
Jiří Zelinka Numerické metody 3. přednáška, 5. března 2014 9 / 16
Příklad
Výpočet 3
√
10:
f (x) = x3
− 10, x ∈ I = [2, 3]
g(x) = x −
x3
− 10
3x2
=
2
3
x +
10
3x2
x0 = 2, x1 = 2.1667, x2 = 2.1545, x3 = 2.1544
Jiří Zelinka Numerické metody 3. přednáška, 5. března 2014 10 / 16
Chování chyby u Newtonovy metody
Věta
Nechť jsou splněny předpoklady předchozí věty,
M = max
x∈I
|f (x)|, m = min
x∈I
|f (x)| > 0, I = [ξ − δ, ξ + δ]. Pak
pro posloupnost xk ∞
k=0
generovanou Newtonovou metodou
platí
a) xk+1
− ξ ≤ M
2m
(xk
− ξ)2
b) xk+1
− ξ ≤ M
2m
(xk+1
− xk
)2
Důkaz
Z Taylorova rozvoje.
Jiří Zelinka Numerické metody 3. přednáška, 5. března 2014 11 / 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 ξ.
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, 5. března 2014 12 / 16
Metoda sečen
Derivaci v bodě xi u Newtonovy metody nahradíme poměrnou
diferencí
f (xi ) ≈
f (xi ) − f (xi−1)
xi − xi−1
, i = 1, 2, . . .
Výsledná iterační metoda
xi+1 = xi −
xi − xi−1
f (xi ) − f (xi−1)
f (xi ), i = 1, 2, . . .
Jiří Zelinka Numerické metody 3. přednáška, 5. března 2014 13 / 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 3. přednáška, 5. března 2014 14 / 16
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:
f (x) = x3
− 10, x ∈ I = [2, 3] Volíme x0 = 2, x1 = 3, pak
x2 = 2.1053, x3 = 2.1391, x4 = 2.11548, x5 = 2.11544.
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, 5. března 2014 15 / 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:
xi+1 = xi −
xi − xs
f (xi ) − f (xs)
f (xi ), i = 0, 1, . . . ,
kde s = s(i) je největší index takový, že f (xi )f (xs) < 0 a
f (x0)f (x1) < 0 (tj. např. x0 = a, x1 = b).
Jiří Zelinka Numerické metody 3. přednáška, 5. března 2014 16 / 16