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 x1, x2 og x3. Generelt kan det skrives som
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 a11 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 x1 elimineres i disse.
- 3) På samme måte kan nå andre ligning brukes til å eliminere x2 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
Det opprinnelige ligningsystemet er dermed bragt over på triangulær form. Fra den siste ligningen kan nå x3 finnes direkte. Settes dette inn i den andre ligningen, gir den igjen x2. Med disse to verdiene finnes så x1 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 ukjente i m ligninger samler man de ukjente sammen i en kolonnevektor x = (x1, x2, ..., xn)T og likedan de inhomogene leddene i kolonnevektoren b = (b1, b2, ..., bm)T slik at ligningssystemet kan skrives som Ax = b. Her er nå A en m × n matrise med elementer bestående av koeffisientene aij til ligningssettet. Tar man med de inhomogene leddene, kan alle koeffisientene i ligningssettet samles i den utvidete matrisen
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:
I den utvidete matrisen kan x1 elimineres fra andre rad ved ganske enkelt å ta differensen mellom denne og den første. Likedan kan x1 elimineres fra den neste raden ved å trekke 4 ganger den første raden fra den tredje. Det gir:
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 x2 elimineres fra siste rad ved å multiplisere andre rad med 9 og trekke resultatet fra tredje rad. På den måten kommer man frem til
Nederste rad tilsvarer nå 2x3 = 6 eller x3 = 3. I andre rad opptrer ikke x3 slik at man også fra denne raden kan lese direkte ut at x2 = 2. Settes disse to resultatene inn i første ligning, gir den til slutt at x1 = 1. Så løsningen til det fulle ligningssettet er gitt ved punktet x0 = (1,2,3)T i vektorrommet R3. I dette enkle tilfellet kunne løsningen bli funnet direkte fra den inverse til matrisen A ved å benytte at x = A-1b . 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 :
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
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 x3 kan derfor ikke bestemmes og er en fri variabel. Kaller man den for s, så er altså x3 = s. Fra andre rad finner man tilsvarende at x2 = 2, mens første rad gir x1 + x3 = 4. Det betyr at heller ikke den ukjente x1 er bestemt, men varierer som x1 = 4 - s. 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
eller x = xp + s v. Her er vektoren v = (-1, 0, 1)T og x0 = (4, 2, 0)T angir et punkt i vektorrommet R3. 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 Ax = 0,
En slik løsning tilhører nullrommet eller kjernen til matrisen A 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 nulliteten null(A) til dette vektorrommet. 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 ligninger med n 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 rangen rang(A) til matrisen A. Da man i alt har n kolonner i matrisen, har man derfor det viktige resultatet
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
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
Her er tredje og femte kolonne uten ledende enere. Nulliteten til matrisen er dermed null(A) = 2, og de tilsvarende ukjente x3 og x5 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 x4 - 5x5 = 0. Setter man den frie variable x5 = s, er altså x4 = 5s. Andre rad gir x2 - 2x3 + 3x5 = 0. Skriver man den fri variable x3 = t, betyr det at x2 = 2t - 3s. Tilslutt, fra første rad følger at x1 + x3 + x5 = 0 slik at x1 = - s - t.
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 x = s v1 + t v2. Dette er vektorer i det 5-dimensjonale rommet R5 hvor de to homogene løsningene v1 = (-1, -3, 0, 5, 1)T og v2 = (-1, 2, 1, 0, 0)T utspenner et 2-dimensjonalt plan som inneholder alle løsningene.
Inhomogene ligninger
Det inhomogene ligningssettet Ax = b vil ha løsninger når vektoren b er konsistent med m × 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 x0 av ligningssettet, vil da i allminnelighet alle løsningene kunne skrives på formen
Her er λi frie parametre som tilsvarer løsningene vi av den homogene ligningen AvI = 0, mens p = n - r er dimensjonen til nullrommet for matrisen A. Denne formen på den generelle løsningen verifiseres ved å skrive den som x = x0 + v. Da blir Ax = Ax0 + Av = b da Av = 0 og den partikulære løsningen oppfyller den inhomogene ligningen Ax0 = b.
Det geometriske innholdet av det generelle løsningsrommet kan man tenke seg å være nullrommet utspent av vektorene vi , som flyttes bort fra origo i vektorrommet Rn med vektoren x0 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
![](http://upload.wikimedia.org/wikipedia/commons/thumb/3/3f/Matrix_Columns.svg/240px-Matrix_Columns.svg.png)
For å finne ut om disse løsningene virkelig eksisterer, kan man undersøke vektorrommet som utspennes av kolonnevektorene til A. Er denne en m × n matrise, vil disse være vektorer med m komponenter,
Da det inhomogene ligningssettet kan nå skrives som
må vektoren b være en lineærkombinasjon av disse kolonnevektorene. Matrisen A inneholder i alt n slike vektorer som tilhører vektorrommet Rm. Hvis antall ukjente n i ligningssystemet er mindre enn antall ligninger m, vil kolonnevektorene til A utspenne et vektorrom som maksimalt har dimensjon n. Da vektoren b ligger i Rm 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 Rm. Det betyr at betingelsen rang(A) = m 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 det(A) ≠ 0 slik at matrisen har en inverse A-1. Løsningen til ligningssettet er da x = A-1b . 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-1. Den man alternativt også finnes ved Gauss-eliminasjon hvor man utvider n × n matrisen A til en n × 2n matrise ved å utvide den med n × n 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-1 der enhetsmatrisen opprinnelig ble satt inn.
Som en illustrasjon av metoden, kan man igjen betrakte den opprinnelige 3 × 3 matrisen A som inngikk i det aller første eksemplet. Utvides denne med 3 × 3 enhetsmatrisen, får man en 3 × 6 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
Den inverse matrisen A-1 kan nå leses ut på høyre side. Løsningen av ligningssettet er dermed x = A-1b eller
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.