Numerické metody 10. přednáška, 22. dubna 2015
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Jiří Zelinka
Jiří Zelinka        Numerické metody 10. prednáška, 22. dubna 2015 1/15
Řešení systémů lin. rovnic - přímé metody
Základní pojmy
/ 3n
Ax = b, A =
X —
r/7/7
>A - matice soustavy, regulární. Řešení: x = A lb
Rozšířená matice soustavy:
(A\b) =
( 3U 321
3ln 32 n
\ 3nl
' nn
□ [5P
Jiří Zelinka        Numerické metody 10. prednáška, 22. dubna 2015 2/15
A A A
Bij
w =
- dolní trojúhelníková: a;j = 0 pro / < /
- horní trojúhelníková: a,y = 0 pro / > j.
- pásová, jestliže existují p, q, 1 < p, q < n taková, že = 0, jestliže i + p <j nebo j + q < i, šířka pásu
p + q-1.
A - trídiagonální pro p = q = 2.
>4 - ryze řádkově diagonálně dominantní
n
au
>
E
a/,-
/ = 1,..., n.
A - ryze sloupcové diagonálne dominantní - podobně Věta:
Ryze řádkově (sloupcově) diagonálně dominantní matice, je regulární. , n
Numerické metody 10. prednáš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 řešení od poslední 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
/ i   o ...
/Ol o
lc =
0 \
o \
/ 1 o /Ol o
\ o o
i/
1/c
\ o o
0 \
o \
i/
Jiří Zelinka
Numerické metody 10. přednáška, 22. dubna 2015 4/15
2. výměna řádků /, k
í 1 0 O 1
Vo
O
P; k - permutační matice
0\ 0
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/
Pi,k - Pi,k
<[fj]^ -š Q, O
Jiří Zelinka        Numerické metody 10. přednáška, 22. dubna 2015 5/15
přičtení c násobku /-tého řádku ke /r-tému, i < k
( 1 o
0 1
Gi,k,c -
0\ 0
V o
Jiří Zelinka        Numerické metody 10. přednáška, 22. dubna 2015 6/15
i,k,c
( 1 o
O 1
—c
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 /c-tého řádku (v případě potřeby)
(ľ) vynulování prvního sloupce pod hlavní diagonálou
AM\bl1')) = G1-(AW\b<1)), G1
ki = -
f(1)
7c 1
f(1) '11
/   1 ••• hl 1
V U 0
Jiří Zelinka        Numerické metody 10. přednáška, 22. dubna 2015 8/15
(i) výměna /-tého. a /c-tého řádku (v případě potřeby) (i') vynulování /-tého sloupce pod hlavní diagonálou
/ = 2,..., n — 1
Jiří Zelinka        Numerické metody 10. přednáška, 22. dubna 2015 9/15
Gaussova eliminaca bez výmeny řádků:
R | b) = G„_i •... G2 • Gi • (/A | fo)
tedy
odkud
/? — G^—i * . . . (j2 * Gi * /A
G^ ^ G2 ^... G^j^ /? — /A.
-1
Matice G; jsou dolní trojúhelníková, tedy Gx 1 jsou také dolní trojúhelníkové, takže
A = Ľ R
L — G^ ^ G2      Gn .
-1
/_ - dolní trojúhelníková matice
Numerické metody 10. prednáška, 22. dubna 2015 Jiří Zelinka 10/15
i
pak
V
o
L — Gx G2  ... G„\ —
-i
/ 1
-/-
21
V-í
A7l
/n,n-i   1 /
Jiří Zelinka
Numerické metody 10. prednáška, 22. dubna 2015 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 xi +  x2 — 3x3 = —9 4xi + x2 + 2x3 = 9
Jirí Zelinka
Numerické metody 10. prednáška, 22. dubna 2015 13/15
Výběr vedoucího prvku (pivota) - částečný
Při úpravě i-tého sloupce najdeme mezi prvky aj;_1),..., a^_1)
(i   1 ^
prvek s maximální absoulutní hodnotou (např. a^- }), pak vyměníme /-tý a k-tý řádek.
Výběr vedoucího prvku (pivota) - úplný
(i   1 ^
Hledáme prvek s maximální absoultní hodnotou mezi , i <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
A =
0,0001
1
se zaokrouhlováním na 3 platné číslice.
Jiří Zelinka
Numerické metody 10. prednáška, 22. dubna 2015 14/15
Veta
Nechť všechny hlavní minory matice A G A4„ jsou různé od nuly, tj.
311 Ž 0.
3ll 3i2 321 ^22
/o
au  ai2 ai3
321    ^22 ^23 332 333
^ 0, ... det/A ^ 0.
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ů.
Jiří Zelinka
Numerické metody 10. prednáška, 22. dubna 2015 15/15