Gaussova eliminačná metóda

Príklad 10. Zistite, či sústava lineárnych rovníc

$$\begin{array}{rrrrrrr} 2x_1 & + &4x_2 & - &2x_3 & = & 6 \\... ...+ & 6x_3 & = & -3 \\ & & & - &12x_3 & = & -3 \\ \end{array}$$

je riešiteľná a ak áno, nájdite jej riešenie.

Riešenie: Determinant odpovedajúcej matice sústavy je $(2)(-3)(-12) \neq 0$, a preto má sústava jediné riešenie. Iste ste si všimli, že z poslednej rovnice ľahko dostávame $r_3 = -3$/$-12 =1/4$. Z predposlednej potom platí $-3x_2 + 6(1/4)=-3$, a teda $r_2 = 3/2$. Konečne z prvej rovnice dostávame, že $r_1 = 3/2$. Potom ${\bf r }=(1/4,3/2,1/4)^T$. $\clubsuit$

Tento spôsob riešenia sústavy rovníc takéhoto tvaru sa nazýva spätná substitúcia.

Sústavy lineárnych rovníc Ax = b , Cx = d sa nazývajú ekvivalentné , ak každé riešenie sústavy Ax = b je riešením sústavy Cx = d a každé riešenie sústavy Cx = d je riešením sústavy Ax = b . Prechod od sústavy Ax = b ku ekvivalentnej sústave Cx = d realizujeme pomocou ekvivalentných úprav.

Uvažujme opäť o sústave (4.5). Gaussova eliminačná metoda (GEM) riešenia sústavy (4.5) je založená na tom, že od sústavy lineárnych rovníc Ax = b prejdeme ku ekvivalentnej sústave rovníc Cx = d , pričom matica C má vlastnosť

$${c_{ij} = 0} \hspace{0.5cm}\mbox{ pre }{ i > j} , { c_{ii} \neq 0}.$$

Matica C je teda regulárna horná trojuholníková matica. Spätnou substitúciou túto sústavu vyriešime a dostaneme tak riešenie pôvodnej sústavy Ax = b .

Ekvivalentné úpravy, ktoré používame pri GEM sú:

• G2: vynásobenie niektorej rovnice sústavy (t. j. jej pravej i ľavej strany) nenulovým číslom
• G3: pripočítanie násobku jednej rovnice sústavy ku inej rovnici sústavy (pripočítavame odpovedajúce si členy).

Všimli ste si, že nebola uvedená ekvivalentná úprava G1?

Príklad 11. GEM riešte sústavu

$$\begin{array}{rrrrrrrr} 2x_1 & + &4x_2 & - &2x_3 & = & 6 &... ... & 0 & \\ 4x_1 &+ &x_2 & - &2x_3 & = & 2 & . \\ \end{array}$$

Riešenie: Pretože $\vert{\bf A}\vert \neq 0$ (presvedčte sa ), má sústava práve jedno riešenie. Pomocou ekvivalentných úprav chceme dospieť ku sústave Cx = d , pričom matica C bude mať štruktúru:

$$\left( \begin{array}{rrr} \clubsuit & \clubsuit & \clubsui... ...uit & \clubsuit \\ 0 & 0 & \clubsuit \\ \end{array}\right)$$

a na diagonále nenulové prvky.

Vynásobme prvú rovnicu sústavy číslom $(-1/2)$ a pripočítajme ju ku druhej rovnici. Dostaneme sústavu

$$\begin{array}{rrrrrrrr} 2x_1 & + &4x_2 & - &2x_3 & = & 6 &... ...& -3 & \\ 4x_1 &+ &x_2 & - &2x_3 & = & 2 & . \\ \end{array}$$

Analogicky, ak vynásobíme prvú rovnicu číslom $(-2)$ a pripočítame ju ku tretej rovnici, dostaneme sústavu

$$\begin{array}{rrrrrrrr} 2x_1 & + &4x_2 & - &2x_3 & = & 6 &... ...= & -3 & \\ &- &7x_2 & + &2x_3 & = & -10 & . \\ \end{array}$$

Teraz už platí, že prvky prvého stĺpca odpovedajúcej matice sústavy, až na prvok v pozícii $(1,1)$, sú nulové.

Vynásobením druhej rovnice číslom $7/(-3)$ a pripočítaním ku tretej rovnici konečne dostaneme

$$\begin{array}{rrrrrrrr} 2x_1 & + &4x_2 & - &2x_3 & = & 6 &... ..._3 & = & -3 & \\ & & & - &12x_3 & = & -3 & . \\ \end{array}$$

To je ale sústava s takou maticou, akou sme si želali. Túto sústavu sme spätnou substitúciou riešili v predchádzajúcom príklade. Preto vieme, že ${\bf r }=(1/4,3/2,1/4)^T$.
$\clubsuit$

Vráťme sa ku všeobecnej sústave (4.5). Sformulujeme všeobecnú stratégiu pri GEM.

Prepokladajme, že prvok $a_{11} \neq 0$. Pripočítaním vhodných násobkov prvej rovnice ku zostávajúcim $(n-1)$ rovniciam dosiahneme, že koeficienty pri $x_1$ v týchto rovniciach budú nulové. Postupne budeme prvú rovnicu násobiť číslami

$${\frac{-a_{21}}{a_{11}}} , {\frac{-a_{31}}{a_{11}}}, \ldots ,{\frac{-a_{n1}}{a_{11}}. }$$

Tým sa dostaneme ku sústave tvaru

$$\begin{array}{rrrrrrrrrrll} a_{11}x_1&+&a_{12}x_2&+&a_{13}x_... ...}x_3&+& \ldots &+&a_{nn}^{(1)}x_n&=&b_n^{(1)}&. \\ \end{array}$$

Horný index naznačuje, že sme ukončili prvý krok GEM.
V druhom kroku GEM, za predpokladu že $a_{22}^{(1)} \neq 0$, budeme pracovať iba so zostávajúcimi $(n-1)$ rovnicami. Vynásobením druhej rovnice číslami

$${\frac{-a_{32}^{(1)}}{a_{22}}} , {\frac{-a_{42}^{(1)}}{a_{22}}}, \ldots ,{\frac{-a_{n2}^{(1)}}{a_{22}}}$$

známym postupom dospejeme ku sústave

$$\begin{array}{rrrrrrrrrrll} a_{11}x_1&+&a_{12}x_2&+&a_{13}x_... ...}x_3&+& \ldots &+&a_{nn}^{(2)}x_n&=&b_n^{(2)}&. \\ \end{array}$$

Ďalej pokračujeme analogicky.

Za predpokladu,že

$${ {a_{11}\neq 0},{a_{22}^{(1)} \neq 0},{a_{33}^{(2)}\neq 0},\ldots,{a_{n-1n-1}^{(n-2)}\neq 0}, }$$

sa po $(n-1)$ krokoch konečne dostaneme ku sústave

$$\begin{array}{rrrrrrrrrrll} a_{11}x_1&+&a_{12}x_2&+&a_{13}x_... ... & & &\ddots &a_{nn}^{(n-1)}x_n&=&b_n^{(n-1)}&. \\ \end{array}$$

Pre maticu C tejto sústavy zrejme platí $c_{ij} = 0$ pre $i>j$ a $\vert {\bf C}\vert =a_{11}. a_{22}^{(1)}. \ldots . a_{nn}^{(n-1)} \neq 0$, lebo $\vert{\bf A}\vert \neq 0$. Tým je skončená prvá časť GEM. Nasleduje druhá časť, riešenie sústavy Cx = d spätnou substitúciou.

Čísla $a_{kk}^{(k-1)}$ pre $k=1,2, \ldots ,n-1$ nazývame pivot $k$ -teho kroku GEM. Pritom ${a_{11}^{(0)}}\equiv a_{11}$.

Existujú dve triedy matíc A, pre ktoré takto popísaná GEM je realizovateľná.

• Nech A je matica sústavy (4.5). Nech platí
  
  $${ {\vert a_{ii}\vert} \geq { \sum_{i=1, i \neq j}^n {\vert a_{ij}\vert}} }$$
  
  
  (matica A sa vtedy nazýva diagonálne dominantná),
  ${{\vert{\bf A} \vert} \neq 0}$. Potom GEM je realizovateľná.

  (Ak pre aspoň jedno $i$ platí
  

  $${ {\vert a_{ii}\vert} > { \sum_{i=1, i \neq j}^n {\vert a_{ij}\vert}} },$$
  
  
  tak matica ${\bf A}$ sa nazýva ostro diagonálne dominantná. )
• Nech A je matica sústavy (4.5). Nech ${\bf A = A^T}$ ( matica A je teda symetrická). Nech pre všetky nenulové vektory ${{{\bf y}=(y_1,y_2, \ldots ,y_n)^T}} \neq {\bf0 }$ platí
  
  $${ {{{\bf y^TAy}} \equiv { \sum_{i=1}^n {\sum_{j=1}^n {a_{ij}y_iy_j}} }} > 0 }$$
  
  
  (matica A sa vtedy nazýva kladne definitná). Potom je GEM realizovateľná.

Diagonálna dominantnosť je ľahko verifikovateľná. O mnohých sústavách lineárnych rovníc, ktoré vznikajú pri riešení praktických problémov sa vie, že matica sústavy je kladne definitná, prípadne je známa podmienka, väčšinou ľahko splniteľná na to, aby matica sústavy bola kladne definitná.

Sústavu lineárnych rovníc

$$\begin{array}{rrrrrrr} & & x_2 & + & x_3 & = & 2 \\ -x_1 ... ...3 & = & 1 \\ x_1 & + & 2x_2 & + & x_3 & = & 1 \\ \end{array}$$

nemôžeme riešiť GEM. Vadí nám samozrejme číslo $0$ pri $x_1$ v prvej rovnici. Iste ste sami prišli na to, že môžeme definovať ďalšiu ekvivalentnú úpravu:

• G1: vzájomná výmena niektorých dvoch rovníc sústavy.

Pridaním tejto ekvivalentnej úpravy sa značne rozšírila trieda rovníc Ax = b , na ktoré môžeme úspešne použiť GEM. Ako uvidíme v časti o numerických metódach riešenia sústav lineárnych rovníc, má úprava G1 aj ďalší, tiež podstatný význam. Je nutné používať G1 aj v iných situáciach, ako sa vyskytla v predchádzajúcej sústave rovníc.

Pri použití GEM nie je nutné preverovať podmienku, či ${{\vert\bf A\vert} \neq 0}$. Na základe známych vlastností determinantov platí: ak ${{\vert\bf A\vert} \neq 0}$, tak aj ${{\vert\bf C\vert} \neq 0}$. (A teda, ak ${{\vert\bf C\vert}=0}$, tak aj ${{\vert\bf A\vert}=0}$. )Pre regulárnosť matice A je totiž podstatné iba to, že ${{\vert\bf A\vert} \neq 0}$ a nie akú má nenulovú hodnotu.

Ekvivalentné úpravy G1, G2, G3 nápadne pripomínajú riadkové operácie O1, O2, O3, ktoré sa používali pri vytvorení Gaussovho tvaru matice. Stačí len ``zrušiť" neznáme $x_1,x_2,\ldots,x_n$ a pracovať s rozšírenou maticou ${(\bf A\vert b)}$. Po nájdení jej Gaussovho tvaru je potrebné zas ``pripísať si" neznáme $x_1,x_2,\ldots,x_n$ za odpovedajúce koeficienty a máme sústavu Cx = d . Technický rozdiel, (ktorý ale vymizne, ak použijeme spätnú substitúciu), je ten, že Gaussov tvar matice vyžadoval vedúce jednotky, kým GEM vyžaduje, aby vedúce prvky (pivoty) ako analógie vedúcich jednotiek boli rôzne od nuly. Samozrejme, že použitím G2 by sme dosiahli, aby boli jednotkami.

Jedna z modifikácií GEM sa nazýva Gaussova -- Jordanova eliminačná metóda. Tá vyžaduje, aby sme sa od sústavy Ax = b cez sústavu Cx = d dostali ku sústave Ex = f , pričom matica E je diagonálna s $e_{ii} \neq 0$. Súvis s redukovaným Gaussovým tvarom matice je už zrejmý.