Opakování
Iteracní metody resení systémů lineárních rovnic
Systém
Ax = b
převedeme na
x = Tx + g xk+1 = Txk+g,      k = 0,l,...
Hlavní věta o konvergenci iteračního procesu
Posloupnost {xk}c^)=Q určená iteračním procesem x = Tx + g konverguje pro každou počáteční aproximaci x° G IR" právě tehdy, když p(T) < 1, přičemž
lim xk = x*, x* = Tx* + g
Jiří Zelinka        Numerické metody 9. přednáška, 15. dubna 2015 2/24
Jacobiova iterační metoda
Ax = b,
/ 3n 321
V a„i
Matici /4 zapišme ve tvaru
A = D - L - U
kde
/ 3ii
D
V
0
3ln \ 32n
3nn y
0 \
(#111 /
Jiří Zelinka        Numerické metody 9. přednáška, 15. dubna 2015 3/24
u
í o
— 321
V -a„i ■■
í O -3i2
Vo
-a„,„-i  O / -au \
~an—\n 0 /
D je diagonálni matice, /. 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 9. přednáška, 15. dubna 2015 4/24
Ax = (D - L - U)x = b
Dx = {L+ U)x + b.
Pokud a,-, 7^ 0, / = 1,...,/?, je matice D regulární a z předchozí rovnice lze vypočítat
x = D-\L+U)x + D xb.
D 1
(h
\ 0
0 \
-i- /
3nn /
Jiří Zelinka        Numerické metody 9. přednáška, 15. dubna 2015 5/24
Maticový tvar Jacobiovy iteracní metody Jacobiova iterační matice: Tj = D'1 (L + U)
Tj = (t;j), ty í
Tj
3nn
.k+1
Tjxk + D ^b,
^ pro i ^ j, ts = 0 pro / = 1,
0	3l2	3ln \
	311	3u
321	0	
322		322
3p2 3nn
D b
í h_ \
3\\ b2_
322
bn 3nn
JiŕT Zelinka        Numerické metody 9. přednáška, 15. dubna 2015 6/24
Realizace výpočtu:
Z první rovnice vypočteme xi:
3iiXi+3i2X2H-----\-alnxn = bi^xi
1
aii
.k+l
aii
(fel - 3i2X2
(/)i-ai2x2-.. .-3inxn)
z druhé rovnice vypočteme x2:
— (fe2 - a2ixf - a23x| a22
3in*„),
obecně z /-té rovnice vypočteme x,-:
.k+l
až z n-té rovnice vypočteme xn, a na pravé straně takto získaného systému jsou prvky matice Tj. , a „ <a „
Jiří Zelinka        Numerické metody 9. přednáška, 15. dubna 2015 7/24
Veta o konvergenci Jacobiovy iteracní metody:
Posloupnost {xk}^_Q generovaná metodou
xk+1 = Tjxk + D rb konverguje pro každou počáteční
aproximaci x° G IR" právě tehdy, když g(Tj) < 1.
Odhad chyby:
Jiří Zelinka        Numerické metody 9. přednáška, 15. dubna 2015 8/24
Silné řádkové sumační kriterium:
Nechť matice A je ryze řádkově diagonálně dominantní, tj.
I ay I >
/ = 1,... ,n.
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.
\akk\ >
/r = 1,..., n.
7 = 1
Pak Jacobiova iterační metoda konverguje pro každou počáteční aproximaci x° G IR".
Jiří Zelinka        Numerické metody 9. přednáška, 15. dubna 2015 9/24
Gaussova-Seidelova iterační metoda
Z první rovnice vypočteme xi:
a11x1+a12x2-\-----h3i„xn = bi     xi = —(/>i-3i2x2-.. .-3i„x„)
3ll
.k+1
311
(fel - 212X3
3lnXn),
z druhé rovnice vypočteme x2, pro xx použijme novou iteraci: 1
Jc+l
322
(62 - 32ix*+1 - a23x3A
3lnXn),
ze třetí rovnice vypočteme x3, pro xx a x2 použijme novou iteraci:
Jc+l
333
(63 - 331XÍ+1 - a32X2+1 - 334X4 ... - 3lnx;),
<n>-«flP> 1 -o^O-
Jin Zelinka        Numerické metody 9. přednáška, 15. dubna 2015 10 /24
Obecně
;-l
3/7 3//
Maticový zápis:
y\x = b    ^ (D-L-U)x (D - L)x
/ = 1,
b
Ux + b.
n.
a,-, 7^ 0, / = 1,..., n,   =>- matice D — /_ je regulární a
x = (D - /.^í/x + (D - L)-1b.
Položme TG = (D — Gaussova-Seidelova iterační
metoda je tvaru
TGxk+g,      g = (D-L)1b.
Jiří Zelinka        Numerické metody 9. přednáška, 15. dubna 2015 11 /24
Veta
Posloupnost {**}^10 generovaná Gaussovou-Seidelovou iterační metodou xk+1 = (D - Ľ) xUxk + (D - L)~xb. konverguje pro každou počáteční aproximaci x° G IR" právě tehdy, když g(TG) < 1.
Silné řádkové sumační kriterium:
Nechť matice A je ryze řádkově diagonálně dominantní, tj.
n
\aa\ >        la'íl'      i = l,...,n.
Pak Gaussova-Seidelova iterační metoda konverguje pro každou počáteční aproximaci x° G IR".
Jiří Zelinka        Numerické metody 9. přednáška, 15. dubna 2015 12 /24
Silné sloupcové sumační kriterium:
Nechť matice A je ryze sloupcově diagonálně dominantní, tj.
n
\3kk\ > ^2 I3'*!'       k = 1,... ,n. i
Pak Gaussova-Seidelova iterační metoda konverguje pro každou počáteční aproximaci x° G IR".
Příklad
Geometrický význam
Jiří Zelinka        Numerické metody 9. přednáška, 15. dubna 2015 13 /24
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 < g(TG) < q{Tj) < 1
• 1 < q(Tj) < g{TG)
• q{Tj) = q(Tg) = 0
• q{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řT Zelinka        Numerické metody 9. přednáška, 15. dubna 2015 14 /24
Relaxační metody
Modifikace Gaussovy-Seidelovy metody, to - relaxační parametr
xf+1 = (1 - u)xf
LU
au
i-1
j=l j=i+l
Relaxační metodu lze maticově zapsat takto
x^1 = (D - - u)D + uU]xk + u(D - uL^b
Tw = (D-ujľ)-1[(1-uj)D + ujU}
< □ ►  ■« flP ►  4 « ►  < ■= ►     -E -O^O-Jin Zelinka        Numerické metody 9. přednáška, 15. dubna 2015 15 /24
Hodnoty parametru u:
Pro 0 < u < 1 se iterační metody nazývají metodami dolní relaxace. Tyto metody jsou vhodné v případě, že Gaussova-Seidelova metoda nekonverguje.
Pro u = 1 je relaxační metoda totožná s Gaussovou-Seidelovou metodou.
Pro 1 < u se metody nazývají metodami horní relaxace, nebo častěji SOR metodami (SOR = Successive Over-Relaxation). Tyto metody lze užít ke zrychlení konvergence Gaussovy-Seidelovy metody.
Věta (Kahan).
Nechť a,-,- ý 0, / = 1,..., n. Pak
Důsledek: Má smysl uvažovat jen u E (0,2).
JiřT Zelinka        Numerické metody 9. přednáška, 15. dubna 2015 16 /24
Veta (Ostrowski-Reich).
Pro pozitivně definitní matici A platí í?(Tw) < 1 pro všechna
u e (0,2).
Třídiagonální matice:
A = (a;j)?j=1,      a,j = 0, pro |/ - j\ > 1
Věta.
Nechť A je třídiagonální pozitivně definitní matice. Pak g(TG) = q2(Tj) < 1 a optimální hodnota relaxačního parametru je dána vztahem
2
9 l+y/l-r{Tj)
Při této volbě je í?(Tw) = |1 — uj\.
JiřT Zelinka        Numerické metody 9. přednáška, 15. dubna 2015 17 /
Cykly v iteračních metodách
Například pro systémy
x1 + kx2 = bi xi — kx2   = t>2
Jacobiova metoda: cyklus délky 4 Gaussova-Seidelova metoda: cyklus délky 2
Relaxační metody: cykly různých délek
qx1
*2 *2
1
1.
Pro oj T2 =
2:
-1 -2 2q 4q-l
if = 2nl/p, 0 < / < p/2
Ai,2 = cos</?±/sin</?, ( >• existuje cyklus délky p.
:(l+cos^)
Body cyklu leží na elipse se středem v hledgnérp řešení.
I -O0.O
Numerické metody 9. přednáška, 15. dubna 2015 18/24
Iterační metody pro systémy nelineárních rovnic
fi{xi, ■ ■ ■ ,xm)   = 0
fm(x1,...,xm)   = 0 Kořen systému: uspořádaná m-tice reálných čísel
É = (£l,...,£m),
která tomuto systému vyhovuje. Vektorový tvar:
F(x) = o,      xeRmo = (0,...,0)í£Kl
<n>4ď> « -O^O-
Jin Zelinka        Numerické metody 9. přednáška, 15. dubna 2015 19 /24
Systém převedeme na ekvivalentní rovnici
x = G {x),     x e Rm
neboli
Xi   =  gi(xi,... ,xm)
Xm    =   §m(x\, • • • , Xm)
a budeme hledat pevný bod zobrazení G : IRm —> IRm. Definujme nyní v prostoru IRm metriku:
g(x,y) = max |x(- - y;\.
1<; <m
Prostor IRm s takto definovanou metrikou je úplným metrickým prostorem. Nyní lze pro vyšetřování konvergence iteračního procesu xk+1 = G(xk), k = 0,1,2,... užít Banachovy věty o pevném bodě.
Jiří Zelinka        Numerické metody 9. přednáška, 15. dubna 2015 20 /
Veta
Nechť zobrazení G : rm -ř rm je kontrakce na rm,
g(G(x),G(y))<qg(x,y),      0 < q < 1.
Pak pro každou počáteční aproximaci x° G rm je posloupnost {xk}7=o' k = 0,l,2,..., xk = G(xk-1), konvergentní v rm a lim xk =    kde £ je jediný pevný bod zobrazení G.
Věta
Nechť £ G rm je pevný bod rovnice x = G(x). Nechť funkce gi, i = 1,..., m, mají spojité parciální derivace pro všechna x G n(£,r), n(£,r) = {x\q(x,£) < r}. Nechť dále platí
%(*)
.9
< —, i,J m
dxj
0 < q < 1 a nechť x° G       r). Pak všechny iterace {xk}™=0 určené vztahem xk+1 = G(xk) leží v množině r) a lim x'' =
Numerické metody 9. přednáška, 15. dubna 2015 21 /24
Jednodušší predpoklad:
max
K; <m
E
dxj
<q<l.
Seidelova matoda
Pro výpočet xf+1 použijeme již vypočtených hodnot x*
k+l
.k+l
.k+l
.k+l
gl{x*,xŽ,...,xkm) g2(x1k+1,x*,...,xkm)
k+l k+l
) A2 )
•••,4)
JiŕT Zelinka        Numerické metody 9. přednáška, 15. dubna 2015 22 /24
Newtonova metoda pro systémy nelineárních rovnic
F(x) = o,      F e C2(0(0)
/ dftjx) dh{x) \
dx\
dx\ dfm(x)
dxm dfm(x)
\   dx\ dxm )
Taylorův rozvoj:
F(x + h) = F(x) + JF(x) ■ h + Odl/íf) • (1,..., 1)T x = xk, xk+1 = xk + h =>- h = xk+1 - xk
Zanedbáme chybový člen,
F(x + h) = o^ JF(xk)(xk^ - xk) = -Fa(xk9
Jiří Zelinka        Numerické metody 9. přednáška, 15. dubna 2015 23 /24
xk+1 = xk - JF\xk)F(xk)
Iterační funkce
G{x) = x - JF1{x)F{x)
Věta
Nechť £ je kořenem rovnice F(x) = o. Nechť Jf{x) je regulární matice se spojitými prvky v okolí 0(£) bodu £, přičemž
II-^MIL < K>       K = konst.,
pro všechna x z tohoto okolí. Nechť funkce /;■,/' = 1,..., m, mají spojité druhé parciální derivace v 0(£). Posloupnost {**}^10 určená Newtonovou metodou konverguje ke kořenu £ za předpokladu, že počáteční aproximace x° leží dostatečně blízko    Řád metody je roven dvěma.
<n><ai> « -o
Jiří Zelinka        Numerické metody 9. přednáška, 15. dubna 2015 24 /