9.3 Lineære likningssystem og Gauss-eliminasjon

Når to ukjente blir til tre

Med to ukjente klarer du deg fint med innsetting eller addisjonsmetoden. Men en fabrikk som skal fordele arbeid, materialer og maskintid på tre produkter, ender raskt opp med tre likninger og tre ukjente -- og da blir de gamle metodene tunge og rotete. Løsningen er Gauss-eliminasjon, en systematisk oppskrift som passer perfekt sammen med matriser og som datamaskiner bruker til å løse selv enorme økonomiske modeller.

Første steg er å skrive systemet kompakt. Et lineært likningssystem kan alltid uttrykkes som $A\mathbf{x} = \mathbf{b}$, der $A$ er koeffisientmatrisen, $\mathbf{x}$ er kolonnen av ukjente og $\mathbf{b}$ er høyresidene. Enda mer praktisk er totalmatrisen (eller utvidet matrise), der vi skriver $\mathbf{b}$ rett ved siden av $A$ med en loddrett strek som erstatter likhetstegnet. For systemet $2x + y - z = 3$, $x - 3y + 2z = -1$, $4x + 2y + 5z = 12$ blir totalmatrisen

$$\left[\begin{array}{ccc|c} 2 & 1 & -1 & 3 \\ 1 & -3 & 2 & -1 \\ 4 & 2 & 5 & 12 \end{array}\right]$$

Hver rad er en likning, hver kolonne til venstre for streken hører til én ukjent. Variabler som mangler i en likning får rett og slett koeffisient $0$.

Radoperasjoner og trappeform

Målet er å forenkle totalmatrisen så mye som mulig -- uten å ødelegge løsningen. Det finnes tre elementære radoperasjoner som garantert bevarer løsningssettet. Vi kan bytte om to rader ($R_i \leftrightarrow R_j$), gange en rad med et tall som ikke er null ($R_i \to kR_i$), og legge et multiplum av én rad til en annen ($R_i \to R_i + kR_j$). Hver av disse svarer til en lovlig operasjon på likningene, så svaret er det samme før og etter.

Det vi sikter mot, kalles trappeform. En matrise er på trappeform når alle rene null-rader står nederst, og når det første tallet som ikke er null i hver rad -- kalt en pivot -- står lenger til høyre enn pivoten i raden over. Matrisen $\begin{pmatrix} 2 & 3 & -1 \\ 0 & 5 & 4 \\ 0 & 0 & 7 \end{pmatrix}$ er et godt eksempel: pivotene danner en trapp som synker mot høyre.

Går vi enda lenger, til redusert trappeform, krever vi i tillegg at hver pivot er $1$ og er det eneste tallet i sin kolonne. Identitetsmatrisen $\begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix}$ er den fineste reduserte trappeformen av alle. Når totalmatrisen er kommet på trappeform, ligger løsningen rett foran oss.

Gauss-eliminasjon steg for steg

Selve Gauss-eliminasjonen går ut på å lage nuller systematisk: bruk rad 1 til å fjerne den første ukjente fra radene under, bruk så rad 2 til å fjerne den neste, og fortsett til matrisen er på trappeform. Til slutt løser vi nedenfra og opp med bakover-innsetting.

Ta systemet $x + y + z = 6$, $2x - y + z = 3$, $x + 2y - z = 2$. Totalmatrisen er $\left[\begin{array}{ccc|c} 1 & 1 & 1 & 6 \\ 2 & -1 & 1 & 3 \\ 1 & 2 & -1 & 2 \end{array}\right]$. Vi gjør $R_2 \to R_2 - 2R_1$ og $R_3 \to R_3 - R_1$, og får $\left[\begin{array}{ccc|c} 1 & 1 & 1 & 6 \\ 0 & -3 & -1 & -9 \\ 0 & 1 & -2 & -4 \end{array}\right]$. For å unngå brøker bytter vi $R_2 \leftrightarrow R_3$ slik at vi får et pent pivot, og deretter $R_3 \to R_3 + 3R_2$. Det gir trappeformen $\left[\begin{array}{ccc|c} 1 & 1 & 1 & 6 \\ 0 & 1 & -2 & -4 \\ 0 & 0 & -7 & -21 \end{array}\right]$.

Nå leser vi nedenfra. Siste rad sier $-7z = -21$, altså $z = 3$. Nest siste sier $y - 2z = -4$, så $y = -4 + 6 = 2$. Øverste rad sier $x + y + z = 6$, så $x = 6 - 2 - 3 = 1$. Løsningen er $x = 1$, $y = 2$, $z = 3$, og en rask innsetting i den opprinnelige likning 1 bekrefter at $1 + 2 + 3 = 6$. Et godt råd: la pivotene gjerne være større tall underveis, og normaliser til $1$ helt til slutt -- det holder brøkene unna i mellomstegene.

Ett, ingen eller uendelig mange svar

Når trappeformen er klar, kan vi straks lese av hvor mange løsninger systemet har. Har hver variabel sin egen pivot, er svaret entydig -- én løsning. Dukker det opp en rad som sier $0 = c$ for et tall $c \neq 0$, er systemet selvmotsigende og har ingen løsning; vi kaller det inkonsistent. Og er det færre pivoter enn variabler, har systemet uendelig mange løsninger, der de variablene uten pivot blir frie og kan settes til hva som helst.

Se på $x + 2y - z = 3$, $2x + 4y - 2z = 7$, $x - y + z = 1$. Gjør vi $R_2 \to R_2 - 2R_1$, blir hele venstresiden $0$ mens høyresiden blir $7 - 6 = 1$. Raden sier $0 = 1$, noe som er umulig -- altså ingen løsning. Et helt annet tilfelle er $x + y + z = 6$, $2x + 2y + 2z = 12$, $x - y + z = 2$: her er likning 2 bare det dobbelte av likning 1 og bidrar ingenting nytt. Vi ender med to pivoter for tre variabler, slik at $z = t$ blir fri og løsningen er $\mathbf{x} = (4 - t,\ 2,\ t)^T$ -- uendelig mange.

For et kvadratisk system finnes en rask snarvei: er $\det(A) \neq 0$, har systemet nøyaktig én løsning. Er $\det(A) = 0$, har det enten ingen eller uendelig mange, avhengig av høyresiden. Disse verktøyene brukes i alt fra produksjonsplanlegging til blandingsproblemer: skal en kaffeprodusent lage 100 kg blanding til 38 kr/kg med dobbelt så mye Brasil som Colombia, gir Gauss-eliminasjon raskt svaret 40 kg Brasil, 40 kg Etiopia og 20 kg Colombia.

Oppsummering

Et lineært likningssystem skriver vi kompakt som $A\mathbf{x} = \mathbf{b}$, og enda mer praktisk som en totalmatrise $[A \mid \mathbf{b}]$ der hver rad er en likning. De tre elementære radoperasjonene -- bytte rader, gange en rad med et tall ulikt null, og legge et multiplum av én rad til en annen -- forenkler matrisen uten å endre løsningen.

Med Gauss-eliminasjon bringer vi totalmatrisen på trappeform, der pivotene synker mot høyre, og leser deretter av svaret med bakover-innsetting nedenfra og opp. Trappeformen avslører også antall løsninger: én når hver variabel har pivot, ingen når en rad sier $0 = c$ med $c \neq 0$, og uendelig mange når det er færre pivoter enn variabler. For kvadratiske system gir determinanten en rask test -- $\det(A) \neq 0$ betyr én entydig løsning. I neste kapittel møter vi Cramers regel og de store økonomiske anvendelsene.