<<

. 7
( 31 .)



>>

o o
Bei der L¨sung linearer Gleichungssysteme sind verschiedene F¨lle m¨glich:
o a o
1. m = n: rang(A) = n, d.h. Ax = b ist eindeutig l¨sbar. Da A invertierbar ist
o
folgt x = A’1 b. Fur numerische Rechnungen ist diese Darstellung jedoch
¨
nicht geeignet: auch die Cramersche Regel ist fur n ≥ 3 numerisch nicht
¨
brauchbar.
LR“Zerlegung und Gauß“Elimination 31




Abbildung 3.2: Eine eher kleine Platine.


2. m > n: Das LGS Ax = b heißt uberbestimmt und hat im allgemeinen keine
¨
Losung. Stattdessen wird ein Ersatzproblem gelost, vgl. Lineare Ausgleichs-
¨ ¨
rechnung.

3. m < n: Das LGS Ax = b heißt unterbestimmt. Wenn eine L¨sung existiert,
o
dann hat der L¨sungsraum die Dimension n’rang(A). Anwendungen ¬ndet
o
man etwa in der Linearen Optimierung.


3.2 LR“Zerlegung und Gauß“Elimination
3.2.1 Idee der Gauß“Elimination/LR“Zerlegung
Sei A = (ai,k ) eine (n, n)“Matrix und b ∈ IRn . Zu l¨sen sei das LGS
o

(3.2) Ax = b

Das Gauß™sche“Eliminationsverfahren zur L¨sung von LGS haben sie bereits im
o
Rahmen ihres bisherigen Studiums kennengelernt. Es ist ein recht anschauliches
Verfahren, das sich zudem leicht implementieren l¨ßt.
a
Wir betrachten zun¨chst den vereinfachten Fall, daß die Matrix A in oberer Drei-
a
ecksform vorliegt, d.h.
« 
r1,1 r1,2 · · · r1,n
¬ ·
¬ 0 r2,2 · · · r2,n ·
¬ ·
(3.3) A=R=¬ . .·
.. ..
¬. .·
. .
. .
0 ··· 0 rn,n

Man spricht dann von einem gesta¬elten Gleichungssystem, der Grund ist leicht
ersichtlich. In diesem Fall kann fur ri,i = 0 leicht eine L¨sung von Rx = c (hier
o
¨
32 Lineare Gleichungssysteme




mit c := b) mittels der rekursiven Vorschrift
cn
xn = ,
rn,n
cn’1 ’ rn’1,n xn
xn’1 = ,
rn’1,n’1
(3.4) .
.
.
c1 ’ r1,2 x2 ’ . . . ’ r1,n xn
x1 = ,
r1,1
beschrieben werden. In kompakter Form ergibt sich
n
1
(3.5) xi = ci ’ ri,j xj , i = n, n ’ 1, . . . , 1.
ri,i j=i+1

Idee der Gauß-Elimination: Forme ein allgemeines Gleichungssystem Ax = b in
ein Gleichungssystem Rx = c um, so dass die Matrix R in oberer Dreiecksform
vorliegt.

3.2.2 Frobeniusmatrizen
Zur Durchfuhrung der Gauß-Elimination werden sogenannte Frobeniusmatrizen
¨
bzw. Elementarmatrizen Lj benotigt:
¨
« 
1
¬ ·
..
¬ ·
.
¬ ·
0
¬ ·
¬ ·
..
¬ ·
.
¬ ·
¬ ·
¬ · ← j-te Zeile
1
Lj = ¬ ·
¬ ·
..
¬ ·
.
’lj+1,j
¬ ·
¬ ·
.
¬ ·
..
.
¬0 ·
.
.
 
’ln,j 1


j-te Spalte
Fur diese Elementarmatrizen gelten die nachfolgend aufgefuhrten Rechenregeln.
¨ ¨
Sei hierzu die Matrix
« 
a1
¬.·
A = ¬ . · mit ai = (ai1 , . . . , ain ).
.
an
LR“Zerlegung und Gauß“Elimination 33




gegeben. Fur die Multiplikation einer Elementarmatrix mit einer Matrix gilt:
¨
« 
a1
¬ ·
.
¬ ·
.
¬ ·
.
¬ ·
¬ ·
aj
¬ ·
(3.6) Lj A = ¬ ·.
¬ aj+1 ’ lj+1,j aj ·
¬ ·
¬ ·
.
¬ ·
.
.
 
an ’ ln,j aj

Die Inverse einer Elementarmatrix l¨ßt sich einfach angeben:
a
« 
1
¬ ·
..
¬ ·
.
¬ ·
¬ ·
¬ ·
1
¬ ·
L’1 = ¬ ·.
(3.7) ¬ ·
..
j
¬ ·
.
lj+1,j
¬ ·
¬ ·
. ..
¬ ·
. .
.
 
ln,j 1

Fur die Multiplikation zweier invertierter Elementarmatrizen gilt die interessante
¨
Beziehung:
« 
1
¬ ·
..
¬ ·
.
¬ ·
¬ ·
¬ ·
1
¬ ·
¬ ·
¬ ·
..
· ←j
¬ .
lj+1,j
¬ ·
¬ ·
. ..
¬ ·
. .
’1 ’1 .
(3.8) Lj · Lk = ¬ ·
¬ ·
.
¬ ·
.
¬ ·
. 1
¬ ·
¬ ·
. ..
¬ · ←k
. .
. lk+1,k
¬ ·
¬ ·
¬ ·
. . ..
. .
¬ ·
.
. .
 
ln,j ln,k 1



j k
34 Lineare Gleichungssysteme




3.2.3 Gauß“Elimination/LR“Zerlegung ohne Pivoting
Sei die Matrix
« 
(1) (1)
a1,1 ··· a1,n
¬ ·
. .
A := ¬ ·
. .
. .
 
(1) (1)

<<

. 7
( 31 .)



>>