"
  1. Gaußin (Jordanin) -eliminointimenetelmä

Gaußin (Jordanin) -eliminointimenetelmä

Usein puhutaan siis Gauß-Jordanin menetelmästä. Tässä esityksessä puhutaan lyhyesti Gaußin eliminoinnista. Aiemmin laskentakapasiteetin rajallisuuteen perustuen oli tarpeen erotella kaksi menetelmää riippuen siitä muunnetaanko kokonaismatriisi riviporrasmuotoon vai redusoituun riviporrasmuotoon. Nykyisin tällainen historiallinen jako on tarpeeton.

Epähomogeenisen lineaarisen yhtälöryhmän ratkaisu

Gaußin eliminointi on systemaattinen menetelmä yhtälöryhmän
\[\begin{split}\left\{ \begin{array}{ccc} a_{11}x_1+a_{12}x_2+ \cdots + a_{1n}x_n&=&b_1\\ a_{21}x_1+a_{22}x_2+ \cdots + a_{2n}x_n&=&b_2\\ &\vdots&\\ a_{m1}x_1+a_{m2}x_2+\cdots + a_{mn}x_n&=&b_m\\ \end{array} \right.\end{split}\]

ratkaisemiseksi. Palautetaan mieliin, että riviekvivalenteilla yhtälöryhmillä on samat ratkaisut, erityisesti alkuperäisellä matriisilla ja siitä alkeismuunnoksella saadulla redusoitua riviporrasmuotoa vastaavalla yhtälöryhmällä. Menetelmä on lyhykäisyydessään seuraava:

Gaußin eliminointimenetelmä
  • Kirjoitetaan lineaarinen yhtälöryhmä kokonaismatriisimuotoon \([A | \bbb]\).
  • Vaakarivimuunnosten avulla saatetaan kokonaismatriisi redusoituun riviporrasmuotoon.
  • Jos saatu yhtälöryhmä on ratkeava, niin ratkaistaan johtavat muuttujat vapaiden muuttujien avulla.

Menetelmässä vapaat muuttujat tarkoittavat muuttujia, joitka voidaan valita vapaasti ja esittää reaalisten parametrien avulla. Kuten muistamme yhtälösysteemillä voi olla:

  • Yksikäsitteinen ratkaisu,
  • Äärettömän monta ratkaisua,
  • Ei ratkaisuja.

Tarkastellaan esimerkkejä kaikista tapauksista:

Esimerkki.

Ratkaise yhtälöryhmä

\[\begin{split}\begin{aligned} x_1+3x_2+2x_3 &=1\\ 2x_2+x_3 &= 0\\ x_1+x_2 &=-1\end{aligned}\end{split}\]

Gaußin eliminoinnilla.

Ratkaisu.

Kirjoitetaan systeemi kokonaismatriisina ja muunnetaan se redusoituun riviporrasmuotoon:

\[\begin{split}[A|\bbb]=\begin{bmatrix} 1 & 3 & 2 & 1\\ 0 & 2 & 1 & 0\\ 1 & 1 & 0 & -1 \end{bmatrix} \longrightarrow \text{rref}([A|\bbb])=\begin{bmatrix} 1 & 0 & 0 & 0\\ 0 & 1 & 0 & -1\\ 0 & 0 & 1 & 2 \end{bmatrix}\end{split}\]

Kirjoitetaan nyt redusoitua riviporrasmuotoa vastaava ”yhtälöryhmä”, siis

\[\begin{split}\begin{aligned} x_1&=0\\ x_2&=-1\\ x_3&=2,\end{aligned}\end{split}\]

joka on yhtälöryhmämme ratkaisu. Näin ollen yhtälöryhmällä on siis yksikäsitteinen ratkaisu.

Esimerkki. :class: caution

Ratkaise yhtälöryhmä

\[\begin{split}\begin{aligned} x_1+2x_2+2x_3 &=1\\ x_1-2x_2+x_3 +x_4&= -1\\\end{aligned}\end{split}\]

Gaußin eliminoinnilla.

Ratkaisu.

Kirjoitetaan systeemi kokonaismatriisina ja muunnetaan se redusoituun riviporrasmuotoon:

\[\begin{split}[A|\bbb]=\begin{bmatrix} 1 & 2 & 2 & 0 & 1\\ 1 & -2 & 1 & 1 & -1\\ \end{bmatrix} \longrightarrow \text{rref}([A|\bbb])=\begin{bmatrix} 1 & 0 & 3/2 & 1/2 & 0\\ 0 & 1 & 1/4 & -1/4 & 1/2\\ \end{bmatrix}\end{split}\]

Kirjoitetaan nyt redusoitua riviporrasmuotoa vastaava ”yhtälöryhmä”, siis

\[\begin{split}\begin{aligned} x_1 + \frac{3}{2}x_3+\frac{1}{2}x_4&=0,\\ x_2+\frac{1}{4}x_3-\frac{1}{4}x_4 &=\frac{1}{2}.\end{aligned}\end{split}\]

Tästä nähdään, että \(x_1\) ja \(x_2\) voidaan esittää \(x_3\):n ja \(x_4\):n avulla, joita kutsutaan vapaiksi muuttujiksi. Toisin sanoa \(x_3\) ja \(x_4\) voidaan valita miten tahansa ja nämä sekä näiden avulla laskettu \(x_1\) ja \(x_2\) toteuttavat alkuperäisen yhtälön. Parametrisoidaan nyt \(x_3\) ja \(x_4\) ja kirjoitetaan ratkaisut muodossa

\[\begin{split}\begin{aligned} x_1 &= -\frac{3}{2}t-\frac{1}{2}s,\\ x_2 &=-\frac{1}{4}t+\frac{1}{4}s +\frac{1}{2},\\ x_3 &= t,\\ x_4 &= s,\end{aligned}\end{split}\]

kun \(t,s\in\mathbb{R}\). Näin ollen yhtälöryhmällä on äärettömän monta ratkaisua.

Esimerkki.

Ratkaise yhtälöryhmä

\[\begin{split}\begin{aligned} x_1+2x_2+2x_3 &=1\\ x_1-2x_2+x_3 &= -1\\ 2x_1 +3x_3&=2\end{aligned}\end{split}\]

Gaußin eliminoinnilla.

Ratkaisu.

Kirjoitetaan systeemi kokonaismatriisina ja muunnetaan se redusoituun riviporrasmuotoon:

\[\begin{split}[A|\bbb]=\begin{bmatrix} 1 & 2 & 2 & 1\\ 1 & -2 & 1 & -1\\ 2 & 0 & 3 & 2 \end{bmatrix} \longrightarrow \text{rref}([A|\bbb])=\begin{bmatrix} 1 & 0 & 3/2 & 0\\ 0 & 1 & 1/4 & 0\\ 0 & 0 & 0 & 1 \end{bmatrix}\end{split}\]

Kirjoitetaan nyt redusoitua riviporrasmuotoa vastaava ”yhtälöryhmä”, siis

\[\begin{split}\begin{aligned} x_1+\frac{3}{2}x_3=0,\\ x_2+\frac{1}{4}x_3=0,\\ 0=1.\end{aligned}\end{split}\]

Tästä nähdään että alimmalle yhtälölle muodostuu ristiriita, joka on voimassa kaikkien muuttujien \(x_1,x_2,x_3\) arvoilla, eli yhtälöryhmällä ei ole ratkaisua.

Homogeenisen lineaarisen yhtälöryhmän ratkaisu

homogeeniseksi :class: aside

,

jos yhtälön vakiotermi \(\bbb=\nol\). ENDB Tarkastellaan homogeenisen yhtälön ratkaisujen määrää. Välittömästi saadaan:

Huomautus.  Homogeenisella lineaarisella yhtälöryhmällä, jonka kokonaismatriisi on \([A|\nol]\), on aina vähintään yksi ratkaisu \(\xx=\nol\). Tämä on ns. triviaaliratkaisu. ENDB Yleisemmin saadaan:

Lause.  Jos \([A| \mathbf{0}]\) on \(m\) lineaarisen yhtälön ja \(n\) muuttujan homogeeninen yhtälöryhmä, missä \(m<n\), niin yhtälöryhmällä on äärettömän monta ratkaisua.

Todistus.
Tällöin Gaußin eliminoinnissa matriisin johtavien ykkösten lukumäärä (\(\le m\)) on pienempi, kuin pystyrivien lukumäärä (\(=n\)), voidaan aina jokin muuttuja ratkaista muiden avulla ja ratkaisuja on näin ollen äärettömän monta. \(\square\)

Esimerkki.

  • Ratkaise homogeeninen lineaarinen yhtälöryhmä

    \[\begin{split}\left\{ \begin{array}{lcc} \,x \,-2y\,+\,z&=&0\\ 3x-7y+2z&=&0.\\ \end{array}\right.\end{split}\]
Ratkaisu.

  • Muunnetaan yhtälöryhmä kokonaismatriisimuotoon \([A|\nol]\).

    \[\begin{split}[A|\nol]=\left[ \begin{array}{cccc} 1 & -2 & 1 & 0 \\ 3 & -7 & 2 & 0 \end{array}\right]\end{split}\]

    Edellisen lauseen perusteella voidaan jo tässä kohtaa todeta, että yhtälöryhmällä on äärettömän monta ratkaisua, sillä pystyrivejä (\(n=3\)) on enemmän kuin vaakarivejä \((n=2)\). Ratkaistaan kokonaismatriisin redusoitu riviporrasmuoto

    \[\begin{split}\begin{aligned} &[A|\nol]=\left[ \begin{array}{cccc} 1 & -2 & 1 & 0 \\ 3 & -7 & 2 & 0 \end{array}\right] \underrightarrow{R_2-3R_1} \left[ \begin{array}{cccc} 1 & -2 & 1 & 0 \\ 0 & -1 & -1 & 0 \end{array}\right] \\ & \underrightarrow{(-1)\cdot R_2} \left[ \begin{array}{cccc} 1 & -2 & 1 & 0 \\ 0 & 1 & 1 & 0 \end{array}\right] \underrightarrow{R_1+2R_2} \left[ \begin{array}{cccc} 1 & 0 & 3 & 0 \\ 0 & 1 & 1 & 0 \end{array}\right] = \text{rref}([A|\nol]) \end{aligned}\end{split}\]

    Redusoidusta riviporrasmuodosta saadaan muodostettua yhtälöryhmä

    \[\begin{split}\begin{cases} x+3z=0 \\ y+z=0 \end{cases}\end{split}\]

    Tässä yhtälöryhmässä \(x\) ja \(y\) ovat johtavia muuttujia ja \(z\) on vapaa muuttuja. Se siis voi saada minkä arvon tahansa ja kaksi muuta muuttujaa voidaan esittää sen avulla ratkaisussa. Esitetään vapaata muuttujaa parametrin \(t\) avulla, eli \(z=t, t\in \mathbb{R}\). Sijoitetaan tämä yhtälöpariin ja ratkaistaan \(x\) ja \(y\).

    \[\begin{split}\begin{cases} x+3t=0 \\ y+t=0 \end{cases} \iff \begin{cases} x = -3t \\ y = -t \\ z = t \end{cases}\end{split}\]

    Ratkaisu voidaan esittää vielä vektorimuodossa :math:`xx=tleft[ begin{array}{c}

    -3 \ -1 \ 1 end{array} right]`, \(t\in \mathbb{R}\). Nyt

    siis ratkaisuja on äärettömän monta, sillä parametri \(t\) voi saada äärettömän monta arvoa.