Hva er problemet?

Et likningssystem $A\mathbf{x}=\mathbf{b}$ med flere likninger enn ukjente («overbestemt», $A$ er $m\times n$ med $m>n$) har som regel ingen eksakt løsning, fordi $\mathbf{b}$ sjelden ligger i kolonnerommet $\operatorname{Col}A$. I stedet leter vi etter den vektoren $\hat{\mathbf{x}}$ som gjør $A\mathbf{x}$ så nær $\mathbf{b}$ som mulig, målt med euklidsk avstand.

Vi minimerer altså summen av kvadrerte avvik:

$$\lVert\mathbf{b}-A\mathbf{x}\rVert^{2}=\sum_{i=1}^{m}\bigl(b_i-(A\mathbf{x})_i\bigr)^{2}.$$

Derav navnet minste kvadraters metode.

Grunnregel — Normallikningene

Den eller de minste kvadraters løsningene $\hat{\mathbf{x}}$ av $A\mathbf{x}=\mathbf{b}$ er nøyaktig løsningene av normallikningene:

$$A^{T}A\,\hat{\mathbf{x}}=A^{T}\mathbf{b}.$$

Hvis kolonnene i $A$ er lineært uavhengige, er $A^{T}A$ invertibel og løsningen er entydig: $\hat{\mathbf{x}}=(A^{T}A)^{-1}A^{T}\mathbf{b}$.

Geometrien: projeksjon på kolonnerommet

Kolonnerommet $\operatorname{Col}A$ består av alle vektorer på formen $A\mathbf{x}$. Den nærmeste vektoren i dette underrommet til $\mathbf{b}$ er den ortogonale projeksjonen $\hat{\mathbf{b}}=A\hat{\mathbf{x}}$. Nøkkelen er at residualet (feilvektoren) $\mathbf{r}=\mathbf{b}-A\hat{\mathbf{x}}$ står ortogonalt på hele $\operatorname{Col}A$:

$$A^{T}(\mathbf{b}-A\hat{\mathbf{x}})=\mathbf{0}\quad\Longleftrightarrow\quad A^{T}A\hat{\mathbf{x}}=A^{T}\mathbf{b}.$$

Vi får en entydig ortogonal dekomposisjon $\mathbf{b}=\hat{\mathbf{b}}+\mathbf{r}$ med $\hat{\mathbf{b}}\in\operatorname{Col}A$ og $\mathbf{r}\in(\operatorname{Col}A)^{\perp}=\operatorname{Nul}(A^{T})$. Ved Pytagoras: $\lVert\mathbf{b}\rVert^{2}=\lVert\hat{\mathbf{b}}\rVert^{2}+\lVert\mathbf{r}\rVert^{2}$.

Når kolonnene er uavhengige, kan vi skrive projeksjonen direkte med projeksjonsmatrisen $P=A(A^{T}A)^{-1}A^{T}$, som oppfyller $P^{2}=P$ og $P^{T}=P$.

Eksempel 1 — Rett linje gjennom fire punkter

Tilpass $y=\beta_0+\beta_1 x$ til $(0,1),(1,1),(2,2),(3,2)$ med minste kvadrater.

Designmatrise og høyreside:

$$A=\begin{bmatrix}1&0\\1&1\\1&2\\1&3\end{bmatrix},\qquad \mathbf{b}=\begin{bmatrix}1\\1\\2\\2\end{bmatrix}.$$

Beregn normallikningene:

$$A^{T}A=\begin{bmatrix}4&6\\6&14\end{bmatrix},\qquad A^{T}\mathbf{b}=\begin{bmatrix}6\\11\end{bmatrix}.$$

Her er $\det(A^{T}A)=4\cdot14-36=20$, så

$$\hat{\mathbf{x}}=\frac{1}{20}\begin{bmatrix}14&-6\\-6&4\end{bmatrix}\begin{bmatrix}6\\11\end{bmatrix}=\frac{1}{20}\begin{bmatrix}84-66\\-36+44\end{bmatrix}=\begin{bmatrix}0{,}9\\0{,}4\end{bmatrix}.$$

Beste linje: $y=0{,}9+0{,}4x$. Kontroll: $\hat{\mathbf{b}}=(0{,}9,\,1{,}3,\,1{,}7,\,2{,}1)$, residual $\mathbf{r}=(0{,}1,\,-0{,}3,\,0{,}3,\,-0{,}1)$, og $\mathbf{1}\cdot\mathbf{r}=0$, $\mathbf{x}\cdot\mathbf{r}=0$ — ortogonalt, som det skal være.

Kurvetilpasning generelt

Metoden virker for enhver modell som er lineær i parametrene. Man bygger designmatrisen $A$ ved å sette basisfunksjonene evaluert i hvert datapunkt som rader:

Linje $y=\beta_0+\beta_1 x$: rad $[\,1\ \ x_i\,]$.
Parabel $y=\beta_0+\beta_1 x+\beta_2 x^2$: rad $[\,1\ \ x_i\ \ x_i^{2}\,]$.
Plan $z=\beta_0+\beta_1 x+\beta_2 y$: rad $[\,1\ \ x_i\ \ y_i\,]$.

Ulineære modeller som $y=\beta_0 e^{\beta_1 x}$ må først linjeariseres, her ved $\ln y=\ln\beta_0+\beta_1 x$.

Eksempel 2 — Projeksjon på kolonnerom

Finn minste kvadraters løsning av $A\mathbf{x}=\mathbf{b}$ med

$$A=\begin{bmatrix}1&0\\1&1\\0&1\end{bmatrix},\qquad \mathbf{b}=\begin{bmatrix}1\\2\\3\end{bmatrix},$$

og bestem projeksjonen $\hat{\mathbf{b}}$ av $\mathbf{b}$ på $\operatorname{Col}A$.

Normallikninger:

$$A^{T}A=\begin{bmatrix}2&1\\1&2\end{bmatrix},\qquad A^{T}\mathbf{b}=\begin{bmatrix}3\\5\end{bmatrix}.$$

$\det=3$, så

$$\hat{\mathbf{x}}=\frac{1}{3}\begin{bmatrix}2&-1\\-1&2\end{bmatrix}\begin{bmatrix}3\\5\end{bmatrix}=\frac{1}{3}\begin{bmatrix}6-5\\-3+10\end{bmatrix}=\begin{bmatrix}1/3\\7/3\end{bmatrix}.$$

Projeksjonen blir

$$\hat{\mathbf{b}}=A\hat{\mathbf{x}}=\begin{bmatrix}1/3\\1/3+7/3\\7/3\end{bmatrix}=\begin{bmatrix}1/3\\8/3\\7/3\end{bmatrix}.$$

Residual: $\mathbf{r}=\mathbf{b}-\hat{\mathbf{b}}=(2/3,\,-2/3,\,2/3)$, med $\lVert\mathbf{r}\rVert=\sqrt{4/3}=\tfrac{2}{\sqrt3}$. Sjekk ortogonalitet: kolonne 1 gir $1\cdot\tfrac23+1\cdot(-\tfrac23)+0=0$, kolonne 2 gir $0-\tfrac23+\tfrac23=0$. Korrekt.

Numeriske aspekter (QR)

Å danne $A^{T}A$ kvadrerer kondisjonstallet og forsterker avrundingsfeil. I praksis bruker man derfor ofte QR-faktorisering $A=QR$ (med ortonormale kolonner i $Q$). Da reduseres normallikningene til $R\hat{\mathbf{x}}=Q^{T}\mathbf{b}$, som løses stabilt ved tilbakesubstitusjon siden $R$ er øvre triangulær.

Studieguide: Minste kvadraters metode

Studieguide: Minste kvadraters metode