1.1 Gauss-eliminasjon: trappeform og merkede radoperasjoner

$$[A\,|\,b]=\left[\begin{array}{ccc|c}a_{11}&a_{12}&a_{13}&b_1\\a_{21}&a_{22}&a_{23}&b_2\\a_{31}&a_{32}&a_{33}&b_3\end{array}\right].$$

Hver rad er én likning, hver av de tre første søylene hører til én ukjent, og siste søyle er høyresiden. Å regne på systemet blir nå å regne på tallrutenettet — vi slipper å skrive $x,y,z$ om og om igjen.

Å bytte om to hele rader (likninger). Notasjon: $I\leftrightarrow II$ betyr «bytt rad 1 og rad 2». Operasjonen endrer ikke løsningsmengden — rekkefølgen på likningene er likegyldig — men brukes for å få et brukbart (helst $1$) pivotelement øverst i en søyle.

Å gange en hel rad med et tall forskjellig fra null. Notasjon: $\tfrac12\,II$ betyr «multipliser rad 2 med $\tfrac12$». Å gange en likning med et tall $\ne 0$ endrer ikke løsningen. Skalering med $0$ er forbudt — da mister man informasjon.

Å legge et tall ganger én rad til en annen rad. Notasjon: $II-2I$ betyr «erstatt rad 2 med (rad 2) $-\,2\cdot$(rad 1)». Dette er arbeidshesten: den lager nuller under et pivotelement. Den erstattede raden er den som endres; raden vi trekker fra, står urørt.

To matriser er radekvivalente, skrevet $A\sim B$, når den ene kan gjøres om til den andre ved en følge av elementære radoperasjoner. Radekvivalente utvidede matriser representerer likningssystemer med nøyaktig samme løsningsmengde — det er derfor vi har lov til å regne oss fra en tungvint matrise til en enkel.

$$\;\overset{\;II-2I,\ III-I\;}{\sim}\;$$

Dette er ikke pynt — det er dokumentasjonen som lar sensor følge argumentet, og den skiller full uttelling fra halv. Umerkede radoperasjoner er den vanligste føringsfeilen i sjanger A.

En matrise er på trappeform når nullene danner en trapp nedover mot venstre: (i) eventuelle helnullrader ligger nederst, og (ii) det første tallet fra venstre som ikke er null i en rad — det ledende elementet — står strengt lenger til høyre enn det ledende elementet i raden over. Da er alle tall rett under et ledende element null. Fra trappeform kan systemet løses ved tilbakesubstitusjon.

Det ledende elementet (pivotet) i en rad er det første tallet fra venstre som ikke er null. Søylen det står i, kalles en pivotsøyle. Pivotene forteller hvor «trappetrinnene» ligger, og antallet deres er nøkkeltallet i kapitlene som følger — det blir rangen (kap. 1.2).

En ukjent hvis søyle er en pivotsøyle, kalles en bunden (ledende) variabel — den bestemmes av de andre. En ukjent hvis søyle ikke har noe pivot, er en fri variabel: den kan velges fritt, og vi gir den en parameter ($t,s,\dots$). Antall frie variabler forteller hvor mange «frihetsgrader» løsningen har.

En redusert trappeform er en trappeform der man i tillegg har (i) skalert hvert pivot til $1$, og (ii) laget nuller også over hvert pivot. Da står løsningen ferdig avlest: hver pivotsøyle inneholder bare ett ettall. Redusert trappeform er entydig for en gitt matrise — i motsetning til vanlig trappeform, som avhenger av regneveien.

Et lineært system har alltid nøyaktig ett av tre utfall, og trappeformen avslører hvilket: (1) entydig løsning — hver variabel er bunden (like mange pivoter som ukjente); (2) ingen løsning — det oppstår en umulig rad $[\,0\ 0\ 0\ |\ k\,]$ med $k\ne0$; (3) uendelig mange løsninger — systemet er konsistent, men minst én variabel er fri.

Et system er konsistent (løsbart) når det har minst én løsning, og inkonsistent når det ikke har noen. Inkonsistens vises ved en rad $[\,0\ \cdots\ 0\ |\ k\,]$ med $k\ne0$ i trappeformen — den sier «$0=k$», som er umulig. Ser du en slik rad, kan du stoppe: systemet har ingen løsning.

Når det finnes frie variabler, beskriver vi alle løsninger ved å gi hver fri variabel en parameter ($z=t$ osv.) og uttrykke de bundne variablene ved parametrene. Løsningen skrives da som en partikulær løsning pluss parameter ganger retningsvektor(er), f.eks. $(x,y,z)=(-3,2,0)+t(7,-3,1)$. Å glemme å parametrisere — og bare oppgi ett løsningspunkt — er en klassisk feil.

Et system $Ax=0$ (bare nuller på høyresiden) kalles homogent. Det er alltid konsistent, for $x=0$ — trivialløsningen — passer alltid. Spørsmålet er om det finnes andre løsninger: det gjør det nøyaktig når systemet har minst én fri variabel. Disse ikke-trivielle løsningene blir nullrommet i kap. 1.2.

En samling likninger der hver ukjent bare opptrer i første potens og aldri ganges med en annen ukjent — i symboler $Ax=b$. «Lineært» betyr rett og slett at grafene er rette linjer / plan, uten kvadrater, produkter eller andre krumninger. Alt i dette kapitlet handler om å løse slike systemer effektivt.

Tallrutenettet $A$ av koeffisientene alene — altså den utvidede matrisen $[A\,|\,b]$ uten høyresidesøylen. For homogene systemer ($b=0$) holder det å radredusere koeffisientmatrisen, siden høyresiden forblir null uansett.

Metoden for å lese ut løsningen fra en trappeform: start i nederste ikke-nullrad, løs den for sin ledende variabel, og sett resultatet oppover i radene én etter én. Dette er Gauss-metodens siste steg, og alternativet til å rydde helt til redusert trappeform.

Den systematiske oppskriften: bruk elementære radoperasjoner til å skape nuller under hvert pivot, søyle for søyle fra venstre, til matrisen er på trappeform — og løs så ved tilbakesubstitusjon. Navnet skyldes Carl Friedrich Gauss, men teknikken var kjent i Kina for over 2000 år siden.

En rad på formen $[\,0\ 0\ \cdots\ 0\ |\ k\,]$ med $k\ne0$, som sier «$0=k$». Dukker en slik rad opp under radreduksjonen, er systemet inkonsistent og har ingen løsning — og du kan stoppe med én gang.

Antall søyler uten pivot i trappeformen. Tallet forteller dimensjonen til løsningsmengden: $0$ frie variabler gir et punkt (entydig), $1$ gir en linje, $2$ gir et plan, og så videre. Det er samtidig antall parametre du trenger i parametriseringen.