Priame metódy pre riešenie veľkých sústav rovníc - História úprav

Juraj na 19:46, 30. júl 2010

2010-07-30T19:46:57Z

Zobraziť rozdiely

Repto: /* Algoritmy riešenia trojuholníkových systémov */

2010-06-18T13:33:20Z

Algoritmy riešenia trojuholníkových systémov

Repto: /* LU rozklad */

2010-05-30T21:57:38Z

LU rozklad

Repto: /* Algoritmy riešenia trojuholníkových systémov */

2010-05-30T21:48:22Z

Algoritmy riešenia trojuholníkových systémov

Repto: /* Algoritmy riešenia trojuholníkových systémov */

2010-05-30T21:45:43Z

Algoritmy riešenia trojuholníkových systémov

Repto na 21:10, 30. máj 2010

2010-05-30T21:10:05Z

Repto na 21:05, 30. máj 2010

2010-05-30T21:05:34Z

Repto na 20:53, 30. máj 2010

2010-05-30T20:53:28Z

Repto na 20:33, 30. máj 2010

2010-05-30T20:33:42Z

Repto na 20:27, 30. máj 2010

2010-05-30T20:27:33Z

@@ Riadok 108: / Riadok 108: @@
 '''Algoritmus s prístupom po stĺpcoch'''
 x=b;
-'''for''' j=1,... n-1 '''do'''
+   for j=1,... n-1 do
-x<sub>j</sub><nowiki>= </nowiki> x<sub>j</sub> / l<sub>jj</sub>
+    xj= xj / Ljj ;
-'''for''' i > j, l<sub>ij</sub>[[Image:Untitled%201_html_m6647c5ea.png]] '''do'''
+      for i > j,Lij != 0 do
-x<sub>j</sub><nowiki>= </nowiki>x<sub>j</sub> – l<sub>ij</sub> x<sub>j</sub><nowiki>;</nowiki>
+       xj= xj – Lij * xj;
-'''end for'''
+      end for
-'''end for'''
+   end for
 '''Algoritmus prístupom po riadkoch'''
 x=b;
-x<sub>1</sub> <nowiki>= </nowiki>x<sub>1</sub> / l<sub>11</sub> <nowiki>;</nowiki>
+   for i=2,... n do
+     for j=2,... i-1 do
-'''for''' i=2,... n '''do'''
+       xj= xj - Lij * xj ;
+     end for
-'''for '''j=1 ...i-1 '''do'''
+    xi= xi / Lii;
+   end for
-x<sub>j</sub><nowiki>= </nowiki> x<sub>j</sub> – l<sub>ij</sub> x<sub>j</sub><nowiki>;</nowiki>
+</source>

@@ Riadok 19: / Riadok 19: @@
 '''LU rozklad (Right-Looking LU Factorization) '''
-Táto forma LU rozkladu využíva Gaussovu elimináciu opísanú v&nbsp;kapitole 1.3.3.
+Táto forma LU rozkladu využíva Gaussovu elimináciu opísanú v&nbsp;kapitole 2.1.3.
 Odvodenie tejto metódy rozkladu začína nasledovnou maticovou rovnicou:
@@ Riadok 25: / Riadok 25: @@
 [[Image:Untitled%201_html_m2f318df1.png]] = [[Image:Untitled%201_html_75b531c3.png]] (3.1)
-kde l11<nowiki>=1 je skalár a&nbsp;všetky tri matice sú štvorcové matice. Sú možné aj iné varianty ako zvoliť l</nowiki>11. V&nbsp;tomto prípade dostaneme dolnú trojuholníkovú maticu a&nbsp;štyri rovnice.
+kde l<sub>11</sub><nowiki>=1 je skalár a&nbsp;všetky tri matice sú štvorcové matice. Sú možné aj iné varianty ako zvoliť </nowiki> l<sub>11</sub>. V&nbsp;tomto prípade dostaneme dolnú trojuholníkovú maticu a&nbsp;štyri rovnice.
 [[Image:Untitled%201_html_me6e6cab.png]] (3.2)
@@ Riadok 70: / Riadok 70: @@
 Algoritmus LU rozkladu vyžaduje [[Image:Untitled%201_html_m65f83ebb.png]]<nowiki> operácií [2][3].</nowiki>
 == Choleského rozklad ==

@@ Riadok 105: / Riadok 105: @@
 Majme rozklad : [[Image:Untitled%201_html_m6664c1d2.png]] = [[Image:Untitled%201_html_2091c33a.png]] , kde [[Image:Untitled%201_html_m5e5abdc8.png]] je štvorcová pravá dolná submatica matice L o&nbsp;rozmeroch n-1. [[Image:Untitled%201_html_m1e0dd299.png]] sú stĺpcové vektory o&nbsp;dĺžke n-1. [[Image:Untitled%201_html_m6ac242f3.png]] sú skaláry. Toto vedie k&nbsp;dvom rovniciam [[Image:Untitled%201_html_1c78ceb1.png]] (3.17) a [[Image:Untitled%201_html_m458f3c1c.png]] (3.18)
-Vyriešime prvú rovnicu (3.17) a&nbsp;získame tak x1 :
+Vyriešime prvú rovnicu (3.17) a&nbsp;získame tak x<sub>1</sub> :
-Druhá rovnica (3.18) je dolný trojuholníkový systém vo forme [[Image:Untitled%201_html_6f51f94b.png]]. Tento systém možno riešiť rekurzívne a&nbsp;získať tak x2. Tento algoritmus využíva iteráciu cez stĺpce matice L. Môžeme si všimnúť, že b1 a&nbsp;b2 sú použité len raz . Preto môžeme v&nbsp;algoritme priradiť x do b a&nbsp;používame ďalej v&nbsp;algoritme už len x.
+Druhá rovnica (3.18) je dolný trojuholníkový systém vo forme [[Image:Untitled%201_html_6f51f94b.png]]. Tento systém možno riešiť rekurzívne a&nbsp;získať tak x<sub>2</sub>. Tento algoritmus využíva iteráciu cez stĺpce matice L. Môžeme si všimnúť, že b<sub>1</sub> a&nbsp;b<sub>2</sub> sú použité len raz . Preto môžeme v&nbsp;algoritme priradiť x do b a&nbsp;používame ďalej v&nbsp;algoritme už len x.

@@ Riadok 138: / Riadok 138: @@
 '''for '''j=1 ...i-1 '''do'''
->x<sub>j</sub><nowiki>= </nowiki> x<sub>j</sub> – l<sub>ij</sub> x<sub>j</sub><nowiki>;</nowiki>
+x<sub>j</sub><nowiki>= </nowiki> x<sub>j</sub> – l<sub>ij</sub> x<sub>j</sub><nowiki>;</nowiki>
 '''end for'''

@@ Riadok 138: / Riadok 138: @@
 '''for '''j=1 ...i-1 '''do'''
-x<sub>j</sub><nowiki>= </nowiki> x<sub>j</sub> – l<sub>ij</sub> x<sub>j</sub><nowiki>;</nowiki>
+>x<sub>j</sub><nowiki>= </nowiki> x<sub>j</sub> – l<sub>ij</sub> x<sub>j</sub><nowiki>;</nowiki>
 '''end for'''
 xi<nowiki>= x</nowiki>i / l<sub>ii</sub><nowiki>;</nowiki>
-−
 '''end for'''

@@ Riadok 5: / Riadok 5: @@
 __TOC__
 = =
-</nowiki>
 '''Priame metódy pre riešenie veľkých sústav rovníc'''

← Staršia verzia		Verzia zo dňa a času 20:33, 30. máj 2010
Riadok 70:		Riadok 70:

	Algoritmus LU rozkladu vyžaduje [[Image:Untitled%201_html_m65f83ebb.png]]<nowiki> operácií [2][3].</nowiki>		Algoritmus LU rozkladu vyžaduje [[Image:Untitled%201_html_m65f83ebb.png]]<nowiki> operácií [2][3].</nowiki>
		+
		+
		+

← Staršia verzia		Verzia zo dňa a času 20:27, 30. máj 2010
Riadok 5:		Riadok 5:
	__TOC__		__TOC__
	= =		= =
		+	</nowiki>
		+
		+	'''Priame metódy pre riešenie veľkých sústav rovníc'''
		+
		+	Priame metódy vedú k presnému riešeniu danej sústavy po konečnom počte krokov. Pri priamych metódach sa väčšinou daná matica systému zjednoduší použitím niektorého rozkladu a potom sa ďalej pracuje s týmto zjednodušeným systémom . Pri použití rozkladov pre zjednodušenie veľkých matíc dostávame väčšinou trojuholníkové systémy. V tejto kapitole sú opísané niektoré známe rozklady ako aj riešenie trojuholníkových systémov, ktoré vzniknú pri použití týchto rozkladov.
		+
		+
		+	== LU rozklad ==
		+	Táto metóda slúži na rozklad matice A na dve trojuholníkové matice. Kde
		+
		+	L je dolná trojuholníková matica a U je horná trojuholníková matica. Existuje viacero spôsobov určenia LU rozkladu matice.
		+
		+	'''LU rozklad (Right-Looking LU Factorization) '''
		+
		+	Táto forma LU rozkladu využíva Gaussovu elimináciu opísanú v kapitole 1.3.3.
		+
		+	Odvodenie tejto metódy rozkladu začína nasledovnou maticovou rovnicou:
		+
		+	[[Image:Untitled%201_html_m2f318df1.png]] = [[Image:Untitled%201_html_75b531c3.png]] (3.1)
		+
		+	kde l11<nowiki>=1 je skalár a všetky tri matice sú štvorcové matice. Sú možné aj iné varianty ako zvoliť l</nowiki>11. V tomto prípade dostaneme dolnú trojuholníkovú maticu a štyri rovnice.
		+
		+	[[Image:Untitled%201_html_me6e6cab.png]] (3.2)
		+
		+	[[Image:Untitled%201_html_3bb15cf3.png]] (3.3)
		+
		+	[[Image:Untitled%201_html_4a22611f.png]] (3.4)
		+
		+	[[Image:Untitled%201_html_24abbc4b.png]] (3.5)
		+
		+	<nowiki>Možno dokázať, že existuje rozklad LU = A so základným argumentom (3.4) a induktívny predpoklad z rovnice (3.5) [3].</nowiki>[[Image:Untitled%201_html_2b18e193.png]] (3.6)
		+
		+	Rozklad LU = A existuje len vtedy, ak každý diagonálny prvok ukk je nenulový. Čiastočný výber hlavného prvku vedie k stabilnejšej variante LU = PA , kde P je matica permutácií . Pri čiastočnom výbere hlavného prvku, riadky matice A sú vymenené, a preto je [[Image:Untitled%201_html_bc4ade2.png]] maximalizované v každom kroku. Táto výmena môže byť určená pre prvý stĺpec matice A zostaví zostávajúce permutácie matice A. Nech P1, patriace do oboru reálnych čísel o rozmeroch [[Image:Untitled%201_html_m7ba66b87.png]]n, je permutačná matica ktorá vymieňa dva riadky A tak, že
		+
		+	<center>[[Image:Untitled%201_html_m4f626776.png]] (3.7)</center>
		+
		+	a [[Image:Untitled%201_html_c0f008f.png]]. Ak rovnica (3.1) a jej ekvivalentné formy (3.2) až (3.5) sú použité priamo na [[Image:Untitled%201_html_m200aba46.png]], vtedy nemožno použiť induktívny predpoklad (3.6). Ak LU = PA je výrok ktorého platnosť dokazujeme, induktívny predpoklad treba aplikovať na maticu menších rozmerov ale rovnakej formy. Rovnica (3.6) nemá permutačnú maticu. Potom induktívny predpoklad vyzerá nasledovne [[Image:Untitled%201_html_m51508616.png]] (3.8)
		+
		+	kde P2<nowiki> je permutačná matica [3]. </nowiki>
		+
		+
		+	Výraz (3.8) možno rozložiť na blokovú maticu aplikovaním rovníc (3.2) až (3.5) na [[Image:Untitled%201_html_m200aba46.png]] a vynásobením obidvoch strán rovnice (3.4) permutačnou maticou [[Image:Untitled%201_html_m16474b3d.png]]. Potom dostávame
		+
		+	[[Image:Untitled%201_html_62dd0f35.png]] (3.9)
		+
		+	[[Image:Untitled%201_html_6d4675c9.png]] (3.10)
		+
		+	[[Image:Untitled%201_html_m30970a6.png]] (3.11)
		+
		+	[[Image:Untitled%201_html_70e7494c.png]] (3.12)
		+
		+	Tieto štyri rovnice možno zapísať ako maticové rovnice rozmeru [[Image:Untitled%201_html_m12e42899.png]]
		+
		+	[[Image:Untitled%201_html_551d27d1.png]] = [[Image:Untitled%201_html_m46f9d020.png]]<nowiki>=</nowiki>[[Image:Untitled%201_html_m675955a8.png]] (3.13)
		+
		+	A úpravou rovnice (3.13) podľa (3.11) dostávame
		+
		+	[[Image:Untitled%201_html_551d27d1.png]] [[Image:Untitled%201_html_m560fee59.png]] (3.14)
		+
		+
		+	Teraz je rovnica (3.14) v požadovanom tvare [[Image:Untitled%201_html_4befde2d.png]] , kde
		+
		+	[[Image:Untitled%201_html_mb417c47.png]] [[Image:Untitled%201_html_m35ea2b1c.png]]
		+
		+	Algoritmus LU rozkladu vyžaduje [[Image:Untitled%201_html_m65f83ebb.png]]<nowiki> operácií [2][3].</nowiki>
		+
		+
		+	== Choleského rozklad ==
		+	<nowiki>Choleského rozklad je špeciálny rozklad matíc, ktorý možno použiť len na rozklad symetrických kladne definitných matíc. Takéto matice sa ale v určitých aplikáciách vyskytujú dosť často. Choleského rozklad je rýchlejší ako tradičný LU rozklad, pretože využíva špeciálne vlastnosti matíc[8]. </nowiki>
		+
		+	Majme systém lineárnych rovníc ''Ax = b'', kde ''A'' je [[Image:Untitled%201_html_m1f50f11c.png]]symetrická kladne definitná matica, ''b'' je známy vektor pravých strán, a ''x ''je hľadaný vektor riešení. Jedným so spôsobov riešenia je použitie Choleského rozkladu.
		+
		+	'''Veta''': Ak je matica symetrická kladne definitná, potom existuje dolná trojuholníková matica L, s kladnými diagonálnymi prvkami tak, že [[Image:Untitled%201_html_2a2d7a63.png]]
		+
		+	Rovnica (3.20)[[Image:Untitled%201_html_m3770d2cb.png]] sa nazýva Choleského rozkladom. Vektor riešení dostaneme vyriešením trojuholníkových systémov [[Image:Untitled%201_html_26e14bbd.png]] a[[Image:Untitled%201_html_bac0f1e.png]]<nowiki> [3].</nowiki>
		+
		+	Pri LU rozkladu prvky matíc L a U nemajú takmer žiadnu vzájomnú väzbu okrem toho, že ich súčinom dostaneme maticu A. Naopak pri Choleského rozklade pre prvky matíc platí [[Image:Untitled%201_html_75600095.png]]<nowiki> [8] .</nowiki>
		+
		+	Nech matica A a hľadaná matica L sú blokové matice [[Image:Untitled%201_html_696253c7.png]] so štvorcovými diagonálnymi blokmi . Vyjadrením (i,j) v rovnici [[Image:Untitled%201_html_m4a983f88.png]] , pre ktoré platí [[Image:Untitled%201_html_m35199ff4.png]], dostávame
		+
		+
		+	[[Image:Untitled%201_html_69681b68.png]]Definujme S, pre ktoré platí nasledovný vzťah:
		+
		+
		+	Potom podľa (3.16) platí že, [[Image:Untitled%201_html_m329aecfb.png]]ak [[Image:Untitled%201_html_3805e7f9.png]] a [[Image:Untitled%201_html_6eb573bb.png]] ak [[Image:Untitled%201_html_m304d7ffe.png]] . Tieto rovnice možno použiť pre výpočet všetkých [[Image:Untitled%201_html_1d0d5994.png]]<nowiki> [3] [8]. </nowiki>
		+
		+	Algoritmus Choleského rozkladu vyžaduje [[Image:Untitled%201_html_289b77e.png]]<nowiki> operácií, čo je v porovnaní s LU rozkladom o polovicu menej [3]. </nowiki>
		+
		+
		+	== Riešenie trojuholníkových systémov ==
		+	Riešenie trojuholníkových systémov lineárnych rovníc, či už hustých alebo riedkych, sa vyskytuje v mnohých aplikáciách. Pretože proces riešenia vyžaduje podstatne menší čas ako príslušný rozklad na trojuholníkový tvar, často požadujeme riešiť dané systémy s rôznymi pravými stranami ale pritom rovnakou trojuholníkovou maticou. Preto je potrebné ich riešiť čo možno najefektívnejšie.
		+
		+	=== Algoritmy riešenia trojuholníkových systémov ===
		+	Existujú dva klasické sekvenčné algoritmy pre riešenie trojuholníkových systémov Lx=b . Odlišujú sa v tom že jeden pristupuje k matici L po riadkoch a druhý algoritmus pristupuje po stĺpcoch.
		+
		+	Majme rozklad : [[Image:Untitled%201_html_m6664c1d2.png]] = [[Image:Untitled%201_html_2091c33a.png]] , kde [[Image:Untitled%201_html_m5e5abdc8.png]] je štvorcová pravá dolná submatica matice L o rozmeroch n-1. [[Image:Untitled%201_html_m1e0dd299.png]] sú stĺpcové vektory o dĺžke n-1. [[Image:Untitled%201_html_m6ac242f3.png]] sú skaláry. Toto vedie k dvom rovniciam [[Image:Untitled%201_html_1c78ceb1.png]] (3.17) a [[Image:Untitled%201_html_m458f3c1c.png]] (3.18)
		+
		+	Vyriešime prvú rovnicu (3.17) a získame tak x1 :
		+
		+
		+	Druhá rovnica (3.18) je dolný trojuholníkový systém vo forme [[Image:Untitled%201_html_6f51f94b.png]]. Tento systém možno riešiť rekurzívne a získať tak x2. Tento algoritmus využíva iteráciu cez stĺpce matice L. Môžeme si všimnúť, že b1 a b2 sú použité len raz . Preto môžeme v algoritme priradiť x do b a používame ďalej v algoritme už len x.
		+
		+
		+	'''Algoritmus s prístupom po stĺpcoch'''
		+
		+	x=b;
		+
		+	'''for''' j=1,... n-1 '''do'''
		+
		+	xj<nowiki>= x</nowiki>j / ljj
		+
		+	'''for''' i > j, lij[[Image:Untitled%201_html_m6647c5ea.png]] '''do'''
		+
		+	xj<nowiki>= x</nowiki>j – lij xj<nowiki>;</nowiki>
		+
		+	'''end for'''
		+
		+	'''end for'''
		+
		+
		+	'''Algoritmus prístupom po riadkoch'''
		+
		+	x=b;
		+
		+	x1<nowiki>= x</nowiki>1 / l11 <nowiki>;</nowiki>
		+
		+	'''for''' i=2,... n '''do'''
		+
		+	'''for '''j=1 ...i-1 '''do'''
		+
		+	xj<nowiki>= x</nowiki>j – lij xj<nowiki>;</nowiki>
		+
		+	'''end for'''
		+
		+	xi<nowiki>= x</nowiki>i / lii<nowiki>;</nowiki>
		+
		+	'''end for'''
		+
		+
		+	Pre riešenie Ux = b , kde U je uložená po stĺpcoch, použijeme ďalší rozklad
		+
		+	[[Image:Untitled%201_html_m7f281dea.png]] = [[Image:Untitled%201_html_2091c33a.png]]
		+
		+	Kde [[Image:Untitled%201_html_7829c687.png]] je štvorcová submatica matice U o rozmeroch n-1. Dostávame dve rovnice [[Image:Untitled%201_html_m471c1329.png]](3.19) a [[Image:Untitled%201_html_2c7f31f8.png]]. Druhú rovnicu (3.20) možno riešiť ako [[Image:Untitled%201_html_376bc6c7.png]] a z prvej (3.19) dostávame [[Image:Untitled%201_html_m254a4557.png]]<nowiki>. Tento horný trojuholníkový systém riešime podobne ako v predchádzajúcom prípade dolný trojuholníkový systém prostredníctvom algoritmu s prístupom po stĺpcoch [1][2].