10Mindste kvadraters metode

10.1 Mindste kvadraters metode

Mindste kvadraters metode kendes nok bedst fra problemet om at bestemme den bedste rette linje gennem nogle punkter i planen. Faktisk er den langt mere generel og drejer sig om at finde approksimative løsninger til overbestemte ligningssystemer. Metoden blev opfundet af Gauss og brugt første gang i forbindelse med bestemmelse af baner for himmellegemer ud fra tre observationer.

Det er ikke altid at et ligningssystem

$A \mathbf x = \mathbf b$ med en $m\times n$ matrix $A$ og $\mathbf b \in \mathbb{C}^m$ har en løsning, og det er heller ikke altid at denne løsning er entydig. Hvis for eksempel $m$ er meget større end $n$ , det vil sige at der er mange flere ligninger end ubekendte, og hvis $A$ og $\mathbf b$ er ''tilfældige'', så vil med overvældende sandsynlighed gælde følgende to ting:

Ligningen $A\mathbf x=\mathbf b$ har ikke nogen løsning.
Den homogene ligning $A\mathbf x=\mathbf 0$ har kun den ene løsning $\mathbf x=\mathbf 0$ .

Det lyder jo ikke særlig lovende.

I denne situation kan vores forventning til at vi kan finde en løsning ligge på et meget lille sted, og det bedste vi kan gøre er at søge en vektor $\mathbf x$ så at $A\mathbf x$ kommer tættest muligt på $\mathbf b$ .

Ligningssystemet

$\begin{pmatrix} 1 & 1\\ i & -1\\ -1 & i \end{pmatrix} \begin{pmatrix} x\\ y \end{pmatrix} = \begin{pmatrix} 3 \\ 1 \\ 1 \end{pmatrix},$ har ingen løsninger da højresiden ikke ligger i søjlerummet for systemmatricen.

Nøglen til at approksimativt løse et ligningssystem ligger i de såkaldte normalligninger.

Lad $A$ være en $m\times n$ matrix og $\mathbf b\in\mathbb{C}^m$ . Så kaldes

$A^*A\mathbf x = A^*\mathbf b \tag{10.1}$ for normalligningerne til ligningssystemet

$A\mathbf x = \mathbf b. \tag{10.2}$ En løsning til (10.1) kaldes en mindste kvadraters løsning til (10.2).

Som vi efterhånden er blevet bekvemme med, så ved vi at nulrummet er vigtigt for at kunne opskrive løsninger til et ligningssystem. Det første vi indser, er at nulrummet for systemmatricen i normalligningerne er præcis det samme som i det oprindelige ligningsystem.

For enhver matrix $A$ gælder at $N(A^*A) = N(A)$ .

Bevis

Lad os starte med en vektor $\mathbf x\in N(A)$ , altså $A\mathbf x = \mathbf 0$ . Så har vi også

$A^*A\mathbf x = A^*\mathbf 0 = \mathbf 0,$ så $\mathbf x\in N(A^*A)$ .

Lad os nu overveje $\mathbf y\in N(A^*A)$ , så mangler vi at vise at dette medfører at $\mathbf y\in N(A)$ . Til dette formål kigger vi nu på normen af $A\mathbf y$ :

$|A\mathbf y|^2 = (A\mathbf y)^*(A\mathbf y) = \mathbf y^*A^*A\mathbf y = \mathbf y^*\mathbf 0 = 0.$ Dette viser at $A\mathbf y = \mathbf 0$ , og derfor at $\mathbf y\in N(A)$ som vi skulle vise.

Ved første øjekast ligner det ikke at der er sket det store fra (10.2) til (10.1), for vi har jo kun ganget med $A^*$ fra venstre. Dette betyder derfor også, at hvis der rent faktisk er en sædvanlig løsning $\mathbf x_0$ til (10.2) så vil $\mathbf x_0$ også være en mindste kvadraters løsning.

Det smukke ved normalligningerne er, at de altid har en løsning, også selv hvis der ikke findes sædvanlige løsninger til (10.2). Forklaringen på dette, kommer af at (10.2) kun har løsninger hvis $\mathbf b$ er i søjlerummet for $A$ , mens (10.1) har løsninger hvis $A^*\mathbf b$ er i søjlerummet for $A^*A$ . Nu er $A$ pludselig involveret i både venstre- og højresiden af ligningssystemet. En geometrisk forklaring på eksistensen af en mindste kvadraters løsning kommer i næste afsnit.

Overvej ligningssystemet $A\mathbf x=\mathbf b$ hvor $A$ er en $m\times n$ matrix og $\mathbf b\in\mathbb{C}^m$ .

Der findes mindst én mindste kvadraters løsning $\mathbf x_0$ .
Alle mindste kvadraters løsninger er givet ved
$\mathbf x_0 + \mathbf y$ hvor $\mathbf y\in N(A)$ .
Hvis nulrummet af $A$ er trivielt, dvs. $N(A) = \{0\}$ , så er $A^*A$ invertibel og den entydige mindste kvadraters løsning er givet ved
$\mathbf x_0 = (A^*A)^{-1}A^*\mathbf b.$

Bevis

Vi får brug for en ortogonal dekomposition af $\mathbf b$

$\mathbf b = \mathbf b_0 + \widehat{\mathbf b}$ hvor $\mathbf b_0\in N(A^*)$ og $\widehat{\mathbf b}\in C(A)$ . Dette betyder blandt andet at $A^*\mathbf b = A^*\widehat{\mathbf b}$ .

Det at $\widehat{\mathbf b}\in C(A)$ betyder lige præcis at der eksisterer en vektor $\mathbf x_0\in \mathbb{C}^n$ der opfylder

$A\mathbf x_0 = \widehat{\mathbf b}.$ Vi kan nu gange med $A^*$ , for at indse at $\mathbf x_0$ faktisk er en mindste kvadraters løsning:

$A^*A\mathbf x_0 = A^*\widehat{\mathbf b} = A^*\mathbf b.$ Nu hvor vi har fundet en løsning til (10.1), så kan samtlige mindste kvadraters løsninger opskrives på formen $\mathbf x_0 + \mathbf y$ hvor $\mathbf y\in N(A^*A)$ , hvilket fra Lemma 10.3 er ensbetydende med at $\mathbf y\in N(A)$ . Dette medfører både resultaterne i (ii) og (iii).

Fra dimensionssætningen (Sætning 6.29) ved vi at nulrummet for $A$ er trivielt hvis og kun hvis rangen af matricen $A$ er $n$ . Det vil sige når alle søjlerne i $A$ er lineært uafhængige.
Beviset for Sætning 10.4 gemmer på en meget vigtig intuition omkring mindste kvadraters løsninger: De er lige præcis løsningerne til
$A\mathbf x = \widehat{\mathbf b}$ hvor $\widehat{\mathbf b}$ er den ortogonale projektion af $\mathbf b$ på $C(A)$ . Det vil sige at man udskifter højresiden i ligningssystemet med en vektor $\widehat{\mathbf b}$ , der ligger tættest muligt på den oprindelige højreside $\mathbf b$ , men garanterer at det nye ligningssystem har en løsning.

10.2 Hvorfor kaldes det mindste kvadraters metode?

Som det blev nævnt i Bemærkning 10.5, så svarer mindste kvadraters løsningerne til at løse et nyt ligningssystem med en projiceret højreside. Det viser sig, at dette netop svarer til at løse et minimeringsproblem.

Hvis $\mathbf x_0$ er en mindste kvadraters løsning til $A\mathbf x=\mathbf b$ , så opfylder $\mathbf x_0$

$|\mathbf b-A\mathbf x_0| = \min_{\mathbf x} |\mathbf b - A\mathbf x|.$

Bevis

Lad $A$ være en $m\times n$ matrix. Vi har at $A\mathbf x_0 = \widehat{\mathbf b}$ hvor $\widehat{\mathbf b}$ er ortogonal projektionen af $\mathbf b$ på $C(A)$ . Fra Sætning 9.32 ved vi at dette betyder

$|\mathbf b-A\mathbf x_0| = |\mathbf b-\widehat{\mathbf b}| = \min\{|\mathbf b-\widetilde{\mathbf b}| : \widetilde{\mathbf b}\in C(A)\}.$ Nu skal vi bruge at $A$ afbilder hele $\mathbb{C}^n$ over på $C(A)$ , altså kan vi erstatte $\widetilde{\mathbf b}\in C(A)$ med $A\mathbf x$ hvor $\mathbf x\in \mathbb{C}^n$ :

$|\mathbf b-A\mathbf x_0| = \min\{|\mathbf b-A\mathbf x| : \mathbf x\in\mathbb{C}^n\}.$

I nogle sammehænge bruges Sætning 10.6 som en definition på en mindste kvadraters løsning og så vises at dette svarer til at løse normalligningerne; de to fremgangsmåder er helt ækvivalente for lineære ligningssystemer. Her har vi valgt at fokusere på selve løsningsmetoden i Sætning 10.4, da generelle metoder til løsning af optimeringsproblemer er en anden snak.

Når vi har en mindste kvadraters løsning $\mathbf x_0$ , kan vi se på hvor langt vi er fra at løse det tilhørende ligningssystem. Vi skal altså kigge på residualvektoren

$\mathbf{r} = \mathbf b - A\mathbf x_0. \tag{10.3}$

Her angiver hvert af koordinaterne i $\mathbf{r} = (r_1,\dots,r_m)$ fejlen der bliver begået i de forskellige ligninger i ligningssystemet. Det vil sige at optimeringsproblemet i Sætning 10.6 minimerer

$|\mathbf{r}| = \sqrt{|r_1|^2+\dots+|r_m|^2}, \tag{10.4}$ altså summen af de kvadrerede fejl; heraf navnet mindste kvadraters metode.

10.3 Eksempler

Lad os begynde med et konkret eksempel.

Lad

$A = \begin{pmatrix} 1 & 1\\ i & -1\\ -1 & i \end{pmatrix} \quad \text{og} \quad \mathbf b = \begin{pmatrix} 3 \\ 1 \\ 1 \end{pmatrix}.$ I Eksempel 10.1 blev det nævnt at $A\mathbf x=\mathbf b$ ikke har nogen løsning. Lad os i stedet finde mindste kvadraters løsninger.

Først har vi

$A^* = \overline{A}^T = \begin{pmatrix} 1 & -i & -1 \\ 1 & -1 & -i \end{pmatrix},$ hvilket giver

$\begin{aligned} A^*A &= \begin{pmatrix} 1 & -i & -1 \\ 1 & -1 & -i \end{pmatrix}\begin{pmatrix} 1 & 1\\ i & -1\\ -1 & i \end{pmatrix} = \begin{pmatrix} 3 & 1 \\ 1 & 3 \end{pmatrix}, \\ A^*\mathbf b &= \begin{pmatrix} 1 & -i & -1 \\ 1 & -1 & -i \end{pmatrix}\begin{pmatrix} 3 \\ 1 \\ 1 \end{pmatrix} = \begin{pmatrix} 2-i \\ 2-i \end{pmatrix}. \end{aligned}$ Vi ser hurtigt at determinanten af $A^*A$ er $\neq 0$ , så der er en entydig mindste kvadraters løsning. Vi kan med fordel anvende formlen for den inverse af en $2\times 2$ matrix:

$\begin{aligned} \mathbf x_0 &= (A^*A)^{-1}A^*\mathbf b = \begin{pmatrix} 3 & 1 \\ 1 & 3 \end{pmatrix}^{-1}\begin{pmatrix} 2-i \\ 2-i \end{pmatrix} \\ &= \frac{1}{8}\begin{pmatrix} 3 & -1 \\ -1 & 3 \end{pmatrix}\begin{pmatrix} 2-i \\ 2-i \end{pmatrix} = \frac{2-i}{4}\begin{pmatrix} 1 \\ 1 \end{pmatrix}. \end{aligned}$

En almindelig anvendelse af mindstre kvadraters løsninger er datafitting.

Den helt klassiske anvendelse af mindste kvadraters løsninger er at finde den bedste linje $y = \alpha t + \beta$ gennem nogle givne punkter

$(t_1, y_1), \quad (t_1, y_1), \quad \dots \quad, (t_n, y_n)$ i planen $\mathbb{R}^2$ .

At det oftest ikke er muligt at finde en perfekt linje, som går gennem alle punkterne kan oversættes til at ligningssystemet

$\begin{pmatrix} t_1 & 1\\ t_2 & 1\\ \vdots & \vdots\\ t_n & 1 \end{pmatrix} \begin{pmatrix} \alpha \\ \beta \end{pmatrix} = \begin{pmatrix} y_1 \\ y_2 \\ \vdots \\ y_n \end{pmatrix}$ ikke har løsninger. Her kan vi så arbejde med en mindste kvadraters løsning, som giver den bedste linje $y = \alpha t + \beta$ gennem punkterne i den forstand at summen af den vertikale kvadratafstand fra linjen til $y$ -erne

$(y_1 -\alpha t_1 -\beta)^2 + (y_2 -\alpha t_2 -\beta)^2 + \cdots + (y_n -\alpha t_n -\beta)^2$ bliver minimal.

Bedste fit af linje til tilfældige punkter fra Wikipedia.

Faktisk kunne vi ligeså godt have spurgt om den bedste parabel

$y = \alpha t^2 + \beta t + \gamma$ gennem punkterne

$(t_1, y_1), \quad (t_1, y_1), \quad \dots \quad, (t_n, y_n)$ i $\mathbb{R}^2$ . Dette ville med samme metode give os ligningssystemet

$\begin{pmatrix} t_1^2 & t_1 & 1\\ t_2 ^2 & t_2 & 1\\ \vdots & \vdots\\ t_n^2 & t_n & 1 \end{pmatrix} \begin{pmatrix} \alpha \\ \beta \\ \gamma \end{pmatrix} = \begin{pmatrix} y_1 \\ y_2 \\ \vdots \\ y_n \end{pmatrix}$ og mindste kvadraters løsningen til dette ligningssystem ville give den bedste parabel gennem punkterne med summen af den vertikale kvadratafstand fra parablen til punkterne minimeret.

Bedste fit af parabel til tilfældige punkter fra Wikipedia.

Helt generelt kan den samme metode bruges til at finde det bedste fit af et $m$ 'te gradspolynomium

$y = a_m t^m + a_{m-1} t^{m-1} + \cdots + a_1 t + a_0$ til en række punkter i planen.

For at gå endnu videre, kan man ved samme princip fitte givne funktioner $f_1,\dots,f_n$ til datapunkter i planen, ved at bruge

$y = \alpha_1 f_1(t) + \alpha_2 f_2(t) + \cdots + \alpha_n f_n(t).$ Den hovedsaglige antagelse er, at de ubekendte koefficienter $\alpha_1,\dots,\alpha_n$ indgår lineært i udtrykket.

10.4 Opgaver

Find den bedste mindste kvadraters linje $y = \alpha t + \beta$ gennem punkterne $(1, 2), (2,1)$ og $(4,3)$ ved at benytte Sætning 10.4.

En cirkel med centrum i $(a, b)$ og radius $r$ i planen har ligningen

$(x - a)^2 + (y - b)^2 = r^2. \tag{10.5}$

Gør rede for hvordan (10.5) kan omskrives til ligningen
$2 a x + 2 b y + c = x^2 + y^2, \tag{10.6}$ hvor $c = r^2 - a^2 - b^2$ .
Forklar hvordan (10.6) i mindste kvadraters kontekst leder frem til ligningssystemet
$\begin{pmatrix} 2 x_1 & 2 y_1 & 1\\ 2 x_2 & 2 y_2 & 1\\ \vdots &\vdots &\vdots\\ 2 x_n & 2 y_n & 1 \end{pmatrix} \begin{pmatrix} a \\ b \\ c \end{pmatrix} = \begin{pmatrix} x_1^2 + y_1^2\\ x_2^2 + y_2^2\\ \vdots \\ x_n^2 + y_n^2 \end{pmatrix},$ i forsøget på at tilpasse en cirkel til punkterne
$(x_1, y_1), (x_2, y_2), \dots, (x_n, y_n)$ i planen.
Find den bedste cirkel i mindste kvadraters forstand gennem punkterne
$(0, 2),\quad (0, 3),\quad (2,0)\quad\text{og}\quad (3, 1)$ ved at angive centrumkoordinaterne og radius med to decimaler.
Diskuter hvornår der går en entydig cirkel gennem tre givne punkter $(x_1, y_1), (x_2, y_2)$ og $(x_3, y_3)$ i henhold til egenskaber ved matricen
$\begin{pmatrix} 2 x_1 & 2 y_1 & 1\\ 2 x_2 & 2 y_2 & 1\\ 2 x_3 & 2 y_3 & 1 \end{pmatrix}.$
Kan man finde en cirkel gennem tre ikke-sammenfaldende punkter, som ligger på en linje?

(Eksamen januar 2021)

Lad $f$ være en funktion med forskrift

$f(t) = \alpha_1 (t^2 - 1) + \alpha_2 t + \alpha_3.$ Her er $\alpha_1,\alpha_2$ og $\alpha_3$ ubekendte reelle tal.

Opskriv et ligningssystem
$A\mathbf x = \mathbf b$ til bestemmelse af de ubekendte $\mathbf x = (\alpha_1,\alpha_2,\alpha_3)^{\textup{T}}$ , således at grafen for $f$ gennemløber følgende fire punkter i planen:
$(-1,0), \quad (0,4), \quad (1,-2), \quad (2,2).$
Lad en vektor $\mathbf v$ være givet ved
$\mathbf v = \begin{pmatrix} -1 \\ 3 \\ -3 \\ 1 \end{pmatrix}.$ Vis at $\mathbf v$ er ortogonal på søjlerne i $A$ , og vis at $\mathbf b = \mathbf u+\mathbf v$ hvor $\mathbf u$ er en af søjlerne i $A$ . Gør rede for hvorfor dette betyder at ligningssystemet $A\mathbf x = \mathbf b$ ikke har løsninger.
Beregn determinanten $\det(A^T A)$ , og vis at
$(A^T A)^{-1} = \frac{1}{\det(A^T A)}\begin{pmatrix} 20 & -20 & 0 \\ -20 & 36 & -8 \\ 0 & -8 & 24 \end{pmatrix}.$
Bestem tallene $\alpha_1$ , $\alpha_2$ og $\alpha_3$ som mindste kvadraters løsning til $A\mathbf x=\mathbf b$ .