<<

. 9
( 31 .)



>>

(3.11) := ¬ ·,
¬ ·
¬ ·
. .
. .
¬0 ·
. .
 
(j) (j)
anj · · · ann


Wir fuhren eine Spaltenpivot-Suche durch: W¨hle eine Zeile r mit
a
¨

(j) (j)
|arj | = max |aij |.
i≥j



Wir haben verschiedenen Falle zu unterscheiden:
¨

(j)
1. Fall: arj = 0: A ist singul¨r, setze Lj = I.
a

(j)
2. Fall: arj = 0: Vertausche die j-te Zeile mit der r-ten Zeile in A(j) . Dies entspricht
38 Lineare Gleichungssysteme




einer Multiplikation von links mit der Permutationsmatrix
« 
1
¬ ·
..
¬ ·
.
¬ ·
¬ ·
¬ ·
1
¬ ·
¬ ·
¬ ··· ··· ··· 0 ··· ··· ··· 1 ··· ··· ··· · ← j
¬ ·
¬ ·
1
¬ ·
¬ ·
¬ ·
..
Pj = ¬ .
·
.
¬ ·
¬ ·
1
¬ ·
¬ ·
··· ··· 1 ··· ··· ··· 0 ··· ··· ··· · ← r
¬ ···
¬ ·
¬ ·
1
¬ ·
¬ ·
¬ ·
..
¬ ·
.
 
1

Damit erhalten wir im ungunstigsten Fall (in jedem Schritt ist eine Vertauschung
¨
von Zeilen notwendig) nach n ’ 1 Schritten
(3.12) Ln’1 Pn’1 . . . L2 P2 L1 P1 A = R.
Dies fuhrt zu einer LR-Zerlegung mittels des folgenden Hilfssatzes.
¨
Hilfssatz 3.4. Sei j < k. Die Permutationsmatrix Pk vertausche die Zeilen k
und r ≥ k. Dann gilt
Pk Lj = Lj Pk ,
wobei Lj aus Lj dadurch hervorgeht, dass man in der j-ten Spalte das k-te und
r-te Element vertauscht.
Beweis: « 
1
¬ ·
..
¬ ·
.
¬ ·
¬ ·
¬ · ←j
1
¬ ·
¬ ·
. ..
¬ ·
. .
.
¬ ·
¬ · ←k
Lj = ¬ 0·
’lkj 1
¬ ·
¬ ·
. ..
¬ ·
. .
¬ ·
.
¬ ·
¬ ·
..
¬ · ←r
.
’lrj
¬ ·
 
.
.
. 0 1
LR“Zerlegung und Gauß“Elimination 39
« 
1
¬ ·
..
¬ ·
.
¬ ·
¬ · ←j
¬ ·
1
¬ ·
¬ ·
. ..
¬ ·
. .
¬ ·
.
Pk Lj = ¬ ·
¬ · ←k
’lrj 0 ··· 1
¬ ·
¬ ·
. . .
¬ ·
. . .
¬ ·
. . .
¬ · ←r
¬ ·
’lkj 1 ··· 0
¬ ·
 
. ..
. .
.
‘ ‘
k r
2
’ Pk Lj Pk = Lj , Pk = I

’ Pk Lj = Lj Pk .

Die Anwendung des Hilfssatzes auf (3.12) zeigen wir der Einfachheit halber fur
¨
n=4:

L3 P3 L2 P2 L1 P1 A =R
” L3 P3 L2 L1 P2 P1 A =R
” L3 L2 L1 P3 P2 P1 A =R
=:P (Permutationsmatrix)
’1 ’1 ’1
” P A = LR, L := L 1 L 2 L3 .

Die Anwendung der obigen Operationen auf die erweiterte Matrix (A, b) fuhrt auf
¨
die Matrix (R, c). R ist regul¨r, wenn A regul¨r ist, und das LGS Rx = c kann
a a
gemaß (3.5) gelost werden.
¨ ¨
Zusammenfassend erhalten wir das folgende Resultat:
Satz 3.5 (LR“Zerlegung und Gauß-Elimination). Zu jeder (n, n)-Matrix A
gibt es eine Permutationsmatrix P , eine linke Dreiecksmatrix L und eine rechte
Dreiecksmatrix R, so dass

P A = LR, ljj = 1 fur j = 1, . . . n.
¨

Ist A regul¨r, so ist auch R regul¨r und die Gauß-Elimation liefert die eindeutige
a a
L¨sung von Ax = b.
o
Bemerkung 3.6. Bei der praktischen Durchfuhrung der Gauß-Elimination kann
¨
man die wesentlichen Elemente von L, d.h. li,k , i ≥ k + 1, k ¤ j ’ 1, auf den
Null-Elementen der Matrix A(j) in 3.11 abspeichern.
40 Lineare Gleichungssysteme




Beispiel 3.7. « «  « 
316 x1 2
¬ ·¬ ·¬·
 2 1 3   x2  =  7 
111 x3 4
Die Pivot“Elemente in den erweiterten Matrizen werden durch einen Unterstrich
markiert.
1. Schritt: « 
3162
¬ ·
2 1 3 7
1114
Anwendung von L1 : « 
3 1 6 2
¬ ·
¬ 2/3 1/3 ’1 17/3 ·
 
1/3 2/3 ’1 10/3
2. Schritt:
Vertausche Zeile 2 und 3
« 
3 1 6 2
¬ ·
¬ 1/3 2/3 ’1 10/3 ·
 
2/3 1/3 ’1 17/3
Anwendung von L2 :
« 
3 1 6 2
¬ ·
¬ 1/3 10/3 ·
2/3 ’1
 
2/3 1/2 ’1/2 4
«  « 
1 0 0 31 6
¬ · ¬ ·
’ L =  1/3 0  , R =  0 2/3 ’1 
1
2/3 1/2 1 0 0 ’1/2
«  « 
10 0 316
¬ · ¬ ·
’ P = 0 0 1 , PA =  1 1 1 
01 0 213
Somit gilt P A = LR
Wir erhalten das gesta¬elte Gleichungssystem Rx = c:
« « « 
31 6 x1 2 x1 = 19
¬ ·¬ ·¬ ·
 0 2/3 ’1   x2  =  10/3  , x2 = ’7
0 0 ’1/2 x3 4 x3 = ’8
LR“Zerlegung und Gauß“Elimination 41




Das Gauß“Verfahren zur Losung von Ax = b untergliedert sich somit in drei
¨
wesentliche Schritte:
Gauß-Elimination:

<<

. 9
( 31 .)



>>