75032 Matrisemetoder

Løsningsforslag til oppgaver gitt til onsdag 5/4–95

Påminnelse: En SVD A = Q_{1}ΣQ_{2}^{T} kan man finne ved å merke seg at vi skal ha A^{T}A = Q_{2}Σ^{T}ΣQ_{2}^{T}, så man finner egenverdiene (kvadratrøttene blir singulærverdiene) til A^{T}A, og lar egenvektorene bli søyelene i Q_{2}. Deretter finner man de første søylene (like mange som det er singulærverdier ≠ 0) i Q_{1} ut fra AQ_{2} = Q_{1}Σ, og resten ved å utvide til ortonormal basis.

Men man kan også skrive AA^{T} = Q_{1}ΣΣ^{T}Q_{1}^{T}, så man diagonaliserer AA^{T} og utnytter tilslutt A^{T}Q_{1} = Q_{2}Σ^{T} for å finne de første søyelene i Q_{2}.

A.2 side 451: Raskest er å skrive AA^{T} = [4] som har egenverdien 4 med normalisert egenvektor [1], slik at σ_{1} = \sqrt{4} = 2, og vi får Q_{1} = [1] og Σ = [2, 0, 0, 0]. Første søyle i Q_{2} må bli 2^{−1}A^{T}[1] = (1/2)[1, 1, 1, 1]^{T}, og resten finner man ved å utvide til en ortonormal basis. For eksempel

Q_{2} = [\begin{matrix}1/2 & 1/2 & 1/\sqrt{2} & 0 \\ 1/2 & 1/2 & −1/\sqrt{2} & 0 \\ 1/2 & −1/2 & 0 & 1/\sqrt{2} \\ 1/2 & −1/2 & 0 & −1/\sqrt{2} \end{matrix}]

som jeg fant uten noe videre regning (men generelt må man dra igang hele maskineriet med Gram-Schmidt eller lignende).

BB^{T} blir en 2 × 2 identitetsmatrise, så singulærverdiene blir σ_{1} = σ_{2} = 1. Jeg fikk

B = Q_{1}ΣQ_{2}^{T} = [\begin{matrix}0 & 1 \\ 1 & 0 \end{matrix}] [\begin{matrix}1 & 0 & 0 \\ 0 & 1 & 0 \end{matrix}] [\begin{matrix}1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix}]

Det er jo søylene i Q_{1} som velges først (egenvektorene for BB^{T}), og opprinnelig hadde jeg valgt dem i omvendt rekkefølge. Men så oppdaget jeg at om jeg gjorde som over ble Q_{1}Σ = B, og dermed var det bare å sette Q_{2} = I uten mer regning.

Jeg fikk

C^{T}C = [\begin{matrix}1 & 1 \\ 1 & 1 \end{matrix}] , σ_{1}^{2} = 2, σ_{2}^{2} = 0, Σ = [\begin{matrix}√ & \overline{2} \\ & 0 \end{matrix}] , Q_{2} = \frac{1}{\sqrt{2}} [\begin{matrix}1 & 1 \\ 1 & −1 \end{matrix}] , Q_{1} = [\begin{matrix}1 & 0 \\ 0 & 1 \end{matrix}]

A.4 side 451: Vi diagonaliserer A^{T}A:

A^{T}A = [\begin{matrix}10 & 6 \\ 6 & 10 \end{matrix}] = Q_{2}ΛQ_{2}^{T}, Λ = [\begin{matrix}16 \\ & 4 \end{matrix}] , Q_{2} = \frac{1}{\sqrt{2}} [\begin{matrix}1 & 1 \\ 1 & −1 \end{matrix}]

Den søkte kvadratroten er

S = Q_{2}ΣQ_{2}^{T} = [\begin{matrix}3 & 1 \\ 1 & 3 \end{matrix}] der Σ = Λ^{1/2} = [\begin{matrix}4 \\ & 2 \end{matrix}] .

(b) Vi kan nå finne polardekomposisjonen A = QS ut fra SVD-en A = Q_{1}ΣQ_{2}^{T} = Q_{1}Q_{2}^{T}S, men da må vi finne Q_{1}. Ikke at det er så vanskelig, men vi kan like gjerne sette

Q = AS^{−1} = \frac{1}{\sqrt{10}} [\begin{matrix}10 & 6 \\ 0 & 8 \end{matrix}] \frac{1}{8} [\begin{matrix}3 & −1 \\ −1 & 3 \end{matrix}] = \frac{1}{\sqrt{10}} [\begin{matrix}3 & 1 \\ −1 & 3 \end{matrix}] .

Til slutt finner vi den “omvendte” polardekomposisjonen: A = QS = QSQ^{T}Q = S′Q der altså

S′ = QSQ^{T} = \frac{1}{10} [\begin{matrix}36 & 8 \\ 8 & 24 \end{matrix}] .

A.6 side 452:

(a) Her har jeg ikke mindre enn tre løsninger! For det første, når A har l.u. søyler slik at A^{T}A er invertibel, har normalligningen A^{T}Ax = A^{T}b entydig løsning som jo er gitt ved x = (A^{T}A)^{−1}A^{T}b, og dermed må den pseudoinverse være matrisen (A^{T}A)^{−1}A^{T}.

Den andre løsningen er å bruke en SVD: A = Q_{1}ΣQ_{2}^{T} gir

A^{T}A = Q_{2}Σ^{T}ΣQ_{2}^{T}, Σ^{T}Σ = [\begin{matrix}σ_{1}^{2} \\ & . & . & . \\ & & & & σ_{n}^{2} \end{matrix}]

der antagelsene forteller oss at A har n singulærverdier ≠ 0, så Σ^{T}Σ er invertibel, og

(A^{T}A)^{−1}A^{T} = Q_{2}(Σ^{T}Σ)^{−1}Q_{2}^{T}Q_{2}Σ^{T}Q_{1}^{T} = Q_{2} \underbrace{(Σ^{T}Σ)^{−1}Σ^{T}}_{Σ^{+}} Q_{1}^{T} = A^{+}.

Den tredje løsningen består i å forstå hvordan A^{+} virker på R(A) og på N (A^{T}):

1. Om b ∈ N (A^{T}) er A^{+}b = 0,

2. Om b ∈ R(A) kan vi skrive b = Ax for en x ∈ N (A)^{⊥} = R(A^{T}), og da er A^{+}b = x.

og siden R(A) og N (A^{T}) tilsammen utspenner R^{m} vil enhver matrise som oppfyller de samme kravene være lik A^{+}. At (A^{T}A)^{−1}A^{T} oppfyller betingelsene er en triviell utregning.

(b) Den første løsningen fra (a) har kanskje ingen enkel versjon i dette tilfellet, men den andre løsningen kan enkelt tilpasses. Jeg viser ikke det her, men tar den tredje varianten.

Når A har l.u. rekker så er N (A^{T}) = {0}, så om b ∈ N (A^{T}) er trivielt A^{T}(AA^{T})^{−1}b = 0.

Og om b ∈ R(A) er skrevet som b = Ax for en x ∈ R(A^{T}) kan vi videre skrive x = A^{T}c, så A^{T}(AA^{T})^{−1}b = A^{T}(AA^{T})^{−1}AA^{T}c = A^{T}c = x.

A.10 side 452: En geometrisk måte å tolke det på er slik: For en m × n-matrise A splitter vi R^{n} opp i ortogonale komponenter R(A^{T}) og N (A), og likedan R^{m} i ortogonale komponenter R(A) og N (A^{T}). A avbilder R(A^{T}) en-til-en på R(A) med invers A^{+}, mens A og A^{+} er null på henhodsvis N (A) og N (A^{T}).

Dermed er AA^{+}x = 0 når x ∈ N (A^{T}) og AA^{+}x = x når x ∈ R(A), så AA^{+} er ortogonalprojeksjonen på R(A).

Likedan er A^{+}Ax = 0 når x ∈ N (A) og A^{+}Ax = x når x ∈ R(A^{T}), så A^{+}A er ortogonalprojeksjonen på R(A^{T}).

Alternativt kan man bruke SVD:

AA^{+} = Q_{1}ΣQ_{2}Q_{2}^{T}Σ^{+}Q_{1}^{T} = Q_{1}ΣΣ^{+}Q_{1}^{T} = Q_{1} [\begin{matrix}1 \\ & . & . & . \\ & & & & 1 \\ & & & & & 0 \\ & & & & & & . & . & . \end{matrix}] Q_{1}^{T}

og matrisen i midten (med r enere på diagonalen) er en prosjeksjon, dermed blir AA^{+} det. Vi ser også at R(AA^{+}) blir utspent av de første r søylene i Q_{1}, som vi allerede vet utspenner R(A). A^{+}A kan behandles på samme måten.

Eksamen mai 1989: 1: Denne oppgaven skulle ikke vært gitt. Jeg skrev oppgave 4 på tavla, men 1 i WWW-siden. I tilfelle noen regnet oppgave 1 så gir jeg en løsning her.

(a) Besvarelsen i oppgavesamlingen pivoterer litt, men det har vel ikke så mye hensikt her. Uten pivotering får jeg

A = LU = [\begin{matrix}1 \\ 3 & 1 \\ −5/2 & −1/2 & 1 \end{matrix}] [\begin{matrix}2 & 1 & 2 \\ & 1 & 2 \\ & & 0 \end{matrix}]

(b) N (A) = N (U) er utspent av [0, −2, 1]^{T}. Basis for R(A) er første og annen søyle i A eller i L (siden pivotene i U finnes i de to søylene). Men vi ser at nullvektoren jeg fant ovenfor er −2 ganger annen søyle i L, så tar vi den vektoren og første søyle i L har vi en basis for R(A).

(c) N (B) ⊆ R(B) gir oss 3 − r ≤ for rangen r til B. Dermed må r ≥ 2. Enhver 3 × 3-matrise B med rang 3 er jo invertibel, så dim N (B) = 0. Og vi har nettopp sett et eksempel på at rangen kan være 2.

Eksamen mai 1989: 4:

(a) Singulærverdidekomposisjonen for A_{k} er jo A_{k} = Q_{1}Σ_{k}Q_{2}^{T}, så rangen er k fordi vi har k singulærverdier på diagonalen i Σ_{k}. Mer detaljert: Σ_{k} har rang k fordi den er på trappeform med k pivoter. Multiplikasjon med invertible matriser på den ene eller andre siden endrer ikke rangen.

Vi følger hintet, og merker oss at (Σ − Σ_{k})x = [0, …, 0, σ_{k+1}x_{k+1}, …, σ_{r}x_{r}, 0, …, 0]^{T} slik at

∥(Σ − Σ_{k})x∥^{2} = ∑_{j=k+1}^{r} σ_{j}^{2}x_{j}^{2} ≤ ∑_{j=k+1}^{r} σ_{k+1}^{2}x_{j}^{2} ≤ σ_{k+1}^{2} ∑_{j=1}^{n} x_{j}^{2} = σ_{k+1}^{2} ∥x∥^{2} .

Der den første ulikheten skyldes at singulærverdiene er sortert. Dette benytter vi så slik:

∥(A − A_{k})x∥ = ∥Q_{1}(Σ − Σ_{k})Q_{2}^{T}x∥ = ∥(Σ − Σ_{k})Q_{2}^{T}x∥ ≤ σ_{k+1} ∥Q_{2}^{T}x∥ = σ_{k+1} ∥x∥ .

(b) La u_{1}, …, u_{k} være en basis for U og v_{1}, …, v_{ℓ} en basis for V. Da er alle disse vektorene lineært uavhengige, for om

c_{1}u_{1} + ⋯ + c_{k}u_{k} + d_{1}v_{1} + ⋯ + d_{ℓ}v_{ℓ} = 0

er

c_{1}u_{1} + ⋯ + c_{k}u_{k} = −(d_{1}v_{1} + ⋯ + d_{ℓ}v_{ℓ}) ∈ U ∩ V = {0}

fordi venstresiden i likheten tilhører U og høyresiden tilhører V. Vi har altså c_{1}u_{1} + ⋯ + c_{k}u_{k} = 0 så c_{1} = ⋯ = c_{k} = 0 fordi uene er lineært uavhengige. På samme måte finner vi d_{1} = ⋯ = d_{ℓ} = 0.

Vi har nå k + ℓ lineært uavhengige vektorer i R^{n}, og da er k + ℓ ≤ n ved plassmangelteoremet.

(c) Vi tar hintet igjen, og betrakter x = [x_{1}, …, x_{k+1}, 0, …, 0]^{T} ≠ 0. Hintet anbefaler oss å vise at BQ_{2}x ≠ 0, så vi antar det motsatte, altså BQ_{2}x = 0, og forsøker å utlede en motsigelse. At fra antagelsen har vi ∥(A − B)Q_{2}x∥ ≤ C ∥Q_{2}x∥, som i vårt tilfelle blir

∥AQ_{2}x∥ ≤ C ∥x∥ (1)

På den annen side blir

∥AQ_{2}x∥ = ∥Q_{1}Σx∥ = ∥Σx∥ = ∥[σ_{1}x_{1}, …, σ_{k+1}x_{k+1}, 0, …, 0]^{T}∥

= \sqrt{∑_{j=1}^{k+1} σ_{j}^{2}x_{j}^{2}} ≥ \sqrt{∑_{j=1}^{k+1} σ_{k+1}^{2}x_{j}^{2}} = σ_{k+1} ∥x∥

som sammen med (1) gir C ≥ σ_{k+1} i motstrid med antagelsen. Altså er BQ_{2}x ≠ 0.

Hva skal vi så bruke dette til? Vi skal vise at rangen til B er stor, mens vi formodentlig skal bruke resultatet fra (b) som bare kan brukes til å vise at dimensjonen til et underrom er lite. Men den ønskede ulikhet er ekvivalent med n − dim N (B) > k, altså k + 1 + dim N (B) ≤ n. Men ovenfor fant vi jo nettopp et rom av dimensjon k + 1, nemlig alle vektorer på formen Q_{2}[x_{1}, …, x_{k+1}, 0, …, 0]^{T}, som har trivielt snitt med N (B). Dermed vil resultatet fra (b) gi oss svaret vi trenger.

(Dette punktet var det nesten ingen som klarte på eksamen. Jeg skal forsøke å ikke ha et like vrient punkt på årets eksamen, men en liten “nøtt” synes jeg må til.)