Lineaarinen yhtälöryhmä
Lineaarinen yhtälöryhmä on nimensä mukaisesti yhtälöryhmä, joka koostuu tietystä määrästä lineaarisia yhtälöitä. "N":n muuttujan lineaarinen yhtälö on muotoa:
Siis "m":n yhtälön "n":n muuttujan lineaarinen yhtälöryhmä on muotoa:
Lineaarinen yhtälöryhmä voidaan esittää matriisimuodossa:
jossa matriisi formula_4 on formula_5'-kerroinmatriisi, formula_6 on ratkaistava sarakevektori ja formula_7 yhtälöryhmän ratkaisuvektori.
Lineaarista yhtälöryhmää kutsutaan homogeeniseksi, jos ratkaisuvektori on nollavektori eli formula_8.
Voimme tulkita lineaarisen yhtälöryhmän myös formula_9:n formula_10-ulotteisen hypertason, jotka määräytyvät yhtälöistä, leikkaukseksi formula_11-ulotteisessa avaruudessa. Siis kolmen muuttujan kolmen yhtälön ratkaisu on kolmiulotteisessa avaruudessa sijaitseva kolmen tason leikkaus. Olettaen, että ratkaisuja on olemassa, on olemassa leikkaus ja samoin, jos on olemassa leikkaus, on olemassa ratkaisuja.
Lineaarisella yhtälöryhmällä voi olla:Jos lineaarisella yhtälöryhmällä ei ole yhtään ratkaisua, sitä kutsutaan "inkonsistentiksi" tai "ristiriitaiseksi". Lineaarisen yhtälöryhmän ratkaisujen määrä voidaan aina luokitella johonkin näistä kolmesta ryhmästä, koska jos yhtälöllä on ratkaisuvektorit formula_12 ja formula_7, voidaan näistä muodostaa kolmas vektori, joka toteuttaa yhtälöt. Siis jos ratkaisuja on enemmän kuin yksi, niitä on äärettömän monta.
Ratkaisujen määrää voi myös ennustaa tiedosta, mikä on muuttujien määrän ja yhtälöiden määrän välinen ero:Tämä perustuu siihen, että kun yhtälöitä on vähemmän kuin muuttujia, ovat yhtälöt inkonsistentteja tai yhtälön ratkaisussa joudutaan ilmaisemaan ratkaisut vapaiden muuttujien avulla, jolloin saadaan ääretön määrä ratkaisuja. Mutta jos yhtälöitä on enemmän kuin muuttujia, ratkaisujen lukumäärästä ei voi tehdä päätelmiä, koska osa yhtälöistä voi olla yhtäpitäviä keskenään.
Yhtälöryhmän ratkaiseminen tapahtuu tavallisesti matriisimuodossa, koska se on helpommin implementoitavissa tietokonelaskentaan ja koska se on tiiviimpi ja kätevämpi kuin yhtälöryhmän standardi muoto.
Saamme yhtälöryhmää vastaavan matriisimuodon (täydennetty matriisi) lisäämällä kerroinmatriisiin yhden sarakkeen perään, eli:
Tämän matriisin ratkaisut ovat alkuperäisen lineaarisen yhtälöryhmän ratkaisut, ja kaikki laskutoimitukset, mitä voidaan tehdä lineaariselle yhtälöryhmälle, voidaan käsitellä matriisin alkeisrivitoimitusten avulla, joita ovat:Kun matriisille toimitetaan jokin yllä olevista operaatioista, sanotaan tulokseksi saadun matriisin olevan riviekvivalentti alkuperäisen matriisin kanssa ja sitä merkitään ~-merkillä. Merkkiä käytetään myös merkitsemään rivioperaatioita tehtäessä välivaiheita. Silloin sen yläpuolelle lisätään tehdyt rivioperaatioiden merkit. Rivioperaatioita merkitään kahdella tavalla, joista kumpikin on pätevä:Molemmat ilmaisevat: "Lisää rivi formula_18 kerrottuna vakiolla formula_19 riviin formula_20 ja laita se formula_20-riville". Samoin:merkitsee: "kerro rivi formula_18 vakiolla formula_19". Mainittakoot, että rivioperaatio voidaan aina kääntää, jolloin, jos matriisi formula_4 on riviekvivalentti formula_27:n kanssa, pätee sama toisin päin. Eli myös formula_27 on riviekvivalentti formula_4:n kanssa.
Tulee havaita, että rivioperaatiot eivät muuta matriisin ratkaisuja ja siten voisi herätä ajatus pyrkiä saamaan matriisi muotoon:
Tätä muotoa kutsutaan matriisin porrasmuodoksi (engl. "row echelon form"). Porrasmuotoisen matriisin jokaisen rivin ensimmäisen nollasta eroavan alkion alla on vain nollia, ja nollarivit ovat pohjalla. Tästä saadaan suoraan ratkaisut alkuperäiselle lineaariselle yhtälöryhmälle, koska tämän matriisin ratkaisujoukko on sama kuin alkuperäisellä matriisilla. Algoritmia, jolla matriisi saatetaan tähän muotoon, kutsutaan Gaussin eliminoinniksi. Sen perusideana on poistaa ensin ensimmäisestä sarakkeesta kaikki muut alkiot ja tehdä sama kaikille muille.
Huomaa, että jos eliminoinnin aikana päädymme riviin formula_31, jossa formula_32, tulisi yhtälöryhmästä tuloksena formula_33, mikä on mahdotonta. Tällöin yhtälöryhmällä ei ole ollenkaan ratkaisuja eli yhtälöryhmä on inkonsistentti.
Toisaalta voimme saada eliminoinnin aikana kokonaisen nollarivin, mikä ei tuota ristiriitaa, mutta yhtälöryhmälle emme saa yksikäsitteistä ratkaisua, koska emme saa viimeisestä yhtälöstä ensimmäistä viimeistä muuttujaa. Silloin joudumme ottamaan vapaan muuttujan ja päädymme äärettömään määrään ratkaisuja. Tästä muodosta on helpointa saada ratkaisut ja tehdä analyysiä ratkaisujen lukumäärästä, mutta joskus voidaan halutessa jatkaa matriisille toimitettuja rivioperaatioita niin, että päädytään muotoon:
mistä saamme suoraan ratkaisut. Tätä muotoa matriisista kutsutaan sen rref-muodoksi. Matriisin rref-muodossa jokaisen rivin ensimmäinen nollasta eroava alkio on yksi, ja sen sarakkeessa kaikki muut arvot ovat nollia, ja nollarivit ovat pohjalla. Algoritmia, jolla pääsemme tähän muotoon ref-muodosta kutsutaan Jordanin eliminoinniksi, ja siten eliminointia, jolla pääsemme tähän muotoon alkuperäisestä matriisista, kutsutaan Gaussin–Jordanin -eliminoinniksi. Tämä eliminointi on kuitenkin useimmiten tarpeetonta, koska ratkaisujen määrä näkyy suoraan ja nopeammin ref-muodosta. Lisäksi rref-muodon rakentamiseen tarvitaan yleensä vähintään saman verran rivioperaatioita kuin porrasmuotoon pääsemiseksi, mikä tekee siitä tehottoman varsinkin tietokonelaskennassa.
Teoreettisesti voimme kuitenkin todeta, että matriisin rref-muoto on yksilöllinen. Matriisin ref-muodosta on hyötyä myös determinantin määrityksessä, koska kolmiomatriisin, eli yhtä hyvin ref-muotoisen matriisin diagonaali-alkioiden tulo kertaa elementaarimatriisioperaatioiden vastaavien kerroinmatriisien determinantit, mikä on helppo määrittää.
Teoreettiselta merkitykseltänsä mielenkiintoisia ratkaisumenetelmiä on muutamia, jotka alla:
Algebrasta tutulla tavalla voimme ratkaista formula_35 kertomalla yhtälön puolittain "a". Samalla tavalla voimme ratkaista lineaarisen yhtälön matriisimuodosta formula_36. Kertomalla yhtälön puolittain (vasemmalta, matriiseista puhuttaessa on puoli määriteltävä) matriisin formula_4 käänteismatriisilla (olettaen tietysti, että se on olemassa) saamme:
Tämä näyttää ihan kätevältä menetelmältä, jos unohdamme hetkeksi, että matriisi on kääntyvä, jos ja vain jos se ei ole singulaarinen ja kun se on neliömatriisi. Tätä ratkaisua voimme käyttää, jos formula_4 on neliömatriisi ja sen determinantti on nollasta eroava. Käänteismatriisin laskeminen on kuitenkin hidasta ja numeerisesti epätarkkaa. Käänteismatriisi on teoreettisesti hyödyllinen, helppo toteuttaa tietokoneella, ja sillä voi tarkistaa yhtälöryhmän ratkaisun.
Laskemalla käänteismatriisi voidaan todistaa, että kun matriisi formula_4 on neliömatriisi ja ei-singulaarinen, ratkaisu saadaan kaavalla:
missä matriisi formula_42 saadaan vaihtamalla formula_18:s sarake ratkaisuvektorilla formula_7. Tämä sääntö kärsii samoista puutteista kuin matriisin kääntämiseen perustuva laskukaava, joten se on tehoton ottaen huomioon, että formula_4:n determinantti vaatii jo itsessään matriisin saattamista porrasmuotoon, jolloin yhtälöryhmä voitaisiin ratkaista takaisinsijoitusten avulla.