Gauss-elimination

Gauss-elimination er en algoritme til at løse et lineært ligningssystem. Samles koefficientene til de ukendte i en matrix, kan denne omformes sådan at den bliver triangulær og har trappeform. Efter denne omskrivning kan de ukendte i ligningerne løses direkte. I Europa blev metoden systematisk benyttet af den tyske matematiker Carl Friedrich Gauss, men var kendt blandt kinesiske matematikere fra år 150 AD. Gauss videreudviklede senere metoden sammen med geologen Wilhelm Jordan, sådan at matricen kunne omskrives på en reduceret trappeform. For mange problemer er dette en fordel. Dette gælder specielt ved meget store ligningssystemer, hvor numeriske metoder benyttes. Metoden kaldes da for Gauss-Jordan-reduktion.

Den samme algoritme kan også benyttes til at beregne nulrummet og rangen for en matrix. Er matricen kvadratisk og regulær, kan Gauss-elimination også benyttes til at finde den tilhørende inverse matrix.

Gauss-algoritme

Metoden kan enklest forklares ved at betragte et konkret eksempel med et lineært ligningssystem med tre variable x₁, x₂ og x₃. Generelt kan det skrives som:

${\begin{array}{rcrcrcl}a_{11}x_{1}&+&a_{12}x_{2}&+&a_{13}x_{3}&=&b_{1},\\a_{21}x_{1}&+&a_{22}x_{2}&+&a_{23}x_{3}&=&b_{2},\\a_{31}x_{1}&+&a_{32}x_{2}&+&a_{33}x_{3}&=&b_{3}.\end{array}}$

Er alle leddene på højre side af ligningerne lig nul, er ligningssystemet homogent. 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ølgende elementære operationer:

1: Man kan bytte rundt på to ligninger.

2: Man kan multiplicere alle led i en ligning med et tal forskelligt fra nul.

3: Man kan addere et multiplum af en ligning til en anden.

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:

• 1) I første ligning antages at koefficienten a₁₁  ikke er lig nul. Skulle den være det, bytter man om på ligningerne.
• 2) Multipliceres den første ligning med et passende tal og trækkes det fra de nedenstående ligningerne, kan den ukendte x₁  elimineres i disse.
• 3) På samme måde kan de andre ligninger anvendes til at eliminere x₂  i ligningerne under. Og så videre med de resterende ukendte i de efterfølgende ligninger.

De tre givne ligninger vil på denne måde dermed blive omformet til et ækvivalent ligningssystem på formen:

${\begin{array}{rcrcrcl}{\tilde {a}}_{11}x_{1}&+&{\tilde {a}}_{12}x_{2}&+&{\tilde {a}}_{13}x_{3}&=&{\tilde {b}}_{1}\\&&{\tilde {a}}_{22}x_{2}&+&{\tilde {a}}_{23}x_{3}&=&{\tilde {b}}_{2}\\&&&&{\tilde {a}}_{33}x_{3}&=&{\tilde {b}}_{3}.\end{array}}$

Det oprindelige ligningssystem er dermed bragt over på triangulær form. Fra den sidste ligning kan x₃  nu findes direkte. Settes dette ind i den anden ligning, giver den igen x₂. Med disse to værdier findes så x₁  fra den første ligningen, og alle de ukendte er blevet bestemt. Ligningssystemet er løst.

Matrixform

Mere generelle ligningssystemer kan skrives på kompakt form ved anvendelse af matricer. Med n  ukendte i m  ligninger, samler man de ukendte sammen i en kolonnevektor x = (x₁, x₂, ..., x_n)^T  og ligeså de inhomogene led i kolonnevektoren b = (b₁, b₂, ..., b_m)^T  sådan at ligningssystemet kan skrives som Ax = b. Her er nu A  en m × n matrix med elementer bestående af koefficientene a_ij  til ligningssystemet. Tager man med de inhomogene led, kan alle koefficienter i ligningssystemet samles i den udvidede koefficientmatrix eller udvidede matrix.

$(A|\mathbf {b} )=\left[{\begin{array}{cccc|c}a_{11}&a_{12}&\cdots &a_{1n}&b_{1}\\a_{21}&a_{22}&\cdots &a_{2n}&b_{2}\\\vdots &\vdots &\vdots &\vdots &\vdots \\a_{m1}&a_{m2}&\cdots &a_{mn}&b_{m}\\\end{array}}\right]$

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.

Eksempel

Som en enkel illustration af algoritmen, kan man betragte et ligningssystem med tre ligninger og 3 ukendte:

${\begin{array}{cccccc}x_{1}&+&2x_{2}&+&x_{3}&=8\\x_{1}&+&x_{2}&+&x_{3}&=6\\4x_{1}&-&x_{2}&+&2x_{3}&=8\\\end{array}}$

I den udvidede matrix kan x₁  elimineres fra andre rækker ved ganske enkelt at tage differensen mellem denne og den første. Ligeledes kan x₁  elimineres fra den næste række ved at trække 4 gange den første række fra den tredje. Det giver:

$(A|\mathbf {b} )=\left[{\begin{array}{ccc|c}1&2&1&8\\1&1&1&6\\4&-1&2&8\\\end{array}}\right]\longrightarrow \left[{\begin{array}{ccc|c}1&2&1&8\\0&-1&0&-2\\0&-9&-2&-24\\\end{array}}\right]$

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 kan x₂  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:

$\left[{\begin{array}{ccc|c}1&2&1&8\\0&1&0&2\\0&9&2&24\\\end{array}}\right]\longrightarrow \left[{\begin{array}{ccc|c}1&2&1&8\\0&1&0&2\\0&0&2&6\\\end{array}}\right]$

Nederste række svarer nu til 2x₃ = 6 eller x₃ = 3. I anden række optræder x₃  ikke sådan at man også fra denne række direkte kan udlæse at x₂ = 2. Sættes disse to resultater ind i første ligning, giver den til slut at x₁ = 1. Så løsningen til det fulde ligningssystem er givet ved punktet x₀ = (1,2,3)^T i vektorrummet R³. I dette enkle tilfælde kunne løsningen blive fundet direkte fra den inverse til matrix A ved at benytte at x = 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 er inkonsistent. 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 da ubestemte løsninger, som svarer til et uendelig stort løsningsrum. I dette tilfælde er de tre ligninger ikke længere uafhængige af hinanden.

Litteratur og refererede værker

• Calinger, Ronald (1999), A Contextual History of Mathematics, Prentice Hall, ISBN 978-0-02-318285-3.
• K. Hoffman and R. Kunze, Linear Algebra, Prentice - Hall, Inc., New Jersey (1971). ISBN 0-13-536821-9.
• G. Fisher, Lineare Algebra, Springer Spektrum, Wiesbaden (2008). ISBN 978-3-658-03944-8.

Eksterne henvisninger

• A. Beezer, Systems of Linear Equations, web-versjon av lærebok i lineær algebra.
• uni-stuttgart.de: An educational tool for experimenting with matrices and the Gauss method