Chr.Nelius : Lineare Algebra I (WS 2004/05) 1

§ 10 Lineare Gleichungssysteme

\underline{(10.1) Bezeichnungen:} Ein System

(⋆) \{ \begin{matrix}a_{11}x_{1} + a_{12}x_{2} + … + a_{1n}x_{n} & = & b_{1} \\ a_{21}x_{1} + a_{22}x_{2} + … + a_{2n}x_{n} & = & b_{2} \\ ⋮ & & ⋮ \\ a_{m1}x_{1} + a_{m2}x_{2} + … + a_{mn}x_{n} & = & b_{m} \end{matrix}

aus m linearen Gleichungen mit reellen Koeffizienten für n Unbekannte heißt ein lineares Gleichungssystem (LGS) über IR . Mit der Koeffizientenmatrix

A = ( \begin{matrix}a_{11} & a_{12} & … & a_{1n} \\ a_{21} & a_{22} & … & a_{2n} \\ ⋮ & ⋮ & & ⋮ \\ a_{m1} & a_{m2} & … & a_{mn} \end{matrix} ) ∈ M_{m,n}(IR)

und dem Vektor b = ( b_{1} ; b_{2} ; ⋮ ; b_{m} ) ∈ IR^{m} der rechten Seite läßt sich das LGS (⋆) darstellen in der Form

A · x = b ,

wobei x = ( x_{1} ; x_{2} ; ⋮ ; x_{n} ) der Spaltenvektor der Unbekannten ist.

Chr.Nelius : Lineare Algebra I (WS 2004/05) 2

Die Matrix

(A|b) := ( \begin{matrix}a_{11} & a_{12} & … & a_{1n} & b_{1} \\ a_{21} & a_{22} & … & a_{2n} & b_{2} \\ ⋮ & ⋮ & & ⋮ & ⋮ \\ a_{m1} & a_{m2} & … & a_{mn} & b_{m} \end{matrix} ) ∈ M_{m,(n+1)}(IR)

heißt die erweiterte Koeffizientenmatrix von (⋆) .

Ein Spaltenvektor y = ( y_{1} ; y_{2} ; ⋮ ; y_{n} ) ∈ IR^{n} heißt eine Lösung von (⋆) , wenn A·y = b gilt.

Lös(A, b) := { y | y ∈ IR^{n}, Ay = b } heißt die Lösungsmenge von (⋆). Das LGS Ax = b heißt lösbar, wenn Lös(A, b) ≠ ∅ ist, ansonsten unlösbar . Das LGS Ax = b heißt homogen, wenn b = o_{m} der Nullvektor ist, ansonsten inhomogen .

Probleme:

• Wie läßt sich rechnerisch feststellen, ob ein Gleichungssystem lösbar ist oder nicht ?

• Was läßt sich über die “Größe” der Lösungsmenge aussagen ?

• Was läßt sich über die Lösungen aussagen ?

• Wie läßt sich die Lösungsmenge rechnerisch bestimmen ?

\underline{(10.2) SATZ:} Die Lösungsmenge des LGS’s

(⋆) \{ \begin{matrix}a_{11}x_{1} + a_{12}x_{2} + … + a_{1n}x_{n} & = & b_{1} \\ a_{21}x_{1} + a_{22}x_{2} + … + a_{2n}x_{n} & = & b_{2} \\ ⋮ & & ⋮ \\ a_{m1}x_{1} + a_{m2}x_{2} + … + a_{mn}x_{n} & = & b_{m} \end{matrix}

ändert sich nicht unter den folgenden Operationen: I) Vertauschung zweier Gleichungen II) Multiplikation einer Gleichung mit einem Skalar ≠ 0 III) Addition des skalaren Vielfachen einer Gleichung zu einer anderen Gleichung. \underline{Bew:} I) ist klar. II) Wir multiplizieren die j–te Gleichung mit r ≠ 0 und erhalten das LGS

(⋆⋆) \{ \begin{matrix}a_{11}x_{1} + a_{12}x_{2} + … + a_{1n}x_{n} & = & b_{1} \\ ⋮ & & ⋮ \\ ra_{j1}x_{1} + ra_{j2}x_{2} + … + ra_{jn}x_{n} & = & rb_{j} \\ ⋮ & & ⋮ \\ a_{m1}x_{1} + a_{m2}x_{2} + … + a_{mn}x_{n} & = & b_{m} \end{matrix}

Es sei L die Lösungsmenge von (⋆) und L′ die von (⋆⋆). Beh: L = L′ Ist y = (y_{k}) ∈ L beliebig, so gilt für alle i = 1, 2, …, m

a_{i1}y_{1} + a_{i2}y_{2} + … + a_{in}y_{n} = b_{i}

insbesondere also für i = j

a_{j1}y_{1} + a_{j2}y_{2} + … + a_{jn}y_{n} = b_{j}

Multipliziert man diese Gleichung (auf beiden Seiten) mit r, so ergibt sich

r(a_{j1}y_{1} + a_{j2}y_{2} + … + a_{jn}y_{n}) = ra_{j1}y_{1} + ra_{j2}y_{2} + … + ra_{jn}y_{n} = rb_{j} d.h. y ist auch eine Lösung von (⋆⋆), ist also ein Element von L′. Ist umgekehrt y = (y_{k}) ∈ L′, so sind alle Gleichungen von (⋆⋆) erfüllt, insbesondere gilt

ra_{j1}y_{1} + ra_{j2}y_{2} + … + ra_{jn}y_{n} = rb_{j}

Multiplikation dieser Gleichung mit r^{−1} (nach Vor. ist r ≠ 0 !!) ergibt

a_{j1}y_{1} + a_{j2}y_{2} + … + a_{jn}y_{n} = b_{j}

so daß y_{1}, …, y_{n} alle Gleichungen von (⋆) erfüllen, also y ∈ L.

III) Sei r ∈ IR . Wir addieren das r–fache der i–ten Gleichung zur j–ten Gleichung (i ≠ j) und erhalten das folgende LGS:

(⋆ ⋆ ⋆) \{ \begin{matrix}a_{11}x_{1} + a_{12}x_{2} + … + a_{1n}x_{n} & = & b_{1} \\ ⋮ & & ⋮ \\ a_{i1}x_{1} + a_{i2}x_{2} + … + a_{in}x_{n} & = & b_{i} \\ ⋮ & & ⋮ \\ (a_{j1} + ra_{i1})x_{1} + (a_{j2} + ra_{i2})x_{2} + … + (a_{jn} + ra_{in})x_{n} & = & b_{j} + rb_{i} \\ ⋮ & & ⋮ \\ a_{m1}x_{1} + a_{m2}x_{2} + … + a_{mn}x_{n} & = & b_{m} \end{matrix}

Es sei L die Lösungsmenge von (⋆) und L′′ die von (⋆ ⋆ ⋆). Beh: L = L′′

Ist y = (y_{k}) ∈ L, so gilt insbesondere

a_{i1}y_{1} + a_{i2}y_{2} + … + a_{in}y_{n} = b_{i}
a_{j1}y_{1} + a_{j2}y_{2} + … + a_{jn}y_{n} = b_{j} .

Die Addition der mit r multiplizierten i–ten Gleichung zur j–ten Gleichung ergibt

(a_{j1} + ra_{i1})y_{1} + (a_{j2} + ra_{i2})y_{2} + … + (a_{jn} + ra_{in})y_{n} = b_{j} + rb_{i}

Damit erfüllen y_{1}, …, y_{n} alle Gleichungen von (⋆ ⋆ ⋆) , also y ∈ L′′. Ist umgekehrt y = (y_{k}) ∈ L′′, so gilt insbesondere

a_{i1}y_{1} + a_{i2}y_{2} + … + a_{in}y_{n} = b_{i}
(a_{j1} + ra_{i1})y_{1} + (a_{j2} + ra_{i2})y_{2} + … + (a_{jn} + ra_{in})y_{n} = b_{j} + rb_{i} .

Addiert man nun zur unteren Gleichung die mit −r multiplizierte i–te Gleichung, so ergibt sich

a_{j1}y_{1} + a_{j2}y_{2} + … + a_{jn}y_{n} = b_{j} .

Folglich erfüllen y_{1}, …, y_{n} alle Gleichungen von (⋆) , d.h. y ∈ L. Insgesamt ist damit L = L′′ gezeigt.

\underline{(10.3) DEF:} Unter einer elementaren Zeilenumformung einer Matrix versteht man eine der folgenden Umformungen:

I) Vertauschung zweier Zeilen

II) Multiplikation einer Zeile mit einem Skalar ≠ 0

III) Addition des skalaren Vielfachen einer Zeile zu einer anderen Zeile.

\underline{(10.4) BEM:} Die Lösungsmenge eines LGS’s Ax = b ändert sich nicht, wenn man an der erweiterten Koeffizientenmatrix elementare Zeilenumformungen vornimmt.

\underline{(10.5) BEISPIEL:} Lösung eines LGS’s

LGS  erweiterte Koeffizientenmatrix

\begin{aligned}x_{1} & + & 2x_{2} & + & 3x_{3} & = & 4 \\ 2x_{1} & + & 3x_{2} & + & 4x_{3} & = & 5 \\ 3x_{1} & + & 4x_{2} & + & 5x_{3} & = & 6 \end{aligned}  1 2 3 4 2 3 4 5 3 4 5 6

Addition der mit (−2) multiplizierten

1. Gl. zur 2. Gl. und der mit (−3) multiplizierten 1. Gl. zur 3. Gl.

Addition des (−2)–fachen der 1. Zeile zur 2. und des (−3)–fachen der 1. Zeile zur 3. Zeile

\begin{aligned}x_{1} & + & 2x_{2} & + & 3x_{3} & = & 4 \\ & − & x_{2} & − & 2x_{3} & = & −3 \\ & − & 2x_{2} & − & 4x_{3} & = & −6 \end{aligned}  \begin{matrix}1 & 2 & 3 & 4 \\ 0 & −1 & −2 & −3 \\ 0 & −2 & −4 & −6 \end{matrix}

Addition der mit (−2) multiplizierten

2. Gl. zur 3. Gl.

Addition des (−2)–fachen der 2. Zeile zur 3. Zeile

\begin{aligned}x_{1} & + & 2x_{2} & + & 3x_{3} & = & 4 \\ & − & x_{2} & − & 2x_{3} & = & −3 \end{aligned}  \begin{matrix}1 & 2 & 3 & 4 \\ 0 & −1 & −2 & −3 \\ 0 & 0 & 0 & 0 \end{matrix}

Multiplikation der zweiten Gl. mit −1

Multiplikation der zweiten Zeile mit −1

\begin{aligned}x_{1} & + & 2x_{2} & + & 3x_{3} & = & 4 \\ & & x_{2} & + & 2x_{3} & = & 3 \end{aligned}  1 2 3 4 0 1 2 3 0 0 0 0

Der Matrix auf der rechten Seite entspricht das linksstehende LGS, das aus zwei Gleichungen für drei Unbekannte besteht. Wir können daher eine Unbekannte frei wählen (etwa x_{3} = t ∈ IR) und die anderen Unbekannten in Abhängigkeit von t bestimmen. Aus der zweiten Gleichung ergibt sich damit x_{2} = 3 − 2t und aus der ersten

x_{1} = 4 − 2x_{2} − 3x_{3} = 4 − 6 + 4t − 3t = −2 + t

Damit hat die Lösungsmenge das folgende Aussehen:

Lös(A, b) = \{ ( \begin{matrix}−2 + t \\ 3 − 2t \\ t \end{matrix} ) | t ∈ IR\}

Jeder Lösungsvektor hängt in diesem Falle von einem frei wählbaren Parameter t ∈ IR ab. Durch Einsetzen der Lösungen in die drei ursprünglichen Gleichungen kann man die Probe machen.

(10.6) BEISPIEL:

\begin{aligned}x_{1} & − & 2x_{2} & & & = & 1 \\ & & x_{2} & + & x_{3} & = & −1 \\ x_{1} & & & + & x_{3} & = & 2 \end{aligned}

\begin{matrix}1 & −2 & 0 & 1 \\ 0 & 1 & 1 & −1 \\ 1 & 0 & 1 & 2 \\ 1 & −2 & 0 & 1 \\ 0 & 1 & 1 & −1 \\ 0 & 2 & 1 & 1 \\ 1 & −2 & 0 & 1 \\ 0 & 1 & 1 & −1 \\ 0 & 0 & −1 & 3 \\ 1 & −2 & 0 & 1 \\ 0 & 1 & 1 & −1 \\ 0 & 0 & 1 & −3 \end{matrix}

Wir erhalten aus dem zugehörigen LGS

x_{1}  + 2x_{3} = −1
x_{2} + x_{3} = −1
x_{3} = −3

als einzige Lösung: x_{3} = −3 ⟹ x_{2} = −1 − x_{3} = 2 ⟹ x_{1} = −1 − 2x_{3} = 5 d.h. die Lösungsmenge ist

\{( \begin{matrix}5 \\ 2 \\ −3 \end{matrix} )\}

Chr.Nelius : Lineare Algebra I (WS 2004/05) 7 (10.7) BEISPIEL:

\begin{aligned}x_{1} & + & 2x_{2} & + & x_{3} & = & 1 \\ 2x_{1} & + & 4x_{2} & + & 2x_{3} & = & −1 \\ x_{1} & − & x_{2} & + & x_{3} & = & 0 \end{aligned}

\begin{matrix}1 & 2 & 1 & 1 \\ 2 & 4 & 2 & −1 \\ 1 & −1 & 1 & 0 \\ 1 & 2 & 1 & 1 \\ 0 & 0 & 0 & −3 \\ 0 & −3 & 0 & −1 \\ 1 & 2 & 1 & 1 \\ 0 & −3 & 0 & −1 \\ 0 & 0 & 0 & −3 \end{matrix}

Wir erhalten aus der letzten Zeile die Gleichung 0x_{1} + 0x_{2} + 0x_{3} = −3. Annahme: Es gibt eine Lösung (y_{k}) ∈ IR^{3}. Dann ergibt sich mit 0 = −3 ein Widerspruch. Das LGS ist also nicht lösbar. (10.8) BEISPIEL:

\begin{aligned}x_{1} & + & x_{2} & + & x_{3} & = & 1 \\ 3x_{1} & + & 6x_{2} & + & 3x_{3} & = & 3 \\ 2x_{1} & + & 4x_{2} & + & 2x_{3} & = & 2 \end{aligned}

1 2 1 1
3 6 3 3
2 4 2 2
1 2 1 1
1 2 1 1
1 2 1 1
1 2 1 1
0 0 0 0
0 0 0 0

Wir erhalten das LGS

x_{1} + 2x_{2} + x_{3} = 1

das aus einer Gleichung für drei Unbekannte besteht. Wir können zwei Unbekannte frei wählen und die dritte daraus berechnen:

Setze x_{3} = t ∈ IR , x_{2} = s ∈ IR ⟹ x_{1} = 1 − 2s − t. Die Lösung hängt also von zwei frei wählbaren Parametern s und t ab, die unabhängig voneinander die reellen Zahlen durchlaufen. Als Lösungsmenge erhalten wir:

\{( \begin{matrix}1 − 2s − t \\ s \\ t \end{matrix} ) | r, s ∈ IR \}