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

Obsah práce

1.	Sústavy lineárnych rovníc a matice
2.	Klasické metódy riešenia sústav lineárnych rovníc
3.	Priame metódy pre riešenie veľkých sústav rovníc
4.	Moderné metódy riešenia veľkých sústav rovníc
5.	Softvérové balíky pre riešenie veľkých lineárnych systémov

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

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

[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₁₁=1 je skalár a všetky tri matice sú štvorcové matice. Sú možné aj iné varianty ako zvoliť l₁₁. V tomto prípade dostaneme dolnú trojuholníkovú maticu a štyri rovnice.

[math]{{u}_{11}}={{a}_{11}}[/math]

(3.2)

[math]{{u}_{12}}={{a}_{12}}[/math]

(3.3)

[math]{{l}_{21}}{{u}_{11}}={{a}_{21}}[/math]

(3.4)

[math]{{l}_{21}}{{u}_{12}}+{{L}_{22}}{{U}_{22}}={{A}_{22}}[/math]

(3.5)

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

[math]{{L}_{22}}{{U}_{22}}={{A}_{22}}-~{{l}_{21}}{{u}_{12}}[/math]

(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 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 n×n, je permutačná matica ktorá vymieňa dva riadky A tak, že

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

[math]{{L}_{22}}{{U}_{22}}={{P}_{2}}\left( {{\overline{A}}_{22}}-~{{l}_{21}}{{u}_{12}} \right)[/math]

(3.8)

kde P2 je permutačná matica [3].

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 vynásobením obidvoch strán rovnice (3.4) permutačnou maticou [math]P_2[/math]. Potom dostávame

[math]{{u}_{11}}={{\overline{a}}_{11}}[/math]

(3.9)

[math]{{u}_{12}}={{\overline{a}}_{12}}[/math]

(3.10)

[math]{{P}_{2}{l}_{21}}{{u}_{11}}={P}_{2}{{\overline{a}}_{21}}[/math]

(3.11)

[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

[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 úpravou rovnice (3.13) podľa (3.11) dostávame

[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 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 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 je n×n 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 [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 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] [8] .

Nech matica A a hľadaná matica L sú blokové matice n×n so štvorcovými diagonálnymi blokmi . Vyjadrením (i,j) v 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, pre ktoré platí nasledovný vzťah:

[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] [3] [8].

Algoritmus Choleského rozkladu vyžaduje [math]{{n}^{3}}/3[/math]operácií, čo je v porovnaní s LU rozkladom o 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 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 : [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 rozmeroch n-1. [math]{{l}_{21}},{{x}_{2}},{{b}_{2}}[/math] sú stĺpcové vektory o dĺžke n-1. [math]{{l}_{11}},{{x}_{1}},{{b}_{1}}[/math] sú skaláry. Toto vedie k dvom rovniciam

[math]{{l}_{11}}{{x}_{1}}={{b}_{1}}[/math]

(3.17)

a

[math]{{l}_{21}}{{x}_{1}}+{{L}_{22~}}{{x}_{2}}=~{{b}_{2}}[/math]

(3.18)

Vyriešime prvú rovnicu (3.17) a získame tak x₁ :

[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 získať tak x₂. Tento algoritmus využíva iteráciu cez stĺpce matice L. Môžeme si všimnúť, že b₁ a b₂ 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= xj / Ljj ;
      for i > j,Lij != 0 do
         xj= xj – Lij * xj;
      end for
   end for

Algoritmus prístupom po riadkoch

   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

Pre riešenie Ux = b , kde U 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 rozmeroch n-1. Dostávame dve rovnice

[math]U_11 x_1+u_12 x_2=b_1[/math]

(3.19)

a

[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 z 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 predchádzajúcom prípade dolný trojuholníkový systém prostredníctvom algoritmu s prístupom po stĺpcoch [1][2].