Lineare Gleichungssysteme

Wir betrachten ein lineares Gleichungssystem mit m Gleichungen und n Variablen, „Unbestimmten“ oder „Unbekannten“ x₁, …, x_n:

a_{1, 1} x₁ + a_{1, 2} x₂ + … + a_{1, n} x_n = b₁, (Gleichung 1)

a_{2, 1} x₁ + a_{2, 2} x₂ + … + a_{2, n} x_n = b₂, (Gleichung 2)

… …

a_{m, 1} x₁ + a_{m, 2} x₂ + … + a_{m, n} x_n = b_m. (Gleichung m)

Hierbei sind alle a_{i, j} und alle b_i gegebene Elemente von K. Die Skalare a_{i, j} heißen die Koeffizienten des Gleichungssystems, und b = (b₁, …, b_m) heißt der rechte Vektor des Systems. Das Gleichungssystem heißt homogen, falls der rechte Vektor der Nullvektor ist.

Das Gleichungssystem heißt lösbar, falls x₁, …, x_n  ∈  K existieren, sodass alle Gleichungen des Systems simultan erfüllt sind. Der Vektor (x₁, …, x_n)  ∈  Kⁿ heißt dann eine Lösung des Systems. Die Menge

L = { (x₁, …, x_n)  ∈  Kⁿ | (x₁, …, x_n) ist eine Lösung des Systems }

heißt die Lösungsmenge oder der Lösungsraum des Systems.

Wir notieren die Koeffizienten des Systems als (m × n)-Matrix A = (a_{i j})_{i j}. Formal ist eine derartige Matrix eine Abbildung A : { 1, …, m } × { 1, …, n } → K, und wir schreiben dann a_{i j} für die Funktionswerte A(i, j).

Oft ist es auch nützlich, den rechten Vektor in die Koeffizientenmatrix zu integrieren, indem wir der Koeffizientenmatrix eine weitere aus b₁, …, b_m gebildete Spalte hinzufügen. Wir bezeichnen diese Matrix mit (A, b) und nennen sie die erweiterte Koeffizientenmatrix. Sie hat m Zeilen und n + 1 Spalten. Die i-te Zeile dieser Matrix ist (a_i, 1, …, a_{i, n}, b_i).

Ein Gleichungssystem mit erweiterter Koeffizientenmatrix (A, b) und Unbekannten x₁, …, x_n notieren wir oft auch in der kompakten Form

A x = b. (Notation für lineare Gleichungssysteme)

Als Nächstes wollen wir einer Koeffizientenmatrix A eine Funktion zuordnen, die die Berechnungen durchführt, die entstehen, wenn wir in einem Gleichungssystem A x = b für die Unbestimmten Skalare von K einsetzen.

Definition (von einer Matrix induzierte Abbildung)

Sei A = (a_{i j})_{i j} eine (m × n)-Matrix in K. Dann definieren wir eine Funktion f_A : Kⁿ → K^m durch:

f_A(x₁, …, x_n)(i) = ∑_{1 ≤ j ≤ n} a_{i, j} x_j = a_{i, 1} x₁ + a_{i, 2} x₂ + … + a_{i, n} x_n

für alle (x₁, …, x_n)  ∈  Kⁿ und alle 1 ≤ i ≤ m.

Die Funktion f_A heißt die von der Matrix A induzierte oder die der Matrix A zugeordnete Abbildung.

Die Abbildung f_A wertet für x₁, …, x_n  ∈  K alle m Terme auf der linken Seite eines Gleichungssystems A x = b aus. Die Ergebnisse dieser Auswertungen fassen wir zu einem Vektor f_A(x) der Länge m zusammen. Die Frage der Lösbarkeit des Gleichungssystems A x = b lautet nun einfach:

Gilt b  ∈  rng(f_A)?

Weiter gilt:

L = { x  ∈  Kⁿ | f_A(x) = b },

d. h. der Lösungsraum ist das Urbild des Vektors b unter der Abbildung f_A.

Wir wollen nun die geometrische Struktur des Lösungsraumes L von A x = b noch genauer ergründen. Hierzu betrachten wir das zugeordnete homogene Gleichungssystem Ax = 0 und setzen

L₀ = { x  ∈  Kⁿ | A x = 0 }.

Für die Lösungsmenge L₀ gilt:

Satz (Struktur des Lösungsraumes eines homogenen Systems)

(i)	0  ∈  L₀,
(ii)	x + y  ∈  L₀	für alle x, y  ∈  L₀,
(iii)	α x  ∈  L₀	für alle x  ∈  L₀ und alle α  ∈  K.

Beweis

Sei f = f_A die zugeordnete Abbildung. Wir rechnen:

f (0) = f(0 · 0) = 0 · f (0) = 0,

f(x + y) = f (x) + f (y) = 0 + 0 = 0	für alle x, y  ∈  L₀,
f(α x) = α f (x) = α 0 = 0	für alle x  ∈  L₀ und alle α  ∈  K.

Aus L₀ = { x  ∈  Kⁿ | f (x) = 0 } folgen die Behauptungen.

Die aufgetauchten Eigenschaften von f werden wir im Abschnitt über „Lineare Abbildungen“ studieren. Hier halten wir die Strukturaussagen (i) − (iii) begrifflich fest:

Definition (Unterraum)

Ein U ⊆ Kⁿ heißt ein Unterraum oder Untervektorraum des Kⁿ, falls 0  ∈  U gilt und U abgeschlossen unter Vektoraddition und Skalarmultiplikation ist, d. h. für alle x, y  ∈  U und alle α  ∈  K gilt x + y  ∈  U und α x  ∈  U.

Der Satz besagt also, dass die Lösungsmenge eines homogenen linearen Gleichungssystems ein Unterraum ist. Umgekehrt zeigt man in der linearen Algebra, dass auch jeder Unterraum als Lösungsraum eines homogenen Gleichungssystems auftaucht.

Für die Lösungsmenge L von A x = b gilt die folgende Darstellung, deren Beweis dem Leser zur Übung überlassen bleiben kann:

Satz (Struktur des Lösungsraumes eines inhomogenen Systems)

Sei y = (y₁, …, y_n)  ∈  L. Dann gilt

L = L₀ + y, wobei L₀ + y = { x + y | x  ∈  L₀ }.

Kennen wir also die Lösung L₀ des zugeordneten homogenen Systems, so liefert uns jede spezielle Lösung von A x = b alle Lösungen von A x = b.

Wir definieren:

Definition (affiner Unterraum)

Ein X ⊆ Kⁿ heißt ein affiner Unterraum des Kⁿ, falls ein Unterraum U des Kⁿ und ein y  ∈  Kⁿ existieren mit

X = U + y = { x + y | x  ∈  U }.

Damit ist die Lösungsmenge eines linearen Gleichungssystems also ein affiner Unterraum des Kⁿ.

Affine Unterräume sind i. A. nicht mehr abgeschlossen unter der Addition von Vektoren. Es gilt aber eine bemerkenswerte andere Abschlusseigenschaft.

Satz (Abschlusseigenschaft eines affinen Unterraums)

Sei X = U + y ein affiner Unterraum, und seien x₁, …, x_k  ∈  X.

Zudem seien α₁, …, α_k  ∈  K mit ∑_{1 ≤ i ≤ k} α_i = 1. Dann gilt ∑_{1 ≤ i ≤ k} α_i x_i  ∈  X.

Beweis

Sei x_i = u_i + y für alle 1 ≤ i ≤ k, mit u_i in U. Dann gilt:

∑_{1 ≤ i ≤ k} α_i x_i = ∑_{1 ≤ i ≤ k} α_i (u_i + y) = (∑_{1 ≤ i ≤ k} α_i u_i) + 1 y  ∈   U + y = X.

Zwei Gleichungen und zwei Unbekannte

Bevor wir uns einem allgemeinen Lösungsverfahren zuwenden, betrachten wir lineare Gleichungssysteme mit zwei Gleichungen und zwei Unbekannten noch etwas genauer. Wir notieren ein derartiges System in der Form

a x + b y = e, (Gleichung 1)

c x + d y = f. (Gleichung 2)

mit Unbekannten x und y und vorgegebenen reellen Zahlen a, …, f. Wir nehmen der Einfachheit halber an, dass b, d ≠ 0 gilt. Dann können wir die beiden Gleichungen schreiben als

y = − (a/b) x + e/b, (Geradengleichung 1)

y = − (c/d) x + f/d. (Geradengleichung 2)

Gerade der ersten Gleichung mit Steigung s = − a/b

Die beiden Gleichungen beschreiben also Geraden in der Ebene, und die Schnittpunkte dieser Geraden bilden die Lösungsmenge des Systems. Sind die Geraden nicht parallel, so existiert genau eine Lösung. Dies ist genau dann der Fall, wenn die Steigungen − a/b und − c/d der Geraden verschieden sind, d. h. falls ad − b c ≠ 0. (Dieser Wert ist unabhängig von e und f.) Sind die Geraden parallel aber verschieden, so existiert keine Lösung. Andernfalls fallen die beiden Geraden zusammen und es gibt unendlich viele Lösungen.

Liegen die Steigungen der Geraden nahe beieinander, d. h. ist |ad − b c| sehr klein, so treten bemerkenswerte Effekte auf. Wir betrachten hierzu folgendes Beispiel (aus einer Arbeit von William Kahan):

0,2161 x + 0,1441 y = 0,1440,

1,2969 x + 0,8648 y = 0,8642.

Die eindeutige Lösung dieses Gleichungssystems ist (x, y) = (2, − 2). Für x = 0,9911 und y = − 0,4870, ergibt sich

0,2161 x + 0,1441 y = 0,1440 + 0,00000001,

1,2969 x + 0,8648 y = 0,8642 − 0,00000001,

d. h. der von (2, − 2) deutlich verschiedene Vektor (x, y) könnte als Lösung des Systems gelten, wenn wir mit weniger als acht Nachkommastellen Genauigkeit rechnen. Umgekehrt betrachtet: Ändern wir die rechte Seite (0,1440, 0,8642) minimal um (10⁻⁸, − 10⁻⁸) ab, so springt die exakte Lösung von (2, − 2) zu (x, y). Man sagt in der Numerik, dass das Gleichungssystem schlecht konditioniert ist.