10Mindste 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 (og nogle gange underbestemte) ligningssystemer. Metoden blev opfundet af Carl Friedrich 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$ har en løsning. 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 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å $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.

10.1 Normalligninger og mindste kvadraters løsning

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

For $m\times n$ matrix $A$ 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, ved vi at nulrummet er vigtigt for at kunne opskrive løsninger til et lineært ligningssystem. Det første vi indser er, at nulrummet for systemmatricen i normalligningerne er præcis det samme som i det oprindelige ligningssystem.

For enhver matrix $A$ er $\mathcal{N}(A^*A) = \mathcal{N}(A).$

Bevis

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

$\lvert A\mathbf y \rvert^2 = (A\mathbf y)\cdot(A\mathbf y) = (A^*A\mathbf y)\cdot\mathbf y = \mathbf 0\cdot\mathbf y = 0.$ Dette viser at $A\mathbf y = \mathbf 0,$ og derfor at $\mathbf y\in \mathcal{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. Hvis der rent faktisk er en sædvanlig løsning $\mathbf x_0$ til (10.2), 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å 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 et generelt lineært ligningssystemet $A\mathbf x=\mathbf b.$

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 \mathcal{N}(A).$
$A^*A$ er invertibel, hvis og kun hvis, nulrummet af $A$ er trivielt, dvs. $\mathcal{N}(A) = \{\mathbf 0\}.$ I så fald er den entydige mindste kvadraters løsning 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 \mathcal{N}(A^*)$ og $\widehat{\mathbf b}\in \mathcal{C}(A)$ (Sætning 9.33). Dette betyder blandt andet at $A^*\mathbf b = A^*\widehat{\mathbf b}.$

Det at $\widehat{\mathbf b}\in \mathcal{C}(A)$ betyder lige præcis, at der eksisterer en vektor $\mathbf x_0,$ 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), kan samtlige mindste kvadraters løsninger opskrives på formen $\mathbf x_0 + \mathbf y$ hvor $\mathbf y\in \mathcal{N}(A^*A),$ hvilket fra Lemma 10.3 er ensbetydende med $\mathbf y\in \mathcal{N}(A).$ Dette medfører både resultaterne i (ii) og (iii).

$\phantom{}$

Fra dimensionssætningen (Sætning 6.25) ved vi, at nulrummet for $A$ er trivielt, hvis og kun hvis, rangen af $m\times n$ matricen $A$ er lig $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 viden om 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å $\mathcal{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, 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.

$\mathbf x_0$ er en mindste kvadraters løsning til $A\mathbf x=\mathbf b,$ hvis og kun hvis, $\mathbf x_0$ opfylder

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

Bevis

Lad $A$ være en $m\times n$ matrix. Vi har at $\mathbf x_0$ er en mindste kvadraters løsning, hvis og kun hvis, $A\mathbf x_0 = \widehat{\mathbf b}$ hvor $\widehat{\mathbf b}$ er ortogonal projektionen af $\mathbf b$ på $\mathcal{C}(A).$ Fra Sætning 9.30 (og entydigheden for løsning af minimeringsproblemet i sætningen) ved vi, at dette er ensbetydende med

$\lvert \mathbf b-A\mathbf x_0 \rvert = \lvert\mathbf b-\widehat{\mathbf b}\rvert = \min\{\, \lvert\mathbf b-\widetilde{\mathbf b}\rvert : \widetilde{\mathbf b}\in \mathcal{C}(A) \,\}.$ $A$ afbilder hele $\mathbb{C}^n$ over på $\mathcal{C}(A),$ så vi kan erstatte $\widetilde{\mathbf b}\in \mathcal{C}(A)$ med $A\mathbf x$ hvor $\mathbf x\in \mathbb{C}^n$ :

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

I nogle sammenhænge bruges minimeringsproblemet i 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.$

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

$\lvert \mathbf{r} \rvert = \sqrt{\lvert r_1 \rvert^2+\dots+\lvert r_m \rvert^2},$ 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}^\textup{T} = \begin{pmatrix} 1 & -i & -1 \\ 1 & -1 & -i \end{pmatrix},$ hvilket giver

$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}$ og

$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}.$ 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 (4.12) 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 mindste kvadraters løsninger er data-fitting.

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_2, y_2), \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_2, y_2), \quad \dots, \quad (t_n, y_n).$ Dette ville med samme metode give os ligningssystemet

$\begin{pmatrix} t_1^2 & t_1 & 1\\ t_2 ^2 & t_2 & 1\\ \vdots & \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 giver 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.

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

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

Helt generelt, kan man ved samme princip fitte givne funktioner $f_1,\dots,f_m$ til datapunkter i planen, ved at bruge

$y = \alpha_1 f_1(t) + \alpha_2 f_2(t) + \cdots + \alpha_m f_m(t).$ Den hovedsaglige antagelse er, at de ubekendte $\alpha_1,\dots,\alpha_m$ 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.3}$

Gør rede for, hvordan (10.3) kan omskrives til ligningen
$2 a x + 2 b y + c = x^2 + y^2, \tag{10.4}$ hvor $c = r^2 - a^2 - b^2.$
Forklar hvordan (10.4) 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), \quad (x_2, y_2), \quad \dots, \quad (x_n, y_n).$
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 ret linje?

For $f(t) = b\mathrm{e}^{at},$ med ubekendte reelle tal $a$ og $b,$ vil vi gerne fitte $f$ til punkterne

$(-1, \mathrm{e}^{-1}), \quad (0, \mathrm{e}^{3}) \quad \text{og} \quad (1,\mathrm{e}^{5}).$

Hvorfor kan vi ikke direkte anvende mindste kvadraters metode, som beskrevet i dette kapitel?
Definer nu $g(t) = \log(f(t)),$ hvor $\log$ er den naturlige logaritme. Vis at
$g(t) = at + \log(b).$
Bestem $a$ og $b$ svarende til at fitte $f$ til punkterne ovenfor. Her skal vi udnytte funktionen $g,$ og først bestemme $a$ og $\log(b)$ ved at fitte $g$ til punkterne ovenfor, hvor $y$ -værdierne i punkterne ændres hvordan?

(Eksamen januar 2023)

Lad $f$ være en funktion med forskrift

$f(t) = \alpha_1 t + \alpha_2 (1-2^{\lvert t \rvert}).$ Her er $\alpha_1$ og $\alpha_2$ ubekendte reelle tal.

Opskriv et lineært ligningssystem
$A\mathbf x = \mathbf b$ med hensyn til de ubekendte $\mathbf x = (\alpha_1,\alpha_2)^{\textup{T}},$ således at grafen for $f$ gennemløber følgende fire punkter i planen:
$(-1,0), \quad (0,0), \quad (1,1), \quad (2,1).$ Det er et ligningssystem på formen (I skal udfylde de manglende værdier "?"):
$\begin{pmatrix} -1 & ? \\ 0 & ? \\ ? & ? \\ ? & ? \end{pmatrix}\begin{pmatrix} \alpha_1 \\ \alpha_2 \end{pmatrix} = \begin{pmatrix} ? \\ ? \\ 1 \\ 1 \end{pmatrix},$ så række $i=1,2,3,4$ tilpasser det $i$ 'te punkt nævnt ovenfor.
Lad en vektor $\mathbf v$ være givet ved
$\mathbf v = \begin{pmatrix} 1 \\ -4 \\ 5 \\ -2 \end{pmatrix}.$ Vis at $\mathbf v$ er ortogonal med de to søjler i $A,$ og at $\mathbf v$ ikke er ortogonal med $\mathbf b.$ På baggrund af dette, gør rede for at $A\mathbf x=\mathbf b$ ikke har løsninger.
Bestem tallene $\alpha_1$ og $\alpha_2$ som mindste kvadraters løsning til $A\mathbf x=\mathbf b.$
Bestem en ortonormalbasis (ONB) for $\mathbb{R}^2,$ bestående af egenvektorer for $A^\textup{T}A.$