Numerické metody 8. přednáška, 14. dubna 2016
Jiří Zelinka
Jiří Zelinka        Numerické metody 8. prednáška, 14. dubna 2016 1/21
Opakování
Normy matic
Souhlasnost maticové a vektorové normy
Řekneme, že maticová norma
je souhlasná s danou
vektorovou normou
, jestliže
Ax
A
x
Vx e C",   V/A e M,-
Pridružená norma
Nechť
je vektorová norma na O1. Pak číslo
/A
= max
11X11^=1
Ax
je maticová norma souhlasná s danou vektorovou normou
(p-
Jiří Zelinka
Numerické metody 8. přednáška, 14. dubna 2016 2/21
Veta
Přidružená maticová norma je nejvýše rovna libovolné maticové normě souhlasné s danou vektorovou normou
Veta
Nechť maticová norma
normou
je souhlasná s danou vektorovou . Pak pro všechna vlastní čísla A matice A platí:
A < A
Jiří Zelinka
Numerické metody 8. přednáška, 14. dubna 2016 3/21
Veta
Nechť ||6|| < 1, || • || je souhlasná s danou vektorovou normou. Pak matice E — B je regulární a platí
(E-B)
-i
<
	E	
1 -		B
Konec opakování
Jiří Zelinka
Numerické metody 8. přednáška, 14. dubna 2016 4/21
Iterační metody řešení systémů lineárních rovnic
Systém
převedeme na
Ax = b
x = Tx + g
x - reseni
x* = (E — T) lg za předpokladu, že E — T je regulární.
x° G W - libovolná počáteční aproximace. Posloupnost {x^}^ určená rekurentně vztahem
xk+i = Jxk + g,      k = 0,1,...
se nazývá iterační posloupnost a matice T se nazývá iterační matice
Jiří Zelinka        Numerické metody 8. přednáška, 14. dubna 2016 5/21
Problémy:
O Jak zvolit iterační matici T, tj. jakým způsobem převést systém Ax = b na systém x = T x + gl
Q Za jakých předpokladů posloupnost {xk}™ konverguje pro libovolnou počáteční aproximaci k přesnému řešení
x*?
1    = Tx° + g,
= Tx1+g= T(Tx°+g)+g= T2x° + (T+E)g,
x
X X
= Tx2+g= T3x° + (72 +T+E)g
xk+1 = Tk+1x° + {Tk + Tk~x + ... + E)g. Definice
Řekneme, že matice H je konvergentní, jestliže
lim Hk = O,
k^oc
kde Oje nulová matice, konvergence je bodová^,
Jiří Zelinka
Numerické metody 8. prednáška, 14. dubna 2016 6/21
Veta
Následující tvrzení jsou ekvivalentní: O H je konvergentní matice.
O  lim = 0 pro nějakou přidruženou maticovou normu
O p(H) < 1 (p(H) je spektrální poloměr H). O  lim Hkx = o pro libovolný vektor x G R".
Lemma
Nechť p{T) < 1. Pak E — T je regulární a platí
(E- 7)"1 = f + T+ Tz + ...
Jiří Zelinka
Numerické metody 8. přednáška, 14. dubna 2016 7/21
Hlavní veta o konvergenci iteracního procesu
Posloupnost {xk}™   určená iteračním procesem x = Tx + g konverguje pro každou počáteční aproximaci x° G W právě tehdy, když p(T) < 1, přičemž
k *
im x = x
k^řoc
x* = 7x* + g
Důsledek
Nechť pro nějakou přidruženou maticovou normu platí |7~|| < 1. Pak posloupnost {xk}™   generovaná iteračním procesem x = Tx + g konverguje k řešení x* = (f — T)~lg pro každou počáteční aproximaci x° G IR". Dále platí
* k
x — X
* k
x — x
<
<
T
* 0
x — x
	T	k
1 -		T
xx-x°
Jiří Zelinka        Numerické metody 8. přednáška, 14. dubna 2016 8/21
Kriteria pro zastavení výpočtu
xk+i _ xk
x
< s
O ||r*+1|| < e{\\A\\ \\xk+1\\ + \\b\\), kde rk+1 = Axk+1 - b
maticová norma je přidružená dané vektorové normě, e > 0 je požadovaná přesnost.
Jiří Zelinka
Numerické metody 8. přednáška, 14. dubna 2016 9/21
Jacobiova iterační metoda
Ax = b,     a =
/ 3n 321
Matici A zapišme ve tvaru
•• •   aln \
32 n
A = D-L-U
' nn
kde
/ au
D =
\
0
0 \
' nn
J
Jiří Zelinka        Numerické metody 8. přednáška, 14. dubna 2016 10/21
L =
U =
í o
— 321 ■
V -a„i ■
( O -312
V o
a„,„-i  O / -ain \
3/7—1,n
O
D je diagonálni matice, L je dolní trojúhelníková matice s nulami na diagonále a U je horní trojúhelníková matice s nulami na diagonále.
Jiří Zelinka        Numerické metody 8. přednáška, 14. dubna 2016 11 /21
Ax = {D-L -U)x = b Dx = (L+U)x + b.
Pokud a,-,- /O, / = 1,..., n, je matice D regulární a z předchozí rovnice lze vypočítat
x = D-X(L+ U)x + D~lb.
-i
/jit
D-1 =
\
0
o \
i. /
Jiří Zelinka        Numerické metody 8. přednáška, 14. dubna 2016 12/21
Maticový tvar Jacobiovy iteracní metody Jacobiova iterační matice: Tj — D~1(L+ U)
x
k+l _
= Tjx* + D-1 b,
Tj = (tij), tjj = -0 pro i ^ j, ta = 0 pro i = 1,..., n.
í
Tj =
\
2nl
]nn
2n2
]nn
0	ai2	31" ^
321 322	0	^2/7 322
0
0"^ =
322
Jiří Zelinka        Numerické metody 8. přednáška, 14. dubna 2016 13/21
Realizace výpočtu:
Z první rovnice vypočteme xi:
1
anxi+3i2X2H-----\-alnxn = 6X     x1 = —(61-312*2-•. .-3i„x„)
Xf+1 = —(bí - 312X2* - ... - 3i„x£),
z druhé rovnice vypočteme x2:
X2      = -(Ď2 - 321*1 - a23*3 - . . . - 3i„xJ,
322
obecně z /-té rovnice vypočteme x,\
. .    // //
7=1
až z /7-té rovnice vypočteme xn, a na pravé straně takto získaného systému jsou prvky matice T/. < n > < fl > < , > < , > ==
Jiří Zelinka        Numerické metody 8. přednáška, 14. dubna 2016 14/21
Veta o konvergenci Jacobiovy iterační metody:
Posloupnost {xk}™   generovaná metodou
x^1 = Tjxk + D~lb konverguje pro každou počáteční aproximaci x° G W1 právě tehdy, když g(Tj) < 1.
Odhad chyby:
x — x
oo
<
	T		k oo	
1 -		T		oo
x — X
o
oo •
Příklad
Geometrický význam
Jiří Zelinka
Numerické metody 8. přednáška, 14. dubna 2016 15/21
Silné řádkové sumační kriterium:
Nechť matice A je ryze řádkově diagonálně dominantní, tj
n
au
>
\au
i = 1.....n.
7=1
Pak Jacobiova iterační metoda konverguje pro každou počáteční aproximaci x° G IR".
Silné sloupcové sumační kriterium:
Nechť matice A je ryze sloupcově diagonálně dominantní, tj
n
2kk
>
k — 1..... n.
i //c
Pak Jacobiova iterační metoda konverguje pro každou počáteční aproximaci x° e IR". 4 n „
1=    s} <\(y
Jiří Zelinka
Numerické metody 8. prednáška, 14. dubna 2016 16/21
Gaussova-Seidelova iterační metoda
Z první rovnice vypočteme xi:
aiix1+a12x2-\-----^alnxn = bľ     xx = —{bi-a12x2-.. .-a^x,,)
x*+1 — —(61 — ai2X^ — ... — a^x^), z druhé rovnice vypočteme x2, pro xi použijme novou iteraci
x
k+1
2      — -(^2      321*1 ^3X3 — • • • —
a22
ze třetí rovnice vypočteme x3, pro xi a x2 použijme novou iteraci:
x
/c+l
3      — -(^3 — 331xl+1 — 332x2+1 — 234X4 ... — ai„X^),
^33
.k+1
Jiří Zelinka        Numerické metody 8. přednáška, 14. dubna 2016 17 / 21
Obecně
/-i
x"+1 = -
Z_j o.. J
j=i "
£« xfc + El
.  .... "II dll
7=1+1
/ = 1,..., n.
Maticový zápis: Ax = b
(D-L-U)x  = b
{D-L)x  =  Í7x + b.
a,v    0, / = 1,..., /?,   ^> matice D — /_ je regulární a
x = (D - L)"1^ + (D - L)"1^
Položme Tg = (D — L)~lU, Gaussova-Seidelova iterační metoda je tvaru
-i
x
k+l
= TGxk + g,      g = (D-L)~1b.
Jiří Zelinka
Numerické metody 8. přednáška, 14. dubna 2016 18/21
Veta
Posloupnost {xk}™   generovaná Gaussovou-Seidelovou iterační metodou xk+l = (D - Ľ)~lUxk + (D - L)'1 b. konverguje pro každou počáteční aproximaci x° G W právě tehdy, když g(Tc) < 1.
Silné řádkové sumační kriterium:
Nechť matice A je ryze řádkově diagonálně dominantní, tj.
n
'//
>
1 = 1
•   • •
/7.
Pak Gaussova-Seidelova iterační metoda konverguje pro každou počáteční aproximaci x° e IR".
Jiří Zelinka
Numerické metody 8. přednáška, 14. dubna 2016 19/21
Silné sloupcové sumační kriterium:
Nechť matice A je ryze sloupcově diagonálně dominantní, tj
n
2kk
>
k — 1..... n.
i //c
Pak Gaussova-Seidelova iterační metoda konverguje pro každou počáteční aproximaci x° e IR".
Příklad
Geometrický význam
Jiří Zelinka        Numerické metody 8. přednáška, 14. dubna 2016 20/21
Veta (Stein-Rosenberg)
Nechť pro prvky matice A platí a,y < 0 pro všechna / ^ j a a,-,- > 0, / = 1,..., n. Pak platí právě jedno z následujících tvrzení:
• 0 < q(tg) < q(Tj) < 1
• 1 < q(Tj) < g{TG)
• q(Tj) = q(Tg) = 0
o g(Tj) = q(Tg) = 1.
To znamená, že konvergují-li obě metody, Gaussova-Seidelova metoda konverguje rychleji.
Věta
Nechť A je pozitivně definitní matice. Pak Gaussova-Seidelova metoda konverguje pro každou počáteční aproximaci.
Jiří Zelinka
Numerické metody 8. přednáška, 14. dubna 2016 21 /21