Gauss-elimination er enalgoritme til at løse etlineært ligningssystem. Samles koefficientene til de ukendte i enmatrix, kan denne omformes sådan at den blivertriangulær og hartrappeform. Efter denne omskrivning kan de ukendte i ligningerne løses direkte. I Europa blev metoden systematisk benyttet af den tyske matematikerCarl Friedrich Gauss, men var kendt blandt kinesiske matematikere fra år 150 AD.[1][2] Gauss videreudviklede senere metoden sammen med geologenWilhelm Jordan, sådan at matricen kunne omskrives på enreduceret trappeform. For mange problemer er dette en fordel. Dette gælder specielt ved meget store ligningssystemer, hvor numeriske metoder benyttes. Metoden kaldes da forGauss-Jordan-reduktion.[3]
Den samme algoritme kan også benyttes til at beregnenulrummet ograngen for en matrix. Er matricenkvadratisk ogregulær, kan Gauss-elimination også benyttes til at finde den tilhørendeinverse matrix.
Metoden kan enklest forklares ved at betragte et konkret eksempel med etlineært ligningssystem med tre variablex1,x2 ogx3.Generelt kan det skrives som:
Er alle leddene på højre side af ligningerne lig nul, er ligningssystemethomogent. I det følgende vil det være et vigtigt specialtilfælde. Rækkefølgen af ligningerne spiller ingen rolle. Hver ligning kan multipliceres med et tal uden, at de mister noget af indholdet. Der sker heller ikke, hvis man adderer og eller trækker to ligninger fra hinanden. På den måde opstår følgendeelementære operationer:
Med disse operationer kan man nu skrive ligningssystemets form om, sådan at de ukendte kan løses direkte. Dette kan gøres på forskellige måder i detaljer, men det svarer til at:
De tre givne ligninger vil på denne måde dermed blive omformet til et ækvivalent ligningssystem på formen:
Det oprindelige ligningssystem er dermed bragt over påtriangulær form. Fra den sidste ligning kanx3 nu findes direkte. Settes dette ind i den anden ligning, giver den igenx2. Med disse to værdier findes såx1 fra den første ligningen, og alle de ukendte er blevet bestemt. Ligningssystemet er løst.
Mere generelle ligningssystemer kan skrives på kompakt form ved anvendelse afmatricer. Medn ukendte im ligninger, samler man de ukendte sammen i enkolonnevektorx = (x1,x2, ...,xn)T og ligeså de inhomogene led i kolonnevektorenb = (b1,b2, ...,bm)T sådan at ligningssystemet kan skrives somAx =b. Her er nuA enm × n matrix med elementer bestående af koefficienteneaij til ligningssystemet. Tager man med de inhomogene led, kan alle koefficienter i ligningssystemet samles i denudvidede koefficientmatrix ellerudvidede matrix.
som indeholder informationen fra hele ligningssystemet. De tilladte elementær operationer på de enkelte ligninger, svarer nu til operationer på rækker i denne udvidede matrix.
Som en enkel illustration af algoritmen, kan man betragte et ligningssystem med tre ligninger og 3 ukendte:
I den udvidede matrix kanx1 elimineres fra andre rækker ved ganske enkelt at tage differensen mellem denne og den første. Ligeledes kanx1 elimineres fra den næste række ved at trække 4 gange den første række fra den tredje. Det giver:
Her kan man nu skifte fortegn på alle leddene i anden og tredje række. Det svarer til at multiplicere hver af dem med -1. Til slut kanx2 elimineres fra sidste række ved at multiplicere anden række med 9 og trække resultatet fra tredje række. På den måde kommer man frem til:
Nederste række svarer nu til 2x3 = 6 ellerx3 = 3. I anden række optræderx3 ikke sådan at man også fra denne række direkte kan udlæse atx2 = 2. Sættes disse to resultater ind i første ligning, giver den til slut atx1 = 1. Så løsningen til det fulde ligningssystem er givet ved punktetx0 = (1,2,3)T i vektorrummetR3. I dette enkle tilfælde kunne løsningen blive fundet direkte fra den inverse til matrixA ved at benytte atx =A-1b . For større ligningssystemer er det mere beregningskrævende end brug af Gauss-elimination.
Geometrisk kan man forstå denne løsningen ved at benytte at hver ligning beskriver et plan i et tredimensionelt rum. To af dem vil da have løsninger, som ligger på skæringslinjen mellem de tilsvarende planer. Det tredje plan vil så skære over denne linjen i et punkt som giver den entydige løsning. Hvis to af planerne er parallelle, vil der ikke være nogen løsninger og ligningssystemet erinkonsistent. Et andet, specielt tilfælde optræder, hvis den sidste ligning beskriver et plan, som går gennem skæringslinjen til de to første planer. Da vil alle punkterne på denne linje være en løsning. Man har daubestemte løsninger, som svarer til et uendelig stortløsningsrum. I dette tilfælde er de tre ligninger ikke længere uafhængige af hinanden.
