<<

. 10
( 63 .)



>>

∈ Lθ , aber ∈ Lθ , falls x2 = 0 .
(1) , /
0 0 x2
r
r ∈ IK
Also Lθ = .
0

0
gilt Lb = … .
(2) Fur b =
¨
1

1 r 0
r ∈ IK ∈ Lb .
(3) Fur b = gilt Lb = , da
¨
0 1 1
2

2.4 Das Eliminationsverfahren
Die L¨sung linearer Gleichungssysteme ist zentral in der numerischen Mathematik und
o
in weiterem Sinne auch in der angewandten Mathematik. Die konstruktive L¨sungsidee
o
besteht darin, ein gegebenes System durch ¨quivalente Umformungen, d.h. durch Umfor-
a
mungen, die die L¨sungsmenge nicht ¨ndern, in eine Form zu bringen, aus der man die
o a
L¨sung dann ablesen kann. Eine solche erstrebenswerte Form ist eine Matrix von oberer
o
Dreiecksgestalt:
Baumeister: Lineare Algebra I / Stand: August 1996 35


De¬nition 2.10
(a) Eine Matrix A = (aij )i=1 (1 )m , j =1 (1 )n heißt von oberer Dreiecksgestalt,
wenn
aij = 0 , falls i > j,
gilt.

(b) Eine Matrix A = (aij )i=1 (1 )m , j =1 (1 )n heißt Diagonalmatrix, wenn gilt:

aij = 0 , falls i = j .
2
In der “einfachsten“ Situation m = n = 2 hat ein Gleichungssystem mit einer Systemma-
trix von oberer Dreiecksgestalt folgende Form:

a11 a12 x1 b1
= .
0 a22 x2 b2

Nun ist klar: Ist a11a22 = 0, so l¨st man so:
o

x2 := a’1 b2 , x1 := (b1 ’ a’1a12b2 )a’1 .
22 22 11

Dies ist die 2 — 2 “ Version eines Algorithmus, der Ruckw¨rtssubstitution genannt
a
¨
wird. In der Einfuhrung haben wir in (2.2),(2.4) ein solches System vorgefunden.
¨

De¬nition 2.11
Eine Matrix A = (aij )i=1 (1 )n , j =1 (1 )n von oberer Dreiecksgestalt heißt regular, falls
¨

a11 · · · ann = 0 ,

anderenfalls singul¨r.
a
2

Beachte, daß eine Diagonalmatrix eine Matrix von oberer Dreiecksgestalt ist und damit
auch Regularit¨t und Singularit¨t fur diesen Typ von Matrizen erkl¨rt ist. Das Produkt
a a¨ a
a11 · · · ann ist im Spezialfall n = 2, a21 = 0 gerade die im Abschnitt 2.1 eingefuhrte Große
¨ ¨
∆.

Die Bedeutung des Begri¬s “regul¨r“, der sp¨ter eine Erweiterung erfahren wird, liegt bei
a a
Systemen mit einer Systemmatrix von oberer Dreiecksgestalt darin, daß die eindeutige
L¨sbarkeit durch diese Eigenschaft gesichert wird (L¨sbarkeit alleine kann auch ohne
o o
diese Bedingung vorliegen). Dies ist eine Konsequenz aus dem folgenden Algorithmus, der
die L¨sung eines Gleichungssystems mit einer Systemmatrix von oberer Dreiecksgestalt
o
beschreibt.
Baumeister: Lineare Algebra I / Stand: August 1996 36


Algorithmus “Ruckw¨rtsubstitution“:
a
¨

Regul¨re Matrix A ∈ IK n,n von oberer Dreicksgestalt.
EIN a
SCHRITT 1 i := n .
SCHRITT 2 xi := bi .
SCHRITT 3 F ur j = (i + 1)(1)n xi := xi ’ aij xj .
¨
SCHRITT 4 xi := xi /aii .
SCHRITT 5 Ist i > 1, gehe mit i := i ’ 1 zu SCHRITT 2, sonst zu AUS .
AUS Losungsvektor x = (x1 , . . . , xn ) .
¨


(Den L¨sungsvektor haben wir in AUS aus Platz“¨konomischen Grunden als n-Tupel und
o o ¨
nicht als Spaltenvektor geschrieben).

Es ist nun erstrebenswert, eine beliebige Matrix auf eine obere Dreiecksgestalt zu trans-
formieren, sodaß die sich der L¨sungsraum nicht ver¨ndert. Dieses leistet das Elimina-
o a
tionsverfahren, das nach Gauß benannt ist, das allerdings fur konkrete F¨lle schon sehr
a
¨
viel fruher Anwendung fand.
¨
¨
Aus dem 2. Jahrhundert n. Chr. gibt es eine Ubersetzung der “Neun Bucher uber die Kunst der
¨ ¨
Mathematik“, die wohl im 2. Jahrhundert v. Chr. aufgeschrieben wurden; das Methodenmaterial
kann aber durchaus ¨lter sein. Diese Bucher sind eine Art Lehrbuch fur Verwaltungsbeamte. Im
a ¨ ¨
VIII. Buch ist folgende Aufgabe enthalten:
Aus drei Garben einer guten Ernte, 2 Garben einer mittelmaßigen Ernte, und 1 Garbe einer schlech-
¨
ten Ernte erh¨lt man den Ertrag von 39 Tou. Aus 2 Garben einer guten Ernte, 3 Garben einer
a
mittelm¨ßigen Ernte und 1 Garbe einer schlechten Ernte erh¨lt man 34 Tou. Aus 1 Garbe guter
a a
Ernte, 2 Garben mittelm¨ßiger Ernte und 3 Garben schlechter Ernte erh¨lt man 26 Tou. Wieviel
a a
ist der Ertrag einer Garbe?
Diese Aufgabe wurde in eine rechteckige Tabelle gebracht (Matrixschema !) und nach Regeln
(“Immer multipliziere mit der Garbenzahl der guten Ernte mit der . . . ), die den Eliminations-

chritten (siehe unten) entsprechen, auf eine Dreieckstabelle gebracht. Dabei k¨nnen auch negative
o
Zahlen “ sie treten hier wohl erstmals in der Geschichte der Mathematik auf “ auftreten, fur den
¨
Umgang dafur wurden Regeln angegeben. Wir k¨nnen das resultierende rechteckige Schema nun
o
¨
als lineares Gleichungssystem mit einer Systemmatrix von oberer Dreiecksgestalt lesen:
« «  « 
321 x1 39
 0 5 1   x2  =  24  .
0 0 36 x3 39

Nun wird mit Ruckw¨rtssubstitution gel¨st.
a o
¨
Die Idee der Elimination wurde auch studiert von Diophantos aus Alexandrien (um 250 n. Chr.).


Welche Manipulationsschritte “ wir nennen sie nun elementare Umformungen “ sind
es, die wir auf ein lineares Gleichungssystem anwenden durfen, ohne die L¨sungsmenge
o
¨
zu ver¨ndern? Es sind dies:
a
Baumeister: Lineare Algebra I / Stand: August 1996 37


Zeilenvertauschung: Zwei Gleichungen vertauschen, was einer Zeilenvertau-
schung in der Systemmatrix und der rechten Seite bedeu-
tet.
Spaltenvertauschungen: Vertauschung von zwei Unbekannten, was einer Spalten-
vertauschung in der Systemmatrix entspricht; man hat sich
dies zu merken!
Multiplikation: Eine Gleichung wird mit einem Skalar r = 0 multipliziert.
Dies entspricht der Multiplikation einer Zeile in der Sy-
stemmatrix und in der rechten Seite.
Eine Gleichung wird zu einer anderen Gleichung addiert.
Addition:
Dies entspricht einer Addition einer Zeile in der System-
matrix und in der rechten Seite.
Kein Zweifel, nichts ¨ndert sich an der L¨sungsmenge, da man jeden Schritt wieder
a o
ruckg¨ngig machen kann. Man beachte, daß man, bis auf die Spaltenvertauschung, die
¨a
Manipulationen stets auf die ger¨nderte Matrix (A|b) anzuwenden hat (A Systemma-
a
trix, b rechte Seite). In unserer Einfuhrung in Abschnitt 2.1 haben wir diese Schritte be-
¨
reits kennengelernt. Wir geben dieser elementaren Formulierung eine Matrixformulierung.


Sei eine (m — n) “ Matrix A0 gegeben. Wir konstruieren unter Verwendung der obigen
Manipulationsschritte eine Folge A0 , A1, . . . in folgender Weise:
• Sei Ak gefunden und sei Ak von der Form
BC
Ak = ,
˜D

wobei B ∈ IK k,k eine regul¨re Matrix von oberer Dreiecksgestalt ist.
a
• Ist D die Nullmatrix, k¨nnen wir abbrechen.
o
• Sonst wird Ak+1 konstruiert nach folgendem Vorgehen:
—¦ Wahle in D = (dij )i=1 (1 )m’k , j =1 (1 )n’k ein Element dij = 0 . Ein solches Ele-
¨
ment wird ein Pivotelement (Ankerelement) genannt.
—¦ Bringe dieses Pivotelement durch Spalten“ und Zeilenvertauschung in die Po-
sition (1,1) von D, d.h. wir k¨nnen o.E. nun annehmen: d11 = 0 . Beachte:
o
Zeilenvertauschungen und Addition von Zeilen sind an der ger¨nderten Matrix
a
vorzunehmen, Spaltenvertauschungen hat man sich zu merken.
—¦ Addiere geeignete Vielfache der ersten Zeile von D zu den darunterliegenden
Zeilen mit dem Ziel, daß
d21 = · · · = d(m’k)1 = 0
erreicht wird.
Dies waren elementare Umformungen und es ergibt sich die Matrix Ak+1 . Das Vor-
gehen ist damit (induktiv) beschrieben.
Baumeister: Lineare Algebra I / Stand: August 1996 38


Wir fassen dies nun algorithmisch zusammen.

Algorithmus “Elimination nach Gauß“:

Systemmatrix A ∈ IK m,n , rechte Seite b ∈ IK m .
EIN
Zu ¬nden ist x ∈ IK n,1 mit Ax = b .
SCHRITT 1 A0 := (A|b) ∈ IK m,n+1 , D := A , d := b , k := 0 .
SCHRITT 2 Sei Ak in der Form
BCc
˜Dd
mit B ∈ IK k,k , c ∈ IK k,1 , d ∈ IK m’k,1 gegeben, wobei
k = 0 bedeutet, daß Ak von der Form (D|d) ist.
SCHRITT 3 Ist D die Nullmatrix, setze r := k und gehe zu AUS .
SCHRITT 4 Finde in D ein Pivotelement dij = 0 .
SCHRITT 5 Falls notig, vertausche in (D|d) Zeile i mit Zeile 1 und in D
¨
Spalte j mit Spalte 1 mit dem Ziel, daß in der resultierenden
Matrix (D |d ) das Element d11 = 0 ist. Sei die Matrix (D |d )
nach eventueller Vertauschung wieder mit (D|d) benannt.

SCHRITT 6 Mache die erste Spalte der Matrix (D|d) durch elementare
Umformungen, angewendet auf die Matrix (D|d), zum Vektor
e1 . Daraus resultiert eine Matrix Ak+1 von der Form
BCc
˜Dd
mit D ∈ IK n’k’1,m’k’1 .
Setze k := k + 1 und gehe, falls k < min{m, n}, zu SCHRITT 3,
sonst setze r := k und gehe zu AUS .
¨
AUS Aquivalentes Gleichungssystem
BC x1 c
= ,
˜˜ x2 d
wobei B ∈ IK r,r eine regulare Matrix von oberer Dreiecksgestalt
¨
ist; in der Diagonale stehen nur Einsen.
Die Interpretation dieser Form im Falle r = m oder r = n ist
C
o¬ensichtlich: Es fehlt die Zeile (˜ ˜) oder die Spalte .
˜
Beachte: Dieses Gleichungssystem ist genau dann l¨sbar, wenn
o
d = θ . Es kann dann mit dem Algorithmus
“Ruckw¨rtssubstitution“ gel¨st werden.
a o
¨

<<

. 10
( 63 .)



>>