Iteraˇcn´ı metody ver. 2.3.2016
Normy matic Pˇ r´ıklad 1 Je d´ ana matice A a vektor y:
2 A= 3 −3
0 −4 −2
y=
2 −2
Spoˇctˇete vˇsechny jejich normy (vektor je tak´e matice, typu n × 1). Ovˇeˇrte, ˇze plat´ı ||Ay|| ≤ ||A|| · ||y||
(1)
ˇ sen´ı Reˇ Ay = (4, 14, −2)T Frobeniova yvan´a Euklidovsk´ p norma - tak´e nˇekdy naz´ √a : ||A||2 = p 22 + 02 + 32 + (−4)2 + (−3)2 + (−2)2 = 42 = 6.4807 √ ||y||2 = p 22 + (−2)2 = 8 = 2.8284 ||Ay||2 = 42 + 142 + (−2)2 = 14.6969 14.6969 ≤ 6.4807 · 2.8284 = 18.3300 Sloupcov´ a norma (po sloupc´ıch seˇcteme absolutn´ı hodnoty prvk˚ u matice a z nich vybereme maximum): ||A||1 = max( |2| + |3| + | − 3|, 0 + | − 4| + | − 2|) = max( 8, 6) = 8 ||y||1 = |2| + | − 2| = 4 ||Ay||1 = |4| + |14| + | − 2| = 20 20 ≤ 8 · 4 = 32 ˇ adkov´ R´ a norma (po ˇr´ adc´ıch seˇcteme absolutn´ı hodnoty prvk˚ u matice a z nich vybereme maximum): ||A||∞ = max( |2| + 0, |3| + | − 4|, | − 3| + | − 2|) = max( 2, 7, 5) = 7 ||y||∞ = max( |2|, | − 2|) = 2 ||Ay||∞ = max( |4|, |14|, | − 2|) = 14 14 ≤ 7 · 2 = 14 Pozor: ve vztahu (1) nesm´ıme m´ıchat r˚ uzn´e typy norem! Zkuste porovnat napˇr´ıklad ||Ay||1 a ||A||2 , ||y||2 .
1
c
Certik
Iteraˇcn´ı metody ver. 2.3.2016
Spektr´ aln´ı polomˇ er Pˇ r´ıklad 2 Urˇcete spektr´ aln´ı polomˇer matice A=
−2 1
−1 −2
a ovˇeˇrte, ˇze plat´ı ρ(A) ≤ ||A|| pro libovolnou normu t´eto matice. ˇ sen´ı Reˇ det(A − λI) = (−2 − λ)2 + 1 = λ2 + 4λ + 5 = 0 ⇔ λ1,2 = −2 ± i p √ |λ1,2 | = (−2)2 + (±1)2 = 5 √ √ √ ρ(A) = max( |λ1 |, |λ2 |) = max( 5, 5) = 5 = 2.2361 p √ ||A||2 = (−2)2 + (−1)2 + 12 + (−2)2 = 10 = 3.1623 ||A||1 = ||A||∞ = max( | − 2| + | − 1|, |1| + | − 2|) = max( 3, 3) = 3 2.2361 < 3.1623,
2.2361 < 3 .
Symetrie, pozitivn´ı definitnost, diagon´ aln´ı dominance Pˇ r´ıklad 3 Jsou d´ any matice −5 −1 0 3 1 A= 3 1 −1 2
−1 0 2 −1 −1 2
1 B = −1 0
1 C = −1 0
−1 0 1 1 1 2
a) Kter´ a z nich je symetrick´ a? b) Kter´ a je ostˇre diagon´ alnˇe dominantn´ı? c) Kter´ a je symetrick´ a pozitivnˇe definitn´ı? ˇ sen´ı Reˇ a) Matice B a C jsou symetrick´e, matice A nen´ı. b) Matice je diagon´ alnˇe dominantn´ı (zkr´acenˇe d.d.), pr´avˇe kdyˇz absolutn´ı hodnota prvku na diagon´ ale je vˇetˇs´ı nebo rovna souˇctu absolutn´ıch hodnot ostatn´ıch ˇ pro vˇsechny ˇr´adky, nebo pro vˇsechny sloupce. Matice je ostˇre prvk˚ u - a to bud diagon´ alnˇe dominantn´ı (zkr´ acenˇe o.d.d.), jsou-li nerovnosti ostr´e. Matice A: ˇr´ adky:
| − 5| > |3| < |2| ≥
| − 1| + | 0 | |3| + |1| | 1 | + | − 1|
sloupce:
| − 5| > |3| > |2| >
|3| + |1| | − 1| + | − 1| |1| + |0|
Ve druh´em ˇr´ adku podm´ınka neplat´ı ⇒ A nen´ı d.d. po ˇr´adc´ıch. Zkus´ıme tedy sloupce: podm´ınka plat´ı pro vˇsechny tˇri sloupce a nav´ıc nerovnosti jsou ostr´e ⇒ A je o.d.d. po sloupc´ıch. Takˇze A je ostˇre diagon´alnˇe dominantn´ı. 2
c
Certik
Iteraˇcn´ı metody ver. 2.3.2016
Matice B je symetrick´ a - kontrolujeme jen ˇr´adky (sloupce vyjdou stejnˇe): |1| ≥ |2| ≥ |2| >
| − 1| + | − 1| + |0| +
|0| | − 1| | − 1|
Podm´ınka plat´ı pro vˇsechny ˇr´adky, nerovnost vˇsak nen´ı vˇzdy ostr´a ⇒ B je diagon´ alnˇe dominantn´ı, ale ne ostˇre. Matice C je symetrick´ a - kontrolujeme jen ˇr´adky: |1| ≥ |1| < |2| >
| − 1| + | 0 | | − 1| + | 1 | | 0 | + |1|
Matice C nen´ı diagon´ alnˇe dominantn´ı, ve druh´em ˇr´adku (i sloupci) je podm´ınka poruˇsena. c) Symetrick´ a matice je pozitivnˇe definitn´ı, pr´avˇe kdyˇz vˇsechny jej´ı hlavn´ı minory jsou kladn´e. Matice A nen´ı symetrick´ a. Matice B: 1 −1 0 1 −1 2 −1 = 1 > 0 det(1) = 1 > 0 , det = 1 > 0 , det −1 −1 2 0 −1 2 Vˇsechny hlavn´ı minory jsou kladn´e, matice B je tedy pozitivnˇe definitn´ı. Matice C: 1 −1 det(1) = 1 > 0 , det =0 −1 1 Druh´ y hlavn´ı minor nen´ı kladn´ y, d´al uˇz tedy nemus´ıme nic zkoumat. Matice C nen´ı pozitivnˇe definitn´ı. Z´ avˇ er: Matice A je ostˇre diagon´alnˇe dominantn´ı, nen´ı symetrick´a ani pozitivnˇe definitn´ı. Matice B je diagon´alnˇe dominantn´ı (ne vˇsak ostˇre), symetrick´a a pozitivnˇe definitn´ı. Matice C je symetrick´a, nen´ı diagon´alnˇe dominantn´ı, ani pozitivnˇe definitn´ı.
3
c
Certik
Iteraˇcn´ı metody ver. 2.3.2016
Iteraˇ cn´ı metody Teorie (velmi struˇcn´y v´ybˇer z pˇredn´aˇsek) Prost´ a iteraˇ cn´ı metoda (d´ale zkratka pim) Soustavu x = U x + v ˇreˇs´ıme tak, ˇze 1. zvol´ıme x(0) , 2. pro k = 0, 1, 2, . . . poˇc´ıt´ ame x(k+1) = U x(k) + v, aˇz ||x(k+1) − x(k) || < . Podm´ınky konvergence: ρ(U ) < 1 ⇔ pim konverguje ||U || < 1 ⇒ pim konverguje ˇ sen´ı soustavy Ax = b Reˇ Postup: soustavu Ax = b pˇrevedeme na soustavu x = U x + v, a tu ˇreˇs´ıme pim. Vyuˇzijeme pˇritom vyj´ adˇren´ı matice A jako souˇctu A = L + D + U , kde L je doln´ı troj´ uheln´ıkov´ a ˇc´ ast, D je diagon´ala a U je horn´ı troj´ uheln´ıkov´a ˇc´ast. Jacobiho metoda (d´ ale zkratka J ) Soustavu Ax = b vyj´ adˇr´ıme jako x = UJ x + vJ , kde UJ = −D−1 (L + U ) a −1 vJ = D b. Tuto soustavu ˇreˇs´ıme pim. Podm´ınky konvergence: ρ(UJ ) < 1 ⇔ J konverguje A je o.d.d ⇒ J konverguje Vˇeta: vlastn´ı ˇc´ısla λi matice UJ lze z´ıskat ˇreˇsen´ım rovnice det(L + λD + U ) = 0. Gaussova-Seidelova metoda (d´ale zkratka GS ) Soustavu Ax = b vyj´ adˇr´ıme jako x = UG x + vG , kde UG = −(L + D)−1 U a −1 vJ = (L + D) b. Tuto soustavu ˇreˇs´ıme pim. Podm´ınky konvergence: ρ(UG ) < 1 ⇔ GS konverguje A je o.d.d ⇒ GS konverguje A je symetrick´ a a pozitivnˇe definitn´ı ⇒ GS konverguje Vˇeta: vlastn´ı ˇc´ısla λi matice UG lze z´ıskat ˇreˇsen´ım rovnice det(λL+λD+U ) = 0.
Prost´ a iteraˇ cn´ı metoda Pˇ r´ıklad 4 Je d´ ana soustava rovnic x = U x + v, kde 1/2 1 U= , −5/4 −3/2
v=
2 0
a) Zvolte x(0) = ( 0, 0)T a spoˇc´ıtejte prvn´ı tˇri iterace prostou iteraˇcn´ı metodou. b) Dokaˇzte, ˇze pim pro tuto soustavu konverguje. 4
c
Certik
Iteraˇcn´ı metody ver. 2.3.2016
ˇ sen´ı Reˇ a) x
(1)
(0)
= Ux
+v =
x(2) = U x(1) + v =
x
(3)
(2)
= Ux
+v =
1/2 −5/4
1 −3/2
1/2 −5/4
1 −3/2
1/2 −5/4
1 −3/2
0 0 2 0
+
2 0
+
3 −5/2
2 0
2 0
=
=
+
2 0
3 −5/2
=
1 0
b) Nejdˇr´ıv zkus´ıme, jestli plat´ı nˇekter´a z postaˇcuj´ıc´ıch podm´ınek, protoˇze se sn´ aze spoˇc´ıtaj´ı: ||U ||1 = max( |1/2| + | − 5/4|, | 1 | + | − 3/2|) = max( 7/4, 10/4) = 10/4 > 1 ||U ||∞ =p max( |1/2| + | 1 |, | − 5/4| + | − 3/2|)p= max( 3/2, 11/4) = 11/4 > 1 ||U ||2 = (1/2)2 + 12 + (−5/4)2 + (−3/2)2 = 81/16 = 9/4 > 1 ˇ adn´ Z´ a z norem nen´ı menˇs´ı neˇz 1, takˇze z nich nepozn´ame nic. Mus´ıme tedy ovˇeˇrit nutnou a postaˇcuj´ıc´ı podm´ınku, tj. spoˇc´ıtat ρ(U ): det(U −λI) =√λ2 +λ+1/2 ⇒ λ√ 1,2 = −1/2±1/2i p = (1/2−λ)(−3/2−λ)+5/4 p 2 2 ||λ1,2 || = (1/2) + (±1/2) = 1/2 = 2/2 ⇒ ρ(U ) = 2/2 < 1 ⇒ pim konverguje.
Jacobiho metoda Pˇ r´ıklad 5 Je d´ ana soustava rovnic Ax = b, kde A je matice z Pˇr´ıkladu 3 a b = (2, 1, −1)T . a) Zvolte x(0) = ( 0, 0, 0)T a spoˇc´ıtejte prvn´ı dvˇe iterace J metodou. b) Dokaˇzte, ˇze J pro tuto soustavu konverguje. c) Lze na z´ akladˇe v´ ysledk˚ u Pˇr. 3 rozhodnout, zda J konverguje i pro matice B a C? ˇ sen´ı Reˇ a) Jednotliv´e iterace J metody se poˇc´ıtaj´ı l´epe po sloˇzk´ach neˇz v maticov´em tvaru. Postup: 1. Nap´ıˇseme si soustavu po jednotliv´ ych rovnic´ıch: −5x1 − x2 3x1 + 3x2 + x3 x1 − x2 + 2x3
=
2
=
1
=
−1
2. Z kaˇzd´e rovnice vyj´ adˇr´ıme diagon´aln´ı prvek: x1
= −(2 + x2 )/5
x2
=
(1 − 3x1 − x3 )/3
x3
=
(−1 − x1 + x2 )/2 5
(2)
c
Certik
Iteraˇcn´ı metody ver. 2.3.2016
3. Pro k = 0, 1, 2, . . . poˇc´ıt´ame x(k+1) tak, ˇze do prav´e strany (2) dosad´ıme sloˇzky pˇredchoz´ı iterace x(k) : (k+1)
= −(2 + x2 )/5
(k+1)
=
(1 − 3x1 − x3 )/3
(k+1)
=
(−1 − x1 + x2 )/2
x1
x2
x3
(k)
(k)
(k)
(k)
(k)
Pro k = 0 dostaneme (1)
= −(2 + x2 )/5 = −(2 + 0)/5 = −2/5
(1)
=
(1 − 3x1 − x3 )/3 = (1 − 0 − 0)/3 = 1/3
(1)
=
(−1 − x1 + x2 )/2 = (−1 − 0 + 0)/2 = −1/2
x1
x2
x3
(0)
(0)
(0)
(0)
(0)
Prvn´ı iterace je tedy x(1) = (−2/5, 1/3, −1/2)T . Druh´a iterace: (2)
=
−(2 + x2 )/5 = −(2 + 1/3)/5 = −7/15
(2)
=
(1 − 3x1 − x3 )/3 = (1 − 3(−2/5) − (−1/2))/3 = 9/10
(2)
=
(−1 − x1 + x2 )/2 = (−1 − (−2/5) + 1/3)/2 = −2/15
x1
x2
x3
(1)
(1)
(1)
(1)
(1)
Druh´ a iterace je x(2) = (−7/15, 9/10, −2/15)T . b) V Pˇr. 3 jsme dok´ azali, ˇze A je ostˇre diagon´alnˇe dominantn´ı, coˇz je postaˇcuj´ıc´ı podm´ınka pro konvergenci J metody. c) Matice B ani C z Pˇr. 3 nejsou o.d.d., postaˇcujc´ı podm´ınka pro konvergenci J metody tedy nen´ı splnˇena a o konvergenci nev´ıme nic. Kdybychom chtˇeli poznat, zda J metoda konverguje, museli bychom spoˇc´ıtat spektr´aln´ı polomˇer matice UJ , coˇz pro matici 3 × 3 obecnˇe nen´ı snadn´e. Pˇ r´ıklad 6 Rozhodnˇete, zda pro soustavu Ax = b bude konvergovat J metoda, je-li d´ano 6 11 −1 0 A= 1 3 −1 0 2 ˇ sen´ı Reˇ Matice nen´ı o.d.d., postaˇcuj´ıc´ı podm´ınka pro konvergenci J metody tedy neplat´ı a mus´ıme spoˇc´ıtat spektr´ aln´ı polomˇer matice UJ . Vlastn´ı ˇc´ısla matice UJ urˇc´ıme z rovnice det(L + λD + U ) = 0, tj. 6λ 11 −1 1 3λ 0 = 36λ3 − 3λ − 22λ = λ(36λ2 − 25) = 0 −1 0 2λ ⇒ λ1 = 0, λ2,3 = ±5/6 ⇒ ρ(UJ ) = 5/6 < 1. Spektr´ aln´ı polomˇer matice UJ je menˇs´ı neˇz 1, takˇze J metoda konverguje. 6
c
Certik
Iteraˇcn´ı metody ver. 2.3.2016
Gaussova-Seidelova metoda Pˇ r´ıklad 7 Je d´ ana soustava rovnic Ax = b, kde A je matice z Pˇr´ıkladu 3 a b = (2, 1, −1)T . a) Zvolte x(0) = ( 0, 0, 0)T a spoˇc´ıtejte prvn´ı dvˇe iterace GS metodou. b) Dokaˇzte, ˇze GS pro tuto soustavu konverguje. c) Lze na z´ akladˇe v´ ysledk˚ u Pˇr. 3 rozhodnout, zda GS konverguje i pro matice B a C? ˇ sen´ı Reˇ a) Jednotliv´e iterace GS metody se poˇc´ıtaj´ı l´epe po sloˇzk´ach neˇz v maticov´em tvaru. Postup: 1. Nap´ıˇseme si soustavu po jednotliv´ ych rovnic´ıch - stejnˇe jako u J metody, viz Pˇr.5. 2. Z kaˇzd´e rovnice vyj´ adˇr´ıme diagon´aln´ı prvek - stejnˇe jako u J metody, viz Pˇr.5. 3. Pro k = 0, 1, 2, . . . poˇc´ıt´ame x(k+1) po jednotliv´ ych rovnic´ıch, poˇc´ınaje prvn´ı. Zaˇcneme jako u J metody, ale jakmile spoˇc´ıt´ame novou sloˇzku, hned ji dosad´ıme do prav´e strany vˇsech zb´ yvaj´ıc´ıch rovnic (2): (k+1)
= −(2 + x2 )/5
(k+1)
=
(1 − 3x1
(k+1)
=
(−1 − x1
x1 x2
x3
(k)
(k+1)
(k)
− x3 )/3
(k+1)
(k+1)
+ x2
)/2
Pro k = 0 dostaneme (1)
= −(2 + x2 )/5 = −(2 + 0)/5 = −2/5
(1)
=
(1 − 3x1 − x3 )/3 = (1 − 3(−2/5) − 0)/3 = 11/15
(1)
=
(−1 − x1 + x2 )/2 = (−1 − (−2/5) + 11/15)/2 = 1/15
x1
x2
x3
(0)
(1)
(0)
(1)
(1)
Prvn´ı iterace je tedy x(1) = (−2/5, 11/15, 1/15)T . Druh´a iterace: (2)
=
−(2 + x2 )/5 = −(2 + 11/15)/5 = −41/75
(2)
=
(1 − 3x1 − x3 )/3 = (1 − 3(−41/75) − 1/15)/3 = 193/225
(2)
=
(−1 − x1 + x2 )/2 = (−1 − (−41/75) + 193/225)/2 = 91/450
x1
x2
x3
(1)
(2)
(2)
(1)
(2)
Druh´ a iterace je x(2) = (−41/75, 193/225, 91/450)T . b) V Pˇr. 3 jsme dok´ azali, ˇze A je ostˇre diagon´alnˇe dominantn´ı, coˇz je postaˇcuj´ıc´ı podm´ınka pro konvergenci GS metody.GS metoda konverguje. c) V Pˇr. 3 jsme dok´ azali, ˇze B je symetrick´a a pozitivnˇe definitn´ı, coˇz je postaˇcuj´ıc´ı podm´ınka pro konvergenci GS metody. Matice C nen´ı o.d.d. ani pozitivnˇe definitn´ı, ˇz´ adn´ a z postaˇcujc´ıch podm´ınek pro konvergenci GS metody 7
c
Certik
Iteraˇcn´ı metody ver. 2.3.2016
pro matici C tedy nen´ı splnˇena. Z´avˇer: pro matici B GS metoda konverguje, pro matici C o konvergenci GS metody nev´ıme nic. Kdybychom chtˇeli poznat, zda GS metoda konverguje i pro matici C, museli bychom spoˇc´ıtat spektr´aln´ı polomˇer odpov´ıdaj´ıc´ı matice UG . Pˇ r´ıklad 8 Rozhodnˇete, zda pro soustavu Ax = b z Pˇr. 6 bude konvergovat GS metoda. ˇ sen´ı Reˇ Matice A nen´ı o.d.d. ani symetrick´a, ˇz´adn´a z postaˇcujc´ıch podm´ınek pro konvergenci GS metody tedy nen´ı splnˇena a mus´ıme spoˇc´ıtat spektr´aln´ı polomˇer matice UG . Vlastn´ı ˇc´ısla matice UG urˇc´ıme z rovnice det(λ(L + D) + U ) = 0, tj. 6λ 11 −1 λ 3λ 0 = 36λ3 − 3λ2 − 22λ2 = λ2 (36λ − 25) = 0 −λ 0 2λ ⇒ λ1,2 = 0, λ3 = 25/36 ⇒ ρ(UG ) = 25/36 < 1. Spektr´ aln´ı polomˇer matice UG je menˇs´ı neˇz 1, takˇze GS metoda konverguje.
8
c
Certik
