Az $Ax=b$ lineáris egyenletrendszer megoldására gyakran használt univerzális módszer a Gauss elimináció. Az egyenletrendszer mátrixai az alábbiak:

$A=\left[\begin{array}{cccc}{a}_{11}& a_{12}& \cdots & a_{1n}\\ a_{21}& a_{22}& \cdots & a_{2n}\\ ⋮& ⋮& \ddots & ⋮\\ a_{n1}& a_{n2}& \cdots & a_{nn}\end{array}\right]$ , $x=\left[\begin{array}{c}{x}_1\\ x_2\\ ⋮\\ x_n\end{array}\right]$ , $b=\left[\begin{array}{c}{b}_1\\ b_2\\ ⋮\\ b_n\end{array}\right]$ (F.33)

ahol $A$ az együttható mátrix, $b$ egy adott ismert értékekből álló vektor, az $x$ vektor pedig az ismeretleneket tartalmazó vektor. Egyszerűbb esetben az $A$ mátrix $n\times n$ -es, de az algoritmus $n\times m$ -es esetre is alkalmazható.

A megoldás bemutatása során a változók felírását gyakran elhagyjuk és az egyenletrendszert az alábbi kibővített mátrix segítségével írjuk fel:

$\text{[}Ab\text{]}=\left[\begin{array}{ccccc}{a}_{11}& a_{12}& \cdots & a_{1n}& b_1\\ a_{21}& a_{22}& \cdots & a_{2n}& b{}_2\\ ⋮& ⋮& \ddots & ⋮& ⋮\\ a_{n1}& a_{n2}& \cdots & a_{nn}& b_n\end{array}\right]$ . (F.34)

Látható, hogy a kibővített mátrix az együttható mátrix kiegészítve a $b$ vektorral. A kiegészített $\text{[}Ab\text{]}$ mátrix és az eredeti $A$ mátrix rangjára vonatkozóan:

- ha $\text{rang(}A\text{)}=\text{rang([}Ab\text{])}=n$ , akkor egy egyértelmű megoldás van.

- ha $\text{rang(}A\text{)}=\text{rang([}Ab\text{])}<n$ , akkor az egyenletnek végtelen sok megoldása van. Ilyen esetben lehet csökkenteni az ismeretlenek számát, majd valamilyen optimális megoldást (pl. a négyzetes hibaminimalizáló megoldás) keresni.

- ha $\text{rang(}A\text{)}<\text{rang([}Ab\text{])}$ akkor nincs megoldás.

A mátrixon az egyenletrendszer eredményének változása nélkül az alábbi elemi sor-műveletek végezhetők:

A fentiek mellett az alábbi, oszlopok cseréjével járó művelet is elvégezhető:

az egyenletrendszerben a változók sorrendjét felcseréljük (ez oszlopok cseréjét jelenti, kibővítettmátrix esetén az utolsó oszlop kivételével).

Az alap eljáráshoz elegendő az első három elemi sor-művelet, de bizonyos esetekben (például a pontosság növeléséhez) az utolsó műveletet is alkalmazzuk. Erről a későbbiekben lesz szó (ld. pivotolás).

A fenti műveletek segítségével a mátrixot, illetve az egyenletrendszert egy olyan egyszerűbb alakra (pl. háromszög-, diagonál mátrix) hozhatjuk, amely esetén egyszerű a megoldás számítása.

$\left[\begin{array}{ccccc}{a}_{11}& a_{12}& \cdots & a_{1n}& b_1\\ 0& {a^{\prime }}_{22}& \cdots & {a^{\prime }}_{2n}& {b^{\prime }}_2\\ ⋮& ⋮& \ddots & ⋮& ⋮\\ 0& 0& \cdots & {a^{\prime }}_{nn}& {b^{\prime }}_n\end{array}\right]$ (F.35)

az eredeti egyenletrendszert egy $Rx=d$ felső háromszögmátrixot ( $R$ ) tartalmazó egyenletrendszerré alakítjuk, ami már egyszerű behelyettesítéssel megoldható. Az algoritmus egy köztes lépésében a

$\left[\begin{array}{ccccc}{a}_{11}& a_{12}& \cdots & a_{1n}& b_1\\ 0& {a^{\prime }}_{22}& \cdots & {a^{\prime }}_{2n}& {b^{\prime }}_2\\ 0& {a^{\prime }}_{32}& \cdots & {a^{\prime }}_{3n}& {b^{\prime }}_3\\ ⋮& ⋮& \ddots & ⋮& ⋮\\ 0& {a^{\prime }}_{n2}& \cdots & {a^{\prime }}_{nn}& {b^{\prime }}_n\end{array}\right]$ , (F.36)

az ${a^{\prime }}_{32}$ kinullázásához a második sort elosztjuk az ${a^{\prime }}_{22}$ generáló „pivot” elemmel majd ennek ${a^{\prime }}_{32}$ szorosát kivonjuk a harmadik sorból. Amennyiben a pivot elem helyén 0 áll, sorcserét kell alkalmazni (ha nincs nem 0 sor, akkor az adott oszlop megfelel az elvárásoknak).

A “pivot” vagy generáló elem, amint azt láthattuk fontos szerephez jut az algoritmus során. A számítási pontosság növelésére szolgál a pivotolás, amikor ezt a pivot elemet tudatosan választjuk ki, ahol a cél egy nagy értékű elem használata. Ez az elem sor illetve oszlop cserével mozgatható a megfelelő pozícióba. A részleges pivotolás (partial pivoting) esetén az adott oszlop abszolút értékben legnagyobb elemét használjuk, míg a teljes pivotolás (complete pivoting) esetén a mátrix oszlopait és sorait is cserélve mozgatjuk az abszolútértékben legnagyobb elemet a megfelelő pozícióba. Ebben az esetben (oszlopok cseréjénél) az ismeretlenek sorrendje is változik. A leggyakrabban elegendő az egyszerűbb részleges pivotolás alkalmazása.

A fentiekhez hasonlóan egy másik algoritmus, a Gauss-Jordan elimináció célja az alábbi diagonális mátrix alak:

$\left[\begin{array}{ccccc}{a}_{11}& 0& \cdots & 0& b_1\\ 0& {a^{\prime }}_{22}& \cdots & 0& {b^{\prime }}_2\\ ⋮& ⋮& \ddots & ⋮& ⋮\\ 0& 0& \cdots & {a^{\prime }}_{nn}& {b^{\prime }}_n\end{array}\right]$ (F.37)

amit a Gauss eliminációnál alkalmazott műveletekkel érhetünk el. Ebben az esetben nincs szükség visszahelyettesítésekre, az eredmény azonnal számítható.