12Singulær værdi dekomposition

Vi så i forrige kapitel hvordan spektralsætningen viser, at enhver hermitesk matrix kan diagonaliseres, ved at lave basisskifte med en ONB bestående af egenvektorer. Nu skal vi se at et næsten tilsvarende resultat holder for alle matricer, også rektangulære matricer. Vi skal nemlig se på 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. Mere specifikt kommer baserne til at være valgt ud fra de fire fundamentale underrum $C(A)$, $N(A)$, $C(A^*)$ og $N(A^*)$ som vi studerede i slutningen af Kapitel 9.SVD er et af de vigtigste resultater der bruges i både anvendelser (til effektive beregninger og lavdimensionel approksimation) og i teori for f.eks. numeriske metoder. Vi skal se lidt mere til dette i de sidste afsnit af kapitlet.Beviset af Sætning 12.2 gennemgåes i de følgende afsnit, både da det på fin vis gør brug af meget af teorien som er gennemgået i kurset, men også fordi det præcis viser hvordan de forskellige matricer bestemmes i praksis.

12.1 De singulære værdier

Vi tager udgangspunkt i en $m\times n$ matrix $A$, og bemærker at hvis vi ganger $A^*$ 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 hermitesk 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 at $\lambda$ er reel samt Sætning 9.21: $$\lambda|\mathbf v|^2 = \lambda(\mathbf v\cdot \mathbf v) = \mathbf v\cdot(A^*A\mathbf v) = (A\mathbf v)\cdot(A\mathbf v) = |A\mathbf v|^2.$$ Vi ser altså at enhver egenværdi for $A^* A$ opfylder: $$\lambda = \frac{|A\mathbf v|^2}{|\mathbf v|^2} \geq 0. \tag{12.2}$$ 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 multiplicitet.De singulære værdier er kvadratroden af de positive egenværdier for $A^*A$:

12.2 De højre singulære vektorer

Da $A^* A$ er en hermitesk 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^*.$$ Fra (12.2) ved vi at $A\mathbf v_i \neq \mathbf 0$ for $i = 1,\dots,r$ og $A\mathbf v_i = \mathbf 0$ for $i>r$. Samtidig ved vi også at $\{\mathbf v_1,\dots,\mathbf v_n\}$ udgør en ONB for hele $\mathbb{C}^n$, hvori $C(A^*)$ og $N(A)$ udgør ortogonale komplementer (Sætning 9.34). Samlet set har vi at $\{\mathbf v_1,\dots,\mathbf v_r\}$ er en ONB for $C(A^*)$ og $\{\mathbf v_{r+1},\dots,\mathbf v_n\}$ er en ONB for $N(A)$.

12.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}\mathbf v_i\cdot(A^*A\mathbf v_j),$$ og vi husker at $\mathbf v_j$ er egenvektor for $A^* A$ med egenværdi $\sigma_j^2$, samt $\mathbf v$-vektorerne er ortonormale. Vi har derfor $$\mathbf u_i\cdot \mathbf u_j = \frac{\sigma_j^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 ONB for $C(A^*) = N(A)^\perp$, så en afbildning af $A$ på denne basis (se f.eks. Figur 12.1) må altså udspænde hele søjlerummet for $A$. Det vil sige, fra (12.4) ved vi nu at $\{\mathbf u_1,\dots,\mathbf u_r\}$ er en ONB for $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 $N(A^*)$ ved brug af f.eks. Gram-Schmidt algoritmen. Bemærk at der er mange forskellige ONB 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 $N(A)$.

12.4 Sammensætning af delresultaterne til SVD

Vi kan nu sætte alle delresultaterne sammen, for at få SVD'en i Sætning 12.2. Da $\{\mathbf v_1,\dots,\mathbf v_n\}$ er en ONB for $\mathbb{C}^n$, så er ligheden $A = U\Sigma V^*$ det samme som $$A\mathbf v_i = (U\Sigma V^*)\mathbf v_i \tag{12.5}$$ for alle $i=1,\dots,n$. Vi vil altså vise ligheden (12.5).Det første vi bemærker er, at 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 standard basis vektor 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 } j=r+1,\dots,n. \end{cases}$$ Her er $\widetilde{\mathbf e}_i$ også den $i$'te standard basis vektor, men denne gang for $\mathbb{C}^m$ (da $\Sigma$ er en $m\times n$ matrix).For $i>r$ har vi derfor at $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 $N(A)$. Nu mangler vi kun at vise (12.5) for $i = 1,\dots,r$, og her skal vi bruge sammenhængen mellem de venstre og højre singulære vektorer i (12.4): $$U\Sigma V^*\mathbf v_i = \sigma_i U\widetilde{\mathbf e}_i = \sigma_i\mathbf u_i = A\mathbf v_i.$$

12.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 hermiteske 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ærdier for $A^* A$ begge har algebraisk multiplicitet $1$, så vil deres geometriske multipliciteter tilsvarende være $1$ af Proposition 8.13. Ved at se på matricerne $$A^*A-4I = \begin{pmatrix} -1 & i \\ -i & -1 \end{pmatrix}, \qquad 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}, \qquad \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.4) 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 $N(A^*)$, hvilket også svarer til nulrummet for matricen $(\mathbf u_1,\mathbf u_2)^*$ da $N(A^*) = 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.6 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$ 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. Vi har nu helt tilsvarende at $$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.6}$$ Den sidste lighed i (12.6) kommer af at $\Sigma_r$ er en diagonalmatrix, og det viser hvordan en rang-$r$ matrix altid kan skrives som en sum af $r$ rang-$1$ matricer.En måde at anvende (12.6), er til lave såkaldt lav-rang approksimation til 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$ som eksempelvis kan have en rang på $10^6$. Ideen ved en rang-$k$ approksimation, hvor $k < 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 spektralsætningen til at lave en egenværdidekomposition.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.6) og (12.8) 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.9}$$ 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, så skal vi først introducere en måde at beskrive størrelsen af en matrix; en matrixnorm.

12.6.1 Matrixnormer

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 nogle særlige navne. $||A||_2$ kaldes den spektrale norm, matrix $2$-normen eller Schatten $\infty$-normen, $||A||_*$ kaldes enten spornormen, nuklearnormen eller Schatten $1$-normen, og til sidst har vi $||A||_\textup{F}$ som kaldes enten Frobeniusnormen, Hilbert-Schmidt normen eller Schatten $2$-normen. Der er også nogle andre formler for den spektrale norm og Frobeniusnormen (nogle gange bruges disse som definitioner), som i nogle sammenhænge er lettere at bruge til udregninger, og som er lettere at vise norm-egenskaberne ud fra. I formlen for Frobeniusnormen kan man tænke på det som at stable søjlerne i matricen til en meget lang vektor, for derefter at finde dens Euklidiske norm. Bevis*I relation til den nævnte ækvivalens af normer, så kan vi udlede ækvivalenskonstanterne der hører til normerne i (12.10), og samtidig også vise 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 $||\cdot||$ er en matrixnorm (f.eks. en af dem fra (12.10)), så er den relative fejl på approksimationen $A_k$ fra (12.8) givet ved $$\frac{||A-A_k||}{||A||}. \tag{12.17}$$ Ved at bruge SVD for $A$, så får vi følgende formler som kun afhænger af de singulære værdier:

12.7 Numerisk teori og anvendelser

12.7.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 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^{+}$. Selv om man har en vis frihedsgrad til valgene af $U$ og $V$ i SVD'en, så viser det sig at den pseudoinverse $A^{+}$ er entydigt bestemt ud fra $A$ (ligesom at $A = U\Sigma V^*$ uanset hvilken SVD man har af $A$). Dette er dog ikke noget vi beviser i dette kursus.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).BevisResultatet i Sætning 12.11 viser også, at hvis $A$ rent faktisk er invertibel så gælder det at $A^{-1} = A^{+}$. Udover at det er en praktisk formel, så kan man også tænke på Sætning 12.11 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 N(A)$. Så hvad er så specielt ved formlen i Sætning 12.11? 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.2 ved er en ONB til $C(A^*) = N(A)^\perp$. Det vil altså sige, at $\mathbf x_0$ er ortogonal på enhver vektor $\mathbf y\in N(A)$, og derfor giver Pythagoras sætning at $$|\mathbf x_0 + \mathbf y|^2 = |\mathbf x_0|^2 + |\mathbf y|^2 \geq |\mathbf x_0|^2$$ for alle $\mathbf y\in N(A)$, og der er kun lighed til sidst hvis $\mathbf y = \mathbf 0$. Vi har vist følgende resultat.

12.7.2 Konditionstal og numerisk stabilitet

Vi starter nu med at fokusere 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 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{|\mathbf x_\epsilon-\mathbf x|}{|\mathbf x|}$$ i forhold til den relative målefejl: $$\frac{|\boldsymbol{\epsilon}|}{|\mathbf b|}.$$ BevisForholdet mellem den 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 lineært ligningssystem. Dette forhold kaldes også 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å (mindste kvadraters) 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, kan dette også forekomme for helt små matricer.

12.7.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.14) 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 vi har fjernet 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.21) 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 u_1^*\mathbf b}{\sigma_1}\Bigr)\mathbf v_1 + \dots + \Bigl(\frac{\mathbf u_k^*\mathbf b}{\sigma_k}\Bigr)\mathbf v_k + \sout{\Bigl(\frac{\mathbf u_{k+1}^*\mathbf b}{\sigma_{k+1}}\Bigr)\mathbf v_{k+1} + \dots + \Bigl(\frac{\mathbf u_r^*\mathbf b}{\sigma_r}\Bigr)\mathbf v_r}.$$ Antal led $k$ i beregningen af TSVD kaldes også en regulariseringsparameter, og valget af $k$ er en afvægtning 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 heurestisk 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 bidragene 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.26}$$ 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$. Figuren nedenfor 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, så kan vi nu løse et nyt system: Dette kaldes en Tikhonov regularisering af $A\mathbf x = \mathbf b$. Metoden er navngivet efter russisk matematiker 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 metoden ($\alpha = 0$ er mindste kvadraters metode):Bevis *Det kan være kompliceret at illustrere disse metoder generelt med et simpelt visuelt eksempel. Et oplagt problem til dette kan være 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 at der er en tilfældighed omkring antallet af fotoner der rammer de forskellige pixels i et billede, samt elektronisk støj når billede lagres. Dette er nok til at det inverse problem med at fjerne sløringen bliver numerisk ustabil.Et eksempel på dette kan ses i Figur 12.19 med Tikhonov regularisering, hvor det ses at det ''optimale'' billede kræver at $\alpha$ er hverken for stor eller lille. En tilsvarende situation gør sig gældende med TSVD.

12.8 Opgaver