1.1 Lineære likningssystem, matriseform og Gauss-eliminasjon

En likning der de ukjente bare opptrer i første potens, ganget med tall og lagt sammen — ingen kvadrater, produkter av ukjente eller funksjoner som $\sin$ eller $\sqrt{\ }$. Formen er $a_1x_1+a_2x_2+\dots+a_nx_n=b$, der $a_1,\dots,a_n$ er kjente koeffisienter og $b$ er høyresiden. For eksempel er $2x+3y-z=5$ lineær, mens $x^2+y=1$ ikke er det.

En samling av én eller flere lineære likninger i de samme ukjente, som skal oppfylles samtidig. Å løse systemet betyr å finne alle verdier av de ukjente som gjør hver likning sann på én gang.

En liste med tallverdier $(x_1,\dots,x_n)$ — én for hver ukjent — som gjør alle likningene i systemet sanne samtidig. Vi skriver den ofte som en vektor $\mathbf x=(x_1,\dots,x_n)$.

Mengden av alle løsninger til systemet. Den kan bestå av nøyaktig ett punkt (entydig løsning), være tom (ingen løsning), eller inneholde uendelig mange punkter (en linje, et plan osv.). Å «løse systemet» betyr egentlig å beskrive hele denne mengden.

Et system som har minst én løsning kalles konsistent. Det kan ha nøyaktig én løsning eller uendelig mange — men løsningsmengden er ikke tom.

Et system uten noen løsning. Likningene motsier hverandre — for eksempel krever de samtidig at en størrelse er både $0$ og $1$. I radreduksjonen avslører dette seg som en rad $[\,0\ \cdots\ 0\mid c\,]$ med $c\ne0$, altså «$0=c$».

Tabellen av koeffisientene foran de ukjente, uten høyresidene. For systemet $2x+3y=5,\ x-y=1$ er koeffisientmatrisen $\begin{bmatrix}2&3\\1&-1\end{bmatrix}$. Radene svarer til likningene, kolonnene til de ukjente.

Koeffisientmatrisen utvidet med en kolonne for høyresidene, skilt med en strek: $[A\mid\mathbf b]$. For $2x+3y=5,\ x-y=1$ er totalmatrisen $\left[\begin{array}{cc|c}2&3&5\\1&-1&1\end{array}\right]$. Hele løsemetoden foregår ved å bearbeide denne matrisen.

Bytt om to rader. Det tilsvarer å skrive likningene i en annen rekkefølge og endrer selvsagt ikke hvilke løsninger systemet har. Skrives $R_i\leftrightarrow R_j$.

Gang alle tallene i en rad med et tall $k\ne0$. Det tilsvarer å gange en likning med $k$ på begge sider. Kravet $k\ne0$ er viktig: ganger du med $0$, mister du likningen. Skrives $R_i\to kR_i$.

Legg et multiplum av én rad til en annen rad: $R_i\to R_i+kR_j$. Dette er arbeidshesten — den lager nuller under en pivot. Fordi vi bare legger til en annen likning (som allerede må være oppfylt), endres ikke løsningsmengden.

To matriser er radekvivalente hvis den ene kan omdannes til den andre med en følge av elementære radoperasjoner. Nøkkelfakta: radekvivalente totalmatriser har nøyaktig samme løsningsmengde. Derfor har vi lov til å radredusere.

En matrise er på trappeform når (1) alle nullrader står nederst, og (2) det første ikke-null-tallet i hver rad (det ledende innslaget) står lenger til høyre enn det ledende innslaget i raden over. Da danner de ledende innslagene en «trapp» nedover mot høyre, og alle tall rett under et ledende innslag er $0$.

Det første tallet som ikke er $0$ i en rad, når vi leser fra venstre. Posisjonen kalles en pivotposisjon. Det er rundt de ledende innslagene hele metoden dreier: vi bruker dem til å lage nuller i resten av kolonnen.

En trappeform der i tillegg (3) hvert ledende innslag er $1$ (et ledende ener), og (4) hvert ledende ener er det eneste tallet som ikke er $0$ i sin kolonne — det er også nuller over det. En matrise har nøyaktig én redusert trappeform, og fra den kan løsningen leses direkte av.

En plass i matrisen der det står et ledende innslag i en (hvilken som helst) trappeform. Antallet pivotposisjoner er fast for en gitt matrise, uansett hvordan du radreduserer.

En kolonne som inneholder en pivotposisjon. De ukjente som svarer til pivotkolonner (blant variabelkolonnene), er de bundne ukjente — de bestemmes av de frie.

En ukjent hvis kolonne er en pivotkolonne. Hver pivotvariabel uttrykkes entydig ved de frie variablene når vi leser av den reduserte trappeformen.

En ukjent hvis kolonne ikke er en pivotkolonne. En fri variabel kan settes til hva som helst — vi gir den gjerne et parameternavn som $t$ eller $s$ — og de andre variablene følger av den. Ingen fri variabel betyr entydig løsning; minst én fri variabel (i et konsistent system) betyr uendelig mange løsninger.

Metoden som radreduserer en matrise til trappeform ved å gå forover: bruk hver pivot til å lage nuller under seg, kolonne for kolonne fra venstre. Deretter kan man lese av løsningen ved bakoversubstitusjon (nederste likning først).

Fortsettelsen av Gauss-eliminasjon helt til redusert trappeform: skaler hver pivot til $1$ og lag nuller også over pivotene. Da står løsningen ferdig avlest i høyresidekolonnen, uten bakoversubstitusjon. Dette er metoden boka bruker som standard.

Et system der alle høyresidene er $0$: $A\mathbf x=\mathbf 0$. Et slikt system er alltid konsistent, for $\mathbf x=\mathbf 0$ er alltid en løsning. Spørsmålet er derfor aldri om det har løsning, men om det har flere enn den ene.

Løsningen $\mathbf x=\mathbf 0$ (alle ukjente lik $0$) til et homogent system. Den finnes alltid, og alene er den ikke interessant.

En løsning av $A\mathbf x=\mathbf 0$ som ikke er $\mathbf 0$. Nøkkelregel: et homogent system har ikke-trivielle løsninger hvis og bare hvis det finnes minst én fri variabel, altså når en variabelkolonne mangler pivot. Med flere ukjente enn likninger er det garantert.

Å skrive en uendelig løsningsmengde som $\mathbf x=\mathbf x_p+t_1\mathbf v_1+\dots+t_k\mathbf v_k$, der $\mathbf x_p$ er én bestemt (partikulær) løsning og hver $\mathbf v_j$ hører til en fri variabel $t_j$. Antall parametre = antall frie variabler. Dette er den påkrevde formen for et svar med uendelig mange løsninger.

Rangen $\operatorname{rang}A$ er antallet pivotposisjoner i matrisen $A$ — like mange som det er ledende innslag i en trappeform. Den teller hvor mange «ekte» uavhengige likninger systemet har. Rangen bruker vi tungt fra Del 3 og utover; her holder det å vite at den er antall pivoter.

Etter Gauss-eliminasjon til trappeform kan man finne de ukjente ved å løse nederste likning først (den har færrest ukjente) og sette resultatet oppover, én rad om gangen. Alternativet er å gå helt til redusert trappeform (Gauss–Jordan), som boka foretrekker.

Et lineært system har nøyaktig én av tre typer løsningsmengde: entydig (én løsning — pivot i hver variabelkolonne), ingen (inkonsistent — pivot i høyresidekolonnen), eller uendelig mange (konsistent med minst én fri variabel). Ingen fjerde mulighet finnes.