Gaussin algoritmi

Gaussin algoritmi eli Gaussin eliminointimenetelmä on ensisijaisesti lineaarialgebran menetelmä, algoritmi, jolla voidaan ratkaista lineaarinen yhtälöryhmä matriisimuodossa. Se tuottaa alkuperäisen matriisin kanssa riviekvivalentin matriisin, josta yhtälöryhmän ratkaisut on mahdollista lukea. Gaussin eliminointimenetelmä toimii kaikissa mahdollisissa tapauksissa, joissa yhtälöryhmällä on 1) ääretön määrä ratkaisuja 2) yksi ratkaisu 3) ei ratkaisua.
Menetelmästä on olemassa myös laajennus, joka tunnetaan Gaussin-Jordanin eliminointimenetelmänä. Tässä menetelmässä matriisin porrasmuotoon saattamisen jälkeen sen työstämistä jatketaan kunnes matriisin tuntemattomia edustava vasen puoli muistuttaa yksikkömatriisia.
Historiaa.
Gaussin eliminointimenetelmä on nimetty matemaatikko Carl Friedrich Gaussin mukaan, mutta hän ei ole kehittänyt sitä. Ensimmäiset maininnat menetelmästä ovat jo vuosilta 150 eaa. - 179 kiinankielisessä kirjassa "Jiuzhang suanshu", Yhdeksän lukua matemaattisesta taiteesta. Nykymuotoonsa menetelmän kehitti Isaac Newton, jonka muistiinpanot mm. yhtälöistä julkaistiin vuonna 1707 teoksessa Arithmetica Universalis. Lopulta, vasta 1950-luvulla menetelmä sai nykyisen nimensä aiheen historiaan liittyvien väärinkäsitysten myötä. 
Algoritmin tausta.
Gaussin eliminointimenetelmä perustuu lineaarisen yhtälöryhmän seuraaviin ominaisuuksiin:
Suoritettaessa mikä tahansa edellä olevista operaatioista muodostetaan uusi, alkuperäisen kanssa ekvivalentti yhtälöryhmä. Toisin sanoen, alkuperäisen ja uuden yhtälöryhmän ratkaisujoukot ovat täsmälleen samat. 
Algoritmi.
Ratkaistaessa yhtälöryhmää, operoidaan itse asiassa ainoastaan tuntemattomien kertoimilla ja vakioilla. Itse tuntemattomat ovat "paikanpitäjän" roolissa. Näin ollen, mistä tahansa yhtälöryhmästä voidaan muodostaa matriisi seuraavasti:
Esimerkki matriisiesityksestä.
Yhtälöryhmää
formula_1
vastaa matriisiesitys
formula_2
jossa siis kolmessa vasemmanpuoleisimmassa sarakkeessa tuntemattomien kertoimet, rivin vastatessa yhtä yhtälöä, ja oikeanpuoleisessa sarakkeessa vakiot yhtälöittäin. 
Toiminta.
Itse Gaussin eliminointimenetelmä toimii seuraavasti: 
Annettu matriisi voidaan aina asettaa porrasmuotoon yhtälöryhmien operaatioita vastaavien alkeisrivitoimitusten avulla. Alkeisrivitoimituksella tarkoitetaan sitä, että 
Alkeisrivitoimituksia yksi kerrallaan, äärellisen määrän suorittamalla päästään alkuperäisen matriisin kanssa riviekvivalenttiin, porrasmuotoiseen matriisiin.
Matriisi on porrasmuodossa, mikäli seuraavat ehdot ovat voimassa:
Suoritetaan Gaussin algoritmi ja päästään matriisiin:
formula_3
joka on siis haluttu, porrasmuotoinen matriisi.
Tästä saadaan takaisinsijoituksella:
formula_4
formula_5
formula_6
Saatiin siis yksikäsitteinen ratkaisu. 
Mahdollisia ongelmia.
Virheherkkyys.
Yhtälöryhmien lähtöaineisto oikeassa elämässä ei läheskään aina ole absoluuttisen
täsmällistä. Jos kerroinmatriisi on lähellä singulaarista, pienetkin epätarkkuudet
saattavat muuttaa ratkaisua olennaisesti.
Skaalaus.
Jakajiksi voi tulla hyvin suuria/pieniä lukuja, mikä voi muuttaa kertoimien
suuruusluokkaa paljonkin.
Yli- ja alivuodot.
Mahdolliset liian suuret/pienet luvut tietokoneen käsiteltäväksi. Ongelma yleensä
vältettävissä oikealla skaalauksella.