Likningssett og Gauss-eliminasjon

En matriselikning er en likning på formen \(Ax = v\), der \(A\) er en \(n \times m\) matrise, \(x\) er en ukjent vektor med høyde \(m\) og \(v\) er en kjent vektor med høyde \(n\). Her har du et eksempel på en matriselikning:

\(\begin{bmatrix}2 & -2 & 0 \\1 & -1 & 1 \\0 & 3 & -2\end{bmatrix} \)\(\begin{bmatrix} x \\ y \\ z \end{bmatrix} \)\(= \)\(\begin{bmatrix} -6 \\ 1 \\ -5 \end{bmatrix} \)

En matriselikning er egentlig bare en annen måte å skrive et likningssett. Hvis vi multipliserer matrisen \(A\) og vektoren \(x\) i matriselikningen over får vi dette:

\(\begin{bmatrix}2x & -2y & 0z \\1x & -1y & 1z \\0x & 3y & -2z\end{bmatrix} \)\(= \)\(\begin{bmatrix} -6 \\ 1 \\ -5 \end{bmatrix} \)

Og for at det skal stå det samme på begge sider i likningen over, må vi ha verdier for \(x\), \(y\) og \(z\) som opfyller alle disse likningene:

\(2x - 2y + 0z = -6\)

\(1x - 1y + 1z = 1\)

\(0x + 3y – 2z = -5\)

Likningssettet representerer altså akkurat samme problem som matriselikningen! Det vil si at hvis man kan finne ut hva \(x\), \(y\) og \(z\) er i matriselikningen, vet man hva \(x\), \(y\) og \(z\) er i likningssettet, og omvendt. Derfor er det vanlig å skrive om likningssett til matriselikning, slik at man kan løse det på pc eller med gauss-eliminasjon.

Nå har vi skrevet opp likningssettet som en matriselikning, så nå lurer du kanskje på hvordan man løser matriselikninger. Det kan man gjøre for hånd med gauss-eliminasjon. Før du starter å «gausse» er det vanlig å skrive om likningen slik:

\(\begin{bmatrix}a_{11} & a_{12} & a_{13} \\a_{21} & a_{22} & a_{23} \\a_{31} & a_{32} & a_{33}\end{bmatrix}\begin{bmatrix} x \\ y \\z \end{bmatrix}=\begin{bmatrix} k_1 \\ k_2 \\ k_3 \end{bmatrix} \) --- \(\rightarrow\) --- \( \begin{array}{ccc|c} a_{11} & a_{12} &a_{13} & k_1\\ a_{21} & a_{22} & a_{23} & k_2 \\ a_{31} & a_{32} & a_{33} & k_3 \end{array} \)

Slik som matriselikningen er skrevet opp nå kaller vi den for en utvidet matrise. Til venstre i den utvidede matrisen har vi en koeffisientmatrise, med alle koeffisientene fra likningssettet. Til høyre har vi konstantene fra likningssettet. Når vi gauss-eliminerer er målet å skrive om matriselikningen til en form der man lett kan se løsningen. For å skrive den om har vi tre operasjoner vi kan gjøre på radene i den utvidede matrisen.

1. Gange rad med en konstant
2. Addere eller subtrahere rader med hverandre
3. Bytte plass på radene

Målet er å bruke disse operasjonene til å omforme den utvidede matrisen helt til den er på trappeform (på engelsk heter dette «reduced row echelon form», som er et SYKT mye kulere navn). En matrise er på trappeform når det er en «trapp» med 0-tall nederst til venstre i matrisen, slik som denne utvidede matrisen:

\( \begin{array}{ccc|c} 2 & 3 & 1&2\\ 0 & 1 & 4 & 2 \\ 0 & 0 & 2 & 4 \end{array} \)

Når man har den utvidede matrisen på trappeform, kan man gjøre den tilbake til et likningssett:

\( \begin{array}{ccc|c} 2 & 3 & 1&2\\ 0 & 1 & 4 & 2 \\ 0 & 0 & 2 & 4 \end{array}\) --- \(\rightarrow\) --- \(\begin{matrix}2x & + & 3y & + & 1z &= & 0 \\0x & + & 1y & + & 4z & = & 2 \\0x & + & 0y & + & 2z & = & 4\end{matrix}\)

Nå kan vi lett se at \(z=2\) ved å se på nederste likning. Deretter kan vi sette inn \(z=2\) i likningen over og finne at \(y=-6\). Til slutt kan vi sette inn \(z=2\) og \(y=-6\) i den øverste likningen, for å finne at \(x=8\).

I denne figuren har jeg forsøkt å vise hele prosessen:

Det finnes likningssett som er uløselige, og det finnes likningssett med uendelig mange løsninger. I denne delen skal vi se på hvordan du kan kjenne igjen disse når du gauss-eliminerer.

Rader uten informasjon

Noen ganger når man gauss-eliminerer kan man ende opp med en rad med bare 0-tall, slik som dette:

\( \begin{array}{ccc|c} 1 & -2 & 1 & 0\\ 0 & 1 & -3 & -1 \\0& 0 & 0 & 0 \end{array} \)

Da inneholder raden med kun 0-tall ikke noen ekstra informasjon om løsningen på likningssettet (raden sier bare 0 = 0, og det er ikke så interresant), og vi kan ta bort raden og fortsette å gauss-eliminere uten den:

\( \begin{array}{ccc|c} 1 & -2 & 1 & 0\\ 0 & 1 & -3 & -1 \\0& 0 & 0 & 0 \end{array} \) ---- \(\rightarrow\) ---- \( \begin{array}{ccc|c} 1 &-2 & 1 & 0\\ 0 & 1 & -3 & -1 \end{array} \)

Ingen løsninger

Man kan også ende opp med en rad der alle tallene på venstre side av streken er 0, men der tallet til høyre for streken ikke er 0, for eksempel:

\( \begin{array}{ccc|c} 1 & -2 & 1 & 0\\ 0 & 1 & -3 & -1 \\0& 0 & 0 & 1 \end{array} \)

Hvis dette skjer er likningssettet uløselig! (skummelt). Det er fordi den nederste raden representerer likningen 0 = 1, som ikke gir mening.

Uendelig antall løsninger

En matriselikning har uendelig antall løsninger dersom man ikke har like mange rader som ukjente variabler. For eksempel:

\( \begin{array}{ccc|c} 3 & 2 & -2 & 1\\ 3 & 0 & -1 & -1 \end{array} \)

Dette kan enten skje hvis man starter med færre likninger enn ukjente, eller hvis noen av radene «forsvinner» underveis i gauss-elimineringen fordi de blir fylt med 0-tall. Når man har uendelig mange løsninger er det fortsatt mulig å finne en løsning, bare at denne løsningen vil inneholde fri variabel.

La oss si at vi har matriselikningen:

\( \begin{bmatrix}-1 & 2 & 2 \\1 & 4 & 2 \\-2 & -8 & -4\end{bmatrix}\vec{v} = 0 \)

Denne matriselikningen kan med gauss-eliminasjon forenkles til:

\( \begin{array}{ccc|c} -1 & 2 & 2 & 0\\ 0 & 6 & 4 & 0 \\0& 0 & 0 & 0 \end{array} \)

Siden den nederste raden ikke har noen informasjon kan vi ta den bort, og få:

\( \begin{array}{ccc|c} -1 & 2 & 2 & 0\\ 0 & 6 & 4 & 0 \end{array} \)

Nå har vi færre rader enn ukjente. For å finne en løsning som inneholder en fri variabel starter vi med å skrive tilbake til likningssett:

\(-1x+2y+2z=0\)

\(6y+4z=0\)

Deretter setter vi en av variablene i likningssettet lik en fri variabel \(s\). I dette eksempelet valgte jeg å sette \(z=s\) fordi det var lettest, men man får også riktig svar hvis man setter \(y=s\) eller \(x=s\). Når vi setter \(z=s\) får vi:

\(-1x+2y+2s=0\)

\(6y+4s=0\)

Deretter løser vi likningssettet for \(x\) og \(y\) med hensyn på \(s\):

\(y=-\frac{2}{3}s\)

\(x=\frac{2}{3}s\)

Dette resultatet kan gjøres om til vektoren:

\( \vec{v} =\begin{bmatrix} \frac{2}{3}s \\ -\frac{2}{3}s \\ s \end{bmatrix} = \begin{bmatrix} \frac{2}{3} \\ -\frac{2}{3} \\ 1 \end{bmatrix}s \)