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.