Numerické metody
2. přednáška
Jiří Zelinka
1. března 2019
Jiří Zelinka Numerické metody 2. přednáška 1 / 19
Domácí úkol
r x
Jiří Zelinka Numerické metody 2. přednáška 2 / 19
r x
S1 S2
α2α
S1 + S2 =
1
2
S.
S1 =
1
2
x2
(α−sin α)
S2 =
1
2
r2
[(2π − 2α)−
− sin(2π − 2α)]
Jiří Zelinka Numerické metody 2. přednáška 3 / 19
r
x
2
α
2
x/2
r
= cos
α
2
,
x = 2r cos
α
2
r < x <
√
2r
π
2
< α <
2π
3
α = tan α−
π
2 cos α
Jiří Zelinka Numerické metody 2. přednáška 4 / 19
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 2. přednáška 5 / 19
Geometrická interpretace
Pevný bod ξ je průsečík grafu funkce g a přímky y = x.
0 0.2 0.4 0.6 0.8 1 1.2 1.4
0
0.2
0.4
0.6
0.8
1
1.2
1.4
g(x)
y=x
ξ
Jiří Zelinka Numerické metody 2. přednáška 6 / 19
Existence pevného bodu
Věta: Jestliže spojitá funkce g zobrazuje interval I do sebe,
tj. pro každé x ∈ I platí g(x) ∈ I, pak na intervalu I existuje
alespoň jeden pevný bod ξ funkce g.
Jednoznačnost pevného bodu
Definice Funkce g zobrazující interval I do sebe se nazývá
kontrakce na I, jestliže existuje taková konstanta L
(Lipschitzova konstanta), 0 ≤ L < 1, že pro každé x, y ∈ I
platí
|g(x) − g(y)| ≤ L|x − y|.
Banachova věta o pevném bodě
Jestliže g je kontrakce na I, pak g má na tomto intervalu
jediný pevný bod a iterační posloupnost definovaná vztahem
xk+1 = g(xk) konverguje k pevnému bodu funkce g pro
libovolné x0.
Jiří Zelinka Numerické metody 2. přednáška 7 / 19
Odhad chyby
Věta: Nechť g je kontrakce s Lipschitzovou konstantou L na I
a x0 ∈ I je libovolné. Pak pro iterační posloupnost definovanou
vztahem xk+1 = g(xk) platí odhad
|xk − ξ| ≤
Lk
1 − L
|x0 − x1|
Určení konstanty L pomocí derivace
Lagrangeova věta o střední hodnotě:
g(x) − g(y) = g (µ) · (x − y)
Pokud pro každé x ∈ I platí |g (x)| ≤ L < 1 a g zobrazuje I
do sebe, je g kontrakce na I.
L = max
x∈I
|g (x)|
Konec opakování
Jiří Zelinka Numerické metody 2. přednáška 8 / 19
Další typy iteračních funkcí (metod)
Vícekroková metoda
xk+1 = g(xk, xk−1, . . . , xk−s+1)
Nestacionární metoda
xk+1 = gk(xk)
Nestacionární vícekroková metoda
xk+1 = gk(xk, xk−1, . . . , xk−s+1)
Jiří Zelinka Numerické metody 2. přednáška 9 / 19
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.
Jiří Zelinka Numerické metody 2. přednáška 10 / 19
Věta: Nechť g ∈ C[a, b], g : [a, b] → [a, b] a nechť ξ je pevný
bod.
Jestliže pro všechna x = ξ z nějakého okolí V bodu ξ platí
g(x) − g(ξ)
x − ξ
< 1,
pak ξ je přitahující pevný bod.
Jestliže pro všechna x = ξ z nějakého okolí U bodu ξ platí
g(x) − g(ξ)
x − ξ
> 1,
pak ξ je odpuzující pevný bod.
Jiří Zelinka Numerické metody 2. přednáška 11 / 19
Důsledek: Nechť g ∈ C[a, b], g : [a, b] → [a, b], ξ je pevný
bod a nechť g má v okolí bodu ξ spojitou 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 2. přednáška 12 / 19
Hledání vhodného tvaru 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
Jiří Zelinka Numerické metody 2. přednáška 13 / 19
Řád metody
Řád konvergence posloupnosti
Definice Mějme posloupnost (xn) lim
n→∞
= ξ.
Chyba v k-tém členu: ek = xk − ξ
Existuje-li nyní reálné číslo p ≥ 1 takové, že platí
lim
k→∞
|xk+1 − ξ|
|xk − ξ|p = lim
k→∞
|ek+1|
|ek|p = C = 0,
řekneme, řád konvergence posloupnosti je p.
Pokud posloupnost (xn) byla získána nějakou iterační
metodou, říkáme, že metoda je řádu p.
Poznámka: Definici lze použít pro libovolné (např.
vícekrokové nebo nestacionární) iterační metody.
Jiří Zelinka Numerické metody 2. přednáška 14 / 19
Řád prosté iterační 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.
Důkaz: Z Taylorova rozvoje.
Jiří Zelinka Numerické metody 2. přednáška 15 / 19
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
x0
x1
x2
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 2. přednáška 16 / 19
Rovnice tečny:
y = f (xk)(x − xk) + f (xk)
y = 0 ⇒ xk+1 = xk −
f (xk)
f (xk)
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 2. přednáška 17 / 19
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 2. přednáška 18 / 19
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 2. přednáška 19 / 19