Numerické metody
10. přednáška, 23. dubna 2014
Jiří Zelinka
Jiří Zelinka Numerické metody 10. přednáška, 23. dubna 2014 1 / 12
Řešení systémů lin. rovnic – přímé metody
Základní pojmy
Ax = b, A =



a11 · · · a1n
...
...
an1 · · · ann


, x =



x1
...
xn


, b =



b1
...
bn


.
A – matice soustavy, regulární. Řešení: ˜x = A−1
b
Rozšířená matice soustavy:
(A | b) =





a11 · · · a1n b1
a21 · · · a2n b2
...
...
...
an1 · · · ann bn





Jiří Zelinka Numerické metody 10. přednáška, 23. dubna 2014 2 / 12
Řešení systémů lin. rovnic – přímé metody
Základní pojmy
Ax = b, A =



a11 · · · a1n
...
...
an1 · · · ann


, x =



x1
...
xn


, b =



b1
...
bn


.
A – matice soustavy, regulární. Řešení: ˜x = A−1
b
Rozšířená matice soustavy:
(A | b) =





a11 · · · a1n b1
a21 · · · a2n b2
...
...
...
an1 · · · ann bn





Jiří Zelinka Numerické metody 10. přednáška, 23. dubna 2014 2 / 12
A – dolní trojúhelníková: aij = 0 pro i < j.
A – horní trojúhelníková: aij = 0 pro i > j.
A – pásová, jestliže existují p, q, 1 < p, q < n taková, že
aij = 0, jestliže i + 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í
|aii | >
n
j=1
j=i
|aij |, i = 1, . . . , n.
A – ryze sloupcově diagonálně dominantní – podobně
Věta:
Ryze řádkově (sloupcově) diagonálně dominantní matice, je
regulární.
Jiří Zelinka Numerické metody 10. přednáška, 23. dubna 2014 3 / 12
Gaussova eliminační metoda
Úprava soustavy na soustavu s horní trojúhelníkovou maticí R:
(A | b) −→ R | ˜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
Ic =






1 0 · · · · · · · · · 0
0 1 0 · · · · · · 0
.
.
.
.
.
.
.
.
.
.
.
. c
.
.
.
..
.
.
.
.
0 0 · · · · · · · · · 1






, I−1
c =






1 0 · · · · · · · · · 0
0 1 0 · · · · · · 0
.
.
.
.
.
.
.
.
.
.
.
. 1/c
.
.
.
..
.
.
.
.
0 0 · · · · · · · · · 1






Jiří Zelinka Numerické metody 10. přednáška, 23. dubna 2014 4 / 12
2. výměna řádků i, k
,k =






















1 0 · · · 0
0 1 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
...
...
0 0 1






















, P−1
i,k = Pi,k
Pi,k – permutační matice
Jiří Zelinka Numerické metody 10. přednáška, 23. dubna 2014 5 / 12
3. přičtení c násobku i-tého řádku ke k-tému, i < k
Gi,k,c =
i
k














1 0 · · · 0
0 1 · · · 0
...
...
1
...
c 1
...
0 1














.
Jiří Zelinka Numerické metody 10. přednáška, 23. dubna 2014 6 / 12
G−1
i,k,c =
i
k














1 0 · · · 0
0 1 · · · 0
...
...
1
...
−c 1
...
0 1














.
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, 23. dubna 2014 7 / 12
Postup při Gaussově eliminaci
(1) výměna 1. a k-tého řádku (v případě potřeby)
(A | b) −→ A(1)
| ˜b
(1)
, A(1)
| ˜b
(1)
= P1,k · (A | b)
(1’) vynulování prvního sloupce pod hlavní diagonálou
A(1 )
| ˜b
(1 )
= G1· A(1)
| ˜b
(1)
, G1 =





1 · · · · · · 0
l21 1
...
...
...
ln1 0 · · · 1





,
lk1 = −
a
(1)
k1
a
(1)
11
Jiří Zelinka Numerické metody 10. přednáška, 23. dubna 2014 8 / 12
(i) výměna i-tého. a k-tého řádku (v případě potřeby)
A(i)
| ˜b
(i)
= Pi,k · A(i−1 )
| ˜b
(i−1 )
(i’) vynulování i-tého sloupce pod hlavní diagonálou
A(i )
| ˜b
(i )
= Gi · A(i)
| ˜b
(i)
,
Gi =











1 · · · 0
...
... 1
li+1,i
...
...
...
0 ln,i 1











, lki = −
a
(i)
ki
a
(i)
ii
i = 2, . . . , n − 1
Jiří Zelinka Numerické metody 10. přednáška, 23. dubna 2014 9 / 12
Gaussova eliminaca bez výměny řádků:
R | ˜b = Gn−1 · . . . G2 · G1 · (A | b)
tedy
R = Gn−1 · . . . G2 · G1 · A
odkud
G−1
1 G−1
2 . . . G−1
n−1R = A.
Matice Gi jsou dolní trojúhelníková, tedy G−i
1 jsou také dolní
trojúhelníkové, takže
A = L · R, L = G−1
1 G−1
2 . . . G−1
n−1.
L – dolní trojúhelníková matice.
Jiří Zelinka
Numerické metody 10. přednáška, 23. dubna 2014
10 / 12
G−1
i =











1 · · · 0
...
... 1
−li+1,i
...
...
...
0 −lni 1











,
pak
L = G−1
1 G−1
2 . . . G−1
n−1 =





1 · · · · · · 0
−l21
...
...
...
...
...
−ln1 · · · −ln,n−1 1





.
Jiří Zelinka
Numerické metody 10. přednáška, 23. dubna 2014
11 / 12
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.
Jiří Zelinka
Numerické metody 10. přednáška, 23. dubna 2014
12 / 12