<<

. 11
( 31 .)



>>

a
sondere ist A regul¨r.
a

2. Es gibt genau eine linke Dreiecksmatrix L mit lii > 0, i = 1, . . . , n, so dass
gilt
A = LLT
(Beachte: lii = 1 wird nicht gefordert)

Beweis:
¨
zu 1: Ubung
zu 2: Nach Satz 3.9 gibt es genau eine Zerlegung

A= UV
U = (uik ) : linke Dreiecksmatrix, uii = 1,
V = (vik ) : regul¨re rechte Dreiecksmatrix
a

Sei « 
v11 0
¬ ·
..
D=¬ ·, vii = 0.
.
 
0 vnn
46 Lineare Gleichungssysteme




Setze
R = D’1 V : rechte Dreiecksmatrix, rii = 1
A = AT = RT DT U T = RT DU T .
’ A = U DR,
Wegen der Eindeutigkeit der Zerlegung folgt:

RT = U, d.h. A = U DU T = RT DR.

Behauptung: D ist positiv de¬nit, d.h. vii > 0.
Fur alle x = 0 gilt:
¨
0 < xT Ax = xT RT DRx = (Rx)T DRx
’ 0 < y T Dy fur alle y = 0, da R regular,
¨ ¨
’D positiv de¬nit.
Mit «√ 
v11 0
¬ ·
..
:= ¬ ·,
1/2
L := U D1/2
D .
 

0 vnn
gilt
A = LLT


Bemerkung 3.18. Ist L eine linke untere Dreiecksmatrix, so ist LT eine rech-
te obere Dreiecksmatrix, d.h. fur positiv de¬nite Matrizen existiert eine LR“
¨
Zerlegung mit R = LT . (Achtung: Hier sind die Diagonalelemente von L nicht
normiert.)
Bemerkung 3.19. O¬ensichtlich reicht es aufgrund von Satz 3.9 fur eine Cholesky“
¨
T
Zerlegung A = LL die Matrix L zu bestimmen.
Leider ist das Cholesky“Verfahren nicht so anschaulich wie die Gauß“Elimination.
Zur Bestimmung der Komponenten von L geht man induktiv Spaltenweise vor:
Sei L = (li,j ) die linke untere (n, n)“Dreiecksmatrix mit A = LLT , die nach Satz
3.9 existiert und eindeutig ist. In Komponentenschreibweise ergibt sich
« « « 
a1,1 · · · a1,n l1,1 0 l1,1 · · · ln,1
¬. . · = ¬ . .. ·¬ . ·.
..
¬. · ¬. ·¬ . .·
. .
(3.17) A= . .
. .

an,1 · · · an,n ln,1 · · · ln,n 0 ln,n
O¬ensichtlich gilt

(3.18) a1,1 = l1,1 · l1,1 , also l1,1 = a1,1 ,
Cholesky“Verfahren 47




d.h. l1,1 laßt sich einfach berechnen. Ebenso gilt
¨
ai,1
(3.19) ai,1 = li,1 · l1,1 , also li,1 = , i = 2, . . . , n,
l1,1

womit die erste Spalte von L bekannt ist (Dieses war der Induktionsanfang). Seien
also die li,j , fur j ¤ k ’ 1 bekannt (Induktionsvoraussetzung). Wir mochten als
¨ ¨
n¨chstes die Elemente der k-ten Spalte berechnen. Aus (3.17) ergibt sich
a
2 2
(3.20) ak,k = lk,1 + . . . + lk,k ,

und somit aufgrund der Eindeutigkeit von L

k’1
2
(3.21) lk,k = ak,k ’ lk,j .
j=1


Ebenso ergibt sich aus (3.17)
k
(3.22) ai,k = li,j lk,j
j=1


und damit
k’1
1
(3.23) li,k = ai,k ’ li,j lk,j , i ≥ k + 1.
lk,k j=1


Auf diesem Wege k¨nnen wir die vollst¨ndige Matrix L bestimmen. Der Zusam-
o a
menhang mit dem Ausgangsproblem ist durch

Ax = LLT x = Lc = b

gegeben. Eine Absch¨tzung des Aufwandes ergibt, daß außer n Quadratwurzeln
a
noch

13
n + O(n2 )
(3.24)
6

Rechenoperationen durchgefuhrt werden mussen.
¨ ¨

Bemerkung 3.20. Auch wenn Gauß“ und Cholesky“Verfahren beide die Ord-
nung O(n3 ) besitzen, so ist das Cholesky“Verfahren fur große n dennoch etwa
¨
doppelt so schnell wie das Gauß“Verfahren, man vergleiche die jeweiligen Fakto-
ren vor n3 .
48 Lineare Gleichungssysteme




Die Losung des LGS Ax = b nach der Metholde von Cholesky erfolgt in den drei
¨
Schritten
= LLT : Cholesky“Zerlegung
1. A
2. Lc =b : Vorwartseinsetzen
¨
(3.25)
3. LT x = c : Ruckw¨rtseinsetzen
a
¨

Bei positiv de¬niten Matrizen A sind die Hauptdiagonalelemente aii = eT Aei >
i
0 d.h. positiv. Daruberhinaus kann man leicht zeigen, dass diagonal-dominante
¨
Matrizen (vgl. De¬nition 3.10) mit aii > 0, d.h.

aii > |aik | (i = 1, . . . , n),
k=i

positiv de¬nit sind.
Fur eine positiv de¬nite Matrix A ist die Reduktion der quadratischen Form
¨
xT Ax auf eine Summe von Quadraten (im K¨rper der reellen Zahlen) m¨glich:
o o
xT Ax = xT LLT x = (LT x)T (LT x)
n n
lkj xk )2 .
= (
j=1 k=j

Zus¨tzlich ergibt sich fur die Hauptabschnittsmatrizen (Hauptmenoren):
a ¨
« 
a11 · · · a1k
n n k
¬. .·
ajj > 0, det ¬ . . ·=
(j)
2 2
det A = ljj = ljj > 0.
. .
j=1 j=1 j=1
ak1 · · · akk

Folgerung 3.21. Eine symmetrische Matrix A ist genau dann positiv de¬nit,
wenn « 
a11 · · · a1k
¬. .·
det ¬ . . · > 0 fur k = 1, . . . , n.
¨
. .
ak1 · · · akk
Beispiel 3.22. Die bei der Diskretisierung von Randwertproblemen fur Di¬eren-
¨
tialgleichungen auftretende Matrix

«
2 ’1 0 

·
¬ 
·
¬ ’1 2 ’1 
·
¬ 
¬ ·
.. .. ..
An = ¬ ·n
. . .
¬ ·
·
¬ 
’1 
’1 2 
 


0 ’1 2
Cholesky“Verfahren 49




ist positiv de¬nit, denn mittels der Rekursion

det An+1 = 2 det An ’ det An’1

erkennt man det An = n + 1 > 0.


3.3.3 Bandmatrizen: Bandausnutzende Verfahren
In vielen Anwendungen spielen Bandmatrizen eine wichtige Rolle.

De¬nition 3.23. Unter der Bandbreite einer Matrix A versteht man die kleinste
naturliche Zahl m < n, so dass gilt
¨

aik = 0 fur alle i und k mit |i ’ k| > m.
¨

Beispiel 3.24. Die Matrix
« 
— — —
¬ ·
¬— — — — ·
¬ ·
¬— — — — — ·
¬ ·
¬ ·
.. .. .. .. ..
A=¬ ·
. . . . .

<<

. 11
( 31 .)



>>