ˇ sen´ı soustav line´arn´ıch rovnic Reˇ
ˇ sen´ı soustav line´ Reˇ arn´ıch rovnic
Pˇripomenut´ı – co je to soustava line´arn´ıch rovnic Pˇr´ıklad 2x −3x x
− 3y + 5y + 2y
+ z + 2z − z
= 5 = −4 = 1
Soustava line´arn´ıch rovnic obecnˇe a11 x1 + a12 x2 + · · · a21 x1 + a22 x2 + · · · .. .
+ a1n xn = b1 + a2n xn = b2 .. .
an1 x1 + an2 x2 + · · ·
+ ann xn = bn
Maticov´y tvar: Ax = b.
ˇ sen´ı soustav line´ Reˇ arn´ıch rovnic
V praxi se vyskytuj´ı velmi velk´e soustavy rovnic, ˇcasto s tzv. ˇr´ıdkou matic´ı (v kaˇzd´em ˇr´adku je jen nˇekolik nenulov´ych prvk˚ u).
Metody ˇreˇsen´ı soustav line´arn´ıch rovnic I
Pˇr´ım´ e – po koneˇcn´em poˇctu matematick´ych operac´ı dojdeme pˇr´ımo ˇ sen´ı ve skuteˇcnosti kv˚ k pˇresn´emu“ ˇreˇsen´ı. (Reˇ uli ” zaokrouhlovac´ım chyb´am pˇresn´e b´yt nemus´ı.)
I
Iteraˇ cn´ı – zvol´ıme poˇc´ateˇcn´ı aproximaci ˇreˇsen´ı a postupnˇe ji zlepˇsujeme. K pˇresn´emu ˇreˇsen´ı bychom se obecnˇe dostali aˇz v limitˇe (tj. nekoneˇcn´ym poˇctem krok˚ u).
ˇ sen´ı soustav line´ Reˇ arn´ıch rovnic
Pˇr´ım´e metody
I
Cramerovo pravidlo
I
Gaussova eliminaˇcn´ı metoda
I
. . . (existuj´ı i dalˇs´ı metody)
ˇ sen´ı soustav line´ Reˇ arn´ıch rovnic
Cramerovo pravidlo Je-li matice soustavy A regul´arn´ı, tj. jej´ı determinant je nenulov´y, pak ˇreˇsen´ı soustavy lze vypoˇc´ıtat jako x1 =
D2 Dn D1 , x2 = , . . . , xn = D D D
kde D je determinant matice soustavy A a Dk , k = 1, . . . , n, jsou determinanty matic, kter´e vzniknou tak, ˇze v A nahrad´ıme k-t´y sloupec vektorem prav´ych stran b. Cramerovo pravidlo je vhodn´ e jen pro velmi mal´ e soustavy.
ˇ sen´ı soustav line´ Reˇ arn´ıch rovnic
Gaussova eliminaˇcn´ı metoda Soustavu pomoc´ı element´arn´ıch u ´prav pˇrevedeme na troj´ uheln´ıkov´y tvar, ze kter´eho se ˇreˇsen´ı snadno spoˇc´ıt´a pomoc´ı tzv. zpˇetn´eho chodu. P˚ uvodn´ı soustava: a11 x1 + a12 x2 + · · · a21 x1 + a22 x2 + · · · .. .
+ a1n xn = b1 + a2n xn = b2 .. .
an1 x1 + an2 x2 + · · ·
+ ann xn = bn
Upraven´a soustava: ˜a11 x1 + ˜a12 x2 + · · · ˜a22 x2 + · · ·
+ ˜a1n xn = b˜1 + ˜a2n xn = b˜2 .. . ˜ann xn = b˜n
ˇ sen´ı soustav line´ Reˇ arn´ıch rovnic
Pˇr´ıklad Gaussovou eliminaˇcn´ı metodou najdˇete ˇreˇsen´ı soustavy 2x −3x x
− 3y + 5y + 2y
+ z + 2z − z
= 5 = −4 = 1
ˇ sen´ı soustav line´ Reˇ arn´ıch rovnic
2 −3 1 5 /· 32 −3 5 2 −4 1 2 −1 1
2 0 0
/· − 21
2 ∼ 0 0
2 −3 1 5 3,5 0,5 3,5 3,5 /· − 0,5 ∼ 0 0 3,5 −1,5 −1,5
2x −
3y + z = 5 0,5y + 3,5z = 3,5 − 26z = −26
−3 1 5 0,5 3,5 3,5 3,5 −1,5 −1,5 −3 0,5 0
1 3,5 −26
⇒ x =2 ⇒ y =0 ⇒ z =1
5 3,5 −26
ˇ sen´ı soustav line´ Reˇ arn´ıch rovnic
Nev´yhody Gaussovy eliminaˇcn´ı metody I
V´ypoˇcet je ˇcasovˇe n´aroˇcn´y, potˇrebn´ych aritmetick´ych operac´ı je ˇr´adovˇe n3 /3.
I
Pˇri v´ypoˇctu se mohou hromadit zaokrouhlovac´ı chyby.
ˇ sen´ı soustav line´ Reˇ arn´ıch rovnic
Pˇr´ıklad Gaussovou eliminaˇcn´ı metodou najdˇete ˇreˇsen´ı soustavy 0,0001x x
+ y + y
= 1 = 2.
Pˇri v´ypoˇctu zaokrouhlujte na 3 platn´e ˇc´ıslice.
ˇ sen´ı soustav line´ Reˇ arn´ıch rovnic
Eliminace s ˇc´asteˇcn´ym v´ybˇerem hlavn´ıho prvku Slouˇz´ı k minimalizaci zaokrouhlovac´ıch chyb. Pro eliminaci prvk˚ u v k-t´em sloupci pouˇz´ıv´ame n´asobky toho ˇr´adku (vyb´ır´ame z k-t´eho aˇz n-t´eho ˇr´adku), ve kter´em m´a ˇc´ıslo v k-t´em sloupci nejvˇetˇs´ı absolutn´ı hodnotu. Toto ˇc´ıslo s nejvˇetˇs´ı absolutn´ı hodnotou naz´yv´ame hlavn´ı prvek nebo t´eˇz pivot.
ˇ sen´ı soustav line´ Reˇ arn´ıch rovnic
Pˇr´ıklad Pomoc´ı eliminace s ˇc´asteˇcn´ym v´ybˇerem hlavn´ıho prvku najdˇete ˇreˇsen´ı soustavy −x 2x −10x
+ 7,5y − 2y − 5y
+ 2z − 8z
= 16 = −4 = −8
ˇ sen´ı soustav line´ Reˇ arn´ıch rovnic
2 1 −1 7,5 0 16 −10 −5 −8 −8 /· 10 /· − 10 2 −2 2 −4 ∼ 2 −2 2 −4 ∼ −10 −5 −8 −8 −1 7,5 0 16
−10 −5 −8 −8 −10 −5 −8 −8 0 −3 0,4 −5,6 ∼ 0 8 0,8 16,8 /· 3 8 0 8 0,8 16,8 0 −3 0,4 −5,6 −10 −5 −8 0 8 0,8 0 0 0,7
∼
−8 16,8 0,7
−10x − 5y − 8z = −8 8y + 0,8z = 16,8 0,7z = 0,7
⇒ x = −1 ⇒ y =2 ⇒ z =1
ˇ sen´ı soustav line´ Reˇ arn´ıch rovnic
Iteraˇcn´ı metody
I
Jacobiho metoda
I
Gauss-Seidelova metoda
I
. . . (existuj´ı i dalˇs´ı metody)
ˇ sen´ı soustav line´ Reˇ arn´ıch rovnic
Jacobiho metoda Z 1. rovnice vyj´adˇr´ıme 1. nezn´amou, z 2. rovnice 2. nezn´amou atd. (0) (0) (0) Zvol´ıme poˇc´ateˇcn´ı aproximaci ˇreˇsen´ı x(0) = (x1 , x2 , . . . , xn )T , dosad´ıme – vypoˇcteme x(1) , opˇet dosad´ıme atd.: (k+1)
=
(k+1)
=
x1 x2
1 (k) (k) (k) b1 − a12 x2 − a13 x3 − · · · − a1n xn a11 1 (k) (k) (k) b2 − a21 x1 − a23 x3 − · · · − a2n xn a22
.. . (k+1)
xn
=
1 (k) (k) (k) bn − an1 x1 − an2 x2 − · · · − an n−1 xn−1 , ann
Pokraˇcujeme, dokud se vˇsechny sloˇzky ˇreˇsen´ı neust´al´ı, tj. dokud neplat´ı (k+1)
|xi
(k)
− xi | < ε
pro vˇsechna i = 1, . . . , n.
ˇ sen´ı soustav line´ Reˇ arn´ıch rovnic
Konvergence a divergence metody ˇ sen´ı pomoc´ı Jacobiho metody nemus´ıme naj´ıt vˇzdy. Reˇ Jestliˇze se postupn´e aproximace k ˇreˇsen´ı bl´ıˇz´ı, ˇrekneme, ˇze metoda konverguje. Jestliˇze ˇreˇsen´ı nenajdeme, ˇrekneme, ˇze metoda diverguje.
ˇ sen´ı soustav line´ Reˇ arn´ıch rovnic
Podm´ınky konvergence pro Jacobiho metodu Diagon´alnˇe dominantn´ı matice Matice A se naz´yv´a ˇr´ adkovˇ e ostˇre diagon´ alnˇ e dominantn´ı, jestliˇze je v kaˇzd´em ˇr´adku absolutn´ı hodnota prvku na diagon´ale vˇetˇs´ı neˇz souˇcet absolutn´ıch hodnot vˇsech ostatn´ıch prvk˚ u v onom ˇr´adku neboli jestliˇze | aii | >
n X
| aij |
pro i = 1, . . . , n
j=1,j6=i
Podobnˇe definujeme sloupcovˇ e ostˇre diagon´ alnˇ e dominantn´ı matici: n X | ajj | > | aij | pro j = 1, . . . , n. i=1,i6=j
ˇ sen´ı soustav line´ Reˇ arn´ıch rovnic
Podm´ınky konvergence pro Jacobiho metodu Je-li matice A ostˇre ˇr´adkovˇe nebo sloupcovˇe diagon´alnˇe dominantn´ı, pak Jacobiho metoda konverguje pro libovolnou poˇc´ateˇcn´ı aproximaci x(0) . Jestliˇze matice nen´ı diagon´alnˇe dominantn´ı, Jacobiho metoda konvergovat m˚ uˇze a nemus´ı.
ˇ sen´ı soustav line´ Reˇ arn´ıch rovnic
Gauss-Seidelova metoda Poˇc´ıt´ame podobnˇe jako u Jacobiho metody, ale v kaˇzd´em kroku pouˇzijeme nejnovˇejˇs´ı hodnoty nezn´am´ych: (k+1)
=
(k+1)
=
(k+1)
=
x1 x2 x3
1 (k) (k) (k) b1 − a12 x2 − a13 x3 − · · · − a1n xn a11 1 (k+1) (k) (k) b2 − a21 x1 − a23 x3 − · · · − a2n xn a22 1 (k+1) (k+1) (k) b3 − a31 x1 − a32 x2 − · · · − a3n xn a33
.. . (k+1)
xn
=
1 (k+1) (k+1) (k+1) bn − an1 x1 − an2 x2 − · · · − an n−1 xn−1 ann
ˇ sen´ı soustav line´ Reˇ arn´ıch rovnic
Podm´ınky konvergence pro Gauss-Seidelovu metodu
Pozitivnˇe definitn´ı matice Symetrick´ a matice A se naz´yv´a pozitivnˇ e definitn´ı, jestliˇze pro kaˇzd´y nenulov´y sloupcov´y vektor x = (x1 , . . . , xn )T plat´ı xT A x > 0 Jestliˇze libovolnou regul´arn´ı matici A vyn´asob´ıme matic´ı k n´ı transponovanou, dostaneme matici, kter´a je symetrick´a a pozitivnˇe definitn´ı.
ˇ sen´ı soustav line´ Reˇ arn´ıch rovnic
Podm´ınky konvergence pro Gauss-Seidelovu metodu Je-li matice A ostˇre ˇr´adkovˇe nebo sloupcovˇe diagon´alnˇe dominantn´ı, pak Gauss-Seidelova metoda konverguje pro libovolnou poˇc´ateˇcn´ı aproximaci x(0) . Je-li matice A symetrick´a pozitivnˇe definitn´ı, pak Gauss-Seidelova metoda konverguje pro libovolnou poˇc´ateˇcn´ı aproximaci x(0) . Jestliˇze matice nem´a ˇz´adnou z uveden´ych vlastnost´ı, Gauss-Seidelova metoda konvergovat m˚ uˇze a nemus´ı.
ˇ sen´ı soustav line´ Reˇ arn´ıch rovnic
Jak zaruˇcit konvergenci Gauss-Seidelovy metody Vyn´asob´ıme-li p˚ uvodn´ı soustavu Ax = b matic´ı k A transponovanou: AT Ax = AT b, dostaneme soustavu s pozitivnˇe definitn´ı matic´ı, pro kterou je konvergence zaruˇcena (m˚ uˇze b´yt ovˇsem dosti pomal´a).
ˇ sen´ı soustav line´ Reˇ arn´ıch rovnic
Jacobiho a Gauss-Seidelova metoda se nejl´epe hod´ı pro velk´e soustavy rovnic s ˇr´ıdkou matic´ı.
ˇ sen´ı soustav line´ Reˇ arn´ıch rovnic
Dalˇs´ı pouˇz´ıvan´e metody I
Metoda LU rozkladu
I
Cholesk´eho rozklad
I
Metoda sdruˇzen´ych gradient˚ u
I
...
