Uke 3 – hva slags informasjon mister en matrise?
Ukens spørsmål: Hva slags informasjon mister en matrise – og hva kan vi finne igjen?
Vi følger ett lite eksempel hele uka: Et bilde med 16 piksler gjøres om til et bilde med fire piksler. Underveis får ideene navn: lineær transformasjon, basis og koordinater, nullrom og rang. Til slutt bruker vi de samme ideene på polynomer. Denne overgangen er grunnlaget for prosjektet.
Kort løype
- 3.1 To bilder, samme output: noe går tapt.
- 3.2 Fra bilde til vektor og matrise: én rad er én måling.
- 3.3 Beskriv bilder med forskjellige basiser: samme bilde, to oppskrifter.
- 3.4 Hva transformasjonen ser og ikke ser: nullrom, kolonnerom og rang.
- 3.5 Overfør ideene til polynomer: grunnlaget for prosjektet.
Forelesning viser hovedløpet. Gå i dybden åpner mellomregninger, ekstra forsøk og sidespor. 3.6 er egenarbeid med bildeforsøk og oppgaver. Støtteløpet (3.7–3.8) er et oppslagsverk dersom Gauss-eliminasjon, pivoter, kolonnerom eller nullrom ikke sitter friskt.
Koden er et verktøy for å undersøke lineær algebra, ikke et eget programmeringspensum. Åpne denne boksen når du møter en ukjent kodelinje. Du trenger ikke lære alt utenat.
Lag og les arrays
x = np.array([2.0, -1.0, 3.0])
X = np.array([[1.0, 2.0],
[3.0, 4.0]])x er en vektor med tre tall. X er en \(2\times2\)-tabell. Python teller fra 0, så x[0] er første tall, X[0, 1] er tallet i første rad og andre kolonne, og X.shape er (2, 2).
Bytt mellom bilde og vektor
x = X.reshape(-1) # [1., 2., 3., 4.]
X_again = x.reshape(2, 2)reshape flytter ikke eller endrer noen verdier. Den viser bare de samme tallene med en annen form. -1 betyr «la NumPy finne riktig lengde».
Bygg matriser av vektorer
A = np.column_stack([u, v]) # u og v blir kolonner
B = np.vstack([r1, r2]) # r1 og r2 blir raderBruk column_stack når vektorene er byggesteiner eller basisvektorer. Bruk vstack når hver vektor beskriver én måling eller én likning.
Kombiner hvert tall i én liste med hvert tall i en annen
a = np.array([1.0, 2.0, 3.0])
b = np.array([10.0, 20.0])
table = a[:, None] * b[None, :] # rad i, kolonne j: a[i]*b[j]a[:, None] gjør a til en kolonne med form (3, 1), og b[None, :] gjør b til en rad med form (1, 2). NumPy kombinerer da hvert tall i kolonnen med hvert tall i raden og lager \(3\times2\)-tabellen [[10, 20], [20, 40], [30, 60]]. Det samme virker med +, - og **.
err = np.array([0.1, -0.5, 0.3])
i = np.argmax(np.abs(err)) # plassnummeret til det største avviket: 1argmax gir plassen, ikke verdien; selve verdien er err[i], her \(-0.5\).
Regn med matriser
y = A @ x
c = np.linalg.solve(P, target)A @ x er matrise-vektorproduktet \(Ax\). solve(P, target) gjør reverse engineering: Den finner koeffisientene c som oppfyller P @ c = target. Vi bruker den her bare når matrisen er kvadratisk og likningssettet har nøyaktig én løsning.
Kontroller et matematisk svar
error = np.linalg.norm(A @ x - b)
rank = np.linalg.matrix_rank(A)norm måler størrelsen på forskjellen. Et resultat som 1e-15 leses vanligvis som numerisk null. matrix_rank teller hvor mange uavhengige retninger NumPy kan skille med maskinpresisjonen; den erstatter ikke begrunnelsen med pivoter eller lineær uavhengighet.
Lag nyttige tallfølger og testdata
indices = np.arange(4) # 0, 1, 2, 3
points = np.linspace(-1.0, 1.0, 5) # fem jevnt fordelte punkter
rng = np.random.default_rng(8)
test = rng.random((2, 2)) # et tilfeldig 2x2-bildeEt fast tall i default_rng(8) gjør at alle får de samme testdataene. Da kan vi gjenta forsøket og sammenligne svar. np.repeat brukes senere til å kopiere en verdi flere ganger; np.zeros((m, n)) lager en \(m\times n\)-matrise som du kan fylle ut.
Kode merket som ferdig maskineri kan brukes uten at du forstår alle indeksene og løkkene. Les først kommentarene og spør: Hva er inputen? Hva er outputen? Hvilken matematisk påstand skal utskriften eller figuren kontrollere?
Kan et sjakkbrett og en ensfarget grå flate bli helt like når vi gjør bildene mindre? Svaret er ja, og denne uka finner vi ut nøyaktig hvorfor. En transformasjon er en regel som tar en input og lager en output,
\[T(\text{input})=\text{output}.\]
Det er det samme som en funksjon; ordet avbildning brukes også. Her er inputen et bilde \(X\) med 16 piksler og outputen et mindre bilde \(Y=T(X)\) med fire piksler. Spørsmålet er hvilken informasjon regelen bruker, og om noe går tapt underveis.
Gå i dybden: transformasjon, funksjon og Python-funksjon
Inputen til en transformasjon kan være et bilde, en lydfil eller en tabell med målinger; outputen kan være et nytt bilde eller noen få tall som oppsummerer inputen. Hver tillatt input får nøyaktig én output, akkurat som for en funksjon. I matematikk er for eksempel \(f(t)=t^2\) en funksjon som sender \(3\) til \(9\). I Python gjør abs(-3) inputen -3 om til outputen 3. På samme måte tar Python-funksjonen average_pool(X) inn et bilde og returnerer et mindre bilde.
Navnet transformasjon sier ikke noe mer mystisk enn dette. Det framhever bare at input og output gjerne er vektorer eller bilder, ikke nødvendigvis enkelttall.
Figuren viser hele oppskriften uten matriser eller formler.
Fargene og pilene viser hva som hører sammen: De fire pikslene i det blå området samles til den blå outputpikselen, og så videre. «Samle» betyr her å ta gjennomsnittet av de fire pikselverdiene, et blokkgjennomsnitt. Dermed går vi fra 16 tall til fire tall.
Vi begynner med to \(4\times4\)-bilder som ser helt forskjellige ut: et ensfarget bilde \(X_1\) og et tydelig sjakkmønster \(X_2\). Bokstaven \(X\) viser alltid til et inputbilde med 16 piksler og \(Y\) til et outputbilde med fire piksler:
\[ Y_1=T(X_1), \qquad Y_2=T(X_2). \]
Cellen under lager de to inputbildene og bruker den ferdige funksjonen average_pool på hvert av dem. Hvordan den regner ut blokkgjennomsnittene med en matrise, ser vi i 3.2.
Inputbildene i venstre kolonne er tydelig forskjellige, mens outputbildene i høyre kolonne er like. For å undersøke dette uten å stole bare på øynene beregner vi to forskjellsmatriser, piksel for piksel:
\[ D_{\text{input}}=X_1-X_2, \qquad D_{\text{output}}=Y_1-Y_2. \]
Hvis to bilder er like, er forskjellen 0 på hver pikselplass. Da får vi nullbildet, altså en matrise der alle pikselverdiene er 0.
Gå i dybden: forskjellsbildet piksel for piksel
Forskjellsmatrisene forteller både hvor bildene er forskjellige, og i hvilken retning pikselverdiene har endret seg. Tabellen nedenfor skal leses rad for rad og kolonne for kolonne:
- Øverste rad viser de beregnede forskjellene. Venstre kolonne sammenligner de to \(4\times4\)-inputene, mens høyre kolonne sammenligner de to \(2\times2\)-outputene.
- Nederste rad viser nullbilder med tilsvarende størrelse. De fungerer som visuelle referanser: En forskjell som ser ut som nullbildet under, har ingen utslag.
- Rødt betyr positiv forskjell, blått betyr negativ forskjell og hvitt betyr
- Størrelsen på hver rute følger antallet piksler, så et \(2\times2\)-bilde har halvparten av sidelengden til et \(4\times4\)-bilde.
Cellen regner ut de to forskjellene og tegner dem over hvert sitt nullbilde.
I feltet øverst til venstre veksler verdiene mellom \(+0.4\) og \(-0.4\). De røde rutene oppstår der \(X_1\) har verdien \(0.5\) og \(X_2\) har \(0.1\); de blå oppstår der \(X_1\) har \(0.5\) og \(X_2\) har \(0.9\). Inputbildene er derfor forskjellige på alle 16 pikselplasser. Feltet øverst til høyre er helt hvitt og ser ut som nullbildet under: \(Y_1-Y_2\) er 0 på alle fire plasser, så outputbildene er like.
Ett tall for størrelsen på en forskjell
Vi vil ha ett tall som svarer på spørsmålet «hvor stor er forskjellen totalt?». Vi kan ikke bare summere verdiene i forskjellsmatrisen. I \(D_{\text{input}}\) er åtte verdier \(0.5-0.1=+0.4\) og åtte verdier \(0.5-0.9=-0.4\). De opphever hverandre og gir summen 0, selv om bildene er forskjellige overalt.
Vi kvadrerer derfor alle verdiene i forskjellsbildet, summerer dem og tar kvadratroten. For et bilde \(D\) blir dette
\[ \lVert D\rVert=\sqrt{\sum_{i,j}D_{ij}^2}. \]
Kvadreringen gjør alle bidragene ikke-negative, slik at positive og negative forskjeller ikke kan kansellere hverandre. Tallet \(\lVert D\rVert\) kalles normen til \(D\): den numeriske avstanden fra \(D\) til nullbildet. Normen er 0 nøyaktig når alle pikselforskjellene er 0. Det er en avstand mellom pikselverdier, ikke nødvendigvis et mål på hvor forskjellige bildene oppleves av et menneske.
For en vektor summerer vi kvadratene av komponentene på samme måte. Cellen regner ut normen av inputforskjellen, først rett fra formelen og så med np.linalg.norm, og deretter normen av outputforskjellen.
De 16 inputforskjellene har alle absoluttverdi \(0.4\), så normen er \(\sqrt{16\cdot0.4^2}=1.6\). De to første utskriftene viser \(1.6\); den ene kan få en avrundingsrest langt ute i desimalene, for eksempel 1.6000000000000005. Outputforskjellen har norm 0. Senere gir avrundingsfeil ofte svært små normer i stedet for nøyaktig 0; da leser vi resultatet som «numerisk nær null».
Bildene er forskjellige, men transformasjonen gir samme output. Den bevarer gjennomsnittet i hver blokk, men ikke hvordan pikselverdiene er fordelt inne i blokken.
Transformasjonen arbeider blokk for blokk. I øvre venstre blokk i X2 er pikselverdiene \(0.1,0.9,0.9,0.1\). Summen er 2, og gjennomsnittet er derfor \(2/4=0.5\). Det samme skjer i de tre andre blokkene. I X1 er hver piksel allerede \(0.5\), så også der blir alle fire blokkgjennomsnittene \(0.5\).
Gå i dybden: de fire blokkene i sjakkbildet
Cellen klipper de fire \(2\times2\)-blokkene ut av X2 og skriver blokkgjennomsnittet over hver av dem.
Figuren viser de fire delene som ble klippet ut av X2, i samme leseretning som outputbildet: først øvre rad fra venstre mot høyre, deretter nedre rad. Ordet «gjennomsnitt» over hvert delbilde er tallet som plasseres i den tilsvarende outputpikselen. Alle fire tallene er \(0.5\), og outputen blir derfor et ensfarget \(2\times2\)-bilde.
Dette er ikke en avrundingsfeil: Gjennomsnittene er matematisk like. Transformasjonen er mange-til-én: flere forskjellige inputbilder kan havne på samme output, så fra outputen alene kan vi ikke avgjøre hvilket bilde som var input.
Resten av uka undersøker vi to egenskaper ved transformasjoner:
- Hva skjer når inputbilder skaleres og legges sammen? Dette leder til lineære transformasjoner.
- Hvilke endringer i inputen blir usynlige i outputen? Dette leder til nullrom, rang og dimensjon.
Før vi gir dette et matematisk navn, kan du prøve å endre X2 uten å endre gjennomsnittet i noen blokk. Hvilke endringer ser ut til å være tillatt?
Pikselverdiene i et bilde kan også legges etter hverandre i en liste. NumPy-funksjonen reshape(-1) leser øverste rad fra venstre mot høyre, deretter neste rad, og så videre. Cellen gjør dette med sjakkbildet X2 og tegner bildet og vektoren ved siden av hverandre.
Figuren viser de samme 16 tallene to ganger; de røde strekene markerer hvor en bilderad slutter. Ingen informasjon er borte. Vi har bare valgt en nummerering som gjør at vanlig matrise-vektor-multiplikasjon kan brukes.
Et \(4\times4\)-bilde beskrives dermed med 16 koordinater og kan behandles som en vektor \(x\in\mathbb R^{16}\). Bildetransformasjonen fra 3.1 kan nå skrives
\[y=Ax,\]
der \(A\) har fire rader og seksten kolonner. Hver rad i \(A\) lager én av de fire outputverdiene. Hver kolonne svarer til én av de 16 inputpikslene og samler virkningen den pikselen har på alle fire målingene.
Slik konstruerer vi matrisen fra en regel
Matrisen skal ikke gjettes. Vi bygger den direkte fra transformasjonen:
- Nummerer inputverdiene i samme rekkefølge som i vektoren \(x\).
- Skriv én formel for hver outputverdi.
- Koeffisientene i outputformel nummer \(i\) blir rad nummer \(i\) i \(A\).
For øvre venstre blokk er
\[y_1=\frac14x_1+\frac14x_2+\frac14x_5+\frac14x_6.\]
Derfor er første rad i \(A\)
\[\begin{bmatrix} \frac14&\frac14&0&0&\frac14&\frac14&0&0&0&0&0&0&0&0&0&0 \end{bmatrix}.\]
Andre rad bygges fra øvre høyre blokk, tredje rad fra nedre venstre og fjerde rad fra nedre høyre. En rad i \(A\) er altså alltid én måling, og slik bygger vi matrisen for enhver lineær transformasjon som er gitt ved formler eller målinger.
Det er nyttig å holde de to sidene fra hverandre:
\[ \underbrace{\mathbb R^{16}}_{\text{inputrom: store bilder}} \xrightarrow{\quad A\quad} \underbrace{\mathbb R^4}_{\text{outputrom: små bilder}}. \]
På venstre side av pilen står inputen \(x\) med 16 pikselverdier, på høyre side outputen \(y\) med fire blokkgjennomsnitt. Inputrommet kalles også definisjonsrommet, og outputrommet, der alle outputene ligger, kalles også verdirommet.
Den ferdige matrisen A_pool er bygd nøyaktig slik, rad for rad. Cellen gjør de to bildene fra 3.1 om til vektorer og regner ut \(Ax\) for hvert av dem.
Neste figur viser produktet: en \(4\times16\)-matrise ganger en 16-vektor gir en 4-vektor. Samme farge brukes på et bildeområde, inputverdiene, matrisraden og outputverdien.
Les én farge om gangen. Den blå matrisraden har fire ruter med \(1/4\) der de fire blå inputverdiene står, og nuller ellers. Rad ganger vektor gir derfor \(1/4\) av summen av de fire blå verdiene: den blå outputverdien.
De andre fargene gjør det samme for sine områder: én matrisrad gir én verdi i outputvektoren. Med sjakkbildet blir alle fire gjennomsnittene \(0.5\).
Skalering og addisjon
Tenk deg at et grafikkprogram bygger et stort bilde av flere lag, for eksempel en jevn bakgrunn og en tekstur. Koeffisienten foran hvert lag bestemmer hvor sterkt laget skal bidra, og lagene legges sammen piksel for piksel. Nå skal programmet også lage et lite forhåndsvisningsbilde. Da finnes det to naturlige arbeidsmåter:
- Sett sammen lagene i full størrelse, og bruk deretter transformasjonen \(T\) til å lage det lille bildet.
- Bruk \(T\) på hvert lag først, og sett deretter sammen de små resultatene.
Her er \(T\) blokkgjennomsnittet, altså \(y=Ax\). Det er ikke opplagt at de to arbeidsmåtene gir samme svar. Hvis de gjør det, kan hvert lag behandles for seg uten at sluttresultatet endres.
Vi bruker det jevne bildet \(X_1\) som bakgrunnslag og et tilfeldig bilde \(X_3\) som teksturlag. Med bidragene \(0.6X_1\) og \(0.4X_3\) gir de to rutene
\[ R_1=T(0.6X_1+0.4X_3) \qquad\text{og}\qquad R_2=0.6\,T(X_1)+0.4\,T(X_3). \]
Cellen lager \(X_3\), regner ut begge rutene og tegner dem i hver sin rad. Målet er å se om forskjellen \(R_1-R_2\) blir nullbildet.
Eksperiment – bland først eller transformer først?
- Kjør cellen og sammenlign \(R_1\) og \(R_2\).
- Bytt
alpha,betaeller frøet idefault_rng(3), og kjør igjen.
Hva viser forsøket? De to rutene gir samme småbilde: Forskjellen \(R_1-R_2\) er hvit (hvitt betyr 0) og har norm 0. Ett forsøk er likevel ikke et bevis, så vi ser på selve regelen.
Gå i dybden: slik leser du tabellen
Les tabellen fra venstre mot høyre. I øverste rad har de tre første bildene størrelse \(4\times4\): De to skalerte lagene legges sammen til \(S=0.6X_1+0.4X_3\), som så transformeres til det mindre resultatet \(R_1\). I nederste rad er transformasjonen allerede brukt på hvert lag. Derfor er alle bildene \(2\times2\), og de to første legges sammen til \(R_2\). Feltet nederst til høyre viser \(R_1-R_2\) med samme rød–blå skala som i 3.1. Det er hvitt fordi alle fire forskjellene er 0.
Hver outputpiksel er summen av fire inputverdier, alle ganget med \(1/4\). For øvre venstre outputpiksel og to inputvektorer \(x\) og \(z\) er
\[ \begin{aligned} &\tfrac14\big((\alpha x_1+\beta z_1)+(\alpha x_2+\beta z_2)+(\alpha x_5+\beta z_5)+(\alpha x_6+\beta z_6)\big)\\ &\qquad=\alpha\cdot\tfrac14(x_1+x_2+x_5+x_6)+\beta\cdot\tfrac14(z_1+z_2+z_5+z_6). \end{aligned} \]
Vi har bare sortert leddene: Både skaleringen og addisjonen kan flyttes inn eller ut av summen. Det samme gjelder de tre andre outputpikslene. Det gir den sentrale regneregelen for en lineær transformasjon:
\[A(\alpha x+\beta z)=\alpha Ax+\beta Az.\]
Her er \(x\) og \(z\) vilkårlige inputvektorer og \(\alpha,\beta\) vilkårlige tall: Både skalering og addisjon kan flyttes gjennom transformasjonen.
Et uttrykk som \(c_1b_1+\cdots+c_kb_k\) kalles en lineærkombinasjon av \(b_1,\ldots,b_k\): Vi skalerer hver byggestein og legger sammen. Linearitet er sentralt fordi vi kan forstå en komplisert input ved å dele den i enkle byggesteiner. Hvis \(x=c_1b_1+\cdots+c_kb_k\), trenger vi ikke analysere hele \(x\) på nytt:
\[Ax=c_1Ab_1+\cdots+c_kAb_k.\]
Vi kan altså finne hva transformasjonen gjør med hver byggestein én gang og deretter kombinere resultatene. Basis, nullrom og kolonnerom bygger alle på denne ideen. Ikke alle transformasjoner er lineære: å klippe alle negative pikselverdier til null eller å sortere pikslene vil for eksempel vanligvis bryte regneregelen.
Vi skal nå finne et systematisk språk for «byggesteiner». Tenk på et tomt \(2\times2\)-bilde og fire skyveknapper, én for hver piksel.
Dra i skyveknappene. Hver knapp skalerer ett lite byggesteinsbilde, og de fire delbildene legges sammen til bildet til høyre. Prøv å lage et helt svart bilde, et ensfarget grått bilde og et bilde med fire forskjellige gråtoner.
Appleten antyder to viktige egenskaper før vi bruker matematisk terminologi. Alle \(2\times2\)-bilder med pikselverdier mellom 0 og 1 kan lages ved å stille inn de fire kontrollene. Samtidig har hvert ferdig bilde bare én innstilling av kontrollene: Pikselverdiene bestemmer skyveknappene.
Ruten lengst til høyre viser blokkgjennomsnittet (0 er svart, 1 er hvitt). Når én piksel endres med \(\Delta\), endres gjennomsnittet med \(\Delta/4\). Denne regelen blir den lille transformasjonen i 3.4.
Byggesteinsbildet \(E_k\) har verdien 1 i piksel \(k\) og 0 i de tre andre pikslene. Startinnstillingen i appleten lager derfor bildet
\[X=\begin{bmatrix}0.2&0.7\\0.4&0.9\end{bmatrix}=0.2E_1+0.7E_2+0.4E_3+0.9E_4.\]
For eksempel bidrar \(0.7E_2\) bare med \(0.7\) i øvre høyre piksel, så hver piksel kan stilles inn uavhengig.
Gå i dybden: pikselbasisen i NumPy
Her gjentar vi appleten i NumPy. De fire første bildene har verdi 1 i hver sin piksel og 0 i de andre. Deretter blir hvert bilde ganget med ønsket pikselverdi, og de fire delbildene legges sammen.
De fire tallene foran byggesteinene kalles koordinater i denne beskrivelsen. Her er de nøyaktig de fire pikselverdiene i \(X\).
Er fire knapper akkurat riktig antall? Vi prøver to endringer: Først fjerner vi \(E_4\), så legger vi til \(E_5=E_1+E_2\), som er bygd av to andre. Cellen gjør begge forsøkene, ett i hver rad. Målet er å se hva som skjer med egenskapene «alle bilder kan lages» og «oppskriften er entydig».
Eksperiment – for få eller for mange byggesteiner?
- Kjør cellen og se hva som mangler når \(E_4\) er borte (øverste rad).
- Sammenlign de to oppskriftene med \(E_5=E_1+E_2\) (nederste rad).
- Bytt \(E_5\) med for eksempel \(E_3+E_4\), og endre
recipe_1slik at den lager det samme bildet med bare \(E_1,\ldots,E_4\).
Hva viser forsøket? Uten \(E_4\) er nedre høyre piksel null i enhver lineærkombinasjon, så ikke alle bilder kan lages. Med \(E_5\) i tillegg gir to forskjellige oppskrifter samme bilde, så oppskriften er ikke entydig. Det hjelper ikke å bytte ut \(E_5\): De fire pikselbildene lager allerede alle \(2\times2\)-bilder, så enhver femte byggestein kan bygges av dem, og da finnes det alltid to oppskrifter. En basis har akkurat nok byggesteiner: ingen hull og ingen overflødige byggesteiner.
- Byggesteinene spenner ut en samling bilder når alle bilder i samlingen kan bygges som lineærkombinasjoner av dem.
- Byggesteinene er lineært uavhengige når ingen av dem kan bygges av de andre. Da har hvert bilde høyst én oppskrift.
- En basis er et sett byggesteiner som både spenner ut hele samlingen og er lineært uavhengig: nok byggesteiner, men ingen overflødige.
Når vi trekker fra bilder eller skalerer mønstre, kan pikselverdiene bli negative eller større enn 1. Derfor regner vi i samlingen
\[\mathbb R^{2\times2},\]
som betyr «fire reelle tall ordnet som to rader og to kolonner». Den er et vektorrom: Objektene kan legges sammen og ganges med tall, og disse operasjonene følger de vanlige regnereglene. Et vektorrom trenger altså ikke å bestå av piler eller tallkolonner.
Gå i dybden: gyldige gråtonebilder og hele vektorrommet
Et vanlig gråtonebilde har pikselverdier mellom 0 og 1: 0 er svart og 1 er hvitt. Slike \(2\times2\)-bilder ligger i \([0,1]^{2\times2}\). Elementene i \(\mathbb R^{2\times2}\) kan regnes med som bilder, forskjellsbilder eller mønstre, selv om ikke alle kan vises direkte som vanlige gråtonebilder. Det er \(\mathbb R^{2\times2}\) som er et vektorrom; \([0,1]^{2\times2}\) er bare delen som består av gyldige gråtonebilder. For eksempel ligger \(E_1\) i \([0,1]^{2\times2}\), men \(-E_1\) gjør det ikke.
\(E_1,E_2,E_3,E_4\) danner en basis for \(\mathbb R^{2\times2}\). Dimensjonen er antallet byggesteiner i en basis, altså
\[\dim(\mathbb R^{2\times2})=4.\]
Dimensjon teller hvor mange uavhengige tall som trengs for å beskrive et bilde; det har ingenting med at bildet ser todimensjonalt ut å gjøre. Et \(4\times4\)-bilde ligger i et rom med dimensjon 16.
Bytt fra pikselbasis til mønsterbasis
Pikselkoordinatene sier bare hvor lyse de fire pikslene er. Vi prøver nå fire andre byggesteiner. I figurene betyr rødt positive verdier, blått negative verdier og hvitt null. Negative tall betyr at et mønster trekkes fra.
Appleten er bygd som pikselappleten, men skyveknappene styrer nå fire mønstre og går fra \(-1\) til \(1\). En negativ koeffisient legger til mønsteret med motsatt fortegn. Tallet i hver piksel viser det faktiske bidraget.
Startinnstillingen lager samme bilde som før, men med andre tall: lysnivå \(0.55\), venstre–høyre \(-0.25\), topp–bunn \(-0.10\) og sjakkmønster \(0\). Legg merke til at kontrastkontrollene endrer bildet, men ikke blokkgjennomsnittet; det forklarer vi i 3.4. Lysnivåkontrollen endrer derimot alle fire pikselverdiene og gjennomsnittet like mye.
Cellen lager de samme fire mønstrene i NumPy. Vi bruker dem resten av uka, og pikslene står i samme rekkefølge som før: øvre rad fra venstre mot høyre, deretter nedre rad.
Lysnivå har samme fortegn overalt og gjør hele bildet lysere eller mørkere. Venstre–høyre øker venstre kolonne samtidig som høyre kolonne minker. Topp–bunn sammenligner øvre og nedre rad. Sjakkmønster skiller de to diagonalene. De tre siste har to \(+1\) og to \(-1\), så summen deres er null.
Er de fire mønstrene en basis? Vi må svare på de samme to spørsmålene som for pikselbasisen: Kan de bygge alle målbilder, og er oppskriften entydig?
Fra en oppskrift til likningen \(Pc=t\)
Først tar vi en mindre versjon med bare to byggesteiner. La
\[b_1=\begin{bmatrix}1\\1\end{bmatrix},\qquad b_2=\begin{bmatrix}1\\-1\end{bmatrix}.\]
Hvis styrkene er \(c_1\) og \(c_2\), blir den ferdige vektoren
\[c_1b_1+c_2b_2 =\begin{bmatrix}1&1\\1&-1\end{bmatrix} \begin{bmatrix}c_1\\c_2\end{bmatrix}.\]
Matrisen oppstår altså ved å sette én byggestein i hver kolonne. Vil vi lage målet \(t=[2,0]^T\), får vi
\[ \underbrace{\begin{bmatrix}1&1\\1&-1\end{bmatrix}}_{P_2} \underbrace{\begin{bmatrix}c_1\\c_2\end{bmatrix}}_{c} = \underbrace{\begin{bmatrix}2\\0\end{bmatrix}}_{t}. \]
Radene sier \(c_1+c_2=2\) og \(c_1-c_2=0\). Legger vi sammen de to likningene, får vi \(2c_1=2\), altså \(c_1=1\); den andre likningen gir da \(c_2=c_1=1\). Vi kontrollerer ved å regne forover: \(1b_1+1b_2=[2,0]^T\). Dette lille eksemplet viser hele mekanismen: \(P\) inneholder kjente byggesteiner, \(t\) er det kjente målet, og \(c\) er den ukjente oppskriften.
For de fire \(2\times2\)-mønstrene gjør vi nøyaktig det samme. Først legger vi radene i hvert mønster etter hverandre:
\[ \begin{aligned} \operatorname{vec}(M)&=[1,1,1,1]^T,\\ \operatorname{vec}(H)&=[1,-1,1,-1]^T,\\ \operatorname{vec}(V)&=[1,1,-1,-1]^T,\\ \operatorname{vec}(D)&=[1,-1,-1,1]^T. \end{aligned} \]
Disse fire kjente vektorene blir kolonnene i
\[ P= \begin{bmatrix} 1& 1& 1& 1\\ 1&-1& 1&-1\\ 1& 1&-1&-1\\ 1&-1&-1& 1 \end{bmatrix}. \]
Koeffisientvektoren \(c=[c_M,c_H,c_V,c_D]^T\) inneholder styrken til de fire mønstrene. Produktet \(Pc\) er ikke et nytt abstrakt objekt: Det er de fire pikselverdiene i \(c_MM+c_HH+c_VV+c_DD\), skrevet radvis som en vektor.
Nå bruker vi det konkrete målbildet fra pikselbasis-eksemplet:
\[X=\begin{bmatrix}0.2&0.7\\0.4&0.9\end{bmatrix},\qquad t=\operatorname{vec}(X)=\begin{bmatrix}0.2\\0.7\\0.4\\0.9\end{bmatrix}.\]
Reverse engineering betyr at \(t\) er kjent, mens mønsterstyrkene i \(c\) er ukjente. Vi løser
\[ \underbrace{P}_{\substack{\text{kjente mønstre}\\4\times4}} \underbrace{c}_{\substack{\text{ukjente styrker}\\4\times1}} = \underbrace{t}_{\substack{\text{kjente målpiksler}\\4\times1}}. \]
Systemet \(Pc=t\) er fire likninger:
\[\begin{aligned}c_M+c_H+c_V+c_D&=0.2,\\ c_M-c_H+c_V-c_D&=0.7,\\ c_M+c_H-c_V-c_D&=0.4,\\ c_M-c_H-c_V+c_D&=0.9.\end{aligned}\]
Mønstrene er laget slik at vi kan legge sammen og trekke fra hele likninger. Legger vi sammen alle fire, faller \(c_H\), \(c_V\) og \(c_D\) bort: \(4c_M=0.2+0.7+0.4+0.9=2.2\), så \(c_M=0.55\). Med fortegnene \(+,-,+,-\) blir bare \(c_H\) igjen: \(4c_H=0.2-0.7+0.4-0.9=-1.0\), så \(c_H=-0.25\). På samme måte gir \(+,+,-,-\) og \(+,-,-,+\)
\[4c_V=0.2+0.7-0.4-0.9=-0.4,\quad c_V=-0.10,\qquad 4c_D=0.2-0.7-0.4+0.9=0,\quad c_D=0.\]
Tallene er de samme som startverdiene i appleten. Kontroll av første likning: \(0.55-0.25-0.10+0=0.20\).
Det er viktig å skille de to retningene:
| Retning | Kjent | Ukjent | Regneoperasjon |
|---|---|---|---|
| Bygg bildet | \(P\) og \(c\) | \(t\) | beregn P @ c |
| Reverse engineering | \(P\) og \(t\) | \(c\) | løs P @ c = t |
En løsning finnes for hvert målbilde akkurat når kolonnene i \(P\) spenner ut hele bilderommet. Løsningen er entydig akkurat når kolonnene er lineært uavhengige. Derfor gir en basis nøyaktig én koeffisientvektor \(c\) for hvert mål \(t\), og hver \(c\) gir nøyaktig ett bilde \(Pc\): Basisen fungerer som et koordinatsystem.
I prosjektet Polynomer i blindsonen er de kjente dataene polynomverdier \(p(x_0),\ldots,p(x_n)\), og de ukjente er polynomkoeffisientene. Reverse engineering er det samme: løs et lineært system for koeffisientene, og kontroller at de gjenskaper dataene.
Cellen gjentar regnestykket: column_stack bygger \(P\), matrix_rank teller pivotene, solve finner \(c\), og P @ c kontrollerer at oppskriften faktisk bygger målet.
Rangutskriften er 4: Alle fire kolonnene er pivotkolonner (pivoter repeteres i 3.7), så ingen mønsterkolonne kan bygges av de andre. Fire uavhengige mønstre i rommet \(\mathbb R^{2\times2}\), som har dimensjon 4, danner en basis. Mønsterkoordinatene er \([0.55,-0.25,-0.10,0]^T\) som i håndregningen, og summen av delbildene rekonstruerer \(X\) (feilen er null eller på størrelse med avrundingsfeil).
Pikselbasisen beskriver bildet med fire lokale lysverdier; mønsterbasisen beskriver det samme bildet som lysnivå pluss tre kontraster. Dette er et basisskifte: samme objekt, ny oppskrift.
En basis er ikke bare et sett som tilfredsstiller en definisjon. Et godt valg av basis kan skille egenskaper vi vil bevare fra egenskaper en transformasjon fjerner. Det er nettopp det som skjer i neste eksperiment.
Gå i dybden: fra byggesteiner til bildekompresjon
Valget av byggesteiner kan få praktisk betydning. Vanlige bilder inneholder ofte store jevne områder, langsomme overganger, kanter og gjentatte mønstre. Hvis byggesteinene passer til denne strukturen, kan bildet kanskje beskrives godt med noen få store koeffisienter og mange små.
Da kan de minste bidragene lagres mindre nøyaktig eller utelates. En mulig kompresjonsalgoritme får dermed denne formen:
- Del bildet opp i egnede mønsterbyggesteiner.
- Finn styrken til hver byggestein.
- Behold de viktigste bidragene.
- Rekonstruer et bilde som ligner originalen.
I uke 7 skal vi bruke singulærverdifaktorisering (SVD) til å konstruere en faktisk algoritme for bildekompresjon. Da arbeider vi med større bilder og beholder de delene som beskriver mest av strukturen i bildet.
I uke 3 er målet mindre, men grunnleggende: Vi analyserer små \(2\times2\)- og \(4\times4\)-bilder der alle byggesteiner, koeffisienter og transformasjoner kan sees direkte. De små bildeblokkene fungerer som en oversiktlig modell for ideene som senere skaleres opp i SVD-algoritmen.
Nå bruker vi matrisen og byggesteinene til å besvare to spørsmål:
- Hvilke inputendringer gir output null? Svaret er nullrommet.
- Hvor mange outputverdier kan styres uavhengig? Svaret er rangen.
Vi løser først problemet for én \(2\times2\)-blokk og bruker deretter samme argument fire ganger for hele \(4\times4\)-bildet.
Én blokk: transformasjonen \(4\to1\)
Legg de fire pikselverdiene i én \(2\times2\)-blokk i vektoren \(u=[u_1,u_2,u_3,u_4]^T\). Gjennomsnittet er
\[G(u)=\frac14(u_1+u_2+u_3+u_4) =\underbrace{\begin{bmatrix}\frac14&\frac14&\frac14&\frac14\end{bmatrix}}_{B}u.\]
Én outputverdi gir én rad i matrisen, som i 3.2. Cellen sender de fire mønstrene fra 3.3 gjennom \(G\), én om gangen. Fordi \(G\) er lineær, forteller resultatene også hva som skjer med enhver kombinasjon av dem.
Hver kolonne i tabellen er ett forsøk: øverst en blokk med fire pikselverdier, rett under den tilhørende \(1\times1\)-outputen. Lysnivåbildet har fire enere, så gjennomsnittet er 1. Hvert kontrastbilde har to enere og to minusenere; summen er 0, og gjennomsnittet er derfor 0.
Resultatene deler byggesteinene i to grupper. Transformasjonen registrerer lysnivåretningen, men sender hver kontrastretning til null. Fordi transformasjonen er lineær (se 3.2), har også enhver kombinasjon av kontrastbildene gjennomsnitt 0.
Kontrastmønstrene \(H,V,D\) kan legges til en blokk uten å endre gjennomsnittet. De er lineært uavhengige og har sum null: tre uavhengige retninger i nullrommet. Når tre av fire pikselverdier er valgt i en blokk med sum null, er den siste bestemt, så nullrommet har dimensjon 3. Den ene gjennomsnittsverdien kan velges fritt, så \(B\) har rang 1. Regnskapet er
\[4=\operatorname{rank}(B)+\dim N(B)=1+3.\]
Fra tidligere kurs i lineær algebra kjenner vi nullrommet som mengden av løsninger av et homogent likningssett. For en transformasjon \(A:\mathbb R^n\to\mathbb R^m\) er
\[N(A)=\{z\in\mathbb R^n:Az=0\}\subseteq\mathbb R^n.\]
Nullrommet kalles også kjernen til \(A\), og mange bøker skriver \(\ker A\) i stedet for \(N(A)\).
Nullrommet ligger i inputrommet: Vektorene der har like mange komponenter som en input. For én blokk ligger det i \(\mathbb R^4\), og med mønstrene skrevet som 4-vektorer er
\[N(B)=\operatorname{span}\{H,V,D\}.\]
Nullrommet er altså ikke bare selve nullbildet; det inneholder mange ikke-null blokker som denne ene blokkmålingen ikke registrerer.
Dette forklarer åpningsproblemet for én blokk. Hvis \(G(u_1)=G(u_2)\), har to blokker samme blokkgjennomsnitt. Vi kan trekke den ene outputen fra den andre, og linearitet gir \(G(u_1-u_2)=0\). Forskjellsblokken \(u_1-u_2\) ligger derfor i nullrommet. Omvendt kan vi legge enhver nullromsendring til en blokk uten å endre den ene outputverdien:
\[G(u_1)=G(u_2)\quad\Longleftrightarrow\quad G(u_1-u_2)=0.\]
Vi går nå langs én usynlig retning. Cellen starter med et jevnt grått bilde og legger til \(t\) ganger sjakkmønsteret for fem verdier av \(t\). Hvis sjakkmønsteret virkelig ligger i nullrommet, skal gjennomsnittet stå stille.
Pikslene endres med \(t\), men titlene viser at gjennomsnittet står på \(0.50\) i alle fem blokker. Nullrommet beskriver alle forskjeller mellom inputblokker som målingen ikke kan oppdage.
Fire blokker: transformasjonen \(16\to4\)
For hele \(4\times4\)-bildet bruker \(A_{\mathrm{pool}}\in\mathbb R^{4\times16}\) den samme raden \(B\) på fire blokker og lager ett blokkgjennomsnitt fra hver. Den tar altså ikke gjennomsnittet av alle 16 piksler samlet.
Når vi gjentar argumentet i hver blokk, får vi \(4\cdot3=12\) usynlige og \(4\cdot1=4\) synlige retninger.
Gå i dybden: alle tolv usynlige mønstre
Tabellen viser presist hvordan resultatene for én blokk overføres til hele bildet:
| Én blokk | Hele bildet |
|---|---|
| 4 inputpiksler | 4 blokker med 4 piksler, altså 16 inputpiksler |
| 1 gjennomsnitt | 1 gjennomsnitt per blokk, altså 4 outputverdier |
| matrisen \(B\) har størrelse \(1\times4\) | matrisen \(A_{\mathrm{pool}}\) har størrelse \(4\times16\) |
| nullitet 3 | tre lokale nullromsretninger i hver blokk: \(4\cdot3=12\) |
| rang 1 | én fritt valgbar output per blokk: \(4\cdot1=4\) |
Dermed kan hver blokk inneholde sine egne usynlige kontraster. Funksjonen place_in_block nedenfor plasserer \(H\), \(V\) eller \(D\) i én blokk og fyller resten av bildet med null. Fire plasseringer med tre kontrasttyper gir \(4\cdot3=12\) bilder.
Hvert bilde endrer bare de fire pikslene i én blokk. Positive og negative bidrag opphever hverandre, så blokkgjennomsnittet av endringene er null. De tre andre blokkene er allerede null. Dermed må alle fire blokkgjennomsnittene, og altså hele outputbildet, bli null for hvert av de tolv inputbildene.
Neste celle kontrollerer dette numerisk. Deretter velger den tolv tilfeldige koeffisienter, skalerer hvert kontrastbilde og legger alle sammen. Det sammensatte inputbildet ser uregelmessig ut, men hver blokk har fortsatt sum null.
For hvert mønster er \(Az\) et \(2\times2\)-outputbilde. Utskriften \(\lVert Az\rVert\) måler avstanden fra denne outputen til nullbildet. Verdiene er 0 (eller på størrelse med avrundingsfeil), så mønsteret forsvinner i transformasjonen.
Venstre felt i tabellen viser kombinasjonen av de tolv mønstrene. Høyre felt viser den mindre outputen etter blokkgjennomsnitt. Den er null i alle fire posisjoner. Koden viser dermed to ting: Hver lokal kontrast gir output null, og en tilfeldig lineærkombinasjon av dem gir fremdeles output null. Grunnen er linearitet, ikke at vi var heldige med koeffisientene.
De tolv byggesteinene påvirker enten forskjellige blokker eller forskjellige kontraster i samme blokk. Ingen av dem kan fjernes uten at vi mister en mulig lokal endring. Samtidig kan ethvert bilde der hver blokk har sum null bygges av dem, blokk for blokk.
Hvis \(Az_1=0\) og \(Az_2=0\), er også \(A(\alpha z_1+\beta z_2)=\alpha Az_1+\beta Az_2=0\). Nullrommet er altså en samling der vi kan addere bilder og multiplisere dem med tall uten å forlate samlingen. En slik lineær samling inni et større rom kalles et underrom. Vi trenger ingen nye regneregler; ordet beskriver bare at lineærkombinasjoner blir værende i samlingen.
De tolv lokale kontrastene (tre i hver blokk) danner en basis for nullrommet til \(A_{\mathrm{pool}}\), som derfor har dimensjon 12.
Matrisekolonnene og rangen
Nå finner vi rangen ved å spørre hva som kan produseres. Da bruker vi en annen måte å bygge en matrise på:
Kolonne \(j\) er outputen når inputen er \(e_j\), altså når inputverdi \(j\) er 1 og alle andre inputverdier er 0.
Gå i dybden: to måter å bygge matrisen på
For en regel som er oppgitt med outputformler, er radmetoden fra 3.2 raskest. For en ukjent regel vi kan teste — et typisk reverse-engineering-problem — kan vi sende inn \(e_1,e_2,\ldots,e_n\) og samle de observerte outputene som kolonner. De to metodene bygger den samme matrisen.
Klikk på en inputpiksel i figuren. Da får den pikselen verdien 1 og alle andre verdien 0; vi sier at vi slår på én piksel. Outputbildet til høyre viser hva transformasjonen gjør. Hvilke \(2\times2\)-bilder kan transformasjonen produsere?
Alle piksler med samme farge peker mot samme felt: Én påslått piksel gir blokkgjennomsnitt \(1/4\) i sin blokk og 0 i de andre. Klikk på flere piksler med samme farge etter tur; outputen blir den samme.
Her kommer forbindelsen til matrisen: Kolonne \(j\) i \(A\) er outputen vi får når bare inputpiksel \(j\) er slått på. Fire piksler som gir samme output, gir derfor fire identiske kolonner. Figuren viser på denne måten fire grupper av like kolonner, én gruppe for hver farge.
Gå i dybden: kolonnene som bilder
La \(f_1,f_2,f_3,f_4\) være pikselbasisen i outputrommet \(\mathbb R^4\). Forsøkene gir konkret
\[ \begin{aligned} a_1=a_2=a_5=a_6&=\tfrac14 f_1,\\ a_3=a_4=a_7=a_8&=\tfrac14 f_2,\\ a_9=a_{10}=a_{13}=a_{14}&=\tfrac14 f_3,\\ a_{11}=a_{12}=a_{15}=a_{16}&=\tfrac14 f_4. \end{aligned} \]
Her er \(a_j\) kolonne \(j\) i \(A_{\mathrm{pool}}\). Den første linjen sier for eksempel at hver av pikslene 1, 2, 5 og 6 påvirker bare øvre venstre outputpiksel, og påvirker den med vekten \(1/4\). Dette er den samme matrisen som vi bygde radvis i 3.2, men nå er den funnet ved å teste transformasjonen på én inputretning om gangen. Slik kan matrisen reverse-engineeres selv om vi ikke kjenner den interne oppskriften til transformasjonen.
Koden nedenfor utfører alle de 16 forsøkene på én gang og tegner hver matriskolonne som et lite \(2\times2\)-bilde.
De 16 små bildene bekrefter det vi så i appleten: Kolonnene kommer i fire grupper. Innenfor hver gruppe er outputbildene identiske. Derfor gir flere kolonner i samme gruppe ingen ny måte å endre outputen på. Fra én gruppe til den neste flytter den eneste outputpikselen som ikke er null, seg til en ny plass.
Velg én representant fra hver gruppe, for eksempel kolonne 1, 3, 9 og 11. Hver av dem har verdien \(1/4\) på én outputplass og 0 på de tre andre, og plassene er forskjellige. Ingen av dem kan derfor bygges av de tre andre: De fire representantene er lineært uavhengige.
De spenner også ut hele outputrommet. For å lage en ønsket output \(y=[y_1,y_2,y_3,y_4]^T\) kan vi for eksempel sette inputpikslene 1, 3, 9 og 11 lik \(4y_1,4y_2,4y_3,4y_4\) og la alle andre inputpiksler være null.
Gå i dybden: en oppskrift for enhver output
En annen, mer bildelik oppskrift er å fylle hver blokk med den ønskede outputverdien. Koden nedenfor bruker denne oppskriften og kontrollerer den på fire tilfeldige målbilder.
Les hver forsøksrad fra venstre mot høyre. Først vises et konstruert \(4\times4\)-inputbilde. I midten står \(2\times2\)-outputen vi ba om, og til høyre står \(2\times2\)-outputen transformasjonen faktisk beregnet. De to små bildene er identiske i alle fire forsøk.
Målbildene ble valgt tilfeldig, men den samme oppskriften virker for alle \(2\times2\)-bilder: kopier hver ønsket outputverdi inn i alle fire pikslene i den tilsvarende inputblokken. Gjennomsnittet av fire like verdier er denne verdien selv. Feilen er derfor nøyaktig null, bortsett fra eventuell avrunding. Transformasjonen kan altså produsere alle vektorer i \(\mathbb R^4\).
Fra tidligere kjenner vi samlingen av alle outputvektorer en matrise kan produsere som kolonnerommet. For hele bildereduksjonen skriver vi
\[\operatorname{Col}(A_{\mathrm{pool}}) =\{A_{\mathrm{pool}}x:x\in\mathbb R^{16}\}\subseteq\mathbb R^4.\]
Kolonnerommet ligger i outputrommet og består av 4-vektorer, mens nullrommet består av 16-vektorer.
Navnet kan nå leses direkte fra eksperimentet. Hvis \(a_j\) er kolonne \(j\) i \(A_{\mathrm{pool}}\), er
\[A_{\mathrm{pool}}x=x_1a_1+\cdots+x_{16}a_{16}.\]
Inputverdien \(x_j\) skalerer kolonnen \(a_j\), og bidragene legges sammen: Alle outputer er lineærkombinasjoner av kolonnene.
For å beskrive kolonnerommet holder det å beholde kolonnene 1, 3, 9 og 11, én fra hver gruppe; de andre tolv er kopier.
Rangen er dimensjonen til kolonnerommet:
\[\operatorname{rank}(A_{\mathrm{pool}}) =\dim\operatorname{Col}(A_{\mathrm{pool}}).\]
Rangen er derfor 4. Det kan vi begrunne på tre likeverdige måter:
- Vi har funnet fire lineært uavhengige matriskolonner.
- Disse fire kolonnene spenner ut hele det firedimensjonale outputrommet.
- Gauss-eliminasjon gir fire pivoter, én for hver kolonnegruppe.
Rangen teller verken kolonnene (16) eller outputplassene (4), men de uavhengige outputretningene kolonnene kan bygge. Den kan aldri bli større enn antallet kolonner eller antallet rader: Hver pivot trenger sin egen kolonne og sin egen rad. For en annen \(4\times16\)-matrise kunne rangen vært mindre dersom noen målinger var avhengige av de andre.
Gå i dybden: NumPy teller det samme
Til slutt lar vi NumPy telle det samme. matrix_rank er bare en kontroll; begrunnelsen er de fire uavhengige kolonnene over.
Gå i dybden: en overflødig femte måling
Her kan du kontrollere at flere outputtall ikke nødvendigvis betyr mer informasjon. Vi legger til gjennomsnittet av alle de 16 inputpikslene som en femte måling. Den nye outputverdien ser først ut som ny informasjon, men den kan beregnes fra de fire blokkgjennomsnittene. Cellen regner ut de fem målingene for et tilfeldig bilde og sammenligner rangen med og uten den nye raden.
Utskriften viser at den femte outputverdien er gjennomsnittet av de fire første; noen ganger skiller tallene seg bare med en avrundingsrest i siste desimal. Matrisen har nå fem rader, men den femte målingen gir ingen ny justeringsmulighet og ingen ny informasjon om inputen. Den er bestemt av de fire andre, så rangen er fortsatt 4. Det samme skjer i prosjektet når et avlesningspunkt gjentas: Den nye raden er en kopi av en gammel og kan ikke øke rangen.
Seksten knapper, men bare fire når fram
Nå beskriver vi det samme inputbildet med 16 nye skyveknapper: fire fargede for blokkgjennomsnittene og tolv grå for kontrastene inne i blokkene (c1–c3 hører til øvre venstre blokk, c4–c6 til øvre høyre, c7–c9 til nedre venstre og c10–c12 til nedre høyre). Prøv begge typer: De fargede endrer både inputbildet og outputen, mens de grå bare endrer inputbildet.
Her regner vi i hele bilderommet: pikselverdier kan være mindre enn 0 eller større enn 1. Bare fargeskalaen klippes til svart–hvitt; tallene og blokkgjennomsnittet klippes ikke. En melding under inputbildet viser når fargeskalaen ikke kan vise hele variasjonen.
Å bevege én knapp mens de andre står stille, kaller vi å bevege oss i én retning. De tolv grå knappene styrer kontrastmønstre som danner en basis for nullrommet. De fire fargede knappene styrer fire inputmønstre som er konstante i hver sin blokk. Disse fire mønstrene og de tolv kontrastene danner til sammen en basis for inputrommet. Outputene til de fire konstante mønstrene danner en basis for kolonnerommet. Til sammen har inputrommet 16 uavhengige retninger:
\[16=4+12.\]
For en matrise med \(n\) kolonner sier rang-nullitet at
\[n=\operatorname{rank}(A)+\dim N(A).\]
Prosjektet skriver det samme med kjernen og det norske ordet rang: \(\dim(\ker A)+\operatorname{rang}(A)=n\).
Svar på ukens spørsmål. Blokkgjennomsnittet mister nøyaktig det som ligger i nullrommet: de tolv kontrastene inne i blokkene. Det den beholder, telles av rangen: fire uavhengige blokkgjennomsnitt. Regnskapet \(16=4+12\) er fullstendig. Nulliteten 12 teller inputretninger som sendes til null, og rangen 4 teller outputretninger som kan lages: to forskjellige typer retninger i to forskjellige rom, som til sammen gjør rede for alle 16 inputdimensjonene. To inputer gir samme output akkurat når forskjellen deres ligger i nullrommet. Hvis nullrommet bare inneholder nullvektoren, går ingenting tapt, og inputen kan finnes igjen fra outputen. Det er dette du bruker i prosjektet når du skal finne et polynom igjen fra noen få avlesninger.
Vil du øve på rang og nullrom med papir og blyant? Se selvtesten i 3.8.
Så langt har vektorene vært bilder eller tallkolonner. Nå bruker vi de kjente begrepene på polynomer. Dette er overgangen til ukeprosjektet.
| I bildeeksemplet | For polynomer |
|---|---|
| Pikselverdier | Polynomkoeffisienter |
| Basisbilder | Basispolynomer |
| Samme bilde i to basiser | Samme polynom i to basiser |
| Matrisemåling \(Ax\) | Avlesning av polynomverdier \(E(p)\) |
| En usynlig bildeendring | Et polynom som er null i avlesningspunktene |
| Rekonstruksjon fra output | Reverse engineering fra polynomverdier |
I 3.3 så vi at et vektorrom ikke trenger å bestå av piler eller tallkolonner: Objektene må kunne legges sammen og ganges med tall, med de vanlige regnereglene. Polynomer er et viktig eksempel.
Polynomer som vektorer
Vi begynner med polynomer av grad høyst 2. For et polynom som ikke er null, er graden den høyeste potensen av \(x\) som har en koeffisient forskjellig fra null. Polynomet \(3-x+x^2\) har for eksempel grad 2.
\[ \mathcal P_2=\{a+bx+cx^2:a,b,c\in\mathbb R\}. \]
Dette er et vektorrom. Vektorene er nå polynomer, og vi regner ved å samle ledd med samme potens av \(x\). For eksempel, hvis
\[p(x)=1+2x,\qquad q(x)=3-x+x^2,\]
så er
\[ p+q=4+x+x^2, \qquad 2p-q=(2+4x)-(3-x+x^2)=-1+5x-x^2. \]
Et uttrykk som \(2p-q\) er en lineærkombinasjon av \(p\) og \(q\), akkurat som for bilder i 3.2: Vi ganger hvert polynom med et tall og legger resultatene sammen.
Fra polynom til tallkolonne
Hvert polynom i \(\mathcal P_2\) kan bygges på nøyaktig én måte av de tre polynomene
\[1,\qquad x,\qquad x^2.\]
For eksempel er
\[4-2x+3x^2=4\cdot1+(-2)\cdot x+3\cdot x^2.\]
Tallene foran byggesteinene samles i en koordinatvektor:
\[ 4-2x+3x^2 \quad\longleftrightarrow\quad \begin{bmatrix}4\\-2\\3\end{bmatrix}. \]
Den ordnede samlingen \((1,x,x^2)\) kalles en basis for \(\mathcal P_2\). Fordi dette er det enkleste og vanligste valget, kalles den ofte standardbasisen, monomialbasisen eller potensbasisen. De tre navnene viser her til den samme ordnede listen. Ordet «standard» betyr ikke at dette er den eneste mulige basisen.
Rekkefølgen bestemmer hvor tallene skal stå: konstantleddet øverst, deretter koeffisienten til \(x\), så koeffisienten til \(x^2\). Hvis en potens mangler, er koeffisienten null. Vi kan også gå motsatt vei: Koordinatvektoren forteller hvilke tall som skal stå foran \(1\), \(x\) og \(x^2\).
Øv på dette: polynomregning og koordinater.
Hva gjør en samling til en basis?
Kravene er de samme som for bilder i 3.3: En basis spenner ut rommet (ingen hull: hvert polynom er en lineærkombinasjon av basispolynomene) og er lineært uavhengig (ingen overflødige byggesteiner). Samlingen \((1,x,x^2)\) er en basis for \(\mathcal P_2\). Samlingen \((1,x,1+x)\) er ikke en basis for \(\mathcal P_2\): Den mangler en byggestein for \(x^2\), og dessuten er \(1+x\) summen av de to første polynomene.
Slike påstander kan vi kontrollere med en matrise. Skriv hvert polynom som en koeffisientkolonne i basisen \((1,x,x^2)\), og sett kolonnene ved siden av hverandre:
\[\underbrace{\begin{bmatrix}1&0&1\\0&1&1\\0&0&0\end{bmatrix}}_{(1,\;x,\;1+x)} \qquad \underbrace{\begin{bmatrix}1&0&0\\1&1&0\\0&0&1\end{bmatrix}}_{(1+x,\;x,\;x^2)}.\]
Trappeform og pivoter repeteres i 3.7. Den første matrisen står allerede på trappeform. Den har to pivoter, så rangen er 2: Tredje kolonne er overflødig (\(1+x=1\cdot1+1\cdot x\)), og nederste rad er null, så ingen kombinasjon gir \(x^2\). I den andre matrisen trekker vi rad 1 fra rad 2 og får
\[\begin{bmatrix}1&0&0\\0&1&0\\0&0&1\end{bmatrix}.\]
Det er tre pivoter, så rangen er 3. Kaller vi den andre matrisen \(Q\), er koeffisientkolonnen til kombinasjonen \(b_1(1+x)+b_2x+b_3x^2\) nettopp \(Qb\). Kombinasjonen er nullpolynomet akkurat når \(Qb=0\). Alle tre kolonnene har en pivot, så systemet har ingen frie variabler, og \(b=0\) er eneste løsning: De tre polynomene er lineært uavhengige. Denne kontrollen kaller vi en rangtest.
Rommet \(\mathcal P_n\) har basisen \((1,x,\ldots,x^n)\) med \(n+1\) polynomer, så \(\dim\mathcal P_n=n+1\). Tre uavhengige polynomer i \(\mathcal P_2\), som har dimensjon 3, danner derfor en basis.
Altså er også
\[\mathcal B=(1+x,\ x,\ x^2)\]
en basis for \(\mathcal P_2\). Hvilke koordinater har \(2-x+3x^2\) i denne basisen? Vi søker \(c_1,c_2,c_3\) med \(c_1(1+x)+c_2x+c_3x^2=2-x+3x^2\). Venstre side er \(c_1+(c_1+c_2)x+c_3x^2\). Vi sammenligner koeffisientene til \(1\), \(x\) og \(x^2\): \(c_1=2\), \(c_1+c_2=-1\) og \(c_3=3\). Dermed er \(c_2=-3\), og
\[2-x+3x^2=2(1+x)-3x+3x^2,\qquad [\,2-x+3x^2\,]_{\mathcal B}=\begin{bmatrix}2\\-3\\3\end{bmatrix}.\]
Samme polynom har altså koordinatene \((2,-1,3)\) i potensbasisen og \((2,-3,3)\) i basisen \(\mathcal B\).
Øv på dette: rangtest, basis og koordinater.
En samling polynomer der vi kan addere og multiplisere med tall uten å forlate samlingen, er et underrom av \(\mathcal P_n\), akkurat som nullrommet i 3.4. Mengden av alle lineærkombinasjoner av noen polynomer, \(\operatorname{Span}(p_1,\ldots,p_k)\), er et slikt underrom. Øv på dette: polynomunderrom.
Polynomverdier som målinger
I bildeeksemplet var hver output en måling, og hver rad i \(A\) sa hvilke piksler målingen bruker. For et polynom er en naturlig måling å lese av verdien i et punkt. Ta \(p(x)=a_0+a_1x+a_2x^2\) og les av i \(x=-1\), \(0\) og \(1\):
\[\begin{aligned} p(-1)&=a_0-a_1+a_2,\\ p(0)&=a_0,\\ p(1)&=a_0+a_1+a_2. \end{aligned}\]
Koeffisientene foran \(a_0,a_1,a_2\) blir radene, akkurat som i 3.2:
\[\begin{bmatrix}p(-1)\\p(0)\\p(1)\end{bmatrix} =\begin{bmatrix}1&-1&1\\1&0&0\\1&1&1\end{bmatrix} \begin{bmatrix}a_0\\a_1\\a_2\end{bmatrix}.\]
Hver rad inneholder verdiene av \(1,x,x^2\) i ett punkt. For \(p(x)=4-2x+3x^2\) gir produktet \([9,4,5]^T\). Kontroll: \(p(-1)=4+2+3=9\), \(p(0)=4\) og \(p(1)=4-2+3=5\). Avlesningen er en lineær avbildning \(E\) fra \(\mathcal P_2\) til \(\mathbb R^3\) (her står \(E\) for avlesning, ikke for pikselbildene \(E_k\) fra 3.3): Definisjonsrommet er \(\mathcal P_2\) og verdirommet er \(\mathbb R^3\). Å gå baklengs, fra de tre verdiene til koeffisientene, er å løse dette systemet: reverse engineering som i 3.3. Hva må rangen være for at det skal finnes nøyaktig én løsning? Det spørsmålet møter du i prosjektet.
Øv på dette: avlesningsmatriser og dimensjon.
Polynomrom krever altså ingen ny type lineær algebra. Vi bruker de samme begrepene som for tallkolonner: lineærkombinasjon, spenn, lineær uavhengighet, basis, koordinater og rang.
I prosjektet Polynomer i blindsonen går vi videre fra koeffisienter til målinger. Vi får verdiene \(p(x_0),\ldots,p(x_n)\) og gjør reverse engineering: Hvilke koeffisienter kan ha produsert disse verdiene? Bildeeksemplene har allerede gitt oss de sentrale spørsmålene: Hvilken basis bruker vi, hvilken informasjon mister målingen, og kan små endringer være nesten usynlige? Del 2 og finalen i prosjektet handler også om avrundingsfeil og kansellering; disse temaene kan du repetere i uke 1.
Denne delen er egenarbeid. Nå går vi tilbake til bildetransformasjonen fra 3.1–3.4, og du skal selv konstruere, teste og forklare transformasjoner. Oppgavene om polynomer fra 3.5 står til slutt i denne delen.
Hjelpefunksjonene, transformasjonen og mønsterbildene fra de foregående delene er tilgjengelige under. Her skal du endre kode og lete etter mønstre selv.
Aktivitet A og oppgavene i Øv på polynomer anbefales: A øver på nullromssteget i prosjektets del 1, og oppgavene øver på rangtesten og avlesningsmatrisene. Aktivitet B–E er valgfrie; E er en numerisk fordypning. For hvert valgt eksperiment arbeider du i denne rekkefølgen:
- Gjett først hva figuren eller outputen vil vise.
- Kjør eksperimentet og beskriv det du faktisk ser.
- Kontroller observasjonen med et tall, for eksempel en residual (uke 2) eller en rang.
- Forklar til slutt observasjonen med begrepene fra uka.
Startcellene tar seg av figurer og utskrifter, men gir ikke ferdige svar. Et forsøk som ikke virker ved første kjøring, kan også være nyttig: Undersøk forskjellen mellom det du forventet og det koden faktisk produserte.
Anbefalt A: Lag et nytt mønster med output null
Endre Z. Hver \(2\times2\)-blokk skal ha gjennomsnitt null, men bruk ikke sjakkmønsteret uendret. Før du kjører cellen, regn ut minst ett blokkgjennomsnitt for hånd. Figuren viser om mønsteret forsvinner, mens normen under figuren måler outputens avstand fra nullbildet.
Legg deretter en liten versjon av mønsteret til et vanlig bilde. Velg størrelsen slik at pikselverdiene fortsatt ligger mellom 0 og 1. Vis originalbildet, det endrede bildet og begge outputene. Forklar både hvorfor inputbildene er forskjellige og hvorfor transformasjonen ikke kan skille dem.
Valgfri B: Hva kan tre byggesteiner lage?
Velg tre mønsterbilder og generer åtte tilfeldige lineærkombinasjoner. Se etter en egenskap som går igjen i alle bildene: finnes det for eksempel en symmetri, en fast sum eller en type kontrast som aldri opptrer? Bytt deretter ut én byggestein og se hvilken ny variasjon som blir mulig.
Forsøk å lage et konkret \(2\times2\)-målbilde som de tre byggesteinene ikke kan treffe. Dette er den eksperimentelle siden av dimensjon: tre uavhengige justeringsmuligheter kan ikke styre fire uavhengige pikselverdier.
Valgfri C: Lag en annen basis
Cellen starter med pikselbasisen som byggesteiner. Bytt ut minst to av bildene. Prøv gjerne først et valg der ett bilde kan bygges av de andre. Observer hva rangen blir og om likningssettet kan løses. Endre deretter byggesteinene til rangen blir 4; da skal fire koeffisienter kunne styre de fire pikselverdiene uavhengig.
Valgfri D: Design en ny bildereduksjon
Lag en lineær transformasjon fra 16 inputpiksler til høyst 6 outputverdier. Hver rad i A_new er én måling av bildet. Tegn først hvilke piksler målingen skal bruke, og sett så inn de tilsvarende vektene i raden. Mulige ideer er radgjennomsnitt, kolonnegjennomsnitt, diagonalsummer eller utvalgte piksler.
Test flere bilder med tydelig struktur, ikke bare det tilfeldige bildet. Finn deretter et ikke-null bilde som transformasjonen sender til null. Vis dette bildet og outputen ved siden av hverandre. Forklar hva hver rad i matrisen måler, og hvilke bildeendringer som derfor ikke registreres.
Valgfri fordypning E: Nesten samme måling
To målinger kan være matematisk forskjellige, men så like at maskinen får problemer med å skille dem. Vi begynner med å tegne vektene i de to målingene. Den første summerer alle piksler likt. Den andre gir bare den siste pikselen en ørliten ekstra vekt.
Forskjellsbildet har bare én ikke-null piksel. Gjør nå denne forskjellen mindre ved å endre eps, og sammenlign hva som skjer når tallene lagres som float64 og float32.
På papiret er målingene uavhengige for enhver \(\varepsilon\neq0\): den lille ekstravekten kan ikke lages ved bare å skalere den første raden. I maskinen kan ekstravekten bli avrundet bort, eller bli vurdert som for liten til å være pålitelig. matrix_rank bruker derfor en toleranse og rapporterer en numerisk rang. Beskriv når de to tallformatene slutter å skille målingene, og knytt resultatet til flyttallene fra uke 1 og toleransebegrepet fra uke 2.
Trenger du en repetisjon av eksakt og numerisk rang, kan du åpne boksen «Eksakt og numerisk rang» i 3.7. I prosjektets del 3 møter du samme idé: en endring som avlesningene nesten ikke ser.
Øv på polynomer
Oppgavene øver på 3.5. Arbeid på papir først og skriv svarene eksakt, for eksempel 1/3 og ikke 0.333.
Polynomer som vektorer
Bruk de samme polynomene som i 3.5, \(p(x)=1+2x\) og \(q(x)=3-x+x^2\), men en annen lineærkombinasjon.
Leddene i polynomet under står ikke i samme rekkefølge som basisen \((1,x,x^2)\). Pass på hvor hvert tall skal stå.
Et polynom \(r\) har koordinatvektoren \([r]_{(1,x,x^2)}=\begin{bmatrix}-1\\2\\3\end{bmatrix}\).
Rangtest, basis og koordinater
Polynomene \(1+x\), \(x+x^2\) og \(1-x^2\) ligger i \(\mathcal P_2\). Skriv dem som kolonner i en koeffisientmatrise og radreduser.
Bruk basisen \(\mathcal B=(1+x,x,x^2)\) og samme framgangsmåte som for \(2-x+3x^2\) i 3.5: Sammenlign koeffisientene til \(1\), \(x\) og \(x^2\).
Når basisen skifter, skifter koordinatene, selv om polynomet er det samme. I \(\mathcal P_2\) bruker vi nå basisen \(\mathcal C=(p_1,p_2,p_3)\), der
\[ p_1=x^2-2,\qquad p_2=-x^2+x+2,\qquad p_3=3x^2+x-5. \]
Å finne \([q]_{\mathcal C}\) betyr å finne tall \(c_1,c_2,c_3\) slik at \(q=c_1p_1+c_2p_2+c_3p_3\). Sammenligner vi koeffisientene til \(1\), \(x\) og \(x^2\) på begge sider, får vi et vanlig lineært likningssett for \(c_1,c_2,c_3\).
Et polynom i \(\mathcal P_3\) skrives som \(a_0+a_1x+a_2x^2+a_3x^3\). I en koeffisientmatrise representerer hver kolonne ett polynom. Radene inneholder koeffisientene til henholdsvis \(1,x,x^2,x^3\).
En basis består av polynomer som er lineært uavhengige og som spenner ut hele det etterspurte rommet. Basisvektorene kan stå i hvilken som helst rekkefølge. Røde kolonner er null eller ligger utenfor rommet. Hvis de gyldige kolonnene er lineært avhengige, farges hele familien gul. En grønn familie er gyldig og uavhengig, men kan fortsatt være for liten til å spenne ut hele rommet.
I rommet
\[ \mathcal P_3=\{a_0+a_1x+a_2x^2+a_3x^3:a_i\in\mathbb R\} \]
kan vi bruke andre basispolynomer enn \(1,x,x^2,x^3\). I svarmatrisen under er hver kolonne ett polynom. Du bestemmer selv hvor mange kolonner som trengs.
Polynomunderrom
Vi begynner med noen polynomer og undersøker alle lineærkombinasjonene de kan lage. La
\[ \begin{aligned} p_1&=1+x, & p_2&=x+x^2,\\ p_3&=1+x^2+x^3, & p_4&=2-x-x^2+x^3. \end{aligned} \]
Notasjonen \(\operatorname{Span}\) betyr «alle lineærkombinasjoner». Mengden \(U=\operatorname{Span}(p_1,p_2,p_3,p_4)\) består derfor av alle polynomer som kan bygges av \(p_1,p_2,p_3,p_4\). Dette er et underrom av \(\mathcal P_3\), og det inneholder nullpolynomet. En basis for \(U\) kan bestå av noen av polynomene over, eller av andre polynomer som spenner ut nøyaktig det samme rommet.
Avlesningsmatriser og dimensjon
Et polynom \(p(x)=a_0+a_1x+a_2x^2\) i \(\mathcal P_2\) leses av i bare to punkter, \(x=1\) og \(x=2\). Avlesningen gir \(E(p)=\begin{bmatrix}p(1)\\p(2)\end{bmatrix}\). Skriv avlesningsmatrisen \(A\) slik at \(E(p)=A\begin{bmatrix}a_0\\a_1\\a_2\end{bmatrix}\), og bruk rang–nullitet.
Dimensjonen til et polynomrom er antallet polynomer i en basis. La \(U=\{a_0+a_2x^2+a_4x^4\}\) være polynomene i \(\mathcal P_4\) som bare har partallspotenser.
Denne delen repeterer radreduksjon fra Matematikk 1: radoperasjoner, likningssett og Gauss-eliminasjon. Den er med slik at du ikke trenger å finne fram gamle notater. Det er en stund siden, så vi forventer ikke at framgangsmåten sitter friskt. Regningen vises steg for steg og kobles til ordene vi bruker nå: pivot, rang, kolonnerom og nullrom. Kan du allerede radredusere en matrise, finne pivotkolonner og beregne en basis for nullrommet, kan du nøye deg med å åpne underdelen du vil slå opp.
Bruk spørsmålene som en rask selvtest:
- Kan du radredusere en matrise og finne pivotkolonnene?
- Vet du hvorfor en kolonneromsbasis hentes fra den opprinnelige matrisen?
- Kan du skrive løsningene av \(Ax=0\) ved hjelp av frie variabler?
- Kan du finne en basis for nullrommet og kontrollere rang–nullitet?
- Kan du avgjøre om \(Ax=b\) har en løsning?
Hvis svaret er ja på alle fem, kan du gå til papir- og kontrolloppgavene i 3.8 dersom du ønsker ekstra trening, eller avslutte siden her.
Bildene i hovedløpet gjorde begrepene synlige. I støtteløpet legger vi bort bildebakgrunnen og regner direkte med én matrise. Målet er å repetere hvordan vi finner rang, basis for kolonnerommet og basis for nullrommet — først med papir og blyant, deretter med kode som kontroll.
Vi bruker samme matrise gjennom hele eksemplet:
\[ A= \begin{bmatrix} 1&2&0&1\\ 0&1&1&1\\ 1&3&1&2 \end{bmatrix}. \]
Matrisen har fire kolonner og tre rader, og beskriver derfor transformasjonen
\[ A:\underbrace{\mathbb R^4}_{\text{inputrom}} \longrightarrow \underbrace{\mathbb R^3}_{\text{outputrom}}. \]
Nullrommet består av 4-vektorer og ligger i inputrommet: \(N(A)\subseteq\mathbb R^4\). Kolonnerommet består av 3-vektorer og ligger i outputrommet: \(\operatorname{Col}(A)\subseteq\mathbb R^3\). Vi vil svare på tre spørsmål:
- Hvor mange uavhengige outputretninger har transformasjonen?
- Hvilke inputretninger gir output null?
- Kan en gitt vektor \(b\) produseres som \(Ax\)?
Vi bruker de samme fargene gjennom hele regningen:
| Farge | I eliminasjonen | Senere i regningen |
|---|---|---|
| 🟦 Blå | første pivot, kolonne 1 | basisvektor \(a_1\) og pivotvariabel \(x_1\) |
| 🟧 Oransje | andre pivot, kolonne 2 | basisvektor \(a_2\) og pivotvariabel \(x_2\) |
| 🟩 Grønn | kolonne uten pivot | fri variabel \(x_3=s\) og første nullromsretning |
| 🟪 Lilla | kolonne uten pivot | fri variabel \(x_4=t\) og andre nullromsretning |
Trekk første rad fra tredje rad. Sammenlign deretter den nye tredje raden med andre rad, og eliminer én gang til. Marker den første ikke-null-oppføringen i hver ikke-null-rad.
Regningen blir
\[ \begin{bmatrix} 1&2&0&1\\ 0&1&1&1\\ 1&3&1&2 \end{bmatrix} \longrightarrow \begin{bmatrix} 1&2&0&1\\ 0&1&1&1\\ 0&1&1&1 \end{bmatrix} \longrightarrow \begin{bmatrix} \color{#277da1}{\boxed{1}}&2&0&1\\ 0&\color{#d98900}{\boxed{1}}&1&1\\ 0&0&0&0 \end{bmatrix}. \]
Den siste raden er null og inneholder derfor ingen ny likning. To ikke-null-rader er igjen, og de ledende oppføringene — pivotene — ligger i kolonne 1 og 2. Dermed er rangen 2.
Koden under utfører vanlig framovereliminasjon. Den går fra venstre mot høyre og bruker den første tilgjengelige ikke-null-oppføringen som pivot. Dette er tilstrekkelig for eksemplene våre og følger papirregningen tett.
matrix_rank er nyttig som kontroll, men eliminasjonen viser hvorfor rangen er 2. Mer robuste eliminasjonsalgoritmer kan bytte om rader og eventuelt kolonner for å unngå dårlige pivoter. Det ser vi ikke på her. Senere skal vi se at numerisk rang alltid avhenger av hva som regnes som «tilstrekkelig nær null».
Pivotene forteller hvilke opprinnelige kolonner som tilfører en ny outputretning. Vi henter derfor kolonne 1 og 2 fra den opprinnelige matrisen:
\[ \color{#277da1}{a_1=\begin{bmatrix}1\\0\\1\end{bmatrix}}, \qquad \color{#d98900}{a_2=\begin{bmatrix}2\\1\\3\end{bmatrix}}. \]
Pivotposisjonene finnes ved å radredusere, men basisvektorene hentes fra den opprinnelige matrisen. Radoperasjoner endrer kolonnene.
De to andre kolonnene kan bygges av disse:
\[ a_3=a_2-2a_1, \qquad a_4=a_2-a_1. \]
Kontroller begge relasjonene før du kjører cellen.
Kolonne 1 og 2 er uavhengige og bygger alle kolonnene i \(A\). De danner derfor en basis for kolonnerommet, som har dimensjon 2.
Nullrommet finnes ved å løse det homogene systemet \(Ax=0\). Trappeformen gir
\[ \begin{aligned} x_1+2x_2+x_4&=0,\\ x_2+x_3+x_4&=0. \end{aligned} \]
Pivotvariablene er \(\color{#277da1}{x_1}\) og \(\color{#d98900}{x_2}\). Variablene \(\color{#4f8f49}{x_3}\) og \(\color{#8b5aa7}{x_4}\) er frie. Sett
\[\color{#4f8f49}{x_3=s},\qquad \color{#8b5aa7}{x_4=t}.\]
Løs den andre likningen for \(x_2\), og bruk resultatet i den første likningen. Samle deretter alle ledd som inneholder \(s\), og alle ledd som inneholder \(t\).
Resultatet er
\[ x= \color{#4f8f49}{s\begin{bmatrix}2\\-1\\1\\0\end{bmatrix}} +\color{#8b5aa7}{t\begin{bmatrix}1\\-1\\0\\1\end{bmatrix}}. \]
Dermed er de to viste vektorene en basis for nullrommet. Koden kontrollerer både at de gir output null, og at en tilfeldig lineærkombinasjon fortsatt gjør det.
I dette eksemplet har både kolonnerommet og nullrommet dimensjon 2. Det betyr ikke at de er samme rom: Kolonneromsbasisen består av 3-vektorer i outputrommet, mens nullromsbasisen består av 4-vektorer i inputrommet. At dimensjonene tilfeldigvis er like her, skyldes at \(4=2+2\).
Matrisen har fire kolonner, altså fire inputvariabler. Eliminasjonen ga to pivotvariabler og to frie variabler:
\[ \underbrace{4}_{\text{inputdimensjon}} = \underbrace{ \color{#277da1}{1}+\color{#d98900}{1} }_{\text{rang}=2} + \underbrace{ \color{#4f8f49}{1}+\color{#8b5aa7}{1} }_{\text{nullitet}=2}. \]
Rangen kommer fra de to pivotene. Nulliteten kommer uavhengig fra nullromsberegningen: Vi fant en basis med to vektorer. Først nå bruker vi disse to resultatene til å kontrollere rang–nullitet.
Siden \(a_1\) og \(a_2\) er en basis for kolonnerommet, kan alle mulige outputvektorer bygges av disse to. La \(\alpha\) og \(\beta\) være to fritt valgte tall. De bestemmer hvor mye av henholdsvis \(a_1\) og \(a_2\) vi bruker:
\[ \color{#277da1}{\alpha a_1}+\color{#d98900}{\beta a_2} = \begin{bmatrix} \alpha+2\beta\\\beta\\\alpha+3\beta \end{bmatrix}. \]
Uansett hvilke tall vi velger for \(\alpha\) og \(\beta\), er tredje komponent summen av de to første. Vi tester derfor to ønskede outputvektorer:
\[ b=\begin{bmatrix}2\\-1\\1\end{bmatrix}, \qquad d=\begin{bmatrix}2\\-1\\4\end{bmatrix}. \]
Vektoren \(b\) oppfyller \(b_3=b_1+b_2\), mens \(d\) ikke gjør det. Den utvidede matrisen \([A\mid b]\) får derfor samme rang som \(A\), men \([A\mid d]\) får én ekstra pivot.
Dermed gjelder kriteriet
\[ Ax=b\text{ har løsning} \quad\Longleftrightarrow\quad \operatorname{rank}(A)=\operatorname{rank}([A\mid b]). \]
Hva gjør vi når en ønsket output som \(d\) ikke kan produseres nøyaktig? Det spørsmålet leder direkte til projeksjon og minste kvadraters metode i uke 4.
Velg en input \(x_0\) og beregn \(y=Ax_0\). Hvis \(z\) ligger i nullrommet, gir \(x_0+z\) samme output:
\[A(x_0+z)=Ax_0+Az=Ax_0.\]
Cellen under lager en hel familie av forskjellige inputvektorer med samme output.
Dette er den rene matriseversjonen av åpningsproblemet: Nullrommet beskriver alle endringer i inputen som ikke endrer outputen.
Til slutt endrer vi den avhengige tredje raden med et svært lite tall. For enhver \(\varepsilon\ne0\) er den forstyrrede matrisen eksakt sett av rang 3. Numerisk må vi likevel avgjøre om den nye pivoten er stor nok til å skilles fra avrundingsfeil.
Dette er ikke en motsigelse. Eksakt rang gjelder en idealisert matrise med eksakte tall. Numerisk rang beskriver hvor mange uavhengige retninger vi kan skille pålitelig med den valgte presisjonen og toleransen.
Dette er repetisjonsoppgaver, ikke en obligatorisk fortsettelse av hovedløpet. Bruk matrisen \(B\) som selvtest. Hvis regningen går greit, kan du gå direkte til kodekontrollen eller avslutte. Bruk matrisen \(C\) som ekstra trening dersom du trenger mer øvelse med avhengige rader, nullrom og rang–nullitet.
Start alltid på papir. Bruk kodeoppgaven nederst etterpå til å kontrollere regningen og eksperimentere videre. Arbeid med én matrise om gangen:
\[ B=\begin{bmatrix} 1&0&1\\ 0&1&1\\ 1&1&2 \end{bmatrix}, \qquad C=\begin{bmatrix} 1&2&3\\ 2&4&6 \end{bmatrix}. \]
På papir
Oppgavene under vurderes eksakt med SymPy. Du velger selv hvor mange pivotindekser og basisvektorer du vil levere. Bruk knappene under matrisen for å legge til eller fjerne kolonner. Antallet er en del av svaret.
For en matrise med \(n\) kolonner gjelder \(n=\operatorname{rank}(M)+\operatorname{nullity}(M)\). Pivotkolonnene bestemmes fra en trappeform, men en basis for kolonnerommet hentes fra de tilsvarende kolonnene i den opprinnelige matrisen. En basis for nullrommet må bestå av lineært uavhengige vektorer \(z\) som oppfyller \(Mz=0\).
I basisoppgavene farges en gyldig og uavhengig familie grønn. Hvis gyldige vektorer er lineært avhengige, blir hele familien gul; rekkefølgen skal ikke avgjøre hvilken vektor som får skylden. En nullvektor eller en vektor utenfor det etterspurte rommet blir rød. En grønn familie kan fortsatt mangle vektorer før den spenner ut hele rommet.
Selvtest med \(B\)
Ekstra trening med \(C\)
Med kode
Bruk denne delen etter at du har arbeidet med den valgte matrisen på papir. Cellen under inneholder en kort, selvstendig kopi av row_echelon, slik at kontrolloppgaven virker selv om du ikke har åpnet og kjørt kodecellen i matriserepetisjonen i 3.7.
- Kontroller trappeformen og pivotkolonnene med
row_echelon. - Kontroller nullromsvektorene ved å beregne
M @ Z. - Lag to forskjellige inputer med samme output.
- Finn én output som kan produseres, og én som ikke kan produseres.