Řešení systémů lin. rovnic - přímé metody
Základní pojmy
		•   aln \		Í"'	\		( bl \
Ax = b, A =						,b =	
	\ a„i	&nn J		\ Xn	)		{bnJ
A - matice soustavy, regulární. Řešení: x = A 1b Rozšířená matice soustavy:
(A\b)
(au ■ ■ ■ a\n y an\   ■ ■ ■ ann
bi \ b2
bn J
□ ►   4 flP I
1 -O^O-
Jin Zelinka        Numerické metody 10. přednáška, 22. dubna 2015 2/15
A - dolní trojúhelníková: a,y = 0 pro / < j.
A - horní trojúhelníková: a,y = 0 pro / > j.
A - pásová, jestliže existují p, q, 1 < p, q < n taková, že a,j = 0, jestliže / + p < j nebo j + q < i, šířka pásu w = p + q — 1.
A - třídiagonální pro p = q = 2.
A - ryze řádkově diagonálně dominantní
n
\an\ >      la«l'      ' = !,•••,"•
/4 - ryze sloupcově diagonálně dominantní - podobně Věta:
Ryze řádkově (sloupcově) diagonálně dominantní matice, je regulární. _<n> <a>       <a>   , ^
Jiří Zelinka        Numerické metody 10. přednáška, 22. dubna 2015 3/15
Gaussova eliminační metoda
Úprava soustavy na soustavu s horní trojúhelníkovou maticí R:
(A\b)
R I b
Pak provádíme tzv. zpětný chod - počítáme složky k první.
Elementární úpravy a matice úprav
Nemění řešení, každá úprava má inverzi.
1. násobení řádku nenulovou konstantou c
/  1    o ......... 0 \ /  1 o
01     o ...... o\ 10 1
\ o   o ......... 1/ \ o o
...... o \
...... o '
... J
Jiří Zelinka        Numerické metody 10. přednáška, 22. dubna 2015 4/15
2. výměna řádků /', k
/l O O 1
V o o
P-,k - permutační matice
0\ O
1	0	0 ••	• 0	0	0 ••	• 0
0	0	0 ••	• 0	1	0 ••	• 0
0	0	1		0	0 ••	• 0
0	0		1	0	0 ••	• 0
0	1	0 ••	• 0	0	0 ••	• 0
0	0	0 ••	• 0	0	1	
1 /
4 □ ► 4 O ► < < ► « < ►     < -O^O-Jin Zelinka        Numerické metody 10. přednáška, 22. dubna 2015 5/15
3. přičtení c násobku /-tého řádku ke /r-tému, i < k
/l 0 0 1
Gi.
k,c
o
i/
<n>4ď> « -O^O-
Jin Zelinka        Numerické metody 10. přednáška, 22. dubna 2015 6/15
Gi,k,c
/i o
O 1
o
Ve skutečnosti pro převod na trojúhelníkovou matici stačí 2. a 3. elementární úprava.
Jiří Zelinka        Numerické metody 10. přednáška, 22. dubna 2015 7/15
Postup pri Gaussove eliminaci
(1) výměna 1. a /r-tého řádku (v případě potřeby)
{A | b) (AM I , (AM I = P1Jt ■ (A | b) (ľ) vynulování prvního sloupce pod hlavní diagonálou
(AM\bll')) = G1.(AW\ti1)), G,
iki
a(1) ZKL
a(1)
/ 1 ••• /21 1
0\
<n>-«flP> -š -O^O-
Jin Zelinka        Numerické metody 10. přednáška, 22. dubna 2015 8/15
(i) výměna /-tého. a /r-tého řádku (v případě potřeby)
>ifa(í)) = p,ví^'ir1T
(i') vynulování /-tého sloupce pod hlavní diagonálou
>") | b"1) = G; ■ (A* I
0\
/1
4/
a® n
i = 2,..., n - 1
Jiří Zelinka        Numerické metody 10. přednáška, 22. dubna 2015 9/15
Gaussova eliminaca bez výmeny řádků:
(/? | bj = Gn_x ■...G2-G1-(A\b)
tedy
R = Gn _i •... G2 • Gi • A
odkud
G11G21...Gn\R = A.
Matice G; jsou dolní trojúhelníková, tedy G{' jsou také dolní trojúhelníkové, takže
A = L-R, L=G1-1G21...Gn\.
L - dolní trojúhelníková matice.
,    Numerické metody 10. přednáška, 22. dubna 2015 Jiří Zelinka        10 / 15
íl
G;
-1
1
pak
1°
/. - G-l 1G21... Gn _\
-/21 V "/„I
-/n,n-l    1 /
i    Numerické metody 10- přednáška, 22. dubna 2015 Jiří Zelinka 11/15
LR rozklad
A = L - R: LR (též LU) rozklad matice A
Použití při řešení soustavy: substituce Rx = y, řešíme soustavu Ly = b s dolní trojúhelníkovou maticí, pak Rx = y s horní trojúhelníkovou maticí. LR rozklad s výměnou řádků
Provádíme LR rozklad matice P ■ A, kde P je vhodná permutační matice, která provádí výměnu řádků. Při praktickém výpočtu, pokud narazíme na potřebu vyměnit řádky, postupujeme takto:
Pokud bychom vyměnili řádky předem, v už vypočítané části matice L by tyto řádky byly vyměněny, zbytek by se nezměnil. Proto můžeme vyměnit řádky ve vypočítané části matice L. Dále v pomocném vektoru p na začátku nastaveném na (1, 2,..., n)T zaznamenáme výměnu řádků, tedy vyměníme v něm stejné řádky.
Numerické metody 10. přednáška, 22. dubna 2015 Jiří Zelinka 12/15
Príklad
2xi + 4x2 -  x3 = -5
*i + x2 — 3x3 = -9
4xi +  x2 + 2x3 = 9
Výběr vedoucího prvku (pivota) - částečný
Při úpravě /-tého sloupce najdeme mezi prvky a|('_1\ ..., a^-1^ prvek s maximální absoulutní hodnotou (např. a^-1^), pak vyměníme /-tý a /r-tý řádek. Výběr vedoucího prvku (pivota) - úplný
Hledáme prvek s maximální absoultní hodnotou mezi a^k_1\ / < j < n, i < k < n, pak vyměníme příslušný řádek a spoupec, čímž se změní pořadí proměnných.
Příklad:
LR rozklad matice
0,0001 1 1 1
se zaokrouhlováním na 3 platné číslice.
Numerické metody 10. přednáška, 22. dubna 2015 Jiří Zelinka 14/15
Veta
Nechť všechny hlavní minory matice A E M.n jsou různé od nuly, tj.
3ll Ý 0,
3ll 3i2 321 322
det/\ t^O.
Pak matici A lze rozložit na součin dolní a horní trojúhelníkové matice.
Důsledky
• Nechť matice A je pozitivně definitní. Pak GEM lze provést bez výměny řádků a sloupců.
• Nechť matice A je ryze řádkově diagonálně dominantní. Pak GEM lze provést bez výměny řádků a sloupců.
I    Numerické metody 10. přednáška, 22. dubna 2015 Jiří Zelinka        15 / 15