<<

. 8
( 60 .)



>>

u
j=1


33
Dies ist eine Teilmenge der Menge aller n-Tupel von Elementen in K : L ‚ K n .
L kann naturlich leer sein, wie wir schon gesehen haben. Wir gehen nun dar-
¨
an, das Gleichungssystem systematisch zu losen. Die Methode heisst “Gauss-
¨
Elimination”, nach dem beruhmten Mathematiker Carl Friedrich Gauss, von ihm
¨
selbst “eliminatio vulgaris” genannt. Dazu fuhren wir Manipulationen des Sy-
¨
stems durch, welche die L¨sungsmenge nicht ¨ndern. Ziel dieser Manipulationen
o a
ist es, das System auf ein anderes System zu reduzieren, bei dem die L¨sungen
o
unmittelbar abgelesen werden k¨nnen. Die Operationen nennt man elementare
o
Zeilenoperationen (die “Zeilen” sind einfach die einzelnen Gleichungen):
Z1 Vertauschen zweier Zeilen des Gleichungssystems.
Z2 Multiplikation einer Zeile mit einem K¨rperelement ± = 0. Hier werden alle
o
Koe¬zienten einer der Gleichungen mit ± multipliziert, und naturlich auch
¨
das entsprechende bi .
Z3 Addition des ±-fachen einer Zeile zu einer anderen, ± ∈ K. Wird etwa das ±-
fache der l-ten Zeile zur k-ten addiert, so sieht das Gleichungssystem (3.3)
wie folgt aus:
a11 x1 + a12 x2 +...+ a1n xn = b1 ,
. . . .
. . . .
. . . .
ak1 x1 + ±al1 x1 + ak2 x2 + ±al2 x2 + . . . + akn xn + ±aln xn = bk + ±bl ,
. . . .
. . . .
. . . .
am1 x1 + am2 x2 +...+ amn xn = bm .
Alle Gleichungen ausser der k-ten bleiben unangetastet. In kompakter
Schreibweise sieht das Gleichungssystem nach dieser Zeilenoperation wie
folgt aus:
n
aij xj = bi , fur 1 ¤ i ¤ m, i = k, (3.4)
¨
j=1
n
(akj + ±alj ) xj = bk + ±bl . (3.5)
j=1


Satz 3.1 Die elementaren Zeilenoperationen Z1-Z3 ver¨ndern die L¨sungsmenge
a o
eines Gleichungssystems nicht.
Beweis. Fur Z1 und Z2 ist das o¬ensichtlich. Wir diskutieren Z3: Sei L
¨
die L¨sungsmenge von (3.3) und L die L¨sungsmenge von (3.4), (3.5). Ist x =
o o
(x1 , x2 , . . . , xn ) ∈ L, so gilt naturlich (3.4) und ferner
¨
n n n
(akj + ±alj ) xj = akj xj + ±alj xj = bk + ±bl ,
j=1 j=1 j=1


34
was nichts anderes als (3.5) ist. Demzufolge ist x ∈ L , und wir haben somit
gezeigt, dass L ‚ L ist.
Zum Beweis von L ‚ L beachte man, dass wir das “alte” Gleichungssystem
(3.3) aus dem Gleichungssystem (3.4), (3.5) erhalten, indem wir zur k-ten Zeile
das (’±)-fache der l-ten addieren. Damit ergibt sich das “alte” Gleichungssystem
aus dem “neuen” ebenfalls durch eine Zeilenoperation des Typs Z3. Die vorherige
¨
Uberlegung zeigt also L ‚ L. Damit ist L = L bewiesen.
Fur den weiteren Verlauf der Diskussion ist es uber¬‚ussig und eher beschwer-
¨ ¨ ¨
lich, die xi in der Notation immer mitzuschleppen. Wir betrachten deshalb ein-
fach die sogenannte Koe¬zientenmatrix
« 
a11 a12 . . . a1n
¬ a21 a22 . . . a2n ·
A=¬ . ·.
¬ ·
. .
. . .
. . . 
am1 am2 . . . amn

Eine solche Anordnung von K¨rperelementen nennt man eine m — n-Matrix. Die
o
obige Matrix hat m Zeilen und n Spalten. aij nennt man die ij-te Komponente
der Matrix. Wir schreiben die Matrix auch als

A = (aij )1¤i¤m, 1¤j¤n ,

oder auch einfach kurz A = (aij ) , wenn klar ist, wieviele Zeilen und Spalten
sie hat. Man bezeichnet die Zeilen und Spalten als “Vektoren” (sp¨ter mehr zu
a
diesem Begri¬). Die Matrix hat also die m Zeilenvektoren

, 1 ¤ i ¤ m,
ai1 ai2 . . . ain

und die n Spaltenvektoren
« 
a1j
a2j
¬ ·
· , 1 ¤ j ¤ n.
¬ ·
.
.
¬
.
 
amj

Einen Zeilenvektor k¨nnen wir naturlich auch als 1 — n-Matrix au¬assen, und
o ¨
einen Spaltenvektor als m — 1-Matrix. Einige zus¨tzliche Begri¬e: Nullvekto-
a
ren sind Vektoren, deren Komponenten alle gleich Null sind. Ebenfalls ist die
Nullmatrix die Matrix mit allen aij = 0. Wir k¨nnen unsere Matrix A durch
o
den zus¨tzlichen Spaltenvektor
a
« 
b1
¬ b2 ·
b=¬ . · (3.6)
¬ ·
. .
bm

35
erganzen und erhalten dann die m — (n + 1)-Matrix
¨
« 
a11 a12 . . . a1n b1
¬ a21 a22 . . . a2n b2 ·
(A, b) := ¬ . ·.
¬ ·
. . .
. . . .
. . . . 
am1 am2 . . . amn bm
Die oben beschriebenen elementaren Zeilenoperationen verandern dann einfach
¨
die Zeilenvektoren, indem bei Z1 zwei Zeilenvektoren vertauscht werden, bei Z2
eine Zeile in jeder Komponente mit einem Korperelement ± = 0 multipliziert
¨
wird und bei Z3 das ±-fache einer Zeile zu einer anderen Zeile addiert wird.
Wir wollen die Matrix (A, b) nun mit Hilfe solcher Zeilenoperationen auf ei-
ne besonders einfache Form bringen, die sogenannte Stufenform. Wir suchen
zunachst nach der ersten Spalte der Matrix A, die nicht gleich dem Nullvektor
¨
ist, d.h. deren Komponenten nicht alle gleich Null sind. Gibt es keine derartige
Spalte, so ist A die Nullmatrix. In diesem Fall ist das Gleichungssystem (3.3)
besonders einfach n
0 · xj = bi , 1 ¤ i ¤ m.
j=1

Die Losungsmenge dieses Gleichungssystems L ist naturlich ganz einfach zu be-
¨ ¨
stimmen: Gibt es mindestens ein bi = 0, so ist L = …, d.h. es gibt gar keine
Losungen. Gilt hingegen bi = 0 fur alle i, so sind o¬ensichtlich alle n-Tupel
¨ ¨
(x1 , x2 , . . . , xn ) Losungen, d.h. es gilt L = Rn . In diesem Fall konnen wir die
¨ ¨
Losungsmenge somit unmittelbar ¬nden. Wir fahren daher fort mit dem Fall,
¨
wo A mindestens eine vom Nullvektor verschiedene Spalte hat. Nehmen wir (der
notationellen Einfachheit halber) an, dies sei die erste Spalte. Dann konnen wir
¨
mit einer Vertauschung von Zeilen (was die Losungsmenge nicht verandert), die
¨ ¨
Matrix (A, b) so verandern, dass die Komponente in der linken oberen Ecke = 0
¨
ist. Wir gehen also nun weiter davon aus, dass a11 = 0 ist.
Nun zum eigentlichen Eliminationsschritt: Wir ver¨ndern die Matrix (A, b)
a
mit Hilfe von Zeilenoperationen Z3, so dass die erste Spalte keine weitere Kom-
ponente = 0 hat; wir “eliminieren” also x1 aus den Gleichungen Nummer 2 bis
m. Dies geht sehr einfach: Wir addieren das (’a21 /a11 )-fache der ersten Zeile
zur zweiten. Damit erhalten wir fur die zweite Zeile
¨
a21 a21 a21
0 a22 ’ . . . a2n ’ b2 ’
a a b .
a11 12 a11 1n a11 1

Nun fahren wir entsprechend weiter mit der dritten, vierten bis zur letzten Zeile
und erhalten die Matrix
« 
a11 a12 ... a1n b1
¬ 0 a22 ’ a21 a12 . . . a2n ’ a21 a1n b2 ’ a21 b1 ·
a11 a11 a11
·.
¬ ·
. . .
. . .
¬
0 . . . 
0 am2 ’ am1 a12 . . . amn ’ am1 a1n bm ’ am1 b1
a11 a11 a11


36
Wir betrachten nun die (m ’ 1) — (n ’ 1)-Matrix
a22 ’ a11 a12 . . . a2n ’ a11 a1n
a21
« 
21
a
. .
— . .
A := 
¬ ·
. . 
am2 ’ am1 a12 . . . amn ’ am1 a1n
a11 a11

und den Spaltenvektor
a21
« 
b2 ’ b
a11 1
.
b— :=  . .
¬ ·
.
am1
bm ’ b
a11 1
Ist A— die Nullmatrix, so ist das Eliminationsverfahren zu Ende, und sonst verfah-
ren wir mit der Matrix (A— , b— ) in gleicher Weise wie vorher mit der Matrix (A, b) .
Es ist o¬ensichtlich, dass das Verfahren nach endlich vielen Schritten abbricht,
wobei wir dann bei einer Matrix A, b der folgenden Form angelangt sind:
« 
0 . . . 0 a1n1 a1,n1 +1 . . . . . . . . . . . . . . . a1n b1
¬ 0 ... ... ... ... 0 a2n2 . . . . . . . . . a2n b2 ·
¬ ·
¬. . .·
... ...
¬. . .·
. . .·
¬
¬ 0 ... ... ... ... . . . . . . 0 ak,nk . . . akn bk ·
¬ ·
¬ 0 ... ... ... ... . . . . . . . . . . . . . . . 0 bk+1 ·
¬ ·
¬. . .·
. . .
. . .
0 ... ... ... ... ... ... ... ... ... 0 bm
Die formale Beschreibung sieht wie folgt aus: Es ist 0 ¤ k ¤ n, und 1 ¤ n1 <
. . . < nk ¤ n. Ist k = 0, so ist A die Nullmatrix. Ist k ≥ 1, so ist fur 1 ¤ j ¤ k die
¨
Komponente aj,nj die erste von Null verschiedene Komponente der j-ten Zeile.
Fur j > k ist die j-te Zeile der Matrix A der Nullvektor. Es k¨nnen jedoch o
¨
durchaus einzelne oder alle der bj fur j > k verschieden von 0 sein.
¨
Wir k¨nnen die Matrix noch etwas vereinfachen, was die nachfolgende Dis-
o
kussion erleichtert: Durch Multiplikation von Zeilen mit K¨rperelementen = 0
o
(Operation Z2) k¨nnen wir erreichen, dass fur 1 ¤ j ¤ k die Komponenten
o ¨
aj,nj = 1 sind. Ferner k¨nnen wir durch nochmalige Anwendung von Z3 errei-

<<

. 8
( 60 .)



>>