Numerické metody
7. přednáška, 2. dubna 2014
Jiří Zelinka
Jiří Zelinka Numerické metody 7. přednáška, 2. dubna 2014 1 / 16
Normy vektorů a matic
Vektory – prvky Rn
nebo Cn
, sloupcové.
Normy vektorů
Vektorová norma na Cn
je funkce · (z Cn
do R)
s následujícími vlastnostmi:
1 x ≥ 0, ∀x ∈ Cn
2 x = 0 ⇔ x = o, o = (0, . . . , 0)T
3 αx = |α| x , ∀α ∈ C, ∀x ∈ Cn
4 x + y ≤ x + y , ∀x, y ∈ Cn
.
Jiří Zelinka Numerické metody 7. přednáška, 2. dubna 2014 2 / 16
Příklady vektorových norem:
1 x 2 =
n
i=1
|xi |2
1
2
(eukleidovská norma)
2 x 1 =
n
i=1
|xi | (oktaedrická norma)
3 x ∞ = max
1≤i ≤n
|xi | (krychlová norma)
4 x p =
n
i=1
|xi |p
1
p
(p norma)
Každá vektorová norma indukuje metriku danou vztahem
ρ(x, y) = x − y .
Konvergence v normě: xn → x ⇔ xn − x → 0.
Jiří Zelinka Numerické metody 7. přednáška, 2. dubna 2014 3 / 16
Matice
Nechť A je čtvercová matice řádu n s reálnými resp.
komplexními prvky:
A =





a11 · · · · · · a1n
a21 a2n
...
...
an1 · · · · · · ann





.
Mn: třída všech matic tohoto typu.
Matici A lze považovat za vektor dimenze n2
. Mohli bychom
tedy definovat normu matice jako normu vektoru. Ale
potřebujeme i další vlastnosti:
Jiří Zelinka Numerické metody 7. přednáška, 2. dubna 2014 4 / 16
Vlastní čísla a vlastní vektory
A · x = λx
x – vlastní vektor matice AA, λ – příslušné vlastní číslo
Vlastní čísla jsou kořeny charakteristického polynomu
ψA(λ) = det(λ · E − A), E – jednotková matice
Spektrální poloměr matice: ρ(A) = max{|λk|; λk je vlastní
číslo matice A}
Stopa matice: tr(A) =
n
k=1
akk
Jiří Zelinka Numerické metody 7. přednáška, 2. dubna 2014 5 / 16
Normy matic
Maticová norma na množině Mn je reálná funkce ·
s těmito vlastnostmi:
1 A ≥ 0, ∀A ∈ Mn
2 A = 0 ⇔ A je nulová matice
3 αA = |α| A , ∀α ∈ C, ∀A ∈ Mn
4 A + B ≤ A + B , A, B ∈ Mn
5 AB ≤ A B , A, B ∈ Mn
Vlastnost 5) se nazývá multiplikativnost.
Jiří Zelinka Numerické metody 7. přednáška, 2. dubna 2014 6 / 16
Souhlasnost maticové a vektorové normy
Řekneme, že maticová norma · je souhlasná s danou
vektorovou normou · ϕ, jestliže
Ax ϕ ≤ A x ϕ, ∀x ∈ Cn
, ∀A ∈ Mn.
Přidružená norma
Nechť · ϕ je vektorová norma na Cn
. Pak číslo
A ϕ = max
x ϕ=1
Ax ϕ
je maticová norma souhlasná s danou vektorovou normou
· ϕ.
Pro jednotkovou matici E platí
E ϕ = max
x ϕ=1
Ex ϕ = 1
a pro souhlasnou maticovou normu platí E ≥ 1.
Jiří Zelinka Numerické metody 7. přednáška, 2. dubna 2014 7 / 16
Věta
Přidružená maticová norma je nejvýše rovna libovolné
maticové normě souhlasné s danou vektorovou normou.
Věta
Nechť maticová norma · je souhlasná s danou vektorovou
normou · ϕ. Pak pro všechna vlastní čísla λ matice A platí:
|λ| ≤ A .
Jiří Zelinka Numerické metody 7. přednáška, 2. dubna 2014 8 / 16
Přidružené maticové normy
Nechť A ∈ Mn. Přidružené maticové normy k vektorovým
normám · 1, · ∞, · 2 jsou dány vztahy
1 A 1 = max
1≤j≤n
n
i=1
|aij |,
2 A ∞ = max
1≤i ≤n
n
j=1
|aij |,
3 A 2 = ρ(A∗A), ρ(A∗
A) je spektrální poloměr A∗
A,
kde A∗
= A
T
, pro reálné matice je A∗
= AT
.
A 2 – spektrální norma matice
Jiří Zelinka Numerické metody 7. přednáška, 2. dubna 2014 9 / 16
Frobeniova norma
A F =
n
j=1
n
i=1
|aij |2
1
2
.
A 2
F = tr(A∗
A)
E F =
√
n.
1√
n
A ∞ ≤ A 2 ≤
√
n A ∞
A 2 ≤ A F ≤
√
n A 2
1√
n
A 1 ≤ A 2 ≤
√
n A 1 .
Jiří Zelinka Numerické metody 7. přednáška, 2. dubna 2014 10 / 16
Věta
Nechť B < 1, · je souhlasná s danou vektorovou
normou. Pak matice E − B je regulární a platí
(E − B)−1
≤
E
1 − B
.
Jiří Zelinka Numerické metody 7. přednáška, 2. dubna 2014 11 / 16
Iterační metody řešení systémů lineárních rovnic
Systém
Ax = b
převedeme na
x = Tx + g
x∗
– řešení
x∗
= (E − T)−1
g za předpokladu, že E − T je regulární.
x0
∈ Rn
– libovolná počáteční aproximace. Posloupnost
xk ∞
k=0
určená rekurentně vztahem
xk+1
= Txk
+ g, k = 0, 1, . . .
se nazývá iterační posloupnost a matice T se nazývá
iterační matice
Jiří Zelinka Numerické metody 7. přednáška, 2. dubna 2014 12 / 16
Problémy:
1 Jak zvolit iterační matici T, tj. jakým způsobem převést
systém Ax = b na systém x = Tx + g?
2 Za jakých předpokladů posloupnost xk ∞
k=0
konverguje
pro libovolnou počáteční aproximaci k přesnému řešení
x∗
?
x1
= Tx0
+ g,
x2
= Tx1
+ g = T(Tx0
+ g) + g = T2
x0
+ (T + E)g,
x3
= Tx2
+ g = T3
x0
+ (T2
+ T + E)g,
...
xk+1
= Tk+1
x0
+ (Tk
+ Tk−1
+ . . . + E)g.
Definice
Řekneme, že matice H je konvergentní, jestliže
lim
k→∞
Hk
= O,
kde O je nulová matice, konvergence je bodová.
Jiří Zelinka Numerické metody 7. přednáška, 2. dubna 2014 13 / 16
Věta
Následující tvrzení jsou ekvivalentní:
1 H je konvergentní matice.
2 lim
k→∞
Hk
= 0 pro nějakou přidruženou maticovou normu.
3 ρ(H) < 1 (ρ(H) je spektrální poloměr H).
4 lim
k→∞
Hk
x = o pro libovolný vektor x ∈ Rn
.
Lemma
Nechť ρ(T) < 1. Pak E − T je regulární a platí
(E − T)−1
= E + T + T2
+ . . .
Jiří Zelinka Numerické metody 7. přednáška, 2. dubna 2014 14 / 16
Hlavní věta o konvergenci iteračního procesu
Posloupnost xk ∞
k=0
určená iteračním procesem x = Tx + g
konverguje pro každou počáteční aproximaci x0
∈ Rn
právě
tehdy, když ρ(T) < 1, přičemž
lim
k→∞
xk
= x∗
, x∗
= Tx∗
+ g
Důsledek
Nechť pro nějakou přidruženou maticovou normu platí
T < 1. Pak posloupnost xk ∞
k=0
generovaná iteračním
procesem x = Tx + g konverguje k řešení x∗
= (E − T)−1
g
pro každou počáteční aproximaci x0
∈ Rn
. Dále platí
x∗
− xk
≤ T k
x∗
− x0
,
x∗
− xk
≤
T k
1 − T
x1
− x0
.
Jiří Zelinka Numerické metody 7. přednáška, 2. dubna 2014 15 / 16
Kriteria pro zastavení výpočtu
1 xk+1
− xk
/ xk
< ε
2 rk+1
≤ ε( A xk+1
+ b ), kde rk+1
= Axk+1
− b
maticová norma je přidružená dané vektorové normě, ε > 0 je
požadovaná přesnost.
Jiří Zelinka Numerické metody 7. přednáška, 2. dubna 2014 16 / 16