Priame metódy pre riešenie veľkých sústav rovníc
Obsah
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 l11=1 je skalár a všetky tri matice sú štvorcové matice. Sú možné aj iné varianty ako zvoliť l11. 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 x1 :
[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 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= 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].
