Numerické metody
11. přednáška, 30. dubna 2014
Jiří Zelinka
Jiří Zelinka Numerické metody 11. přednáška, 30. dubna 2014 1 / 9
Řešení systémů lin. rovnic – přímé metody
Opakování
Ax = b, A =



a11 · · · a1n
...
...
an1 · · · ann


, x =



x1
...
xn


, b =



b1
...
bn


.
A – matice soustavy, regulární.
Rozšířená matice soustavy:
(A | b) =





a11 · · · a1n b1
a21 · · · a2n b2
...
...
...
an1 · · · ann bn





Jiří Zelinka Numerické metody 11. přednáška, 30. dubna 2014 2 / 9
Řešení systémů lin. rovnic – přímé metody
Opakování
Ax = b, A =



a11 · · · a1n
...
...
an1 · · · ann


, x =



x1
...
xn


, b =



b1
...
bn


.
A – matice soustavy, regulární.
Rozšířená matice soustavy:
(A | b) =





a11 · · · a1n b1
a21 · · · a2n b2
...
...
...
an1 · · · ann bn





Jiří Zelinka Numerické metody 11. přednáška, 30. dubna 2014 2 / 9
Gaussova eliminační metoda
(A | b) −→ R | ˜b
(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 11. přednáška, 30. dubna 2014 3 / 9
Gaussova eliminace bez výměny řádků:
R | ˜b = Gn−1 · . . . G2 · G1 · (A | b)
R = Gn−1 · . . . G2 · G1 · A ⇒ G−1
1 G−1
2 . . . G−1
n−1R = A.
A = L · R, L = G−1
1 G−1
2 . . . G−1
n−1.
L – dolní trojúhelníková matice.
G−1
i =











1 · · · 0
...
... 1
−li+1,i
...
...
...
0 −lni 1











Jiří Zelinka Numerické metody 11. přednáška, 30. dubna 2014 4 / 9
L = G−1
1 G−1
2 . . . G−1
n−1 =





1 · · · · · · 0
−l21
...
...
...
...
...
−ln1 · · · −ln,n−1 1





.
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ů.
Konec opakování.
Jiří Zelinka Numerické metody 11. přednáška, 30. dubna 2014 5 / 9
Příklad:
LR rozklad matice
A =
0, 0001 1
1 1
.
se zaokrouhlováním na 3 platné číslice.
Výběr vedoucího prvku (pivota) – částečný
Při úpravě i-tého sloupce najdeme mezi prvky a
(i−1)
ii , . . . , a
(i−1)
ni
prvek s maximální absoulutní hodnotou (např. a
(i−1)
ki ), pak
vyměníme i-tý a k-tý řádek.
Výběr vedoucího prvku (pivota) – úplný
Hledáme prvek s maximální absoultní hodnotou mezi a
(i−1)
jk ,
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.
Jiří Zelinka Numerické metody 11. přednáška, 30. dubna 2014 6 / 9
Příklad
2x1 + 4x2 − x3 = −5
x1 + x2 − 3x3 = −9
4x1 + x2 + 2x3 = 9
Jiří Zelinka Numerické metody 11. přednáška, 30. dubna 2014 7 / 9
Věta
Nechť matice A je ryze řádkově diagonálně dominantní.
Pak GEM lze provést bez výměny řádků a sloupců.
Nechť matice A je pozitivně deﬁnitní. Pak GEM lze
provést bez výměny řádků a sloupců.
Věta
Nechť všechny hlavní minory matice A ∈ Mn jsou různé od
nuly, tj.
a11 = 0,
a11 a12
a21 a22
= 0, . . . , det A = 0.
Pak matici A lze rozložit na součin dolní a horní trojúhelníkové
matice.
Jiří Zelinka Numerické metody 11. přednáška, 30. dubna 2014 8 / 9
Věta
Nechť matice A je ryze řádkově diagonálně dominantní.
Pak GEM lze provést bez výměny řádků a sloupců.
Nechť matice A je pozitivně deﬁnitní. Pak GEM lze
provést bez výměny řádků a sloupců.
Věta
Nechť všechny hlavní minory matice A ∈ Mn jsou různé od
nuly, tj.
a11 = 0,
a11 a12
a21 a22
= 0, . . . , det A = 0.
Pak matici A lze rozložit na součin dolní a horní trojúhelníkové
matice.
Jiří Zelinka Numerické metody 11. přednáška, 30. dubna 2014 8 / 9
Choleského rozklad
Věta
Nechť matice A je symetrická a její všechny hlavní minory
matice A ∈ Mn jsou různé od nuly, tj.
a11 = 0,
a11 a12
a21 a22
= 0, . . . , det A = 0.
Pak existuje taková horní trojúhelníková matice T ∈ Mn, že
A = TT
T.
Jiří Zelinka Numerické metody 11. přednáška, 30. dubna 2014 9 / 9