Tilbake
5.2

5.2 Minste kvadrater: normallikninger, projeksjonssnarvei og affin løsning

Minste kvadraters løsning av Cx=b på to belønnede måter — normallikningene CᵀCx̂=Cᵀb og projeksjonssnarveien p=proj_W b ⇒ Cx=p — pluss det avgjørende poenget: ved rangdefekt er løsningen affin (partikulær + Nul C).

60 min
7 oppgaver
Minste kvadraternormallikningerprojeksjonssnarveiaffin løsning
Din fremgang i kapitlet
0 / 7 oppgaver
Forkunnskaper:

- Kap. 5.1 — ortogonal projeksjon og dekomposisjonen y=y^+z\mathbf{y}=\hat{\mathbf{y}}+\mathbf{z}; minste kvadrater er projeksjon i forkledning
- Kap. 1.2NulC\operatorname{Nul}C og full kolonnerang; den affine løsningen ved rangdefekt er partikulær +NulC+\operatorname{Nul}C
- Kap. 1.1 — å lese en liten RREF av normallikningene fra vedlegget er samme teknikk
- Matriseregning og transponering (MAT1110) — grunnleggende matrisemultiplikasjon og transponering

Noen ganger har likningssystemet Cx=bC\mathbf{x}=\mathbf{b} ingen løsningb\mathbf{b} ligger ikke i ColC\operatorname{Col}C. I stedet for å gi opp spør vi: hvilken x^\hat{\mathbf{x}} gjør Cx^C\hat{\mathbf{x}} så nær b\mathbf{b} som mulig? Det er minste kvadraters problem, og svaret er nettopp projeksjon: Cx^C\hat{\mathbf{x}} skal være projWb\operatorname{proj}_W\mathbf{b} der W=ColCW=\operatorname{Col}C.

Vi jobber i tre løkker: (1) minste kvadraters problem og normallikningene CTCx^=CTbC^{T}C\hat{\mathbf{x}}=C^{T}\mathbf{b}; (2) projeksjonssnarveien og koblingen projWb=Cx^\operatorname{proj}_W\mathbf{b}=C\hat{\mathbf{x}}; (3) entydighet vs. affin løsning ved rangdefekt, og datatilpasning. Hver løkke går teori → eksempel → oppgave.

Tidsanslaget (~60 min) gjelder kjernestoffet — begrepsbanken til slutt er repetisjon.

Løkke 1 — Minste kvadraters problem og normallikningene (~24 min)

Minste kvadraters problem
Gitt en matrise CC og en vektor b\mathbf{b} (der Cx=bC\mathbf{x}=\mathbf{b} kanskje ikke har løsning) er en minste kvadraters løsning en vektor x^\hat{\mathbf{x}} som gjør residualet minst mulig:

x^ minimerer bCx.\hat{\mathbf{x}}\ \text{minimerer}\ \|\mathbf{b}-C\mathbf{x}\|.

I ord: vi finner den x^\hat{\mathbf{x}} slik at Cx^C\hat{\mathbf{x}} er den vektoren i ColC\operatorname{Col}C som ligger nærmest b\mathbf{b}. Navnet «minste kvadrater» kommer av at bCx2\|\mathbf{b}-C\mathbf{x}\|^2 er en sum av kvadrater som minimeres. Residualet er bCx^\mathbf{b}-C\hat{\mathbf{x}}.

📜Normallikningene
En vektor x^\hat{\mathbf{x}} er en minste kvadraters løsning av Cx=bC\mathbf{x}=\mathbf{b} hvis og bare hvis den løser normallikningene

CTCx^=CTb.C^{T}C\,\hat{\mathbf{x}}=C^{T}\mathbf{b}.

Hvorfor: Cx^C\hat{\mathbf{x}} er nærmest b\mathbf{b} nettopp når residualet bCx^\mathbf{b}-C\hat{\mathbf{x}} står vinkelrett på ColC\operatorname{Col}C (beste tilnærming, kap. 5.1). Å være ortogonal på alle kolonnene i CC betyr CT(bCx^)=0C^{T}(\mathbf{b}-C\hat{\mathbf{x}})=\mathbf{0}, som omordnet er CTCx^=CTbC^{T}C\hat{\mathbf{x}}=C^{T}\mathbf{b}. Dette er alltid et konsistent (løsbart) system, og det er lite: bare n×nn\times n der nn er antall kolonner i CC — les RREF-en av det fra vedlegget.

✏️Eksempel 1: Minste kvadrater via normallikningene
Finn minste kvadraters løsning av Cx=bC\mathbf{x}=\mathbf{b} med
C=[11121314],b=[3236].C=\begin{bmatrix}1&1\\1&2\\1&3\\1&4\end{bmatrix},\qquad \mathbf{b}=\begin{bmatrix}3\\2\\3\\6\end{bmatrix}.
Vedlegget gir rref[CTCCTb]=[101011].\operatorname{rref}\big[\,C^{T}C\mid C^{T}\mathbf{b}\,\big]=\begin{bmatrix}1&0&1\\0&1&1\end{bmatrix}.
Sett opp normallikningene. Regn de små produktene for hånd:
CTC=[4101030],CTb=[1440].C^{T}C=\begin{bmatrix}4&10\\10&30\end{bmatrix},\qquad C^{T}\mathbf{b}=\begin{bmatrix}14\\40\end{bmatrix}.
(Første komponent i CTbC^{T}\mathbf{b} er 3+2+3+6=143+2+3+6=14; andre er 13+22+33+46=3+4+9+24=401\cdot3+2\cdot2+3\cdot3+4\cdot6=3+4+9+24=40.)

Løs systemet. Fra vedleggets RREF ser vi at
rref[41014103040]=[101011]  x^=[11].\operatorname{rref}\begin{bmatrix}4&10&14\\10&30&40\end{bmatrix}=\begin{bmatrix}1&0&1\\0&1&1\end{bmatrix}\ \Rightarrow\ \hat{\mathbf{x}}=\begin{bmatrix}1\\1\end{bmatrix}.

Kontroll og residual. Cx^=(2,3,4,5)C\hat{\mathbf{x}}=(2,3,4,5), så residualet er
bCx^=(3,2,3,6)(2,3,4,5)=(1,1,1,1).\mathbf{b}-C\hat{\mathbf{x}}=(3,2,3,6)-(2,3,4,5)=(1,-1,-1,1).
Dette står vinkelrett på begge kolonnene i CC: (1,1,1,1),(1,1,1,1)=0\langle(1,-1,-1,1),(1,1,1,1)\rangle=0 og (1,1,1,1),(1,2,3,4)=123+4=0.\langle(1,-1,-1,1),(1,2,3,4)\rangle=1-2-3+4=0.Eksakt svar: x^=(1,1)\hat{\mathbf{x}}=(1,1).

📝Oppgave 1

(Innstegsoppgave — ren gjengivelse.) Skriv opp normallikningene for minste kvadraters problem Cx=bC\mathbf{x}=\mathbf{b}, og forklar med ett ord hva løsningen x^\hat{\mathbf{x}} gjør.

📝Oppgave 2

Finn minste kvadraters løsning av Cx=bC\mathbf{x}=\mathbf{b} med C=[10111213]C=\begin{bmatrix}1&0\\1&1\\1&2\\1&3\end{bmatrix}, b=[2167]\mathbf{b}=\begin{bmatrix}2\\1\\6\\7\end{bmatrix}. Vedlegget gir rref[CTCCTb]=[101012]\operatorname{rref}\big[\,C^{T}C\mid C^{T}\mathbf{b}\,\big]=\begin{bmatrix}1&0&1\\0&1&2\end{bmatrix}.

Løkke 2 — Projeksjonssnarveien og koblingen projWb=Cx^\operatorname{proj}_W\mathbf{b}=C\hat{\mathbf{x}} (~18 min)

📜Koblingen projWb=Cx^\operatorname{proj}_W\mathbf{b}=C\hat{\mathbf{x}}
La W=ColCW=\operatorname{Col}C. For enhver minste kvadraters løsning x^\hat{\mathbf{x}} gjelder

Cx^=projWb.C\hat{\mathbf{x}}=\operatorname{proj}_W\mathbf{b}.

Med andre ord: Cx^C\hat{\mathbf{x}} er nettopp projeksjonen av b\mathbf{b} ned på kolonnerommet. Dette gir to veier til samme mål:

- Normallikninger: løs CTCx^=CTbC^{T}C\hat{\mathbf{x}}=C^{T}\mathbf{b}, deretter er projWb=Cx^\operatorname{proj}_W\mathbf{b}=C\hat{\mathbf{x}}.
- Projeksjonssnarvei: finn en ortogonal basis for WW (Gram–Schmidt), regn p=projWb\mathbf{p}=\operatorname{proj}_W\mathbf{b} direkte, og løs det konsistente systemet Cx=pC\mathbf{x}=\mathbf{p}.

Begge gir samme Cx^C\hat{\mathbf{x}}, og residualet bCx^=z\mathbf{b}-C\hat{\mathbf{x}}=\mathbf{z} er restvektoren fra dekomposisjonen. Har du allerede projisert (fra en tidligere deloppgave), er snarveien gratis.

✏️Eksempel 2: Projeksjonssnarveien

For CC og b\mathbf{b} fra Eksempel 1: bruk projeksjonssnarveien til å bestemme projWb\operatorname{proj}_W\mathbf{b} der W=ColCW=\operatorname{Col}C, og kontroller mot Cx^C\hat{\mathbf{x}}.

Ortogonal basis for W=ColCW=\operatorname{Col}C. Kolonnene c1=(1,1,1,1)\mathbf{c}_1=(1,1,1,1), c2=(1,2,3,4)\mathbf{c}_2=(1,2,3,4) er ikke ortogonale (c1,c2=100\langle\mathbf{c}_1,\mathbf{c}_2\rangle=10\ne0), så Gram–Schmidt:
w1=(1,1,1,1),w2=c2104w1=(32,12,12,32)×2(3,1,1,3).\mathbf{w}_1=(1,1,1,1),\quad \mathbf{w}_2=\mathbf{c}_2-\tfrac{10}{4}\mathbf{w}_1=\left(-\tfrac32,-\tfrac12,\tfrac12,\tfrac32\right)\xrightarrow{\times2}(-3,-1,1,3).

Projeksjon av b=(3,2,3,6)\mathbf{b}=(3,2,3,6):
c1=b,w14=144=72,c2=b,w220=92+3+1820=1020=12.c_1=\frac{\langle\mathbf{b},\mathbf{w}_1\rangle}{4}=\frac{14}{4}=\frac72,\quad c_2=\frac{\langle\mathbf{b},\mathbf{w}_2\rangle}{20}=\frac{-9-2+3+18}{20}=\frac{10}{20}=\frac12.
p=72(1,1,1,1)+12(3,1,1,3)=(2,3,4,5).\mathbf{p}=\tfrac72(1,1,1,1)+\tfrac12(-3,-1,1,3)=(2,3,4,5).

Kontroll: Cx^=(2,3,4,5)C\hat{\mathbf{x}}=(2,3,4,5) (fra Eksempel 1) =p=\mathbf{p}. ✓ Koblingen projWb=Cx^\operatorname{proj}_W\mathbf{b}=C\hat{\mathbf{x}} stemmer. Merk at snarveien og normallikningene gir nøyaktig samme punkt i ColC\operatorname{Col}C.

📝Oppgave 3

For C=[11121314]C=\begin{bmatrix}1&1\\1&2\\1&3\\1&4\end{bmatrix} og b=(3,2,3,6)\mathbf{b}=(3,2,3,6) er x^=(1,1)\hat{\mathbf{x}}=(1,1) (fra Eksempel 1). Bruk koblingen projWb=Cx^\operatorname{proj}_W\mathbf{b}=C\hat{\mathbf{x}} til å finne både projeksjonen og avstanden fra b\mathbf{b} til W=ColCW=\operatorname{Col}C.

Løkke 3 — Entydighet, affin løsning ved rangdefekt og datatilpasning (~18 min)

📜Entydighet ⇔ full kolonnerang
Minste kvadraters løsning er entydig hvis og bare hvis CC har full kolonnerang (lineært uavhengige kolonner). Da er CTCC^{T}C invertibel, og

x^=(CTC)1CTb(entydig).\hat{\mathbf{x}}=(C^{T}C)^{-1}C^{T}\mathbf{b}\quad(\text{entydig}).

Har CC derimot ikke full kolonnerang (avhengige kolonner, NulC{0}\operatorname{Nul}C\ne\{\mathbf{0}\}), er CTCC^{T}C ikke invertibel, og løsningsmengden er affin.

Affin løsning ved rangdefekt
Når CC ikke har full kolonnerang, har normallikningene CTCx^=CTbC^{T}C\hat{\mathbf{x}}=C^{T}\mathbf{b} uendelig mange løsninger. Løsningsmengden er affin:

x^=x^p+NulC,\hat{\mathbf{x}}=\hat{\mathbf{x}}_p+\operatorname{Nul}C,

altså én partikulær løsning x^p\hat{\mathbf{x}}_p pluss hele nullrommet til CC (én fri parameter per avhengig kolonne). Dette er felle nr. 5: å oppgi ett svar som om det var entydig. Merk: selv om x^\hat{\mathbf{x}} ikke er entydig, er Cx^=projWbC\hat{\mathbf{x}}=\operatorname{proj}_W\mathbf{b} det samme for alle løsningene — projeksjonen er alltid entydig.

✏️Eksempel 3: Affin løsning (rangdefekt)
Finn alle minste kvadraters løsninger av Cx=bC\mathbf{x}=\mathbf{b} med
C=[112101011112],b=[3002],C=\begin{bmatrix}1&1&2\\1&0&1\\0&1&1\\1&1&2\end{bmatrix},\qquad \mathbf{b}=\begin{bmatrix}3\\0\\0\\2\end{bmatrix},
der tredje kolonne er summen av de to første. Vedlegget gir rref[CTCCTb]=[101101110000].\operatorname{rref}\big[\,C^{T}C\mid C^{T}\mathbf{b}\,\big]=\begin{bmatrix}1&0&1&1\\0&1&1&1\\0&0&0&0\end{bmatrix}.
Full kolonnerang? Nei: c3=c1+c2\mathbf{c}_3=\mathbf{c}_1+\mathbf{c}_2, så kolonnene er avhengige og rangC=2<3\operatorname{rang}C=2<3. Da er CTCC^{T}C ikke invertibel — vent en affin løsning.

Normallikninger. CTC=[3252355510]C^{T}C=\begin{bmatrix}3&2&5\\2&3&5\\5&5&10\end{bmatrix}, CTb=[5510]C^{T}\mathbf{b}=\begin{bmatrix}5\\5\\10\end{bmatrix}. Fra vedleggets RREF ser vi pivot i kolonne 1 og 2, fri variabel x3x_3:
x1=1x3,x2=1x3.x_1=1-x_3,\quad x_2=1-x_3.

Affin løsningsmengde. Med x3=sx_3=s:
x^=[110]+s[111],sR.\hat{\mathbf{x}}=\begin{bmatrix}1\\1\\0\end{bmatrix}+s\begin{bmatrix}-1\\-1\\1\end{bmatrix},\quad s\in\mathbb{R}.
Den partikulære er x^p=(1,1,0)\hat{\mathbf{x}}_p=(1,1,0), og NulC=Span{(1,1,1)}\operatorname{Nul}C=\operatorname{Span}\{(-1,-1,1)\} (fordi c1+c2c3=0\mathbf{c}_1+\mathbf{c}_2-\mathbf{c}_3=\mathbf{0}). Konklusjon: løsningen er ikke entydig — den er affin. Men Cx^p=(2,1,1,2)=projWbC\hat{\mathbf{x}}_p=(2,1,1,2)=\operatorname{proj}_W\mathbf{b} er den samme for alle ss.

📝Oppgave 4

For CC og b\mathbf{b} i Eksempel 3: bestem projWb\operatorname{proj}_W\mathbf{b} (W=ColCW=\operatorname{Col}C) og avstanden d(b,W)d(\mathbf{b},W) ved hjelp av én av de affine løsningene. Forklar hvorfor svaret er uavhengig av hvilken løsning du velger.

Datatilpasning (rett linje)
Å tilpasse en rett linje y=β0+β1ty=\beta_0+\beta_1t til datapunkter (ti,yi)(t_i,y_i) er et minste kvadraters problem. Sett

C=[1t11tm],x=[β0β1],b=[y1ym].C=\begin{bmatrix}1&t_1\\ \vdots&\vdots\\1&t_m\end{bmatrix},\quad \mathbf{x}=\begin{bmatrix}\beta_0\\\beta_1\end{bmatrix},\quad \mathbf{b}=\begin{bmatrix}y_1\\\vdots\\y_m\end{bmatrix}.

Normallikningene CTCx^=CTbC^{T}C\hat{\mathbf{x}}=C^{T}\mathbf{b} gir da den «beste» linjen (minst sum av kvadrerte avvik). Så lenge minst to tit_i er ulike, har CC full kolonnerang og linjen er entydig. Eksempel 1 var nettopp en slik linjetilpasning: y=1+ty=1+t.

📝Oppgave 5

Tilpass en rett linje y=β0+β1ty=\beta_0+\beta_1 t til punktene (1,3),(2,2),(3,3),(4,6)(1,3),(2,2),(3,3),(4,6) ved minste kvadrater. (Dette er C,bC,\mathbf{b} fra Eksempel 1.) Skriv ned linjen.

Begrepsbank til eksamen

Kjernebegrepene fra kapitlet i eksamensrettet kortform — apparatet bak sjanger C (minste kvadrater).

Begrepsbanken er flashcard-/repetisjonsstoff — den gjentar det du nettopp har lest. Hopp trygt over ved førstegangslesing; tidsanslaget for kapitlet gjelder kjernestoffet.

Minste kvadraters løsning

En x^\hat{\mathbf{x}} som minimerer bCx\|\mathbf{b}-C\mathbf{x}\| — gjør Cx^C\hat{\mathbf{x}} nærmest b\mathbf{b} i ColC\operatorname{Col}C. Brukes når Cx=bC\mathbf{x}=\mathbf{b} ikke har eksakt løsning.

Normallikningene
CTCx^=CTbC^{T}C\hat{\mathbf{x}}=C^{T}\mathbf{b} — alltid konsistent. Fås ved å multiplisere Cx=bC\mathbf{x}=\mathbf{b} med CTC^{T}, eller av at residualet skal være ortogonalt på ColC\operatorname{Col}C.
Residual

Vektoren bCx^\mathbf{b}-C\hat{\mathbf{x}}. Ved en minste kvadraters løsning står den vinkelrett på ColC\operatorname{Col}C, og dens norm er avstanden d(b,ColC)d(\mathbf{b},\operatorname{Col}C).

CTCC^{T}C

Kvadratisk n×nn\times n-matrise (n=n= antall kolonner i CC). Invertibel nøyaktig når CC har full kolonnerang; da er x^=(CTC)1CTb\hat{\mathbf{x}}=(C^{T}C)^{-1}C^{T}\mathbf{b}.

CTbC^{T}\mathbf{b}

Høyresiden i normallikningene. Komponent ii er prikkproduktet av kolonne ii i CC med b\mathbf{b}.

Koblingen projWb=Cx^\operatorname{proj}_W\mathbf{b}=C\hat{\mathbf{x}}

For W=ColCW=\operatorname{Col}C er Cx^C\hat{\mathbf{x}} nettopp projeksjonen av b\mathbf{b} ned i kolonnerommet — samme for alle minste kvadraters løsninger.

Projeksjonssnarvei

Regn p=projWb\mathbf{p}=\operatorname{proj}_W\mathbf{b} direkte (Gram–Schmidt + Fourier), og løs det konsistente Cx=pC\mathbf{x}=\mathbf{p}. Alternativ til normallikningene.

To belønnede veier

Normallikninger eller projeksjonssnarvei — begge gir samme Cx^C\hat{\mathbf{x}}. Velg den som utnytter det du allerede har regnet (f.eks. en tidligere projeksjon).

Full kolonnerang

Kolonnene i CC er lineært uavhengige (NulC={0}\operatorname{Nul}C=\{\mathbf{0}\}). Da er CTCC^{T}C invertibel og løsningen entydig.

Rangdefekt

Kolonnene i CC er avhengige (NulC{0}\operatorname{Nul}C\ne\{\mathbf{0}\}). Da er CTCC^{T}C ikke invertibel og løsningen affin.

Affin løsningsmengde
x^=x^p+NulC\hat{\mathbf{x}}=\hat{\mathbf{x}}_p+\operatorname{Nul}C — én partikulær løsning pluss hele nullrommet. Oppstår ved rangdefekt (felle nr. 5).
Projeksjonen er alltid entydig

Selv når x^\hat{\mathbf{x}} er affin, er Cx^=projWbC\hat{\mathbf{x}}=\operatorname{proj}_W\mathbf{b} det samme for alle løsninger, fordi Cn=0C\mathbf{n}=\mathbf{0} for nNulC\mathbf{n}\in\operatorname{Nul}C.

Residual ColC\perp\operatorname{Col}C

Betingelsen CT(bCx^)=0C^{T}(\mathbf{b}-C\hat{\mathbf{x}})=\mathbf{0} er selve grunnen til normallikningene — residualet er ortogonalt på hver kolonne.

Avstand ved minste kvadrater
d(b,ColC)=bCx^d(\mathbf{b},\operatorname{Col}C)=\|\mathbf{b}-C\hat{\mathbf{x}}\| — residualets norm, ikke Cx^\|C\hat{\mathbf{x}}\|.
Les RREF fra vedlegget

Normallikningene danner et lite n×nn\times n-system; RREF leses av Matlab-utskriften eller RREF-arket, ikke radredusert for hånd.

Datatilpasning (linje)
y=β0+β1ty=\beta_0+\beta_1t til punkter (ti,yi)(t_i,y_i): CC har 1-kolonne og tt-kolonne, b\mathbf{b} er yy-verdiene. Entydig når tit_i-ene ikke alle er like.
Datatilpasning (kurve)

Samme prinsipp for y=β0+β1t+β2t2y=\beta_0+\beta_1t+\beta_2t^2: legg til en t2t^2-kolonne i CC. Fortsatt lineært i β\beta-ene, så normallikningene gjelder.

Sum av kvadrater

«Minste kvadrater» minimerer bCx2=(bi(Cx)i)2\|\mathbf{b}-C\mathbf{x}\|^2=\sum(b_i-(C\mathbf{x})_i)^2 — summen av kvadrerte residualer.

Minste kvadrater = projeksjon

Å løse Cx^=projWbC\hat{\mathbf{x}}=\operatorname{proj}_W\mathbf{b} er hele ideen: den beste tilnærmingen i ColC\operatorname{Col}C er projeksjonen av b\mathbf{b}.

Begrunn valg og entydighet

Sensor vil se hvilken vei du velger og en eksplisitt setning om løsningen er entydig (full kolonnerang) eller affin (rangdefekt).

CTCC^{T}C er symmetrisk og positiv semidefinit

Uansett CC er CTCC^{T}C symmetrisk, og xTCTCx=Cx20\mathbf{x}^{T}C^{T}C\mathbf{x}=\|C\mathbf{x}\|^2\ge0. Den er positiv definit (dermed invertibel) nøyaktig når CC har full kolonnerang.

Overbestemt system

Flere likninger enn ukjente (flere rader enn kolonner i CC) har som regel ingen eksakt løsning — minste kvadrater gir den beste tilnærmingen i stedet.

Velg partikulær løsning

Ved rangdefekt oppgir du gjerne den enkleste partikulære løsningen (frie variabler =0=0) og legger til NulC\operatorname{Nul}C. Alle valg gir samme Cx^=projWbC\hat{\mathbf{x}}=\operatorname{proj}_W\mathbf{b}.

Repetisjonsoppgaver
Din fremgang
0 / 2 oppgaver
Symbol- og formelliste

Dette kapitlet er skrevet av Anthropics toppmodeller (Claude Opus og Claude Fable) og er foreløpig ikke manuelt gjennomgått — kvalitetskontrollen gjøres av uavhengige KI-agenter, og innmeldte feil rettes fortløpende. Funnet en feil? Meld fra, så retter vi den. Les mer om hvordan innholdet lages.

Skolesaga er en uavhengig læringsressurs og er ikke tilknyttet eller godkjent av Universitetet i Oslo. Dette er ikke offisielt studiemateriell. Les mer.