75032 Matrisemetoder 26. mai 1995: Løsningsforslag

Oppgave 1

a Standard Gausseliminasjon gir U:

A = [\begin{matrix}1 & 1 & 1 & 1 \\ 1 & 2 & 3 & 4 \\ 1 & 3 & 6 & 10 \\ 1 & 4 & 10 & 20 \end{matrix}] → [\begin{matrix}1 & 1 & 1 & 1 \\ & 1 & 2 & 3 \\ & 2 & 5 & 9 \\ & 3 & 9 & 19 \end{matrix}] → [\begin{matrix}1 & 1 & 1 & 1 \\ & 1 & 2 & 3 \\ & & 1 & 3 \\ & & 3 & 10 \end{matrix}] → [\begin{matrix}1 & 1 & 1 & 1 \\ & 1 & 2 & 3 \\ & & 1 & 3 \\ & & & 1 \end{matrix}] = U

der man som vanlig noterer koeffisientene som ble brukt i Gausseliminasjonen i matrisen

L = [\begin{matrix}1 \\ 1 & 1 \\ 1 & 2 & 1 \\ 1 & 3 & 3 & 1 \end{matrix}]

Vi legger for øvrig merke til at U = L^{T}, så A = LU = LL^{T}.

Ligningen Ax = b løses i to trinn; først Ly = b ved fremoversubstitusjon, og så Ux = y ved tilbakesubstitusjon:

y_{1} = 1
y_{2} = 3 − y_{1} = 2
y_{3} = 9 − y_{1} − 2y_{2} = 4
y_{4} = 27 − y_{1} − 3y_{2} − 3y_{3} = 8
x_{4} = y_{4} = 8
x_{3} = y_{3} − 3x_{4} = −20
x_{2} = y_{2} − 2x_{3} − 3x_{4} = 18
x_{1} = y_{1} − x_{2} − x_{3} − x_{4} = −5

altså x = [−5 18 −20 8]^{T}.

b Determinanten er 1 (produktet av diagonalelementene i U). Den er positivt definit fordi Gausseliminasjonen gikk an uten pivotering og U har bare positive elementer på diagonalen. Mer direkte kan vi se dette ut fra A = LL^{T} siden L er invertibel.

75032 Matrisemetoder 26. mai 1995 Løsningsforslag

Oppgave 2

a Nullrommet til A er gitt ved Ax = 0, ekvivalent Ux = 0 siden L alltid er invertibel. Ligningssystemet Ux = 0 har to frie variable, x_{2} og x_{4} (fra søylene uten pivoter). Vi setter i tur og orden (x_{2}, x_{4}) = (1, 0) og (x_{2}, x_{4}) = (0, 1) og løser med med hensyn på basisvariablene x_{1} og x_{3}, så ender vi med basisen

[\begin{matrix}−2 \\ 1 \\ 0 \\ 0 \end{matrix}] , [\begin{matrix}−7 \\ 0 \\ 1 \\ 1 \end{matrix}]

for N (A) = N (U).

Av A^{T} = U^{T}L^{T} ser vi at R(A^{T}) = R(U^{T}) som har som basis de to første søylene i U^{T}, altså

[\begin{matrix}1 \\ 2 \\ 3 \\ 4 \end{matrix}] , [\begin{matrix}0 \\ 0 \\ 1 \\ −1 \end{matrix}]

Det går også an å regne ut dette fra R(A^{T}) = N (A)^{⊥}, og en tidligere utgave av dette løsningsforslaget gjorde det slik — men det er altså unødig tungvint.

b Når A^{2} = 0 er R(A) ⊆ N (A). A har jo rang 2, som vi ser av formen på U. Med andre ord er dim R(A) = 2 og dim N (A) = 4 − 2 = 2. Dermed er R(A) = N (A), og kan åpenbart gis samme basis som N (A). Vi finner også N (A^{T}) = R(A)^{⊥} = N (A)^{⊥} = R(A^{T}), og det har vi også funnet en basis for ovenfor.

c Alle egenverdiene er 0 fordi A^{2} = 0 (bevis: om Ax = λx med x ≠ 0 finner vi 0 = A^{2}x = A(Ax) = A(λx) = λAx = λ^{2}x hvorav λ = 0). Jordan-formen inneholder altså bare Jordanblokker med 0 på diagonalen, og hver av dem bidrar med 1 til dimensjonen av N (A). Dermed er det to Jordanblokker, og de kan bare være enten henholdsvis 3 × 3 og 1 × 1 eller begge 2 × 2. Altså er Jordanformen en av disse to:

[\begin{matrix}0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{matrix}] eller [\begin{matrix}0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \end{matrix}]

Men den første av disse har ikke kvadrat lik null, så vi står igjen med den andre.

75032 Matrisemetoder 26. mai 1995 Løsningsforslag Oppgave 3

a Vi finner

A^{T}A = [\begin{matrix}113 & 84 \\ 84 & 162 \end{matrix}]
A^{T}A − 225I = [\begin{matrix}−112 & 84 \\ 84 & −63 \end{matrix}] = 7 [\begin{matrix}−16 & 12 \\ 12 & −9 \end{matrix}]
A^{T}A − 50I = [\begin{matrix}63 & 84 \\ 84 & 112 \end{matrix}] = 7 [\begin{matrix}9 & 12 \\ 12 & 63 \end{matrix}]

Og da finner vi raskt egenvektorene

[\begin{matrix}3 \\ 4 \end{matrix}] for λ = 225, [\begin{matrix}4 \\ −3 \end{matrix}] for λ = 50.

Dette gir oss to av matrisene

Σ = [\begin{matrix}15 & 0 \\ 0 & 5\sqrt{2} \\ 0 & 0 \end{matrix}] , Q_{2} = \frac{1}{5} [\begin{matrix}3 & 4 \\ 4 & −3 \end{matrix}]

i singulærverdidekomposisjonen A = Q_{1}ΣQ_{2}^{T}. Fra ligningen AQ_{2} = Q_{1}Σ finner vi raskt søylene i Q_{1}:

\frac{1}{15}A · \frac{1}{5} [\begin{matrix}3 \\ 4 \end{matrix}] = \frac{1}{3}221 og \frac{1}{5\sqrt{2}}A · \frac{1}{5} [\begin{matrix}4 \\ −3 \end{matrix}] = \frac{1}{\sqrt{2}} [\begin{matrix}−1 \\ 1 \\ 0 \end{matrix}]

blir de to første søylene, mens den siste må være ortogonal på de første to. Vi ledes altså til

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

b Kaller vi høyresiden b, og minste kvadraters løsning x, blir

Σ^{+} = [\begin{matrix}1/15 & 0 & 0 \\ 0 & 1/(5\sqrt{2}) & 0 \end{matrix}] , x = Q_{2}Σ^{+}Q_{1}^{T}b = [\begin{matrix}−1 \\ 1 \end{matrix}] .

Oppgave 4

a La oss kalle den gitte matrisen A_{n}. Gausseliminasjon på første søyle leder fra den opprinnelige matrisen til

[ \begin{matrix}& 1 & −1 & 1 & −1 & … \\ & 0 & 1 & −1 & 1 & … \\ & 0 & −1 & 2 & −2 & … \\ & 0 & 1 & −2 & 3 & … \\ ⋮ & & ⋮ & ⋮ & ⋮ & ... \end{matrix}]

der nederste høyre (n − 1) × (n − 1)-hjørne er A_{n−1}. Videre Gausseliminasjon leder til

A_{n} = LU = LL^{T} = [\begin{matrix}1 & 0 & 0 & & 0 & … \\ −1 & 1 & 0 & & 0 & … \\ 1 & −1 & 1 & & 0 & … \\ −1 & 1 & −1 & & 1 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & & ... \end{matrix}] [ \begin{matrix}& 1 & −1 & 1 & −1 & … \\ & 0 & 1 & −1 & 1 & … \\ & 0 & 0 & 1 & −1 & … \\ & 0 & 0 & 0 & 1 & … \\ ⋮ & & ⋮ & ⋮ & ⋮ & ... \end{matrix}]

b For å invertere A_{n} inverterer vi først L_{n} ved å stille opp den utvidede n × (2n)-matrisen [A_{n} I]. En gangs Gausseliminasjon i første rekke leder til

[ \begin{matrix}& 1 & 0 & 0 & & 0 & … & 1 & & & & & & & … \\ & 0 & 1 & 0 & & 0 & … & 1 & & 1 & & & & & … \\ & 0 & −1 & 1 & & 0 & … & −1 & & 0 & & 1 & & & … \\ & 0 & 1 & −1 & & 1 & … & 1 & & 0 & & 0 & & 1 & … \\ ⋮ & & ⋮ & ⋮ & ⋮ & & … & ⋮ & ⋮ & & ⋮ & & ⋮ & & ... \end{matrix}]

Når vi så bruker annen rekke for å eliminere alt under diagonalen i annen søyle, ser vi at første søyle i matrisen til høyre blir fylt med nuller fra posisjon 3 og nedover. Vi ender med

L^{−1} = [\begin{matrix}1 \\ 1 & 1 \\ & 1 & 1 \\ & & ... & ... \\ & & & 1 & 1 \end{matrix} ]

og dermed

A_{n}^{−1} = (LL^{T})^{−1} = (L^{−1})^{T}L^{−1} = [\begin{matrix}2 & 1 \\ 1 & 2 & 1 \\ & ... & ... & ... \\ & & 1 & 2 & 1 \\ & & & 1 & 1 \end{matrix}] .

Oppgave 5

Kall matrisen A_{n}. Det finnes (minst) to måter å finne determinanten på.

Vi kan trekke r^{−i} ganger rekke 1 fra rekke i for i = 2, …, n, og finne

det A_{n} = |\begin{matrix}1 & r & r^{2} & & & r^{n−1} \\ r − r^{−1} & 0 & 0 & 0 & … & 0 \\ ∗ & r − r^{−1} & 0 & 0 & & 0 \\ ⋮ & ... & ... & ... & ... & ⋮ \\ ∗ & ∗ & ∗ & … & r − r^{−1} & 0 \end{matrix}|

(der ∗ betyr et tall som ikke har noen innvirkning på svaret) som vi utvikler etter siste søyle, og finner

det A_{n} = (−1)^{n−1}r^{n−1}(r − r^{−1})^{n−1} = (1 − r^{2})^{n−1}

Vi kan også utvikle den opprinnelige determinanten etter første søyle. Da ser vi at alle kofaktorene med unntak av de første to blir 0, for om vi stryker første søyle og rekke i fra A der i ≥ 3, står vi igjen med en matrise der første rekke er r ganger annen rekke, slik at determinanten av denne matrisen er 0. Når vi stryker første søyle og første rekke får vi A_{n−1}, men stryker vi annen rekke i stedet får vi en matrise som skiller seg fra A_{n−1} ved at første rekke er multiplisert med r. Vi ledes derfor til det A_{n} = (1 − r^{2}) det A_{n−1}. Løsning av denne rekursjonen leder til samme svar som ovenfor.

En rask sjekk av øverste venstre 2×2 undermatrise av A_{n} viser at matrisen er positivt definit bare dersom 1 − r^{2} > 0, med andre ord bare dersom |r| < 1. Omvendt, om |r| < 1 er A_{n} positivt definit, for i dette tilfellet har alle øvre venstre undermatriser A_{k} (der k = 1, …, n) positiv determinant (nemlig (1 − r^{2})^{k}).