<<

. 8
( 31 .)



>>

an,1 · · · an,n

gegeben.

(1)
1. Schritt: Sei a1,1 = 0

« 
(1) (1)
a1,1 ··· · · · a1,n
¬ ·
(2) (2)
¬0 ·
a2,2 · · · a2,n
¬ ·
L1 A = ¬ . (vgl. (3.6) mit j = 1)
·
. .
¬. ·
. .
. . . 
(2) (2)
0 an,2 · · · an,n

mit
(1)
ai1
li1 : = , i = 2, . . . , n,
(1)
a11
(2) (1) (1)
aik = aik ’ li1 a1k , i, k = 2, . . . , n.

In Worten: Subtrahiere von der i-ten Zeile der Matrix A das li1 -fache der 1. Zeile,
i = 2, ..., n.
Allgemein sei nun unsere Ausgangssituation vor dem j-ten Schritt (j ≥ 2) be-
kannt.
Ausgangsmatrix vor dem j-ten Schritt (j ≥ 2):
« 
(1) (1)
a11 a1n
¬ ·
.
¬ ·
.. .
¬ ·
. .
¬ ·
¬ ·
(j) (j)
Lj’1 . . . L1 A = ¬ ·.
ajj · · · ajn
¬ ·
¬ ·
. .
. .
¬0 ·
. .
 
(j) (j)
anj · · · ann

Mit diesem Wissen k¨nnen wir den j-ten Schritt in Angri¬ nehmen:
o
LR“Zerlegung und Gauß“Elimination 35



(j)
j-ter Schritt (j ≥ 2): Sei ajj = 0
« 
(1) (1)
a1,1 ··· ··· ··· ··· a1,n
¬ ·
.
¬ ·
.. .
¬ ·
. .
¬ ·
¬ ·
(j) (j)
aj,j ··· ··· aj,n
¬ ·
Lj Lj’1 . . . L1 A = ¬ ·
¬ ·
(j+1) (j+1)
0 aj+1,j+1 · · · aj+1,n
¬ ·
¬ ·
. . .
¬ ·
. . .
¬ ·
. . .
 
(j+1) (j+1)
0 an,j+1 · · · an,n

mit
(j)
aij
lij = , i = j + 1, . . . , n,
(j)
ajj
(j+1) (j) (j)
aik = aik ’ lij ajk , i, k = j + 1, . . . , n.

Nach n ’ 1 Schritten erhalten wir dann das gewunschte Resultat:
¨
« 
(1) (1)
a11 · · · · · · a1n
¬ ·
.
..
¬ ·
.
. .
¬ ·
Ln’1 . . . L1 A = ¬ · =: R = (rik )
(3.9) ¬ ·
.
.. .
¬ ·
. .
 
(n)
0 ann

(i)
mit rii = aii = 0.

Wendet man die Matrizen Lj direkt auf die erweiterte Matrix (A, b) an, so ergibt
sich
Ln’1 . . . L1 (A, b) = (R, c).

Das LGS Ax = b ist dann ¨quivalent zu Rx = c und kann gem¨ß (3.5) gel¨st
a a o
werden (Gauß-Elimination).

Aus (3.9) folgt mittels der Formeln (3.7)(3.8) die LR-Zerlegung der Matrix A:

A = L’1 . . . L’1 R =: LR
(3.10) 1 n’1
36 Lineare Gleichungssysteme
« 
1 0
¬ ·
¬ ·
..
¬ ·
.
l2,1
¬ ·
¬ ·
. .. ..
L=¬ · linke Dreiecksmatrix
. . .
.
¬ ·
¬ ·
.
¬ ·
.. ..
.
¬ ·
. .
.
 
ln,1 · · · · · · ln,n’1 1

Bei gegebener LR-Zerlegung A = LR ist das LGS Ax = b ¨quivalent zu den
a
beiden leicht au¬‚¨sbaren LGS
o

Lc = b, Rx = c.

Insbesondere folgt noch aus (3.10)
n
det(A) = det(L) det(R) = Π rjj .
j=1

(j)
¨
Bei unseren bisherigen Uberlegungen hatten wir stets ajj = 0 voraussetzen
mussen und es stellt sich die Frage, wann dies gesichert anzunehmen ist.
¨
(j)
Problem: Wann gilt ajj = 0?

Satz 3.3. Sei A eine (n, n)-Matrix, deren Hauptabschnittsmatrizen Aj regul¨r
a
sind. Dann gibt es eine eindeutige Zerlegung
A = LR,
L linke Dreiecksmatrix mit ljj = 1, j = 1, . . . n,
R regul¨re rechte Dreiecksmatrix.
a

Beweis: Vgl. Satz 3.9

3.2.4 Permutationsmatrizen
(j)
Zur Behandlung des Falles ajj = 0 fur ein j benotigen wir sogenannte Permuta-
¨ ¨
tionsmatrizen. Hierzu sei
«
0
¬.·
¬.·
¬.·
¬·
¬0·
¬·
¬·
ei = ¬ 1 · ← i der i ’ te kanonische Einheitsvektor
¬·
¬0·
¬·
¬.·
¬.·
.
0
LR“Zerlegung und Gauß“Elimination 37




Eine Matrix P heißt Permutationsmatrix, wenn eine Permutation (i1 , . . . , in ) von
(1, . . . , n) existiert mit
« T
ei1
¬.·
P = ¬ . ·.
.
eTn
i



Insbesondere haben Permutationsmatrizen die Eigenschaften: P 2 = I, also P ’1 =
P.



3.2.5 Gauß“Elimination/LR“Zerlegung mit Pivoting

Wir gehen davon aus, dass wir vielleicht bereits einige Schritte zur Gauß“Elimination
bzw. LR“Zerlegung durchgefuhrt haben und be¬nden uns im j“ten j ≥ 1 Schritt.
¨

j-ter Schritt (j ≥ 1): Die Ausgangsmatrix sei

« 
(1) (1)
a11 a1n
¬ ·
.
..
¬ ·
.
.
¬ ·
.
¬ ·
¬ ·
(j) (j)
A(j) A(1) := A
ajj · · · ajn

<<

. 8
( 31 .)



>>