7 Prikprodukter

Kommentarer/spørgsmål?

I planen $\mathbb{R}^2$ har vi stiftet bekendtskab med prikproduktet

$\begin{pmatrix} x_1 \\ x_2 \end{pmatrix} \cdot \begin{pmatrix} y_1 \\ y_2 \end{pmatrix} = x_1 y_1 + x_2 y_2$ for to vektorer. Ved hjælp af prikproduktet indførte vi begreber som længden af en vektor og ortogonalitet. Længden af en vektor $\mathbf u\in \mathbb{R}^2$ blev defineret som $\sqrt{\mathbf u\cdot \mathbf u}$ og to vektorer $\mathbf u, \mathbf v\in \mathbb{R}^2$ blev kaldt vinkelrette eller ortogonale hvis $\mathbf u\cdot \mathbf v = 0$ . I dette kapitel indfører vi den oplagte generalisering af prikproduktet fra planen $\mathbb{R}^2$ til vilkårlige søjlevektorer $\mathbb{R}^n$ ved

$\begin{pmatrix} x_1 \\ \vdots \\ x_n \end{pmatrix} \cdot \begin{pmatrix} y_1 \\ \vdots \\ y_n \end{pmatrix} = x_1 y_1 + \cdots + x_n y_n. \tag{7.1}$ Næsten alle definitioner fra $\mathbb{R}^2$ generaliserer. Læg mærke til at prikproduktet kan formuleres via matrixmultiplikationen

$\begin{pmatrix} x_1 \\ \vdots \\ x_n \end{pmatrix} \cdot \begin{pmatrix} y_1 \\ \vdots \\ y_n \end{pmatrix} = \begin{pmatrix} x_1 & \cdots & x_n\end{pmatrix} \begin{pmatrix} y_1 \\ \vdots \\ y_n \end{pmatrix}$ svarende til $\mathbf u\cdot \mathbf v = \mathbf u^T \mathbf v$ for to vektorer $\mathbf u, \mathbf v\in \mathbb{R}^n$ . For at udvide prikproduktet i (7.1) fra $\mathbb{R}^n$ til $\mathbb{C}^n$ kan man ikke overtage definitionen uden ændringer. For naturligt at kunne definere længden af en vektor $\mathbf u$ har vi brug for at $\mathbf u\cdot \mathbf u\geq 0$ . Dette er ikke opfyldt for $\mathbf u\in \mathbb{C}^n$ med definitionen i (7.1). Allerede for $n=1$ gælder $\mathbf u\cdot \mathbf u = -1$ med $\mathbf u=(i)$ . Heldigvis kan vi reparere denne defekt ret enkelt ved at benytte den konjugerede

$\bar{z} = x - i y$ til et komplekst tal $z = x + i y$ . Her er $z \bar{z} = x^2 + y^2 = |z|^2$ . Med disse forberedelser udvider prikproduktet til $\mathbb{C}^n$ som

$\begin{pmatrix} x_1 \\ \vdots \\ x_n \end{pmatrix} \cdot \begin{pmatrix} y_1 \\ \vdots \\ y_n \end{pmatrix} = x_1 \bar{y}_1 + \cdots + x_n \bar{y}_n,$ hvor indgangene i den anden vektor er konjugerede. Hvis for eksempel $\mathbf u = (a + b i, c + d i)^T\in \mathbb{C}^2$ , så vil $\mathbf u\cdot \mathbf u = a^2 + b^2 + c^2 + d^2$ og generelt kan man sige at $\mathbb{C}^n$ i denne forstand svarer til $\mathbb{R}^{2n}$ . Moralen i dette kapitel er at lineær algebra bliver væsentligt mere kraftfuldt (og spændende!), når vi har et prikprodukt at arbejde med.

Kommentarer/spørgsmål?

7.1 Definitioner og uligheder

For en $m\times n$ matrix $A$ med indgange i de komplekse tal defineres den komplekst konjugerede matrix $\bar{A}$ som matricen $A$ med indgangene konjugerede det vil sige

$\bar{A}_{ij} = \overline{A_{ij}}.$

Læg mærke til at $\bar{A} = A$ , hvis $A$ har indgange i de reelle tal. Vi er nu i stand til at generalisere næsten alle begreberne vi har for prikproduktet i planen.

Lad $\mathbf u, \mathbf v\in \mathbb{C}^n$ . Prikproduktet mellem $\mathbf u$ og $\mathbf v$ er defineret som

$\mathbf u\cdot \mathbf v = \mathbf u^T \bar{\mathbf v} = x_1 \bar{y}_1 + \cdots + x_n \bar{y}_n,$ for $\mathbf u = \begin{pmatrix} x_1 \\ \vdots \\ x_n \end{pmatrix}$ og $\mathbf v = \begin{pmatrix} y_1 \\ \vdots \\ y_n \end{pmatrix}.$

Vektorerne $\mathbf u$ og $\mathbf v$ kaldes vinkelrette eller ortogonale og betegnes $\mathbf u \perp \mathbf v$ , hvis
$\mathbf u\cdot \mathbf v = 0.$
Længden af $\mathbf u$ er defineret som
$|\mathbf u| = \sqrt{\mathbf u\cdot \mathbf u}.$
En vektor $\mathbf u$ kaldes en enhedsvektor hvis $|\mathbf u| = 1$ .

Quiz

Hvilke af nedenstående udsagn er rigtige, når prikproduktet er defineret som i Definition 7.2?

Hvis $\mathbf u, \mathbf v\in \mathbb{R}^n$ er

$\mathbf u\cdot \mathbf v = \mathbf u^T \mathbf v.$

$\begin{pmatrix} 1 \\ i \end{pmatrix}\cdot \begin{pmatrix} 1 \\ i \end{pmatrix} = 0.$

$\begin{pmatrix} 1 \\ i \end{pmatrix}\cdot \begin{pmatrix} 1 \\ i \end{pmatrix} = 2.$

$\begin{pmatrix} 1 \\ 2 \end{pmatrix}\cdot \begin{pmatrix} 3 \\ 4 \end{pmatrix} = 11.$

$\overline{ \begin{pmatrix} 1 - i & -i\\ \\ 1 - i & -i \end{pmatrix}} = \begin{pmatrix} 1 + i & i \\ \\ -1 + i & -i \end{pmatrix}.$

$\overline{ \begin{pmatrix} 1 - i & -i\\ \\ 1 - i & i \end{pmatrix}} = \begin{pmatrix} 1 + i & i \\ \\ 1 + i & -i \end{pmatrix}.$

For to matricer $A$ og $B$ , hvor matrixproduktet $A B$ giver mening gælder

$\overline{A B} = A \bar{B}.$

For to matricer $A$ og $B$ , hvor matrixproduktet $A B$ giver mening gælder

$\overline{A B} = \bar{A} \bar{B}.$

Lad $\mathbf u, \mathbf v, \mathbf w\in \mathbb{C}^n$ og $\lambda\in \mathbb{C}$ . Så gælder

$(\lambda \mathbf u)\cdot \mathbf v = \lambda (\mathbf u\cdot \mathbf v)$
$\mathbf u\cdot (\lambda \mathbf v) = \bar \lambda (\mathbf u\cdot \mathbf v)$
$\mathbf u\cdot (\mathbf v+\mathbf w) = \mathbf u\cdot \mathbf v + \mathbf u\cdot \mathbf w$
$\mathbf u\cdot \mathbf v = \overline{\mathbf v\cdot \mathbf u}$
$\mathbf u\cdot \mathbf u \geq 0$ og $\mathbf u\cdot \mathbf u=0$ hvis og kun hvis $\mathbf u=0$ .

Bevis

Med prikproduktet defineret som $\mathbf u\cdot \mathbf v = \mathbf u^T \bar{\mathbf v}$ følger resultaterne af regneregler for matrixmultiplikation og konjugering af komplekse tal og overlades til læseren.

Ud fra kun definitionen af prikproduktet kan vi lave overraskende meget nyttig matematik, bland andet nedenstående resultat, som kaldes Cauchy-Schwarz ulighed

Lad $\mathbf u, \mathbf v\in \mathbb{C}^n$ . Så gælder

Bevis

Med det komplekse prikprodukt $\mathbf u\cdot \mathbf v = \mathbf u^T \bar{\mathbf v}$ har vi

$\begin{aligned} 0\leq (\mathbf u+\lambda \mathbf v)\cdot (\mathbf u + \lambda \mathbf v) &= |\mathbf u|^2 + \mathbf u\cdot (\lambda \mathbf v) + (\lambda\mathbf v)\cdot \mathbf u + |\lambda|^2 |\mathbf v|^2\\ &=|\mathbf u|^2 + \mathbf u\cdot (\lambda \mathbf v) + \overline{\mathbf u\cdot (\lambda \mathbf v)} + |\lambda|^2 |\mathbf v|^2\\ &= |\mathbf u|^2 + 2 \mathrm{Re\,} \mathbf u\cdot (\lambda \mathbf v) + |\lambda|^2 |\mathbf v|^2\\ &= |\mathbf u|^2 + 2 \mathrm{Re\,} \bar{\lambda} (\mathbf u\cdot \mathbf v) + |\lambda|^2 |\mathbf v|^2, \end{aligned}\tag{7.2}$ for et vilkårligt komplekst tal $\lambda$ , fordi $z + \bar{z} = 2 \mathrm{Re\,}(z)$ for et komplekst tal $z$ . Hvis $|\mathbf v|\neq 0$ kan vi indsætte

$\lambda = -\frac{\mathbf u\cdot \mathbf v}{|\mathbf v|^2}$ i (7.2) og få

$0\leq | \mathbf u+\lambda \mathbf v| ^2=|\mathbf u|^2 - 2\frac{|\mathbf u\cdot \mathbf v|^2}{|\mathbf v|^2}+\frac{|\mathbf u\cdot \mathbf v|^2|\mathbf v|^2}{|\mathbf v|^4}= |\mathbf u|^2 - \frac{|\mathbf u\cdot \mathbf v|^2}{|\mathbf v|^2}, \tag{7.3}$ hvoraf uligheden følger. Vi skal nu overveje hvornår denne ulighed faktisk er en lighed.

$\phantom{phantom}$ Hvis $\mathbf v=\mathbf 0$ gælder lighed, og også at $\mathbf u,\mathbf v$ er lineært afhængige.

$\phantom{phantom}$ Vi kan altså antage at $\mathbf v\neq \mathbf 0$ . Hvis $\mathbf u,\mathbf v$ er lineært afhængige kan vi skrive $\mathbf u=\lambda \mathbf v$ for $\lambda\in \mathbb{C}$ . Da er

$|\mathbf u\cdot\mathbf v|=|\lambda|\cdot|\mathbf v|^2=|\lambda \mathbf v|\cdot|\mathbf v|=|\mathbf u|\cdot|\mathbf v|$ så at vi har lighed. Antag omvendt at $|\mathbf u\cdot\mathbf v|=|\mathbf u|\cdot|\mathbf v|$ . Da $\mathbf v\neq\mathbf 0$ kan vi dividere med $|\mathbf v|^2$ , så at vi kan definere $\lambda = -\frac{\mathbf u\cdot \mathbf v}{|\mathbf v|^2}$ . Ifølge (7.3) er $|\mathbf u + \lambda \mathbf v|^2=0$ så at $\mathbf u = -\lambda \mathbf v$ . Altså er $\mathbf u$ et multiplum af $\mathbf v$ .

Opgave

Lad $x_1, \ldots, x_n\in \mathbb{R}$ . Prøv at bevise

$(x_1 + x_2 + \cdots +x_n)^2 \leq n (x_1^2 + x_2^2 + \cdots + x_n^2)$ uden at bruge Sætning 7.5. Lykkedes det? Hvis ikke, prøv med.

Eksempel

Cauchy-Schwarz ulighed giver at

$-1 \leq \frac{u\cdot \mathbf v}{|\mathbf u|\, |\mathbf v|} \leq 1$ for to vektorer $\mathbf u, \mathbf v\in \mathbb{R}^n$ og det giver mening at definere vinklen $\theta$ mellem dem ud fra

$\cos(\theta) = \frac{\mathbf u \cdot \mathbf v}{|\mathbf u|\, |\mathbf v|}.$ Dette tal benyttes under betegnelsen cosine similarity ofte som et mål for korrelationen mellem to datasæt givet i form af de to vektorer $\mathbf u$ og $\mathbf v$ . For eksempel kan man benytte det som et mål for ligheden mellem to tekster. Lad os som eksempel se på to tekster

Matematik er sjovt og lineær algebra er anvendeligt
Matematik er morsomt og lineær algebra er brugbart

Ud fra ordene i de to tekster laver vi følgende to vektorer i $\mathbb{R}^9$ :

Matematik	1	1
er	2	2
sjovt	1	0
morsomt	0	1
og	1	1
lineær	1	1
algebra	1	1
anvendeligt	1	0
brugbart	0	1

\floatbarrier hvor hvert ord i de to tekster har en koordinat, som tæller antal forekomster af ordet i teksten. Et mål for ligheden mellem de to tekster er cosinus til vinklen mellem de to vektorer. Jo tættere cosinus til vinklen kommer på $1$ (svarende til en vinkel på $0$ grader), jo tættere anser vi de to tekster at være på hinanden. I ovenstående tilfælde er $\cos(\theta) = 0.8$ .

Ud fra Cauchy-Schwarz ulighed kan vi udlede trekantsuligheden.

For to vektorer $\mathbf u, \mathbf v\in \mathbb{C}^n$ gælder

$|\mathbf u + \mathbf v| \leq |\mathbf u| + |\mathbf v|.$ Lighedstegnet gælder hvis og kun hvis $\mathbf u = \mu \mathbf v$ for $\mu \geq 0\in \mathbb{R}$ .

Bevis

Beviset følger af Sætning 7.5 på følgende måde:

$\begin{aligned} |\mathbf u+\mathbf v|^2 &= (\mathbf u+\mathbf v)\cdot (\mathbf u+\mathbf v) = |\mathbf u|^2 + |\mathbf v|^2 + 2 \mathrm{Re\,} \mathbf u\cdot \mathbf v\\ &\leq |\mathbf u|^2 + |\mathbf v|^2 + 2 |\mathbf u\cdot \mathbf v|\\ &\leq |\mathbf u|^2 + |\mathbf v|^2 + 2 |\mathbf u| |\mathbf v| = (|\mathbf u| + |\mathbf v|)^2. \end{aligned}$ Ved lighedstegn må begge de to uligheder være ligheder, så at

$\mathrm{Re\,} \mathbf u\cdot \mathbf v=|\mathbf u\cdot \mathbf v|$
$|\mathbf u\cdot \mathbf v| = |\mathbf u| |\mathbf v|$

Ifølge (β) og Sætning 7.5 må $\mathbf u = \mu \mathbf v$ for et $\mu\in \mathbb{C}$ . Ved at kigge nærmere på beviset, ser vi at

$\mu=\frac{\mathbf u\cdot\mathbf v}{|\mathbf v| ^2}.$ Vi sætter dette ind i (α):

$\mathrm{Re\,} \mathbf u\cdot \mathbf v=|\mathbf u\cdot \mathbf v|=|\mu|\cdot|\mathbf v|^2=|\mathbf u\cdot \mathbf v|.$ Men hvis $z=a+bi$ er et komplekst tal og $a=\mathrm{Re\,} z = |z|=\sqrt{a^2+b^2}$ så er $b=0$ og $a\geq 0$ , så $\mathbf u\cdot \mathbf v\in \mathbb{R}$ med $\mathbf u\cdot \mathbf v\geq 0$ . Dermed er

$\mu=\frac{\mathbf u\cdot\mathbf v}{|\mathbf v| ^2}>0$

7.2 Matricer og prikproduktet

Prikproduktet giver anledning til at indføre nogle vigtige klasser af matricer. Først en vigtig definition for komplekse matricer.

Den konjugerede transponerede $A^*$ af en $m\times n$ matrix $A$ med komplekse indgange er defineret som

$A^* = \bar{A}^T$ det vil sige $A^*_{ij} = \bar{A}_{ji}$ for $i = 1, \ldots, n$ og $j=1,\ldots, m$ . Matricen $A$ kaldes hermitesk hvis

$A = A^*.$ En hermitesk matrix med reelle indgange kaldes symmetrisk.

For eksempel er

$A^* = \begin{pmatrix} -i & 1\\ 1 - i & i \end{pmatrix}\qquad\mathrm{for}\qquad A = \begin{pmatrix} i & 1 + i\\ 1 & -i \end{pmatrix}.$ Læg også mærke til at $B^* = B^T$ hvis og kun hvis $B$ har reelle tal som indgange, netop fordi $z = \bar{z}$ gælder hvis og kun hvis $z\in \mathbb{R}$ . En symmetrisk matrix $B$ opfylder altså også at $B=B^T$ .

Quiz

Hvilke af nedenstående udsagn er rigtige?

En hermitesk matrix er kvadratisk.

En hermitesk matrix kan godt have det komplekse tal $2+3i$ som indgang i diagonalen.

$H = \begin{pmatrix} i & 1 + i\\ 1 & -i \end{pmatrix}$ er en hermitesk matrix.

$H^* H$ er en hermitesk matrix.

$\begin{pmatrix} 1 & 2\\ 2 & 1 \end{pmatrix}$ er en hermitesk matrix.

$\begin{pmatrix} 1 & 2\\ 3 & 1 \end{pmatrix}$ er en hermitesk matrix.

7.2.1 Egenværdier og egenvektorer for hermiteske matricer

Nedenstående resultat viser hvordan prikproduktet opfører sig under matrixmultiplikation på en af vektorerne. Beviserne for formlerne gør brug af formlen $(A B)^T = B^T A^T$ for matricer $A$ og $B$ hvor produktet $A B$ giver mening.

Hvis en $n\times n$ matrix $A$ opfylder at
$\mathbf u\cdot (A \mathbf v) = \mathbf u\cdot \mathbf v$ for alle $\mathbf u, \mathbf v\in \mathbb{R}^n$ (eller $\mathbb{C}^n$ ) så må $A = I_n$ .
Hvis $A$ er en $n\times n$ matrix med reelle indgange, så gælder
$(A \mathbf u)\cdot \mathbf v = \mathbf u \cdot (A^T \mathbf v)$ for prikproduktet på $\mathbb{R}^n$ .
Hvis $A$ er en $n\times n$ matrix med komplekse indgange, så gælder
$(A \mathbf u)\cdot \mathbf v = \mathbf u \cdot (A^* \mathbf v)$ for prikproduktet på $\mathbb{C}^n$ .

Bevis

Påstanden i (α) følger af at

$\mathbf e_i\cdot (A \mathbf e_j) = A_{ij},$ hvor $\mathbf e_1, \ldots, \mathbf e_n$ er standardbasen for $\mathbb{R}^n$ (eller $\mathbb{C}^n$ ). Påstanden i (β) følger af udregningen

$(A \mathbf u)\cdot \mathbf v = (A \mathbf u)^T \mathbf v = (\mathbf u^T A^T) \mathbf v = \mathbf u^T (A^T \mathbf v) = \mathbf u\cdot (A^T \mathbf v).$ Påstanden i (γ) følger på den samme måde af udregningen

$(A \mathbf u)\cdot \mathbf v = (A \mathbf u)^T \bar{\mathbf v} = (\mathbf u^T A^T) \bar{\mathbf v} = \mathbf u^T (A^T \bar{\mathbf v}) = \mathbf u^T(\overline{\overline{A}^T \mathbf v}) = \mathbf u \cdot (A^* \mathbf v).$

En ekstremt vigtig observation er at selvom hermiteske matricer generelt har komplekse tal som indgange så er deres egenværdier reelle tal og egenvektorer hørende til forskellige egenværdier er ortogonale. Dette er en meget stærk anvendelse af prikproduktet og faktisk er beviset slet ikke så svært.

Lad $A$ være en hermitesk matrix og $\lambda$ en egenværdi for $A$ . Så er $\lambda$ reel. Lad $\mu$ være en egenværdi for $A$ med $\mu \neq \lambda$ . Hvis $\mathbf u$ er en egenvektor hørende til $\mu$ og $v$ en egenvektor hørende til $\lambda$ , så gælder

$\mathbf u\cdot \mathbf v = 0.$ Det vil sige at egenvektorer hørende til forskellige egenrum for $A$ er ortogonale.

Bevis

For en egenvektor $\mathbf v$ hørende til $\lambda$ har vi

$\lambda (\mathbf v\cdot \mathbf v) = (A \mathbf v)\cdot \mathbf v = \mathbf v\cdot (A^* \mathbf v) = \mathbf v\cdot (A \mathbf v) = \mathbf v\cdot (\lambda \mathbf v) = \bar{\lambda} (\mathbf v\cdot \mathbf v).$ Dermed er $\lambda = \bar{\lambda}$ og vi må have $\lambda\in \mathbb{R}$ , fordi $\mathbf v\neq 0$ og dermed $\mathbf v\cdot \mathbf v \neq 0$ Samme type argument giver ortogonaliteten af egenvektorerne $\mathbf u$ og $\mathbf v$ :

$\mu (\mathbf u\cdot \mathbf v) = (A \mathbf u)\cdot \mathbf v = \mathbf u\cdot (A \mathbf v) = \lambda (\mathbf u\cdot \mathbf v).$ Denne identitet medfører ligningen

$(\mu-\lambda) (\mathbf u\cdot \mathbf v) = 0,$ hvoraf $\mathbf u\cdot \mathbf v = 0$ , da $\mu\neq \lambda$ .

Faktisk er det ret utroligt at hvis man stanger en vilkårlig symmetrisk matrix som for eksempel

$\begin{pmatrix} 1 & 3 & 7 & 5\\ 3 & 1 & 2 & 4\\ 7 & 2 & 2 & 6\\ 5 & 4 & 6 & 1 \end{pmatrix}$ ud, at dens karakteristiske polynomium kun kan have reelle rødder. Det er en af konsekvenserne af Sætning 7.13. At vise at en hermitesk matrix faktisk har en egenværdi overhovedet er mere kompliceret. Her bliver vi nødt til at henvise til algebraens fundamentalsætning, som siger at ethvert polynomium af grad $\geq 1$ har en kompleks rod.

Kommentarer/spørgsmål?

Opgave

Gør helt eksplicit rede for at en symmetrisk $2\times 2$ matrix

$\begin{pmatrix} a & b\\ b & c \end{pmatrix},$ med $a, b, c\in \mathbb{R}$ faktisk har reelle egenværdier.

7.2.2 Ortogonale og unitære matricer

Ud fra Proposition 7.12 fremkommer følgende resultat.

Hvis $A$ er en $n\times n$ matrix med reelle indgange og
$(A \mathbf u) \cdot (A \mathbf v) = \mathbf u\cdot \mathbf v$ for alle $\mathbf u, \mathbf v\in\mathbb{R}^n$ , så må $A^T A = I_n$ .
Hvis $A$ er en $n\times n$ matrix med komplekse indgange og
$(A \mathbf u) \cdot (A \mathbf v) = \mathbf u\cdot \mathbf v$ for alle $\mathbf u, \mathbf v\in\mathbb{C}^n$ , så må $A^* A = I_n$ .

Matricer, som bevarer prikproduktet i ovenstående forstand, er så vigtige at de har specielle navne.

En $n\times n$ matrix $Q$ med reelle indgange kaldes ortogonal hvis
$Q^T Q = I_n.$
En $n\times n$ matrix $U$ med komplekse indgange kaldes unitær hvis
$U^* U = I_n.$

En $n\times n$ matrix er ortogonal/unitær netop når dens søjler er ortogonale enhedsvektorer med hensyn til prikproduktet.

Bevis

Dette følger af definitionen på matrixmultiplikation opfattet på følgende måde. Lad $A$ og $B$ være reelle $n\times n$ matricer og lad $\mathbf b_1, \ldots, \mathbf b_n$ være søjlerne i $B$ . Så er søjlerne i $A B$ netop

$A \mathbf b_1, \ldots, A \mathbf b_n.$ Altså er søjlerne i $B^T B$ netop $B^T \mathbf b_i$ og dermed er

$(B^T B)_{ij} = (B^T)^i B_j = \mathbf b_i\cdot \mathbf b_j.$ Hvis $B$ er en kompleks matrix, så er tilsvarende indgangene i $B^* B$ netop $\mathbf b_i\cdot \mathbf b_j$ (med det komplekse prikprodukt).

Eksempel

Lad os analysere hvordan en ortogonal $2\times 2$ matrix $Q$ tager sig ud. Antag at
$Q = \begin{pmatrix} a & b\\ c & d \end{pmatrix}.$ Så er
$Q^T Q = \begin{pmatrix} a & c\\ b & d \end{pmatrix} \begin{pmatrix} a & b\\ c & d \end{pmatrix} = \begin{pmatrix} a^2 + c^2 & a b + c d\\ a b + d c & b^2 + d^2 \end{pmatrix} = \begin{pmatrix} 1 & 0\\ 0 & 1 \end{pmatrix}.$ Derfor er søjlevektorerne i $Q$ ortogonale enhedsvektorer. Sætter vi $a = \cos(\theta)$ og $c = \sin(\theta)$ har vi altså to muligheder for $Q$ :
$Q_1 = \begin{pmatrix} \cos(\theta) & -\sin(\theta)\\ \sin(\theta) & \phantom{-}\cos(\theta) \end{pmatrix}\qquad\mathrm{og}\qquad Q_2 = \begin{pmatrix} \cos(\theta) & \phantom{-}\sin(\theta)\\ \sin(\theta) & -\cos(\theta) \end{pmatrix}.$ Geometrisk svarer $Q_1$ til en drejning af planen, mens $Q_2$ svarer til en spejling. Ved eksplicit udregning ser man at $1$ er en egenværdi for $Q_2$ . En tilhørende egenvektor er retningsvektor for linjen, som der spejles i (som viser sig at være linjen gennem $(0,0)$ med vinklen $\theta/2$ med $x$ -aksen).
En unitær $1\times 1$ matrix er netop et komplekst tal $z$ med $z \bar{z} = 1$ . Det vil sige $z = e^{i \theta}$ for en passende vinkel $\theta$ . For to komplekse tal $a, b\in \mathbb{C}$ med $|a|^2+|b|^2 = 1$ er
$U = \begin{pmatrix} a & b\\ -\bar{b} & \bar{a} \end{pmatrix}$ et eksempel på en unitær $2\times 2$ matrix. Her kan man for eksempel benytte
$\begin{aligned} a &= e^{i\varphi_1} \cos \theta\\ b &= e^{i\varphi_2} \sin \theta \end{aligned}$ for vilkårlige vinkler $\theta, \varphi_1, \varphi_2$ . For eksempel er
$\begin{pmatrix} \frac{1}{2} + \frac{1}{2} i & \frac{1}{2} + \frac{1}{2} i\,\, \\ \\ -\frac{1}{2} + \frac{1}{2} i & \frac{1}{2} - \frac{1}{2} i\,\, \end{pmatrix}$ en unitær $2\times 2$ matrix svarende til $\theta = \varphi_1 = \varphi_2 = \pi/4$ . Tre berømte unitære og hermiteske matricer er
$\begin{pmatrix} 0 & 1\\ 1 & 0 \end{pmatrix},\qquad \begin{pmatrix} 0 & -i\\ i & 0 \end{pmatrix}\qquad\mathrm{og}\qquad \begin{pmatrix} 1 & 0\\ 0 & -1 \end{pmatrix}.$ I kapitlet om anvendelser vil prøve på at forklare hvorfor disse matricer er så berømte.

Quiz

Hvilke af nedenstående udsagn er rigtige?

Determinanten af en ortogonal matrix kan være alle tal $\neq 0$ .

Determinanten af en ortogonal matrix er enten $1$ eller $-1$ .

Matricen, som repræsenterer en rotation omkring en akse gennem $0$ i $\mathbb{R}^3$ med hensyn til den naturlige basis er en ortogonal matrix.

Matricen

$\begin{pmatrix} 1 & 0 & 0\\ 0 & \cos(\theta) & -\sin(\theta)\\ 0 & \sin(\theta) & \phantom{-}\cos(\theta) \end{pmatrix}$ er ortogonal for en vinkel $\theta$ .

7.3 Anvendelser af ortogonalitet

At have et prikprodukt giver sig specielt udslag i udregningen af baser for underrum. Pæne baser består af ortogonale vektorer. Den første indikation på at ortogonale vektorer opfører sig specielt pænt kommer her.

Hvis $\mathbf v_1, \ldots, \mathbf v_m\in \mathbb{C}^n$ er vektorer med $\mathbf v_i\neq 0$ og $\mathbf v_i \perp \mathbf v_j$ for $i\neq j$ og $i, j = 1, \ldots, m$ , så er $\mathbf v_1, \ldots, \mathbf v_m$ lineært uafhængige det vil sige hvis

$\lambda_1 \mathbf v_1 + \cdots + \lambda_m \mathbf v_m = 0$ for $\lambda_1, \ldots, \lambda_m\in \mathbb{C}$ så medfører det $\lambda_1 = \cdots = \lambda_m = 0$ .

Bevis

Lad

$\mathbf v = \lambda_1 \mathbf v_1 + \cdots + \lambda_m \mathbf v_m.$ Så vil

$\begin{aligned} \mathbf v \cdot \mathbf v_i &= (\lambda_1 \mathbf v_1 + \cdots + \lambda_m \mathbf v_m)\cdot \mathbf v_i\\ &= \lambda_1 (\mathbf v_1 \cdot \mathbf v_i) + \cdots + \lambda_i (\mathbf v_i\cdot \mathbf v_i) + \cdots + \lambda_n (\mathbf v_n \cdot \mathbf v_i)\\ &= \lambda_i (\mathbf v_i\cdot \mathbf v_i) = \lambda_i |\mathbf v_i|^2 = 0, \end{aligned}$ hvilket medfører at $\lambda_i=0$ for alle $i=1, \ldots, m$ , fordi $\mathbf v_i\neq \mathbf 0$ .

7.3.1 Ortogonal- og ortonormalbaser

Lad $V$ være et underrum i $\mathbb{C}^n$ . En basis $(\mathbf u_1, \ldots, \mathbf u_m)$ for $V$ kaldes en ortogonalbasis, hvis $\mathbf u_i\cdot \mathbf u_j = 0$ for $i\neq j$ . Hvis alle vektorerne i en ortogonalbasis er enhedsvektorer kaldes basen en ortonormalbasis.

Et naturligt eksempel på en ortonormalbasis for $\mathbb{R}^n$ består af standardbasisvektorerne

$\begin{pmatrix} 1 \\ 0 \\ \vdots \\ 0\end{pmatrix}, \begin{pmatrix} 0 \\ 1 \\ \vdots \\ 0\end{pmatrix}, \ldots, \begin{pmatrix} 0 \\ 0 \\ \vdots \\ 1\end{pmatrix},$ men der er masser af andre spændende ortonormalbaser. Nedenstående resultat viser at en ortonormalbasis opfører sig ligesom den kanoniske basis i to vigtige henseender.

Lad $\mathbf e_1, \ldots, \mathbf e_m$ være en ortonormal basis for et underrum $V$ og lad $\mathbf v\in V$ . Så er

$\mathbf v = (\mathbf v\cdot \mathbf e_1) \mathbf e_1 + \cdots + (\mathbf v\cdot \mathbf e_m) \mathbf e_m.$
$|\mathbf v|^2 = |\mathbf v\cdot \mathbf e_1|^2 + \cdots + |\mathbf v\cdot \mathbf e_m|^2$

Bevis

Vi ved at

$\mathbf v = x_1 \mathbf e_1 + \cdots + x_m \mathbf e_m$ for entydigt bestemte $x_i$ . Nu følger

$\mathbf v\cdot \mathbf e_i = (x_1 \mathbf e_1 + \cdots + x_m \mathbf e_m)\cdot \mathbf e_i = x_1 (\mathbf e_1\cdot \mathbf e_i) + \cdots + x_i (\mathbf e_i \cdot \mathbf e_i) +\cdots + x_m (\mathbf e_m \cdot \mathbf e_i) = x_i,$ hvilket viser første påstand, fordi $\mathbf e_i\cdot \mathbf e_j = 0$ for $i\neq j$ og $\mathbf e_i\cdot \mathbf e_i = 1$ . Den anden påstand følger af regneregler for prikproduktet:

$|\mathbf v|^2 = \mathbf v\cdot \mathbf v = (x_1 \mathbf e_1 + \cdots + x_m \mathbf e_m)\cdot (x_1 \mathbf e_1 + \cdots + x_m \mathbf e_m) = x_1^2 + \cdots + x_m^2,$ hvor vi på samme måde har benyttet at $\mathbf e_i\cdot \mathbf e_j = 0$ for $i\neq j$ og $\mathbf e_i\cdot \mathbf e_i = 1$ .

Eksempel

De tre vektorer

$\mathbf v_1 = \begin{pmatrix} -\frac{1}{\sqrt{2}}\,\,\\ \\ \phantom{-}\frac{1}{\sqrt{2}}\\ \\ 0\\ \\ 0 \end{pmatrix},\quad \mathbf v_2 = \begin{pmatrix} \frac{1}{2}\\ \\ \frac{1}{2}\\ \\ \frac{1}{2}\\ \\ \frac{1}{2} \end{pmatrix},\quad\mathrm{og}\quad \mathbf v_3 = \begin{pmatrix} -\frac{1}{2}\,\\ \\ -\frac{1}{2}\\ \\ \phantom{-}\frac{1}{2}\\ \\ \phantom{-}\frac{1}{2} \end{pmatrix}$ udgør en ortonormal basis for deres span $V = \mathrm{span}(\mathbf v_1, \mathbf v_2, \mathbf v_3)$ i $\mathbb{R}^4$ . Det er nu under brug af Proposition 7.22 specielt nemt at afgøre om en forelagt vektor $\mathbf u\in \mathbb{R}^4$ ligger i $V$ . Dette sker hvis og kun hvis

$\mathbf u = (\mathbf u\cdot \mathbf v_1) \mathbf v_1 + (\mathbf u\cdot \mathbf v_2) \mathbf v_2 + (\mathbf u\cdot \mathbf v_3) \mathbf v_3.$ Hvis for eksempel

$\mathbf u = \begin{pmatrix} 1 \\ 1 \\ 2 \\ 1 \end{pmatrix}$ er

$(\mathbf u\cdot \mathbf v_1) \mathbf v_1 + (\mathbf u\cdot \mathbf v_2) \mathbf v_2 + (\mathbf u\cdot \mathbf v_3) \mathbf v_3 = \tfrac{5}{2}\, \mathbf v_2 + \tfrac{1}{2}\, \mathbf v_3 = \begin{pmatrix} 1\\ \\ 1\\ \\ \frac{3}{2}\\ \\ \frac{3}{2} \end{pmatrix}$ og det fremgår at $\mathbf u\notin V$ . Derimod har vi med

$\mathbf u' = \begin{pmatrix} 0 \\ 0 \\ 1 \\ 1 \end{pmatrix}$ at

$\mathbf u' = (\mathbf u'\cdot \mathbf v_1) \mathbf v_1 + (\mathbf u'\cdot \mathbf v_2) \mathbf v_2 + (\mathbf u'\cdot \mathbf v_3) \mathbf v_3 = \mathbf v_2 + \mathbf v_3$ det vil sige $\mathbf u'\in V$ .

Quiz

Lad $V$ være underrummet i $\mathbb{R}^3$ med en basis $B$ bestående af vektorerne

$\mathbf v_1 = \begin{pmatrix} 1\\ 2\\ 1 \end{pmatrix}\quad\mathrm{og}\quad \mathbf v_2 = \begin{pmatrix} -1\\ \phantom{-}1\\ -1 \end{pmatrix}.$ Hvilke af nedenstående udsagn er rigtigt?

$B$ er en ortogonalbasis for $V$ .

$B$ er en ortonormalbasis for $V$ .

$V = \mathbb{R}^3$ .

$\left(\tfrac{1}{\sqrt{6}}\, \mathbf v_1, \tfrac{1}{\sqrt{3}}\, \mathbf v_2\right)$ er en ortonormalbasis for $V$ .

$\begin{pmatrix} 1\\ 1\\ 1 \end{pmatrix}\in V.$

7.3.2 Gram-Schmidt algoritmen

Vi har set ovenfor at ortonormalbaser for underrum er specielt nemme at regne med. Spørgsmålet er om alle underrum har en ortonormalbasis. Her er svaret ja og grunden ligger i en klassisk og smuk algoritme tilmed opfundet af en dansker. Ideen kommer fra formlen for projektion af en vektor på en anden i planen. Lad os kaste et blik igen på tegningen

som forekom i Kapitel 1 i forbindelse med formlen for projektion af en vektor på en anden vektor. Givet to vektorer $\mathbf u, \mathbf v$ med $\mathbf v\neq 0$ fandt vi ud af at hvis et tal $\lambda$ opfylder

$\mathbf u - \lambda \mathbf v \perp \mathbf v, \tag{7.4}$ så må

$\lambda = \frac{\mathbf u\cdot \mathbf v}{|\mathbf v|^2}.$ Argumentet for dette var løsning af en førstegradsligning! Her er førstegradsligningen, som kommer fra betingelsen (7.4) og hvis løsning er ovenstående $\lambda$ :

$(\mathbf u - \lambda \mathbf v)\cdot \mathbf v = (\mathbf u\cdot \mathbf v) - \lambda (\mathbf v\cdot \mathbf v) = (\mathbf u\cdot \mathbf v) - \lambda |\mathbf v|^2=0.$ Læg mærke til at disse udregninger er fuldstændigt uafhængige af om vi regner i de reelle eller komplekse tal.

Teknikken ovenfor kan benyttes til at omforme to vektorer $\mathbf v_1, \mathbf v_2\in \mathbb{C}^n$ til to vektorer

$\begin{aligned} \mathbf u_1 &= \mathbf v_1\\ \mathbf u_2 &= \mathbf v_2 - \frac{\mathbf v_1\cdot \mathbf v_2}{|\mathbf v_1|^2} \mathbf v_1 \end{aligned}$ så $\mathbf u_1$ er ortogonal på $\mathbf u_2$ samt

$\mathrm{span}(\mathbf v_1, \mathbf v_2) = \mathrm{span}(\mathbf u_1, \mathbf u_2).$ Man kan endda gå et skridt videre med tre eller flere vektorer: Lad os antage for tre vektorer $\mathbf v_1, \mathbf v_2, \mathbf v_3$ at $\mathbf v_1$ og $\mathbf v_2$ allerede er ortogonale det vil sige $\mathbf v_1\cdot \mathbf v_2 = 0$ . Kan vi erstatte $\mathbf v_3$ med en vektor $\mathbf u_3$ i $\mathrm{span}(\mathbf v_1, \mathbf v_2, \mathbf v_3)$ så $\mathbf u_3$ bliver ortogonal på $\mathbf v_1$ og $\mathbf v_2$ ? Med input fra tilfældet med to vektorer viser formlen sig at blive

$\mathbf u_3 = \mathbf v_3 - \frac{\mathbf v_3\cdot \mathbf v_1}{|\mathbf v_1|^2}\, \mathbf v_1 - \frac{\mathbf v_3\cdot \mathbf v_2}{|\mathbf v_2|^2}\, \mathbf v_2.$ Det overlades som en øvelse at indse at $\mathbf u_3\cdot \mathbf v_1 = 0$ og $\mathbf u_3\cdot \mathbf v_2 = 0$ .

Animation af den modificerede Gram-Schmidt algoritme for tre vektorer fra Wikipedia. Læg mærke til at prikproduktet $\mathbf u\cdot \mathbf v$ noteres som $\langle \mathbf u, \mathbf v\rangle$ i animationen.

Ovenstående procedure kan generaliseres fra to og tre vektorer til et vilkårligt antal vektorer. Denne generalisering blev først fundet af danskeren Jørgen Pedersen Gram i 1883 og kendes i dag under navnet Gram-Schmidt algoritmen . Algoritmen er angivet i sætningen nedenfor. Det er en af de helt fundamentale algoritmer i lineær algebra.

Lad $\mathbf v_1, \ldots, \mathbf v_m$ være lineært uafhængige vektorer i $\mathbb{C}^n$ og lad

$V = \mathrm{span}(\mathbf v_1,\ldots, \mathbf v_m).$ Ved algoritmen

$\begin{aligned} \mathbf u_1 &= \mathbf v_1\\ \mathbf u_2 &= \mathbf v_2 - \frac{\mathbf v_2\cdot \mathbf u_1}{|\mathbf u_1|^2} \mathbf u_1\\ \mathbf u_3 &= \mathbf v_3 - \frac{\mathbf v_3\cdot \mathbf u_1}{|\mathbf u_1|^2}\, \mathbf u_1 - \frac{\mathbf v_3\cdot \mathbf u_2}{|\mathbf u_2|^2}\, \mathbf u_2\\ &\vdots\\ \mathbf u_m &= \mathbf v_m - \frac{\mathbf v_m\cdot \mathbf u_1}{|\mathbf u_1|^2}\, \mathbf u_1 - \cdots -\frac{\mathbf v_m\cdot \mathbf u_{m-1}}{|\mathbf u_{m-1}|^2}\, \mathbf u_{m-1} \end{aligned}$ opnås ortogonale vektorer $\mathbf u_1, \ldots, \mathbf u_m\in V$ så at $\mathbf u_i\neq \mathbf 0$ og

$V = \mathrm{span}(\mathbf u_1, \ldots, \mathbf u_m).$ Således har ethvert underrum en ortogonalbasis og (dermed) en ortonormalbasis.

Bevis

Undervejs i algoritmen viser man ved ren og skær udregning med prikproduktet at den nyligt konstruerede vektor $\mathbf u_i$ opfylder $\mathbf u_i\cdot \mathbf u_1 = 0, \ldots, \mathbf u_i\cdot \mathbf u_{i-1} = 0$ samt

$\mathrm{span}(\mathbf v_1, \ldots, \mathbf v_i) = \mathrm{span}(\mathbf u_1, \ldots, \mathbf u_i).$ At $\mathbf u_i = 0$ ikke kan forekomme er på grund af antagelsen om lineær uafhængighed blandt vektorerne $\mathbf v_1, \ldots, \mathbf v_m$ . Hvis $\mathbf u_i = 0$ ville

$\mathbf v_i\in \mathrm{span}(\mathbf u_1, \ldots, \mathbf u_{i-1}) = \mathrm{span}(\mathbf v_1, \ldots, \mathbf v_{i-1}),$ i strid med at vektorerne $\mathbf v_1, \ldots, \mathbf v_i$ er lineært uafhængige.

Hvis Sætning 7.25 benyttes på et sæt af vektorer, som ikke er lineært uafhængige, vil algoritmen undervejs afsløre dette og give $\mathbf u_i = 0$ , hvor

$\mathbf v_i\in \mathrm{span}(\mathbf v_1, \ldots, \mathbf v_{i-1}).$ Algoritmen kan modificeres ret enkelt ved at springe trin med $\mathbf u_i = 0$ over og arbejde videre med $\mathbf v_{i+1}$ ud fra de allerede fundne ortogonale vektorer $\mathbf u_1, \ldots, \mathbf u_{i-1}$ . En anden enkel modifikation er at normalisere vektorerne undervejs til enhedsvektorer ved at udskifte $\mathbf u_i$ med $(1/|\mathbf u_i|) \mathbf u_i$ . Dette leder frem til en ortonormalbasis. Man kan også normalisere de ortogonale vektorer til sidst som i eksemplet nedenfor.

Kommentarer/spørgsmål?

Eksempel

Vi betragter underrummet $V$ i $\mathbb{R}^5$ med basis $B$ bestående af vektorerne

$\mathbf v_1 = \begin{pmatrix} \phantom{-} 1 \\ -1 \\ \phantom{-} 0 \\ \phantom{-} 1 \\ \phantom{-} 1 \end{pmatrix}, \quad \mathbf v_2 = \begin{pmatrix} 6 \\ 2 \\ 3 \\ 0 \\ 4 \end{pmatrix} \quad\mathrm{og}\quad \mathbf v_3 = \begin{pmatrix} 5 \\ 3 \\ 3 \\ 1 \\ 5 \end{pmatrix}$ og vil benytte Gram-Schmidt algoritmen til at finde en ortonormalbasis for $V$ . Vi indleder med at finde en ortogonalbasis for $V$ . Første trin er $\mathbf u_1 = \mathbf v_1$ . Dernæst udregner vi

$\mathbf u_2 = \mathbf v_2 - \frac{\mathbf v_2\cdot \mathbf u_1}{|\mathbf u_1|^2} \mathbf u_1 = \begin{pmatrix} 6 \\ 2 \\ 3 \\ 0 \\ 4 \end{pmatrix} - 2\begin{pmatrix} \phantom{-} 1 \\ -1 \\ \phantom{-} 0 \\ \phantom{-} 1 \\ \phantom{-} 1 \end{pmatrix} = \begin{pmatrix} \phantom{-} 4 \\ \phantom{-} 4 \\ \phantom{-} 3 \\ -2 \\ \phantom{-} 2 \end{pmatrix}$ Så vidt så godt. Man checker at $\mathbf u_1 \cdot \mathbf u_2 = 0$ . Sidste skridt er nu udregningen af $\mathbf u_3$ via

$\begin{aligned} \mathbf u_3 &= \mathbf v_3 - \frac{\mathbf v_3\cdot \mathbf u_1}{|\mathbf u_1|^2} \mathbf u_1 - \frac{\mathbf v_3\cdot \mathbf u_2}{|\mathbf u_2|^2} \mathbf u_2 \\ \\ &= \begin{pmatrix} 5 \\ 3 \\ 3 \\ 1 \\ 5 \end{pmatrix} - 2 \begin{pmatrix} \phantom{-} 1 \\ -1 \\ \phantom{-} 0 \\ \phantom{-} 1 \\ \phantom{-} 1 \end{pmatrix} - \begin{pmatrix} \phantom{-} 4 \\ \phantom{-} 4 \\ \phantom{-} 3 \\ -2 \\ \phantom{-} 2 \end{pmatrix} = \begin{pmatrix} -1 \\ \phantom{-} 1 \\ \phantom{-} 0 \\ \phantom{-} 1\\ \phantom{-} 1 \end{pmatrix}. \end{aligned}$ Hermed er $(\mathbf u_1, \mathbf u_2, \mathbf u_3)$ en ortogonalbasis for $V$ . Da $|\mathbf u_1| = 2, |\mathbf u_2| = 7$ og $|\mathbf u_3| = 2$ vil

$\left(\tfrac{1}{2}\, \mathbf u_1, \tfrac{1}{7}\, \mathbf u_2, \tfrac{1}{2}\, \mathbf u_3\right)$ være en ortonormalbasis for $V$ .

7.3.3 Den modificerede Gram-Schmidt algoritme

Gram-Schmidt algoritmen som angivet ovenfor er numerisk ustabil i praksis. Ved en lille modifikation med hensyn til udregningen af $\mathbf u_i$ fås en numerisk stabil algoritme, som er mindre følsom overfor afrundingsfejl. Dette modificerede trin består i at udregne $\mathbf u_i$ gennem følgende kæde af operationer:

$\begin{aligned} \mathbf u_i^{(1)} &= \mathbf v_i - (\mathbf v_i\cdot \mathbf u_1) \mathbf u_1\\ \mathbf u_i^{(2)} &= \mathbf u_i^{(1)} - (\mathbf u_i^{(1)}\cdot \mathbf u_2) \mathbf u_2\\ &\vdots\\ \mathbf u_i^{(i-1)} &= \mathbf u_i^{(i-2)} - (\mathbf u_i^{(i-2)}\cdot \mathbf u_{i-1}) \mathbf u_{i-1} \end{aligned}$ med $\mathbf u_i = \frac{\mathbf u_i^{(i-1)}}{|\mathbf u_i^{(i-1)}|}$ som resultat.

Eksempel

Lad os benytte vektorerne

$\mathbf v_1 = \begin{pmatrix} \phantom{-} 1 \\ -1 \\ \phantom{-} 0 \\ \phantom{-} 1 \\ \phantom{-} 1 \end{pmatrix}, \quad \mathbf v_2 = \begin{pmatrix} 6 \\ 2 \\ 3 \\ 0 \\ 4 \end{pmatrix} \quad\mathrm{og}\quad \mathbf v_3 = \begin{pmatrix} 5 \\ 3 \\ 3 \\ 1 \\ 5 \end{pmatrix}$ fra sidste eksempel som input til den modificerede Gram-Schmidt algoritme. Første skridt giver

$\mathbf u_1 = \mathbf v_1 / |\mathbf v_1| = \frac{1}{2}\begin{pmatrix} \phantom{-} 1 \\ -1 \\ \phantom{-} 0 \\ \phantom{-} 1 \\ \phantom{-} 1 \end{pmatrix}.$ Udregningen af $\mathbf u_2$ foregår som

$\mathbf u_2^{(1)} = \mathbf v_2 - (\mathbf v_2\cdot \mathbf u_1) \mathbf u_1 = \begin{pmatrix} 6 \\ 2 \\ 3 \\ 0 \\ 4 \end{pmatrix} - 4\cdot \frac{1}{2}\begin{pmatrix} \phantom{-} 1 \\ -1 \\ \phantom{-} 0 \\ \phantom{-} 1 \\ \phantom{-} 1 \end{pmatrix} = \begin{pmatrix} \phantom{-} 4 \\ \phantom{-} 4 \\ \phantom{-} 3 \\ -2 \\ \phantom{-} 2 \end{pmatrix}$ med

$\mathbf u_2 = \frac{1}{7}\begin{pmatrix} \phantom{-} 4 \\ \phantom{-} 4 \\ \phantom{-} 3 \\ -2 \\ \phantom{-} 2 \end{pmatrix}.$ Udregningen af $\mathbf u_3$ foregår som

$\mathbf u_3^{(1)} = \mathbf v_3 - (\mathbf v_3\cdot \mathbf u_1) \mathbf u_1 = \begin{pmatrix} 5 \\ 3 \\ 3 \\ 1 \\ 5 \end{pmatrix} - 4\cdot \frac{1}{2} \begin{pmatrix} \phantom{-} 1 \\ -1 \\ \phantom{-} 0 \\ \phantom{-} 1 \\ \phantom{-} 1 \end{pmatrix} = \begin{pmatrix} \phantom{-} 3 \\ \phantom{-} 5 \\ \phantom{-} 3 \\ -1 \\ \phantom{-} 3 \end{pmatrix}$ og

$\mathbf u_3^{(2)} = \mathbf u_3^{(1)} - (\mathbf u_3^{(1)}\cdot \mathbf u_2) \mathbf u_2 = \begin{pmatrix} \phantom{-} 3 \\ \phantom{-} 5 \\ \phantom{-} 3 \\ -1 \\ \phantom{-} 3 \end{pmatrix} - 7 \cdot \frac{1}{7} \begin{pmatrix} \phantom{-} 4 \\ \phantom{-} 4 \\ \phantom{-} 3 \\ -2 \\ \phantom{-} 2 \end{pmatrix} = \begin{pmatrix} -1 \\ \phantom{-} 1 \\ \phantom{-} 0 \\ \phantom{-} 1 \\ \phantom{-} 1 \end{pmatrix}$ med endeligt resultat

$\mathbf u_3 = \frac{1}{2}\begin{pmatrix} -1 \\ \phantom{-} 1 \\ \phantom{-} 0 \\ \phantom{-} 1 \\ \phantom{-} 1 \end{pmatrix}$ i fin overensstemmelse med Eksempel 7.26.

Denne algoritme kaldes den modificerede Gram-Schmidt algoritme. Den numeriske stabilitet illustreres i eksemplet (hentet fra MIT OpenCourseWare) nedenfor.

For at uddybe hvad der egentlig menes med numerisk stabil eller mindre følsom overfor afrundingsfejl kan man som eksempel afprøve Gram-Schmidt algoritmen og den modificerede Gram-Schmidt algoritme på vektorerne

$\begin{pmatrix} 1 \\ \epsilon \\ 0 \\ 0 \end{pmatrix},\quad \begin{pmatrix} 1 \\ 0 \\ \epsilon \\ 0 \end{pmatrix}\quad \mathrm{og}\quad \begin{pmatrix} 1 \\ 0 \\ 0 \\ \epsilon \end{pmatrix}$ med afrundingsfejlen $1 + \epsilon^2 \approx 1$ . Hvis en lommeregner for eksempel kan vise $10$ cifre i displayet og $\epsilon = 0.000001$ så er $1 + \epsilon^2 = 1$ på lommeregneren. Med afrunding og normering i hvert trin giver den klassiske Grams-Schmidt algoritme resultatet

$\mathbf u_1 = \begin{pmatrix} 1 \\ \epsilon \\ 0 \\ 0 \end{pmatrix},\quad \mathbf u_2 = \frac{1}{\sqrt{2}} \begin{pmatrix} \phantom{-} 0 \\ -1 \\ \phantom{-} 1 \\ \phantom{-} 0 \end{pmatrix}\quad\mathrm{og}\quad \mathbf u_3 = \frac{1}{\sqrt{2}} \begin{pmatrix} \phantom{-} 0 \\ -1 \\ \phantom{-} 0 \\ \phantom{-} 1 \end{pmatrix}.$ Læg mærke til at $\mathbf u_2\cdot \mathbf u_3 = \frac{1}{2}$ , hvilket er en grim fejl som følge af afrundingen. Derimod giver den modificerede Grams-Schmidt algoritme resultatet

$\mathbf u_1 = \begin{pmatrix} 1 \\ \epsilon \\ 0 \\ 0 \end{pmatrix},\quad \mathbf u_2 = \frac{1}{\sqrt{2}} \begin{pmatrix} \phantom{-} 0 \\ -1 \\ \phantom{-} 1 \\ \phantom{-} 0 \end{pmatrix}\quad\mathrm{og}\quad \mathbf u_3 = \frac{1}{\sqrt{6}} \begin{pmatrix} \phantom{-} 0 \\ -1 \\ -1 \\ \phantom{-} 2 \end{pmatrix}.$ Her er $\mathbf u_2\cdot \mathbf u_3 = 0$ .

7.3.4 QR dekomposition

Hvis vi benytter Gram-Schmidt algoritmen på søjlerne $\mathbf a_1, \ldots, \mathbf a_n$ i en invertibel $n\times n$ matrix $A$ fås

$\begin{aligned} \mathbf u_1 &= \mathbf a_1\\ \mathbf u_2 &= \mathbf a_2 - \frac{\mathbf a_2\cdot \mathbf u_1}{|\mathbf u_1|^2} \mathbf u_1\\ \mathbf u_3 &= \mathbf a_3 - \frac{\mathbf a_3\cdot \mathbf u_1}{|\mathbf u_1|^2}\, \mathbf u_1 - \frac{\mathbf a_3\cdot \mathbf u_2}{|\mathbf u_2|^2}\, \mathbf u_2\\ &\vdots\\ \mathbf u_n &= \mathbf a_n - \frac{\mathbf a_n\cdot \mathbf u_1}{|\mathbf u_1|^2}\, \mathbf u_1 - \cdots -\frac{\mathbf a_n\cdot \mathbf u_{n-1}}{|\mathbf u_{n-1}|^2}\, \mathbf u_{n-1}. \end{aligned}$ Ved at ortonormalisere basen og sætte $\mathbf e_i = (1/|\mathbf u_i|) \mathbf u_i$ fås nu

$\begin{aligned} \mathbf a_1 &= (\mathbf a_1\cdot \mathbf e_1) \mathbf e_1\\ \mathbf a_2 &= (\mathbf a_2\cdot \mathbf e_1) \mathbf e_1 + (\mathbf a_2\cdot \mathbf e_2) \mathbf e_2\\ \mathbf a_3 &= (\mathbf a_3\cdot \mathbf e_1) \mathbf e_1 + (\mathbf a_3\cdot \mathbf e_2)\mathbf e_2 + (\mathbf a_3\cdot \mathbf e_3) \mathbf e_3\\ &\vdots\\ \mathbf a_n &= (\mathbf a_n\cdot \mathbf e_1) \mathbf e_1 + (\mathbf a_n\cdot \mathbf e_2) \mathbf e_2 + \cdots + (\mathbf a_n\cdot \mathbf e_{n-1}) \mathbf e_{n-1}. \end{aligned}\tag{7.5}$ Oversat giver det matrix identiteten

$A = Q R,$ hvor $Q$ er matricen med søjler $\mathbf e_1, \ldots, \mathbf e_n$ og

$R = \begin{pmatrix} (\mathbf a_1\cdot \mathbf e_1) & (\mathbf a_2 \cdot \mathbf e_1) & \cdots & (\mathbf a_n\cdot \mathbf e_1)\\ 0 & (\mathbf a_2\cdot \mathbf e_2) & \cdots & (\mathbf a_n\cdot \mathbf e_2)\\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & (\mathbf a_n \cdot \mathbf e_n) \end{pmatrix}.$ Læg mærke til at matricen $Q$ er ortogonal fordi dens søjler udgør en ortonormal basis samt at $R$ er en øvre trekantsmatrix (den har nuller under diagonalen). Vi har vist følgende.

En invertibel matrix kan skrives som produkt af en ortogonal matrix og en øvre trekantsmatrix.

En faktorisering af en matrix $A = Q R$ som produkt af en ortogonal matrix $Q$ og en øvre trekantsmatrix $R$ kaldes en QR dekomposition af $A$ .

Eksempel

Matricen

$A = \begin{pmatrix} 2 & 1 \\ 1 & 2 \end{pmatrix}$ er en invertibel $2\times 2$ matrix. Ved hjælp af Gram-Schmidt algoritmen finder man med input fra søjlerne i $A$ matricen $Q$ indeholdende den ortonormale basis

$Q = \begin{pmatrix} \frac{2}{\sqrt{5}} & -\frac{1}{\sqrt{5}} \\ \frac{1}{\sqrt{5}} & \frac{2}{\sqrt{5}} \end{pmatrix}$ med QR dekompositionen

$A = \begin{pmatrix} \frac{2}{\sqrt{5}} & -\frac{1}{\sqrt{5}} \\ \frac{1}{\sqrt{5}} & \frac{2}{\sqrt{5}} \end{pmatrix} \begin{pmatrix} \sqrt{5} & \frac{4}{\sqrt{5}} \\ 0 & \frac{3}{\sqrt{5}} \end{pmatrix}$ som følge.

7.3.5 Den mirakuløse QR-algoritme

Det meste lineære algebra er langtidsholdbart matematik og flere hundrede år gammelt. Det hænder dog at ekstremt vigtige nye opdagelser bliver gjort for eksempel ved at eksperimentere med computere. Følgende næsten halvnaive algoritme til at udregne egenværdier for en kvadratisk matrix $A$ blev opdaget sidst i 1950'erne. Den hedder QR algoritmen og bygger netop på QR dekompositionen. Indledningsvis sættes $A_0 = A$ og algoritmen udregner nye QR dekompositioner i hvert trin med hensyn til det modsatte produkt af $Q$ og $R$ fra foregående trin:

$\begin{aligned} A_0 &= Q_0 R_0 \\ A_1 &= R_0 Q_0 = Q_1 R_1\\ A_2 &= R_1 Q_1 = Q_2 R_2\\ &\vdots \end{aligned}$ Læg her mærke til at $A_i$ og $A_{i+1}$ har de samme egenværdier, fordi de er ``konjugerede'':

$A_{i+1} = R_iQ_i=(Q_i^{-1}Q_i)(R_iQ_i)=Q_i^{-1}(Q_iR_i)Q_i=Q_i^{-1}A_iQ_i$ Her har vi brugt at vi ved at den ortogonale matrix $Q_i$ er inverterbar. Hvorfra ved vi forresten det? Jo, fordi $Q_iQ_i^T=Q_i^TQ=I_n$ , så $Q_i^{-1}=Q_i^T$ . Under alle omstændigheder, hvis $\mathbf u$ er en egenvektor til $A_i$ med egenværdi $\lambda$ , så er $Q_i^{-1}\mathbf u$ en egenvektor til $A_{i+1}$ med den samme egenværdi $\lambda$ . Oftest vil diagonalelementerne i $R_n$ konvergere mod egenværdierne i den oprindelige matrix $A$ .

Betragt matricen

$A = \begin{pmatrix} 2 & 1\\ 1 & 2 \end{pmatrix}$ fra Eksempel 7.30. Man kan ret nemt regne ud at $A$ har egenværdierne $\lambda = 1$ og $\lambda = 3$ . Lad os afprøve QR algoritmen rent numerisk på $A$ . De første trin giver

$\begin{aligned} A_0 = Q_0 R_0 = \begin{pmatrix} 0.894427 & -0.447214\\ 0.447214 & 0.894427 \end{pmatrix} &\begin{pmatrix} \color{red}{2.23607} & 1.78885\\ 0 & \color{red}{1.34164} \end{pmatrix} \\ A_1 = R_0 Q_0 = Q_1 R_1 = \begin{pmatrix} 0.977802 & 0.209529\\ 0.209529 & 0.977802 \end{pmatrix} &\begin{pmatrix} \color{red}{2.86356} & 0.83812\\ 0 & \color{red}{1.04765\phantom{0}} \end{pmatrix} \\ A_2 = R_1 Q_1 = Q_2 R_2 = \begin{pmatrix} 0.99729 & -0.0735706\\ 0.0735706 & 0.99729 \end{pmatrix} &\begin{pmatrix} \color{red}{2.9837\phantom{0}} & 0.29428\\ 0 & \color{red}{1.00546\phantom{0}} \end{pmatrix} \\ A_3 = R_2 Q_2 = Q_3 R_3 = \begin{pmatrix} 0.999696 & -0.0246726\\ 0.0246726 & 0.999696 \end{pmatrix} &\begin{pmatrix} \color{red}{2.99817} & 0.098690\\ 0 & \color{red}{1.00061\phantom{00}} \end{pmatrix}. \end{aligned}$ Eksperimentet synes at bekræfte at diagonalelementerne (markeret med rødt) i følgen af de øvrige trekantsmatricer i QR dekompositionerne konvergerer mod egenværdierne af den oprindelige matrix.

7.3.6 Ortogonalkomplement og ortogonalprojektion

Man har ofte brug for en anelse mere terminologi omkring underrum og ortogonalitet, herunder ortogonalkomplement og ortogonalprojektion.

For et underrum $V$ i $\mathbb{R}^n$ knytter der sig et komplementært underrum med hensyn til prikproduktet. Dette underrum er defineret ved

$V^\perp = \{\mathbf v\in \mathbb{R}^n \mid \mathbf u\cdot \mathbf v = 0,\,\textrm{for alle }\mathbf u\in V\}.$ og kaldes ortogonalkomplementet til $V$ .

At $V^\perp$ er et underrum følger af egenskaberne ved prikproduktet givet i Proposition 7.4.

Et underrum $V$ i $\mathbb{R}^n$ er givet ved en basis $(\mathbf u_1, \ldots, \mathbf u_m)$ . Ud fra denne basis kan en basis for ortogonalkomplementet $V^\perp$ udregnes som en basis for $N(A^T)$ , hvor $A$ er matricen med søjler $\mathbf u_1, \ldots, \mathbf u_m$ . Dette følger af observationen at $\mathbf v\in \mathbb{R}^n$ opfylder $\mathbf u\cdot \mathbf v=0$ for alle $\mathbf u\in V$ hvis og kun hvis

$\begin{aligned} \mathbf u_1\cdot \mathbf v &= 0\\ &\vdots\\ \mathbf u_m\cdot \mathbf v &= 0, \end{aligned}\tag{7.6}$ fordi alle $\mathbf u\in V$ kan skrives $\mathbf u = \lambda_1 \mathbf u_1 + \cdots + \lambda_m \mathbf u_m$ og

$\mathbf u\cdot \mathbf v = (\lambda_1 \mathbf u_1 + \cdots + \lambda_m \mathbf u_m) \cdot \mathbf v = \lambda_1 (\mathbf u_1 \cdot \mathbf v) + \cdots + \lambda_m (\mathbf u_m \cdot \mathbf v) = \mathbf 0,$ hvis $\mathbf v$ er en løsning i (7.6). Skrevet i matrixnotation svarer ligningssystemet (7.6) præcis til $A^T \mathbf v = <nul$ . Derfor er $V^\perp = N(A^T)$ .

Lad $V$ være et underrum af $\mathbb{R}^n$ . Enhver vektor $\mathbf u\in \mathbb{R}^n$ kan på entydig måde skrives

$\mathbf u = \mathbf v + \mathbf v', \tag{7.7}$ hvor $\mathbf v\in V$ og $\mathbf v'\in V^\perp$ : Hvis $\mathbf v_1, \mathbf v_2\in V$ og $\mathbf v'_1, \mathbf v'_2\in V^\perp$ med

$\mathbf v_1 + \mathbf v'_1 = \mathbf v_2 + \mathbf v'_2,$ så er $\mathbf v_1 = \mathbf v_2$ og $\mathbf v'_1 = \mathbf v'_2$ .

Bevis

Hvis $\mathbf v_1, \ldots, \mathbf v_m$ er en ortonormal basis for $V$ , så gælder

$\mathbf v^\perp = \mathbf u - ((\mathbf u\cdot \mathbf v_1) \mathbf v_1 + \cdots + (\mathbf u\cdot \mathbf v_m) \mathbf v_m)\in V^\perp.$ Derfor gælder

$\mathbf u = \mathbf v + \mathbf v^\perp \tag{7.8}$ med

$\mathbf v = (\mathbf u\cdot \mathbf v_1) \mathbf v_1 + \cdots + (\mathbf u\cdot \mathbf v_m) \mathbf v_m)\in V.$ Fremstillingen i (7.8) er entydig. Hvis $\mathbf v_1 + \mathbf v'_1 = \mathbf v_2 + \mathbf v'_2$ så er $\mathbf v_1-\mathbf v_2=\mathbf v'_1-\mathbf v'_2\in V^\perp$ . Men da $\mathbf v_1-\mathbf v_2\in V$ , så er $|\mathbf v_1-\mathbf v_2| ^2= (\mathbf v_1-\mathbf v_2)\cdot (\mathbf v_1-\mathbf v_2)=0$ . Det følger at $\mathbf v_1=\mathbf v_2$ . Formuleret på en anden måde er $V\cap V^\perp = \{<nul\}$ .

I opskrivningen (7.7) kaldes $\mathbf v$ ortogonalprojektionen af $\mathbf u$ på $V$ .

Begreberne kan endnu en gang forstås gennem den centrale figur nedenfor i tilfældet $\mathbb{R}^2$ .

Med $V = \mathrm{span}(\mathbf v)$ er $\lambda \mathbf v$ ortogonalprojektion af $\mathbf u$ på $V$ og ortogonalkomplementet $V^\perp$ til $V$ er underrummet $\mathrm{span}(\mathbf u-\lambda \mathbf v)$ .

Ortogonalprojektion af en vektor $\mathbf u\in \mathbb{R}^n$ på et underrum $V$ fås ved hjælp af en ortonormalbasis for $\mathbf v_1, \ldots, \mathbf v_m$ for $V$ som

$\mathbf v = (\mathbf u\cdot \mathbf v_1) \mathbf v_1 + \cdots + (\mathbf u\cdot \mathbf v_m) \mathbf v_m.$ Da $\mathbf u - \mathbf v\in V^\perp$ , fordi $(\mathbf u-\mathbf v)\cdot \mathbf v_1 = 0, \ldots, (\mathbf u-\mathbf v)\cdot \mathbf v_m = 0$ , bliver den entydige opskrivning fra (7.7) hermed

$\mathbf u = \mathbf v + (\mathbf u - \mathbf v).$

I Eksempel 7.23 betragtede vi underrummet $V = \mathrm{span}(\mathbf v_1, \mathbf v_2, \mathbf v_3)$ af $\mathbb{R}^4$ med

$\mathbf v_1 = \begin{pmatrix} -\frac{1}{\sqrt{2}}\,\,\\ \\ \phantom{-}\frac{1}{\sqrt{2}}\\ \\ 0\\ \\ 0 \end{pmatrix},\quad \mathbf v_2 = \begin{pmatrix} \frac{1}{2}\\ \\ \frac{1}{2}\\ \\ \frac{1}{2}\\ \\ \frac{1}{2} \end{pmatrix},\quad\mathrm{og}\quad \mathbf v_3 = \begin{pmatrix} -\frac{1}{2}\,\\ \\ -\frac{1}{2}\\ \\ \phantom{-}\frac{1}{2}\\ \\ \phantom{-}\frac{1}{2} \end{pmatrix}.$ Bemærk igen at $(\mathbf v_1, \mathbf v_2, \mathbf v_3)$ er en ortonormalbasis for $V$ . Her er

$V^\perp = \mathrm{span}\left(\begin{pmatrix} \phantom{-} 0\\ \phantom{-} 0\\ \phantom{-} 1 \\ -1 \end{pmatrix}\right),$ da vi ved at $\dim V^\perp = 4 - \dim V = 1$ (hvorfor?). I Eksempel 7.23 fandt vi ud af at $\mathbf u\notin V$ , hvor

$\mathbf u = \begin{pmatrix} 1 \\ 1 \\ 2 \\ 1 \end{pmatrix}.$ Vi udregnede i eksemplet også

$(\mathbf u\cdot \mathbf v_1) \mathbf v_1 + (\mathbf u\cdot \mathbf v_2) \mathbf v_2 + (\mathbf u\cdot \mathbf v_3) \mathbf v_3 = \tfrac{5}{2}\, \mathbf v_2 + \tfrac{1}{2}\, \mathbf v_3 = \begin{pmatrix} 1\\ \\ 1\\ \\ \frac{3}{2}\\ \\ \frac{3}{2} \end{pmatrix}$ Denne vektor er ortogonalprojektionen af $\mathbf u$ på $V$ i henhold til Bemærkning 7.36.

7.4 Mindste kvadraters metode

Kommentarer/spørgsmål?

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 .

$\phantom{phantom}$ Det er ikke altid et ligningssystem

$A \mathbf x = \mathbf b$ med $A$ en $m\times n$ matrix og $\mathbf b$ en $m\times 1$ matrix har en løsning, og det er heller ikke altid at denne løsning er entydig. Hvis for eksempel $m\gg 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 følgende to ting gælde:

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$ .

Eksempel

Ligningssystemet

$\begin{pmatrix} \phantom{-} 1 & \phantom{-} 1\\ \phantom{-} 1 & -1\\ -1 & \phantom{-} 1 \end{pmatrix} \begin{pmatrix} x\\ y \end{pmatrix} = \begin{pmatrix} 3 \\ 1 \\ 1 \end{pmatrix},$ er et ligningssystem med $3$ ligninger og $2$ ubekendte. Det har ingen løsninger.

For at præcisere hvad der menes med tættest på indføres følgende definition.

En mindste kvadraters løsning til ligningssystemet $A \mathbf x = \mathbf b$ , med $A$ en $m\times n$ matrix og $\mathbf b$ en $m\times 1$ , er en vektor $\mathbf x_0\in \mathbb{R}^n$ , som opfylder

$|\mathbf b - A \mathbf x_0|^2 \leq |\mathbf b - A \mathbf x|^2$ for alle $\mathbf x\in \mathbb{R}^n$ .

Læg mærke til at en mindste kvadraters løsning opfylder at $|\mathbf b - A \mathbf x_0| \leq |\mathbf b - A \mathbf x|$ for alle $\mathbf x\in \mathbb{R}^n$ . $\mathbf x_0$ er det valg af $\mathbf x=\mathbf x_0$ så at $A\mathbf x_0$ er tættest på $\mathbf b$ for alle mulige valg af $\mathbf x$ . Jeg bliver lige overrasket hver gang over at dette minimeringsproblem har så smuk en løsning ved hjælp af lineær algebra. En vigtig ingrediens er generaliseringen af Pythagoras til $n$ dimensioner.

Lad $\mathbf u, \mathbf v\in \mathbb{C}^n$ . Hvis $\mathbf u$ og $\mathbf v$ er ortogonale, så er

$|\mathbf u + \mathbf v|^2 = |\mathbf u|^2 + |\mathbf v|^2.$

Bevis

Dette følger af egenskaber ved prikproduktet:

$|\mathbf u + \mathbf v|^2 = (\mathbf u+\mathbf v)\cdot (\mathbf u+\mathbf v) = \mathbf u\cdot \mathbf u + \mathbf u\cdot \mathbf v + \mathbf v\cdot \mathbf u + \mathbf v\cdot \mathbf v = |\mathbf u|^2 + |\mathbf v|^2.$

Et ligningssystem $A \mathbf x = \mathbf b$ , hvor $A$ er en $m\times n$ matrix og $\mathbf b$ en $m\times 1$ matrix, har altid en mindste kvadraters løsning $\mathbf x_0\in \mathbb{R}^n$ . En løsning $\mathbf x_0$ kan findes som løsning til ligningssystemet
$A^T A \mathbf x = A^T \mathbf b.$
Antag nu at ligningen $A\mathbf x=\mathbf 0$ ikke har andre løsninger end $\mathbf x=\mathbf 0$ . Da er der kun en eneste mindste kvadraters løsning. Desuden er matricen $A^TA$ invertibel, og den entydigt bestemte løsning kan udregnes ved formlen
$\mathbf x_0 = (A^T A)^{-1} A^T \mathbf b. \tag{7.9}$

Betingelse at $A\mathbf x=\mathbf 0$ kun har nulløsningen kan på en mere fancy måde udtrykkes ved at dimensionen af nulrummet $N(A)$ er 0. Ifølge dimensionssætningen i Kapitel 6 er dette det samme som at rangen af matricen $A$ er $n$ .

Bevis*

Vi viser at der altid findes en løsning. En helt central observation er at vi kan finde $\mathbf x_0\in \mathbb{R}^n$ så $\mathbf b - A \mathbf x_0$ er ortogonal på søjlerne i $A$ . Dette er en følge af Gram-Schmidt algoritmen: Hvis $\mathbf e_1, \ldots, \mathbf e_r$ er en ortonormal basis for søjlerummet for $A$ , så vil

$\mathbf y = (\mathbf b\cdot \mathbf e_1) \mathbf e_1 + \cdots + (\mathbf b\cdot \mathbf e_r) \mathbf e_r$ opfylde at $\mathbf b - \mathbf y$ er ortogonal på $\mathbf e_1, \ldots, \mathbf e_r$ og dermed ortogonal på søjlerne i $A$ . Da $\mathbf y$ ligger i søjlerummet for $A$ kan $\mathbf y$ skrives som $A \mathbf x_0$ for passende $\mathbf x_0\in \mathbb{R}^n$ . Et sådant $\mathbf x_0$ vil være en mindste kvadraters løsning. Vi forklarer hvorfor. Da vektoren $\mathbf b-A\mathbf x_0$ er ortogonal på alle søjler i $A$ , er den ortogonal på alle vektorer af formen $A\mathbf v$ . Specielt gælder det at for enhver vektor $\mathbf x\in \mathbb{R}^n$ er de to vektorer $\mathbf b-A\mathbf x_0$ og $A (\mathbf x_0 - \mathbf x)$ ortogonale. Ved at bruge Proposition 7.40 finder vi at

$\begin{aligned} |\mathbf b - A \mathbf x|^2 &= |\mathbf b - A \mathbf x_0 + A \mathbf x_0 - A \mathbf x|^2\\ &= |\mathbf b - A \mathbf x_0 + A (\mathbf x_0 - \mathbf x)|^2 \\ &= |\mathbf b - A \mathbf x_0|^2 +|A (\mathbf x_0 - \mathbf x)|^2. \end{aligned}$ Derfor gælder

$|\mathbf b - A \mathbf x_0|^2 \leq |\mathbf b - A \mathbf x|^2$ for alle $\mathbf x\in \mathbb{R}^n$ .

$\phantom{phantom}$ Nu vil vi vise at det $\mathbf x_0$ som vi lige har fundet løser ligningen $(A^TA)\mathbf x=A^T\mathbf b$ . Vi arbejder videre ud fra vores nyvundne viden om at $\mathbf b - A \mathbf x_0$ skal være ortogonal på alle vektorer af formen $A\mathbf y$ . Dette betyder at, for alle $\mathbf y\in \mathbb{R}^n$ ,

$A\mathbf y \cdot (\mathbf b - A \mathbf x_0) = 0,$ og dermed (husk at $\mathbf y\cdot A \mathbf v = A^T \mathbf y \cdot \mathbf v$ )

$\mathbf y\cdot (A^T\mathbf b - A^TA \mathbf x_0)=\mathbf y\cdot A^T(\mathbf b - A \mathbf x_0)=A\mathbf y \cdot (\mathbf b - A \mathbf x_0)=0.$ Dette vil gælde for alle $\mathbf y\in \mathbb{R}^n$ . Nu bruger vi et beskidt men nyttigt kneb: Vi sætter ind $\mathbf y=(A^T\mathbf b - A^TA \mathbf x_0)$ og får at

$|A^T\mathbf b - A^TA \mathbf x_0| ^2=(A^T\mathbf b - A^TA \mathbf x_0)\cdot (A^T\mathbf b - A^TA \mathbf x_0)=0.$ Det følger at

$A^T\mathbf b - A^TA \mathbf x_0=0$ eller

$A^TA \mathbf x_0=A^T\mathbf b.$

$\phantom{phantom}$ Fra nu af antager vi at $A\mathbf x=\mathbf 0$ kun har den trivielle nulløsning.

$\phantom{phantom}$ Vi vil vise påstanden om entydighed. Hvis $\mathbf x_0$ er den løsning som vi fandt i de foregående trin, og $\mathbf x_0'$ er en anden mindste kvadraters løsninger, så har vi jo lige set at $\mathbf b - A \mathbf x_0$ er ortogonal på $A(\mathbf x_0-\mathbf x_0')$ . Igen følger det af Pythagoras:

$\phantom{phantom}$ Til sidst skal vi vise at $A^T A$ er invertibel. Dette gør vi ved at vise at antage at

$(A^T A) \mathbf x = \mathbf 0$ og vise at dette medfører at $\mathbf x=\mathbf 0$ (se den relevante sætning i Kapitel 4). Det kan vi gøre med denne fikse udregning:

$A\mathbf x\cdot A\mathbf x=\mathbf x\cdot A^T(A\mathbf x)=\mathbf x\cdot (A^TA)\mathbf x=\mathbf x \cdot\mathbf 0 = 0.$ Da $|A\mathbf x|^2=A\mathbf x\cdot A\mathbf x=0$ er $A\mathbf x=\mathbf 0$ , og det følger fra vores antagelse om $A$ at $\mathbf x=\mathbf 0$ .

Eksempel

Lad os finde en mindste kvadraters løsning for ligningssystemet

$A = \begin{pmatrix} \phantom{-} 1 & \phantom{-} 1\\ \phantom{-} 1 & -1\\ -1 & \phantom{-} 1 \end{pmatrix} \qquad\mathrm{og}\qquad b = \begin{pmatrix} 3 \\ 1 \\ 1 \end{pmatrix},$ som ved indsættelse i (7.9) giver mindste kvadraters løsningen

$x_0 = \left( A^T A\right)^{-1} A^T b = \begin{pmatrix} 3 & -1\\ -1 & 3 \end{pmatrix}^{-1} \begin{pmatrix} 3 \\ 3 \end{pmatrix} = \begin{pmatrix} \frac{3}{2} \\ \frac{3}{2} \end{pmatrix}.$

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

$(x_1, y_1), \quad (x_1, y_1), \quad \ldots \quad, (x_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} x_1 & 1\\ x_2 & 1\\ \vdots & \vdots\\ x_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 x + \beta$ gennem punkterne i den forstand at summen af den vertikale kvadratafstand fra linjen til $y$ -erne

$(y_1 -\alpha x_1 -\beta)^2 + (y_2 -\alpha x_2 -\beta)^2 + \cdots + (y_n -\alpha x_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 x^2 + \beta x + \gamma$ gennem punkterne

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

$\begin{pmatrix} x_1^2 & x_1 & 1\\ x_2 ^2 & x_2 & 1\\ \vdots & \vdots\\ x_n^2 & x_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 eller fitte et $m$ -te grads polynomium

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

7.5 Opgaver

7.5.1

Gør rede for at $1$ og $-1$ er egenværdier for matricen

$\begin{pmatrix} \cos(\theta) & \phantom{-}\sin(\theta)\\ \sin(\theta) & -\cos(\theta) \end{pmatrix},$ hvor $\theta$ er en vilkårlig vinkel. Forsøg at bestemme egenvektorerne.

7.5.2

Gør rede for at

$(A B)^* = B^* A^*,$ hvor $A$ og $B$ er to matricer, hvor produktet $A B$ giver mening. Vis yderligere at

$(A^*)^* = A.$

7.5.3

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

7.5.4

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

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

Gør rede for hvordan (7.10) kan omskrives til ligningen
$2 a x + 2 b y + c = x^2 + y^2, \tag{7.11}$ hvor $c = r^2 - a^2 - b^2$ .
Forklar hvordan (7.11) 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), \ldots, (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\mathrm{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?

7.5.5

Bestem vinklen mellem vektorerne

$\begin{pmatrix} 1 \\ 1\\ 1\\ 1 \end{pmatrix}\qquad\mathrm{og}\qquad \begin{pmatrix} 1 \\ 1\\ 1\\ 0 \end{pmatrix}.$

7.5.6

Hvor tæt er de to sætninger

Jeg vil gerne have et glas vand
Jeg vil gerne have et glas vin

på hinanden?

7.5.7

Find den inverse til matricen

$P = \begin{pmatrix} 0 & \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}}\\ 0 & \frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}}\\ -1 & 0 & 0 \end{pmatrix}$ uden at regne.

7.5.8

Gør detaljeret rede for at

$\left(\begin{pmatrix} -1 \\ \phantom{-} 2 \\ -1 \end{pmatrix}, \begin{pmatrix} 1 \\ 1 \\ 1 \end{pmatrix}\right)$ er en ortogonalbasis for underrummet

$V = \mathrm{span}\left( \begin{pmatrix} 1 \\ 2 \\ 1 \end{pmatrix}, \begin{pmatrix} 1 \\ 1 \\ 1 \end{pmatrix}\right)$ af $\mathbb{R}^3$ . Benyt derefter Proposition 7.22 (og Eksempel 7.23) til at afgøre om

$\begin{pmatrix} 1 \\ 0 \\ 1 \end{pmatrix}\in V.$

7.5.9

Find en ortonormalbasis for underrummet

$\mathrm{span}\left(\begin{pmatrix} 1 \\ 1 \\ 0\\ 0 \end{pmatrix}, \begin{pmatrix} 1 \\ 0 \\ 1 \\ 0\end{pmatrix}, \begin{pmatrix} 1 \\ 0 \\ 0 \\ 1\end{pmatrix} \right)$ af $\mathbb{R}^4$ .

7.5.10

Skriv matricen

$A = \begin{pmatrix} 1 & 1 & 0\\ 1 & 0 & 1\\ 0 & 1 & 1 \end{pmatrix}$ som et produkt $Q R$ , hvor $Q$ er en ortogonal matrix og $R$ en øvre trekantsmatrix (en matrix, som har nuller under diagonalen). Gør rede for dine udregninger og metoder. Find en ortogonal matrix $P$ så

$P^T A P = \begin{pmatrix} 2 & 0 & 0\\ 0 & -1 & 0\\ 0 & 0 & 1 \end{pmatrix}.$