Soustavy lineárních rovnic-numerické řešení

Soustavy lineárních rovnic-numerické řešení

November 9, 2008

Soustavy lineárních rovnic-numerické řešení 1 / 52

(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.


◮

koeficienty systému - aĳ ,

◮

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


(Matice, opakování) ◮

typy matíc

◮

operace s maticemi

◮

lin. závislost, nezávislost

◮

determinanty


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.


(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


Příklad (Cramerovo pravidlo) Najděte řešení soustavy rovnic: x1 − 3x2 = 7 8x1 + x2 = 3


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


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


(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


(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


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


Příklad (GEM, řešení) 



1 3 −4 7   ∼  0 −13 11 −13  ∼ 0 −5 5 −20





1 3 −4 7   ∼  0 −13 11 −13  ∼ 0 1 −1 4









1 3 −4 7 1 3 −4 7     ∼ 0 4  ∼  0 1 −1 4  1 −1 0 −13 11 −13 0 0 −2 39


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

31 2

= 7

x = −

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 . . .


Příklad (GEM s hl. prvkem) 



0,14 0,24 −0,84 1,11   0,48  ∼ 0,56  1,07 −0,83 0,64 0,43 −0,38 −0,83





1,07 −0,830 0 0,560 0 0,480 0   ∼  0,14 1,047 2  ∼ 0,348 6 −0,913 2 0,00 0,926 4 −0,714 9 −1,117 1





1,07 −0,830 0 0,560 0 0,480 0   ∼  0,00 0,926 4 −0,714 9 −1,117 1  0,00 0,000 0 −0,644 2 1,467 6


Iterační metody


(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


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)

(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

Příklad (Jacobiho metoda, řešení) Soustavy lineárních rovnic-numerické řešení 24 / 52

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)

(k)

x2 2,1 1,98 2,001 2,000 1 2,000 01

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.

Příklad (Jacobiho metoda, divergence) Soustavy lineárních rovnic-numerické řešení 25 / 52

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

Příklad (Jacobiho metoda, divergence) Soustavy lineárních rovnic-numerické řešení 26 / 52

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í! Soustavy lineárních rovnic-numerické řešení 27 / 52

( 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


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žĳeme 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

Příklad (Gauss-Seidlova metoda, řešení) Soustavy lineárních rovnic-numerické řešení 29 / 52

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

(k)

x3 3,3 2,999 4 2,999 856 3 3,000 001 81 3,000 000 05


(Konvergence a odhad chyb)


(Normy vektorů a matic) ◮

sloupcová norma: ||A||1 = max( j

◮

řádková norma: ||A||∞ = max( i

n P

|aĳ |)

i=1 n P

|aĳ |)

j=1


(Ostře řádkově nebo sloupcově diagonálně dominantní matice) ◮

řádkově: |aii | >

n X

|aĳ | pro

i = 1, . . . , n

n X

|aĳ | pro

j = 1, . . . , n

j=1,j6=i ◮

sloupcově: |ajj | >

i=1,i6=j


(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


(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) 

(2)



0 −0, 1 0, 1   0 −0, 05 C =  0, 05 −0, 1 −0, 1 0


(Odhad chyby Jacobiho a Gauss-Seidlovy metody) ||x (r) − x|| ≤

||C || · ||x (r) − x (r−1) || 1 − ||C ||


(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


(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í.


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]. Soustavy lineárních rovnic-numerické řešení 39 / 52

( Relaxační metoda )


Mějme Ax = b, det A 6= 0. α-řešení ⇒ b − Aα = 0 Při řešení využĳeme 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 Soustavy lineárních rovnic-numerické řešení 41 / 52

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.

Příklad ( Relaxační metoda, pokr.) Soustavy lineárních rovnic-numerické řešení 42 / 52

(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 .


(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 .


(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)


(Podmíněnost matice)


Číslo podmíněnosti matice Cp(A) = ||A−1 || · ||A|| Matice s velkým číslem podm. můžou výrazně zesilnit chyby.


Příklad Zjistěte číslo podm. matice systému x1 + 0, 99x2 = 1, 99 1, 01x1 + x2 = 2, 01


Příklad "

1 0, 99 A= 1, 01 1

#


Příklad A

−1

"

10000 −9999 = 10100 10000

#


Příklad ||A|| = 2, 01

||A−1 || = 20100

CpA = 40401.


Příklad Jacobiho metodou zjistěte řešení systému x1 + 0, 99x2 = 1, 99 1, 01x1 + x2 = 2, 01


Soustavy lineárních rovnic-numerické řešení

Recommend Documents