Cvičení z Numerických metod I - 12.týden
Přímé metody řešení systému lineárních rovnic
Máme systém lineárních rovnic
Ax = b, A
Budeme hledat přesné řešení soustavy x*
din ^ í X\ \
v < /
b
\bn J
Nejznámější metodou je Gaussova eliminační metoda (GEM). Hlavní myšlenkou je převést zadaný systém ekvivalentními úpravami na redukovaný problém, tj. na systém s horní trojúhelníkovou maticí Rx = c. Z toho systému pomocí zpětného chodu jednoduše získáme přesné řešení x*. Zároveň pomocí GEM můžeme získat rozklad matice A na součin dolní a horní trojúhelníkové matice.
GEM: (A|b)-----(R|c)
Ukážeme si několik modifikací GEM:
1. GEM bez výměny řádků
• neměníme pořadí řádků (ne vždy je to možné - některý pivot může být nulový a nelze pokračovat)
• násobky prvního řádku odečítáme od ostatních řádků, abychom pod prvním prvkem prvního řádku (hlavní prvek, pivot) získali nuly
• pokud máme nuly pod pivotem prvního řádku, uděláme totéž pod prvkem na diagonále druhého řádku (pivot druhého řádku)
• postup dále opakujeme podle velikosti matice
• na konci získáme (R|c), kde R je horní trojúhelníková matice
• zároveň získáme rozklad matice A = LR, kde L je dolní trojúhelníková matice obsahující multiplikátory, kterými jsme násobili jednotlivé řádky
2. GEM s částečným výběrem pivota
• v prvním sloupci najdeme největší prvek v absolutní hodnotě
• řádek s tímto prvkem vyměníme s prvním řádkem a prvky pod tímto pivotem vynulujeme
• v druhém sloupci (bez prvního řádku) najdeme největší prvek v absolutní hodnotě
• řádek s tímto prvkem vyměníme s druhým řádkem a prvky pod tímto pivotem vynulujeme
• postup dále opakujeme podle velikosti matice
• na konci získáme (R|c), kde R je horní trojúhelníková matice
• zároveň získáme rozklad matice PA = LR, kde L je dolní trojúhelníková matice obsahující multiplikátory, kterými jsme násobili jednotlivé řádky, a matice P je permutační matice (ukazuje, které řádky jsme museli vyměnit)
Věta Nechť jsou hlavní minory matice A různé od nuly. Pak lze provést GEM bez výměny řádků, tj. matici A lze rozložit na součin dolní a horní trojúhelníkové matice.
1
Příklad Řešte systém lineárních rovnic
2x1 2x1 -3xi
6x2 3x2 6x2
x3 x3
3
4 -3
1. GEM bez výměny řádků
Pro náš systém je rozšířená matice soustavy:
2 6-1 2     3 1 -3  -6 0
První řádek vynásobíme 1 a odečteme od druhého. První řádek vynásobíme 2 třetího. Prvky dolní trojúhelníkové matice L tedy budou I21 = 1 a /31 = — |. Získáme
3 a odečteme od
6 -3 3
Druhý řádek vynásobíme -1 a odečteme od druhého. Prvek dolní trojúhelníkové matice L tedy bude /32 = —1. Získáme
Řešení systému rovnic tedy je
x3
x2
X\
6 -3 0
5/2 I72
1-2-5
-3 3 + 5
5
3
6-3
Rozklad matice A je
A = LR
6 -3 0
2. GEM s částečným výběrem pivota
Začneme se stejnou rozšířenou maticí soustavy:
2 6-1 2     3 1 -3  -6 0
Z prvního sloupce vybereme největší číslo v absolutní hodnotě. To je -3 ve třetím řádku.
/ 0  0 1
Vyměníme tedy třetí řádek s prvním. To odpovídá permutační matici Pi =  I  0   1 0
\ 1  0 0
Získáme
0
1
-1
První řádek vynásobíme — § a odečteme od druhého, resp. od třetího. Prvky dolní trojúhelníkové matice L tedy budou /21 = — f a /31 = — |. Získáme
V druhém sloupci vybereme největší prvek v absolutní hodnotě (bez prvního řádku). To je 2 ve třetím řádku. Vyměníme tedy třetí a druhý řádek. To odpovídá permutační matici P2 = 1  0  0 \
0  0   1. Pozor, musíme vyměnit i již získané prvky matice L. Získáme 0 10/
-3 -6 0 2 0 -1
Druhý řádek vynásobíme odečteme od druhého. Prvek dolní trojúhelníkové matice L tedy bude Z32 :
•|. Získáme
Řešení systému rovnic tedy je
-3 0 0
x3
-6 2 0
5^ = 5
1/2
2
-3 + 6- 3
Celková permutační matice je
a rozklad matice PA tedy je
PA
P2P1
-3 0 0
-6 2 0
Další modifikací GEM by mohla být GEM s úplným výběrem pivota. Ukážeme si ji rovnou při řešení systému lineárních rovnic z předchozího příkladu. Začneme opět s rozšířenou maticí soustavy:
2 6-1 2     3 1 -3  -6 0
Vybereme největší číslo v absolutní hodnotě v celé matici A. To je 6 v prvním řádku a druhém sloupci nebo -6 ve třetím řádku a druhém sloupci. Můžeme si tedy vybrat a řádek s tímto prvkem přesuneme na první řádek. My vybereme prvek v prvním řádku a druhém sloupci, nemusíme tedy žádné řádky měnit. Vynulujeme všechny prvky ve druhém sloupci pod tímto prvkem. První řádek
3
vynásobíme | a odečteme od druhého, podobně první řádek vynásobíme -la odečteme od třetího. Získáme
-1
3 2
-1
V submatici bez prvního řádku a druhého sloupce vybereme největší prvek v absolutní hodnotě. To jsou | v druhém řádku a třetím sloupci. Řádek s tímto prvkem bychom přesunuli na druhý řádek, to už opět máme. Prvky pod tímto prvkem vynulujeme. Druhý řádek vynásobíme — | a odečteme od třetího. Získáme
Z této rozšířené matice jednoduše získáme řešení soustavy
5/3
x3
x2
-5
5
-1/3 5/2 + 5
2/3 3 + 5 + 2-5 6
Na závěr se podíváme na obecný rozklad matice A na součin dolní a horní trojúhelníkové matice - obecný LU rozklad. Zároveň si ukážeme, jak tento rozklad využít při řešení soustav lineárních rovnic.
Obecný LU rozklad ukážeme opět na předchozím příkladu soustavy lineárních rovnic. Máme
A
Rozklad matice A si zapíšeme obecně.
2 2 -3
6 3 -6
a b
3
4
A
2 2 -3
6 3 -6
11	0	0
21	^22	0
31	^32	^33
hiun hiu12
kiun   h\U\2 + /22M22 h\U\z
kiuu  hiu12 + /32M22  hiui-s + /32M23
^33M33
Porovnáním jednotlivých prvků matic získáme 9 rovnic pro 12 neznámých, řešení tedy není jednoznačné. Můžeme například předpokládat, že na diagonále dolní trojúhelníkové matice L jsou 1, tedy ^11 = ^22 = ^33 = 1- Pak dostaneme
a U
6 -3 0
Nyní přistoupíme k řešení soustavy Ax = b. Tu můžeme přepsat jako LUx = b. Řešení soustavy najdeme postupným vyřešením dvou soustav lineárních rovnic s trojúhelníkovými maticemi:
Lz
Ux
b z
Tedy
3
4
Řešení této soustavy jez
. Poté řešíme další soustavu
3
1
5
2
Vyřešením získáme konečné řešení soustavy x
3
5
5