9Indre produkt og ortogonalitet

I planen $\mathbb{R}^2$ har vi i Kapitel 1 set på det Euklidiske indre produkt (kaldes også nogle gange prikprodukt eller skalarprodukt) $$\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 det indre produkt indførte vi begreber som normen (længden) af en vektor og ortogonalitet. Normen 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 det indre produkt fra planen $\mathbb{R}^2$ til vilkårlige søjlevektorer i $\mathbb{C}^n$. Her skal man være særlig opmærksom på at der for komplekse tal også indgår en kompleks konjugering, som er helt essentiel for at vi kan tale om længden af en kompleks vektor. Vi husker at konjugeringen af et komplekst tal $z = x+iy$ er givet ved at skifte fortegn på imaginærdelen $$\overline{z} = x - iy,$$ og vi husker at der helt særligt fås et reelt tal (modulus af $z$ i anden potens) når et komplekst tal ganges med sin konjugerede $$z\overline{z} = |z|^2.$$ Moralen i dette kapitel er at lineær algebra bliver væsentligt mere kraftfuldt (og spændende!), når vi har et indre produkt at arbejde med. Specielt kan meget af vores geometriske intuition fra vektorer i planen fra Kapitel 1 anvendes på vektorer i $\mathbb{C}^n$. Det vigtigste begreb vi kommer ind på i denne sammenhæng er ortonormalbaser som giver en let måde at finde koordinater til vektorer (på samme måde som det er kendt fra standard basen) og hvordan en ''almindelig'' basis kan omdannes til en ortonormalbasis.

9.1 Egenskaber for indre produkter og normer

Der gælder følgende helt essentielle egenskaber for det Euklidiske indre produkt. BevisUd fra egenskaberne i Proposition 9.3, kan vi nu se at vi kan bruge samme formel for projektionen af en vektor $\mathbf u\in\mathbb{C}^n$ på en vektor $\mathbf v\in\mathbb{C}^n$ hvor $\mathbf v\neq \mathbf 0$, som vi havde i Kapitel 1: Specifikt har vi at $\mathbf w$ er parallel med $\mathbf v$ (det er $\mathbf v$ ganget med skalaren i parantesen) og vi har at $\mathbf w\perp(\mathbf u-\mathbf w)$: $$\mathbf w\cdot(\mathbf u-\mathbf w) = \mathbf w\cdot\mathbf u - |\mathbf w|^2 = \frac{(\mathbf u\cdot\mathbf v)(\mathbf v\cdot\mathbf u)}{|\mathbf v|^2} - \frac{|\mathbf u\cdot\mathbf v|^2|\mathbf v|^2}{|\mathbf v|^4} = 0.$$ Bemærk at vi derfor kan skrive $\mathbf u = \mathbf w + (\mathbf u-\mathbf w)$, hvor højresiden er to ortogonale vektorer; $\mathbf w$ er komponenten af $\mathbf u$ der peger i retning af $\mathbf v$, mens $\mathbf u-\mathbf w$ er komponenten af $\mathbf u$ der er ortogonal på $\mathbf v$.Ud fra kun definitionen af det indre produkt og ortogonale projektioner kan vi lave overraskende meget nyttig matematik. Blandt andet nedenstående resultat, som kaldes Cauchy-Schwarz ulighed. BevisUd fra Cauchy-Schwarz ulighed kan vi udlede trekantsuligheden. BevisFra ortogonalitet følger Pythagoras sætning ved direkte udregning, som er kendt fra retvinklede trekanter med kateter $|\mathbf u|$ og $|\mathbf v|$ samt diagonal $|\mathbf u+\mathbf v|$. Bevis

9.2 Ortonormalbaser

De fleste kan godt lide at bruge standard basen $\{\mathbf e_1,\dots,\mathbf e_m\}$ for $\mathbb{C}^m$, på grund af de flotte geometriske egenskaber den har. Hver vektor peger ud af akserne i det typiske retvinklede koordinatsystem, og koordinaterne til vektor $\mathbf u = (x_1,\dots,x_m)^T\in \mathbb{C}^m$ kan direkte aflæses fra vektorens indgange. Vi har nemlig $$\begin{aligned} \mathbf u &= x_1\mathbf e_1 + x_2\mathbf e_2 + \dots + x_n\mathbf e_m \\ &= (\mathbf u\cdot\mathbf e_1)\mathbf e_1 + (\mathbf u\cdot\mathbf e_2)\mathbf e_2 + \dots + (\mathbf u\cdot\mathbf e_n)\mathbf e_m. \end{aligned}\tag{9.2}$$ Det at vi kan ''aflæse'' koordinaterne nemt, svarer præcis til udregningen af koordinatvektoren ved de indre produkter $(\mathbf u\cdot\mathbf e_1,\dots,\mathbf u\cdot\mathbf e_m)^T$. Dette er betydelig lettere end at skulle løse et ligningssystem for at finde en koordinatvektor. Vi skal se at denne lettere måde at finde koordinater på hænger sammen med ortogonalitet af basisvektorerne.Først skal vi overbevise os selv om, at ortogonale vektorer er lineært uafhængige, hvilket fra et geometrisk synspunkt nok ikke er så overraskende.BevisDa ortogonale vektorer er lineært uafhængige, så opfylder de allerede det vigtigste kriterium for at danne baser for vektorrum.Vi vil meget ofte anvende ONB-forkortelsen fra Definition 9.10 fremadrettet. Der er flere af resultaterne i de næste afsnit og kapitler der specifikt gør brug af ortonormalbaser, hvor det er vigtigt at vektorerne er normaliseret så de har norm 1 (ved at dividere med normen af vektoren) og ikke kun er ortogonale; dette er nok en af de mest almindelige fejl man begår når man første gang skal diagonalisere en matrix ved brug af spektralsætningen i Kapitel 11.Nu skal vi se nogle pæne formler for at udregne koordinater for en ONB, helt analogt med hvad vi så for standard basen i (9.2), samt en brugbar formel der relaterer normen af en vektor til de indre produkter med basisvektorerne. Bevis

9.3 Gram-Schmidt algoritmen

Vi har set ovenfor at ONB'er er specielt nemme at regne med. Spørgsmålet er om alle underrum af $\mathbb{C}^m$ har en ONB? 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 vektor, som vi genopfriskede i (9.1).Hvis $\{\mathbf u_1,\dots,\mathbf u_m\}$ er en ortogonalbasis for et vektorrum $V$, så kan vi finde en ONB ved at normalisere $$\mathbf w_1 = \frac{\mathbf u_1}{|\mathbf u_1|}, \quad \mathbf w_2 = \frac{\mathbf u_2}{|\mathbf u_2|}, \quad \dots, \quad \mathbf w_m = \frac{\mathbf u_m}{|\mathbf u_m|}.$$ Ved at sætte dette ind i Proposition 9.11, får vi den tilsvarende formel for koordinaterne i en ortogonalbasis $$\begin{aligned} \mathbf v &= (\mathbf v\cdot \mathbf w_1) \mathbf w_1 + (\mathbf v\cdot \mathbf w_2) \mathbf w_2 + \cdots + (\mathbf v\cdot \mathbf w_m) \mathbf w_m \\ &= \Bigl(\frac{\mathbf v\cdot\mathbf u_1}{|\mathbf u_1|^2}\Bigr)\mathbf u_1 + \Bigl(\frac{\mathbf v\cdot\mathbf u_2}{|\mathbf u_2|^2}\Bigr)\mathbf u_2 + \dots + \Bigl(\frac{\mathbf v\cdot\mathbf u_m}{|\mathbf u_m|^2}\Bigr)\mathbf u_m. \end{aligned}\tag{9.3}$$ Hvis vi kigger på de enkelte led, og sammenligner med (9.1), så ser vi at $\mathbf v$ er summen af de ortogonale projektioner af $\mathbf v$ på henholdsvis $\mathbf u_1$, $\mathbf u_2$, $\dots$, $\mathbf u_m$. En måske vigtigere observation fra (9.3), er at vi kan finde komponenten af $\mathbf v$ i én ortogonal retning ved at trække alle de andre ortogonale projekterne fra $\mathbf v$. For eksempel er det sidste komponent $$\Bigl(\frac{\mathbf v\cdot\mathbf u_m}{|\mathbf u_m|^2}\Bigr)\mathbf u_m = \mathbf v - \Bigl(\frac{\mathbf v\cdot\mathbf u_1}{|\mathbf u_1|^2}\Bigr)\mathbf u_1 - \Bigl(\frac{\mathbf v\cdot\mathbf u_2}{|\mathbf u_2|^2}\Bigr)\mathbf u_2 - \dots - \Bigl(\frac{\mathbf v\cdot\mathbf u_{m-1}}{|\mathbf u_{m-1}|^2}\Bigr)\mathbf u_{m-1}.$$ Dette er princippet der ligger bag Gram-Schmidt algoritmen: Tag en basis for et vektorrum, og lav nye vektorer hvor vi induktivt trækker ortogonalprojektioner fra til at danne en ny ortogonalbasis for det samme vektorrum.Proceduren i animationen ovenfor kan generaliseres fra to og tre vektorer til et vilkårligt antal vektorer. Denne generalisering blev først fundet af danskeren 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 metoder i lineær algebra. BevisHvis Sætning 9.15 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 = \mathbf 0$, hvor $$\mathbf v_i\in \mathrm{span}\{\mathbf v_1, \dots, \mathbf v_{i-1}\}.$$ Algoritmen kan modificeres ret enkelt ved at springe trin med $\mathbf u_i = \mathbf 0$ over og arbejde videre med $\mathbf v_{i+1}$ ud fra de allerede fundne ortogonale vektorer $\mathbf u_1, \dots, \mathbf u_{i-1}$.

9.3.1 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. EksempelDenne algoritme kaldes den modificerede Gram-Schmidt algoritme. Den numeriske stabilitet illustreres i eksemplet (hentet fra MIT OpenCourseWare) nedenfor.

9.4 Unitære og ortogonale matricer

For en $m\times n$ kompleks matrix $A$ er $\overline{A}$ den kompleks konjugerede af $A$. Det svarer til at konjugere hver af indgangene i matricen, som set nedenfor: $$A = \begin{pmatrix} a_{11} & \dots & a_{1n} \\ \vdots & \ddots & \vdots \\ a_{m1} & \dots & a_{mn} \end{pmatrix}, \qquad \overline{A} = \begin{pmatrix} \overline{a_{11}} & \dots & \overline{a_{1n}} \\ \vdots & \ddots & \vdots \\ \overline{a_{m1}} & \dots & \overline{a_{mn}} \end{pmatrix}.$$ Nu skal vi introducere en matrix som har helt særlige egenskaber når det kommer til det indre produkt, og som bliver brugt i resten af kapitlerne.Som vi kender det fra transponering af matricer, kan vi bestemme den konjugerede og transponerede af et produkt ved formlen $$(AB)^* = B^*A^*.$$ Herudover kan vi også se, at en anden måde at skrive det Euklidiske indre produkt af to vektorer $\mathbf u,\mathbf v\in\mathbb{C}^n$, er $$\mathbf u\cdot\mathbf v = \mathbf v^*\mathbf u.$$ Ved at kombinere de to ovenstående principper, får vi en meget vigtig egenskab. Vi kan altså flytte en matrix fra én indgang i det indre produkt til den anden, ved at finde dens konjugerede og transponerede.Læg mærke til at $\overline{A} = A$ hvis $A$ er en reel matrix, så i det tilfælde vil $A^* = A^T$.Vi skal nu se på de matricer $U$, hvorom det gælder at $U^* = U^{-1}$, altså hvor vi meget nemt kan udregne den inverse af matricen ved blot at konjugere og transponere. Selvom disse matricer ofte ser grimme og ubehagelige ud (rent numerisk) så er det nogle af de letteste at arbejde med, måske lige ud over diagonalmatricerne, og de har en særrolle i diagonalisering af nogle vigtige klasser af matricer i Kapitel 11.En vigtig geometrisk egenskab for unitære matricer $U$, er at de bevarer det indre produkt, altså Tilsvarende, ved at indsætte $\mathbf u$ på $\mathbf v$'s plads ovenfor, ses at unitære matricer også bevarer normen af en vektor: En afbildning med denne egenskab kaldes en isometri.Det næste resultat viser, at det ikke er kompliceret at konstruere unitære matricer; det svarer præcis til de kvadratiske matricer med ortonormale søjler. Her kender vi allerede Gram-Schmidt algoritmen til at bestemme ONB'er. Bevis

9.4.1 QR dekomposition

Hvis vi benytter Gram-Schmidt algoritmen på søjlerne $\mathbf a_1, \dots, \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 - \Bigl(\frac{\mathbf a_2\cdot \mathbf u_1}{|\mathbf u_1|^2}\Bigr) \mathbf u_1\\ \mathbf u_3 &= \mathbf a_3 - \Bigl(\frac{\mathbf a_3\cdot \mathbf u_1}{|\mathbf u_1|^2}\Bigr) \mathbf u_1 - \Bigl(\frac{\mathbf a_3\cdot \mathbf u_2}{|\mathbf u_2|^2}\Bigr) \mathbf u_2\\ &\vdots\\ \mathbf u_n &= \mathbf a_n - \Bigl(\frac{\mathbf a_n\cdot \mathbf u_1}{|\mathbf u_1|^2}\Bigr) \mathbf u_1 - \cdots -\Bigl(\frac{\mathbf a_n\cdot \mathbf u_{n-1}}{|\mathbf u_{n-1}|^2}\Bigr) \mathbf u_{n-1}. \end{aligned}$$ Efter normalisering $\mathbf w_i = \mathbf u_i/|\mathbf u_i|$ fås nu af Proposition 9.11 $$\begin{aligned} \mathbf a_1 &= (\mathbf a_1\cdot \mathbf w_1) \mathbf w_1\\ \mathbf a_2 &= (\mathbf a_2\cdot \mathbf w_1) \mathbf w_1 + (\mathbf a_2\cdot \mathbf w_2) \mathbf w_2\\ \mathbf a_3 &= (\mathbf a_3\cdot \mathbf w_1) \mathbf w_1 + (\mathbf a_3\cdot \mathbf w_2) \mathbf w_2 + (\mathbf a_3\cdot \mathbf w_3) \mathbf w_3\\ &\vdots\\ \mathbf a_n &= (\mathbf a_n\cdot \mathbf w_1) \mathbf w_1 + (\mathbf a_n\cdot \mathbf w_2) \mathbf w_2 + \cdots + (\mathbf a_n\cdot \mathbf w_{n}) \mathbf w_{n}. \end{aligned}\tag{9.5}$$ Oversat giver det matrix identiteten $$A = Q R,$$ hvor $Q$ er matricen med søjler $\mathbf w_1, \dots, \mathbf w_n$ og $$R = \begin{pmatrix} \mathbf a_1\cdot \mathbf w_1 & \mathbf a_2 \cdot \mathbf w_1 & \cdots & \mathbf a_n\cdot \mathbf w_1\\ 0 & \mathbf a_2\cdot \mathbf w_2 & \cdots & \mathbf a_n\cdot \mathbf w_2\\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & \mathbf a_n \cdot \mathbf w_n \end{pmatrix}.$$ Læg mærke til at matricen $Q$ er unitær fordi dens søjler udgør en ONB, samt at $R$ er en øvre trekantsmatrix (den har nuller under diagonalen). Vi har vist følgende.Faktoriseringen $A = QR$ kaldes, af åbenlyse årsager, en QR dekomposition eller QR faktorisering af $A$.

9.4.2 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 similære: $$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 unitære matrix $Q_i$ er invertibel. 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$.

9.5 Ortogonal komplement og ortogonal projektion

Man har ofte brug for en anelse mere terminologi omkring underrum og ortogonalitet, herunder ortogonalt komplement og ortogonal projektion på et underrum. Dette er særlig vigtigt for at få en god geometrisk forståelse af hvad der foregår når man løser et ligningssystem, og det er helt essentielt for at forstå tilnærmelsesvise løsninger med mindste kvadraters metode i Kapitel 10.$V^\perp$ er altså samtlige vektorer som står ortogonalt på alle vektorer i $V$. At $V^\perp$ er et underrum af $\mathbb{C}^n$ følger af egenskaberne ved det indre produkt givet i Proposition 9.3.Ortogonale komplementer giver en fornuftig måde at opdele vektorrum på med forskellige egenskaber, som eksempelvis er nyttigt til at beskrive løsninger til lineære ligningssystemer. BevisVektorerne i Sætning 9.30 har særlige navne, de kaldes nemlig ortogonale projektioner på henholdsvis $V$ og $V^\perp$.På samme måde som (9.1) angiver en formel for den ortogonale projektion ind på et et-dimensionelt vektorrum (på linjen udspændt af en vektor), så giver Sætning 9.30 at man kan projicere ind på ethvert underrum af $\mathbb{C}^n$, eksempelvis et to-dimensionelt vektorrum (en plan udspændt af to vektorer) eller af en vilkårlig høj dimension $\leq n$. I modsætning til (9.1) giver Sætning 9.30 dog ikke nogen direkte formel til at udregne projektionerne $\mathbf w$ eller $\mathbf v$.Men her skal man bare kigge ind i beviset til Sætning 9.30, som afslører hvordan man kan bruge en ONB til at udregne en ortogonal projektion. Ydermere viser Pythagoras sætning hvad en ortogonal projektion $\mathbf w\in V$ af $\mathbf u$ geometisk betyder: $\mathbf w$ er vektoren i $V$ med korteste afstand til $\mathbf u$. Bevis

9.6 De fire fundamentale underrum

Som vi allerede så en indikation af i foregående eksempel, så er der en sammenhæng mellem søjlerummet af en matrix $A$ og nulrummet af $A^*$. BevisVed at indse at $(A^*)^* = A$, så får vi også fra Sætning 9.34 at $N(A^*)^\perp = C(A)$. For enhver $m\times n$ matrix har vi derfor følgende fire fundamentale underrum Det er næsten for godt til at være sandt, at ud fra en vilkårlig $m\times n$ matrix $A$, så kan søjlerum og nulrum for $A$ og $A^*$ bruges til at finde baser for $\mathbb{C}^m$ og $\mathbb{C}^n$. Bemærk at for en reel matrix $A$, så er $C(A^*) = C(A^T)$ hvilket er rækkerummet af $A$.Specifikt, hvis man nærstuderer følgende figur, som er populariseret af Gilbert Strang, så kan man med stor sikkerhed påstå at man har styr på sine fundamentale begreber, og beskrivelse af løsninger, inden for lineær algebra.Figuren ovenfor, samt en række andre figurer, er blevet brugt som redskaber til undervisning under navnet lineær algebraens fundamentalsætning (ikke at forveksle med algebraens fundamentalsætning).Figur 9.35 fortæller stort set alt hvad der er værd at vide om lineære ligningssystemer med komplekse $m\times n$ matricer $A$ med rang $r$. Enhver vektor $\mathbf x\in \mathbb{C}^n$ kan ortogonalt dekomponeres som $\mathbf x = \mathbf x_1 + \mathbf x_2$ hvor $\mathbf x_1 \in C(A^*)$ og $\mathbf x_2\in N(A)$, det vil sige at $\mathbf x_1\perp\mathbf x_2$. Hvis vi udregner matrix-vektor produktet $A\mathbf x$, ser vi $$\mathbf b = A\mathbf x = A\mathbf x_1 + A\mathbf x_2 = A\mathbf x_1$$ da vi har at komponenten $\mathbf x_2$ sendes til $A\mathbf x_2 = \mathbf 0$. Bemærk at $\mathbf b = A\mathbf x \in C(A)$. Specifikt, når vi løser et ligningssystem $A\mathbf x = \mathbf b$ har det kun en løsning hvis $\mathbf b\in C(A)$. Blandt alle løsninger vil en entydig komponent komme fra $C(A^*)$, mens $N(A)$ beskriver alle tænkelige bidrag fra de frie variable. Kun hvis $N(A) = \{\mathbf 0\}$ kan der være en entydig løsning til ligningssystemet.Vi skal se hvordan de fire fundamentale underrum på den mest fantastiske vis binder hele teorien sammen ved brug af singulær værdi dekomposition i Kapitel 12.

9.7 Opgaver