11Spektralsætning og Hermitiske matricer

Vi husker fra Kapitel 9, at for en matrix $A$ kan vi definere dens adjungerede $A^*$ ved

$A^* = \overline{A}^\textup{T}.$ I dette kapitel skal vi se på en helt særlig klasse af matricer, opkaldt efter Charles Hermite.

$\phantom{ }$

Matrix $A$ kaldes Hermitisk (eller selvadjungeret) hvis $A^* = A.$
Reel matrix $A$ kaldes symmetrisk hvis $A^\textup{T} = A.$

Bemærk, en symmetrisk matrix er Hermitisk, men det modsatte er kun sandt hvis matricen er reel.

Matricen

$\begin{pmatrix} 1 & 1-i \\ 1+i & -4 \end{pmatrix}$ er et eksempel på en Hermitisk matrix, prøv selv at tjekke efter ved at finde dens adjungerede. Prøv at overvise jer selv om, hvorfor diagonalelementerne i en Hermitisk matrix bliver nødt til at være reelle.

Matricen

$\begin{pmatrix} 1 & 2 \\ 2 & -4 \end{pmatrix}$ er et eksempel på en symmetrisk matrix (som naturligvis derfor også er Hermitisk).

Blandt de komplekse matricer fortjener de Hermitiske en særstatus. Det viser sig, at disse altid er diagonaliserbare, og endda ved brug af en ONB bestående af egenvektorer. Dette resultat kaldes spektralsætningen, og er et af højdepunkterne i noterne. Husk på, normalt kan man ikke forvente, at en matrix er diagonaliserbar. For eksempel er matricen

$\begin{pmatrix} 1 & 1\\ 0 & 1 \end{pmatrix}$ ikke diagonaliserbar.

Før vi når til diagonalisering af Hermitiske matricer, skal vi se nogle pæne egenskaber for deres egenværdier og egenvektorer.

11.1 Egenværdier og egenvektorer for Hermitiske matricer

En meget vigtig observation er, at selvom Hermitiske matricer generelt har komplekse tal som indgange, er deres egenværdier reelle tal og egenvektorer hørende til forskellige egenværdier er ortogonale. Dette er en meget stærk anvendelse af det indre produkt, og faktisk er beviset slet ikke kompliceret.

Lad $A$ være en Hermitisk matrix. Så er egenværdierne for $A$ reelle tal.

Lad $\lambda_1\neq\lambda_2$ være egenværdier for $A.$ Hvis $\mathbf v_1$ er en egenvektor hørende til $\lambda_1,$ og $\mathbf v_2$ en egenvektor hørende til $\lambda_2,$ så gælder

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

Bevis

For en egenvektor $\mathbf v$ hørende til egenværdi $\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) = \overline{\lambda} (\mathbf v\cdot \mathbf v).$ Dermed er $\lambda = \overline{\lambda}$ og vi må have $\lambda\in \mathbb{R},$ fordi $\mathbf v\neq \mathbf 0$ og dermed $\mathbf v\cdot \mathbf v \neq 0.$

Samme type argument giver ortogonaliteten af egenvektorerne $\mathbf v_1$ og $\mathbf v_2$ (dette er også et særtilfælde af Opgave 9.14):

$\lambda_1 (\mathbf v_1\cdot \mathbf v_2) = (A \mathbf v_1)\cdot \mathbf v_2 = \mathbf v_1\cdot (A \mathbf v_2) = \lambda_2 (\mathbf v_1\cdot \mathbf v_2).$ Denne identitet medfører ligningen

$(\lambda_1-\lambda_2) (\mathbf v_1\cdot \mathbf v_2) = 0,$ hvoraf $\mathbf v_1\cdot \mathbf v_2 = 0$ da $\lambda_1\neq \lambda_2.$

At egenværdierne for en Hermitisk matrix er reelle, skyldes symmetrien i matricen, for eksempel har

$\begin{pmatrix} 0 & -1\\ 1 & 0 \end{pmatrix}$ ikke reelle egenværdier. Faktisk er det ret utroligt, at hvis man stanger en vilkårlig symmetrisk matrix ud, som for eksempel

$\begin{pmatrix} 1 & 3 & 7 & 5\\ 3 & 1 & 2 & 4\\ 7 & 2 & 2 & 6\\ 5 & 4 & 6 & 1 \end{pmatrix},$ kan dens karakteristiske polynomium kun kan have reelle rødder. Det er en af konsekvenserne af Sætning 11.3.

Det er dog vigtigt at huske på, at Sætning 11.3 kun giver ortogonalitet for egenvektorer hørende til forskellige egenrum. Hvis den geometriske multiplicitet af en egenværdi er større end én, så bliver vi stadig nødt til at anvende Gram-Schmidt algoritmen (Sætning 9.10) for at finde ortogonale egenvektorer for dette egenrum.

11.2 Schur dekomposition

Den matematiske indgang til diagonalisering af Hermitiske matricer, er et klassisk resultat af Issai Schur. Hvis du kigger fremad til beviset for spektralsætningen (Sætning 11.9), vil du helt klart opdage meningen med resultatet nedenfor som kaldes Schur dekomposition.

Lad $A$ være en kvadratisk matrix. Der eksisterer en unitær matrix $U,$ så

$U^* A U$ er en øvre trekantsmatrix.

Bevis $*$

Vi beviser resultatet med induktion. Det er sandt for $1\times 1$ matricer med $U = 1.$ Antag nu, at resultatet er sandt for $(n-1)\times(n-1)$ matricer, så skal vi vise at dette medfører resultatet for $n\times n$ matricer.

Lad $A\mathbf v = \lambda\mathbf v$ for en egenværdi $\lambda$ og hvor $\lvert \mathbf v \rvert = 1.$ Korollar 6.20 og Gram-Schmidt algoritmen (Sætning 9.10) kan udvide med vektorer $\mathbf w_2,\dots,\mathbf w_n,$ således at $\{\mathbf v,\mathbf w_2,\dots,\mathbf w_n\}$ udgør en ONB for $\mathbb{C}^n.$ Vi definerer en $n\times n$ unitær matrix ved $U_1 = (\mathbf v,\mathbf w_2,\dots,\mathbf w_n).$ Bemærk at $U_1\mathbf e_1 = \mathbf v,$ så

$(U_1^*AU_1)\mathbf e_1 = U_1^{-1}A\mathbf v = \lambda U_1^{-1}\mathbf v = \lambda\mathbf e_1$ viser, at første søjle af $U_1^*AU_1$ er $\lambda\mathbf e_1.$ Så matricen har følgende blok-struktur:

$U_1^* A U_1 = \begin{pmatrix} \lambda & C \\ \mathbf 0 & B \end{pmatrix},$ hvor $B$ er $(n-1)\times (n-1)$ , $C$ er $1\times(n-1)$ og $\mathbf 0$ er en $(n-1)\times 1$ nulvektor.

Fra induktionsantagelsen findes en unitær $(n-1)\times(n-1)$ matrix $V,$ således at $V^*BV$ er en øvre trekantsmatrix. Nu udvider vi $V$ til en $n\times n$ matrix $U_2$ på følgende måde:

$U_2 = \begin{pmatrix} 1 & \mathbf 0^\textup{T} \\ \mathbf 0 & V \end{pmatrix}.$ Nullerne i søjlerne hvor $V$ indgår påvirker ikke normerne af søjlevektorerne, og tydeligvis er første søjle af $U_2$ ortogonal med de resterende søjler. Da $V$ er unitær har den ortonormale søjler (Proposition 9.19), og dermed er $U_2$ også unitær.

Vi ser på $U_2^*(U_1^*AU_1)U_2,$ hvor vi udnytter blok-strukturerne for matricerne:

$U_2^*(U_1^*AU_1)U_2 = \begin{pmatrix} 1 & \mathbf 0^\textup{T} \\ \mathbf 0 & V^* \end{pmatrix}\begin{pmatrix} \lambda & C \\ \mathbf 0 & B \end{pmatrix}\begin{pmatrix} 1 & \mathbf 0^\textup{T} \\ \mathbf 0 & V \end{pmatrix} = \begin{pmatrix} \lambda & CV \\ \mathbf 0 & V^*BV \end{pmatrix}.$ Da $V^*BV$ er en øvre trekantsmatrix, er også

$U_2^*(U_1^*AU_1)U_2 = (U_1U_2)^*A(U_1U_2)$ en øvre trekantsmatrix. Beviset afsluttes, da produktet af unitære matricer igen giver en unitær matrix (Opgave 11.4), så vi kan bruge

$U = U_1U_2.$

11.2.1 Determinant og spor fra egenværdier

Udover at Schur dekomposition kan anvendes til at bevise spektralsætningen i næste afsnit, kan den også bruges til andre mindre resultater, der udnytter den pæne struktur i en trekantsmatrix.

Vi starter med at definere sporet (på engelsk: trace) af en matrix.

Lad $A$ være en $n\times n$ matrix. Sporet af $A,$ $\mathrm{tr}(A),$ er defineret som summen af diagonalelementerne:

$\mathrm{tr}(A) = a_{11} + a_{22} + \dots + a_{nn}.$

Ud fra definitionen af sporet ses let, at $A\mapsto \mathrm{tr}(A)$ er en lineær afbildning. Men herudover gælder også, at sporet er cyklisk.

For $m\times n$ matrix $A$ og $n\times m$ matrix $B$ gælder

$\mathrm{tr}(AB) = \mathrm{tr}(BA).$

Bevis

Fra definitionen af matrixmultiplikation:

$\begin{aligned} \mathrm{tr}(AB) &= \sum_{i=1}^m (AB)_{ii} = \sum_{i=1}^m \sum_{j=1}^n A_{ij}B_{ji} \\ &= \sum_{j=1}^n \sum_{i=1}^m B_{ji}A_{ij} = \sum_{j=1}^n (BA)_{jj} = \mathrm{tr}(BA), \end{aligned}$ hvilket giver resultatet.

Der er en smuk sammenhæng mellem egenværdierne for en matrix, og matricens determinant og spor.

Lad $A$ være en kvadratisk matrix med egenværdier $\lambda_1,\dots,\lambda_n$ (gentaget efter algebraisk multiplicitet). Så gælder

$\begin{aligned} \det(A) &= \lambda_1\lambda_2\cdots\lambda_n, \\ \mathrm{tr}(A) &= \lambda_1 + \lambda_2 + \dots + \lambda_n. \end{aligned}$

Bevis

For en $n\times n$ trekantsmatrix $T$ er $\det(T)$ lig med produktet af diagonalelementerne (Proposition 5.11):

$\det(T) = t_{11}t_{22}\cdots t_{nn}.$ Men egenværdierne for $T,$ gentaget efter deres algebraiske multipliciteter, står i diagonalen (Opgave 8.8). Dermed er $\det(T)$ lig produktet af dens egenværdier.

Lad os nu se på en generel $n\times n$ matrix $A.$ Schur dekomposition (Sætning 11.4) fortæller, at der findes en unitær matrix $U,$ således at $T = U^*AU$ er en øvre trekantsmatrix. Specifikt har vi, at $A$ og $T$ er similære. Fra Opgave 8.15 har $A$ og $T$ det samme karakteristiske polynomium (og derfor samme egenværdier), samt de har samme determinant. Samlet set er

$\det(A) = \det(T) = \lambda_1\lambda_2\cdots\lambda_n.$

For sporet har vi fra Proposition 11.6, at

$\mathrm{tr}(A) = \mathrm{tr}(UTU^*) = \mathrm{tr}(TU^*U) = \mathrm{tr}(T) = \lambda_1+\lambda_2+\dots+\lambda_n.$

11.2.2 Alle kvadratiske matricer er næsten diagonaliserbare

Den næste konsekvens af Schur dekomposition vi skal se på er, at for enhver kvadratisk matrix $A,$ eksisterer en diagonaliserbar matrix $S$ vilkårligt tæt på $A.$ Det vil sige, for en given tolerance $\epsilon>0,$ kan $S$ vælges så absolut værdien for indgangene i $A-S$ er mindre end $\epsilon.$ Matematisk kaldes dette, at de diagonaliserbare matricer udgør en tæt delmængde.

De diagonaliserbare matricer udgør en tæt delmængde af de kvadratiske matricer.

Bevis

Lad $\epsilon > 0$ være vilkårlig. Lad $A$ være en kvadratisk matrix, med Schur dekomposition $A = UTU^*,$ hvor $T$ er en øvre trekantsmatrix. Vi lader nu

$S = U(T+D)U^*,$ hvor $D$ er en diagonalmatrix, således at samtlige diagonalelementer i $T+D$ er forskellige. Dette kan gøres hvor diagonalelementerne i $D$ er vilkårligt små, altså vi kan vælge $\max_i\lvert d_{ii} \rvert < \epsilon.$

Da $S$ er similær med en trekantsmatrix, med forskellige diagonalelementer, så gælder af Opgave 8.15, Opgave 8.8 og Proposition 8.14 at $S$ er diagonaliserbar.

Vi ser nu fremad mod Kapitel 12, hvor der nævnes i Bemærkning 12.6, at alle matrixnormer er ækvivalente. Så vi vælger den spektrale norm fra (12.9), og regner:

$\lVert A-S \rVert_2 = \lVert UDU^* \rVert_2 = \lVert D \rVert_2 = \max_i \lvert d_{ii} \rvert < \epsilon.$ Her brugte vi, at den spektrale norm er unitært invariant (Opgave 12.4). En anvendelse af Proposition 12.7 viser, at $\max_{i,j}\lvert c_{ij} \rvert\leq \lVert C \rVert_2$ for enhver matrix $C.$

11.3 Spektralsætningen for Hermitiske matricer

Selvom Schur dekompositionen havde et lidt teknisk bevis, bliver beviset for spektralsætningen tilgengæld ekstremt kort.

Lad $A$ være en $n\times n$ Hermitisk matrix. Der eksisterer en unitær matrix $U,$ så

$D = U^* A U$ er en diagonalmatrix med reelle indgange.

Søjlerne i $U$ er en ONB for $\mathbb{C}^n,$ bestående af egenvektorer for $A,$ og diagonalen i $D$ består af de tilsvarende egenværdier for $A,$ gentaget efter deres algebraiske multipliciteter.

Hvis $A$ er en symmetrisk matrix, kan $U$ vælges som en ortogonal matrix.

Bevis

Dette er et smukt og kort bevis, som benytter Schur dekomposition (Sætning 11.4): Der findes en unitær matrix $U,$ så

$U^* A U$ er en øvre trekantsmatrix. Men $U^* A U$ er en Hermitisk matrix da

$(U^* A U)^* = U^* A^* (U^*)^* = U^* A U.$ En øvre trekantsmatrix som er Hermitisk, bliver nødt til at være en diagonalmatrix med reelle indgange (Opgave 11.5), hvilket giver resultatet i sætningen. Relationen til egenværdier og egenvektorer for en diagonalisering er kendt fra Kapitel 8.

Antag nu at $A$ er symmetrisk, og lad $\lambda$ være en egenværdi (som er reel af Sætning 11.3). Så er $A-\lambda I$ en reel matrix, og reelle rækkeoperationer overfører denne til sin RREF. Fra Sætning 6.23 og Gram-Schmidt algoritmen (Sætning 9.10), eksisterer en reel ONB for egenrummet $\mathcal{N}(A-\lambda I).$ Nu kan reelle ONB'er fra hvert egenrum bruges til en diagonalisering, således at $U$ bliver en ortogonal matrix i denne konstruktion af Sætning 11.3.

Betragt den symmetriske matrix

$A = \begin{pmatrix} 0 & 2 & -1 \\ 2 & 3 & -2 \\ -1 & -2 & 0 \end{pmatrix}.$ Det oplyses, at $A$ har egenværdierne $\lambda = -1$ og $\lambda = 5.$ Ud fra dette vil vi finde en ortogonal matrix $U,$ så $U^\textup{T} A U$ er en diagonalmatrix, hvilket vi på forhånd ved er muligt af spektralsætningen (Sætning 11.9).

Her er det nok at finde en ONB af egenvektorer for $A.$ Dette gøres ved at finde en ONB for hvert egenrum, bemærke at egenvektorer hørende til forskellige egenrum for en symmetrisk matrix er ortogonale (Sætning 11.3), og kombinere dem til en ONB for hele $\mathbb{R}^3$ (Sætning 9.5 og Sætning 6.18). Vi kigger først på egenværdien $\lambda = -1.$ Her regner man sig frem til at

$\mathbf v_1 = \begin{pmatrix} 1 \\ 0 \\ 1 \end{pmatrix} \quad\text{og}\quad \mathbf v_2 = \begin{pmatrix} -2 \\ 1 \\ 0 \end{pmatrix} \tag{11.1}$ er en basis for egenrummet $\mathcal{N}(A+I),$ ved at løse ligningssystemet

$\begin{pmatrix} 1 & 2 & -1\\ 2 & 4 & -2\\ -1 & -2 & 1 \end{pmatrix} \mathbf v = \begin{pmatrix} 0 \\ 0 \\ 0 \end{pmatrix}.$ Se tilbage i Kapitel 6 hvordan dette relaterer sig til RREF af matricen $A+I,$ og hvordan man kan finde en basis for $\mathcal{N}(A+I).$

Vi benytter nu Gram-Schmidt algoritmen (Sætning 9.10) på vektorerne i (11.1), og kommer frem til ONB

$\mathbf w_1 = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 \\ 0 \\ 1 \end{pmatrix} \quad\text{og}\quad \mathbf w_2 = \frac{1}{\sqrt{3}}\begin{pmatrix} -1 \\ 1 \\ 1 \end{pmatrix}.$ Nu ved vi at $\dim \mathcal{N}(A-5I) = 1$ for egenværdien $\lambda=5$ (hvorfor? Hvis du ikke ved dette, kan det være en god ide at genopfriske Kapitel 8). Som ovenfor finder vi at

$\mathbf v_3 = \begin{pmatrix} -1 \\ -2 \\ 1 \end{pmatrix}$ er en basis for $\mathcal{N}(A - 5 I),$ og dermed at

$\mathbf w_3 = \frac{1}{\sqrt{6}}\begin{pmatrix} -1 \\ -2 \\ 1 \end{pmatrix}$ er en ONB for $\mathcal{N}(A-5I).$ Samlet bliver $\{\mathbf w_1, \mathbf w_2, \mathbf w_3\}$ en ONB for $\mathbb{R}^3$ bestående af egenvektorer for $A.$ Matricen $U = (\mathbf w_1,\mathbf w_2,\mathbf w_3)$ er dermed en ortogonal matrix

$U = \frac{1}{\sqrt{6}}\begin{pmatrix} \sqrt{3} & -\sqrt{2} & -1 \\ 0 & \sqrt{2} & -2 \\ \sqrt{3} & \sqrt{2} & 1 \end{pmatrix},$ som opfylder

$U^\textup{T} A U = \begin{pmatrix} -1 & 0 & 0\\ 0 & -1 & 0\\ 0 & 0 & 5 \end{pmatrix}.$

11.4 Min-max princip og sammenfletning af egenværdier

For en Hermitisk matrix $A,$ bemærker vi at

$(A\mathbf x)\cdot \mathbf x = \mathbf x\cdot (A^*\mathbf x) = \mathbf x\cdot (A\mathbf x) = \overline{(A\mathbf x)\cdot \mathbf x},$ så for ethvert $\mathbf x$ er $(A\mathbf x)\cdot \mathbf x$ et reelt tal.

Følgende resultat er en meget berømt sætning, kendt som min-max princippet. Det er en af konsekvenserne af spektralsætningen, og bruges blandt andet til numerisk bestemmelse af egenværdier for Hermitiske matricer.

Lad $A$ være en $n\times n$ Hermitisk matrix, med egenværdier $\lambda_1\geq \dots \geq \lambda_n$ (gentaget efter algebraisk multiplicitet) i aftagende rækkefølge.

For underrum $W\subseteq \mathbb{C}^n,$ optimerer vi $(A\mathbf x)\cdot\mathbf x$ over enhedsvektorerne i $W^\perp$ eller $W$ :

$\begin{aligned} \mu_W &= \max_{\mathbf x\in W^\perp,\, \lvert \mathbf x \rvert = 1} (A\mathbf x)\cdot \mathbf x, \\ \nu_W &= \min_{\mathbf x\in W,\, \lvert \mathbf x \rvert = 1} (A\mathbf x)\cdot \mathbf x. \end{aligned}$ Så findes $\lambda_j$ ved at minimere $\mu_W$ (eller maksimere $\nu_W$ ) blandt alle underrum $W\subseteq \mathbb{C}^n$ af en given dimension:

$\lambda_j = \min_{\dim(W)=j-1} \mu_W = \max_{\dim(W)=j} \nu_W.$ Minimum/maksimum opnås ved $\lambda_j = \mu_{W_j} = \nu_{\widetilde{W}_j},$ hvor $W_j$ udspændes af ortonormale egenvektorer til $\lambda_1,\dots,\lambda_{j-1},$ mens $\widetilde{W}_j$ udspændes af ortonormale egenvektorer til $\lambda_1,\dots,\lambda_j.$

Bevis

Beviset er opdelt, relateret til $\mu_W$ (min-max) og $\nu_W$ (max-min), og kan læses uafhængigt af hinanden.

Min-max

Fra spektralsætningen (Sætning 11.9) har $\mathbb{C}^n$ en ONB af egenvektorer $\{\mathbf v_1,\dots,\mathbf v_n\},$ hvor $\mathbf v_j$ hører til egenværdi $\lambda_j.$ Definer underrummene

$\begin{aligned} W_j &= \mathrm{span}\{\mathbf v_1,\dots,\mathbf v_{j-1}\}, \\ W_j^\perp &= \mathrm{span}\{\mathbf v_j,\dots,\mathbf v_n\}. \end{aligned}$ Så har vi $\dim(W_j) = j-1.$

Lad $\mathbf x_0\in W_j^\perp$ med $\lvert \mathbf x_0 \rvert = 1,$ det vil sige

$\mathbf x_0 = a_j\mathbf v_j + \dots + a_n\mathbf v_n,$ hvor vektoren $\mathbf a = (a_j,\dots,a_n)^\textup{T}$ opfylder $\lvert \mathbf a \rvert = 1$ af Proposition 9.8. Af ortonormalitet har vi

$(A\mathbf x_0)\cdot \mathbf x_0 = \lambda_j\lvert a_j \rvert^2 + \dots + \lambda_n\lvert a_n \rvert^2 \leq \lambda_j\lvert \mathbf a \rvert^2 = \lambda_j.$ Vi har også $(A\mathbf v_j)\cdot\mathbf v_j = \lambda_j,$ hvor det bemærkes at $\mathbf v_j\in W_j^\perp$ og $\lvert \mathbf v_j \rvert=1.$ Dermed er

$\mu_{W_j} = \lambda_j. \tag{11.2}$ Hvis vi kalder

$\delta_j = \min_{\dim(W)=j-1} \mu_W,$ så er $\delta_j\leq \lambda_j$ af (11.2). Vi mangler at vise $\delta_j \geq \lambda_j.$

Lad nu $W\subseteq \mathbb{C}^n$ være et underrum med $\dim(W) = j-1.$ Da $\dim(W^\perp)+\dim(W_{j+1}) = n+1,$ så må

$W^\perp \cap W_{j+1} \neq \{\mathbf 0\}.$ Lad nu $\mathbf x_0 \in W^\perp \cap W_{j+1}$ med $\lvert \mathbf x_0 \rvert = 1,$ det vil sige

$\mathbf x_0 = a_1\mathbf v_1 + \dots + a_j\mathbf v_j,$ hvor $\mathbf a = (a_1,\dots,a_j)^\textup{T}$ opfylder $\lvert \mathbf a \rvert = 1.$ Igen, af ortonormalitet får vi

$(A\mathbf x_0)\cdot \mathbf x_0 = \lambda_1\lvert a_1 \rvert^2 + \dots + \lambda_j\lvert a_j \rvert^2 \geq \lambda_j\lvert \mathbf a \rvert^2 = \lambda_j.$ Dermed har vi $\mu_W \geq \lambda_j$ for alle underrum $W\subseteq \mathbb{C}^n$ med $\dim(W)=j-1,$ og derfor er $\delta_j\geq \lambda_j.$

Max-min

Fra spektralsætningen (Sætning 11.9) har $\mathbb{C}^n$ en ONB af egenvektorer $\{\mathbf v_1,\dots,\mathbf v_n\},$ hvor $\mathbf v_j$ hører til egenværdi $\lambda_j.$ Definer underrummene

$\begin{aligned} \widetilde{W}_j &= \mathrm{span}\{\mathbf v_1,\dots,\mathbf v_{j}\}, \\ \widehat{W}_j &= \mathrm{span}\{\mathbf v_j,\dots,\mathbf v_n\}. \end{aligned}$ Så har vi $\dim(\widetilde{W}_j) = j$ og $\dim(\widehat{W}_j) = n-j+1.$

Lad $\mathbf x_0\in \widetilde{W}_j$ med $\lvert \mathbf x_0 \rvert = 1,$ det vil sige

$\mathbf x_0 = a_1\mathbf v_1 + \dots + a_j\mathbf v_j,$ hvor vektoren $\mathbf a = (a_1,\dots,a_j)^\textup{T}$ opfylder $\lvert \mathbf a \rvert = 1$ af Proposition 9.8. Af ortonormalitet har vi

$(A\mathbf x_0)\cdot \mathbf x_0 = \lambda_1\lvert a_1 \rvert^2 + \dots + \lambda_j\lvert a_j \rvert^2 \geq \lambda_j\lvert \mathbf a \rvert^2 = \lambda_j.$ Vi har også $(A\mathbf v_j)\cdot\mathbf v_j = \lambda_j,$ hvor det bemærkes at $\mathbf v_j\in \widetilde{W}_j$ og $\lvert \mathbf v_j \rvert=1.$ Dermed er

$\nu_{\widetilde{W}_j} = \lambda_j. \tag{11.3}$ Hvis vi kalder

$\delta_j = \max_{\dim(W)=j} \nu_W,$ så er $\delta_j\geq \lambda_j$ af (11.3). Vi mangler at vise $\delta_j \leq \lambda_j.$

Lad nu $W\subseteq \mathbb{C}^n$ være et underrum med $\dim(W) = j.$ Da $\dim(W)+\dim(\widehat{W}_j) = n+1,$ så må

$W \cap \widehat{W}_j \neq \{\mathbf 0\}.$ Lad nu $\mathbf x_0 \in W \cap \widehat{W}_j$ med $\lvert \mathbf x_0 \rvert = 1,$ det vil sige

$\mathbf x_0 = a_j\mathbf v_j + \dots + a_n\mathbf v_n,$ hvor $\mathbf a = (a_1,\dots,a_j)^\textup{T}$ opfylder $\lvert \mathbf a \rvert = 1.$ Igen, af ortonormalitet får vi

$(A\mathbf x_0)\cdot \mathbf x_0 = \lambda_j\lvert a_j \rvert^2 + \dots + \lambda_n\lvert a_n \rvert^2 \leq \lambda_j\lvert \mathbf a \rvert^2 = \lambda_j.$ Dermed har vi $\nu_W \leq \lambda_j$ for alle underrum $W\subseteq \mathbb{C}^n$ med $\dim(W)=j,$ og derfor er $\delta_j \leq \lambda_j.$

Ganske kort kan man fra Sætning 11.11 skrive

$\lambda_j = \min_{\substack{W\subseteq \mathbb{C}^n \\ \dim(W)=j-1}}\max_{\substack{\mathbf x\in W^\perp \\ \lvert \mathbf x \rvert = 1}} \enskip(A\mathbf x)\cdot \mathbf x = \max_{\substack{W\subseteq \mathbb{C}^n \\ \dim(W)=j}}\min_{\substack{\mathbf x\in W \\ \lvert \mathbf x \rvert = 1}} \enskip(A\mathbf x)\cdot \mathbf x,$ hvor navnet min-max princippet bliver åbenlyst.

Dette gør det muligt at vise følgende besynderlige resultat af Augustin-Louis Cauchy, som siger at hvis en matrix $B$ fremkommer ved at slette et antal rækker og søjler fra en Hermitisk matrix $A,$ så vil deres egenværdier være sammenflettede.

Lad $A$ være en $n\times n$ Hermitisk matrix, og lad $B$ fremkomme ved at slette $k$ rækker og $k$ søjler (samme række- og søjlenumre) fra $A.$

Lad $\lambda_1\geq\dots\geq\lambda_n$ være egenværdierne for $A,$ og lad $\mu_1\geq\dots\geq\mu_{n-k}$ være egenværdierne for $B$ (gentaget efter algebraisk multiplicitet) i aftagende rækkefølge.

Så gælder

$\lambda_{j+k} \leq \mu_j \leq \lambda_{j}, \quad j = 1,\dots,n-k.$

Bevis

Vi kan anvende et lige antal række-/søjleombytninger på $A,$ således at $B$ bliver placeret i øverste venstre hjørne af matricen, og således at de tilsvarende operationer på en identitetsmatrix igen giver en identitetsmatrix. Dette ændrer ikke på egenværdierne af Sætning 5.4. Så vi kan antage, at dette allerede er udgangspunktet.

Lad $P$ bestå af de første $n-k$ søjler af $I_n,$ så er $B = P^\textup{T}AP$ og derved er $B$ også en Hermitisk matrix. For $\mathbf x\in\mathbb{C}^{n-k}$ udvider vi med nuller i bunden til $\widehat{\mathbf x}\in\mathbb{C}^n,$ svarende til $P\mathbf x = \widehat{\mathbf x}.$

Lad $\widetilde{W}_j$ være som i Sætning 11.11, men relateret til matricen $B.$ Så gælder

$\begin{aligned} \mu_j &= \min_{\mathbf 0\neq\mathbf x\in \widetilde{W}_j} \frac{(B\mathbf x)\cdot \mathbf x}{\lvert \mathbf x \rvert^2} \\ &= \min_{\mathbf 0\neq\mathbf x\in \widetilde{W}_j} \frac{(P^\textup{T}AP\mathbf x)\cdot \mathbf x}{\lvert \mathbf x \rvert^2} \\ &= \min_{\mathbf 0\neq\mathbf x\in \widetilde{W}_j} \frac{(A\widehat{\mathbf x})\cdot \widehat{\mathbf x}}{\lvert \widehat{\mathbf x} \rvert^2} \\ &\leq \max_{\substack{W\subseteq \mathbb{C}^n \\ \dim(W)=j}}\min_{\mathbf 0\neq\mathbf y\in W} \frac{(A\mathbf y)\cdot \mathbf y}{\lvert \mathbf y \rvert^2} \\ &= \lambda_j, \end{aligned}$ hvor Sætning 11.11 blev anvendt først på $B,$ og dernæst på $A.$

Lad nu $W_{j}$ være som i Sætning 11.11, men relateret til matricen $B.$ Bemærk, at $\dim(W_j^\perp) = n-k-j+1$ her. Så har vi

$\begin{aligned} \mu_j &= \max_{\mathbf 0\neq\mathbf x\in W_{j}^\perp} \frac{(B\mathbf x)\cdot \mathbf x}{\lvert \mathbf x \rvert^2} \\ &= \max_{\mathbf 0\neq\mathbf x\in W_j^\perp} \frac{(A\widehat{\mathbf x})\cdot \widehat{\mathbf x}}{\lvert \widehat{\mathbf x} \rvert^2} \\ &\geq \min_{\substack{W\subseteq \mathbb{C}^n \\ \dim(W)=k+j-1}}\max_{\mathbf 0\neq\mathbf y\in W^\perp} \frac{(A\mathbf y)\cdot \mathbf y}{\lvert \mathbf y \rvert^2} \\ &= \lambda_{j+k}, \end{aligned}$ hvor Sætning 11.11 igen først blev anvendt på $B,$ og dernæst på $A.$

11.5 Positiv semidefinit matricer

En vigtig struktur for matricer, som ofte indgår i anvendelser, er positiv semidefinit matricer.

En Hermitisk matrix $A$ kaldes positiv definit hvis

$(A\mathbf x)\cdot\mathbf x > 0 \textup{ for alle } \mathbf x\neq\mathbf 0.$ $A$ kaldes positiv semidefinit hvis " $>$ " erstattes med " $\geq$ ".

Hvis $-A$ er positiv (semi)definit, kaldes $A$ negativ (semi)definit.

Positiv (semi)definit kan relateres til egenværdierne $\lambda_1,\dots,\lambda_n$ af $A$ via diagonalisering. Fra spektralsætningen (Sætning 11.9) eksisterer unitær matrix $U$ og diagonalmatrix $D,$ med $\lambda_1,\dots,\lambda_n$ i diagonalen, så

$A = UDU^*.$ Da $U^*$ er invertibel er $\mathbf x\neq \mathbf 0,$ hvis og kun hvis, $\mathbf y\neq \mathbf 0$ hvor $\mathbf y = U^*\mathbf x.$ Så har vi

$(A\mathbf x)\cdot\mathbf x = (UDU^*\mathbf x)\cdot \mathbf x = (D\mathbf y)\cdot \mathbf y = \lambda_1\lvert y_1 \rvert^2+\dots+\lambda_n\lvert y_n \rvert^2.$ Dermed er en Hermitisk matrix $A$ positiv definit præcis hvis alle dens egenværdier er positive, og positiv semidefinit hvis egenværdierne er ikke-negative. Tilsvarende negativ definit hvis egenværdierne er negative, og negativ semidefinit hvis egenværdierne er ikke-positive.

11.5.1 Hessematrix og optimering

For en funktion $f \colon U\to \mathbb{R},$ hvor $U\subseteq\mathbb{R}^n$ er en åben mængde og hvor $f$ er to gange kontinuert differentiabel, kan vi konstruere en Hessematrix (på engelsk: Hessian), navngivet efter Ludwig Otto Hesse:

$H_f(\mathbf x) = \begin{pmatrix} \frac{\partial^2}{\partial x_1^2}f(\mathbf x) & \frac{\partial^2}{\partial x_1\partial x_2}f(\mathbf x) & \cdots & \frac{\partial^2}{\partial x_1\partial x_n}f(\mathbf x) \\[2mm] \frac{\partial^2}{\partial x_2\partial x_1}f(\mathbf x) & \frac{\partial^2}{\partial x_2^2}f(\mathbf x) & \cdots & \frac{\partial^2}{\partial x_2\partial x_n}f(\mathbf x) \\[2mm] \vdots & \vdots & \ddots & \vdots \\[2mm] \frac{\partial^2}{\partial x_n\partial x_1}f(\mathbf x)& \frac{\partial^2}{\partial x_n\partial x_2}f(\mathbf x) & \cdots & \frac{\partial^2}{\partial x_n^2}f(\mathbf x) \end{pmatrix}. \tag{11.4}$ Fra vores antagelser kan man ombytte rækkefølgen af de afledede, og derfor er $H_f$ en symmetrisk matrix i hvert punkt.

Lad $\mathbf x_0\in U,$ og lad $B$ være en kugle i $\mathbb{R}^n$ med centrum i $\mathbf 0$ og lille nok radius, så $\mathbf x_0+\mathbf h \in U$ for $\mathbf h\in B.$ Så kan vi undersøge funktionsværdierne for $f,$ når vi går fra $\mathbf x_0$ i en retning $\mathbf h\in B$ til punktet $\mathbf x_0+\mathbf h.$ Her indgår gradienten $\nabla f$ og Hessematricen $H_f$ i anden ordens approksimationen fra Taylor's sætning i flere variable:

$f(\mathbf x_0+\mathbf h) = f(\mathbf x_0) + \nabla f(\mathbf x_0)\cdot \mathbf h + \tfrac{1}{2}(H_f(\mathbf x_0)\mathbf h)\cdot \mathbf h + o(\lvert \mathbf h \rvert^2),$ hvor restleddet bruger lille-o notation. Hvis $\mathbf x_0$ er et indre kritisk punkt, det vil sige $\nabla f(\mathbf x_0) = \mathbf 0,$ så har vi

$f(\mathbf x_0+\mathbf h) = f(\mathbf x_0) + \tfrac{1}{2}(H_f(\mathbf x_0)\mathbf h)\cdot \mathbf h + o(\lvert \mathbf h \rvert^2), \tag{11.5}$ og nu beskriver $(H_f(\mathbf x_0)\mathbf h)\cdot \mathbf h$ hvordan funktionsværdien ændres fra $f(\mathbf x_0),$ når man bevæger sig en lille smule fra $\mathbf x_0$ i retning $\mathbf h$ :

Hvis $H_f(\mathbf x_0)$ er positiv definit, er $(H_f(\mathbf x_0)\mathbf h)\cdot \mathbf h > 0$ for alle retninger $\mathbf h,$ og derfor vil $f$ vokse i alle disse retninger i en lille omegn omkring $\mathbf x_0$ (så restleddet er lille nok). Derfor er $\mathbf x_0$ et isoleret lokalt minimum.
Hvis $H_f(\mathbf x_0)$ er negativ definit, er $(H_f(\mathbf x_0)\mathbf h)\cdot \mathbf h < 0$ for alle retninger $\mathbf h,$ og derfor vil $f$ aftage i alle disse retninger i en lille omegn omkring $\mathbf x_0$ (så restleddet er lille nok). Derfor er $\mathbf x_0$ et isoleret lokalt maksimum.
Hvis $H_f(\mathbf x_0)$ er indefinit, det vil sige matricen både har positive og negative egenværdier, så vil $f$ vokse i nogle retninger og aftage i andre retninger. Derfor er $\mathbf x_0$ et såkaldt saddelpunkt.

Saddelpunkt fra Wikipedia, baseret på en funktion af to variable: $f(x_1,x_2) = x_1^2-x_2^2.$

Hvis $H_f(\mathbf x_0)$ kun er positiv/negativ semidefinit, kan vi ikke umiddelbart afgøre noget på grund af restleddet. Specifikt, hvis $\mathbf h$ er en egenvektor for en egenværdi 0 for $H_f(\mathbf x_0),$ er kun restleddet tilbage med afhængighed af $\mathbf h$ i (11.5). Derfor ved vi ikke (uden at undersøge situationen nærmere) om funktionen vokser, aftager eller er konstant i denne retning.

Hessematricen indgår også i Newton's metode, en særdeles hurtig iterativ numerisk metode, til at bestemme kritiske punkter for en funktion, med kvadratisk lokal konvergens. Mange af de mest popuplære metoder til optimering, som Gauss-Newton, Levenberg-Marquardt og Broyden-Fletcher-Goldfarb-Shanno (BFGS), bruger approksimationer af Hessematricen for at undgå anden ordens afledede, men dog med et tab i konvergenshastighed.

11.5.2 Konjugerede gradienters metode

Hvis $A$ er en meget stor matrix (måske med mange tusinde/millioner rækker og søjler), kan det være en uoverskuelig opgave at udregne $A^{-1}$ direkte, og i praksis kan iterative metoder til løsning af meget store lineære ligningssystemer være mere relevante end Gauss elimination.

Mange af sådanne iterative metoder baserer sig på de såkaldte Krylov underrum:

$\mathcal{K}_k(A,\mathbf b) = \mathrm{span}\{\mathbf b,A\mathbf b,A^2\mathbf b,\dots,A^{k-1}\mathbf b\}.$ For en $n\times n$ positiv definit matrix $A,$ er en særlig kraftig metode kendt under navnet konjugerede gradienters metode (på engelsk: conjugate gradient method). $A$ er invertibel, så til en højreside $\mathbf b$ vil $A\mathbf x=\mathbf b$ have den entydige løsning $\mathbf x=A^{-1}\mathbf b.$ Det er en konsekvens af Cayley-Hamilton sætning (Sætning B.13) at $\mathbf x \in\mathcal{K}_n(A,\mathbf b).$

Da $A$ er positiv definit, kan defineres et indre produkt på $\mathbb{C}^n$ (andet end det Euklidiske indre produkt) ved

$\langle \mathbf u,\mathbf v \rangle_A = (A\mathbf u)\cdot \mathbf v. \tag{11.6}$ Det vil sige, at (11.6) opfylder alle de samme egenskaber som i Proposition 9.2 (det Euklidiske indre produkt svarer til $A=I$ ). Hvis to vektorer $\mathbf u$ og $\mathbf v$ er ortogonale i $\langle \cdot,\cdot \rangle_A,$ kaldes de konjugerede med hensyn til $A.$ Fra det indre produkt kommer også en norm $\lvert \mathbf u \rvert_A = \sqrt{\langle \mathbf u,\mathbf u \rangle_A}.$

Konjugerede gradienters metode er følgende. Man starter ud fra $\mathbf x_0 = \mathbf 0,$ residualen $\mathbf r_0 = \mathbf b-A\mathbf x_0 = \mathbf b$ og $\mathbf u_0 = \mathbf r_0.$ Følgende udføres nu iterativt, hvor et indeks $k$ forøges efter hver iteration, startende med $k=0$ :

$\begin{aligned} \alpha_k &= \frac{\lvert \mathbf r_k \rvert^2}{\lvert \mathbf u_k \rvert_A^2}, \\ \mathbf x_{k+1} &= \mathbf x_k+\alpha_k\mathbf u_k, \\ \mathbf r_{k+1} &= \mathbf r_k-\alpha_k A\mathbf u_k, \\ \beta_k &= \frac{\lvert \mathbf r_{k+1} \rvert^2}{\lvert \mathbf r_k \rvert^2}, \\ \mathbf u_{k+1} &= \mathbf r_{k+1} + \beta_k\mathbf u_k. \end{aligned}\tag{11.7}$

Nu bemærker vi, at

$\begin{aligned} \mathbf b - A\mathbf x_{k+1} - \mathbf r_{k+1} &= \mathbf b - A\mathbf x_k -\alpha_k A\mathbf u_k - \mathbf r_{k+1} \\ &= \mathbf b - A\mathbf x_k -\mathbf r_k \\ &\enskip\vdots \\ &= \mathbf b - A\mathbf x_0 - \mathbf r_0 = \mathbf 0. \end{aligned}$ Derfor er

$\mathbf r_{k+1} = \mathbf b-A\mathbf x_{k+1}$ residualen for den $(k+1)$ 'te iteration. Hvis $\mathbf r_{k+1} = \mathbf 0$ undervejs er $\mathbf x_{k+1} = \mathbf x$ løsningen, og vi siger at metoden har konvergeret.

Konjugerede gradienters metode konvergerer inden for højst $n$ iterationer.

Hvis vi for et indeks $k$ har $\mathbf r_k\neq\mathbf 0$ gælder:

Vi har
$\mathcal{K}_{k+1}(A,\mathbf b) = \mathrm{span}\{\mathbf x_1,\dots,\mathbf x_{k+1}\} = \mathrm{span}\{\mathbf u_0,\dots,\mathbf u_k\} = \mathrm{span}\{\mathbf r_0,\dots,\mathbf r_k\}.$
$\mathbf r_0,\dots,\mathbf r_k$ er indbyrdes ortogonale i det Euklidiske indre produkt, mens $\mathbf u_0,\dots,\mathbf u_k$ er indbyrdes konjugerede med hensyn til $A.$

Bevis $*$

Antag at $\mathbf r_j\neq \mathbf 0$ og $\mathbf u_j\neq \mathbf 0$ for $j\leq k,$ hvilket er brugbart for at vise (i) og (ii). Et efterfølgende induktionsbevis viser, at dette følger fra antagelsen $\mathbf r_k \neq \mathbf 0.$

(i): Da $\mathbf x_0=\mathbf 0$ og $\mathbf u_0=\mathbf r_0=\mathbf b,$ ses ved induktion (udført i flere omgange på formlerne i (11.7)):

$\mathrm{span}\{\mathbf x_1,\dots,\mathbf x_{k+1}\} = \mathrm{span}\{\mathbf u_0,\dots,\mathbf u_k\} = \mathrm{span}\{\mathbf r_0,\dots,\mathbf r_k\}.$ Tilsvarende ved induktion på $\mathbf r_{k+1}=\mathbf r_k-\alpha_kA\mathbf u_k,$ og ovenstående, ses at

$\mathcal{K}_{k+1}(A,\mathbf b) = \mathrm{span}\{\mathbf r_0,\dots,\mathbf r_k\}.$ (ii): Overvej hvis vi i metoden brugte

$\beta_k = -\frac{\langle \mathbf r_{k+1},\mathbf u_k \rangle_A}{\lvert \mathbf u_k \rvert_A^2}, \tag{11.8}$ som vi nu viser er lig med den i metoden oprindeligt angivne $\beta_k.$ Ud fra (11.8) og definitionen af $\mathbf u_{k+1}$ haves

$\langle \mathbf u_{k+1},\mathbf u_k \rangle_A = \langle \mathbf r_{k+1},\mathbf u_k \rangle_A+\beta_k\lvert \mathbf u_k \rvert_A^2 = 0,$ så $\mathbf u_{k+1}$ og $\mathbf u_k$ er konjugerede. Derfor, ved brug af ovenstående for iteration $k-1$ (samt ved $k=0$ ved vi at $\mathbf u_0=\mathbf r_0$ ), har vi at

$\alpha_k = \frac{\lvert \mathbf r_k \rvert^2}{\lvert \mathbf u_k \rvert_A^2} = \frac{\lvert \mathbf r_k \rvert^2}{\langle \mathbf u_k,\mathbf r_k \rangle_A},$ og derfor

$\mathbf r_{k+1}\cdot\mathbf r_k = \lvert \mathbf r_k \rvert^2 - \alpha_k\langle \mathbf u_k,\mathbf r_k \rangle_A = 0.$ Dermed er $\mathbf r_{k+1}$ og $\mathbf r_k$ ortogonale. Nu bruges

$A\mathbf u_k = \frac{1}{\alpha_k}(\mathbf r_k-\mathbf r_{k+1}),$ samt ortogonalitet og at $A$ er Hermitisk, til at vise

$\langle \mathbf r_{k+1},\mathbf u_k \rangle_A = -\frac{\lvert \mathbf r_{k+1} \rvert^2}{\alpha_k}.$ Ved at indsætte definitionen af $\alpha_k,$ er $\beta_k$ som angivet i metoden.

Vi vil nu vise at

$\mathbf r_{k+1}\cdot \mathbf r_j = 0 = \langle \mathbf u_{k+1},\mathbf u_j \rangle_A, \quad j \leq k. \tag{11.9}$ Induktionsstarten er allerede vist ovenfor, at $\mathbf r_1$ er ortogonal med $\mathbf r_0$ og $\mathbf u_1$ er konjugeret med $\mathbf u_0.$ Antag derfor, at (11.9) holder for $\mathbf r_k$ og $\mathbf u_k$ og med indeks $j\leq k-1.$

Vi har allerede ovenfor vist, at $\mathbf r_{k+1}$ er ortogonal med $\mathbf r_k$ og $\mathbf u_{k+1}$ er konjugeret med $\mathbf u_k,$ så lad $j \leq k-1.$ Så har vi

$\langle \mathbf u_k,\mathbf r_j \rangle_A = \langle \mathbf u_k,\mathbf u_j \rangle_A - \beta_{j-1}\langle \mathbf u_k,\mathbf u_{j-1} \rangle_A = 0,$ og derfor

$\mathbf r_{k+1}\cdot \mathbf r_{j} = \mathbf r_{k}\cdot\mathbf r_{j} -\alpha_k\langle \mathbf u_k,\mathbf r_j \rangle_A = 0.$ Vi har også

$\langle \mathbf r_{k+1},\mathbf u_j \rangle_A = \frac{1}{\alpha_j}\mathbf r_{k+1}\cdot(\mathbf r_{j}-\mathbf r_{j+1}) = 0,$ og derfor

$\langle \mathbf u_{k+1},\mathbf u_j \rangle_A = \langle \mathbf r_{k+1},\mathbf u_j \rangle_A + \beta_{k}\langle \mathbf u_{k},\mathbf u_j \rangle_A = 0.$ Dette afslutter induktionsbeviset for (11.9).

Til slut vises, at metoden konvergerer inden for $n$ iterationer. $\mathcal{K}_j(A,\mathbf b)\subseteq \mathcal{K}_{j'}(A,\mathbf b)$ for $j\leq j',$ og hvis der er lighed holder denne lighed også for alle indeks større end $j'.$ Samtidig er dimensionen af et Krylov underrum maksimalt $n,$ da det er underrum af $\mathbb{C}^n.$ Derfor er $\mathcal{K}_{n}(A,\mathbf b)$ det største Krylov underrum.

Hvis $\dim\mathcal{K}_n(A,\mathbf b)=k+1\leq n,$ så må $\mathbf r_{j}\neq\mathbf 0$ for $j\leq k,$ samt at $\mathbf r_{k+1}\in\mathrm{span}\{\mathbf r_0,\dots,\mathbf r_{k}\}.$ Men vi har også at $\mathbf r_{j'}\cdot \mathbf r_{j} = 0$ for $j'\neq j,$ og dermed er $\mathbf r_{k+1} = \mathbf 0.$ Det betyder at $\mathbf x_{k+1} = \mathbf x.$

Typisk er man slet ikke interesseret i at anvende helt op til $n$ iterationer for store systemer, og man ser sig tilfreds med at være inden for en tilpas lille tolerance på $\mathbf x.$ Det kan vises, at der er følgende maksimale relative fejl på iterationerne af metoden (og ofte er fejlen meget lavere):

$\frac{\lvert \mathbf x-\mathbf x_k \rvert}{\lvert \mathbf x \rvert} \leq 2\biggl(\frac{\sqrt{\operatorname{\kappa}(A)}-1}{\sqrt{\operatorname{\kappa}(A)}+1}\biggr)^k, \tag{11.10}$ hvor $\operatorname{\kappa}(A)\geq 1$ er det såkaldte konditionstal for $A,$ som beskriver hvor numerisk stabilt det lineære ligningssystem er; vi definerer og ser nærmere på konditionstallet i Afsnit 12.3.

En kvadratisk funktion (her med reelle matricer/vektorer/skalarer)

$f(\mathbf x) = \tfrac{1}{2}(A\mathbf x)\cdot \mathbf x - \mathbf b\cdot\mathbf x + c,$ hvor $A$ er symmetrisk, har gradient

$\nabla f(\mathbf x) = A\mathbf x-\mathbf b.$ Så at finde et kritisk punkt for en kvadratisk funktion, er ækvivalent med at løse det lineære ligningssystem $A\mathbf x=\mathbf b.$ Dermed kan konjugerede gradienters metode også anvendes til at minimere/maksimere kvadratiske funktioner i flere variable, baseret på en positiv definit matrix. Dette anvendes i sequential quadratic programming (SQP), som kan løse meget generelle ikke-lineære optimeringsproblemer, ved i stedet at løse en følge af optimeringsproblemer med kvadratiske funktioner.

Eksempel fra Wikipedia: Konjugerede gradienters metode (rød) overfor metoden steepest descent (grøn), ved minimering af en kvadratisk funktion i to variable (niveaukurver i blå). Konjugerede gradienters metode konvergerer her i to iterationer.

11.5.3 Positiv kvadratrod og absolut værdi af matricer

Når det kommer til kvadratrødder, opfører positiv semidefinit matricer sig på samme måde som ikke-negative tal. Til ethvert ikke-negativt tal $x,$ findes en entydig ikke-negativ kvadratrod $\sqrt{x},$ som løser $\sqrt{x}^2 = x.$ Tilsvarende kan man snakke om en positiv kvadratrod $\sqrt{A}$ af en positiv semidefinit matrix $A.$

Lad $A$ være en positiv semidefinit matrix, med egenværdier $\lambda_1,\dots,\lambda_n$ (gentaget efter algebraisk multiplicitet). Fra diagonaliseringen af $A,$ med unitær matrix $U,$

$A = U\begin{pmatrix} \lambda_1 & & \\ & \ddots & \\ & & \lambda_n \end{pmatrix}U^*,$ defineres den positive kvadratrod af $A$ :

$\sqrt{A} = U\begin{pmatrix} \sqrt{\lambda_1} & & \\ & \ddots & \\ & & \sqrt{\lambda_n} \end{pmatrix}U^*.$

Notationen med $\sqrt{A}$ kommer naturligvis af følgende udregning:

$\sqrt{A}\sqrt{A} = U\begin{pmatrix} \sqrt{\lambda_1}^2 & & \\ & \ddots & \\ & & \sqrt{\lambda_n}^2 \end{pmatrix}U^* = A.$ $\sqrt{A}$ også er positiv semidefinit (og positiv definit, hvis $A$ er positiv definit).

Lad $A$ og $B$ være positiv semidefinit matricer. Hvis $B^2 = A$ er $B = \sqrt{A}.$

Bevis

Af spektralsætningen (Sætning 11.9) eksisterer en ONB $\{\mathbf v_1,\dots,\mathbf v_n\}$ for $\mathbb{C}^n$ bestående af egenvektorer for $B,$ hørende til egenværdier $\lambda_1,\dots,\lambda_n.$ Dermed har vi

$A\mathbf v_j = B^2\mathbf v_j = \lambda_j^2\mathbf v_j.$ Da $B$ er positiv semidefinit, er $\lambda_j\geq 0$ for $j = 1,\dots,n.$ Derfor har vi, per konstruktion af $\sqrt{A}$ :

$\mathcal{N}(B-\lambda_jI) \subseteq \mathcal{N}(A-\lambda_j^2I) = \mathcal{N}(\sqrt{A}-\lambda_jI).$ Af ovenstående er $B\mathbf v_j = \sqrt{A}\mathbf v_j,$ og da $\{\mathbf v_1,\dots,\mathbf v_n\}$ er en basis for $\mathbb{C}^n$ er $B=\sqrt{A}.$

Senere i Afsnit 12.1.1 gøres der rede for, at for enhver $m\times n$ matrix $A$ er $A^* A$ en $n\times n$ positiv semidefinit matrix, som derfor har en positiv kvadratrod. Denne kaldes absolut værdien af $A.$

Lad $A$ være en $m\times n$ matrix. Så er absolut værdien af $A$ den $n\times n$ positiv semidefinit matrix

$\lvert A \rvert = \sqrt{A^* A}.$

11.5.4 Dekompositioner med positiv semidefinit matricer

I numerisk løsning af lineære ligningssystemer bruges typisk dekompositioner med trekantsmatricer, da løsning med trekantsmatricer er hurtigt og numerisk stabilt. I alle standard computerimplementationer for løsning af lineære ligningssystemer, anvendes altid Cholesky dekomposition hvis systemmatricen er positiv semidefinit (ofte uden man eksplicit får det at vide).

Lad $A$ være en positiv semidefinit matrix. Der eksisterer en øvre trekantsmatrix $R,$ så

$A = R^*R.$ Hvis $A$ er positiv definit, er $R$ og $R^*$ invertible.

Hvis $A$ er en reel matrix, kan $R$ vælges som en reel matrix.

Bevis

Vi gør brug af QR dekompositionen af $\sqrt{A}$ (Sætning 9.24),

$\sqrt{A} = QR,$ hvor $Q$ er unitær og $R$ er en øvre trekantsmatrix. Hvis $A$ er reel, er $\sqrt{A}$ reel, og så kan $Q$ og $R$ vælges som reelle matricer af Sætning 9.24.

Så er

$A = \sqrt{A}\sqrt{A} = (\sqrt{A})^*\sqrt{A} = R^*Q^*QR = R^*R.$ Hvis $A$ er positiv definit har $\sqrt{A}$ positive egenværdier, så nulrummet $\mathcal{N}(\sqrt{A})$ er trivielt og $\sqrt{A}$ er invertibel. Dermed er

$R = Q^*\sqrt{A}$ invertibel af Sætning 4.16. Af Sætning 9.17 er $R^*$ også invertibel.

Følgende resultat springer mest naturligt ud af den singulære værdi dekomposition, som er emnet i Kapitel 12. Vi inkluderer det dog her, da det omhandler $\lvert A \rvert,$ som er positiv semidefinit.

Den polære dekomposition nedenfor kan relateres til den polære form for et komplekst tal (dette er tilfældet for en $1\times 1$ matrix). Den unitære matrix $U$ svarer (i en vis forstand) til en rotation, mens $\lvert A \rvert$ og $\lvert A^* \rvert$ svarer til skalering. Beviset viser også hvordan matricen $U$ konstrueres ud fra den singulære værdi dekomposition.

Lad $A$ være en kvadratisk matrix. Der eksisterer en unitær matrix $U,$ så

$A = U\lvert A \rvert = \lvert A^* \rvert U.$

Bevis

Beviset gør brug af den singulære værdi dekomposition af $A$ fra Sætning 12.1. Det vil sige

$A = W\Sigma V^*,$ hvor $W$ og $V$ er unitære, og $\Sigma$ er en kvadratisk diagonalmatrix (da $A$ er kvadratisk) med ikke-negative tal. Herfra regner man sig hurtigt frem til

$\lvert A \rvert = V\Sigma V^* \quad \text{og} \quad \lvert A^* \rvert = W\Sigma W^*.$ Vi vælger $U$ som

$U = WV^*,$ som er unitær af Opgave 11.4. Dermed bliver

$U\lvert A \rvert = (WV^*)(V\Sigma V^*) = W\Sigma V^* = A,$ og

$\lvert A^* \rvert U = (W\Sigma W^*)(WV^*) = W\Sigma V^* = A,$ som forventet.

11.6 Struktur af kvadratiske former

Lad $A$ være en $n\times n$ matrix. Så kaldes funktionen

$q_A(\mathbf x) = (A\mathbf x)\cdot \mathbf x, \quad \mathbf x\in\mathbb{C}^n$ for den tilhørende kvadratiske form.

Vi har allerede set flere anvendelser af kvadratiske former, for eksempel i min-max princippet (Sætning 11.11) og for positiv semidefinit matricer (Afsnit 11.5). I disse anvendelser har vi dog kun set på kvadratiske former hørende til Hermitiske matricer. I dette afsnit skal vi se, at $q_A$ altid kan relateres til kvadratiske former for Hermitiske matricer.

Vi starter ud med følgende egenskab, der som konsekvens viser, at en kvadratisk form har reelle funktionsværdier, hvis den hører til en Hermitisk matrix.

For enhver kvadratisk matrix $A$ gælder $q_A = \overline{q_{A^*}}.$

Bevis

Beviset er en kort udregning med anvendelse af egenskaber for det indre produkt og Sætning 9.16:

$q_A(\mathbf x) = (A\mathbf x)\cdot \mathbf x = \mathbf x\cdot (A^*\mathbf x) = \overline{(A^*\mathbf x)\cdot\mathbf x} = \overline{q_{A^*}(\mathbf x)}.$

En kvadratisk matrix kan generelt omskrives, ved brug af Hermitiske matricer:

$A = A_{\textup{R}}+iA_{\textup{I}}, \tag{11.11}$ hvor

$A_{\textup{R}} = \frac{1}{2}(A+A^*) \quad\text{og}\quad A_{\textup{I}} = \frac{1}{2i}(A-A^*). \tag{11.12}$ En hurtig hovedregning viser, at $A_{\textup{R}}$ og $A_{\textup{I}}$ er Hermitiske matricer. Dette leder frem til følgende karakterisering af kvadratiske former.

Lad $A$ være en kvadratisk matrix.

Den tilhørende kvadratiske form opfylder
$q_A = q_{A_\textup{R}} + i q_{A_{\textup{I}}},$ det vil sige at $\mathrm{Re}(q_A) = q_{A_\textup{R}}$ og $\mathrm{Im}(q_A) = q_{A_{\textup{I}}}$ .
Der er entydighed i den forstand, at hvis
$q_A = q_B + iq_C,$ hvor $B$ og $C$ er Hermitiske, så er $B = A_{\textup{R}}$ og $C = A_{\textup{I}}$ .

Bevis

(i): Dette kommer direkte ved at indsætte (11.11) i $q_A$ , samt at $q_{A_\textup{R}}$ og $q_{A_\textup{I}}$ har reelle værdier af Lemma 11.21.

(ii): Dette reduceres til at vise, at hvis $E$ er Hermitisk og $q_E \equiv 0,$ så er $E = \mathbf 0$ . I den konkrete situation har vi de to tilfælde, $E = B-A_{\textup{R}}$ og $E = C-A_{\textup{I}}$ , som kommer af at se på realdel og imaginærdel hver for sig.

Men da $q_E\equiv 0$ er $E$ positiv semidefinit, og har derfor en positiv kvadratrod $\sqrt{E},$ som blandt andet er en Hermitisk matrix. Vi får:

$0 = q_E(\mathbf x) = (E\mathbf x)\cdot \mathbf x = \lvert \sqrt{E}\mathbf x \rvert^2,$ for alle $\mathbf x\in\mathbb{C}^n$ . Det viser at $\sqrt{E} = \mathbf 0,$ og derfor er $E = \sqrt{E}^2 = \mathbf 0$ .

En direkte konsekvens af Sætning 11.22 er, at hvis $A$ og $\mathbf x$ er reelle, så må $q_{A_\textup{I}}(\mathbf x) = 0$ . I det tilfælde gælder

$q_A(\mathbf x) = q_{A_{\textup{R}}}(\mathbf x), \quad \mathbf x\in\mathbb{R}^n,$ hvor $A_{\textup{R}}$ er den entydige symmetriske matrix, der tilhører den samme reelle kvadratiske form.

For en Hermitisk matrix så vi i Afsnit 11.5, hvordan et invertibelt variabelskifte kan overføre den kvadratiske form til at tilhøre diagonalmatricen fra en diagonalisering. Faktisk kan man gå endnu længere med kvadratiske former, hvor positive egenværdier også skaleres til $1$ og negative egenværdier skaleres til $-1,$ således at man får den simplest mulige kvadratiske form.

Lad $A$ være en Hermitisk matrix med $n_+$ antal positive egenværdier og $n_-$ antal negative egenværdier. Der eksisterer en invertibel matrix $M,$ så variabelskiftet $\mathbf y = M\mathbf x$ giver

$q_A(\mathbf x) = q_\Lambda(\mathbf y) = \lvert y_1 \rvert^2 + \cdots + \lvert y_{n_+} \rvert^2 - \lvert y_{n_+ +1} \rvert^2 - \cdots - \lvert y_{n_+ + n_-} \rvert^2,$ hvor

$\Lambda = \begin{pmatrix} I_{n_+} \\ & -I_{n_-} \\ & & \mathbf 0 \end{pmatrix}.$

Bevis

For diagonalisering $A = UDU^*$ med unitær matrix $U$ og diagonalmatrix $D,$ lad egenværdierne $\lambda_1,\dots,\lambda_n$ være i rækkefølge hvor først er de positive, så de negative, og til sidst egenværdi $0$ . Overvej funktionen $\rho \colon \mathbb{R} \to (0,\infty)$ givet ved

$\rho(t) = \begin{cases} \sqrt{\lvert t \rvert} & \text{for }t\neq 0, \\ 1 & \text{for }t = 0, \end{cases}$ og definer diagonalmatricen

$P = \begin{pmatrix} \rho(\lambda_1) & & \\ & \ddots & \\ & & \rho(\lambda_n) \end{pmatrix}.$ Så er $P$ invertibel og

$D = P\Lambda P^*,$ da multiplikation af diagonalmatricer sker elementvist (Proposition 8.1). Nu definerer vi

$M = (UP)^*,$ som er invertibel af Sætning 4.16, hvilket giver

$A = UDU^* = UP\Lambda P^*U^* = M^*\Lambda M.$ Ved brug af det invertible variabelskifte $\mathbf y = M\mathbf x$ , får vi derfor

$q_A(\mathbf x) = (M^*\Lambda M\mathbf x)\cdot\mathbf x = (\Lambda M\mathbf x)\cdot(M\mathbf x) = q_{\Lambda}(\mathbf y).$

Hvis $A$ er Hermitisk og $S$ er invertibel, så er $B = S^*AS$ også Hermitisk. Men $A$ og $B$ er ikke nødvendigvis similære ( $S$ behøver ikke være unitær her). Det vil sige, generelt er egenværdierne for $A$ og $B$ forskellige. Dette leder frem til følgende berømte sætning af James Sylvester, som fortæller at fortegnene af egenværdierne er bevaret.

Lad $A$ være en Hermitisk matrix, $S$ en invertibel matrix og $B = S^*AS.$ Uafhængigt af $S,$ og talt med algebraisk multiplicitet, har $A$ og $B$ samme antal positive egenværdier og samme antal negative egenværdier.

Bevis $*$

Tag en vilkårlig $n\times n$ Hermitisk matrix $C.$ Af spektralsætningen (Sætning 11.9) findes en ONB $\{\mathbf v_1,\dots,\mathbf v_n\}$ af egenvektorer for $C$ hørende til egenværdier $\mu_1,\dots,\mu_n$ (gentaget efter algebraisk multiplicitet), og i rækkefølge så $\mu_1,\dots,\mu_k$ er positive mens $\mu_{k+1},\dots,\mu_n$ er ikke-positive. Vi definerer nu

$V_{>0} = \mathrm{span}\{\mathbf v_1,\dots,\mathbf v_k\} \quad \text{og} \quad V_{\leq 0} = \mathrm{span}\{\mathbf v_{k+1},\dots,\mathbf v_n\}.$ Lad

$\mathbf x_{>0} = \sum_{j=1}^k a_j\mathbf v_j \quad \text{og} \quad \mathbf x_{\leq 0} = \sum_{j=k+1}^n b_j\mathbf v_j,$ så gælder af ortonormalitet at

$\begin{aligned} q_C(\mathbf x_{>0}) &= \sum_{j=1}^k \mu_j\lvert a_j \rvert^2 > 0 \quad \text{for} \quad{\mathbf x_{>0}\neq \mathbf 0}, \\ q_C(\mathbf x_{\leq 0}) &= \sum_{j=k+1}^n \mu_j\lvert b_j \rvert^2 \leq 0. \end{aligned}$ Dermed er $q_C$ positiv definit på underrummet $V_{>0},$ mens $q_C$ er negativ semidefinit på $V_{\leq 0}.$ Vi vil nu vise, at blandt underrum $W$ hvorpå $q_C$ er positiv definit, har $V_{>0}$ maksimal dimension.

For et sådan $W$ gælder $W\cap V_{\leq 0} = \{\mathbf 0\},$ og begge er underrum af $\mathbb{C}^n,$ det vil sige

$\dim(W) + \dim(V_{\leq 0}) \leq n = \dim(V_{>0}) + \dim(V_{\leq 0}),$ altså at $\dim(W) \leq \dim(V_{>0}).$

Hvis $V_{<0}$ er underrummet udspændt af egenvektorerne for de negative egenværdier af $C,$ findes et helt tilsvarende bevis for, at $V_{<0}$ er et underrum af maksimal dimension hvorpå $q_C$ er negativ definit.

Lad os nu vende tilbage til situationen i sætningen. Da $A$ er Hermitisk er $B = S^*AS$ også Hermitisk. Lad $M$ og $\Lambda$ være som i Proposition 11.23 og lad $\mathbf y = MS\mathbf x,$ så er $q_B(\mathbf x) = q_\Lambda(\mathbf y).$ Da $M$ og $S$ er invertible, så er den maksimale dimension af underrum hvorpå $q_B$ er positiv definit (eller negativ definit), lig den maksimale dimension af underrum hvorpå $q_{\Lambda}$ er positiv definit (eller negativ definit).

Fra ovenstående bevis, først med $C = B$ og dernæst med $C = \Lambda,$ så har disse to matricer samme antal positive/negative egenværdier, hvilket fra konstruktionen af $\Lambda$ er det tilsvarende antal positive/negative egenværdier for $A.$

11.7 Spektralsætningen for normale matricer

Vi ser nu på det lidt mere generelle resultat end Sætning 11.9, som viser at alle normale matricer kan diagonaliseres, det vil sige matricer som opfylder

$A^* A = AA^*.$ Her skal man ikke lade sig snyde af navnet normal matrix, da der er masser af "unormale" matricer. Et eksempel på en normal matrix, som ikke nødvendigvis er Hermitisk, er en unitær matrix.

En $n\times n$ matrix $A$ opfylder

$A^*A = AA^*,$ hvis og kun hvis, der eksisterer en unitær matrix $U,$ så

$D = U^* A U$ er en diagonalmatrix.

Søjlerne i $U$ er en ONB for $\mathbb{C}^n,$ bestående af egenvektorer for $A,$ og diagonalen i $D$ består af de tilsvarende egenværdier for $A,$ gentaget efter deres algebraiske multipliciteter.

Bevis

Antag at en unitær matrix $U$ eksisterer, således at $D = U^* AU$ er en diagonalmatrix. Så har vi

$\begin{aligned} A^* A &= (UDU^*)^*(UDU^*) = UD^*(U^*U)DU^* \\ &= UD^*DU^* = UDD^*U^* = UD(U^*U)D^*U^* = AA^*. \end{aligned}$ Her brugte vi, at kvadratiske diagonalmatricer kommuterer (Proposition 8.1), samt at $U^*U= I.$

Lad os nu vise den anden retning i "hvis og kun hvis" resultatet, altså antag at $A$ er en normal matrix, det vil sige $A^*A=AA^*.$ Vi kan via (11.11) skrive

$A = A_{\textup{R}} + iA_{\textup{I}},$ hvor $A_{\textup{R}}$ og $A_{\textup{I}}$ er de Hermitiske matricer fra (11.12). Det ses også fra (11.12) at $A_{\textup{R}}$ og $A_{\textup{I}}$ kommuterer da $A$ er normal. Der findes derfor en unitær matrix $U,$ som simultant diagonaliserer begge disse matricer (Opgave 11.11):

$A = UD_{\textup{R}}U^* + iUD_{\textup{I}}U^* = U(D_{\textup{R}}+iD_{\textup{I}})U^*.$ Her er $D_{\textup{R}}$ og $D_{\textup{I}}$ reelle diagonalmatricer, med henholdsvis egenværdierne for $A_{\textup{R}}$ og $A_{\textup{I}}$ . Hermed ses også, at realdel af egenværdierne for $A$ er egenværdier for $A_{\textup{R}},$ og imaginærdel af egenværdierne for $A$ er egenværdier for $A_{\textup{I}}.$

Hermitiske matricer er normale, og det viser sig at være lige præcis de normale matricer hvor alle egenværdierne er reelle, hvilket også ses at være den specifikke forskel i resultaterne for Sætning 11.9 og Sætning 11.25.

Der gælder tilsvarende for normale matricer, at egenvektorer hørende til forskellige egenværdier er ortogonale.

Lad $A$ være en normal matrix, det vil sige $A^*A=AA^*.$

$A\mathbf v = \lambda\mathbf v,$ hvis og kun hvis, $A^*\mathbf v = \overline{\lambda}\mathbf v.$
Lad $\lambda_1\neq\lambda_2$ være egenværdier for $A.$ Hvis $\mathbf v_1$ er en egenvektor hørende til $\lambda_1,$ og $\mathbf v_2$ en egenvektor hørende til $\lambda_2,$ så gælder
$\mathbf v_1\cdot \mathbf v_2 = 0.$ Det vil sige, at egenvektorer hørende til forskellige egenrum for $A$ er ortogonale.

Bevis

(i): Fra spektralsætningen (Sætning 11.25) findes en unitær matrix $U$ så $A = UDU^*,$ hvor $D$ er en diagonalmatrix indeholdende egenværdierne for $A$ efter deres algebraiske multipliciteter. Men så er $A^* = UD^*U^*,$ hvilket betyder at $\lambda$ er egenværdi for $A,$ hvis og kun hvis, $\overline{\lambda}$ er egenværdi for $A^*,$ og med samme algebraisk multiplicitet. Tilsvarende indeholder $U$ de tilhørende ONB'er for egenrummene, som derfor opfylder

$\mathcal{N}(A-\lambda I) = \mathcal{N}(A^*-\overline{\lambda}I).$ (ii): Vi gør brug af (i) til dette resultat, og får

$\lambda_1(\mathbf v_1\cdot\mathbf v_2) = (A\mathbf v_1)\cdot\mathbf v_2 = \mathbf v_1\cdot(A^*\mathbf v_2) = \mathbf v_1\cdot(\overline{\lambda_2}\mathbf v_2) = \lambda_2(\mathbf v_1\cdot\mathbf v_2).$ Dermed har vi

$(\lambda_1-\lambda_2)(\mathbf v_1\cdot\mathbf v_2) = 0,$ hvoraf $\mathbf v_1\cdot \mathbf v_2 = 0$ da $\lambda_1\neq \lambda_2.$

Lad os overveje den to-dimensionale rotationsmatrix

$R_\theta = \begin{pmatrix} \cos(\theta) & -\sin(\theta) \\ \sin(\theta) & \phantom{-}\cos(\theta) \end{pmatrix}.$ Produktet $R_\theta\mathbf v$ for en vektor $\mathbf v\in\mathbb{R}^2,$ roterer $\mathbf v$ med en vinkel $\theta$ mod urets retning (se også Eksempel 4.3).

Det er ikke kompliceret at tjekke, at $R_\theta$ er en ortogonal matrix (prøv at tjekke dette selv), og derfor også en normal matrix. Det er klart at $R_\theta$ ikke er symmetrisk, undtagen hvis $\theta$ er et heltalsmultiplum af $\pi,$ så $\sin(\theta)= 0.$ Derfor får vi brug for Sætning 11.25 i stedet for Sætning 11.9.

$R_\theta$ har egenværdi $\lambda_1 = \mathrm{e}^{i\theta}$ med tilhørende enhedsegenvektor

$\mathbf w_1 = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 \\ -i \end{pmatrix},$ samt egenværdi $\lambda_2 = \mathrm{e}^{-i\theta}$ med tilhørende enhedsegenvektor

$\mathbf w_2 = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 \\ i \end{pmatrix}.$ $\mathbf w_1$ og $\mathbf w_2$ er ortogonale enhedsvektorer, så $U = (\mathbf w_1,\mathbf w_2)$ er en unitær matrix. Vi har derfor følgende diagonalisering af rotationsmatricen:

$R_\theta = U\begin{pmatrix} \mathrm{e}^{i\theta} & \\ & \mathrm{e}^{-i\theta} \end{pmatrix} U^* = \frac{1}{2}\begin{pmatrix} 1 & 1 \\ -i & i \end{pmatrix}\begin{pmatrix} \mathrm{e}^{i\theta} & \\ & \mathrm{e}^{-i\theta} \end{pmatrix}\begin{pmatrix} 1 & i \\ 1 & -i \end{pmatrix}.$ $U$ afhænger ikke af $\theta,$ og kan derfor bruges til diagonalisering for enhver vinkel.

11.8 Opgaver

Gør helt eksplicit rede for, ved direkte udregning (uden brug af Sætning 11.3), 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.

Hvilke af nedenstående udsagn er rigtige?

En Hermitisk matrix er kvadratisk.

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

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

$A^*A$ er en Hermitisk matrix.

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

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

Hvilke af nedenstående matricer er øvre trekantsmatricer?

$\begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}.$

$\begin{pmatrix} 1 & i\\ 0 & 1 \end{pmatrix}.$

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

$\begin{pmatrix} 1 & 0\\ 1 & 1 \end{pmatrix}.$

Vis at produktet af to unitære matricer er en unitær matrix.

Lad $T$ være en Hermitisk trekantsmatrix. Hvorfor bliver $T$ nødt til at være en diagonalmatrix med reelle indgange?

Lad

$A = \begin{pmatrix} 2 & 1 - i\\ 1 + i & 1 \end{pmatrix}.$ Find en unitær matrix som diagonaliserer $A.$

Udregn en ONB for $\mathbb{R}^3$ af egenvektorer for matricen

$A = \begin{pmatrix} 0 & 0 & 1\\ 0 & 1 & 0\\ 1 & 0 & 0 \end{pmatrix}.$ Find dernæst en ortogonal matrix $U,$ så $U^\textup{T} A U$ er en diagonalmatrix.

Gør rede for, at det karakteristiske polynomium til matricen

$A = \begin{pmatrix} 1 & 1 & 1\\ 1 & 1 & 1\\ 1 & 1 & 1 \end{pmatrix}$ er $\lambda^2 (3-\lambda).$ Benyt dette til at vise, at

$A^n = 3^{n-1} A$ for naturlige tal $n.$ Find dernæst en ortogonal matrix $U,$ så $U^\textup{T} AU$ er en diagonalmatrix.

Gør rede for, at der lige så godt kunne stå "nedre trekantsmatrix", som "øvre trekantsmatrix", i Schur dekompositionen (Sætning 11.4).

Hint

Lad $A$ være kvadratisk, og start med at bruge Schur dekomposition som angivet i Sætning 11.4, men for matricen $A^*.$ Det vil sige, der er en unitær matrix $U,$ så

$T = U^*A^*U$ er en øvre trekantsmatrix. Hvad kan nu siges om $T^*,$ og hvad er dens forbindelse til $A$ ?

(Eksamen januar 2021)

Lad en kompleks $3\times 3$ matrix $A$ være givet ved

$A = \begin{pmatrix} 0 & 0 & -i \\ 0 & 0 & 1 \\ i & 1 & -1 \end{pmatrix}.$

Gør rede for, at $A$ ikke er invertibel.
Gør rede for, uden at regne egenværdier og egenvektorer, at $A$ er diagonaliserbar.
Vis at vektorerne
$\mathbf v_1 = \begin{pmatrix} i \\ -1 \\ 2 \end{pmatrix}, \quad \mathbf v_2 = \begin{pmatrix} -i \\ 1 \\ 1 \end{pmatrix}, \quad \mathbf v_3 = \begin{pmatrix} i \\ 1 \\ 0 \end{pmatrix}, \quad \mathbf v_4 = \begin{pmatrix} 2 \\ 2i \\ -4i \end{pmatrix}$ er egenvektorer for $A.$
Bestem en unitær matrix $U$ og en diagonalmatrix $D,$ således at
$D = U^*AU.$

I denne opgave viser vi følgende resultat om simultan diagonalisering (sammenlign med Sætning 8.16):

Lad $A$ og $B$ være Hermitiske matricer. Så gælder $AB=BA,$ hvis og kun hvis, der eksisterer en unitær matrix $U,$ så både

$U^* AU \qquad \text{og} \qquad U^* BU$ er reelle diagonalmatricer. Hvis både $A$ og $B$ er symmetriske matricer, kan $U$ vælges som en ortogonal matrix.

Hint

Opgaven går ud på at gennemgå beviset for Sætning 8.16. Udnyt spektralsætningen (Sætning 11.9) til diagonaliseringer i beviset, og gør blandt andet rede for, at matricen $C$ i beviset dermed også bliver Hermitisk. Du får sikkert også brug for resultatet i Opgave 11.4.

Dette resultat kan eksempelvis bruges til at give et meget kort og intuitivt bevis for spektralsætningen for normale matricer (Sætning 11.25).

Vi generaliserer nu Opgave 11.11 til normale matricer:

Lad $A$ og $B$ være normale matricer (dvs. $A^*A=AA^*$ og $B^*B=BB^*$ ). Så gælder $AB=BA,$ hvis og kun hvis, der eksisterer en unitær matrix $U,$ så både

$U^* AU \qquad \text{og} \qquad U^* BU$ er diagonalmatricer.

Hint

Opgaven går ud på at gennemgå beviset for Sætning 8.16. Udnyt spektralsætningen (Sætning 11.25) til diagonaliseringer i beviset, og gør blandt andet rede for, at matricen $C$ i beviset dermed også bliver normal, $C^*C = CC^*.$ Du får sikkert også brug for resultatet i Opgave 11.4.

Gør rede for, at resultatet af spektralsætningen (Sætning 11.9 og Sætning 11.25) alternativt kan skrives

$A = \sum_{j=1}^r \lambda_j P_j,$ hvor $\lambda_1,\dots,\lambda_r$ er de forskellige egenværdier af $A,$ og $P_j$ er den ortogonale projektionsmatrix på egenrummet hørende til $\lambda_j.$