Gaussin algoritmi

Matematiikassa Gaussin eliminointi (jota kutsutaan myös rivien vähentämiseksi) on menetelmä, jota käytetään lineaaristen yhtälöiden ratkaisemiseen. Se on nimetty Carl Friedrich Gaussin mukaan, joka on kuuluisa saksalainen matemaatikko, joka kirjoitti tästä menetelmästä mutta ei keksinyt sitä.

Gaussin eliminoinnin suorittamiseksi lineaarisen yhtälösysteemin ehtojen kertoimia käytetään luomaan matriisityyppi, jota kutsutaan lisätyksi matriisiksi. Tämän jälkeen käytetään alkeisrivioperaatioita matriisin yksinkertaistamiseksi. Käytettävät kolmenlaiset rivioperaatiot ovat seuraavat:

Tyyppi 1: Yhden rivin vaihtaminen toiseen riviin.

Tyyppi 2: Rivin kertominen luvulla, joka ei ole nolla.

Tyyppi 3: Rivin lisääminen tai vähentäminen toisesta rivistä.

Gaussin eliminoinnin tavoitteena on saada matriisi rivi-echelon-muotoon. Jos matriisi on rivi-echelon-muodossa, se tarkoittaa, että vasemmalta oikealle luettaessa jokainen rivi alkaa vähintään yhdellä nollatermillä enemmän kuin sen yläpuolella oleva rivi. Joissakin Gaussin eliminoinnin määritelmissä sanotaan, että matriisin tuloksen on oltava pelkistetyssä rivi-echelon-muodossa. Tämä tarkoittaa, että matriisi on rivi-echelon-muodossa ja että ainoa nollasta poikkeava termi kullakin rivillä on 1. Gaussin eliminointia, joka tuottaa pelkistetyn rivi-echelon-muotoisen matriisituloksen, kutsutaan joskus Gauss-Jordanin eliminoinniksi.

Esimerkki

Oletetaan, että tavoitteena on löytää vastaukset tähän lineaariseen yhtälösysteemiin.

2 x + y - z = 8 ( R 1 ) - 3 x - y + 2 z = - 11 ( R 2 ) - 2 x + y + 2 z = - 3 ( R 3 ) {\displaystyle {\begin{alignedat}{7}2x&&\\;+\;&&y&&&\;-\;&&z&&\;=\;&&8&\qquad (R_{1})\\-3x&&\;-\;&&y&&\;+\;&&2z&&\;=\;&&-11&\qquad (R_{2})\\-2x&&\;+\;&&y&&\;+\;&&2z&&\;=\;&&-3&\qquad (R_{3})\end{alignedat}}} ${\begin{alignedat}{7}2x&&\;+\;&&y&&\;-\;&&z&&\;=\;&&8&\qquad (R_{1})\\-3x&&\;-\;&&y&&\;+\;&&2z&&\;=\;&&-11&\qquad (R_{2})\\-2x&&\;+\;&&y&&\;+\;&&2z&&\;=\;&&-3&\qquad (R_{3})\end{alignedat}}$

Ensin järjestelmä on muutettava lisätyksi matriisiksi. Täydennetyssä matriisissa jokainen lineaarinen yhtälö muuttuu riviksi. Lisätyn matriisin toisella puolella lineaarisen yhtälön jokaisen termin kertoimet muuttuvat matriisin numeroiksi. Lisätyn matriisin toisella puolella ovat vakiotermit, joiden kanssa kukin lineaarinen yhtälö on yhtä suuri. Tämän järjestelmän osalta täydennetty matriisi on:

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

Tämän jälkeen lisätylle matriisille voidaan tehdä rivioperaatioita sen yksinkertaistamiseksi. Seuraavassa taulukossa esitetään yhtälösysteemin ja lisätyn matriisin rivien vähentämisprosessi.

Yhtälösysteemi	Rivitoiminnot	Täydennetty matriisi
2 x + y - z = 8 - 3 x - y + 2 z = - 11 - 2 x + y + 2 z = - 3 {\displaystyle {\begin{alignedat}{7}2x&&\;+\;&&y&&\;-\;&&z&&\;=\;&&8&\\-3x&&\;-\;&&y&&\;+\;&&2z&& \;=\;&&-11&\\-2x&&\;+\;&&y&&\;+\;&&2z&&\;=\;&&-3&\end{alignedat}}} ${\begin{alignedat}{7}2x&&\;+\;&&y&&\;-\;&&z&&\;=\;&&8&\\-3x&&\;-\;&&y&&\;+\;&&2z&&\;=\;&&-11&\\-2x&&\;+\;&&y&&\;+\;&&2z&&\;=\;&&-3&\end{alignedat}}$		[ 2 1 - 1 8 - 3 - 1 2 - 11 - 2 1 2 - 3 ] {\displaystyle \left[{\begin{array}{ccc\|c}2&1&-1&8\\\\-3&-1&2&-11\\\-2&1&2&-3\end{array}}\right]} $\left[{\begin{array}{ccc\|c}2&1&-1&8\\-3&-1&2&-11\\-2&1&2&-3\end{array}}\right]$
2 x + y - z = 8 1 2 y + 1 2 z = 1 2 y + z = 5 {\displaystyle {\begin{{alignedat}{7}2x&&\;+&&&y&&\;-&&&\;z&&\;=\;&&8&\\\\\&&&&{\frac {1}{2}}y&&\;+&&\;{\frac {1}{2}}z&&\;=\;&&1&\\&&&&2y&&\;+&&\;z&&\;=\;&&5&\end{alignedat}}} ${\begin{alignedat}{7}2x&&\;+&&y&&\;-&&\;z&&\;=\;&&8&\\&&&&{\frac {1}{2}}y&&\;+&&\;{\frac {1}{2}}z&&\;=\;&&1&\\&&&&2y&&\;+&&\;z&&\;=\;&&5&\end{alignedat}}$	R 2 + 3 2 R 1 → R 2 {\displaystyle R_{2}+{\frac {3}{2}}R_{1}\rightarrow R_{2}}} $R_{2}+{\frac {3}{2}}R_{1}\rightarrow R_{2}$ R 3 + R 1 → R 3 {\displaystyle R_{3}+R_{1}\rightarrow R_{3}} $R_{3}+R_{1}\rightarrow R_{3}$	[ 2 1 - 1 8 0 1 / 2 1 / 2 1 0 2 1 5 ] {\displaystyle \left[{\begin{array}{ccc\|c}{ccc\|c}2&1&-1&8\\\\0&1/2&1/2&1/2&1\\\0&2&1&5\end{array}}\right]} $\left[{\begin{array}{ccc\|c}2&1&-1&8\\0&1/2&1/2&1\\0&2&1&5\end{array}}\right]$
2 x + y - z = 8 1 2 y + 1 2 z = 1 - z = 1 {\displaystyle {\begin{alignedat}{7}2x&&\;+&&&&y\;&&&-&&&\;z\;&&=\;&&8&\\\\&&&&{\frac {1}{2}}y\;&&+&&\;{\frac {1}{2}}z\;&&=\;&&1&\\&&&&&&&&\;-z\;& &\;=\;&&1&\end{alignedat}}} ${\begin{alignedat}{7}2x&&\;+&&y\;&&-&&\;z\;&&=\;&&8&\\&&&&{\frac {1}{2}}y\;&&+&&\;{\frac {1}{2}}z\;&&=\;&&1&\\&&&&&&&&\;-z\;&&\;=\;&&1&\end{alignedat}}$	R 3 + - 4 R 2 → R 3 {\displaystyle R_{3}+-4R_{2}\rightarrow R_{3}} $R_{3}+-4R_{2}\rightarrow R_{3}$	[ 2 1 - 1 8 0 1 / 2 1 / 2 1 0 0 - 1 1 ] {\displaystyle \left[{\begin{array}{ccc\|c}2&1&-1&8\\\0&1/2&1/2&1/2&1\\0&0&-1&1\end{array}}\right]} $\left[{\begin{array}{ccc\|c}2&1&-1&8\\0&1/2&1/2&1\\0&0&-1&1\end{array}}\right]$

Matriisi on nyt rivi-echelon-muodossa. Tätä kutsutaan myös kolmiomuodoksi.

Yhtälösysteemi	Rivitoiminnot	Täydennetty matriisi
2 x + y = 7 1 2 y = 3 / 2 - z = 1 {\displaystyle {\begin{alignedat}{7}2x&&\;+&&&y\;&&&&\;\;&&=\;&&7&\\\&&&&&&&{\frac {1}{2}}y\;&&&&\;\;&&=\;&&3/2&\\&&&&&&&&\;-z\;&&\;=\;&&1&\end{alignedat}}} ${\begin{alignedat}{7}2x&&\;+&&y\;&&&&\;\;&&=\;&&7&\\&&&&{\frac {1}{2}}y\;&&&&\;\;&&=\;&&3/2&\\&&&&&&&&\;-z\;&&\;=\;&&1&\end{alignedat}}$	R 2 + 1 2 R 3 → R 2 {\displaystyle R_{2}+{\frac {1}{2}}R_{3}\rightarrow R_{2}}} $R_{2}+{\frac {1}{2}}R_{3}\rightarrow R_{2}$ R 1 - R 3 → R 1 {\displaystyle R_{1}-R_{3}\rightarrow R_{1}} $R_{1}-R_{3}\rightarrow R_{1}$	[ 2 1 0 7 0 1 / 2 0 3 / 2 0 0 - 1 1 ] {\displaystyle \left[{\begin{array}{ccc\|c}{ccc\|c}2&1&0&7\\\0&1/2&0&3/2\\\0&0&-1&1\end{array}}\right]} $\left[{\begin{array}{ccc\|c}2&1&0&7\\0&1/2&0&3/2\\0&0&-1&1\end{array}}\right]$
2 x + y = 7 y = 3 z = - 1 {\displaystyle {\begin{alignedat}{7}2x&&\;+&&&y\;&&&&\;\;&&=\;&&7&&\\\&&&&&&y\;&&&&\;\;&&=\;&&3&\\&&&&&&&&\;z\;&&\;=\;&&-1&\end{alignedat}}} ${\begin{alignedat}{7}2x&&\;+&&y\;&&&&\;\;&&=\;&&7&\\&&&&y\;&&&&\;\;&&=\;&&3&\\&&&&&&&&\;z\;&&\;=\;&&-1&\end{alignedat}}$	2 R 2 → R 2 {\displaystyle 2R_{2}\rightarrow R_{2}} $2R_{2}\rightarrow R_{2}$ R 3 → R 3 {\displaystyle -R_{3}\rightarrow R_{3}} $-R_{3}\rightarrow R_{3}$	[ 2 1 0 7 0 1 0 3 0 0 0 1 - 1 ] {\displaystyle \left[{\begin{array}{ccc\|c}2&1&0&7\\\0&1&0&3\\0&0&1&-1\end{array}}\right]} $\left[{\begin{array}{ccc\|c}2&1&0&7\\0&1&0&3\\0&0&1&-1\end{array}}\right]$
x = 2 y = 3 z = - 1 {\displaystyle {\begin{alignedat}{7}x&&\;&&\;&&&&\;\;&&=\;&&2&\\\&&&& y\;&&&&\;\;&&=\;&&3&\\&&&&&&&&\;z\;&&\;=\;&&-1&\end{alignedat}}} ${\begin{alignedat}{7}x&&\;&&\;&&&&\;\;&&=\;&&2&\\&&&&y\;&&&&\;\;&&=\;&&3&\\&&&&&&&&\;z\;&&\;=\;&&-1&\end{alignedat}}$	R 1 - R 2 → R 1 {\displaystyle R_1}-R_{2}\rightarrow R_{1}} $R_{1}-R_{2}\rightarrow R_{1}$ 1 2 R 1 → R 1 {\displaystyle {\frac {1}{2}}R_{1}\rightarrow R_{1}} ${\frac {1}{2}}R_{1}\rightarrow R_{1}$	[ 1 0 0 2 0 0 1 0 3 0 0 0 1 - 1 ] {\displaystyle \left[{\begin{array}{ccc\|c}1&0&0&2\\\0&1&0&3\\0&0&1&-1\end{array}}\right]} $\left[{\begin{array}{ccc\|c}1&0&0&2\\0&1&0&3\\0&0&1&-1\end{array}}\right]$

Matriisi on nyt pelkistetyssä rivi-echelon-muodossa. Tämän matriisin lukeminen kertoo, että yhtälöryhmän ratkaisut löytyvät, kun x = 2, y = 3 ja z = -1.

Kysymyksiä ja vastauksia

K: Mikä on Gaussin eliminointi?

V: Gaussin eliminointi on matematiikassa käytetty menetelmä lineaaristen yhtälöryhmien järjestelmien ratkaisemiseen.

K: Kenen mukaan se on nimetty?

V: Se on nimetty Carl Friedrich Gaussin mukaan, kuuluisan saksalaisen matemaatikon, joka kirjoitti tästä menetelmästä, mutta ei keksinyt sitä.

K: Miten Gaussin eliminointi suoritetaan?

V: Gaussin eliminointi suoritetaan käyttämällä lineaarisen yhtälösysteemin termien kertoimia täydennetyn matriisin luomiseksi. Tämän jälkeen käytetään alkeisrivioperaatioita matriisin yksinkertaistamiseksi.

K: Mitä kolmea rivioperaatiotyyppiä käytetään Gaussin eliminoinnissa?

V: Gaussin eliminoinnissa käytettävät kolmenlaiset rivioperaatiot ovat: Rivin kertominen luvulla, joka ei ole nolla, ja rivin lisääminen tai vähentäminen toisesta rivistä.

K: Mikä on Gaussin eliminoinnin tavoite?

V: Gaussin eliminoinnin tavoitteena on saada matriisi rivi-echelon-muotoon.

K: Mikä on rivi-echelon-muoto?

V: Jos matriisi on rivi-echelon-muodossa, se tarkoittaa, että vasemmalta oikealle luettaessa jokainen rivi alkaa vähintään yhdellä nollatermillä enemmän kuin sen yläpuolella oleva rivi.

K: Mikä on pelkistetty rivi-echelon-muoto?

V: Pelkistetty rivi-echelon-muoto tarkoittaa, että matriisi on rivi-echelon-muodossa ja että ainoa nollasta poikkeava termi kullakin rivillä on 1. Gaussin eliminointia, joka tuottaa pelkistetyn rivi-echelon-matriisin tuloksen, kutsutaan joskus Gauss-Jordanin eliminoinniksi.