Gausselimináció

Gauss-elimináció, vagy Gaussian elimination, alapvető módszer lineáris egyenletrendszerek megoldására. Adott Ax = b, ahol A n×n mátrix és b n hosszú vektor. A megközelítés a bővített mátrix [A|b] sorműveletekkel történő átalakítása: cél, hogy a mátrixot felső háromszög alakúvá tegyük, majd visszahelyettesítéssel megkapjuk x értékeit.

Eljárásának fő lépései: először előre-elimináció (forward elimination) és pivotálás. Gyakran alkalmaznak részleges pivotálást: sorcserével a j-edik oszlopban a legnagyobb abszolút értékű elem legyen a pivot. Ezt követően a sorokon végrehajtjuk: m = a_i_j / a_j_j; a_i := a_i - m · a_j. Így az alatta lévő elemek nullá válnak, és a mátrix egy felső háromszög alakú formát vesz fel.

Miután a felső háromszöget elértük, visszahelyetteséssel oldunk meg: x_n az utolsó egyenletből, majd x_{n-1}, és így tovább. A módszer kapcsolódik a LU-dekompozícióhoz is: A = LU, amelyben a pivotálás figyelembevételével PLU formában dolgozunk.

Rövid kiértékelés: a Gauss-elimináció lehet Gauss-Jordan változata is, amely [A|I] átalakításával közvetlenül az A^{-1}-et adja, de több számítást igényel. Változatai közé tartozik a teljes pivotálás is, amely oszlopcseréket is alkalmaz. A módszer időbeli bonyolultsága általában O(n^3) művelet, és numerikus stabilitását a pivotálás javítja, különösen rosszul kondicionált problémák esetén.

Alkalmazási területek közé tartozik a lineáris egyenletrendszerek megoldása, determinánsok kiszámítása és mátrixok inverzének meghatározása.