75032 Matrisemetoder 27. mai 1988: Løsningsforslag

Løsningsforslaget var opprinnelig skrevet bare som et notat til sensor, og kan til tider være noe for kortfattet eller kryptisk. Likevel kan det kanskje være av en viss nytteverdi.

Oppgave 1

a Om man gjør Gausseliminasjon uten pivotering får man

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

b Nullrommet er rommet utspent av vektoren [1 1 −2]^{T}. Ligningen kan løses hvis og bare hvis b er ortogonal på nullrommet, det vil si [1 1 −2] b = 0, eller β = −1.

Oppgave 2

a Siden (Av_{j})^{T}(Av_{i}) = v_{j}^{T}(A^{T}Av_{i}) er vektorene Av_{1}, …, Av_{n} parvis ortogonale hvis og bare hvis A^{T}Av_{i} er ortogonal på v_{j} for alle j ≠ i. Siden v_{1}, …, v_{n} er en ortogonal basis er dette ekvivalent med at A^{T}Av_{i} er et multiplum av v_{i}, dvs. at v_{i} er en egenvektor for A^{T}A.

Alternativt, om vi setter Q = [v_{1} … v_{n}] er Av_{1}, …, Av_{n} parvis ortogonale hviss AQ^{T}AQ er diagonal, og det er ekvivalent med A^{T}AQ = QΛ for Λ diagonal, dvs. v_{1}, …, v_{n} er egenvektorer for A^{T}A.

Hvis A^{T}Av_{i} = λ_{i}v_{i} er v_{i}^{T}A^{T}Av_{i} = λ_{i}, siden ∥v_{i}∥ = 1. Vi får dermed λ_{i} = ∥Av_{i}∥^{2}.

Vektorene kan velges slik fordi A^{T}A er symmetrisk (spektralteoremet).

b Valgene i oppgaven gjør at w_{1}, …, w_{r} er et ortonormalt sett av vektorer i ℝ^{m}. Så de kan utvides til en ortonormal basis for ℝ^{m}. Da blir

AQ_{2} = [Av_{1} … Av_{n}] = [σ_{1}w_{1} … σ_{r}w_{r} 0 … 0] = Q_{1}Σ

der matrisen Σ er en “diagonal” m × n matrise:

Σ = [ \begin{matrix}σ_{1} \\ & σ_{2} \\ & & . & . & . \end{matrix} ]

75032 Matrisemetoder 27. mai 1988 Løsningsforslag

c I produktet

A = Q_{1}ΣQ_{2}^{T} = [ \begin{matrix}∗ & ∗ & # & # \\ ∗ & ∗ & # & # \\ ∗ & ∗ & # & # \\ ∗ & ∗ & # & # \end{matrix} ] [ \begin{matrix}σ_{1} & 0 & 0 \\ 0 & σ_{2} & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{matrix} ] [ \begin{matrix}∗ & ∗ & ∗ \\ ∗ & ∗ & ∗ \\ # & # & # \end{matrix} ]

vil ikke elementene merket # gi noe bidrag fordi de to siste radene og den siste søylen i Σ er fylt med nuller. Hvis vi fjerner disse radene og søylene vil derfor matriseproduktet være uforandret (og fremdeles veldefinert).

d Først finner vi egenverdiene og egenvekttorene til A^{T}A. Vi får egenverdier 12, 8 og 0 med egenvektorer henholdsvis [1 1 1]^{T}, [1 −1 0]^{T} og [1 1 −2]^{T}. (Som selvsagt danner en ortogonal basis siden A^{T}A er symmetrisk). Dette gir singulærverdier 2\sqrt{3}, 2\sqrt{2} og 0. Om vi multipliserer de to første egenvektorene med A, får vi [3 3 −3 −3]^{T} og [2 −2 −2 2]^{T}. Om vi normaliserer disse, får vi altså de to søylene i Q̂_{1}. Tilsvarende er det de to egenvektorene (normalisert) som blir søyler i Q̂_{2}:

Q̂_{1} = \frac{1}{2} [ \begin{matrix}1 & 1 \\ 1 & −1 \\ −1 & −1 \\ −1 & 1 \end{matrix} ] , Q̂_{2} = [ \begin{matrix}\frac{1}{\sqrt{3}} & \frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{3}} & −\frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{3}} & 0 \end{matrix} ] , Σ̂ = [ \begin{matrix}2\sqrt{3} & 0 \\ 0 & 2\sqrt{2} \end{matrix} ]

e En grei formel er

x = Q̂_{2}Σ̂^{−1}Q̂_{1}^{T}b = [−\frac{1}{6} −\frac{1}{6} −\frac{1}{6} ]^{T}

Formelen A^{+} = Q_{2}Σ^{+}Q_{1}^{T} er kjent fra pensum (der man får Σ^{+} fra Σ^{T} ved å erstatte σ_{i} med σ_{i}^{−1} når σ_{i} > 0), og formelen over kan da begrunnes på samme måte som punkt 2c.

Oppgave 3

a Gram-Schmidt ortogonalisering rett fram på søylene i A gir A = QR, der

Q = \frac{1}{2} [ \begin{matrix}1 & −1 & 1 \\ 1 & −1 & −1 \\ 1 & 1 & 1 \\ 1 & 1 & −1 \end{matrix} ] , R = [ \begin{matrix}2 & 4 & −6 \\ 0 & 2 & −2 \\ 0 & 0 & 6 \end{matrix} ]

b Søylene i Q er en ortonormal basis. c Normalligningen for systemet Ax = b er A^{T}Ax = A^{T}b, som etter innsetting, forkorting og

forenkling gir x = R^{−1}Q^{T}b. Følgelig må A^{+} = R^{−1}Q^{T}.

d Hvis vi kaller høyresiden b og løsningen x så må Rx = Q^{T}b. Denne ligningen løses ved tilbakesubstitusjon, og vi får Qb = [6 −6 6]^{T}, x = [10 −2 1]^{T}.

Oppgave 4

Ligningen på matriseform:

[ \begin{matrix}x_{n+1} \\ x_{n} \\ x_{n−1} \end{matrix} ] = [ \begin{matrix}−\frac{3}{2} & −\frac{1}{2} & \frac{3}{4} \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{matrix} ] [ \begin{matrix}x_{n} \\ x_{n−1} \\ x_{n−2} \end{matrix} ]

Karakteristisk polynom til koeffisientmatrisen blir −λ^{3} − \frac{3}{2}λ^{2} − \frac{1}{2}λ + \frac{3}{4}. Den opplagte egenverdien som følger av løsningen x_{n} = 2^{−n} er 1/2. Dividerer vi det karakteristiske polynomet med λ − \frac{1}{2}, får vi −(λ^{2} + 2λ + \frac{3}{2}), og røttene i dette polynomet har produkt 3/2, så minst en egenverdi har absoluttverdi større enn 1 og vi har instabilitet (ikke alle løsninger går mot 0). (Røttene er −1 ± \frac{i}{2} \sqrt{2}.)