<<

. 11
( 63 .)



>>

Baumeister: Lineare Algebra I / Stand: August 1996 39


Satz 2.12
Betrachte das lineare Gleichungssystem

Ax = b (2.10)

mit A ∈ IK m,n , b ∈ IK m .
Das Gaußsche Eliminationsverfahren liefert ein Gleichungssystem

Ax=b (2.11)

mit
BC c
∈ IK m,n , b = ∈ IK m,1 ,
A=
˜˜ d
wobei B ∈ IK r,r , r ¤ min{m, n}, eine regul¨re Matrix von oberer Dreiecksgestalt ist.
a
Zus¨tzlich gilt:
a

(a) Das Gleichungssystem (2.10) ist losbar genau dann, wenn d = θ .
¨
(b) Ist das System (2.10) l¨sbar, so erh¨lt man die L¨sungskomponenten x1 , . . . , xr
o a o
in eindeutiger Weise (R¨ckw¨rtssubstitution) als L¨sung z von
u a o

Bz = c (2.12)

durch xi := zi , 1 ¤ i ¤ r; die restlichen Komponenten xr+1 , . . . , xn sind frei
w¨hlbar.
a
Beweis:
Die Aussagen folgen aus der Entwicklung der Algorithmen “Ruckw¨rtssubstitution“ und
a
¨
“Eliminationsverfahren nach Gauß“. Daß xr+1 , . . . , xn frei w¨hlbar sind, folgt aus der
a
Form des Systems (2.11).


Folgerung 2.13
Ist das System (2.10) quadratisch, d.h. ist m = n, so tritt genau eine der folgenden
Alternativen ein:

(i) Das System (2.10) ist eindeutig losbar.
¨
(ii) Das zugehorige homogene System ( b = θ) hat nichttriviale Losungen.
¨ ¨
Beweis:
Es tritt genau eine der Alternativen r = n oder r < n ein.


Folgerung 2.14
Ist das System (2.10) unterbestimmt, d.h. ist m < n, so hat das zugeh¨rige homogene
o
System ( b = θ) nichttriviale L¨sungen.
o
Beweis:
Baumeister: Lineare Algebra I / Stand: August 1996 40


Es ist notwendigerweise r ¤ m < n. Nach (b) in Satz 2.12 sind die Komponenten
xr+1 , . . . , xn frei w¨hlbar.
a


Bemerkung 2.15
In obigem Satz spielt die Zahl r eine nicht unwesentliche Rolle. Es wird hier noch nicht
gekl¨rt, ob diese Zahl nur von der gegebenen Systemmatrix A oder auch vom gew¨hlten
a a
L¨sungsverfahren abh¨ngt. Sp¨ter wird sich ergeben, daß r wirklich vom Verfahren un-
o a a
2
abh¨ngig ist; sie wird dann der Rang der Matrix A genannt.
a


Beispiel 2.16
Betrachte das Gleichungssystem aus dem VIII. Buch der “Neun Bucher uber die Kunst
¨ ¨
der Mathematik“: « «  « 
3 21 x1 39
¬
3 1   x2  =  34 · .
·¬ · ¬
2 
1 23 x3 26
Der Algorithmus “Elimination nach Gauß“ wird folgendermaßen durchlaufen:
«  « 
3 2 1 39 321
¬ · ¬ ·
A0 =  2 3 1 34  , D =  2 3 1  .
SCHRITT 1
1 2 3 26 123
SCHRITT 4 Pivotelement d11 = 3 .
« 
1 2/3 1/3 13
A1 =  0 5/3 1/3 8 · .
¬

SCHRITT 6
0 4/3 8/3 13
SCHRITT 4 Pivotelement dij = 5/3 .
« 
1 2/3 1/3 13
¬
1/5 24/5 · .
A2 =  0 1 
SCHRITT 6
0 0 12/5 33/5
« 
3 2 1 39
¬ ·
 0 5 1 24  .
AUS
0 0 12 33
Mit Ruckw¨rtsubstitution erhalten wir als Losung x = (x1, x2 , x3) :
a
¨ ¨

x3 = 11/4 , x2 = 17/4 , x1 = 37/4

2
Beachte, daß jeweils viele Pivotelemente zur Verfugung stehen.
¨
Baumeister: Lineare Algebra I / Stand: August 1996 41


Bemerkung 2.17
Nach Durchlauf der Gaußschen Elimination kann man durch elementare Umformungen
die erreichte Form
BC x1 c
= .
˜˜ x2 d
in die Form
EC x1 c
=
˜˜ x2 d
bringen; hierbei ist nun E eine (r — r) “ Einheitsmatrix. Das resultierende Verfahren
wird das Gauß “ Jordan Eliminationsverfahren genannt.Die Ruckwartssubstitution
¨ ¨
2
gestaltet sich hier sehr einfach.


Bemerkung 2.18
Verschiedenen Varianten eines Eliminationsverfahrens kann man nach der Anzahl der
ben¨tigten Rechenoperationen bewerten. Dabei ist es erlaubt, Additionen und Subtrak-
o
tionen bzw. Multiplikationen und Divisionen gleichsetzen, da sie etwa gleichgroßen Re-
chenaufwand erfordern.
Bei der Gauß “ Elimination fallen bei einer quadratischen n — n “ Matrix h¨chstens
o
n(n + 1)(2n + 1)
n2 + (n ’ 1)2 + · · · + 12 = Additionen
6
und
n(n + 1)(2n + 1) n(n + 1)
n(n ’ 1) + (n ’ 1)(n ’ 2) + · · · + 1 = ’ Multiplikationen
6 2
an. Bei der anschließenden Ruckwartssubstitution fallen dann
¨ ¨
n(n ’ 1)
n ’1 + n ’ 2+ ··· + 1 = Additionen
2
und
n(n ’ 1)
n + n ’ 1+ ··· + 1 = Multiplikationen
2
an. Der Aufwand w¨chst asymptotisch also wie n3 /3 .
a
2
Beim Gauß “ Jordan Eliminationsverfahren ermittelt man denselben Rechenaufwand.

In der Praxis wird die L¨sung eines (großen) linearen Gleichungssystems auf einem Com-
o
puter durchgefuhrt. Dieser hat nur endlich viele (Dezimal-)Stellen fur die Rechnung zur
¨ ¨
Verfugung, auf die jeweils durch eine Variante einer “Rundung“ die Zahlen reduziert wer-
¨
den. Berucksichtigt man dies, so kommt zu den bisher angesprochenen Fragen
¨

Existenz (einer L¨sung), Eindeutigkeit (einer L¨sung)
o o

die Frage der
Stabilitat (der Berechnung gegenuber Rundung)
¨ ¨
Baumeister: Lineare Algebra I / Stand: August 1996 42

¨
hinzu. Die Frage der Stabilit¨t ist wesentlicher Teil von Uberlegungen, die in der numeri-
a
schen Mathematik hinsichtlich der numerischen L¨sung von linearen Gleichungssystemen
o
(auch unabh¨ngig vom L¨sungsverfahren) angestellt werden. Die Wahl eines Pivotele-
a o
ments spielt eine wesentliche Rolle bei der Betrachtung. Im Abschnitt uber euklidische
¨
Vektorr¨ume streifen wir die Werkzeuge fur die Behandlung dieser Frage, n¨tig ist insbe-
a o
¨
sondere etwas Topologie (Stetigkeit).
Sind bei einem Gleichungssystem alle drei Fragen positiv beantwortet, nennt man das
Problem gut konditioniert. Diese Begri¬sbildung ist eine Version des von J. Hadamard
(1865 “ 1963) im Zusammenhang mit partiellen Di¬erentialgleichungen eingefuhrten Be-
¨
gri¬s korrekt gestellt oder gut gestellt. Nach Hadamard heißt ein Problem korrekt
gestellt, wenn folgende Aussagen veri¬ziert werden k¨nnen:
o

Existenz: Das Problem hat eine Losung.
¨
Eindeutigkeit: Das Problem hat hochstens eine Losung.
¨ ¨
Stabilitat: Die Losung h¨ngt stetig von den Daten des Problems ab.
a
¨ ¨
Dem widerspricht nicht, eine Theorie uber die Behandlung von schlechtgestellten Proble-
¨
men zu entwickeln, d.h. Probleme zu untersuchen, bei denen mindestens eine der oben
angefuhrten Eigenschaften nicht gegeben ist; in der Praxis ist die Stabilit¨t die Proble-
a
¨
matik. Ziel einer solchen Theorie ist, herauszu¬nden, welche “physikalisch“ begrundbaren
¨
Eigenschaften einem mathematischen Modell hinzugefugt werden mussen, damit ein gut-
¨ ¨
gestelltes Problem resultiert (Regularisierung).


2.5 Geometrische Interpretation
Lineare Gleichungssysteme mit sehr vielen Unbekannten, insbesondere mit mehr als drei
Unbekannten, sind sehr interessant. Es lassen sich ohne Muhe viele Anwendungen ¬nden,
¨
bei denen die Anzahl der Unbekannten mehrere Hundert betr¨gt. Die Betrachtungen der
a
zugeh¨rigen L¨sungsmengen spielen sich dann in einem Raum IK n ab mit Dimension n,
o o
die sehr viel gr¨ßer als drei ist. Eine geometrische Interpretation von linearen Gleichungs-
o
systemen setzt dann voraus, daß es eine Geometrie in R¨umen IK n , n > 3, “gibt“.
a

Geometrie ist die Besch¨ftigung mit Objekten wie Geraden, Kreise, Ebenen, Kugeln . . ..
a
Die Grundidee einer Geometrie in IK n besteht darin, mit den Punkten x = (x1, . . . , xn )
geometrische Objekte wie Gerade, Ebenen, Kugeln, . . . in IK n zu beschreiben. Diese Grun-
didee geht zuruck auf R. Descartes (1596 “ 1650) “ im cartesischen Koordinatensystem
¨
lebt der lateinische Name Cartesius fur Descartes fort. Die Einsicht, daß man Geome-
¨
n
trie in IK , n > 3, treiben kann und sollte, wurde vertieft von A. Cayley (1821 “ 1895),
wenngleich mit Mißtrauen und Unglauben aufgenommen:
Man kann mit dem 4-dimensionalen Raum umgehen “sans recourir a aucune notion m´taphysique
` e
` l™´gard de la possibilit´ de l™espace a quatre dimensions“.
ae e `
A.C., 1846
Nahezu gleichzeitig mit A. Cayley schuf H. Grassmann (1809 “ 1877) seine “lineale Aus-
dehnungslehre“, ein Werk, dessen Tiefe zun¨chst nicht erkannt wurde. Darin wird die
a
Baumeister: Lineare Algebra I / Stand: August 1996 43

<<

. 11
( 63 .)



>>