Gaussin eliminointimenetelmä¶

Edellä esitelty matriisin muuntaminen redusoituun riviporrasmuotoon motivoi Gauss-Jordanin menetelmän, eli lyhyesti Gaussin menetelmän yhtälöryhmän ratkaisemiseksi. Tavoitteena on eliminoida alkeisrivioperaatioiden avulla muuttujien esiintymiä yhtälöryhmässä.

Kirjoita lineaarisen yhtälöryhmän kokonaismatriisi \([A\mid\mathbf{b}]\).
Vie kokonaismatriisi redusoituun riviporrasmuotoon rivimuunnosten avulla.
Jos matriisin \(\operatorname{rref}[A\mid\mathbf{b}]\) alin rivi päättyy johtavaan ykköseen, ratkaisua ei ole. Muussa tapauksessa tunnista vapaat muuttujat.
Parametrisoi vapaat muuttujat ja kirjoita yhtälöryhmän ratkaisu.

Menetelmä toimii, sillä matriisien \([A\mid\mathbf{b}]\) ja \(\operatorname{rref}[A\mid\mathbf{b}]\) riviekvivalenttius takaa alkuperäisen yhtälöryhmän ja redusoitua riviporrasmuotoa vastaavan yhtälöryhmän ratkaisujen samuuden. Vapaalla muuttujalla tarkoitetaan yhtälöryhmän muuttujia, jotka voidaan valita vapaasti ja silti päätyä ratkaisuun. Jokaista ryhmän muuttujaa vastaa kokonaismatriisin sarake, ja vapaat muuttujat vastaavat niitä redusoidun riviporrasmuodon sarakkeita, joissa ei ole johtavaa ykköstä.

Tarkastellaan seuraavaksi esimerkkejä tapauksista, joissa yhtälöryhmällä on täsmälleen yksi, äärettömän monta tai ei yhtään ratkaisua. Käytännön sovelluksissa kokonaismatriisin redusointia ei tietenkään tehdä käsin, vaan esimerkiksi Matlabin komennolla rref.

Esimerkki.

Ratkaise yhtälöryhmä \(\begin{cases} x_1 + 3x_2 + 2x_3 = 1 \\ 2x_2 + x_3 = 0 \\ x_1 + x_2 = -1. \end{cases}\)

Ratkaisu.

Kirjoitetaan systeemi kokonaismatriisina ja muunnetaan se redusoituun riviporrasmuotoon.

\[\begin{split}[A\mid\mathbf{b}] = \begin{bmatrix} 1 & 3 & 2 & 1\\ 0 & 2 & 1 & 0\\ 1 & 1 & 0 & -1 \end{bmatrix} \longrightarrow \operatorname{rref}[A\mid\mathbf{b}] = \begin{bmatrix} 1 & 0 & 0 & 0\\ 0 & 1 & 0 & -1\\ 0 & 0 & 1 & 2 \end{bmatrix}\end{split}\]

Redusoitua riviporrasmuotoa vastaa yhtälöryhmä

\[\begin{split}\begin{aligned} \begin{cases} x_1 = 0 \\ x_2 = -1 \\ x_3 = 2, \end{cases}\qquad\text{eli}\qquad \mathbf{x}= \begin{bmatrix} 0 \\ -1 \\ 2 \end{bmatrix}.\end{aligned}\end{split}\]

Yhtälöryhmän ratkaisu on siis yksikäsitteinen.

Esimerkki.

Ratkaise yhtälöryhmä \(\begin{cases} x_1 + 2x_2 + 2x_3 = 1 \\ x_1 - 2x_2 + x_3 + x_4 = -1. \end{cases}\)

Ratkaisu.

Kirjoitetaan systeemi kokonaismatriisina ja muunnetaan se redusoituun riviporrasmuotoon.

\[\begin{split}[A\mid\mathbf{b}] = \begin{bmatrix} 1 & 2 & 2 & 0 & 1\\ 1 & -2 & 1 & 1 & -1\\ \end{bmatrix} \longrightarrow \operatorname{rref}[A\mid\mathbf{b}] = \begin{bmatrix} 1 & 0 & \frac{3}{2} & \frac{1}{2} & 0\\ 0 & 1 & \frac{1}{4} & -\frac{1}{4} & \frac{1}{2}\\ \end{bmatrix}\end{split}\]

Redusoitua riviporrasmuotoa vastaa yhtälöryhmä

\[\begin{split}\begin{aligned} \begin{cases} 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{cases}\end{aligned}\end{split}\]

missä \(x_3\) ja \(x_4\) ovat vapaita muuttujia. Asetetaan niille mielivaltainen reaalilukuarvo parametrisoimalla \(x_3 = t\) ja \(x_4 = s\), jolloin yhtälöryhmän yleinen ratkaisu on

\[\begin{split}\begin{aligned} \begin{cases} x_1 = -\frac{3}{2}t - \frac{1}{2}s \\ x_2 = \frac{1}{2} - \frac{1}{4}t + \frac{1}{4}s \\ x_3 = t \\ x_4 = s, \end{cases}\qquad\text{eli}\qquad \mathbf{x}= \begin{bmatrix} 0 \\ \frac{1}{2} \\ 0 \\ 0 \end{bmatrix} + t \begin{bmatrix} -\frac{3}{2} \\ -\frac{1}{4} \\ 1 \\ 0 \end{bmatrix} + s \begin{bmatrix} -\frac{1}{2} \\ \frac{1}{4} \\ 0 \\ 1 \end{bmatrix},\end{aligned}\end{split}\]

missä \(t\) ja \(s\) ovat reaalilukuja. Koska \(t\) ja \(s\) voidaan valita äärettömän monella tavalla, yhtälöryhmällä on äärettömän monta ratkaisua.

Esimerkki.

Ratkaise yhtälöryhmä \(\begin{cases} x_1 + 2x_2 + 2x_3 = 1 \\ x_1 - 2x_2 + x_3 = -1 \\ 2x_1 + 3x_3 = 2. \end{cases}\)

Ratkaisu.

Kirjoitetaan systeemi kokonaismatriisina ja muunnetaan se redusoituun riviporrasmuotoon.

\[\begin{split}[A\mid\mathbf{b}] = \begin{bmatrix} 1 & 2 & 2 & 1\\ 1 & -2 & 1 & -1\\ 2 & 0 & 3 & 2 \end{bmatrix} \longrightarrow \operatorname{rref}[A\mid\mathbf{b}] = \begin{bmatrix} 1 & 0 & \frac{3}{2} & 0\\ 0 & 1 & \frac{1}{4} & 0\\ 0 & 0 & 0 & 1 \end{bmatrix}\end{split}\]

Redusoitua riviporrasmuotoa vastaa yhtälöryhmä

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

jolla ei ole ratkaisua ristiriitaisen alimman rivin vuoksi.

Tarkastellaan vielä tärkeää lineaarisen yhtälöryhmän erikoistapausta.

Määritelmä.

Lineaarista yhtälöryhmää kutsutaan homogeeniseksi, jos sitä vastaava vakiotermivektori \(\mathbf{b}=\mathbf{0}\).

Ei ole vaikeaa nähdä, että homogeenisella lineaarisella yhtälöryhmällä on aina ratkaisu, sillä

\[a_{i1} \cdot 0 + a_{i2} \cdot 0 + \cdots + a_{in} \cdot 0 = 0.\]

Siis \((x_1, x_2, \ldots, x_n) = (0, 0, \ldots, 0)\) kelpaa ratkaisuksi. Toisin sanottuna homogeeninen lineaarinen yhtälöryhmä ei ole koskaan ristiriitainen. Nollaratkaisua kutsutaan homogeenisen yhtälöryhmän triviaaliratkaisuksi.

Lause.

Jos homogeenisessa lineaarisessa yhtälöryhmässä on vähemmän yhtälöitä kuin muuttujia, niin yhtälöryhmällä on äärettömän monta ratkaisua.

Todistus.

Oletetaan, että kokonaismatriisin \([A\mid\mathbf{0}]\) edustamassa yhtälöryhmässä on \(m\) yhtälöä ja \(n\) muuttujaa ja että \(m < n\). Gaussin eliminoinnissa syntyvien johtavien ykkösten lukumäärä \(p\) on korkeintaan rivien lukumäärä, eli oletuksen nojalla \(p \leq m < n\). Täten vapaiden muuttujien lukumäärä \(n - p > 0\), eli yhtälöryhmässä on vähintään yksi muuttuja, jonka arvo voidaan valita äärettömän monella tavalla. Täten ratkaisujakin on äärettömän monta. \(\square\)

Esimerkki.

Ratkaise homogeeninen lineaarinen yhtälöryhmä \(\begin{cases} x - 2y + z = 0 \\ 3x - 7y + 2z = 0. \end{cases}\)

Ratkaisu.

Edellisen lauseen perusteella voidaan jo tässä kohtaa todeta, että yhtälöryhmällä on äärettömän monta ratkaisua, sillä muuttujia (\(n=3\)) on enemmän kuin yhtälöitä \((m=2)\). Kirjoitetaan systeemi kokonaismatriisina ja muunnetaan se redusoituun riviporrasmuotoon.

\[\begin{split}\begin{aligned} = \begin{bmatrix} 1 & -2 & 1 & 0 \\ 3 & -7 & 2 & 0 \end{bmatrix} &\xrightarrow{R_2 - 3R_1} \begin{bmatrix} 1 & -2 & 1 & 0 \\ 0 & -1 & -1 & 0 \end{bmatrix} \xrightarrow{-R_2} \begin{bmatrix} 1 & -2 & 1 & 0 \\ 0 & 1 & 1 & 0 \end{bmatrix} \\ &\xrightarrow{R_1+2R_2} \begin{bmatrix} 1 & 0 & 3 & 0 \\ 0 & 1 & 1 & 0 \end{bmatrix} = \operatorname{rref}[A\mid\mathbf{0}]\end{aligned}\end{split}\]

Redusoitua riviporrasmuotoa vastaa yhtälöryhmä

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

missä \(z\) on vapaa muuttuja. Asetetaan sille mielivaltainen reaalilukuarvo parametrisoimalla \(z = t\), jolloin yhtälöryhmän yleinen ratkaisu on

\[\begin{split}\begin{cases} x = -3t \\ y = -t \\ z = t, \end{cases}\qquad\text{eli}\qquad \mathbf{x}= t \begin{bmatrix} -3 \\ -1 \\ 1 \end{bmatrix},\end{split}\]

missä \(t\) on reaaliluku.