Ein Invertierungsverfahren

Wir stellen ein effektives Verfahren vor, das eine Matrix A  ∈  ℝ^{n × n} auf Invertierbarkeit überprüft und im positiven Fall ihr Inverses A⁻¹ berechnet. Das Verfahren verwendet die folgenden elementaren Zeilenoperationen:

(Z1) Multiplikation einer Zeile mit einem Skalar λ ≠ 0.

(Z2) Addition des λ-Fachen einer Zeile zu einer anderen Zeile.

Invertierungverfahren für Matrizen

Gegeben sei A  ∈  ℝ^n × n. Wir setzen A₀ = A. Durch Anwendung von (Z1) und (Z2) versuchen wir, A schrittweise in die Einheitsmatrix E_n zu überführen. Wir erzeugen so Matrizen A₀, …, A_k. Parallel wenden wir dieselben Zeilenoperationen auf B₀ = E_n an und erzeugen so Matrizen B₀, …, B_k. Hat A_k eine Nullzeile, so stoppen wir mit „A ist singulär“. Erreichen wir A_k = E_n, so geben wir B_k als Ergebnis aus.

Beispiel: Invertierung einer Matrix

A₀ = $( \begin{matrix} 1 & 1 & 0 \\ 1 & 0 & 1 \\ 1 & - 1 & 1 \end{matrix} )$ $( \begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix} )$ = B₀

A₁ = $( \begin{matrix} 1 & 1 & 0 \\ 0 & - 1 & 1 \\ 1 & - 1 & 1 \end{matrix} )$ $( \begin{matrix} 1 & 0 & 0 \\ - 1 & 1 & 0 \\ 0 & 0 & 1 \end{matrix} )$ = B₁

A₂ = $( \begin{matrix} 1 & 1 & 0 \\ 0 & - 1 & 1 \\ 0 & - 2 & 1 \end{matrix} )$ $( \begin{matrix} 1 & 0 & 0 \\ - 1 & 1 & 0 \\ - 1 & 0 & 1 \end{matrix} )$ = B₂

A₃ = $( \begin{matrix} 1 & 1 & 0 \\ 0 & - 1 & 1 \\ 0 & 0 & - 1 \end{matrix} )$ $( \begin{matrix} 1 & 0 & 0 \\ - 1 & 1 & 0 \\ 1 & - 2 & 1 \end{matrix} )$ = B₃

A₄ = $( \begin{matrix} 1 & 1 & 0 \\ 0 & - 1 & 0 \\ 0 & 0 & - 1 \end{matrix} )$ $( \begin{matrix} 1 & 0 & 0 \\ 0 & - 1 & 1 \\ 1 & - 2 & 1 \end{matrix} )$ = B₄

A₅ = $( \begin{matrix} 1 & 0 & 0 \\ 0 & - 1 & 0 \\ 0 & 0 & - 1 \end{matrix} )$ $( \begin{matrix} 1 & - 1 & 1 \\ 0 & - 1 & 1 \\ 1 & - 2 & 1 \end{matrix} )$ = B₅

A₆ = $( \begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & - 1 \end{matrix} )$ $( \begin{matrix} 1 & - 1 & 1 \\ 0 & 1 & - 1 \\ 1 & - 2 & 1 \end{matrix} )$ = B₆

A₇ = $( \begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix} )$ $( \begin{matrix} 1 & - 1 & 1 \\ 0 & 1 & - 1 \\ - 1 & 2 & - 1 \end{matrix} )$ = B₇

Wir geben B₇ als Ergebnis aus. In der Berechnung haben wir verwendet:

0 nach 1: Addition des −1-Fachen der ersten Zeile zur zweiten.

1 nach 2: Addition des −1-Fachen der ersten Zeile zur dritten.

2 nach 3: Addition des −2-Fachen der zweiten Zeile zur dritten.

…

6 nach 7: Multiplikation der dritten Zeile mit dem Skalar −1.

Das Diagramm zeigt die Spate der Spaltenvektoren (blau, orange, grün) der Matrizen A₀, …, A₇. Die Spate werden schrittweise zum Einheitswürfel umgeformt. In jedem Schritt wird höchstens eine Komponente jedes Spaltenvektors verändert.

Wir haben den Algorithmus angegeben und an einem Beispiel illustriert. Nun zeigen wir, dass der Algorithmus das leistet, was wir behaupten:

Korrektheit des Invertierungsverfahrens

Die Zeilenoperationen lassen sich durch invertierbare Matrizen L₁, …, L_k beschreiben, die wir von links an A bzw. B₀ multiplizieren (vgl. die Übungen).

Erster Fall: Erhalten wir

(+) L_k … L₁ A = A_k = E_n,

so ist die Matrix

B = B_k = L_k … L₁ = L_k … L₁ E_n

invers zu A. Denn B ist als Produkt invertierbarer Matrizen invertierbar und es gilt B A = E_n, sodass automatisch auch B A = E_n (einseitige Überprüfung). Nach den Invertierungsregeln sind also A und B invers zueinander, sodass A⁻¹ = B_k.

Zweiter Fall: Hat A_k eine Nullzeile, so ist L_k … L₁ A singulär. Da die Matrizen L₁, …, L_k invertierbar sind, ist notwendig A singulär.

Diese Zweiteilung ist typisch: In einem ersten Schritt wird der Algorithmus lediglich beschrieben. Danach wird gezeigt, was der Algorithmus leistet. Der erste Teil entspricht einer Definition, der zweite einem Satz mit Beweis. Die Beschreibung eines Algorithmus kann in der mathematischen Umgangssprache erfolgen. Dabei wird deutlich, wie das Verfahren mit Hilfe einer Programmiersprache umgesetzt werden kann. Aus Gründen der Einfachheit haben wir den Algorithmus kurz und informal beschrieben. Eine genauere Version mit konkreten Zeilenoperationen lässt sich angeben. Dadurch wird das Verfahren deterministisch: Jeder Schritt ergibt sich eindeutig aus dem bisherigen Verlauf der Berechnung. In der Regel genügen Beispiele, um das Verfahren zu erläutern. Wer es genauer wissen möchte, kann folgende Präzisierung verwenden:

Präzisierung des Algorithmus

Wir können die Matrix A durch wiederholte Anwendung von (Z2) in eine Matrix A′ in Zeilenstufenform (v₁, …, v_r, 0, …, 0)  ∈  ℝ^n × n, r ≤ n, mit Pivots p(1) < p(2) < … < p(r) überführen, d. h. es gilt

p(i) = „das kleinste j mit a′_ij ≠ 0“

Anschaulich entspricht diese Form (die wir im nächsten Kapitel genauer betrachten werden) dem Ausräumen unterhalb der Diagonale, wobei Querschritte mit p(i + 1) ≥ p(i) + 2 entstehen können (verlängerte waagrechte Stufen). Genau in diesem Fall ist A singulär und jeder derartige Querschritt führt zu einer Nullzeile von A′. Ist r = n und p(i) = i für alle i („perfekte Treppe“), so ist A invertierbar. Wir können nun A auch noch oberhalb der Diagonale ausräumen und schließlich mit Hilfe von (Z1) die Einheitsmatrix E_n erzeugen. Dadurch erhalten wir A⁻¹.