Zobrazenie zdroja stránky Priame metódy pre riešenie veľkých sústav rovníc

[[Kategória:Študentské práce]]
[[Kategória:Ročníkové práce]]
[[Kategória:Matematika]]
{{Praca_uvod|3|Moderné metódy riešenia veľkých sústav lineárnych rovníc|Sústavy lineárnych rovníc a matice|Klasické metódy riešenia sústav lineárnych rovníc|Priame metódy pre riešenie veľkých sústav rovníc|Moderné metódy riešenia veľkých sústav rovníc|Softvérové balíky pre riešenie veľkých lineárnych systémov||||||||||}}
__TOC__
= =
Priame metódy vedú k&nbsp;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&nbsp;potom sa ďalej pracuje s&nbsp;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&nbsp;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&nbsp;na dve trojuholníkové matice. Kde L je dolná trojuholníková matica a&nbsp;U&nbsp;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&nbsp;kapitole 2.1.3. 

Odvodenie tejto metódy rozkladu začína nasledovnou maticovou rovnicou:

{{vzorec|<math>\left[ \begin{matrix}
   {{l}_{11}} & 0  \\
   {{l}_{21}} & {{L}_{22}}  \\
\end{matrix} \right]*~\left[ \begin{matrix}
   {{u}_{11}} & {{u}_{12}}  \\
   0 & {{U}_{22}}  \\
\end{matrix} \right]=\left[ \begin{matrix}
   {{a}_{11}} & {{a}_{12}}  \\
   {{a}_{21}} & {{A}_{22}}  \\
\end{matrix} \right]</math>|3.1}}

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.

{{vzorec|<math>{{u}_{11}}={{a}_{11}}</math>|3.2}}

{{vzorec|<math>{{u}_{12}}={{a}_{12}}</math>|3.3}}

{{vzorec|<math>{{l}_{21}}{{u}_{11}}={{a}_{21}}</math>|3.4}}

{{vzorec|<math>{{l}_{21}}{{u}_{12}}+{{L}_{22}}{{U}_{22}}={{A}_{22}}</math>|3.5}}

Možno dokázať, že existuje rozklad LU = A&nbsp;so základným argumentom (3.4) a&nbsp;induktívny predpoklad z&nbsp;rovnice (3.5) [3].

{{vzorec|<math>{{L}_{22}}{{U}_{22}}={{A}_{22}}-~{{l}_{21}}{{u}_{12}}</math>|3.6}}

Rozklad LU = A&nbsp;existuje len vtedy, ak každý diagonálny prvok ukk je nenulový. Čiastočný výber hlavného prvku vedie k&nbsp;stabilnejšej variante LU = PA , kde P je matica permutácií . Pri čiastočnom výbere hlavného prvku, riadky matice A&nbsp;sú vymenené, a preto je [[Image:Untitled%201_html_bc4ade2.png]] maximalizované v&nbsp;každom kroku. Táto výmena môže byť určená pre prvý stĺpec matice A&nbsp;zostaví zostávajúce permutácie matice A. Nech P1, patriace do oboru reálnych čísel o&nbsp;rozmeroch n×n, je permutačná matica ktorá vymieňa dva riadky A&nbsp;tak, že 

{{vzorec|<math>{{P}_{1}}A=\overline{A}=\left[ \begin{matrix}
   {{\overline{a}}_{11}} & {{\overline{a}}_{12}}  \\
   {{\overline{a}}_{21}} & {{\overline{A}}_{22}}  \\
\end{matrix} \right]</math>|3.7}}

a <math>\left| {{\overline{a}}_{11}} \right|\ge max\left| {{\overline{a}}_{21}} \right|</math>. Ak rovnica (3.1) a&nbsp;jej ekvivalentné formy (3.2) až (3.5) sú použité priamo na <math>\bar{A}</math>, 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 

{{vzorec|<math>{{L}_{22}}{{U}_{22}}={{P}_{2}}\left( {{\overline{A}}_{22}}-~{{l}_{21}}{{u}_{12}} \right)</math>|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 <math>\bar{A}</math> a&nbsp;vynásobením obidvoch strán rovnice (3.4) permutačnou maticou <math>P_2</math>. Potom dostávame 

{{vzorec|<math>{{u}_{11}}={{\overline{a}}_{11}}</math>|3.9}}

{{vzorec|<math>{{u}_{12}}={{\overline{a}}_{12}}</math>|3.10}}

{{vzorec|<math>{{P}_{2}{l}_{21}}{{u}_{11}}={P}_{2}{{\overline{a}}_{21}}</math>|3.11}}

{{vzorec|<math>{{P}_{2}}~{{l}_{21}}{{u}_{12}}+{{L}_{22}}{{U}_{22}}={{P}_{2}}{{\overline{A}}_{22}}</math>|3.12}}

Tieto štyri rovnice možno zapísať ako maticové rovnice rozmeru 2×2

{{vzorec|<math>\left[ \begin{matrix}
   1 & 0  \\
   {{P}_{2}}~{{l}_{21}} & {{L}_{22}}  \\
\end{matrix} \right]*~\left[ \begin{matrix}
   {{u}_{11}} & {{u}_{12}}  \\
   0 & {{U}_{22}}  \\
\end{matrix} \right]=\left[ \begin{matrix}
   {{\overline{a}}_{11}} & {{\overline{a}}_{12}}  \\
   {{P}_{2}}{{\overline{a}}_{21}} & {{P}_{2}}{{\overline{A}}_{22}}  \\
\end{matrix} \right]=\left[ \begin{matrix}
   1 & 0  \\
   0 & {{P}_{2}}  \\
\end{matrix} \right]*\left[ \begin{matrix}
   {{\overline{a}}_{11}} & {{\overline{a}}_{12}}  \\
   {{\overline{a}}_{21}} & {{\overline{A}}_{22}}  \\
\end{matrix} \right]</math>|3.13}}

A&nbsp;úpravou rovnice (3.13) podľa (3.11) dostávame 

{{vzorec|<math>\left[ \begin{matrix}
   1 & 0  \\
   {{P}_{2}}~{{l}_{21}} & {{L}_{22}}  \\
\end{matrix} \right]*~\left[ \begin{matrix}
   {{u}_{11}} & {{u}_{12}}  \\
   0 & {{U}_{22}}  \\
\end{matrix} \right]=\left[ \begin{matrix}
   1 & 0  \\
   0 & {{P}_{2}}  \\
\end{matrix} \right]*{{P}_{1}}A</math>|3.14}}

Teraz je rovnica (3.14) v&nbsp;požadovanom tvare LU=PA  , kde

<math>L=\left[ \begin{matrix}
   1 & 0  \\
   {{P}_{2}}~{{l}_{21}} & {{L}_{22}}  \\
\end{matrix} \right],\ U=\left[ \begin{matrix}
   {{u}_{11}} & {{u}_{12}}  \\
   0 & {{U}_{22}}  \\
\end{matrix} \right]~,P=\left[ \begin{matrix}
   1 & 0  \\
   0 & {{P}_{2}}  \\
\end{matrix} \right]*{{P}_{1}}</math>

Algoritmus LU rozkladu vyžaduje <math>2{{n}^{3}}/3</math>operácií [2][3].

== Choleského rozklad ==
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&nbsp;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].

Majme systém lineárnych rovníc ''Ax = b'', kde ''A''&nbsp;je n×n symetrická kladne definitná matica, ''b'' je známy vektor pravých strán, a&nbsp;''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&nbsp;kladnými diagonálnymi prvkami tak, že <math>A=L{{L}^{T}}</math>

Rovnica (3.20) sa nazýva Choleského rozkladom. Vektor riešení dostaneme vyriešením trojuholníkových systémov 
<math>Ly=b\ \ a\ \ {{L}^{T}}x=y</math> [3].

Pri LU rozkladu prvky matíc L a&nbsp;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í <math>{{L}_{ij}}=L_{ji}^{T}</math> <nowiki> [8] .</nowiki>

Nech matica A&nbsp;a&nbsp;hľadaná matica L sú blokové matice n×n so štvorcovými diagonálnymi blokmi . Vyjadrením (i,j) v&nbsp;rovnici (3.15) , pre ktoré platí i≥j , dostávame 

<math>{{A}_{ij}}=\underset{k=1}{\overset{j}{\mathop \sum }}\,{{L}_{ik}}L_{jk}^{T}</math>

Definujme S,&nbsp;pre ktoré platí nasledovný vzťah:

{{vzorec|<math>S={{A}_{ij}}-\underset{k=1}{\overset{j-1}{\mathop \sum }}\,{{L}_{ik}}L_{jk}^{T}</math>|3.16}}

Potom podľa (3.16) platí že, <math>{{L}_{jj}}L_{jj}^{T}=S~</math> ak i=j a <math>{{L}_{ij}}L_{jj}^{T}=S</math> ak i>j. Tieto rovnice možno použiť pre výpočet všetkých <math>L_{ij}</math><nowiki> [3] [8]. </nowiki>

Algoritmus Choleského rozkladu vyžaduje <math>{{n}^{3}}/3</math>operácií, čo je v&nbsp;porovnaní s&nbsp;LU rozkladom o&nbsp;polovicu menej [3]. 

== 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&nbsp;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&nbsp;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&nbsp;tom že jeden pristupuje k&nbsp;matici L po riadkoch a&nbsp;druhý algoritmus pristupuje po stĺpcoch. 

Majme rozklad : <math>\left[ \begin{matrix}
   {{l}_{11}} & 0  \\
   {{l}_{21}} & {{L}_{22}}  \\
\end{matrix} \right]*~\left[ \begin{matrix}
   {{x}_{1}}  \\
   {{x}_{2}}  \\
\end{matrix} \right]=\left[ \begin{matrix}
   {{b}_{1}}  \\
   {{b}_{2}}  \\
\end{matrix} \right]</math> , kde <math>L_{22}</math> je štvorcová pravá dolná submatica matice L o&nbsp;rozmeroch n-1. <math>{{l}_{21}},{{x}_{2}},{{b}_{2}}</math> sú stĺpcové vektory o&nbsp;dĺžke n-1. <math>{{l}_{11}},{{x}_{1}},{{b}_{1}}</math> sú skaláry. Toto vedie k&nbsp;dvom rovniciam 

{{vzorec|<math>{{l}_{11}}{{x}_{1}}={{b}_{1}}</math>|3.17}}

a

{{vzorec|<math>{{l}_{21}}{{x}_{1}}+{{L}_{22~}}{{x}_{2}}=~{{b}_{2}}</math>|3.18}}

Vyriešime prvú rovnicu (3.17) a&nbsp;získame tak x<sub>1</sub> :

<math>{{x}_{1}}=\frac{{{b}_{1}}}{{{l}_{11}}}</math>

Druhá rovnica (3.18) je dolný trojuholníkový systém vo forme <math>{{L}_{22}}{{x}_{2}}=~{{b}_{2}}-{{l}_{21}}{{x}_{1}}</math>. 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.


'''Algoritmus s prístupom po stĺpcoch''' 

<source lang="pascal">
   x=b;
   for j=1,... n-1 do
      xj= xj / Ljj ;
      for i > j,Lij != 0 do
         xj= xj – Lij * xj;
      end for
   end for
</source>


'''Algoritmus prístupom po riadkoch''' 

<source lang="pascal">
   x=b;
   x1= x1 / l11 ;
   for i=2,... n do
     for j=2,... i-1 do
       xj= xj - Lij * xj ;
     end for
    xi= xi / Lii;
   end for
</source>


Pre riešenie Ux = b , kde U&nbsp;je uložená po stĺpcoch, použijeme ďalší rozklad 

<math>\left[ \begin{matrix}
   {{U}_{11}} & {{u}_{12}}  \\
   0 & {{u}_{22}}  \\
\end{matrix} \right]*~\left[ \begin{matrix}
   {{x}_{1}}  \\
   {{x}_{2}}  \\
\end{matrix} \right]=\left[ \begin{matrix}
   {{b}_{1}}  \\
   {{b}_{2}}  \\
\end{matrix} \right]</math>

Kde <math>U_{11}</math> je štvorcová submatica matice U o&nbsp;rozmeroch n-1. Dostávame dve rovnice

{{vzorec|<math>U_11 x_1+u_12 x_2=b_1</math>|3.19}}

a 

{{vzorec|<math>{{u}_{22}}{{x}_{2}}={{b}_{2}}</math>|3.20}}

Druhú rovnicu (3.20) možno riešiť ako <math>{{x}_{2}}=\frac{{{b}_{2}}}{{{u}_{22}}}</math> a&nbsp;z&nbsp;prvej (3.19) dostávame <math>{{U}_{11}}{{x}_{1}}=~{{b}_{1}}-{{u}_{12}}{{x}_{2}}</math>. Tento horný trojuholníkový systém riešime podobne ako v&nbsp;predchádzajúcom prípade dolný trojuholníkový systém prostredníctvom algoritmu s&nbsp;prístupom po stĺpcoch [1][2].