Gaussin algoritmi

Wikipedia

Gaussin algoritmi on matematiikassa lineaarialgebran algoritmi, jolla voidaan määrittää lineaaristen yhtälöryhmien ratkaisuja ja matriisien asteita sekä laskea säännöllisten neliömatriisien käänteismatriiseja. Algoritmin tuloksena matriisi saadaan porrasmuotoon. Siitä käytetään myös nimityksiä Gaussin eliminoimismenetelmä tai Gaussin-Jordanin eliminoimismenetelmä. Menetelmä on nimetty Carl Friedrich Gaussin ja Wilhelm Jordanin mukaan. Gaussin eliminointimenetelmää pidetään ensimmäisenä osana Gaussin-Jordanin eliminoimismenetelmää.

Sisällysluettelo

[muokkaa] Historiaa

Metodi on nimetty matemaatikko Carl Friedrich Gaussin mukaan, mutta saman metodin tunsi jo Liu Hui. Algoritmi mainitaan jo tärkeässä kiinankielisessä kirjassa Jiuzhang suanshu, Yhdeksän lukua matemaattisesta taiteesta, vuonna 263.

[muokkaa] Algoritmi

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

[muokkaa] Porras- ja redusoitu porrasmuoto

Gaussin algoritmilla voidaan matriisi asettaa aina porras- tai redusoituun porrasmuotoon alkeisrivitoimitusten avulla. Alkeisrivitoimituksella tarkoitetaan sitä, että

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

Sanotaan, että rivin johtava alkio on rivin vasemmanpuoleisin nollasta eroava alkio.

Nyt matriisin sanotaan olevan porrasmuodossa, mikäli

  • 1) matriisin kunkin rivin johtava alkio on ylemmän rivin johtavan alkion oikealla puolella, lukuun ottamatta ensimmäistä riviä
  • 2) samalla sarakkeella, mutta johtavan alkion alapuolella olevat alkiot ovat nollia
  • 3) matriisin nollarivit ovat alimpana

Matriisi on redusoidussa porrasmuodossa, mikäli se on porrasmuodossa ja lisäksi

  • 4) jokainen johtava alkio on 1
  • 5) samalla sarakkeella, mutta johtavan alkion yläpuolella olevat alkiot ovat nollia

Annetun matriisin redusoitu porrasmuoto on aina yksikäsitteinen, mutta matriisilla voi olla useita porrasmuotoja.

[muokkaa] Muita sovelluksia

[muokkaa] Käänteismatriisin etsiminen

Olkoon A n×n neliömatriisi, jonka käänteismatriisi pitää määrittää. Täydennetään matriisi n×2n matriisiksi, missä matriisin vasemmanpuoleinen n×n matriisi on alkuperäinen matriisi A ja jälkimmäinen n×n matriisi yksikkömatriisi. Kun Gaussin algoritmin suoritetaan loppuun, yksikkömatriisi on täydennetyn matriisin vasemmanpuoleisena osana ja oikealla puolella A:n käänteismatriisi.

Algoritmi jää aina "jumiin" kun A ei ole säännöllinen.

[muokkaa] Matriisin kantojen ja asteen etsiminen

Kun Gaussin algoritmi suoritetaan, algoritmista voidaan lukea rivi-, sarake- ja nolla-avaruuden kannat. Tällöin saadaan selville matriisin aste.


Tämä matematiikkaan liittyvä artikkeli on tynkä.
Voit auttaa Wikipediaa laajentamalla artikkelia.