\[\newcommand{\N}{\mathbb N}
\newcommand{\Z}{\mathbb Z}
\newcommand{\Q}{\mathbb Q}
\newcommand{\R}{\mathbb R}
\newcommand{\C}{\mathbb C}
\newcommand{\ba}{\mathbf{a}}
\newcommand{\bb}{\mathbf{b}}
\newcommand{\bc}{\mathbf{c}}
\newcommand{\bd}{\mathbf{d}}
\newcommand{\be}{\mathbf{e}}
\newcommand{\bff}{\mathbf{f}}
\newcommand{\bh}{\mathbf{h}}
\newcommand{\bi}{\mathbf{i}}
\newcommand{\bj}{\mathbf{j}}
\newcommand{\bk}{\mathbf{k}}
\newcommand{\bN}{\mathbf{N}}
\newcommand{\bn}{\mathbf{n}}
\newcommand{\bo}{\mathbf{0}}
\newcommand{\bp}{\mathbf{p}}
\newcommand{\bq}{\mathbf{q}}
\newcommand{\br}{\mathbf{r}}
\newcommand{\bs}{\mathbf{s}}
\newcommand{\bT}{\mathbf{T}}
\newcommand{\bu}{\mathbf{u}}
\newcommand{\bv}{\mathbf{v}}
\newcommand{\bw}{\mathbf{w}}
\newcommand{\bx}{\mathbf{x}}
\newcommand{\by}{\mathbf{y}}
\newcommand{\bz}{\mathbf{z}}
\newcommand{\bzero}{\mathbf{0}}
\newcommand{\nv}{\mathbf{0}}
\newcommand{\cA}{\mathcal{A}}
\newcommand{\cB}{\mathcal{B}}
\newcommand{\cC}{\mathcal{C}}
\newcommand{\cD}{\mathcal{D}}
\newcommand{\cE}{\mathcal{E}}
\newcommand{\cF}{\mathcal{F}}
\newcommand{\cG}{\mathcal{G}}
\newcommand{\cH}{\mathcal{H}}
\newcommand{\cI}{\mathcal{I}}
\newcommand{\cJ}{\mathcal{J}}
\newcommand{\cK}{\mathcal{K}}
\newcommand{\cL}{\mathcal{L}}
\newcommand{\cM}{\mathcal{M}}
\newcommand{\cN}{\mathcal{N}}
\newcommand{\cO}{\mathcal{O}}
\newcommand{\cP}{\mathcal{P}}
\newcommand{\cQ}{\mathcal{Q}}
\newcommand{\cR}{\mathcal{R}}
\newcommand{\cS}{\mathcal{S}}
\newcommand{\cT}{\mathcal{T}}
\newcommand{\cU}{\mathcal{U}}
\newcommand{\cV}{\mathcal{V}}
\newcommand{\cW}{\mathcal{W}}
\newcommand{\cX}{\mathcal{X}}
\newcommand{\cY}{\mathcal{Y}}
\newcommand{\cZ}{\mathcal{Z}}
\newcommand{\rA}{\mathrm{A}}
\newcommand{\rB}{\mathrm{B}}
\newcommand{\rC}{\mathrm{C}}
\newcommand{\rD}{\mathrm{D}}
\newcommand{\rE}{\mathrm{E}}
\newcommand{\rF}{\mathrm{F}}
\newcommand{\rG}{\mathrm{G}}
\newcommand{\rH}{\mathrm{H}}
\newcommand{\rI}{\mathrm{I}}
\newcommand{\rJ}{\mathrm{J}}
\newcommand{\rK}{\mathrm{K}}
\newcommand{\rL}{\mathrm{L}}
\newcommand{\rM}{\mathrm{M}}
\newcommand{\rN}{\mathrm{N}}
\newcommand{\rO}{\mathrm{O}}
\newcommand{\rP}{\mathrm{P}}
\newcommand{\rQ}{\mathrm{Q}}
\newcommand{\rR}{\mathrm{R}}
\newcommand{\rS}{\mathrm{S}}
\newcommand{\rT}{\mathrm{T}}
\newcommand{\rU}{\mathrm{U}}
\newcommand{\rV}{\mathrm{V}}
\newcommand{\rW}{\mathrm{W}}
\newcommand{\rX}{\mathrm{X}}
\newcommand{\rY}{\mathrm{Y}}
\newcommand{\rZ}{\mathrm{Z}}
\newcommand{\pv}{\overline}
\newcommand{\iu}{\mathrm{i}}
\newcommand{\ju}{\mathrm{j}}
\newcommand{\im}{\mathrm{i}}
\newcommand{\e}{\mathrm{e}}
\newcommand{\real}{\operatorname{Re}}
\newcommand{\imag}{\operatorname{Im}}
\newcommand{\Arg}{\operatorname{Arg}}
\newcommand{\Ln}{\operatorname{Ln}}
\DeclareMathOperator*{\res}{res}
\newcommand{\re}{\operatorname{Re}}
\newcommand{\im}{\operatorname{Im}}
\newcommand{\arsinh}{\operatorname{ar\,sinh}}
\newcommand{\arcosh}{\operatorname{ar\,cosh}}
\newcommand{\artanh}{\operatorname{ar\,tanh}}
\newcommand{\sgn}{\operatorname{sgn}}
\newcommand{\diag}{\operatorname{diag}}
\newcommand{\proj}{\operatorname{proj}}
\newcommand{\rref}{\operatorname{rref}}
\newcommand{\rank}{\operatorname{rank}}
\newcommand{\Span}{\operatorname{span}}
\newcommand{\vir}{\operatorname{span}}
\renewcommand{\dim}{\operatorname{dim}}
\newcommand{\alg}{\operatorname{alg}}
\newcommand{\geom}{\operatorname{geom}}
\newcommand{\id}{\operatorname{id}}
\newcommand{\norm}[1]{\lVert #1 \rVert}
\newcommand{\tp}[1]{#1^{\top}}
\renewcommand{\d}{\mathrm{d}}
\newcommand{\sij}[2]{\bigg/_{\mspace{-15mu}#1}^{\,#2}}
\newcommand{\abs}[1]{\lvert#1\rvert}
\newcommand{\pysty}[1]{\left[\begin{array}{@{}r@{}}#1\end{array}\right]}
\newcommand{\piste}{\cdot}
\newcommand{\qedhere}{}
\newcommand{\taumatrix}[1]{\left[\!\!#1\!\!\right]}
\newenvironment{augmatrix}[1]{\left[\begin{array}{#1}}{\end{array}\right]}
\newenvironment{vaugmatrix}[1]{\left|\begin{array}{#1}}{\end{array}\right|}
\newcommand{\trans}{\mathrm{T}}
\newcommand{\EUR}{\text{\unicode{0x20AC}}}
\newcommand{\SI}[3][]{#2\,\mathrm{#3}}
\newcommand{\si}[2][]{\mathrm{#2}}
\newcommand{\num}[2][]{#2}
\newcommand{\ang}[2][]{#2^{\circ}}
\newcommand{\meter}{m}
\newcommand{\metre}{\meter}
\newcommand{\kilo}{k}
\newcommand{\kilogram}{kg}
\newcommand{\gram}{g}
\newcommand{\squared}{^2}
\newcommand{\cubed}{^3}
\newcommand{\minute}{min}
\newcommand{\hour}{h}
\newcommand{\second}{s}
\newcommand{\degreeCelsius}{^{\circ}C}
\newcommand{\per}{/}
\newcommand{\centi}{c}
\newcommand{\milli}{m}
\newcommand{\deci}{d}
\newcommand{\percent}{\%}
\newcommand{\Var}{\operatorname{Var}}
\newcommand{\Cov}{\operatorname{Cov}}
\newcommand{\Corr}{\operatorname{Corr}}
\newcommand{\Tasd}{\operatorname{Tasd}}
\newcommand{\Ber}{\operatorname{Ber}}
\newcommand{\Bin}{\operatorname{Bin}}
\newcommand{\Geom}{\operatorname{Geom}}
\newcommand{\Poi}{\operatorname{Poi}}
\newcommand{\Hyperg}{\operatorname{Hyperg}}
\newcommand{\Tas}{\operatorname{Tas}}
\newcommand{\Exp}{\operatorname{Exp}}
\newcommand{\tdist}{\operatorname{t}}
\newcommand{\rd}{\mathrm{d}}\]
Yhtälönratkaisun idea
1. asteen yhtälöiden ratkaisu
Ennen kuin paneudutaan yhtälöryhmien ratkaisemiseen, tutkitaan yhtälönratkaisun ideaa yksikertasemmassa tapauksessa, jossa ratkaistavana on vain yksi yhtälö.
Koulussa opitaan ratkaisemaan ensimmäisen asteen yhtälöitä. Sellainen on esimerkiksi \(2x-5=4\). Yhtälönratkaisulle opitaan algoritmi eli järjestelmällinen sarja operaatioita, joilla yhtälön voi aina ratkaista:
\[\begin{split}\begin{aligned}
2x&-5=4 \\
2x&=4+5 \\
2x&=9 \\
x&=\frac{9}{2}
\end{aligned}\end{split}\]
Mutta mitä yhtälönratkaisussa oikeastaan tapahtuu? Miksi oheinen algoritmi tuottaa yhtälön ratkaisun?
Kirjoitetaan yhtälön ratkaisu uudelleen tällä kertaa selittäen välivaiheet ja täsmentäen merkintöjä:
\[\begin{split}\begin{aligned}
&&2x&-5=4 && \text{|| Lisätään yhtälön molemmille puolelille 5}\\
&\iff & 2x&=4+5 &&\\
&\iff &2x&=9 && \text{|| Kerrrotaan yhtällön molemmat puolet luvulla } \frac{1}{2} \\
&\iff &x&=\frac{9}{2} &
\end{aligned}\end{split}\]
Ekvivalenssinuoli \(\iff\) tarkoittaa, että peräkkäiset yhtälöt ovat yhtäpitävät. Ensimmäisestä yhtälöstä seuraa toinen ja toisesta ensimmäinen. Yhtälölle tehdyt operaatiot tuotavat yhtäpitäviä yhtälöitä, sillä operaatiot voi aina peruuttaa: Luvun \(5\) lisäämisen voi peruuttaa vähentämällä luvun \(5\). Luvulla \(\frac{1}{2}\) kertomisen voi peruuttaa kertomalla luvulla \(2\).
Yhtäpitävillä yhtälöillä on täsmälleen samat ratkaisut. Yhtälönratkaisualgoritmin ideana on, että yhtälöä muokataan aina vain yksinkertaisempaan muotoon tuottaen yhtäpitäviä yhtälöitä. Uuden yhtälön ratkaisut ovat aina samat kuin edellisen. Alimmalta riviltä ratkaisu on helppo nähdä, sillä se lukee siinä suoraan: \(x=\frac{9}{2}\). Tähän samaan ideaan perustuu myös lineaaristen yhtälöryhmien ratkaiseminen.
Lineaaristen yhtälöryhmien ratkaisemisen idea
Seuraavaksi tutustutaan Gaussin–Jordanin menetelmään, jolla voidaan ratkaista mikä tahansa lineaarinen yhtälöryhmä. Periaate on sama kuin 1. asteen yhtälöiden ratkaisussa. Ideana on muokata yhtälöryhmästä uusia yhtälöryhmiä,
joilla on samat ratkaisut kuin alkuperäisellä yhtälöryhmällä. Viimeisenä saatu
yhtälöryhmä on sellaisessa muodossa, josta sen ratkaisuja koskeviin kysymyksiin on helppo vastata. Koska viimeisen yhtälöryhmän ratkaisut ovat samat kuin alkuperäisen yhtälöryhmän, myös alkuperäisen yhtälöryhmän ratkaisut ja niiden luonne tunnetaan.
Yhtälöryhmä ratkaistaan muokkaamalla siitä uusia yhtälöryhmiä, jotka ovat ekvivalentteja alkuperäisen yhtälöryhmän kanssa.
Yhtälöryhmiä muokataan niin kutsutuilla alkeisrivimuunnoksilla.
Koska matriisien käsitteleminen on helpompaa kuin yhtälöryhmien, tehdään alkeisrivimuunnokset suoraan matriiseille.
Alkeisrivimuunnoksia kutsutaan myös alkeisrivioperaatioiksi tai alkeisrivitoimituksiksi.
Alkeisrivimuunnoksille käytetään tässä materiaalissa seuraavia
lyhennysmerkintöjä.
- \(R_i \leftrightarrow R_j\): vaihdetaan rivien \(i\) ja \(j\) paikat (\(i \neq j\)).
- \(aR_i\): kerrotaan rivi \(i\) luvulla \(a \neq 0\).
- \(R_i+bR_j\): lisätään riviin \(i\) rivi \(j\) luvulla \(b\) kerrottuna (\(i \neq j\)).
Esimerkki 4.3.3
Seuraavassa on annettu esimerkit erilaisista alkeisrivimuunnoksista:
\[\begin{split}\begin{augmatrix}{rcr}
-4&3&4 \\
1&2&-1 \\
5&3&2 \\
0&6&4
\end{augmatrix}
\overset{R_1 \leftrightarrow R_2}{\longrightarrow}
\begin{augmatrix}{rcr}
1&2&-1 \\
-4&3&4 \\
5&3&2 \\
0&6&4
\end{augmatrix}
\overset{R_3-5R_1}{\longrightarrow}
\begin{augmatrix}{rrr}
1&2&-1 \\
-4&3&4 \\
0&-7&7 \\
0&6&4
\end{augmatrix}
\overset{-\frac{1}{7}R_3}{\longrightarrow}
\begin{augmatrix}{rcr}
1&2&-1 \\
-4&3&4 \\
0&1&-1 \\
0&6&4
\end{augmatrix}.\end{split}\]
Lineaaristen yhtälöryhmien ratkaisu perustuu seuraavaan tulokseen.
Lause 4.3.4
Alkeisrivimuunnoksien tekeminen ei muuta yhtälöryhmän ratkaisuja. Toisin sanoen alkeisrivimuunnoksen tekeminen tuotaa yhtälöryhmän, joka on yhtäpitävä alkuperäisen yhtälöryhmän kanssa.
Piilota/näytä todistus
Täsmällinen todistus on melko tekninen, joten sitä ei esitetä tässä. Tutkitaan kuitenkin
todistuksen ideaa. Se perustuu siihen, että alkeisrivimuunnokset ovat kääntyviä eli tehdyn alkeisrivimuunnoksen voi aina peruuttaa. alkeisrivimuunnoksen \(R_i \leftrightarrow R_j\) voi peruuttaa tekemällä sen uudelleen.
alkeisrivimuunnoksen \(aR_i\) voi peruuttaa alkeisrivimuunnoksella \(\frac{1}{a}R_i\) ja alkeisrivimuunnoksen \(R_i+bR_j\) voi peruuttaa alkeisrivimuunnoksella \(R_i-bR_j\).
Jos lineaarisesta yhtälöryhmästä muodostetaan alkeisrivimuunnoksen avulla uusi yhtälöryhmä, pätee uusi yhtälöryhmä aina silloin, kun alkuperäinenkin yhtälöryhmä pätee. Siten kaikki alkuperäisen yhtälöryhmän ratkaisut ovat myös uuden yhtälöryhmän ratkaisuja. Toisaalta uudesta yhtälöryhmästä voidaan aina peruuttaa alkuperäiseen yhtälöryhmään jollakin alkeisrivimuunnoksella. Siten kaikki uuden yhtälöryhmän ratkaisut ovat myös alkuperäisen yhtälöryhmän ratkaisuja. Näin ollen molemmilla yhtälöryhmillä on samat ratkaisut.
Fig. 1: Gaussin–Jordanin eliminointimenetelmän perusta.
Esimerkki 4.3.6
Esimerkissä 4.3.3 matriisista
\[\begin{split}\begin{augmatrix}{rcr}
-4&3&4 \\
1&2&-1 \\
5&3&2 \\
0&6&4
\end{augmatrix}\end{split}\]
muokattiin alkeisrivimuunnoksella \(R_1 \leftrightarrow R_2\) matriisi
\[\begin{split}\begin{augmatrix}{rcr}
1&2&-1 \\
-4&3&4 \\
5&3&2 \\
0&6&4
\end{augmatrix}.\end{split}\]
Nämä kaksi matriisia ovat riviekvivalentteja. Kaikki muutkin esimerkissä esiintyvät matriisit ovat rivievivalentteja keskenään.
alkeisrivimuunnoksia voidaan ajatella tehtävän myös nolla kappaletta. Siten jokainen matriisi on itsensä kanssa riviekvivalentti.
Nyt lause 4.3.4 voidaan muotoilla toisin sanoin:
Jos yhtälöryhmiä vastaavat matriisit ovat riviekvivalentit, yhtälöryhmät ovat yhtäpitävät.
Porrasmatriisit ja redusoidut porrasmatriisit
Yhtälöryhmää ratkaistaessa on tavoitteena muuttaa yhtälöryhmän
matriisi alkeisrivimuunnoksilla niin kutsutuksi redusoiduksi porrasmatriisiksi,
josta ratkaisut on helppo lukea. Määritellään ensin porrasmatriisi.
Seuraavat matriisit ovat porrasmatriiseja. Niiden johtavat alkiot on lihavoitu.
\[\begin{split}\begin{augmatrix}{rrrr}
\mathbf{14}&3&2&4 \\
0&0&\mathbf{8}&0 \\
0&0&0&\mathbf{-3} \\
0&0&0&0
\end{augmatrix} \quad
\begin{augmatrix}{rrrrrr}
0&0&\mathbf{4}&0&0&-3 \\
0&0&0&\mathbf{-1}&7&-11 \\
0&0&0&0&\mathbf{1}&-3
\end{augmatrix} \quad
\begin{augmatrix}{rrrrrr}
\mathbf{-3}&-41&1&0&-3&6 \\
0&0&0&0&\mathbf{5}&-11 \\
0&0&0&0&0&0
\end{augmatrix}\end{split}\]
Porrasmuoto auttaa jo yhtälöryhmän ratkaisemisessa, mutta se ei ole yksikäsitteinen. Kutakin matriisia kohden löytyy nimittäin useampi kuin yksi sen kanssa riviekvivalentti porrasmatriisi. Porrasmatriisi voidaan kuitenkin muokata alkeisrivimuunnosten avulla redusoituun muotoon, joka on kullekin matriisille yksikäsitteinen.
Redusoituja porrasmatriiseja kutsutaan myös pidemmällä nimellä redusoitu riviporrasmatriisi.
Esimerkiksi seuraavat matriisit ovat redusoituja porrasmatriiseja. Johtavat alkiot on jälleen lihavoitu.
\[\begin{split}\begin{augmatrix}{rrrr}
\mathbf{1}&0&0&4 \\
0&\mathbf{1}&0&0 \\
0&0&\mathbf{1}&-3 \\
0&0&0&0
\end{augmatrix} \quad
\begin{augmatrix}{rrrrrrr}
0&0&\mathbf{1}&-53&0&0&-3 \\
0&0&0&0&\mathbf{1}&0&-11 \\
0&0&0&0&0&\mathbf{1}&-3 \\
\end{augmatrix} \quad
\begin{augmatrix}{rrrrrr}
\mathbf{1}&3&0&0&-3&8 \\
0&0&\mathbf{1}&-3&5&-11 \\
0&0&0&0&0&0
\end{augmatrix}\end{split}\]
Seuraavat matriisit puolestaan eivät ole redusoituja porrasmatriiseja:
\[\begin{split}\begin{augmatrix}{ccc}
\mathbf{1} & 2 & 1\\
0 & 0 & \mathbf{1}
\end{augmatrix},\qquad
\begin{augmatrix}{rrr}
\mathbf{1} & 0 & -3\\
0 & \mathbf{1} & 1\\
0 & 0 & \mathbf{1}
\end{augmatrix},\qquad
\begin{augmatrix}{cccc}
\mathbf{1} & 2 & 1 &0\\
0 & 0 & \mathbf{1}&0\\
0 & 0 & 0 &\mathbf{1}\\
\end{augmatrix}\qquad\text{ja}\qquad
\begin{augmatrix}{cccrcr}
\mathbf{1} & 2 & 0 &1&1&2\\
0 & 0 & \mathbf{1}&-2&0&-3\\
0 & 0 & 0 &0&\mathbf{1}&1\\
0 & 0 & 0 &0&0&0\\
\end{augmatrix}\end{split}\]
Niissä on nollasta poikkeavia alkioita johtavien ykkösten sarakkeissa.
Esimerkki 4.3.9
Matriisi
\[\begin{split}\begin{augmatrix}{rrr|r}
1 & 0 & 0 & 4 \\
0 & 1 & 0 & -2 \\
0 & 0 & 1 & 3 \\
\end{augmatrix}\end{split}\]
on redusoitu porrasmatriisi. Sitä vastaava yhtälöryhmä on
\[\begin{split}\left\{
\begin{array}{rcr}
x_1 & = & 4 \\
x_2 & = & -2 \\
x_3 & = & 3
\end{array}\right.\end{split}\]
Huomataan, että matriisista näkyy suoraan yhtälöryhmän ratkaisu.
- Alkeisrivimuunnoksia tehdessä matriisi muuttuu, mutta matriisia vastaavan yhtälöryhmän ratkaisut eivät muutu.
- Yhtälöryhmää ratkaistaessa sen matriisi muutetaan alkeisrivitoimituksilla ensin porrasmatriisiksi ja sitten redusoiduksi porrasmatriisiksi.
- Redusoidusta porrasmatriisista ratkaisu on helppo lukea.