Gausseliminering

Gausseliminering er en metode i lineær algebra til løsning af lineære ligningssystemer og til at finde inverser af matricer og determinanter ved hjælp af rækkeoperationer. Metoden bygger på at ændre den udvidede matrix [A|b] ved hjælp af rækkeoperationer, som ikke ændrer løsningen, og dermed bringe A nærmere en form der er nem at udregne fra.

Forward elimination er det første skridt. I hver kolonne vælges et pivotelement og elementerne under pivoten elimineres ved at trække passende multipler af pivotrækken fra de underliggende rækker. Hvis pivoten er nul, byttes rækker (og i nogle varianter også kolonner) for at få en mere stabil og ikke-nul pivot. Målet er at få A til en øvre trekantsform U, mens højresiden ændrer sig tilsvarende.

Back substitution anvendes efter forward elimination til at beregne løsningen x fra Ux = y. Gauss-Jordan-eliminering er en videreudvikling, hvor elimineringen fortsættes for at få hele matrisen i reduceret rækkeform. Ved at arbejde med [A|I] kan man gennem de samme rækkeoperationer også få inversen til A.

Pivotering spiller en central rolle for numerisk stabilitet. Partial pivoting (bytte af rækker for at bringe den største pivot ind i pivots position) er almindelig, og komplet pivoting indebærer også kolonnebytte i mere krævende tilfælde. Generelt har Gausseliminering kompleksitet omkring O(n^3) operationer og kræver at A er kvadratisk og ikke-singulær for entydige løsninger. Metoden danner grundlag for LU-faktorisering og anvendes i mange praktiske beregninger.