Gauss-eliminasjon

**Gauss-eliminasjon** er en algoritme  til å løse et sett med lineære ligninger. Samles koeffisientene til de ukjente i en matrise, kan denne omformes slik at den blir triangulær og har **trappeform**. Etter denne omskrivningen kan de ukjente i ligningene løses ut direkte. Metoden ble systematisk benyttet av den tyske matematiker Carl Friedrich Gauss, men var kjent blant kinesiske matematikere for snart nitten hundre år siden. Gauss videreutviklet metoden senere sammen med geologen Wilhelm Jordan slik at matrisen kunne omskrives på en **redusert trappeform**. For mange problem er dette en fordel. Dette gjelder spesielt ved svært store ligningssett hvor numeriske metoder må benyttes. Metoden kalles da **Gauss-Jordan-reduksjon**.

Den samme algoritmen kan også benyttes til å beregne nullrommet og  rangen til en matrise. Er matrisen kvadratisk, kan Gauss-eliminasjon også benyttes til å finne den inverse matrisen. 

## Gauss-algoritme

Metoden kan enklest forklares ved å betrakte et konkret eksempel med et lineært ligningssystem med tre variable *x*1,  *x*2 og  *x*3. 
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øyre side av ligningene lik null, er ligningssettet homogent. I det følgende vil det være et viktig spesialtilfelle. Rekkefølgen til ligningene spiller ingen rolle. Hver ligning kan multipliseres med et tall uten at de mister noe av innholdet. Det skjer heller ikke om man adderer og eller trekker to ligninger fra hverandre. På den måten oppstår følgende **elementære operasjoner**:

:  **1**: Man kan bytte om to ligninger.
:  **2**: Man kan multiplisere hver ligning med et tall forskjellig med null.
:  **3**: Man kan addere et multiplum av en ligning til en annen.

Med disse operasjonene kan man nå skrive om formen til ligningssettet slik at de ukjente kan løses direkte ut. Dette kan gjøres på forskjellige måter i detalj, men tilsvarer at:

* 1) I første ligning antar man at koeffisienten *a*11&thinsp; ikke er lik null. Skulle den være det, bytter man bare om på ligningene.
* 2) Multipliseres nå denne første ligningen med et passende tall og trekkes fra de nedenstående ligningene, kan den ukjente *x*1&thinsp; elimineres i disse. 
* 3) På samme måte kan nå andre ligning brukes til å eliminere *x*2&thinsp; i ligningene under. Og så videre med de resterende ukjente i de neste ligningene.

De tre gitte ligningene vil på denne måten dermed bli omformet til et ekvivalent ligningssett 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 opprinnelige ligningsystemet er dermed bragt over på *triangulær form*. Fra den siste ligningen kan nå *x*3&thinsp; finnes direkte. Settes dette inn i den andre ligningen, gir den igjen *x*2. Med disse to verdiene finnes så *x*1&thinsp; fra den første ligningen, og alle de ukjente er blitt bestemt. Ligningssettet er løst.

### Matriseform

Mer generelle ligningsett kan skrives på kompakt form ved bruk av matriser. Med *n&thinsp;* ukjente i *m&thinsp;* ligninger samler man de ukjente sammen i en kolonnevektor  og likedan de inhomogene leddene i kolonnevektoren  slik at ligningssystemet kan skrives som . Her er nå *A&thinsp;* en *m*&thinsp;&times;&thinsp;*n* matrise med elementer bestående av koeffisientene *a<sub>ij</sub>&thinsp;* til ligningssettet. Tar man med de inhomogene leddene, kan alle koeffisientene i ligningssettet samles i den **utvidete matrisen**

: (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 inneholder informasjonen fra hele ligningssettet. De tillatte elementæroperasjonene på de enkelte ligningene tilsvarer nå operasjoner på radene i denne utvidete matrisen.

### Eksempel

Som en enkel illustrasjon av algoritmen kan man betrakte et ligningssett med tre ligninger og 3 ukjente:

: \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 utvidete matrisen kan  *x*1&thinsp;  elimineres fra andre rad ved ganske enkelt å ta differensen mellom denne og den første. Likedan kan *x*1&thinsp;  elimineres fra den neste raden ved å trekke 4 ganger den første raden fra den tredje. Det gir:

: (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 nå skifte fortegn på alle leddene i andre og tredje rad. Det tilsvarer å multiplisere hver av dem med  -1. Til slutt kan *x*2&thinsp; elimineres fra siste rad ved å multiplisere andre rad med 9 og trekke resultatet fra tredje rad. På den måten 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 rad tilsvarer nå 2*x*3 = 6 eller *x*3 = 3. I andre rad opptrer ikke *x*3&thinsp; slik at  man også fra denne raden kan lese direkte ut at . Settes disse to resultatene inn i første ligning, gir den til slutt at . Så løsningen til det fulle ligningssettet er gitt ved punktet  i vektorrommet **R**3. I dette enkle tilfellet kunne løsningen bli funnet direkte fra den inverse til matrisen *A* ved å benytte at . For større ligningssytem er det vanligvis mer beregningskrevende enn bruk av Gauss-eliminasjon.

Geometrisk kan man forstå denne løsningen ved å benytte at hver ligning beskriver et plan i et tredimensjonalt rom. To av dem vil da ha løsninger som ligger på skjæringslinjen mellom de tilsvarende planene. Det tredje planet vil så skjære over denne linjen i et punkt som gir den entydige løsningen. Hvis to av planene er parallelle, vil det ikke være noen løsninger og ligningssystemet er **inkonsistent**. Et annet, spesielt tilfelle opptrer hvis den siste ligningen beskriver et plan som går gjennom skjæringslinjen til de to første planene. Da vil alle punktene på denne linjen være en løsning. Man har da *ubestemte løsninger* som tilsvarer et uendelig stort **løsningsrom**. I dette tilfellet er ikke de tre ligningene lenger uavhengige av hverandre.

## Gauss-Jordan-reduksjon

Denne gjennomføres med de samme, elementære radoperasjonene som tidligere, men slik at hver rad begynner med et 1-tall etter nullene. Raden har da en **ledende ener**. I tillegg benyttes så denne raden til å fremskaffe nuller i samme kolonne i radene over dette 1-tallet.  Denne prosessen foretas igjen ovenfra og nedover i matrisen. Da er matrisen blitt redusert til standard Gauss-Jordan-form.

Utføres denne reduksjonen på matrisen som ble funnet i forrige eksempel, gir den :

:       \left[\begin{array}{ccc|c} 1 & 2  & 1 & 8  \\ 0  & 1  & 0 & 2  \\ 0 & 0  & 2 & 6  \\ \end{array}\right]   
                    \longrightarrow  \left[\begin{array}{ccc|c} 1 & 0 & 1 & 4  \\ 0  & 1  & 0 & 2  \\  0 & 0  & 1 & 3  \\ \end{array}\right] 
                    \longrightarrow  \left[\begin{array}{ccc|c} 1 & 0 & 0 & 1  \\ 0  & 1  & 0 & 2  \\ 0 & 0  & 1 & 3  \\ \end{array}\right]


I første steg har man laget en ledende ener i tredje rad ved å dele denne raden med 2. Samtidig er 2 ganger andre rad trukket fra første rad for å fjerne 2-tallet over den ledende ener i andre rad. På samme vis i siste steg er 1-tallet fjernet i første rad over den ledende ener i tredje rad. I dette enkle eksemplet er nå den reduserte matrisen blitt diagonal i den venstre *A*-delen slik at man kan lese løsningene direkte ut fra *b*-delen i siste kolonne til høyre. Så enkelt er det vanligvis ikke. Men løsningene kan alltid systematisk finnes fra denne reduserte formen ved å starte bestemmelsen av de ukjente i de nederste radene og så nøste ut de andre fra radene over.

### Ubestemte løsninger

I samme eksempel som over kan man modifisere den tredje ligningen slik at den utvidete matrisen for ligningssettet blir

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


Første steg har bragt matrisen på triangulær form og til slutt er den redusert til Gauss-Jordan-form. Siste raden har bare nuller og derfor ikke noen ledende ener. Den ukjente *x*3&thinsp; kan derfor ikke bestemmes og er en **fri variabel**. Kaller man den for *s*, så er altså . Fra andre rad finner man tilsvarende at  , mens første rad gir . Det betyr at heller ikke den ukjente  *x*1&thinsp; er bestemt, men varierer som  . Løsningene er derfor ikke lenger fullstendig entydige, men danner et uendelig stort løsningsrom.

Det geometriske innholdet av disse løsningene kan finnes ved å skrive løsningene på vektorfrom som

: 
                   \mathbf{x} =  \begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix} =  \begin{bmatrix} 4 -s \\ 2\\ s \end{bmatrix} 
                                      = \begin{bmatrix} 4 \\ 2\\ 0 \end{bmatrix} + s \begin{bmatrix} -1 \\ 0 \\ 1 \end{bmatrix} 


eller **x** = **x***p* + *s*&thinsp;**v**. Her er vektoren **v** = (-1, 0, 1)*T*&thinsp; og  angir et punkt i vektorrommet **R**3. Løsningene ligger altså på en rett linje gjennom dette punktet med retning gitt ved vektoren **v**. Dette skyldes at de tre opprinnelige ligningene ikke lenger er lineært uavhengig av hverandre.

## Homogene ligninger

I dette siste eksemplet er vektoren ***v*** en løsning av den homogene ligningen *A*'x** = **0**'', 

: <math>
                   \begin{bmatrix} 1 & 2 & 1 \\ 1 & 1 & 1 \\ 1 & 0 & 1 \\ \end{bmatrix} \begin{bmatrix} -1 \\ 0 \\ 1 \end{bmatrix} =  \begin{bmatrix} 0 \\ 0 \\ 0 \end{bmatrix} 
</math>

En slik løsning tilhører [[lineært ligningssystem|nullrommet]] eller **kjernen** til matrisen ''A&thinsp;'' og bidrar på en sentral måte til bestemmelsen av løsningsrommet for inhomogene ligninger. Derfor er kjennskap til løsningene av det homogene ligningssystemet viktig.

===Rang og nullitet===

I det generelle tilfellet vil det finnes flere slike nulløsninger. Antall slike nulløsninger er lik dimensjonen eller [[lineær transformasjon|nulliteten]] null(''A'')&thinsp; til dette [[vektorrom]]met. Fra eksemplet over ser man at nulløsningen er forbundet med den ene, frie variabel som ble funnet. Og denne oppsto på grunn av at den siste raden den Gauss-Jordan-reduserte matrisen ikke hadde et ledende 1-tall. 

Innsikten fra dette eksemplet kan generaliseres til en mer alminnelig situasjon hvor man har ''m&thinsp;'' ligninger med ''n&thinsp;'' ukjente. Hvis man så etter Gauss-Jordan-reduksjonen ender opp med et visst antall kolonner uten ledende enere, er dette også antall frie variable i problemet som igjen er lik nulliteten til matrisen. Antall gjenværende kolonner, de med ledende enere, kalles [[lineær transformasjon|rangen]] rang(''A'')&thinsp; til matrisen ''A''. Da man i alt har ''n&thinsp;'' kolonner i matrisen, har man derfor det viktige resultatet

: <math> n = \text{null}(A) + \text{rang}(A) </math>

Denne dimensjonsformelen kan bevises generelt og heter **rang-nullitet-setningen**.  Da antall kolonner er lik antall ukjente i problemet, sier den også hvor mange avhengige variable man har i problemet. Det er igjen lik antallet med lineært uavhengige ligninger i det opprinnelige ligningssettet eller antall rader i den Gauss-reduserte matrisen som ikke består av bare nuller. I det første eksemplet over var rang(''A'') = 3 og nullrommet ikke noe annet enn den trivielle nullvektoren **0** med null dimensjon. I det andre eksemplet var rang(''A'') = 2, og dimensjonen til nullrommet var null(''A'') = 1 som tilsvarer linjen i retning av vektoren **v**.

===Eksempel===

For å illustrere denne systematikken, kan man betrakte et homogent ligningssett med fem ukjente beskrevet ved matrisen


: <math> A  =   \begin{bmatrix} -2 & -5 & 8 & 0 & -17 \\ 1 & 3 & -5 & 1 & 5 \\ 3 & 11 & -19 & 7 & 1 \\1 & 7 & -13 & 5 & -3 \end{bmatrix} 
                     \longrightarrow \begin{bmatrix} 1 & 3 & -5 & 1 & 5 \\ 0 & 1 & -2 & 2 & -7 \\ 0 & 0 & 0 & 1 & -5 \\0 & 0 & 0 & 0 & 0 \end{bmatrix} 
</math>

og dens triangulære form etter Gauss-eliminasjon. På den formen har den tre rader med ledende enere. Rangen til matrisen er derfor rang(''A'') = 3.

Nulliteten kan bestemmes etter en Gauss-Jordan-reduksjon. Den gir

: <math> A  =  \begin{bmatrix} 1 & 3 & -5 & 1 & 5 \\ 0 & 1 & -2 & 2 & -7 \\ 0 & 0 & 0 & 1 & -5 \\0 & 0 & 0 & 0 & 0 \end{bmatrix} 
                     \longrightarrow \begin{bmatrix} 1 & 0 & 1 & 0 & 1 \\ 0 & 1 & -2 & 0 & 3 \\ 0 & 0 & 0 & 1 & -5 \\0 & 0 & 0 & 0 & 0 \end{bmatrix} 
</math>

Her er tredje og femte kolonne uten ledende enere. Nulliteten til matrisen er dermed null(''A'') = 2, og de tilsvarende ukjente ''x''<sub>3</sub>&thinsp; og ''x''<sub>5</sub>&thinsp; vil være frie variable. Rang-nullitet-setningen er derfor oppfylt.

Dimensjonen til nullrommet i dette eksemplet er to. Det er derfor utspent ved to lineært uavhengige vektorer. De kan finnes fra det reduserte ligningssettet som nå kan leses diekte ut fra Gauss-Jordan-matrisen. Fra tredje rad fås . Setter man den frie variable , er altså . Andre rad gir . Skriver man den fri variable  , betyr det at  Tilslutt, fra første rad følger at  slik at 

Løsningsrommet inneholder to frie parametre ''s'' og ''t'' som tilsvarer at det er 2-dimensjonalt. Skrives disse løsningene på vektorform som i det tidligere eksemplet, kan de sammenfattes som  . Dette er vektorer i det 5-dimensjonale rommet **R**<sup>5</sup> hvor de to homogene løsningene  og  utspenner et 2-dimensjonalt plan som inneholder alle løsningene.

==Inhomogene ligninger==

Det inhomogene ligningssettet  vil ha løsninger når vektoren **b** er konsistent med ''m''&thinsp;&times;&thinsp;''n'' matrisen ''A'' med rang ''r'' på en måte som kan belyses ved Gauss-eliminasjon. Hvis det er tilfelle, og man finner en eller annen **partikulær løsningen** **x**<sub>0</sub>&thinsp; av ligningssettet, vil da i allminnelighet alle løsningene kunne skrives på formen

: <math> \mathbf{x} = \mathbf{x}_0 + \lambda_1\mathbf{v}_1 + \lambda_2\mathbf{v}_2 + \ldots + \lambda_p\mathbf{v}_p </math>

Her er ''&lambda;<sub>i</sub>&thinsp;''  frie parametre som tilsvarer løsningene **v**<sub>''i''</sub>&thinsp; av den homogene ligningen , mens   er dimensjonen til nullrommet for matrisen ''A''.  Denne formen på den generelle løsningen verifiseres ved å skrive den som . Da blir  da  og den partikulære løsningen oppfyller den inhomogene ligningen 

Det geometriske innholdet av det generelle løsningsrommet kan man tenke seg å være nullrommet utspent av vektorene **v**<sub>''i''</sub>&thinsp;, som flyttes bort fra [[origo]] i [[vektorrom]]met **R**<sup>''n''</sup> med vektoren **x**<sub>0</sub>&thinsp; som representerer den partikulære løsningen. Løsningsmengden er derfor et [[affint rom]] med dimensjon gitt ved nulliteten til matrisen ''A''.

===Kolonnevektorer og konsistens===


For å finne ut om disse løsningene virkelig eksisterer, kan man undersøke [[vektorrom]]met som utspennes av **kolonnevektorene** til ''A''. Er denne en  ''m''&thinsp;&times;&thinsp;''n'' matrise, vil disse være vektorer med ''m'' komponenter,

: <math> \mathbf{A}_i = \begin{bmatrix} A_{1i} \\ A_{2i} \\ \vdots \\ A_{mi} \end{bmatrix}

</math>

Da det  inhomogene ligningssettet kan nå skrives som

: <math> \sum_{i=1}^n x_i\mathbf{A}_i = \mathbf{b}, </math>

må vektoren **b** være en [[lineærkombinasjon]] av disse kolonnevektorene. Matrisen ''A'' inneholder i alt ''n'' slike vektorer som tilhører vektorrommet **R**<sup>''m''</sup>. Hvis antall ukjente ''n&thinsp;'' i ligningssystemet er mindre enn antall ligninger ''m'', vil kolonnevektorene til ''A&thinsp;'' utspenne et vektorrom som maksimalt  har dimensjon ''n''. Da vektoren **b** ligger i **R**<sup>''m''</sup> med dimensjon ''m > n'', vil det i alminnelighet ikke være noen løsninger i dette tilfellet. Ligningssettet er **overbestemt**.

I det motsatte tilfellet  ''m < n'', er det færre ligninger enn ubestemte. Ligningssettet sies å være **underbestemt**. For at det i dette tilfellet skal finnes en løsning av det inhomogene ligningssettet, må de lineært uavhengige kolonnevektorene til ''A'' kunne utspenne et vektorrom med samme dimensjon som **R*'<sup>m</sup>. Det betyr at betingelsen  må være oppfylt. 

På samme måte er betingelsen for å ha en løsning i det spesielle tilfellet *m = n*,  at alle kolonnevektorene til *A* er lineært uavhengige av hverandre. Det betyr at determinanten  slik at matrisen har en inverse . Løsningen til ligningssettet er da  . Gauss-eliminasjon kan også benyttes til å beregne  den inverse matrisen.

==Beregning av den inverse matrise==

Når det lineære  ligningsettet består av like mange ligninger som ukjente, er matrisen *A* kvadratisk og det kan løses ved bruk av [[Cramers regel]]. Det tilsvarer å beregne den inverse matrisen *A*<sup>-1</sup>. Den man alternativt også finnes ved Gauss-eliminasjon hvor man utvider  matrisen *A* til en  matrise ved å utvide den med  [[matrise|enhetsmatrisen]] i høyre del. Når denne utvidete matrisen så skrives om ved Gauss-eliminasjon slik at den samme enhetsmatrisen fremstår der matrisen *A* opprinnelig stod, vil man finne den inverse matrisen *A*<sup>-1</sup> der enhetsmatrisen opprinnelig ble satt inn.

Som en illustrasjon av metoden, kan man igjen betrakte den opprinnelige  matrisen *A* som inngikk i det aller første eksemplet. Utvides denne med   enhetsmatrisen, får man en  matrise. Ved Gauss-eliminasjon skrives nå denne om slik at venstre del først blir triangulær. I neste skritt fjernes så på venstre side de ikke-diagonale leddene på samme måte. Det gir

:<math>  
\begin{align} 
      (A|I)  & =  \left[\begin{array}{ccc|ccc} 1 & 2 & 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 & 1 & 0 \\ 4 & -1 & 2 & 0 & 0 & 1 \\ \end{array}\right]  
\longrightarrow \left[\begin{array}{ccc|ccc} 1 & 2 & 1 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1 & -1 & 0 \\ 0 & 0 & 1 & -5/2 & 9/2 & -1/2  \\ \end{array}\right]  \\
 & \longrightarrow \left[\begin{array}{ccc|ccc} 1 & 0 & 0 & 3/2 & -5/2 & 1/2 \\ 0 & 1 & 0 & 1 & -1 & 0 \\ 0 & 0 & 1 & -5/2 & 9/2 & -1/2  \\ \end{array}\right]    \\
\end{align}
</math>

Den inverse matrisen *A*<sup>-1</sup> kan nå leses ut på høyre side. Løsningen av ligningssettet er dermed   eller

:: <math>
              \begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix} 
             =   \begin{bmatrix} 3/2 & -5/2 & 1/2 \\ 1 & -1 & 0 \\ -5/2 & 9/2 & -1/2 \\ \end{bmatrix} \begin{bmatrix} 8 \\ 6 \\ 8 \end{bmatrix} 
             = \begin{bmatrix} 1 \\ 2 \\ 3 \end{bmatrix} 
</math>

som stemmer med hva som ble tidligere funnet.

For større matriser kan denne metoden vise seg å være numerisk unøyaktig, og den inverse matrisen må beregnes med en mer stabil metode.

==Litteratur==

* 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 lenker

* A. Beezer,  Systems of Linear Equations, web-versjon av lærebok i lineær algebra.