Gaussin algoritmi

Wikipedia
Loikkaa: valikkoon, hakuun

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[muokkaa | muokkaa wikitekstiä]

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[muokkaa | muokkaa wikitekstiä]

Gaussin eliminointimenetelmä perustuu lineaarisen yhtälöryhmän seuraaviin ominaisuuksiin:

  • Yhtälöryhmän kahden yhtälön paikkaa voidaan vaihtaa
  • Yhtälöryhmän yhtälö voidaan kertoa puolittain nollasta poikkeavalla vakiolla
  • Yhtälöryhmän yhtälö voidaan lisätä yhtälöryhmän toiseen yhtälöön, kerrottuna nollasta poikkeavalla vakiolla

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[muokkaa | muokkaa wikitekstiä]

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ä[muokkaa | muokkaa wikitekstiä]

Yhtälöryhmää

\begin{cases}
2x + y - z &= 8 \\
-3x - y + 2z &= -11 \\
-2x + y + 2z &= -3 \\
\end{cases}

vastaa matriisiesitys


\left[ \begin{array}{ccc|c}
2 & 1 & -1 & 8 \\
-3 & -1 & 2 & -11 \\
-2 & 1 & 2 & -3
\end{array} \right]

jossa siis kolmessa vasemmanpuoleisimmassa sarakkeessa tuntemattomien kertoimet, rivin vastatessa yhtä yhtälöä, ja oikeanpuoleisessa sarakkeessa vakiot yhtälöittäin.

Toiminta[muokkaa | muokkaa wikitekstiä]

Itse Gaussin eliminointimenetelmä toimii seuraavasti: Annettu matriisi voidaan aina asettaa porrasmuotoon yhtälöryhmien operaatioita vastaavien alkeisrivitoimitusten avulla. Alkeisrivitoimituksella tarkoitetaan sitä, että

  • Rivi kerrotaan jollain nollasta eroavalla vakiolla.
  • Rivi kerrotaan jollain nollasta eroavalla vakiolla ja lisätään se johonkin toiseen riviin.
  • Kaksi matriisin riviä vaihdetaan keskenään.

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:

  • Nollarivit (jos niitä on) ovat alimpina.
  • Jokaisen nollasta eroavan rivin vasemmalta lukien ensimmäinen nollasta eroava alkio, ko. rivin johtava alkio = 1.
  • Alemman rivin johtavan alkion sarake sijaitsee aina ylemmän rivin johtavan alkion sarakkeen oikealla puolella.

Suoritetaan Gaussin algoritmi ja päästään matriisiin:


\left[ \begin{array}{ccc|c}
1 & \frac{1}{3} & -\frac{2}{3} & \frac{11}{3} \\
0 & 1 & \frac{2}{5} & \frac{13}{5} \\
0 & 0 & 1 & -1
\end{array} \right]

joka on siis haluttu, porrasmuotoinen matriisi.

Tästä saadaan takaisinsijoituksella:

z = -1
y + \frac{2}{5}z = \frac{13}{5} \Longleftrightarrow y = 3
x + \frac{1}{3}y -\frac{2}{3}z = \frac{11}{3} \Longleftrightarrow x = 2

Saatiin siis yksikäsitteinen ratkaisu.

Gaussin algoritmi tietokoneelle[muokkaa | muokkaa wikitekstiä]

i=1
j=1
while (i ≤ m and j ≤ n) do
  # Etsi johtava alkio sarakkeelta j, alkaen riviltä i:
  max_val = A[i,j]
  max_ind = i
  for k=i+1 to m do
    val = A[k,j]
    if abs(val) > abs(max_val) then
      max_val = val
      max_ind = k
    end_if
  end_for
  if max_val ≠ 0 then
    vaihda rivit i ja max_ind
    jaa i luvulla max_val
    for u = 1 to m do
       if u ≠ i then
          lisää -A[u,j] * rivi i riviin u
       end_if
    end_for
    i = i + 1
  end_if
  j = j + 1
end_while

Gaussin eliminointimenetelmän sovelluksia[muokkaa | muokkaa wikitekstiä]

Kaikki lineaariseksi yhtälöryhmäksi puettavat ongelmat[muokkaa | muokkaa wikitekstiä]

  • Esim. sähköverkot, liikennevirrat, tuotanto ja kulutus, väestönkasvu.

Lineaarialgebran lukuisat ongelmat[muokkaa | muokkaa wikitekstiä]

Differentiaaliyhtälöt[muokkaa | muokkaa wikitekstiä]

LU-hajotelma[muokkaa | muokkaa wikitekstiä]

Mahdollisia ongelmia[muokkaa | muokkaa wikitekstiä]

Virheherkkyys[muokkaa | muokkaa wikitekstiä]

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[muokkaa | muokkaa wikitekstiä]

Jakajiksi voi tulla hyvin suuria/pieniä lukuja, mikä voi muuttaa kertoimien suuruusluokkaa paljonkin.

Yli- ja alivuodot[muokkaa | muokkaa wikitekstiä]

Mahdolliset liian suuret/pienet luvut tietokoneen käsiteltäväksi. Ongelma yleensä vältettävissä oikealla skaalauksella.