Soustavy lineárních rovnic-numerické řešení
October 2, 2008
INM 2008
(Systém lin. rovnic) Systém rovnic a11 x1 + a12 x2 + · · · + a1n xn = b1 a21 x1 + a22 x2 + · · · + a2n xn = b2 ............... an1 x1 + an2 x2 + · · · + ann xn = bn nazveme systém n-lineárnych rovnic s n neznámými.
INM 2008
koeficienty systému - aij , matice systému a11 a12 . . . a 21 a22 . . . ... ... ... an1 an2 . . . rozšířená matice a11 a12 . . . a 21 a22 . . . ... ... ... an1 an2 . . .
i, j = 1, 2, ..., n
a1n a2n ... ann systému b a1n 1 b a2n 2 . . . . . . . . . bn ann
INM 2008
(Matice, opakování) typy matíc operace s maticemi lin. závislost, nezávislost determinanty
INM 2008
Věta (Základní věta lineární algebry) Systém lineárních rovnic má řešení ⇐⇒ hodnost matice A je stejná jako hodnost rozšířené matice systému.
INM 2008
(Cramerovo pravidlo) Ak je matica systému regulární, tak systém má jediné řešení x = A−1 b
a x =
Dn D1 D2 D , D ,... D
INM 2008
Příklad (Cramerovo pravidlo) Najděte řešení soustavy rovnic: x1 − 3x2 = 7 8x1 + x2 = 3
INM 2008
Příklad (Cramerovo pravidlo, řešení) Soustavu rovnic upravíme na rozš. matici systému: 1 −3 7 8 1 3
!
Abychom mohli využít Cramerova pravidla, tak musí být determinant matice nenulový. Výpočet determinantu matice: D = 1 · 1 − (−3) · 8 = 1 + 24 = 25 6= 0
INM 2008
Příklad (Cramerovo pravidlo, pokr.) Vypočítáme determinant D1 , který vznikl nahrazením prvního sloupce matice soustavy vektorem pravých stran. 7 −3 D1 = = 7 · 1 − (−3) · 3 = 7 + 9 = 16. 3 1
Můžeme vypočítat kořen x1 soustavy rovnic: x1 =
16 D1 = . D 25
Stejným způsobem vypočítáme i druhý kořen x2 soustavy rovnic: 1 D2 = 8
7 3
= 1 · 3 − 7 · 8 = 3 − 56 = −53,
x2 =
53 D2 =− . D 25 INM 2008
(Numerické metody:) přímé Gaussova eliminační metoda Gaussova eliminační metoda s výběrem hlavního prvku
iterační Jacobiho metoda Gauss-Seidlova metoda Relaxační metoda
INM 2008
(Gaussova eliminační metoda) Příklad (GEM, zadání) Gaussovou elim. metodou najděte řešení soustavy rovnic: x + 3y − 4z = 7 2x − 7y + 3z = 1 3x + 4y − 7z = 1
INM 2008
Příklad (GEM, řešení) Postupně provádíme elementární ekvivaletní úpravy, až dosáhneme trojúhelníkové matice:
1 3 −4 7 3 1 ∼ 2 −7 3 4 −7 1
INM 2008
Příklad (GEM, řešení)
7 1 3 −4 ∼ 0 −13 11 −13 ∼ 0 −5 5 −20
INM 2008
Příklad (GEM, řešení)
7 1 3 −4 ∼ 0 −13 11 −13 ∼ 4 0 1 −1
INM 2008
Příklad (GEM, řešení)
7 1 3 −4 7 1 3 −4 1 −1 ∼ 0 4 ∼ 0 1 −1 4 0 −13 11 −13 0 0 −2 39
INM 2008
Příklad (GEM, řešení) Z matice v trojuhelníkovém tvaru vyčíslíme x, y a z: −2z = 39 39 z = − 2
y− −
39 2
= 4
y = − 31 x +3 − 2
39 −4 − 2
= 7
x = −
INM 2008
31 2
49 2
(Gaussova eliminační metoda s částeč. výběrem hlavního prvku) V prvním kroku vybereme do prvního řádku tu rovnici, která má v absolutní hodnotě u x1 největší koeficient. Pak eliminujeme x1 v dalších rovnicích. V dalším kroku si budeme vybírat ze zbylých rovnic tu rovnici do druhého řádku, která má v absolutní hodnotě největší koeficient při x2 . Pak ze zbylých rovnic eliminujeme x2 . A tak dále . . .
INM 2008
Příklad (GEM s hl. prvkem)
1,11 0,14 0,24 −0,84 0,56 0,48 ∼ 1,07 −0,83 0,64 0,43 −0,38 −0,83
INM 2008
Příklad (GEM s hl. prvkem)
0,480 0 1,07 −0,830 0 0,560 0 0,348 6 −0,913 2 ∼ 0,14 1,047 2 ∼ 0,00 0,926 4 −0,714 9 −1,117 1
INM 2008
Příklad (GEM s hl. prvkem)
0,480 0 1,07 −0,830 0 0,560 0 0,926 4 −0,714 9 −1,117 1 ∼ 0,00 1,467 6 0,00 0,000 0 −0,644 2
INM 2008
Iterační metody
INM 2008
(Jacobiho metoda) Příklad (Jacobiho metoda, zadání) Jacobiho metodou řešte soustavu rovnic. 10x1 + x2 − x3 = 9 −x1 + 20x2 + x3 = 42 x1 + x2 + 10x3 = 33
INM 2008
Příklad (Jacobiho metoda, řešení) Z první rovnice si vyjádříme první neznámou, ze druhé rovnice vyjádříme druhou neznámou a ze třetí rovnice vyjádříme poslední neznámou. Toto je soustava rovnic, do které budeme v každém dalším kroku dosazovat. x1 = 0,1(−x2 + x3 + 9) x2 = 0,05(x1 − x3 + 42) x3 = 0,1(−x1 − x2 + 33)
INM 2008
(1)
Příklad (Jacobiho metoda, řešení) Začneme počáteční aproximací x (0) = (0,9; 2,1; 3,3) a dosadíme do předchozích vztahů pro naše neznámé: (1)
x1 = 0,1(−2,1 + 3,3 + 9) = 1,02 (1) x2 = 0,05(0,9 − 3,3 + 42) = 1,98 (1) x3 = 0,1(−0,9 − 2,1 + 33) = 3,00 Dostali jsme další aproximaci, kterou opět dosadíme do soustavy rovnic (2). (2)
x1 = 0,1(−1,98 + 3,00 + 9) = 1,002 (2) x2 = 0,05(1,02 − 3,00 + 42) = 2,001 (2) x3 = 0,1(−1,02 − 1,98 + 33) = 3,000
INM 2008
Příklad (Jacobiho metoda, řešení) V tabulce jsou výsledky z dalších dvou kroků Jacobiho metody. k 0 1 2 3 4
(k)
x1 0,9 1,02 1,002 0,999 9 0,999 96
(k)
x2 2,1 1,98 2,001 2,000 1 2,000 01
(k)
x3 3,3 3,00 3,000 2,999 7 3,000 00
Sledujeme rozdíly u každé neznámé ve dvou po sebe jdoucích aproximacích. Metodu ukončíme, když jsou rozdíly v absolutní hodnotě (u každé neznámé) menší než požadovaná přesnost.
INM 2008
Příklad (Jacobiho metoda, divergence) Zde si ukážeme případ, kdy Jacobiho metoda diverguje. x1 + x2 + 10x3 = 33 10x1 + x2 − x3 = 9 −x1 + 20x2 + x3 = 42 x1 = −x2 − 10x3 + 33 x2 = −10x1 + x3 + 9 x3 = x1 − 20x2 + 42
INM 2008
Příklad (Jacobiho metoda, divergence) x1 = −2,1 − 10 · 3,3 + 33 = −2,1 x2 = −10 · 0,9 + 3,3 + 9 = 3,3 x3 = 0,9 − 20 · 2,1 + 42 = 0,9 x1 = −3,3 − 10 · 0,9 + 33 = 20,7 x2 = 10 · 2,1 + 0,9 + 9 = 30,9 x3 = −2,1 − 20 · 3,3 + 42 = −26,1
Příklad (Jacobiho metoda, divergence) x1 = 30,9 − 10 · (−26,1) + 33 = 263,1 x2 = −10 · 20,7 − 26,1 + 9 = −224,1 x3 = 20,7 − 20 · 30,9 + 42 = −555,3 Jak je vidět, tak Jacobiho metoda v tomto případě diverguje. Všimněte si, že se jedná o stejnou soustavu jako v předchozím příkladu, jen řádky soustavy jsou v jiném pořadí! INM 2008
( Gauss-Seidlova metoda) Příklad (Gauss-Seidlova metoda, zadání) Najděte řešení soustavy rovnic Gauss-Seidlovou metodou. 10x1 + x2 − x3 = 9 −x1 + 20x2 + x3 = 42 x1 + x2 + 10x3 = 33
INM 2008
Příklad (Gauss-Seidlova metoda, řešení) Začneme s počátoční aproximaci řešení x (0) = (0,9; 2,1; 3,3). Při (1) (1) výpočtu x1 pracujeme s počátoční aproximací, při výpočtu x2 (1) (1) už využíváme hodnotu x1 a při výpočtu x3 využijeme i hodnotu (1) x2 , porovnejte si to s Jacobiho metodou! (1)
(0)
(0)
x1 = 0,1(−x2 + x3 + 9) = 0,1(−2,1 + 3,3 + 9) = 1,02 (1) (1) (0) x2 = 0,05(x1 − x3 + 42) = 0,05(1,02 − 3,3 + 42) = 1,986 (1) (1) (1) x3 = 0,1(−x1 − x2 + 33) = 0,1(−1,02 − 1,986 + 33) = 2,9994
INM 2008
Příklad (Gauss-Seidlova metoda, řešení) Tabulka výsledků do čtvrtého řádu: k 0 1 2 3 4
(k)
x1 0,9 1,02 1,001 34 0,999 975 93 0,999 999 58
(k)
x2 2,1 1,986 2,000 097 2,000 005 98 1,999 999 89
INM 2008
(k)
x3 3,3 2,999 4 2,999 856 3 3,000 001 81 3,000 000 05
(Konvergence a odhad chyb)
INM 2008
(Normy vektorů a matic) sloupcová norma: ||A||1 = max( j
řádková norma: ||A||∞ = max( i
n P
|aij |)
i=1 n P
|aij |)
j=1
INM 2008
(Ostře řádkově nebo sloupcově diagonálně dominantní matice) řádkově: |aii | >
n X
|aij | pro
i = 1, . . . , n
n X
|aij | pro
j = 1, . . . , n
j=1,j6=i
sloupcově: |ajj | >
i=1,i6=j
INM 2008
(Pozitivňe definitní matice) Symetrická matice A řádu n se nazývá pozitivně definitní, jestliže pro každý nenulový sloupcový vektor x= (x1 , x2 , . . . , xn )T platí x T .A.x > 0
INM 2008
(Iterační matice, příklad na Jacobiho metodu, pokr.) x1 = 0,1(−x2 + x3 + 9) x2 = 0,05(x1 − x3 + 42) x3 = 0,1(−x1 − x2 + 33)
0 −0, 1 0, 1 0 −0, 05 C = 0, 05 −0, 1 −0, 1 0
INM 2008
(2)
(Odhad chyby Jacobiho a Gauss-Seidlovy metody) ||x (r) − x|| ≤
||C || · ||x (r) − x (r−1) || 1 − ||C ||
INM 2008
(odhad pro příklad na Jacobiho metodu) ||C ||∞ = max{|−0, 1|+|0, 1|; |0, 05|+|−0, 05|; |−0, 1|+|0, 1|} = 0, 2. ||x (4) − x (3) || = ||0, 00006; −0, 00009; 0, 0003|| = = max{|0, 00006|; | − 0.00009|; |0, 0003|} = 0, 0003 ||x (4) − x|| ≤
0, 2 · 0, 0003 = 0, 000075. 1 − 0, 2
INM 2008
(Pravidla) Je-li matice soustavy ostře řádkově nebo sloupcově diagonálně dominantní, Jacobiho aj Gauss-Seidelova metoda konvergují Je-li matice soustavy symetrická a pozitivně definitní Gauss-Seidelova metoda konverguje (Jacobiho metoda konvergovat nemusí) Vynásobíme-li libovolnou regul. čtvercovou matici zleva maticí k ní transponovanou, vzniklá matice je symetrická a pozitivně definitní.
INM 2008
Příklad Všimněte si následující soustavu rovnic: x1 −0,464x2 = 0,536 2,047x1 +x2 −0,464x3 = 2,583 −0,464x1 + +x3 = 0,536 Zkuste si, že Jacobiho metoda konverguje při řešení této soustavy. Ale Gauss-Seidlova metoda diverguje.
Nechť A je symetrická a pozitivně definitní a Jacobiho metoda konverguje (když A je symetrická a pozitivně definitní, Jacobiho metoda konvergovat ještě nemusí, ale může) ⇒ Gauss-Seidlova metoda konverguje dvakrát rychleji než Jacobiho metoda. [Ralston, A.: Základy numerické matematiky, 1978]. INM 2008
( Relaxační metoda )
INM 2008
Mějme Ax = b, det A 6= 0. α-řešení ⇒ b − Aα = 0 Při řešení využijeme tzv. rezídua. Rezíduum vypočítáme pomocí následujícího vzorce: r = b − Ax Složky vektoru rezíduí se snažíme zmenšovat. Jestliže rezíduum konverguje k 0 dostáváme iterační metodu: Např.: tzv. relaxační metodu.
Příklad ( Relaxační metoda, zadání) Příklad. Relaxační metodou řešte soustavu rovnic. 10x1 + x2 + x3 = 22 x1 + 10x2 + x3 = 13 −x1 + x2 + 10x3 = 9 INM 2008
Příklad ( Relaxační metoda, řešení) Začneme počáteční aproximací x (0) = (0, 0, 0), vypočítáme počáteční aproximaci rezídua: r = (22 − 10x1 − x2 − x3 , 13 − x1 − 10x2 − x3 , 9 + x1 − x2 − 10x3 ) r (0) = (22; 13; 9)
|22| > |13|, |22| > |9|
Jelikož první složka rezídua je dominantní (v absolutní hodnotě je největší ze všech složek nulté iterace rezídua), tak budeme upravovat první rovnici (zejména neznámou x1 ) tak, aby tato první složka byla vynulována.
INM 2008
Příklad ( Relaxační metoda, pokr.) (1)
(0)
(0)
10x1 + x2 + x3 = 22 (1) 10x1 = 22 (1) (1) x1 = 2,2, r1 = 0 x (1) = (2,2; 0; 0)
r (1) = (0; 10,8; 11,2)
Nájdeme v absolutní hodnotě největší složku první iterace rezídua a příslušnou rovnici a neznámou upravíme tak, aby se tato složka vynulovala. Největší složka je 11, 2, (třetí složka) proto si budeme všímat třetí rovnici a zejména třetí neznámou x3 .
INM 2008
Příklad ( Relaxační metoda, pokr.) (1)
(1)
(2)
−x1 + x2 + 10x3 = 9 (2) −2,2 + 0 + 10x3 = 9 (2) x3 = 1,12 x (2) = (2,2; 0; 1,12)
r (2) = (−1,12; 9,68; 0)
Největší složka ve druhé iteraci rezídua je 9, 68, proto si budeme všímat příslušnou rovnici a neznámou, teda druhou rovnici a x2 .
INM 2008
Příklad ( Relaxační metoda, pokr.) (2)
(3)
(2)
x1 + 10x2 + x3 = 13 (3) 2,2 + 10x2 + 1,12 = 13 (3) x2 = 0,968 x (3) = (2,2; 0,968; 1,12)
r (3) = (−2,088; 0; −0,968)
.. . Po pěti dalších výpočetních krocích dostáváme x (8) = (1,9997; 1,00065; 1,99991)
r (8) = (0,0241; −0,00608; 0)
INM 2008
(Podmíněnost matice)
INM 2008
Číslo podmíněnosti matice Cp(A) = ||A−1 || · ||A|| Matice s velkým číslem podm. můžou výrazně zesilnit chyby.
INM 2008
Příklad Zjistěte číslo podm. matice systému x1 + 0, 99x2 = 1, 99 1, 01x1 + x2 = 2, 01
INM 2008
Příklad "
1 0, 99 A= 1, 01 1
INM 2008
#
Příklad A
−1
"
10000 −9999 = 10100 10000
INM 2008
#
Příklad ||A|| = 2, 01
||A−1 || = 20100
CpA = 40401.
INM 2008
Příklad Jacobiho metodou zjistěte řešení systému x1 + 0, 99x2 = 1, 99 1, 01x1 + x2 = 2, 01
INM 2008
