Numerické metody
2. přednáška, 26. února 2014
Jiří Zelinka
Jiří Zelinka Numerické metody 2. přednáška, 26. února 2014 1 / 14
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, 26. února 2014 2 / 14
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, 26. února 2014 3 / 14
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.
Důkaz: Položme f (x) = x − g(x). Pak
g(a) ≥ a ⇒ f (a) = a − g(a) ≤ 0,
g(b) ≤ b ⇒ f (b) = b − g(b) ≥ 0
Protože f je spojitá, existuje ξ takové, že f (ξ) = 0, tedy
ξ − g(ξ) = 0, neboli ξ = g(ξ).
Jiří Zelinka Numerické metody 2. přednáška, 26. února 2014 4 / 14
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 funkce g je kontrakce na I, pak g má na tomto
intervalu jediný pevný bod.
Důkaz: Existence plyne z předchozí věty. Pokud by existovaly
2 pevné body ξ1 a ξ2, pak
|ξ1 − ξ2| = |g(ξ1) − g(ξ2)| ≤ L|ξ1 − ξ2| < |ξ1 − ξ2|
Spor.
Konec opakování
Jiří Zelinka Numerické metody 2. přednáška, 26. února 2014 5 / 14
Volba počáteční iterace
Věta: Nechť g je kontrakce s Lipschitzovou konstantou L na I
a x0 ∈ I je libovolné. Pak iterační posloupnost definovaná
vztahem xk+1 = g(xk) konverguje k pevnému bodu funkce g.
Důkaz:
|xk − ξ| = |g(xk−1) − g(ξ)| ≤ L |xk−1 − ξ|
Indukcí
|xk − ξ| ≤ Lk
|x0 − ξ| → 0 pro L < 1
Jiří Zelinka Numerické metody 2. přednáška, 26. února 2014 6 / 14
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|
Důkaz:
|xk+1 − xk| = |g(xk) − g(xk−1)| ≤ L |xk − xk−1| ≤ . . . ≤ Lk
|x1 − x0|
Dále pro m > k ≥ 1
|xm − xk| ≤ |xm − xm−1| + |xm−1 − xm−2| + . . . + |xk+1 − xk| ≤
≤ Lm−1
|x1 − x0| + Lm−2
|x1 − x0| + · · · + Lk
|x1 − x0| =
= Lk
1 + L + · · · + Lm−k−1
|x1 − x0|
Jiří Zelinka Numerické metody 2. přednáška, 26. února 2014 7 / 14
lim
m→∞
xm = ξ
|ξ − xk| = lim
m→∞
|xm − xk| ≤ Lk
|x1 − x0|
∞
n=0
Ln
=
Lk
1 − L
x1 − x0
Určení konstanty L pomocí derivace
Lagrangeova věta o střední hodnotě:
g(x) − g(y) = g (µ) · (x − y)
Bod µ leží mezi x a y.
Pokud pro každé x ∈ I platí |g (x)| ≤ L < 1 a g zobrazuje I
do sebe, je g kontrakce na I.
Jiří Zelinka Numerické metody 2. přednáška, 26. února 2014 8 / 14
Řád metody
Mějme posloupnost (xn) získanou nějakou iterační metodou,
lim
n→∞
= ξ.
Chyba k-té iterace: 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, že daná iterační metoda je řádu p.
Jiří Zelinka Numerické metody 2. přednáška, 26. února 2014 9 / 14
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, 26. února 2014 10 / 14
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, 26. února 2014 11 / 14
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, 26. února 2014 12 / 14
Důsledek: 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 2. přednáška, 26. února 2014 13 / 14
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)
Jiří Zelinka Numerické metody 2. přednáška, 26. února 2014 14 / 14