75032 Matrisemetoder 1996–08–13: Løsningsforslag

Oppgave 1

a Gausseliminasjon uten pivotering går greit, og som alltid samler vi opp koeffisientene som brukes underveis i L:

A = [\begin{matrix}1 & 1 & 1 & 1 \\ a & a + 1 & a + 2 & a + 3 \\ 0 & a & 2a + 1 & 4a \\ 1 & 1 & a + 1 & a^{2} + 1 \end{matrix}] → [\begin{matrix}1 & 1 & 1 & 1 \\ 0 & 1 & 2 & 3 \\ 0 & a & 2a + 1 & 4a \\ 0 & 0 & a & a^{2} \end{matrix}]

→ [\begin{matrix}1 & 1 & 1 & 1 \\ 0 & 1 & 2 & 3 \\ 0 & 0 & 1 & a \\ 0 & 0 & a & a^{2} \end{matrix}] → [\begin{matrix}1 & 1 & 1 & 1 \\ 0 & 1 & 2 & 3 \\ 0 & 0 & 1 & a \\ 0 & 0 & 0 & 0 \end{matrix}] = U, L = [\begin{matrix}1 & 0 & 0 & 0 \\ a & 1 & 0 & 0 \\ 0 & a & 1 & 0 \\ 1 & 0 & a & 1 \end{matrix}] .

Vi ser at U, og dermed A, har rang 3 og derfor er singulær.

b Vi løser Ux = 0 ved tilbakesubstitusjon. Det er én fri variabel x_{4}, som vi setter lik 1, og tilbakesubstitusjon gir da

x_{3} + ax_{4} = 0 ⇒ x_{3} = −a,
x_{2} + 2x_{3} + 3x_{4} = 0 ⇒ x_{2} = −2(−a) − 3 = 2a − 3,
x_{1} + x_{2} + x_{3} + x_{4} = 0 ⇒ x_{1} = −a + 2.

En basis for 𝒩 (A) består altså av den ene vektoren [−a + 2 2a − 3 −a 1]^{T}.

ℛ(A) har en basis bestående av de første 3 søylene i A, siden de tilsvarende søylene i U inneholder pivoter.

c Vi har Ax = b ⇔ LUx = b ⇔ Ux = y der Ly = b. Vi løser altså Ly = [1 1 1 1]^{T} ved framoversubstitusjon:

y_{1} = 1;
ay_{1} + y_{2} = 1 ⇒ y_{2} = 1 − a;
ay_{2} + y_{3} = 1 ⇒ y_{3} = 1 − a(1 − a) = a^{2} − a + 1;
y_{1} + ay_{3} + y_{4} = 1 ⇒ y_{4} = 1 − y_{1} − ay_{3} = −a(a^{2} − a + 1).

Men Ux = y har en løsning hvis og bare hvis y_{4} = 0, det vil si dersom a = 0 eller a^{2}−a+1 = 0; altså

a = 0 eller a = \frac{1}{2} ± \frac{i}{2}\sqrt{3}.

75032 Matrisemetoder 1996–08–13 Løsningsforslag

Oppgave 2

a Søyle j i produktet A = QR er Q · (søyle j i R), det vil si a_{j} = Q [r_{1j} ⋯ r_{jj} 0 ⋯ 0]^{T} hvor vi har utnyttet at R er øvre triangulær. Men Qx er en lineærkombinasjon av søylene i Q: Qx = ∑_{i=1}^{n} x_{i}q_{i}. I dette tilfellet gir det a_{j} = ∑_{i=1}^{j} r_{ij}q_{i}.

Vi skal ha q_{i}^{T}q_{j} = 0 for i ≠ j og q_{i}^{T}q_{i} = 1 (ortonormalitet).

b For j = 1 gir formelen a_{1} = r_{11}q_{1}. Kravet q_{1}^{T}q_{1} = 1 leder til r_{11}^{2} = a_{1}^{T}a_{1}. Krever vi r_{11} > 0 (som er vanlig) blir da r_{1} = ∥a_{1}∥, og q_{1} = a_{1}/∥a_{1}∥.

Ved å multiplisere ligningen fra a) med q_{k}^{T} på venstre side, får vi

q_{k}^{T}a_{j} = ∑_{i=1}^{j} r_{ij}q_{k}^{T}q_{i} = r_{kj}  (1)

fordi vektorene q_{i} er ortonormale. Med k = 1 kan vi dermed regne ut r_{1j} = q_{1}^{T}a_{j} for j = 2, …, n.

Generelt finner vi ved å omorganisere ligningen fra a):

r_{jj}q_{j} = a_{j} − ∑_{i=1}^{j−1} r_{ij}q_{i}  (2)

hvor alt på høyresiden er kjent når vi kommer så langt. Som før ledes vi til at r_{jj} blir normen av vektoren på høyresiden av (2), mens q_{j} blir vektoren delt med r_{jj}. Deretter bruker vi (1) med k = j for å finne r_{j,j+1}, …, r_{j,n}, og dermed har vi alle data som trengs for å øke j med 1 og starte fra (2) igjen.

Dette er faktisk akkurat de samme utregningene som ved Gram-Schmidt ortogonalisering, bare med en liten forskjell i organiseringen: Alle indreproduktene q_{k}^{T}a_{j} = r_{kj} regnes ut så snart det er mulig, istedet for at man venter til man trenger verdiene for å finne neste ortogonale vektor. Setter vi nemlig inn r_{ij} = q_{i}^{T}a_{j} (fra (1)) i (2) finner vi jo

r_{jj}q_{j} = a_{j} − ∑_{i=1}^{j−1}(q_{i}^{T}a_{j})q_{i}  (3)

som er velkjent fra Gram-Schmidt.

c Vi bruker algoritmen fra forrige punkt og finner, i tur og orden (men hopper over noen detaljer): a_{1}^{T}a_{1} = 4, r_{11} = 2, q_{1} = ^{1}/_{2} [1 1 −1 −1]^{T}. Deretter r_{12} = q_{1}^{T}a_{2} = 2u, r_{13} = q_{1}^{T}a_{3} = 0. I neste runde blir (ved (2)) r_{22}q_{2} = a_{2} − r_{12}q_{1} = [2 −2 2 −2]^{T} hvorav r_{22} = 4 og q_{2} = ^{1}/_{2} [1 −1 1 −1]^{T}. Dernest finner vi r_{23} = q_{2}^{T}a_{3} = 2v, og til slutt r_{33}q_{3} = a_{3} − r_{13}q_{1} − r_{23}q_{2} = [1 1 1 1]^{T} som gir r_{33} = 2 og q_{3} = ^{1}/_{2} [1 1 1 1]^{T}. Oppsummert:

A = QR = \frac{1}{2} [\begin{matrix}1 & 1 & 1 \\ 1 & −1 & 1 \\ −1 & 1 & 1 \\ −1 & −1 & 1 \end{matrix}] · [\begin{matrix}2 & 2u & 0 \\ 0 & 4 & 2v \\ 0 & 0 & 2 \end{matrix}] .

d Normalligningen A^{T}Ax = A^{T}b med A = QR forenkles til Rx = Q^{T}b = [4 4 4]^{T} som løses ved tilbakesubstitusjon:

2x_{3} = 4 ⇒ x_{3} = 2;
4x_{2} + 2vx_{3} = 4 ⇒ x_{2} = 1 −^{1}/_{2}vx_{2} = 1 − v;
2x_{1} + 2ux_{2} = 4 ⇒ x_{1} = 2 − ux_{2} = 2 − u + uv

og dermed

x = [\begin{matrix}2 − u + uv \\ 1 − v \\ 2 \end{matrix}] .

Oppgave 3

Fordi matrisen er symmetrisk må den tredje egenvektoren stå ortogonalt på de to første, og er altså parallell med [1 1 −2]^{T}. Da kan vi skrive egenverdiligningen som AQ = QΛ der den ortogonale matrisen har de normaliserte egenvektorene som søyler og diagonalmatrisen Λ har egenverdiene på diagonalen:

Q = [ \begin{matrix}1/\sqrt{3} & 1/\sqrt{2} & 1/\sqrt{6} \\ 1/\sqrt{3} & −1/\sqrt{2} & 1/\sqrt{6} \\ 1/\sqrt{3} & 0 & −2/\sqrt{6} \end{matrix}] , Λ = [\begin{matrix}\sqrt{3} & 0 & 0 \\ 0 & \sqrt{2} & 0 \\ 0 & 0 & λ \end{matrix}]

Dermed får vi

A = QΛQ^{T} = [\begin{matrix}\frac{1}{\sqrt{3}} + \frac{1}{\sqrt{2}} + \frac{λ}{6} & \frac{1}{\sqrt{3}} − \frac{1}{\sqrt{2}} + \frac{λ}{6} & \frac{1}{\sqrt{3}} − \frac{λ}{3} \\ \frac{1}{\sqrt{3}} − \frac{1}{\sqrt{2}} + \frac{λ}{6} & \frac{1}{\sqrt{3}} + \frac{1}{\sqrt{2}} + \frac{λ}{6} & \frac{1}{\sqrt{3}} − \frac{λ}{3} \\ \frac{1}{\sqrt{3}} − \frac{λ}{3} & \frac{1}{\sqrt{3}} − \frac{λ}{3} & \frac{1}{\sqrt{3}} + \frac{2λ}{3} \end{matrix}]

(merk at siden matrisen er symmetrisk, trenger vi bare regne ut seks av de ni matriseelementene).

Oppgave 4

a Vi trekker første rekke fra hver av de øvrige, og utvikler etter siste søyle:

D_{n} = |\begin{matrix}1 + d_{1} & 1 & 1 & ⋯ & 1 \\ −d_{1} & d_{2} & 0 & ⋯ & 0 \\ −d_{1} & 0 & d_{3} & ⋯ & 0 \\ ⋮ & ⋮ & ⋮ & ... & ⋮ \\ −d_{1} & 0 & 0 & ⋯ & d_{n} \end{matrix}|

= d_{n} |\begin{matrix}1 + d_{1} & 1 & ⋯ & 1 \\ −d_{1} & d_{2} & ⋯ & 0 \\ ⋮ & ⋮ & ... & ⋮ \\ −d_{1} & 0 & ⋯ & d_{n−1} \end{matrix}| + (−1)^{n−1} |\begin{matrix}−d_{1} & d_{2} & 0 & ⋯ & 0 \\ −d_{1} & 0 & d_{3} & ⋯ & 0 \\ ⋮ & & & ... & 0 \\ −d_{1} & 0 & 0 & ⋯ & d_{n−1} \\ −d_{1} & 0 & 0 & ⋯ & 0 \end{matrix}|

= d_{n}D_{n−1} + (−1)^{n−1}(−1)^{n−2}(−d_{1}) |\begin{matrix}d_{2} & 0 & & & & 0 \\ 0 & d_{3} & & & & 0 \\ & & . & . & . \\ 0 & ⋯ & & 0 & & d_{n−1} \end{matrix}|

= d_{n}D_{n−1} + d_{1} ⋯ d_{n−1}

og fra dette kan den ønskede formelen lett vises ved induksjon. Vi kan også «oppdage» den: Med p_{n} = d_{1} ⋯ d_{n} finner vi

\frac{D_{n}}{p_{n}} = \frac{D_{n−1}}{p_{n−1}} + \frac{1}{d_{n}}

For n = 2 blir D_{2} = (1 + d_{1})(1 + d_{2}) − 1 = d_{1}d_{2} + d_{1} + d_{2} som gir D_{2}/p_{2} = 1 + 1/d_{1} + 1/d_{2}. Fra formelen over følger dermed umiddelbart at

\frac{D_{n}}{p_{n}} = 1 + ∑_{k=1}^{n} \frac{1}{d_{k}} .

b A_{n} er positivt definit fordi den er symmetrisk og alle dens øvre venstre k × k underdeterminanter, nemlig D_{k} for k = 1, …, n, er positive.