(10.26) SATZ

Der Entzerrungsalgorithmus

Gegeben sei das LGS Ax = b mit A ∈ M_{m,n}(IR) und b ∈ IR^{m}. Ferner gelte rg(A|b) = rg(A) =: r. Die Treppenmatrix (T (A), b′) der erweiterten Koeffizientenmatrix (A|b) habe die charakteristischen Indizes k_{1}, k_{2}, …, k_{r}, und es sei {j_{1}, j_{2}, …, j_{n−r}} := {1, 2, …, n} \ {k_{1}, k_{2}, …, k_{r}}. Durch Einfügen oder Löschen von Nullzeilen in der Matrix (T (A), b′) erhält man eine Matrix vom Format (n, n+1), bei der die Einsen der Spalten mit den Indizes k_{1}, k_{2}, …, k_{r} in der Hauptdiagonale stehen. Die Spalten von B seien w_{1}, w_{2}, …, w_{n}, u . Setze

v_{j_{i}} := w_{j_{i}} − e_{j_{i}} (i = 1, 2, …, n − r)

Dann gilt:

a) u ∈ Lös(A, b)

b) v_{j_{1}}, v_{j_{2}}, …, v_{j_{n−r}} ist eine Basis des Untervektorraumes Lös(A, o_{m})

c) Jede Lösung von Ax = b ist von der Form

u + α_{1}v_{j_{1}} + +α_{2}v_{j_{2}} + … + +α_{n−r}v_{j_{n−r}}

mit reellen Koeffizienten α_{1}, α_{2}, …, α_{n−r}.

Beweis: Die Voraussetzung rg(A|b) = rg(A) sichert, daß das LGS überhaupt lösbar ist (10.25) .

a) Es ist u eine Linearkombination der Spalten w_{1}, …, w_{n} und daher nach (10.9) eine Lösung von T (A)x = b′ (die eingefügten oder gestrichenen Nullzeilen spielen dabei keine Rolle!) und damit auch von Ax = b.

b) Wir betrachten zunächst den Fall k_{i} = i (für i = 1, 2, …, r) . Dann hat die Matrix B ∈ M_{n,n+1}(IR) die folgende Gestalt

\begin{matrix}1 & 0 & … & 0 & ⋆ & … & ⋆ & ⋆ \\ 0 & 1 & … & 0 & ⋆ & … & ⋆ & ⋆ \\ 0 & 0 & … & 0 & ⋆ & … & ⋆ & ⋆ \\ ⋮ & ⋮ & … & ⋮ & ⋮ & … & ⋮ & ⋮ \\ 0 & 0 & … & 1 & ⋆ & … & ⋆ & ⋆ \\ 0 & 0 & … & 0 & 0 & … & 0 & 0 \\ ⋮ & ⋮ & … & ⋮ & ⋮ & … & ⋮ & ⋮ \\ 0 & 0 & … & 0 & 0 & … & 0 & 0 \\ w_{1} & w_{2} & … & w_{r} & w_{r+1} & … & w_{n} & u \end{matrix}

Mit B′ werde die (n × n)–Matrix bezeichnet, die aus den Spalten w_{1}, …, w_{n} aufgebaut ist. Setze

v_{j} := w_{j} − e_{j} (j = r + 1, …, n)

Für j > r sei

w_{j} = ( b_{1} ; ⋮ ; b_{r} ; 0 ; ⋮ ; 0 ) , und damit v_{j} = w_{j} − e_{j} = ( b_{1} ; ⋮ ; b_{r} ; 0 ; ⋮ ; 0 ; −1 ; 0 ; ⋮ ; 0 )

wobei −1 in der j–ten Zeile des Vektors v_{j} steht. Es gilt nun

b_{1}w_{1} + … + b_{r}w_{r} + (−1)w_{j} = b_{1}e_{1} + … + b_{r}e_{r} + (−1)w_{j}

= ( b_{1} ; ⋮ ; b_{r} ; 0 ; ⋮ ; 0 ) + (−1)w_{j}

= w_{j} + (−1)w_{j}
= o_{n}

Damit ist o_{n} eine Linearkombination der Spalten w_{1}, …, w_{n} von B′. Nach (10.9) ist der Vektor v_{j} eine Lösung des homogenen LGS’s B′x = o_{n}, folglich eine Lösung von T (A)x = o_{m} und schließlich eine Lösung von Ax = o_{m}. Damit ist gezeigt:

v_{j} ∈ L_{0} := Lös(B′, o_{n}) = Lös(A, o_{m}) für alle j = r + 1, …, n

Als nächstes überlegen wir uns, daß die Vektoren v_{r+1}, …, v_{n} linear unabhängig sind.

v_{r+1} = ( ⋆ ; ⋮ ; ⋆ ; −1 ; 0 ; ⋮ ; 0 ) , v_{r+2} = ( ⋆ ; ⋮ ; ⋆ ; 0 ; −1 ; 0 ; ⋮ ; 0 ) , …, v_{n} = ( ⋆ ; ⋮ ; ⋆ ; 0 ; ⋮ ; 0 ; −1 )

Gilt nun (+) n ; ∑ ; j=r+1 α_{j}v_{j} = o_{n} mit beliebigen Koeffizienten α_{j} ∈ IR , so

bedeutet dies

( ⋆ ; ⋮ ; ⋆ ; −α_{r+1} ; ⋮ ; −α_{n} ) = ( 0 ⋮ 0 0 ⋮ 0 )

Folglich sind in (+) alle Koeffizienten gleich 0 , d.h. die Vektoren v_{r+1}, …, v_{n} sind linear unabhängig .

Schließlich zeigen wir, daß sich jede Lösung v = ( c_{1} ; ⋮ ; c_{n} ) ∈ L_{0} als Linearkom-

bination von v_{r+1}, …, v_{n} darstellen läßt. Nach (10.9) gilt

n ; ∑ ; i=1 c_{i}w_{i} = o_{n} ,

da v eine Lösung von B′x = o_{n} ist. Setze α_{j} := −c_{j} für j > r und beachte w_{j} = v_{j} + e_{j} für j > r. Damit ergibt sich

o_{n} = r ; ∑ ; k=1 c_{k}w_{k} + n ; ∑ ; j=r+1 c_{j}w_{j}
= r ; ∑ ; k=1 c_{k}e_{k} + n ; ∑ ; j=r+1 c_{j}(v_{j} + e_{j})
= \underline{r ; ∑ ; k=1 c_{k}e_{k}} + n ; ∑ ; j=r+1(−α_{j})v_{j} + \underline{n ; ∑ ; j=r+1 c_{j}e_{j}}
= n ; ∑ ; i=1 c_{i}e_{i} − n ; ∑ ; j=r+1 α_{j}v_{j}
= v − n ; ∑ ; j=r+1 α_{j}v_{j}

Also v = n ; ∑ ; j=r+1 α_{j}v_{j}.

Damit ist der spezielle Fall vollständig bewiesen. Den allgemeinen Fall können wir durch Spaltenvertauschungen auf den speziellen Fall zurückführen. Eine Vertauschung zweier Spalten der Matrix A bedeutet lediglich eine Umnumerierung der Unbekannten des LGS’s Ax = b (mache dir das klar!) . Durch Spaltenvertauschungen können wir also immer die Situation des speziellen Falles herstellen, wofür wir das Ergebnis bewiesen haben. Machen wir anschließend die dadurch bedingte Umnumerierung der Unbekannten wieder rückgängig, so haben wir auch den allgemeinen Fall bewiesen.

c) Dies ist eine unmittelbare Folgerung, die sich mit a) und b) aus (10.11) ergibt.

Bemerkungen:

a) Der Entzerrungsalgorithmus ist ein weitergeführter Gauß–Algorithmus.

b) Für die Lösung des LGS’s Ax = b mit Hilfe des Entzerrungsalgorithmus sind entsprechend Satz (10.26) die folgenden Schritte auszuführen:

• Bringe die erweiterte Koeffizientenmatrix (A|b) durch elementare Zeilenumformungen auf Treppenform. Das Ergebnis ist eine Matrix (T (A), b′) vom Format (m, n + 1) . An dieser Matrix läßt sich insbesondere ablesen, ob das LGS lösbar ist oder nicht. Im Falle der Lösbarkeit führe die nächsten Schritte aus:

• Füge Nullzeilen ein oder streiche Nullzeilen, so daß aus (T (A), b′) eine Matrix B vom Format (n, n + 1) entsteht, bei der die Einsen der Spalten mit den charakteristischen Indizes in der Hauptdiagonale stehen.

• Ersetze in der Matrix B die Nullen in der Hauptdiagonale durch −1 . Die entstandene Matrix heiße C.

• Die rechte Spalte von C ist eine spezielle Lösung von Ax = b, die Spalten mit −1 in der Haupdiagonalposition bilden eine Basis des Lösungsraumes des homogenen LGS’s Ax = o_{m}.

• Bilde die Lösungsmenge von Ax = b entsprechend (10.26c) .