- MATH.MA.140
- 3. Lineaariset yhtälöryhmät
- 3.4 Gauss–Jordanin eliminointimenetelmä
Gauss–Jordanin eliminointimenetelmä¶
Tavoitteena on muuttaa yhtälöryhmän matriisi alkeisrivimuunnosten avulla redusoiduksi porrasmatriisiksi, josta ratkaisut näkyvät suoraan. Voidaan osoittaa, että mikä tahansa matriisi voidaan muuttaa redusoiduksi porrasmatriisiksi ja että alkeisrivimuunnosten käyttämisjärjestys ei vaikuta tulokseen. Seuraava esimerkki näyttää, kuinka tämä tehdään.
Esimerkki 3.4.1
Muutetaan matriisi
redusoiduksi porrasmatriisiksi. Aloitetaan ensimmäisestä sarakkeesta. Vaihtamalla ensimmäisen ja toisen rivin paikat, saadaan ensimmäisen rivin johtavaksi alkioksi \(1\):
Tämän jälkeen johtavan alkion alla olevat alkiot on helppo muuttaa nolliksi. Vähennetään ensin toisesta rivistä ensimmäinen rivi luvulla \(2\) kerrottuna:
Lisätään sitten kolmanteen riviin ensimmäinen rivi luvulla 1 kerrottuna:
Nyt ensimmäinen sarake on halutussa muodossa. Siirrytään muokkaamaan toista saraketta. Muutetaan ensin sen johtava alkio ykköseksi, jotta voidaan toimia samoin kuin edellä. Kerrotaan siis toinen rivi luvulla \(-1\). Saadaan matriisi
Toisen rivin johtavan alkion avulla voidaan muuttaa sen alla oleva alkio nollaksi. Lisätään kolmanteen riviin toinen rivi luvulla 2 kerrottuna. Saadaan matriisi
joka on porrasmatriisi.
Jatketaan muokkaamista niin, että saadaan aikaan redusoitu porrasmatriisi. Muutetaan ensin viimeinenkin johtava alkio ykköseksi:
Muutetaan alimman rivin johtavan alkion avulla kaikki kolmannen sarakkeen muut alkiot nolliksi:
Näin saatu matriisi on redusoitu porrasmatriisi.
Saatu redusoitu porrasmatriisi on eri matriisi kuin se, josta lähdettiin liikkeelle. Matriisit myös vastaavat erilaisia yhtälöryhmiä. Näillä yhtälöryhmillä on kuitenkin samat ratkaisut lauseen 3.3.4 nojalla.
Redusoituun porrasmatriisiin voi päästä monia eri reittejä. On kuitenkin olemassa algoritmi, jonka avulla redusoidun porrasmatriisin voi tuottaa. Varsinkin alussa kannattaa käyttää sitä, sillä sattumanvarainen alkeisrivimuunnosten pyörittäminen menee helposti sotkuiseksi. Esimerkeissä on käytetty tätä algoritmia.
Ohje 3.4.2
Eräs tapa redusoidun porrasmatriisin muodostamiseen:
- Porrasmatriisia muodostetaan vasemmalta oikealle ja ylhäältä alaspäin.
- Johtavat alkiot kannattaa useimmiten muuttaa ykkösiksi. Aloita hankkimalla 1. rivin johtavaksi alkioksi ykkönen.
- Johtavan alkion avulla muutetaan sen alapuolella olevat alkiot nolliksi.
- Siirry sitten 2. riville. Hanki 2. rivin johtavaksi alkioksi ykkönen ja muuta sen avulla alapuolella olevat alkiot nolliksi. Jatka sitten eteenpäin aina alimmalle riville asti.
- Näin saadaan aikaan porrasmatriisi.
- Redusoitua porrasmatriisia muodostetaan oikealta vasemmalle ja alhaalta ylöspäin.
- Johtavien alkioiden avulla muutetaan niiden yläpuolella olevat alkiot nolliksi. Aloita alimmasta nollasta poikkeavasta rivistä. Muuta johtavan alkion avulla sen yläpuolella olevat alkiot nolliksi. Siirry sitten toiseksi alimmalle riville. Jatka eteepäin aina ylimmälle riville asti.
- Tee vain yksi alkeisrivimuunnos kerrallaan. Tällöin vältät todennäköisemmin virheet.
Nyt olemme valmiita ratkaisemaan yhtälöryhmiä. Seuraavissa esimerkeissä esiintyy erilaisia tapauksia, joihin yhtälöryhmän ratkaisussa voi päätyä.
Esimerkki 3.4.3
Ratkaistaan yhtälöryhmä
Yhtälöryhmän matriisi on
Tämä matriisi muutettiin redusoiduksi porrasmatriisiksi esimerkissä 3.4.1:
Redusoitua porrasmatriisia vastaava yhtälöryhmä on
Koska alkuperäisen yhtälöryhmän ratkaisut ovat lauseen 3.3.4 nojalla samat kuin lopuksi saadun yhtälöryhmän, on yhtälöryhmä ratkaistu. Sen ratkaisu on siis
Esimerkki 3.4.4
Ratkaistaan lineaarinen yhtälöryhmä
Muutetaan yhtälöryhmän matriisi redusoiduksi porrasmatriisiksi:
Vastaava yhtälöryhmä on
Alin yhtälö on aina epätosi, joten yhtälöryhmällä ei ole ratkaisuja.
Esimerkki 3.4.5
Ratkaistaan lineaarinen yhtälöryhmä
Muutetaan yhtälöryhmän matriisi redusoiduksi porrasmatriisiksi:
Saatua matriisia vastaa yhtälöryhmä
Alin yhtälö \(0 = 0\) on aina tosi. Se ei siis anna ratkaisujen kannalta mitään informaatiota ja voidaan unohtaa. Tuntemattomat \(x_1\) ja \(x_2\) riippuvat tuntemattomasta \(x_3\). Tuntemattomalle \(x_3\) ei puolestaan aseteta mitään rajoitteita, joten se voi olla mikä tahansa reaaliluku. Sanotaan, että \(x_3\) on vapaa muuttuja. Merkitään \(x_3 = t\), missä \(t \in \R\).
Ratkaistaan vielä muut tuntemattomat. Ensimmäinen yhtälö saa nyt muodon \(x_1-2t=1\), joten \(x_1=1+2t\). Toinen yhtälö puolestaan on \(x_2-3t=2\) eli \(x_2=2+3t\). Siten yhtälöryhmän ratkaisu on
Ratkaisuja on siis äärettömän monta. Yksittäisiä ratkaisuja saadaan antamalla parametrille \(t\) eri arvoja. Esimerkiksi sijoittamalla \(t = 1\) saadaan yhdeksi ratkaisuksi \(x_1 = 3\), \(x_2 = 5\) ja \(x_3 = 1\) . Sijoittamalla \(t = -1\) saadaan toinen ratkaisu \(x_1 = -1\), \(x_2 = -1\) ja \(x_3 = -1\). Jokaisella reaaliluvulla \(t\) yhtälöryhmälle saadaan eri ratkaisu.
Edellisessä esimerkissä yhtälöryhmässä oli vapaa muuttuja, jolloin yhtälöryhmällä oli äärettömän monta ratkaisua. Yhtälöryhmässä saattaa olla useitakin vapaita muuttujia. Nämä löytyvät redusoidussa porrasmatriisissa niistä sarakkeista, joissa ei ole lainkaan johtavaa alkiota.
Esimerkki 3.4.6
Lineaarisen yhtälöryhmän matriisi muutettiin alkeisrivimuunnoksilla redusoiduksi porrasmatriisiksi
Mikä on yhtälöryhmän ratkaisu?
Johtavat alkiot ovat sarakkeissa 1, 3 ja 6. Muita sarakkeita vastaavat tuntemattomat \(x_2\), \(x_4\) ja \(x_5\) ovat vapaita muuttujia. Merkitään \(x_2=r\), \(x_4 = s\) ja \(x_5 = t\), missä \(r\), \(s\), \(t \in \R\).
Nyt voidaan kirjoittaa
Tämä yhtälöryhmä on yhtäpitävä yhtälöryhmän
kanssa. Yhtälöryhmän ratkaisu on siis
Luvut \(r\), \(s\) ja \(t\) voidaan valita täysin vapaasti, ja jokainen valinta tuottaa yhtälöryhmän erään ratkaisun.
Kootaan vielä yhteen Gauss–Jordanin menetelmän vaiheet.
Ohje 3.4.7
Gauss–Jordanin menetelmä:
- Kirjoita yhtälöryhmän matriisi.
- Muuta matriisi alkeisrivimuunnoksilla redusoiduksi porrasmatriisiksi.
- Lue ratkaisut redusoidusta porrasmatriisista.
- Jos matriisin alimmalla nollasta poikkeavalla rivillä on ristiriitainen yhtälö, yhtälöryhmällä ei ole ratkaisuja.
- Jos epätotta yhtälöä ei ole ja jokaisessa viivan vasemmalla puolella olevassa sarakkeessa on johtava alkio, ratkaisuja on täsmälleen yksi.
- Jos epätotta yhtälöä ei ole ja jostain sarakkeesta puuttuu johtava alkio, ratkaisuja on äärettömän monta. Jokaista saraketta, josta johtava alkio puuttuu, vastaa vapaa muuttuja. Vapaan muuttujan arvo voidaan valita vapaasti.
Gauss ei itse kehittänyt nimeään kantavaa menetelmää, vaan sen tunsi jo ainakin Newton sata vuotta aikaisemmin 1600-luvun loppupuolella. Kiinalaiset puolestaan tunsivat menetelmän jo toisella vuosisadalla eKr. Nimitys ”Gaussin eliminointimenetelmä” tuli käyttöön kuitenkin vasta 1950-luvulla. Tällä nimityksellä tarkoitetaan yleensä nimenomaan porrasmatriisiin tähtäävää menetelmää, ja mikäli halutaan jatkaa redusoituun porrasmatriisiin asti, menetelmää kutsutaan ”Gauss–Jordanin eliminoinniksi”. Jordan esitti tämän version eliminointimenetelmästä vuonna 1887.
Tarkastellaan sitten hiukan erilaista tapaa kirjoittaa yhtälöryhmän ratkaisu. Lineaarisen yhtälöryhmän ratkaisuja voi ajatella listana lukuja. Ne voi siis kirjoittaa vektorin muodossa.
Esimerkki 3.4.8
Esimerkissä 3.4.3 saatiin yhtälöryhmälle ratkaisu
Ratkaisun voi ilmaista myös muodossa
Esimerkissä 3.4.5 puolestaan saatiin yhtälöryhmälle ratkaisu
Ratkaisun voi ilmaista myös muodossa
missä \(r,s,t \in \R\)
Puetaan vielä täsmällisten lauseiden muotoon Gauss–Jordanin muutamia menetelmään liittyviä tuloksia. Niiden todistuksia ei kuitenkaan esitetä tässä teknisyytensä vuoksi. Ensinnäkin, jotta Gauss–Jordanin menetelmä toimisi, täytyy tietää, että redusoidun porrasmatriisin muodostaminen on aina mahdollista.
Lause 3.4.9
Oletetaan, että \(A \in \R^{m \times n}\). Tällöin on olemassa yksikäsitteinen matriisi \(B \in \R^{m \times n}\), jolle pätevät seuraavat ehdot:
- \(A\) ja \(B\) ovat riviekvivalentteja,
- \(B\) on redusoitu porrasmatriisi.
Edellisen lauseen matriisia \(B\) kutsutaan matrisiin \(A\) redusoiduksi porrasmuodoksi tai redusoiduksi riviporrasmuodoksi. Sille käytetään merkintää \(\rref(A)\). Merkintä tulee englannin kielen ilmaisusta ”reduced row echelon form”.
Yhtälöryhmän ratkaisut luetaan redusoidusta porrasmatriisista. Kuten ohjeessa 3.4.7 todetaan, ratkaisujen lukumäärän suhteen voidaan päätyä vain kolmeen erilaiseen tulokseen.
Lause 3.4.10
Lineaarisella yhtälöryhmällä on joko täsmälleen yksi, ei yhtään tai äärettömän monta ratkaisua.
Määritelmä 3.4.11
Matriisin aste on sen redusoidussa porrasmuodossa esiintyvien johtavien alkioiden lukumäärä. Matriisin \(A\) astetta merkitään \(\rank(A)\).
Esimerkissä 3.4.1 nähtiin, että matriisin
redusoitu porrasmuoto on
Koska johtavia alkioita on kolme, on matriisin aste \(3\).
Porrasmatriisien tulkinta¶
Usein kiinnostavaa ei ole yhtälöryhmän tarkka ratkaiseminen, vaan se, kuinka monta ratkaisua yhtälöryhmällä on. Tällöin ei tarvitse muuttaa yhtälöryhmän matriisia redusoituun porrasmuotoon, vaan pelkkä porrasmuoto riittää. Kaikkia tässä osiossa esitettyjä väitteitä ei perustella tarkasti, sillä pitkien ja teknisten todistusten kirjoittaminen ei olisi mielekästä.
Kerrataan vielä, miten ratkaisujen lukumäärän voi lukea redusoidusta porrasmatriisista. Olkoon \(M\) redusoitu porrasmatriisi.
- Jos jokin matriisin \(M\) viimeisistä riveistä on muotoa \(\begin{augmatrix}{ccc|c}0 & \cdots & 0 & 1\end{augmatrix}\) (eli rivin johtava ykkönen on pystyviivan oikealla puolella), kyseistä riviä vastaa epätosi yhtälö \(0=1\). Yhtälöryhmällä ei ole ratkaisua.
- Oletetaan, että edellinen tapaus ei toteudu. Jos joltakin matriisin \(M\) sarakkeelta puuttuu johtava alkio (pystyviivan vasemmalta puolelta), tuota saraketta vastaava muuttuja on vapaa. Yhtälöryhmän ratkaisut voidaan esittää vapaiden muuttujien avulla. Kunkin vapaan muuttujan arvo voidaan valita vapaasti, joten yhtälöryhmällä on ratkaisuja ääretön määrä.
- Oletetaan, että edelliset tapaukset eivät toteudu. Tällöin matriisin \(M\) jokaisessa sarakkeessa pystyviivan vasemmalla puolella on johtava alkio, ja yhtälöryhmällä on täsmälleen yksi ratkaisu.
Esimerkki 3.4.12
Oletetaan, että yhtälöryhmän matriisi on saatu alkeisrivimuunnoksilla muotoon
Toiseksi viimeinen rivi vastaa yhtälöä \(0=-4\), joka on aina epätosi. Nyt tiedetään, että alkuperäisellä yhtälöryhmällä ei ole ratkaisuja, eikä redusoiduksi porrasmatriisiksi muuttaminen ole tarpeellista.
Tutkitaan sitten yhtälöryhmää, jonka matriisi on saatu alkeisrivimuunnoksilla porrasmatriisiksi
Tässäkin tapauksessa ratkaisujen lukumäärä nähdään suoraan. Koska porrasmatriisissa ei näy yhtälöä, joka olisi epätosi, ei sellaista tule redusoituun porrasmatriisiinkaan. Siten voidaan sanoa suoraan porrasmatriisin perusteella, että yhtälöryhmällä on ratkaisuja. Huomataan vielä, että porrasmatriisin kolmannessa sarakkeessa ei ole johtavaa alkiota. Jos matriisi muutettaisiin redusoiduksi porrasmatriisiksi, ei siinäkään olisi johtavaa alkiota kolmannessa sarakkeessa. Siten yhtälöryhmällä on äärettömän monta ratkaisua, ja sen näkee suoraan porrasmatriisista.
Tarkastellaan vielä lopuksi yhtälöryhmää, jonka matriisi on saatu alkeisrivimuunnoksilla porrasmatriisiksi
Epätosia yhtälöitä ei ole, joten yhtälöryhmällä on ratkaisuja. Koska jokaisessa sarakkeessa viivan vasemmalla puolella on johtava alkio, voidaan päätellä, että vapaita muuttujia ei ole. Siten yhtälöryhmällä on täsmälleen yksi ratkaisu.
Esimerkki 3.4.13
Tarkastellaan yhtälöryhmää
Tutkitaan, miten luvun \(k\) arvot vaikuttavat ratkaisujen lukumäärään. Ryhdytään muuttamaan yhtälöryhmän matriisia redusoiduksi porrasmatriisiksi:
Kaikki alkeisrivimuunnokset voidaan tähän asti tehdä riippumatta siitä, mikä luku \(k\) on. Jatkaminen ei kuitenkaan onnistu, sillä toisen rivin alkio \(k - 1\) saattaa olla nolla, samoin kolmannen rivin alkio \(2 - k - k^2\). Tarkastellaan näitä tapauksia erikseen.
Oletetaan ensin, että kolmannen rivin alkio \(2 - k - k^2 = 0\) eli \(k = -2\) tai \(k = 1\).
Jos \(k = -2\), viimeinen matriisi on
\[\begin{split}\begin{augmatrix}{rrr|r} 1&1&-2&1\\ 0&-3&3&0\\ 0&0&0&0\\ \end{augmatrix}.\end{split}\]Tämä matriisi on porrasmuodossa, joten siitä voidaan päätellä yhtälöryhmän ratkaisujen lukumäärä. Koska epätosia yhtälöitä ei ole, ratkaisuja on olemassa. Tuntematonta \(x_3\) vastaavassa sarakkeessa ei ole johtavaa alkiota, joten \(x_3\) on vapaa muuttuja. Ratkaisuja on siten äärettömän monta.
Jos \(k = 1\), viimeinen matriisi on
\[\begin{split}\begin{augmatrix}{rrr|r} 1&1&1&1\\ 0&0&0&0\\ 0&0&0&-3\\ \end{augmatrix}.\end{split}\]Havaitaan, että alinta riviä vastaava yhtälö \(0 = -3\) on aina epätosi. Siten yhtälöryhmällä ei ole ratkaisuja.
Oletetaan sitten, että toisen rivin alkio \(k-1 = 0\) eli \(k = 1\). Tämä tapaus käsiteltiin sattumalta jo edellä.
Tarkastellaan vielä lopuksi tilannetta, jossa sekä toisen rivin alkio \(k-1\) että kolmannen rivin alkio \(2 - k - k^2\) ovat nollasta poikkeavia. Tällöin voidaan jatkaa alkeisrivimuunnosten tekemistä. Koska \(k-1 \neq 0\) ja \(2 - k - k^2 \neq 0\) saadaan
Saatu matriisi on porrasmuodossa. Koska jokaisessa pystyviivan vasemmalla puolella olevassa sarakkeessa on johtava alkio, yhtälöryhmällä on täsmälleen yksi ratkaisu.
Päädyttiin siis seuraavaan tulokseen. Yhtälöryhmällä on äärettömän monta ratkaisua, jos ja vain jos \(k = -2\). Yhtälöryhmällä ei ole ratkaisua, jos ja vain jos \(k = 1\). Yhtälöryhmällä on tasan yksi ratkaisu, jos ja vain jos \(k \neq 1\) ja \(k \neq -2\).
Redusoidut porrasmatriisit ovat teoreettisesti mielenkiintoisia, koska jokaista matriisia vastaa täsmälleen yksi redusoitu porrasmatriisi. Edellä kuitenkin nähtiin, että yhtälöryhmän ratkaisujen lukumärä on luettavissa jo porrasmatriisista. Itse asiassa yhtälöryhmä voidaan jopa ratkaista porrasmatriisivaiheen avulla.
Esimerkin 3.4.5 yhtälöryhmää vastaava porrasmatriisi oli
Koska kolmannessa sarakkeessa ei ole johtavaa alkiota, sitä vastaava muuttuja on vapaa. Tähän havaintoon ei tarvita redusoitua porrasmuotoa. Jos merkitään \(x_3=t\), muut muuttujat voidaan ratkaista \(t\):n avulla. Toisen rivin perusteella
ja tämän jälkeen ensimmäisen rivin perusteella
Porrasmatriisi siis riittää yhtälöryhmän ratkaisemiseen.
Homogeeniset yhtälöryhmät¶
Määritelmä 3.4.14
Lineaarinen yhtälöryhmä, jonka kaikki vakiot ovat nollia, on nimeltään homogeeninen yhtälöryhmä.
Homogeeninen yhtälöryhmä on siis muotoa
missä \(a_{11},\dots,a_{mn} \in \R\). Homogeenisella yhtälöryhmällä on aina ainakin yksi ratkaisu:
Tätä kutsutaan yhtälöryhmän triviaaliksi ratkaisuksi.
Lause 3.4.15
Jos homogeenisessa yhtälöryhmässä tuntemattomien määrä \(n\) on suurempi kuin yhtälöiden määrä \(m\), yhtälöryhmällä on äärettömän monta ratkaisua.
Ensinnäkin yhtälöryhmällä on välttämättä ainakin triviaali ratkaisu. Siten ratkaisuja on joko yksi tai äärettömän monta.
Oletuksen mukaan yhtälöryhmän matriisissa on pystyviivan vasemmalla puolella enemmän sarakkeita kuin koko matriisissa on rivejä. Toisaalta johtavia alkioita on enintään yksi joka rivillä. Siten matriisissa on oltava pystyviivan vasemmalla puolella ainakin yksi sarake, jossa ei ole johtavaa alkiota. Näin ollen löytyy vapaa muuttuja, mistä seuraa, että yhtälöryhmällä on äärettömän monta ratkaisua.
- Gauss-Jordanin eliminointimentelmällä voi ratkaista lineaarisia yhtälöryhmiä.
- Gauss-Jordanin eliminointimentelmä antaa tavan, jolla matriisista voi aina muodostaa redusoidun porrasmatriisin. Tästä redusoidusta porrasmatriisista voidaan lukea yhtälöryhmän ratkaisut.
- Lineaarisella yhtälöryhmällä on joko yksi, ei yhtään tai äärettömän monta ratkaisua.
- Yhtälöryhmän ratkaisujen lukumäärän selville saamikseksi riittää muuttaa sitä vastaava matriisi porrasmuotoon.