Lineare Algebra für die Informatik || Lineare Gleichungssysteme

Lineare Gleichungssysteme 43

3 Lineare Gleichungssysteme

Lineare Gleichungssysteme spielen in vielen Anwendungen eine wichtigeRolle, insbesondere auch bei der fehlertoleranten Codierung, die wir im Ka-pitel 5 betrachten werden. Deshalb beschaftigen wir uns in diesem Kapitelmit der Losbarkeit sowie mit einem Losungsverfahren fur solche Systeme.Wir werden sehen, dass wir dabei Kenntnisse uber Vektorraume und Ma-trizen verwenden konnen.

Nach dem Durcharbeiten dieses Kapitels sollten Sie Lernziele

• Kriterien kennen, die die Losbarkeit eines linearen Gleichungssystemsbestimmen,

• das Gausssche Eliminationsverfahren zur Losung von losbaren linearenGleichungssystemen anwenden konnen,

• wissen, dass ein lineares Gleichungssystem eine lineare Abbildung dar-stellt und dass die Losungsmenge des entsprechenden homogenen Glei-chungssystems genau der Kern dieser linearen Abbildung ist,

• erlautern konnen, dass sich die Losungsmenge eines linearen Gleichungs-systems als additive Nebenklasse dieses Kerns und einer speziellenLosung des inhomogenen Systems ergibt.

3.1 Grundlegende Definitionen

Definition 3.1 Es sei m, n ∈ N. Ein System gmnmnmn(x) von m linearen Glei- Homogenes,inhomogenes,linearesGleichungssystem

chungen mit n Unbekannten x1, . . . , xn uber einem Korper K ist gegebendurch:

a11x1 + a12x2 + . . . + a1nxn = b1

a21x1 + a22x2 + . . . + a2nxn = b2...

......

......

......

......

am1x1 + am2x2 + . . . + amnxn = bm

Dabei heißen die aij ∈ K, 1 ≤ i ≤ m, 1 ≤ j ≤ n, Koeffizienten des Glei-chungssystems.

b = (b1, . . . , bm) ∈ Km heißt Ergebnisvektor oder Konstantenvektor vongmnmnmn(x).

Ist bi = 0, 1 ≤ i ≤ m, dann heißt gmnmnmn(x) homogen, sonst inhomogen.

Fur x = (x1, . . . , xn) sei GLKmn [x] die Menge aller linearen (m × n)-

Gleichungssysteme uber dem Korper K.

K.-U. Witt, Lineare Algebra für die Informatik, DOI 10.1007/978-3-658-00189-6_3, © Springer Fachmedien Wiesbaden 2013

44 Losung linearer Gleichungssysteme

Die Matrix

A = (aijijij) 1≤i≤m1≤j≤n

=

⎛⎜⎜⎜⎝

a11 a12 . . . a1n

a21 a22 . . . a2n...

......

...am1 am2 . . . amn

⎞⎟⎟⎟⎠

heißt Koeffizientenmatrix von gmnmnmn(x), und die MatrixKoeffizienten-matrix

(A,b) =

⎛⎜⎜⎜⎝

a11 a12 . . . a1n b1

a21 a22 . . . a2n b2...

......

......

am1 am2 . . . amn bm

⎞⎟⎟⎟⎠

heißt erweiterte Koeffizientenmatrix von gmnmnmn(x). �ErweiterteKoeffizienten-matrix Wenn wir b = (b1, . . . , bm) ∈ Km und x = (x1, . . . , xn) als (1×m)- bzw. als

(1×n)-Matrizen auffassen, lasst sich ein (m×n)-Gleichungssystem gmnmnmn(x)auch als Matrizenprodukt darstellen:

A · xT = bT

Da es sich bei x und b um Vektoren und nicht um”echte Matrizen“ handelt,

schreibt man in der Regel nur:

A · x = b

Das heißt: gmnmnmn(x) ist durch die Koeffizientenmatrix A und den Ergebnisvek-tor b eindeutig bestimmt, weshalb wir anstelle von gmnmnmn(x) oder A · x = bauch (A,b)mnmnmn schreiben konnen, und falls auf die Angabe von m und nverzichtet werden kann, schreiben wir (A,b) anstelle von (A,b)mnmnmn.

3.2 Losung linearer Gleichungssysteme

Definition 3.2 Ein lineares Gleichungssystem (A,b) ∈ GLKmn [x] heißt

losbar, falls es einen Vektor �� = (�1, . . . , �n) ∈ Kn gibt, so dass A · �� = bgilt. �� heißt Losung von (A,b) in K.

Die MengeLosungs-menge L(A,b) = {�� ∈ Kn | A · �� = b }

aller Losungen von (A,b) in K heißt Losungsmenge von (A,b) in K. Gibtes keine Losung, d.h. ist L(A,b) = ∅, dann heißt (A,b) nicht losbar in K.

Zwei Gleichungssysteme (A1,b1), (A2,b2) ∈ GLKmn [x] heißen aquivalent

genau dann, wenn sie dieselben Losungsmengen besitzen, d.h. wennL(A1,b1) = L(A2,b2) gilt. Schreibweise: (A1,b1) ≡ (A2,b2). �


Ohne uns schon mit der Losbarkeit von Gleichungssystemen oder mit Lo-sungsverfahren fur Gleichungssysteme beschaftigt zu haben, konnen wir fol-gende Aussagen uber Losbarkeit und Losungsmengen treffen.

Satz 3.1 a) Jedes homogene Gleichungssystem (A,0) ist losbar.

b) Sind �1�1�1, �2�2�2 ∈ L(A,0) sowie α1, α2 ∈ K, dann gilt α1�1�1�1 + α2�2�2�2 ∈ L(A,0).

c) L(A,0) ist ein Vektorraum uber K, genauer ein Unterraum von Kn. LosungsraumL(A,0) heißt Losungsraum des homogenen Gleichungssystems (A,0).

Beweis a) Es gilt 0 = (0, . . . , 0) ∈ L(A,0), da A · 0 = 0 ist.

b) Da �1�1�1, �2�2�2 Losungen von (A,0) sind, gilt A ·�1�1�1 = 0 und A ·�2�2�2 = 0. Darausfolgt

A · (α1�1�1�1 + α2�2�2�2) = α1 · A · �1�1�1 + α2 · A · �2�2�2 = α2 · 0 + α2 · 0 = 0

d.h. α1�1�1�1 + α2�2�2�2 ist Losung von (A,0).

c) folgt unmittelbar aus b) mithilfe von Satz 1.2. �

3.2.1 Zeilenreduktion

Definition 3.3 Eine Matrix A ∈ MKmn, die keine Nullspalte enthalt, die

in der in der Form⎛⎜⎜⎜⎜⎜⎝

1 x . . . x 0 x . . . x 0 x . . . x 01 x . . . x 0 x . . . x 0

1 x . . . x 0 . . .1

. . .

⎞⎟⎟⎟⎟⎟⎠ (3.1)

vorliegt, wobei x . . . x fur irgendwelche Elemente aus K stehen, und der freiePlatz vollstandig mit Nullen belegt ist, heißt Matrix in Zeilenstufenform.�

Beispiel 3.1 Die folgenden beiden Matrizen⎛⎝1 7 0 2

0 0 1 20 0 0 0

⎞⎠ und

⎛⎝1 0 −1 0 46

0 1 2 0 −800 0 0 1 29

⎞⎠

befinden sich in Zeilenstufenform. �

Fur eine Matrix in Zeilenstufenform gelten folgende drei Eigenschaften:

(a) Das erste von Null verschiedene Element einer Zeile ist 1. Dieses Element PivotPivotelementheißt Pivot oder Pivotelement

(b) Das Pivotelement in Zeile i + 1 steht rechts von dem in Zeile i.

(c) Alle Spaltenelemente oberhalb eines Pivots sind Null.


Wenn man bei dem Verfahren aus dem Beweis von Satz 2.6 nur Zeilenre-duktionen und keine Spaltenreduktionen zulasst, ist offensichtlich, dass sichjede Matrix A ∈ MK

mn, die keine Nullspalte enthalt, in Zeilenstufenformumwandeln lasst. Man sucht in der ersten Spalte ein Element ungleich Null(naturlich nur, wenn das erste Element gleich Null ist). Sei dieses Elementin der Zeile i, dann tauscht man mithilfe der Operation C(1, i) die erste mitdieser Zeile. Falls nun a11 = 1 ist, dividiert man die erste Zeile durch a11

mithilfe der entsprechenden Operation M(1, a−111 ). Jetzt werden die Opera-

tionen S(i, 1,−ai1), 2 ≤ i ≤ m, durchgefuhrt, wodurch alle Elemente inder ersten Spalte unter der 1 zu Null gemacht werden. Wir erhalten so eineMatrix der Form⎛

⎜⎜⎜⎝1 x . . . x x . . . x0 0 . . . 0 x . . . x...

......

......

0 0 . . . 0 x . . . x

⎞⎟⎟⎟⎠ =

⎛⎜⎜⎝

1 x . . . x x . . . x

0 B

⎞⎟⎟⎠

Auf die Matrix B wird nun rekursiv das oben beschriebene Verfahren an-gewendet. Dabei mussen, falls in der Spalte j uber einer 1 in Zeile i nochElemente arj = 0 stehen, fur die entsprechenden Zeilen r ∈ { 1, . . . , i − 1 }die Operationen S(r, i,−arj) durchgefuhrt werden, damit uber dem Pivotaij = 1 nur Nullen stehen.

Das Verfahren endet, falls B eine Nullmatrix ist oder falls B leer gewordenist. Letztendlich erreicht man eine Matrix in Zeilenstufenform (3.1).

Auf der Basis von Satz 2.6 sowie der Folgerungen 2.7 und 2.8 kann manuberlegen, dass folgende Folgerungen gelten.

Folgerung 3.1 a) Die Anzahl r ≤ m der von Null verschiedenen Zeilender Zeilenstufenform der Matrix A ∈ MK

mn ist gleich dem Rang von A.

b) Sei A ∈ MKm eine quadratische Matrix in Zeilenstufenform, dann ist

entweder A = E oder die letzte Zeile von A ist eine Nullzeile. �

Des Weiteren kann man zeigen, dass die Zeilenstufenform einer Matrix Aunabhangig von der Folge der Zeilenreduktionen ist, die auf A angewendetwerden; die Zeilenstufenform zu A ist also eindeutig.

✍ Ubungsaufgaben

3.1 Transformieren Sie mithilfe von Zeilenreduktionen die Matrix

A =

⎛⎝2 4 6 8 4

1 3 5 7 99 8 7 8 6

⎞⎠ ∈ MR

3,5

schrittweise in Zeilenstufenform! �


3.2.2 Gausssches Eliminationsverfahren

Wir bezeichnen im Folgenden fur ein lineares Gleichungssystem (A,b) mitA ∈ MK

mn und b ∈ Km mit M = (A|b) ∈ MKmn+1 die erweiterte Koeffi-

zientenmatrix von (A,b). Fur die Anwendung einer Folge L von Zeilenre-duktionen auf M gilt dann LM = (LA|Lb).

Wir verwenden nun die Methode der Zeilenreduktion zur Losung von linea-ren Gleichungssystemen. Dieses Losungsverfahren fur lineare Gleichungssys-teme heißt Gausssches Eliminationsverfahren.4 Basis dafur ist der folgendeSatz, der besagt, dass Zeilenreduktionen die Losungsmenge eines linearenGleichungssystems invariant lassen.

Satz 3.2 Fur ein lineares Gleichungssystem M = (A|b) und eine Fol-ge L von Zeilenreduktionen gilt: L(M) = L(LM), d.h. M und LM sindaquivalent.

Beweis Es sei L = Lkkk . . .L111. Da wegen Satz 2.4 die ElementaroperationenLi, 1 ≤ i ≤ k, invertierbar sind, ist auch die Zeilenreduktion L invertierbar,und es ist L−1 = L−1

111 . . .L−1kkk ebenfalls eine Zeilenreduktion (siehe Folgerung

2.6).

Sei nun �� ∈ Kn eine Losung von M, d.h. es ist A · �� = b. Es folgt L ·A · �� = L · b, d.h. �� ist auch eine Losung von LM = (LA|Lb). Es folgtL(M) ⊆ L(LM)).

Sei nun �� ∈ Kn eine Losung von LM = (LA|Lb), d.h. es ist L ·A ·�� = L ·b.Durch Linksmultiplikation dieser Gleichung mit L−1 erhalten wir A ·�� = b,d.h. �� ist eine Losung von (A,b). Damit folgt L(LM)) ⊆ L(M).

Insgesamt folgt L(M) = L(LM)), womit die Behauptung gezeigt ist. �

Folgerung 3.2 Es sei M′′′ = (A′′′|b′′′) die Zeilenstufenform zu der erweiter-ten Koeffizientenmatrix M = (A|b) des linearen Gleichungssystems (A,b),dann gilt L(M′′′) = L(M), d.h. eine erweiterte Koeffizientenmatrix und ihreZeilenstufenform sind aquivalent. �

Auf der Basis dieser Folgerung ergibt sich folgendes Verfahren, das so ge- GaussschesElimininations-verfahren

nannte Gausssche Eliminationsverfahren, zur Losung linearer Gleichungs-systeme (A,b) ∈ GLK

mn [x]:

(1) Berechne (mit dem im letzten Abschnitt beschriebenen Verfahren) zurerweiterten Koeffizientenmatrix (A|b) die Zeilenstufenform, die wirebenfalls mit (A|b) bezeichnen wollen.

4 Carl Friedrich Gauss (1777 - 1855), deutscher Mathematiker, Astronom und Physi-ker, zahlt nach wie vor zu den großten Mathematikern aller Zeiten, der in allen dreiGebieten vielseitig tatig war und fundamentale Beitrage lieferte, wobei er bei vie-len seiner Erkenntnisse auch deren praktische Anwendungsmoglichkeiten im Augehatte.


(2) Es ist L(A,b) = ∅, d.h. das Gleichungssystem hat keine Losung, genaudann, wenn in der letzten Spalte b ein Pivot steht. In diesem Fall istrang(A|b) > rang(A).

(3) Ist rang(A) = rang(A|b) = n, dann hat die Zeilenstufenform von (A|b)die Gestalt ⎛

⎜⎜⎜⎝1 b1

1 b2

. . ....

1 bn

⎞⎟⎟⎟⎠

woraus sich unmittelbar die eindeutige Losung �� = (b1, b2, . . . , bn) able-sen lasst.

(4) Ist rang(A) = rang(A|b) < n, dann ist die Losung mehrdeutig.

Es sei P ⊆ { 1, . . . , n } die Menge der Indizes der Pivotspalten. Es ist|P | = rang(A).

Die Losungsmenge erhalt man wie folgt: Fur die Unbekannten xi mitSpezielleLosung i ∈ P , d.h. fur die Unbekannten, in deren Spalte kein Pivot steht, wahlt

man einen beliebigen Wert xi = λi ∈ K als spezielle Losung.

Die Losungen der Unbekannten xk mit k ∈ P , welche durch die Pivot-spalten gegeben sind, ergeben sich dann durch

xk = bk −⎛⎝∑

j∈P

akjλj

⎞⎠

Beispiel 3.2 a) Das Gleichungssystem

x1 − x3 = 5x2 + x3 = 0

3x1 − 3x3 = 10

hat die erweiterte Koeffizientenmatrix

(A|b) =

⎛⎝1 0 −1 5

0 1 1 03 0 −3 10

⎞⎠

Durch Anwendung der Elementaroperationen S(3, 1,−3), M(3,−1

5

)und

S(1, 3,−5) erhalt man die Zeilenstufenform

(A|b) =

⎛⎝1 0 −1 0

0 1 1 00 0 0 1

⎞⎠

In der b-Spalte steht ein Pivot (es ist rang(A|b) = 3 > 2 rang(A)),also besitzt das Gleichungssystem keine Losung.

=


b) Das Gleichungssystem

x1 + 2x2 + 3x3 = 142x1 + 3x2 + x3 = 115x1 − x2 + 2x3 = 9


(A|b) =

⎛⎝1 2 3 14

2 3 1 115 −1 2 9

⎞⎠

Durch Anwendung der Elementaroperationen S(2, 1,−2), S(3, 1,−5),M(2,−1), S(3, 2, 11), S(1, 2,−2), M

(3, 1

42

), S(2, 3,−5) und S(1, 3, 7) erhalt

man die Zeilenstufenform

(A|b) =

⎛⎝1 0 0 1

0 1 0 20 0 1 3

⎞⎠

woraus unmittelbar die einzige Losung �� = (1, 2, 3) abgelesen werden kann.

c) Das Gleichungssystem

x1 + x4 + 2x5 = 12x2 + 2x4 + 3x5 = 1

x3 + 2x4 + 3x5 = 13x1 + 3x4 + 6x5 = 3


(A|b) =

⎛⎜⎜⎝

1 0 0 1 2 10 2 0 2 3 10 0 1 2 3 13 0 0 3 6 3

⎞⎟⎟⎠

Durch Anwendung der Elementaroperationen S(4, 1,−3) und M(2, 1

2

)erhalt man die Zeilenstufenform⎛

⎜⎜⎝1 0 0 1 2 10 1 0 1 3

212

0 0 1 2 3 10 0 0 0 0 0

⎞⎟⎟⎠

Es ist rang(A|b) = rang(A) = 3 < 5 = n. Das Gleichungssystem besitztalso eine mehrdeutige Losung. Es ist P = { 1, 2, 3 } und P = { 4, 5 }. Wirwahlen x4 = λ und x5 = μ. Damit ergeben sich insgesamt die allgemeinenLosungen:

x1 = 1 − λ − 2μx2 = 1

2− λ − 3

2μ

x3 = 1 − 2λ − 3μx4 = λx5 = μ

(3.2)


Als Losungsvektor geschrieben

x =

(1 − λ − 2μ,

1

2− λ − 3

2μ, 1 − 2λ − 3μ, λ, μ

)

Fur die folgende Darstellung der Losung x stellen wir deren Komponentenxi aus (3.2) noch einmal dar und zwar jetzt mithilfe von Farben:

x1 = 1 − 1λ − 2μx2 = 1

2− 1λ − 3

2μ

x3 = 1 − 2λ − 3μx4 = 0 + 1λ + 0μx5 = 0 + 0λ + 1μ

(3.3)

Wir fassen nun die Konstanten der Komponenten xi von x – in blau darge-stellt – sowie die Koeffizienten von λ – in rot dargestellt – und die Koeffizi-enten von μ – in grun dargestellt – von xi jeweils zu Vektoren ��, �1�1�1 bzw. �2�2�2

zusammen und erhalten:

�� =

(1,

1

2,1,0,0

)�1�1�1 = (−1,−1,−2,1,0)

�2�2�2 =

(−2,−3

2,−3,0,1

)

Dabei ist �� eine spezielle Losung des inhomogenen Gleichungssystems(A,b), die man erhalt, wenn λ = μ = 0 gesetzt wird. Es gilt also

x = �� + λ�1�1�1 + μ�2�2�2

Damit lasst sich die Losungsmenge des Gleichungssystems wie folgt schrei-ben:

L(A,b) = {x | x = �� + λ�1�1�1 + μ�2�2�2, λ, μ ∈ R }Dabei sind λ�1�1�1 + μ�2�2�2 die Losungen des homogenen Systems (A,0):

L(A,0) = {x | λ�1�1�1 + μ�2�2�2, λ, μ ∈ R }

Es ist dim(L(A,0)) = n−rang(A) = 5−3 = 2. �1�1�1 und �2�2�2 sind Basisvektorenvon L(A,0)). �

Aus dem Verfahren lassen sich folgende Aussagen ableiten:

Folgerung 3.3 a) Das Gleichungssystem (A,b) ist genau dann losbar,wenn rang(A,b) = rang(A) gilt.

Fur die folgenden Aussagen sei (A,b) als losbar vorausgesetzt, (A′′′,b′′′) seidie Zeilenstufenform von (A,b), P sei die Menge der Pivotindizes, undpi = |{ s ∈ P | s < i }| ist die Anzahl der Nicht-Pivotindizes kleiner als i.


b) Es ist |P | = rang(A) und∣∣P ∣∣ = n − rang(A).

c) Ist rang(A) = n, dann besitzt (A,b) eine eindeutig bestimmte Losung,und es ist A′′′ = E, und x = b′′′ ist die einzige Losung.

d) Ist rang(A) < n, dann besitzt (A,b) eine mehrdeutige Losung.

Wir wahlen fur j ∈ Pxj = λj ∈ K, λj = 0

als spezielle Losungen und berechnen mit diesen fur k ∈ P

xk = b′k−pk−

⎛⎝∑

j∈P

a′kjλj

⎞⎠

woraus sich insgesamt die Losung

x = (x1, x2, . . . , xn)

ergibt. Es gilt fur i ∈ P

xi = li +∑k∈P

likλk mit li = 0 und lik =

{1, j = k

0 j = k

sowie fur i ∈ P

xi = li +∑k∈P

likλk mit li = b′i−piund lik =

{0, 1 ≤ k ≤ j − 1

−a′ik, j + 1 ≤ k ≤ n

e) Wir setzen nun�� = (l1, . . . , ln)

sowie fur k ∈ P�k�k�k = (l1k, . . . , lnk)

Dann gilt:

(i) Fur λk ∈ K, k ∈ P , ist

x = �� +∑k∈P

λk�k�k�k

Losung von (A,b).

(ii) Die Losungsmenge des homogenen Systems (A,0) ist gegeben durchden Unterraum

L(A,0) =

⎧⎨⎩∑

k∈P

λk�k�k�k | λk ∈ K, k ∈ P

⎫⎬⎭

von Kn.


(iii) Es ist dim(L(A,0)) = n−rang(A) =∣∣P ∣∣, und die Menge {�k�k�k | k ∈ P }

bildet eine Basis von L(A,0).

(iv) b′′′ ∈ Kn ist eine spezielle Losung von (A,b), die man erhalt, wennman in (A′′′,b′′′) xj = λj = 0, j ∈ P , setzt,

(v) Die Losungsmenge von (A,b) ist gegeben durch

L(A,b) = �� + L(A,0)

f) Es sei A ∈ MKmn mit m < n. Dann besitzt (A,0) eine Losung x =

(x1, . . . , xn), in der mindestens ein xi = 0 ist. Denn es gilt rang(A) ≤ m < nund damit ist

∣∣P ∣∣ = n−rang(A) > 0, d.h. es gibt mindestens ein i ∈ P , d.h.es kann mindestens ein xj = λ ∈ K mit λ = 0 als Losung gewahlt werden.�

Beispiel 3.3 Wir betrachten das Gleichungssystem

x1 + x2 + x3 + 4x4 + x5 + x6 + 8x7 = 1

x1 + x2 + x3 + 6x4 + 2x5 + 2x6 + 10x7 = 2

mit der erweiterten Koeffizientenmatrix

(A,b) =

(1 1 1 4 1 1 8 11 1 1 6 2 2 10 2

)Die Elementaroperationen S(2, 1,−1), M

(2, 1

2

)und S(1, 2,−4) fuhren zur

Zeilenstufenform

(A,b) =

(1 1 1 0 −1 −1 4 −10 0 0 1 1

212

1 12

)Es ist rang(A) = rang(A,b) = 2 < 7, das Gleichungssystem hat also einemehrdeutige Losung. Es ist P = { 1, 4 } die Menge der Indizes der Pivot-spalten und damit ist P = { 2, 3, 5, 6, 7 } die Menge der Indizes der Nicht-Pivotspalten. Wir erhalten mit Folgerung 3.3 d) und e):

x1 = −1 − 1 · λ2 − 1 · λ3 + 1 · λ5 + 1 · λ6 − 4 · λ7

x2 = 0 + 1 · λ2 + 0 · λ3 + 0 · λ5 + 0 · λ6 + 0 · λ7

x3 = 0 + 0 · λ2 + 1 · λ3 + 0 · λ5 + 0 · λ6 + 0 · λ7

x4 =1

2+ 0 · λ2 + 0 · λ3 − 1

2· λ5 − 1

2· λ6 − 1 · λ7

x5 = 0 + 0 · λ2 + 0 · λ3 + 1 · λ5 + 0 · λ6 + 0 · λ7

x6 = 0 + 0 · λ2 + 0 · λ3 + 0 · λ5 + 1 · λ6 + 0 · λ7

x7 = 0 + 0 · λ2 + 0 · λ3 + 0 · λ5 + 0 · λ6 + 1 · λ7

Daraus ergibt sich

�� =

0BBBBBBB@

−10012000

1CCCCCCCA

�2�2�2 =

0BBBBBBB@

−1100000

1CCCCCCCA

�3�3�3 =

0BBBBBBB@

−1010000

1CCCCCCCA

�5�5�5 =

0BBBBBBB@

100

− 12100

1CCCCCCCA

�6�6�6 =

0BBBBBBB@

100

− 12010

1CCCCCCCA

�7�7�7 =

0BBBBBBB@

400

−1001

1CCCCCCCA


Es ist

L(A,0) = {λ2�2�2�2 + λ3�3�3�3 + λ5�5�5�5 + λ6�6�6�6 + λ7�7�7�7 | λ2, λ3, λ5, λ6, λ7 ∈ R }sowie dim(L(A,0) = n − rang(A) = 7 − 2 = 5.

{�2�2�2, �3�3�3, �5�5�5, �6�6�6, �7�7�7 } bildet eine Basis von L(A,0).

Die gesamte Losungsmenge ergibt sich durch L(A,b) = �� + L(A,0). �

✍ Ubungsaufgaben

3.2 Losen Sie mithilfe des Gaussschen Eliminationsverfahrens

(1) das Gleichungssystem in Beispiel 1.5,

(2) das Gleichungssystem in der Musterl sung von Aufgabe 1.5 b)sowie

(3) das Gleichungssystem

x1 + x2 + x3 + x4 + x5 + x6 + x7 + x8 + x9 = 10

x1 + 2x2 + 3x3 + 4x4 + 5x5 + 6x6 + 7x7 + 8x8 + 9x9 = 10

in GLF112,9 [x]! �

3.3 Gleichungssysteme als lineare Abbildungen

Die Erkenntnisse (ii) und (iii) in Folgerung 3.3 e) hatten wir auch bereits ausKenntnissen uber lineare Abbildungen (siehe Kapitel 1.4) herleiten konnen.Ist namlich A ∈ MK

mn eine (m × n)-Matrix uber dem Korper K, dann istdie Funktion FAFAFA : Kn → Km definiert durch y = FAFAFA(x) = A · x eine lineareAbbildung vom Vektorraum Kn in den Vektorraum Km, denn es gilt:

FAFAFA(α1x111+α2x222) = A·(α1x111+α2x222) = α1·A·x111+α2·A·x222 = α1·FAFAFA(x111)+α2·FAFAFA(x222)

Fur den Kern von FAFAFA gilt

Kern(FAFAFA) = {x ∈ Kn | FAFAFA(x) = 0 } = {x ∈ Kn | A · x = 0 } = L(A,0)

Das heißt: Der Kern von FAFAFA ist der Losungsraum des homogenen linearenGleichungssystems A · x = 0.

Des Weiteren gilt:

Bild(FAFAFA) = {b ∈ Km | es existiert x ∈ Kn mit FAFAFA(x) = b }= {b ∈ Km | es existiert x ∈ Kn mit A · x = b }

o

54 Gleichungssysteme als lineare Abbildungen

Aus Satz 1.13 und Definition 1.10 wissen wir, dass dann, wenn die Dimensi-on des Bildraums einer linearen Abbildung rg ist, die Dimension des Kernsn − rg ist. rg heißt dort der Rang der linearen Abbildung. Dieser stimmt– im Nachhinein nicht anders als zu erwarten – mit dem Rang des Glei-chungssystems uberein, das durch die die lineare Abbildung bestimmendeMatrix A gegeben ist, wahrend n− rg die Dimension des Kerns, d.h. die Di-mension des Losungsraums des durch die Matrix A festgelegten homogenenGleichungssystems, ist.

3.4 Zusammenfassung

Ein lineares Gleichungssystem A · x = b uber einem Korper K mit mGleichungen und n Unbekannten x = (x1, . . . , xn) ist festgelegt durchdie erweiterte Koeffizientenmatrix (A,b) mit A ∈ MK

mn und b ∈ Km.Ist b = 0, dann heißt das System homogen, sonst inhomogen. Jedeshomogene Gleichungssystem besitzt mindestens eine Losung, namlichden Nullvektor. Die Losungsmenge eines homogenen Gleichungssystemsbildet einen Unterraum von Kn, die Dimension des Losungsraums istn − rang(A). Ein inhomogenes System ist genau dann losbar, wennrang(A) = rang(A,b) ist. Ist rang(A) < rang(A,b), dann besitzt dasSystem keine Losung, ist rang(A) = rang(A,b) = n, dann besitzt dasSystem genau eine Losung. Ist rang(A) = rang(A,b) < n, dann istdie Losung mehrdeutig. Die Losungsmenge ergibt sich als Summe einerspeziellen Losung des inhomogenen Systems und des Losungsraums deszugehorigen homogenen Systems. Dieser Losungsraum hat die Dimensi-on n− rang(A). Die folgenden Zeilenreduktionen der erweiterten Koef-fizientenmatrix lassen die Losungsmenge eines linearen Gleichungssys-tems invariant: Vertauschen von Zeilen, Multiplikation einer Zeile miteinem Skalar, die Addition einer Linearkombination von Zeilen zu einerZeile. Auf diesen Operationen basiert das Gausssche Eliminationsver-fahren, mit dem der Rang und gegebenenfalls die Losungsmenge eineslinearen Gleichungssystems bestimmt werden konnen. Fur A ∈ MK

mn

beschreibt FAFAFA(x) = A · x eine lineare Abbildung vom Vektorraum Kn

in den Vektorraum Km. Der Kern dieser Abbildung ist der Losungs-raum des zugehorigen homogenen Gleichungssystems, er hat die Di-mension n− rang(A), und der Rang von A ist gleich der Dimension desBildraums. Die Losungsmenge des Gleichungssystems ist die durch einespezielle Losung des inhomogenen Systems festgelegte Nebenklasse desKerns.

Documents

Lineare Algebra für die Informatik || Lineare Gleichungssysteme