12Singulær værdi dekomposition

I forrige kapitel viste spektralsætningen, at enhver Hermitisk matrix kan diagonaliseres, ved basisskifte med en ONB bestående af egenvektorer. Et næsten tilsvarende resultat holder for alle matricer, også rektangulære matricer. Vi skal til kulminationen af kurset: Den meget vigtige singulær værdi dekomposition (SVD). Her laves basisskifte med to (måske forskellige) ONB'er for at opnå en diagonalmatrix. Baserne bliver valgt ud fra de fire fundamentale underrum, som vi studerede i slutningen af Kapitel 9.

12.1 SVD

SVD er et af de vigtigste resultater, der bruges i både anvendelser (til effektive beregninger og lav-dimensional approksimation), og i teori for f.eks. numeriske metoder. Vi skal se lidt mere til dette i de sidste afsnit af kapitlet.Beviset for Sætning 12.1 gennemgås i de følgende afsnit, både da det på fin vis gør brug af teorien, som er gennemgået i kurset, men også fordi det præcis viser, hvordan de forskellige matricer bestemmes i praksis.

12.1.1 De singulære værdier

Vi tager udgangspunkt i en $m\times n$ matrix $A,$ og bemærker at hvis vi ganger $A^*$ på fra venstre, så får vi en $n\times n$ matrix $A^* A.$ Denne nye kvadratiske matrix har nogle pæne egenskaber:

1. $A^* A$ er Hermitisk, og har derfor reelle egenværdier af Sætning 11.3.
2. Alle egenværdier for $A^* A$ er ikke-negative.

Den anden egenskab vises således: Lad $A^* A\mathbf v = \lambda \mathbf v$ for en egenvektor $\mathbf v\neq \mathbf 0$ og en egenværdi $\lambda.$ Nu kan vi lave følgende udregning, hvor vi anvender Sætning 9.16: $$\lambda\lvert \mathbf v \rvert^2 = \lambda(\mathbf v\cdot \mathbf v) = (A^*A\mathbf v)\cdot\mathbf v = (A\mathbf v)\cdot(A\mathbf v) = \lvert A\mathbf v \rvert^2.$$ Vi ser at enhver egenværdi for $A^* A$ opfylder: $$\lambda = \frac{\lvert A\mathbf v \rvert^2}{\lvert \mathbf v \rvert^2} \geq 0.$$ Vi kan nu sortere egenværdierne for $A^* A$ i aftagende rækkefølge, $$\lambda_1\geq \dots \geq \lambda_r > 0 \quad\text{og}\quad \lambda_{r+1}=\dots=\lambda_n = 0,$$ hvor vi husker at gentage dem efter deres algebraiske multipliciteter.De singulære værdier er kvadratroden af de positive egenværdier for $A^*A$:

12.1.2 De højre singulære vektorer

Da $A^* A$ er en Hermitisk matrix ved vi fra spektralsætningen (Sætning 11.9), at der findes en $n\times n$ unitær matrix $V = (\mathbf v_1,\dots,\mathbf v_n),$ bestående af egenvektorer for $A^* A,$ således at $$A^*A = V\begin{pmatrix} \lambda_1 & & \\ & \ddots & \\ & & \lambda_n \end{pmatrix}V^* = V\begin{pmatrix} \sigma_1^2 & & \\ & \ddots & \\ & & \sigma_r^2 \\ & & & 0 \\ & & & & \ddots \\ & & & & & 0 \end{pmatrix}V^*.$$ Vi har at $\{\mathbf v_{r+1},\dots,\mathbf v_n\}$ udgør en ONB for egenrummet $\mathcal{N}(A^*A) = \mathcal{N}(A)$ (Lemma 10.3). De resterende $\{\mathbf v_1,\dots,\mathbf v_r\}$ udgør en ONB for $\mathcal{N}(A)^\perp = \mathcal{C}(A^*)$ (Sætning 9.33).

12.1.3 De venstre singulære vektorer

Vi starter med at definere de første $r$ venstre singulære vektorer, ud fra de tilsvarende højre singulære vektorer: Vi skal nu overbevise os selv om, at disse vektorer er ortonormale. Dette gøres ved følgende udregning $$\mathbf u_i\cdot \mathbf u_j = \frac{1}{\sigma_i\sigma_j}(A\mathbf v_i)\cdot(A\mathbf v_j) = \frac{1}{\sigma_i\sigma_j}(A^*A\mathbf v_i)\cdot \mathbf v_j,$$ og vi husker at $\mathbf v_i$ er egenvektor for $A^* A$ med egenværdi $\sigma_i^2,$ samt $\mathbf v$-vektorerne er ortonormale. Vi har derfor $$\mathbf u_i\cdot \mathbf u_j = \frac{\sigma_i^2}{\sigma_i\sigma_j}(\mathbf v_i\cdot \mathbf v_j) = \begin{cases} 0 & \text{for } i\neq j, \\ 1 & \text{for } i = j. \end{cases}$$ I forrige afsnit så vi, at $\{\mathbf v_1,\dots,\mathbf v_r\}$ er en ONB for $\mathcal{C}(A^*) = \mathcal{N}(A)^\perp,$ så en afbildning af $A$ på denne basis (se f.eks. Figur 9.4), må altså udspænde hele søjlerummet for $A.$ Fra (12.3) ved vi nu, at $\{\mathbf u_1,\dots,\mathbf u_r\}$ er en ONB for $\mathcal{C}(A).$Men hvad så med de resterende venstre singulære vektorer $\{\mathbf u_{r+1},\dots,\mathbf u_{m}\}$? De kan udregnes som en vilkårlig ONB for $\mathcal{N}(A^*) = \mathcal{C}(A)^\perp,$ ved brug af Gram-Schmidt algoritmen. Der er mange forskellige ONB'er for et vektorrum, så der er en vis valgfrihed her, tilsvarende som der er ved bestemmelse af de sidste højre singulære vektorer, som kan vælges som en vilkårlig ONB for $\mathcal{N}(A).$

12.1.4 Sammensætning af delresultaterne til SVD

Vi kan nu sammensætte delresultaterne for at få SVD'en i Sætning 12.1. Da $\{\mathbf v_1,\dots,\mathbf v_n\}$ er en ONB for $\mathbb{C}^n,$ er ligheden $A = U\Sigma V^*$ det samme som $$A\mathbf v_i = (U\Sigma V^*)\mathbf v_i \tag{12.4}$$ for alle $i=1,\dots,n.$ Vi vil altså vise ligheden (12.4).Fra ortonormaliteten af $\mathbf v$-vektorerne gælder $$V^*\mathbf v_i = \begin{pmatrix} \mathbf v_i\cdot \mathbf v_1 \\ \mathbf v_i\cdot \mathbf v_2 \\ \vdots \\ \mathbf v_i\cdot \mathbf v_n \end{pmatrix} = \mathbf e_i,$$ altså den $i$'te standardbasisvektor i $\mathbb{C}^n.$Dernæst, ved at gange med diagonalmatricen $\Sigma,$ får vi udtrukket den $i$'te søjle af $\Sigma$: $$\Sigma V^* \mathbf v_i = \Sigma\mathbf e_i = \begin{cases} \sigma_i \widetilde{\mathbf e}_i & \text{for } i=1,\dots,r, \\ \mathbf 0 & \text{for } i=r+1,\dots,n. \end{cases}$$ Her er $\widetilde{\mathbf e}_i$ også den $i$'te standardbasisvektor, men denne gang for $\mathbb{C}^m$ (da $\Sigma$ er en $m\times n$ matrix).For $i>r$ har vi derfor $U\Sigma V^*\mathbf v_i = \mathbf 0,$ men dette er netop lig med $A\mathbf v_i,$ da $\{\mathbf v_{r+1},\dots,\mathbf v_n\}$ er vektorer i $\mathcal{N}(A).$ Nu mangler vi kun at vise (12.4) for $i = 1,\dots,r,$ og her skal vi bruge sammenhængen mellem de venstre og højre singulære vektorer i (12.3): $$U\Sigma V^*\mathbf v_i = \sigma_i U\widetilde{\mathbf e}_i = \sigma_i\mathbf u_i = A\mathbf v_i.$$

12.1.5 Eksempel på udregning af SVD

Lad os grundigt gennemgå et eksempel på udregning af SVD for matricen $$A = \begin{pmatrix} 1 & i \\ 1 & i \\ -i & -1 \end{pmatrix}.$$ Først skal de singulære værdier og de højre singulære vektorer bestemmes ud fra diagonalisering af den Hermitiske matrix $$A^* A = \begin{pmatrix} 3 & i \\ -i & 3 \end{pmatrix}.$$ Vi får det karakteristiske polynomium $$\det(A^* A - \lambda I) = (3-\lambda)^2-(-i)i = \lambda^2-6\lambda+8,$$ som har rødderne $\lambda_1 = 4$ og $\lambda_2 = 2.$ Dermed er $\sigma_1 = \sqrt{\lambda_1} = 2$ og $\sigma_2 = \sqrt{\lambda_2} = \sqrt{2}$ de singulære værdier for $A,$ og vi har $$\Sigma = \begin{pmatrix} 2 & 0 \\ 0 & \sqrt{2} \\ 0 & 0 \end{pmatrix}.$$ Da egenværdierne for $A^* A$ begge har algebraisk multiplicitet $1,$ vil deres geometriske multipliciteter tilsvarende være $1$ af Proposition 8.14. Ved at se på matricerne $$A^*A-4I = \begin{pmatrix} -1 & i \\ -i & -1 \end{pmatrix} \quad\text{og}\quad A^*A-2I = \begin{pmatrix} 1 & i \\ -i & 1 \end{pmatrix},$$ kan vi forholdsvist let indse at vektorerne $$\mathbf v_1 = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 \\ -i \end{pmatrix} \quad\text{og}\quad \mathbf v_2 = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 \\ i \end{pmatrix}$$ udgør ONB'er for egenrummene, hørende til henholdsvis $\lambda_1$ og $\lambda_2.$ Dermed er $$V = (\mathbf v_1,\mathbf v_2) = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 & 1 \\ -i & i \end{pmatrix},$$ og derfor $$V^* = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 & i \\ 1 & -i \end{pmatrix}.$$ Nu anvendes (12.3) til at finde de første to venstre singulære vektorer: $$\begin{aligned} \mathbf u_1 &= \frac{1}{\sigma_1}A\mathbf v_1 = \frac{1}{2}\begin{pmatrix} 1 & i \\ 1 & i \\ -i & -1 \end{pmatrix}\frac{1}{\sqrt{2}}\begin{pmatrix} 1 \\ -i \end{pmatrix} = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 \\ 1 \\ 0 \end{pmatrix}, \\ \mathbf u_2 &= \frac{1}{\sigma_2}A\mathbf v_2 = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 & i \\ 1 & i \\ -i & -1 \end{pmatrix}\frac{1}{\sqrt{2}}\begin{pmatrix} 1 \\ i \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \\ -i \end{pmatrix}. \end{aligned}$$ Til slut skal vi finde $\mathbf u_3$ som ONB for $\mathcal{N}(A^*),$ hvilket også svarer til nulrummet for matricen $(\mathbf u_1,\mathbf u_2)^*$ da $\mathcal{N}(A^*) = \mathcal{C}(A)^\perp.$ Ved at inspicere $\mathbf u_1$ og $\mathbf u_2,$ ser vi at $$\mathbf u_3 = \frac{1}{\sqrt{2}}\begin{pmatrix} -1 \\ 1 \\ 0 \end{pmatrix}$$ er en enhedsvektor ortogonal med $\mathbf u_1$ og $\mathbf u_2.$ Derfor er $$U = (\mathbf u_1,\mathbf u_2,\mathbf u_3) = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 & 0 & -1 \\ 1 & 0 & 1 \\ 0 & -\sqrt{2}i & 0 \end{pmatrix},$$ og vi har $A = U\Sigma V^*.$

12.2 Approksimation med lav-rang matricer

En mere kompakt måde at opskrive en SVD på, som tager højde for, at de sidste $\mathbf u$-vektorer og $\mathbf v$-vektorer ikke har betydning for matrixproduktet, er ved kun at se på de første $r = \mathrm{rang}(A)$ søjler i $U$ og $V$; disse forkortede matricer kaldes $U_r = (\mathbf u_1,\dots,\mathbf u_r)$ og $V_r = (\mathbf v_1,\dots,\mathbf v_r).$ Tilsvarende kalder vi $\Sigma_r$ for $r\times r$ diagonalmatricen med de singulære værdier i diagonalen. Så har vi $$A = U\Sigma V^* = U_r\Sigma_rV_r^* = \sigma_1 \mathbf u_1\mathbf v_1^* + \sigma_2 \mathbf u_2\mathbf v_2^* + \dots + \sigma_r \mathbf u_r\mathbf v_r^*. \tag{12.5}$$ Den sidste lighed for den kompakte SVD i (12.5) kommer af Proposition 4.7, da $\Sigma_r$ er en diagonalmatrix. Det viser hvordan en rang-$r$ matrix altid kan skrives som en sum af $r$ rang-$1$ matricer.En måde at anvende (12.5), er til såkaldt lav-rang approksimation af en matrix, hvilket vil sige at man eksempelvis vil finde en matrix $A_{100},$ som kun har en rang på $100,$ men som er så tæt som muligt på den oprindelige matrix $A,$ der eksempelvis kan have en rang på $10^6.$ Ideen ved en rang-$k$ approksimation, hvor $k \leq r,$ er kun at medtage de led der svarer til de største $k$ singulære værdier: Dette princip bliver blandt andet brugt til at udvælge det mest relevante data inden for statistik, og går også under navnet principal component analysis (PCA). Dog har man ofte at gøre med symmetriske matricer i PCA, så her kan man også bruge en diagonalisering.Der er også et min-max princip for singulære værdier (svarende til Sætning 11.11). Dette er meget brugbart i lav-rang approksimationer, til numerisk at udregne de største singulære værdier for store matricer. BevisGanske kort kan man fra Sætning 12.4 skrive $$\sigma_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\lvert A\mathbf x \rvert = \max_{\substack{W\subseteq \mathbb{C}^n \\ \dim(W)=j}}\min_{\substack{\mathbf x\in W \\ \lvert \mathbf x \rvert = 1}} \enskip\lvert A\mathbf x \rvert.$$ For at forstå hvorfor dette er en fornuftig måde at approksimere $A$ på med matricer af lav rang, skal vi kigge på hvilken fejl der bliver begået i approksimationen, altså hvad er forskellen $A - A_k.$ Ved at se på (12.5) og (12.7) har vi: $$A-A_k = \sigma_{k+1} \mathbf u_{k+1}\mathbf v_{k+1}^* + \dots + \sigma_r \mathbf u_r\mathbf v_r^*. \tag{12.8}$$ Fejlen kommer altså fra leddene med de mindste singulære værdier. Men for at kunne give et konkret tal, der beskriver den procentvise fejl, skal vi først introducere en måde at beskrive størrelsen af en matrix; en matrixnorm.

12.2.1 Matrixnormer og bedste lav-rang approksimation

En matrixnorm skal opfylde tilsvarende krav som andre vektornormer; forklaringen for dette er, at man udstyrer et vektorrum $\mathbb{C}^{m\times n}$ bestående af de komplekse $m\times n$ matricer med en norm, altså er vektorerne i disse vektorrum matricer.Nogle af de mest almindelige matrixnormer kan opskrives ved brug af matricens singulære værdier: Disse normer har mange forskellige navne: $\lVert A \rVert_2$ kaldes den spektrale norm, operatornormen, matrix $2$-normen eller Schatten $\infty$-normen. $\lVert A \rVert_*$ kaldes enten spornormen, nuklearnormen eller Schatten $1$-normen. Til sidst har vi $\lVert A \rVert_\textup{F}$ som kaldes enten Frobenius normen, Hilbert-Schmidt normen eller Schatten $2$-normen. Der er også andre formler for matrixnormerne i (12.9), som også er lettere at vise norm-egenskaberne ud fra (se Opgave 12.1). Formlen for Frobenius normen nedenfor, svarer til at stable søjlerne i matricen til en meget lang vektor, for derefter at finde dens Euklidiske norm. Genopfrisk gerne Definition 11.5 og Definition 11.17 for definitionerne på spor og på absolut værdi af en matrix. BevisI relation til den nævnte ækvivalens af normer i Bemærkning 12.6, kan vi udlede ækvivalenskonstanterne der hører til normerne i (12.9), da $\mathrm{rang}(A)\leq \min\{m,n\}$ for en $m\times n$ matrix $A.$ Samtidig vises en vigtig ulighed, som senere bruges til at vise stabilitet for numeriske beregninger med lineære ligningssystemer. BevisNu kan vi beskrive den relative fejl for en lav-rang approksimation. Hvis $\lVert \cdot \rVert$ er en matrixnorm (f.eks. en af dem fra (12.9)), så er den relative fejl på approksimationen $A_k$ fra (12.7) givet ved $$\frac{\lVert A-A_k \rVert}{\lVert A \rVert}. \tag{12.11}$$ Ved at bruge SVD for $A$ får vi følgende formler, som kun afhænger af de singulære værdier: Næste resultat fortæller, at $A_k$ faktisk er den bedst mulige lav-rang approximation. Bevis $*$ For produkter af matricer $AB$ og summer $A+B$ holder nogle interessante uligheder for de singulære værdier, som kan relateres til singulære værdier af $A$ og $B.$ Dette medfører blandt andet at matrixnormerne defineret ved singulære værdier er såkaldt submultiplikative (Opgave 12.5), og at de singulære værdier er stabile overfor støj (Opgave 12.6). Bevis

12.3 Numerisk teori og anvendelser

12.3.1 Pseudoinvers og mindste kvadraters løsning

I løbet af kurset har vi gang på gang stødt på singulære matricer, om det så er kvadratiske matricer der ikke er invertible, eller om det er rektangulære matricer. På den anden side ved vi, at det altid er muligt at finde (mindst én) mindste kvadraters løsning til et lineært ligningssystem.Nu skal vi se, hvordan vi ud fra en $m\times n$ matrix $A$ kan bruge dens SVD, til at opskrive en såkaldt Moore-Penrose pseudoinvers $A^{+}.$ Det viser sig, at $A^{+} \mathbf b$ giver en mindste kvadraters løsning til ligningssystemet $A\mathbf x = \mathbf b.$ Matricen $A^+$ opfører sig altså som en "næsten-invers" til $A$ (deraf navnet pseudoinvers). BevisSætning 12.13 viser også, at $A^{-1} = A^{+}$ hvis $A$ rent faktisk er invertibel. Udover at det er en praktisk formel, så kan man også tænke på Sætning 12.13 som et alternativt bevis på, at der altid findes mindst én mindste kvadraters løsning.Men der kan jo sagtens være flere mindste kvadraters løsninger, helt præcist ved vi fra Kapitel 10, at $$\mathbf x_0 + \mathbf y$$ er en mindste kvadraters løsning for ethvert $\mathbf y\in \mathcal{N}(A).$ Hvad er så specielt ved formlen i Sætning 12.13? Svaret på dette bliver lidt mere tydeligt, når vi omskriver formlen: Her indser vi, at $\mathbf x_0$ er en linearkombination af de første $r$ af $\mathbf v$-vektorerne, som vi fra Sætning 12.1 ved er en ONB til $\mathcal{C}(A^*) = \mathcal{N}(A)^\perp.$ Det vil altså sige, at $\mathbf x_0$ er ortogonal på enhver vektor $\mathbf y\in \mathcal{N}(A),$ og derfor giver Pythagoras sætning at $$\lvert \mathbf x_0 + \mathbf y \rvert^2 = \lvert \mathbf x_0 \rvert^2 + \lvert \mathbf y \rvert^2 \geq \lvert \mathbf x_0 \rvert^2$$ for alle $\mathbf y\in \mathcal{N}(A),$ og der er kun lighed til sidst hvis $\mathbf y = \mathbf 0.$ Vi har vist følgende resultat.Selvom man har en vis frihedsgrad til valgene af $U$ og $V$ i SVD'en, viser det sig, at den pseudoinverse $A^{+}$ er entydigt bestemt fra $A.$ Forklaringen kommer fra den forrige proposition

12.3.2 Konditionstal og numerisk stabilitet

Vi fokuserer nu på et ligningssystem $$A\mathbf x = \mathbf b,$$ hvor $A$ er en generel $m\times n$ matrix. Her kan man tænke på $A$ som en matematisk model for et system i f.eks. fysik, biologi eller kemi, og $\mathbf b$ betegner måledata. I en praktisk situation vil der typisk være små målefejl, og tilsvarende vil en computerudregning have afrundingsfejl, så i virkeligheden løser man måske et andet problem $$A\mathbf x_\epsilon = \mathbf b + \boldsymbol{\epsilon},$$ hvor vektoren $\boldsymbol{\epsilon}$ betegner en ukendt målefejl.Spørgsmålet er nu: Hvor stor påvirkning kan en sådan målefejl have på vores slutresultat $\mathbf x_\epsilon,$ i forhold til resultatet $\mathbf x$ uden målefejl? Altså hvor stor er den relative fejl $$\frac{\lvert \mathbf x_\epsilon-\mathbf x \rvert}{\lvert \mathbf x \rvert},$$ i forhold til den relative målefejl $$\frac{\lvert \boldsymbol{\epsilon} \rvert}{\lvert \mathbf b \rvert}?$$ BevisForholdet mellem største og mindste singulære værdi beskriver (i værste tilfælde), hvor meget målestøj påvirker en løsning til et løsbart lineært ligningssystem. Dette forhold kaldes konditionstallet for matricen $A$: Eksempelvis vil en matrix med konditionstal på $10^6,$ kunne forøge en lille relativ målefejl på $10^{-3},$ til en ganske stor relativ fejl på løsningen, svarende til $10^3.$ I mange praktiske sammenhænge, og især med meget store matricer, er det ikke ualmindeligt at man ser så store konditionstal, og i særligt ustabile problemer vil det være meget større. Men som man kan se nedenfor, forekommer det også for helt små matricer.

12.3.3 Trunkeret SVD og Tikhonov regularisering

Ud fra konditionstallet $\operatorname{\kappa}(A) = \frac{\sigma_1}{\sigma_r},$ er det i anvendelser typisk ikke størrelsen af $\sigma_1$ der bliver problematisk. Derimod er det ofte, at nogle af de singulære værdier, og derfor blandt andet $\sigma_r,$ kommer meget tæt på nul. Et stort konditionstal er konsekvensen, hvilket gør løsning af $A\mathbf x=\mathbf b$ numerisk ustabilt (se Sætning 12.16), i forhold til små "tilfældige" fejl eksempelvis fra målinger i anvendelser, numeriske approksimationer eller afrundingsfejl i computerberegninger.I dette afsnit skal vi undersøge, hvordan man ofte i praksis tilnærmelsesvist løser numerisk ustabile lineære ligningssystemer. Den første tilgang er den simpleste: Vi erstatter $A$ med en lav-rang approksimation $A_k,$ hvor $k$ typisk er meget mindre end rangen af $A.$ Vi har netop at $$\operatorname{\kappa}(A_k) = \frac{\sigma_1}{\sigma_k},$$ svarende til at fjerne bidrag fra de mindste singulære værdier af $A.$ Vi kalder nu for en trunkeret SVD (TSVD) regularisering af $A\mathbf x=\mathbf b.$ Hvis vi kigger nærmere på (12.18), svarer TSVD til at fjerne bidrag med store værdier af $1/\sigma_j,$ som ganges på $\mathbf b,$ der kan være "forstyrret" af tilfældig støj: $$\mathbf x_{\textup{TSVD}} = \Bigl(\frac{\mathbf b\cdot \mathbf u_1}{\sigma_1}\Bigr)\mathbf v_1 + \dots + \Bigl(\frac{\mathbf b\cdot \mathbf u_k}{\sigma_k}\Bigr)\mathbf v_k + \xcancel{\color{red}{\Bigl(\frac{\mathbf b\cdot \mathbf u_{k+1}}{\sigma_{k+1}}\Bigr)\mathbf v_{k+1} + \dots + \Bigl(\frac{\mathbf b\cdot \mathbf u_r}{\sigma_r}\Bigr)\mathbf v_r}}.$$ Antal led $k$ i beregningen af TSVD kaldes en regulariseringsparameter, og valget af $k$ er en afvejning af to faktorer:

1. Desto mindre $k$ er, desto dårligere approksimation er $A_k$ til $A,$ hvilket afspejler sig i $\mathbf x_{\textup{TSVD}}$ som approksimativ løsning til $A\mathbf x=\mathbf b.$
2. Tilgengæld er stabiliteten for beregningen af $\mathbf x_{\textup{TSVD}}$ bedre, desto mindre $k$ er.

I en praktisk sammenhæng er det nødvendigt at lave et kompromis, og vælge $k$ således at både approksimationsfejlen og beregningsfejlen er lav. Dette er ikke let at gøre generelt, og det afhænger blandt andet af statistiske "støjmodeller", for hvilke fejl der kan indgå i $\mathbf b.$ En metode til dette kaldes Discrepancy Principle. En anden metode, som dog er heuristisk, men stadig meget populær, er L-kurve metoden, som endda er opfundet af danske Per Christian Hansen.I stedet for i TSVD at smide al informationen væk, der kommer fra bidragene af de mindste singulære værdier, kan man i stedet lave en vægtning. Denne vægtning skal forsøge at bibeholde bidraget fra de største singulære værdier, men dæmpe bidraget fra de mindste singulære værdier.For et $\alpha > 0$ definerer vi $$\sigma_{\alpha,j} = \frac{\sigma_j^2 + \alpha}{\sigma_j}. \tag{12.23}$$ Kigger vi på $1/\sigma_{\alpha,j}$ ser vi nu $$\frac{1}{\sigma_{\alpha,j}} \simeq \begin{cases} 0 & \text{for lille } \sigma_j, \\ \frac{1}{\sigma_j} & \text{for stort } \sigma_j. \end{cases}$$ Her er betydningen af "lille" og "stort" ret vag, men skal ses i forholdet mellem $\alpha$ og $\sigma_j.$ Figur 12.1 giver et bedre indtryk, hvor denne dæmpning kan ses sammenlignet med trunkeringen i TSVD.Hvis vi kalder $A_\alpha$ for matricen svarende til $A,$ men hvor $\sigma_j$ er erstattet af $\sigma_{\alpha,j}$ i dens SVD, kan vi nu løse et nyt system: Dette kaldes en Tikhonov regularisering af $A\mathbf x = \mathbf b$ med regulariseringsparameter $\alpha>0.$ Metoden er navngivet efter Andrey Nikolayevich Tikhonov, som har været en meget markant indflydelse på moderne metoder i numerisk analyse.Rollen af $\alpha$ i Tikhonov regularisering svarer til den reciprokke rolle af $k$ i TSVD. For lille $\alpha$ fås lille approksimationsfejl, men stor beregningsfejl, og omvendt for stort $\alpha.$En traditionel måde at karakterisere Tikhonov regularisering på, er som et minimeringsproblem der generaliserer mindste kvadraters metode (som svarer til $\alpha = 0$ nedenfor). Bevis $*$ Disse metoder anvendes meget ofte på problemer i praksis. Et oplagt visuelt eksempel til at illustrere dem, er at fjerne sløring (deblurring) fra et billede, taget med et kamera ude af fokus. I sådanne billeder vil der også være støj i det slørede billede, svarende til en tilfældighed omkring antallet af fotoner der rammer de forskellige pixels, samt elektronisk støj når billedet lagres. Dette er nok til at det inverse problem med at fjerne sløringen bliver numerisk ustabilt. Med Tikhonov regularisering kræver det "optimale" billede, at $\alpha$ er hverken for stor eller lille (se Figur 12.2). En tilsvarende situation gør sig gældende med TSVD.

12.4 Opgaver