Musterlösung Aufgabe 27

Aufgabe 27: (Cholesky-Zerlegung dünnbesetzter Matrizen) Betrachte eine s.p.d. Matrix der Form

A = ( \begin{matrix}d_{1} & a_{1} & 0 & … & 0 & a_{n} \\ a_{1} & d_{2} & ... & 0 & … & 0 \\ 0 & ... & ... & ... & ... & ⋮ \\ ⋮ & ... & ... & ... & ... & 0 \\ 0 & … & 0 & ... & d_{n−1} & a_{n−1} \\ a_{n} & 0 & … & 0 & a_{n−1} & d_{n} \end{matrix} ) .

Zeige, daß eine Faktorisierung A = LL^{T} mit einem Cholesky-Faktor der Form

L = ( \begin{matrix}δ_{1} \\ β_{1} & ... \\ 0 & ... & ... \\ ⋮ & ... & ... & ... \\ 0 & … & 0 & β_{n−2} & δ_{n−1} \\ γ_{1} & γ_{2} & … & γ_{n−2} & γ_{n−1} & γ_{n} \end{matrix} )

existiert. Finde einen Algorithmus (in Pseudo-Code anzugeben), der die Daten δ_{1}, …, γ_{n} in der Laufzeit O(n) bestimmt. Musterlösung: Der Ansatz

L = ( \begin{matrix}l & 0 \\ γ^{T} & γ_{n} \end{matrix} ) , L^{T} = ( \begin{matrix}l^{T} & γ⃗ \\ 0 & γ_{n} \end{matrix} ) , LL^{T} = ( \begin{matrix}ll^{T} & lγ⃗ \\ (lγ⃗)^{T} & ⟨γ⃗, γ⃗⟩ + γ_{n}^{2} \end{matrix} ) ,

führt mit

A = ( \begin{matrix}d_{1} & a_{1} & & & & a_{n} \\ a_{1} & d_{2} & ... & & & 0 \\ & ... & ... & ... & & ⋮ \\ & & ... & ... & a_{n−2} & 0 \\ & & & a_{n−2} & d_{n−1} & a_{n−1} \\ a_{n} & 0 & … & 0 & a_{n−1} & d_{n} \end{matrix} ) = ( \begin{matrix}a & a⃗ \\ a^{T} & d_{n} \end{matrix} )

zu

a = ll^{T} , lγ⃗ = a⃗ , d_{n} = ⟨γ⃗, γ⃗⟩ + γ_{n}^{2} .

D.h., bestimme i) den linken oberen (n − 1) × (n − 1)-Block

l = ( \begin{matrix}δ_{1} \\ β_{1} & ... \\ & ... & ... \\ & & β_{n−2} & δ_{n−1} \end{matrix} )

von L durch Cholesky-Faktorisierung des 3-bändigen Blocks a, ii) dann die n.te Zeile γ^{T} = (γ_{1}, …, γ_{n−1}) aus

lγ⃗ = ( \begin{matrix}δ_{1} \\ β_{1} & ... \\ & ... & ... \\ & & β_{n−2} & δ_{n−1} \end{matrix} ) ( γ_{1} ; γ_{2} ; ⋮ ; γ_{n−1} ) = ( a_{n} ; 0 ; ⋮ ; 0 ; a_{n−1} ) ,

iii) dann γ_{n} durch

γ_{n} = \sqrt{d_{n} − ⟨γ⃗, γ⃗⟩} .

Zu i):

l = ( \begin{matrix}δ_{1} \\ β_{1} & ... \\ & ... & ... \\ & & β_{n−2} & δ_{n−1} \end{matrix} ) , l^{T} = ( \begin{matrix}δ_{1} & β_{1} \\ & ... & ... \\ & & ... & β_{n−2} \\ & & & δ_{n−1} \end{matrix} ) ⇒

ll^{T} = ( \begin{matrix}δ_{1}^{2} & δ_{1}β_{1} \\ δ_{1}β_{1} & β_{1}^{2} + δ_{2}^{2} \\ & ... & ... & ... \\ & & ... & ... & δ_{n−2}β_{n−2} \\ & & & δ_{n−2}β_{n−2} & β_{n−2}^{2} + δ_{n−1}^{2} \end{matrix} ) = ( \begin{matrix}d_{1} & a_{1} \\ a_{1} & ... & ... \\ & ... & ... & a_{n−2} \\ & & a_{n−2} & d_{n−1} \end{matrix} )

Die Cholesky-Faktorisierung des linken oberen Blocks ergibt sich hiermit durch δ_{1} := \sqrt{d_{1}} ;

                   for i = 2 .. n − 1 do begin

β_{i−1} := a_{i−1}/δ_{i−1} ; δ_{i} := \sqrt{d_{i} − β_{i−1}^{2}} ;

                   end;

Zu ii): Rücksubstitution

\begin{matrix}γ_{1} := a_{n}/δ_{1} ; \\ for i = 2 .. n − 2 do γ_{i} := −β_{i−1} γ_{i−1}/δ_{i}; \\ γ_{n−1} := ( a_{n−1} − β_{n−2}γ_{n−2} ) / δ_{n−1} ; \end{matrix}

Zu iii):

γ_{n} := \sqrt{d_{n} − ∑_{i=1}^{n−1} γ_{i}^{2}} ;

Zusammengefaßt:

δ_{1} := \sqrt{d_{1}} ; γ_{1} := a_{n}/δ_{1} ;

for i = 2 .. n − 2 do begin

β_{i−1} := a_{i−1}/δ_{i−1} ; δ_{i} := \sqrt{d_{i} − β_{i−1}^{2}} ; γ_{i} := −β_{i−1} γ_{i−1}/δ_{i};

end;

β_{n−2} := a_{n−2}/δ_{n−2} ; δ_{n−1} := \sqrt{d_{n−1} − β_{n−2}^{2}} ;

γ_{n−1} := \frac{a_{n−1} − β_{n−2}γ_{n−2}}{δ_{n−1}} ; γ_{n} := \sqrt{d_{n} − ∑_{i=1}^{n−1} γ_{i}^{2}} ;

Rechenaufwand: 1 + 4 (n − 3) + 4 + n − 1 ≈ 5 n Multiplikationen, n Wurzeln.