Äquivalenztransformation

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

Die Äquivalenztransformation oder reguläre Transformation von Matrizen ist in der linearen Algebra die Transformation einer Matrix A in eine Äquivalente Matrix B durch invertierbare Matrizen L und R vermöge[1]:56

LAR = B

Ist die Matrix A eine hermitesche Matrix und soll auch B es sein, sind R und L hermitesch zueinander zu wählen. Die Äquivalenztransformation geht dann über in den Spezialfall der Kongruenz­transformation[1]:56

LALH = B   oder im Reellen    LAL = B

Eine Äquivalenztransformation kann praktisch in einer erweiterten Matrix mit drei Matrizen und bestimmten Grund- oder Elementaroperationen der Spalten- und Zeilen der Matrizen durchgeführt werden.[1]:56[2]:59

Von zentraler Bedeutung ist die Überführung von Matrizen in eine Pivotmatrix, die in jeder Spalte und Zeile höchstens einen von null verschiedenen Eintrag aufweist. Die Einheits-, Diagonal- und Permutationsmatrizen sind Pivotmatrizen; diese müssen jedoch weder quadratisch noch invertierbar sein. Die Anzahl der von null verschiedenen Einträge in einer Pivotmatrix entspricht ihrem Rang.[1]:75

Die Äquivalenztransformation ist Grundlage für das Gauß’sche Eliminationsverfahren und den Gauß-Jordan-Algorithmus und sie ist dienlich bei der Ermittlung des Ranges einer Matrix sowie der Eigenspalten und Eigenzeilen einer singulären Matrix.

Sind bei gegebenen A die Matrizen LBR = A mit einer Pivotmatrix B gesucht, dann empfiehlt sich der Algorithmus von Banachiewicz.

Gegeben sei ein Körper K, meist oder , auf dem die n×m-Matrizen A und B, sowie die n×n-Matrix L und m×m-Matrix R – L und R invertierbar – definiert sind. Jede reguläre Transformation

LAR = B

lässt sich multiplikativ aus drei Grundoperationen zusammensetzen, die sich entweder auf die Spalten von R und B oder die Zeilen von L und B auswirken.[1]:56ff Bei manueller Durchführung im Generalschema einer Äquivalenztransformation werden die Matrizen in einer erweiterten Matrix angeordnet und die Operationen auf diese Matrix angewendet. Ausgangspunkt ist oft, dass L und R Einheitsmatrizen sind und B mit A initialisiert wird. Ziel der Operationen kann sein, die Matrix B in eine Dreiecksmatrix, eine Pivotmatrix oder eine angestrebte Normalform einer Matrix umzuwandeln.

Grundoperationen

[Bearbeiten | Quelltext bearbeiten]

Die Grundoperationen lassen sich mit einer invertierbaren Matrix T darstellen, mit der die Transformationsgleichung LAR = B von rechts bzw. links multipliziert wird:

Spaltenoperationen:    LART = BT    →   LAR' = B'   mit   R' = RT   und   B' = BT
Zeilenoperationen: TLAR = TB L"AR = B" mit L" = TL und B" = TB

Nach k solchen Operationen ist

R' = RT1T2…Tk    bzw.    L" = TkTk-1…T1L

was die multiplikative Zusammensetzung der regulären Transformation zeigt. Sind R und L anfänglich Einheitsmatrizen, enthält R' das Produkt der Transformationsmatrizen in der Reihenfolge ihres Auftretens und L" das Produkt in entgegengesetzter Reihenfolge. Umgekehrt verhält es sich bei ihren Inversen: Da enthält L"−1 das Produkt der Inversen in der Reihenfolge ihres Auftretens und R'−1 das Produkt in entgegengesetzter Reihenfolge. Diese Tatsache ist bei den absteigenden Folgen von Elevatoren bedeutsam.

Die drei Grundoperationen sind:

Umordnung der Spalten oder Zeilen
  • Umordnung der Spalten: Die Reihenfolge der Spalten wird modifiziert, ohne sie selbst zu verändern. Die entsprechende Matrix T ist eine Permutationsmatrix PR, deren Inverse ihre transponierte Matrix ist.
  • Umordnung der Zeilen entsprechend einer Permutationsmatrix T = PL.
Multiplikation der Spalten oder Zeilen mit invertierbaren Skalaren
  • Multiplikation der Spalten: Alle Einträge in einer Spalte werden mit demselben Faktor (ungleich null) multipliziert. Die Matrix T ist eine Diagonalmatrix DR mit den Skalaren auf der Hauptdiagonalen. Die Inverse dieser Diagonalmatrix ist die Diagonalmatrix mit den Kehrwerten, die nach Voraussetzung existieren.
  • Multiplikation der Zeilen, was mit einer Diagonalmatrix T = DL geschieht.
Linearkombination der Spalten oder Zeilen
  • Linearkombination der Spalten: Eine Spalte, die Pivotspalte, wird mit einem Faktor multipliziert und zu einer anderen Spalte addiert oder von ihr subtrahiert. Die Matrix T ist ein sogenannter Zeilenelevator ρ, dessen Inverse sich durch Vorzeichenumkehr der Nebendiagonalglieder bildet.
  • Linearkombination der Zeilen mittels eines Spaltenelevators T = λ, dessen Inverse auch durch Vorzeichenumkehr der Nebendiagonalglieder entsteht.

Die Grundoperationen können weiter in Einzelschritte mit Elementarmatrizen zerlegt werden, die ebenso leicht wie die Matrizen PR/L, DR/L, ρ und λ invertiert werden können. Das Produkt der Elevatoren, das bei mehreren aufeinander folgenden Linearkombinationen von Spalten oder Zeilen anfällt, kann auch leicht invertiert werden, wenn sie eine absteigende Folge eines vollständigen Systems von Elevatoren bilden.

Bei einer Linearkombination von Spalten oder Zeilen einer Einheitsmatrix wird diese in einen Zeilenelevator ρ bzw. Spaltenelevator λ transformiert, der, multipliziert mit einer Matrix, dieselbe Wirkung hat wie die Linearkombination deren Spalten oder Zeilen.

Ein Zeilenelevator besteht gemäß

ρ = Im + ej pj

mit Standardbasis e1,…,m des Km aus der Einheitsmatrix Im ∈ Km×m und höchstens einer signifikanten Zeile pj ∈ Km mit weiteren von null verschiedenen Einträgen. Das hochgestellte ⊤ zeigt die transponierte Matrix an, sodass pj ein Zeilenvektor ist. Tatsächlich ist mit den Spalten bk = B ek:

B' ek = B ρ ek = B (Im + ej pj) ek = bk + bj pjk   mit    pjk = pjek

Das heißt, dass zu jeder Spalte bk, wie es sein soll, das pjk fache der Pivotspalte bj hinzu addiert wird. Die günstigen Eigenschaften, die eine Absteigende Folge von Elevatoren hat, basieren darauf, dass die Pivotspalte bei der Linearkombination der Spalten unveränderlich ist, also pjj = 0 ist. Die j-te Zeile von ρ,

zj = ejρ = (ej + pj)

hat daher eine Eins auf der Hauptdiagonale, zjj = 1, während die restringierte Zeile pj dort eine Null aufweist.

Die Inverse Matrix der Elevatoren kann sofort angegeben werden:

ρ−1 = Im − ej pj

Denn wegen 0 = pjj = pjej ist

ρρ−1 = (Im + ejpj)(Im − ejpj) = Im + ejpj − ejpj − ejpjejpj = Im

Entsprechendes gilt für die Spaltenelevatoren

λ = In + qj ej   →    λ−1 = In − qj ej

wo nun der Kn zugrunde gelegt wird und die Faktoren in einer signifikanten Spalte λej = sj = ej + qj auftreten, mit sjj = 1 und qjj = 0. Die Inversen der Elevatoren bilden sich jedenfalls durch Vorzeichenumkehr der Nebendiagonalglieder.

Vollständige Systeme von Elevatoren

[Bearbeiten | Quelltext bearbeiten]

Zeilenelevatoren (der Dimension m) bilden ein vollständiges System, wenn die Matrix mit ihren signifikanten Zeilen die folgende Form annimmt:[1]:67

Ein solches System fällt im Generalschema einer Äquivalenztransformation an, wenn

  1. jede Spalte höchstens einmal Pivotspalte ist und
  2. die Linearkombinationen der Spalten direkt aufeinander folgen, ohne von Spaltenmultiplikationen oder -umordnungen unterbrochen worden zu sein.

Gleiches gilt für ein vollständiges System von Spaltenelevatoren (der Dimension n):

Einzelne oder mehrere der oder können Nullvektoren sein, die Zeilen von R bzw. die Spalten von L also nur die Eins auf der Hauptdiagonalen und sonst nur Nullen aufweisen. Im Extremfall sind alle Nebendiagonalglieder null und R oder L gleich einer Einheitsmatrix.

Absteigende Folge von Elevatoren

[Bearbeiten | Quelltext bearbeiten]

Ein vollständiges System von Zeilenelevatoren bildet eine absteigende Folge von Zeilenelevatoren, wenn es eine Permutationsmatrix P gibt, sodass für die Matrix R des vorangegangenen Abschnitts

P R P = P [Im + (p1 p2 … pm)] P

eine normierte obere Dreiecksmatrix ist. Dann gilt:[1]:68

  1. die Hauptdiagonalen aller Elevatoren bestehen nur aus Einsen (entsprechend pjj = 0),
  2. für jedes j = 1,…,m gibt es einen Elevator mit mindestens j−1 Nullen in seiner signifikanten Zeile, und
  3. es gibt einen Nachfolger, der in seiner signifikanten Zeile mindestens j−1 Nullen an denselben Stellen wie sein Vorgänger hat.

Eine solche Folge von Zeilenelevatoren entsteht bei der Überführung einer Matrix in eine Pivotmatrix mittels r Nullenkreuzen, wo r immer kleiner oder gleich dem Rang der Matrix ist. Die absteigende Folge eines vollständigen Systems von Spaltenelevatoren entspricht einer normierten unteren Dreiecksmatrix und weist analog verteilte Nullen in ihren Spalten auf.

Das Produkt eines vollständigen Systems absteigender Elevatoren braucht nicht durch Matrizenmultiplikation berechnet zu werden, sondern ergibt sich durch Übertrag der signifikanten Zeilen bzw. Spalten in eine Matrix, was formal mittels der Standardbasis e1,…,m/n erfolgen kann:[1]:68

   bzw.   

wo eine Permutation von und eine solche von ist. Hierbei ist zu beachten:

  1. Die Reihenfolge der Zeilenelevatoren im Produkt ist umgekehrt als bei den Spaltenelevatoren λk. Grund hierfür ist, dass obige Gleichungen durch Transponierung und Austausch von n und m in einander übergehen.
  2. Im Generalschema einer Äquivalenztransformation entstehen die Produkte in der umgekehrten Reihenfolge: R = ρ1ρ2…ρm und L = λnλn-1…λ1.
  3. Die Inverse der Matrix R kann wie folgt in einfacher Weise ermittelt werden: Eine Phantommatrix[1]:78 M wird mit der Nullmatrix initialisiert, die signifikanten Zeilen pj mit umgekehrtem Vorzeichen in die j-te Zeile von M eingetragen und die Hauptdiagonale von M mit Einsen belegt. Dann enthält M am Schluss die Inverse: R−1 = M. Entsprechend kann die Inverse von L sofort angegeben werden, wenn die signifikanten Spalten qk mit umgekehrtem Vorzeichen in den Spalten der Phantommatrix notiert werden und die Hauptdiagonale von M ebenso mit Einsen belegt wird.

Die Zeilenelevatoren

bilden eine vollständige absteigende Folge, denn

  • ihre farbig markierten signifikanten Zeilen z1,2,3, mit einer 1 in den Spalten eins, zwei bzw. drei, lassen sich in einer quadratischen Matrix anordnen, die nur Einsen auf der Hauptdiagonalen hat,
  • z2 besitzt keine Null, z3 eine und z1 zwei, und
  • z1 und z3 haben eine Null an derselben Stelle (in Spalte 2)

Die Permutationsmatrix transformiert R vermöge PRP in eine normierte obere Dreiecksmatrix. Der Unterschied zwischen den Zeilen zj und pj ist, dass zjj = 1 und pjj = 0 ist, daher auch die unterschiedliche Bezeichnung. Das Produkt der Elevatoren in umgekehrter Reihenfolge lautet

Die Inverse des ersten Elevators ist beispielsweise

und die Inverse des Produkts der Elevatoren lautet:

Die Spaltenelevatoren

haben vergleichbare Eigenschaften, denn sie bilden wegen ebenso eine vollständige absteigende Folge wie die Zeilenelevatoren oben. Das Produkt der Spaltenelevatoren lautet

und die Inverse des umgekehrten Produkts entsteht auch hier durch Vorzeichenumkehr der Nebendiagonalglieder:

Diese Tatsachen können insbesondere im Gauß-Jordan-Algorithmus ausgenutzt werden. Die Matrizen in den für die Spaltenelevatoren aufgeschriebenen Gleichungen gehen durch Transposition (sowie Namenstausch λ,q ↔ ρ,p) aus denen für die Zeilenelevatoren hervor und umgekehrt.

Wichtige Konfigurationen

[Bearbeiten | Quelltext bearbeiten]

Beim Pivotkreuz wird in einem Schritt die Matrix A gemäß LAR = B in eine Matrix B transformiert, in der eine Spalte und eine Zeile vorgegebene Einträge besitzt:

 q1j  A11 A1j A1l A1m  A     →       B11 B1j B1l B1m  B
︙ 
 qkj  Ak1 Akj Akl Akm Bk1 Bkj Bkl Bkm
︙ 
1  Ai1 Aij Ail Aim Bi1 Aij Bil Bim
︙ 
 qnj  An1 Anj Anl Anm Bn1 Bnj Bnl Bnm
  pi1 1 pil pim  

Die vorgegebene Spalte und Zeile heißt Pivotspalte bzw. -zeile (blau und gelb unterlegt) und das Matrixelement, in dem sie sich treffen ist das Pivotelement (rosa unterlegt). Es muss von null verschieden sein und ist bei diesem Vorgang unveränderlich. Durch die Vorgaben sind die Linearkombinationen mit der Pivotspalte und -zeile eindeutig festgelegt.

Zur Erzielung des vorgegebenen Elements Bkj der Pivotspalte j, muss der Faktor qkj die Bedingung[1]:60

Bkj = Akj + qkj Aij

erfüllen. Weil nach Voraussetzung Aij ≠ 0, bestimmt sich der Faktor zu

qkj = (Bkj - Akj)/Aij

Der Faktor pil ermittelt sich analog aus dem Pivotelement Aij und dem vorgegebenen Element Bil der Pivotzeile i:[1]:62

Bil = Ail + pil Aij   →   pil = (Bil − Ail)/Aij

Als Beispiel diene die Matrix

mit dem Ziel des gelb unterlegten Pivotkreuzes und der fünf als Pivotelement:

 q12   1  2  3   A     →        B11  7  B13   B
1 4 5 6 -6 5 1
 p21   1   p23       

Der Faktor q12 berechnet sich zu

q12 = (B12 - A12)/A22 = (7 - 2)/5 = 1

Die Faktoren p21 und p23 ergeben sich aus

p21 = (B21 - A21)/A22 = (-6 - 4)/5 = -2
p23 = (B23 - A23)/A22 = (1 - 6)/5 = -1

Der Vektor links von A wird in die Einheitsmatrix eingetragen, was den Spaltenelevator

gibt und der Zeilenvektor unter A erbringt in die Einheitsmatrix eingetragen den Zeilenelevator

Die Transformation

bestätigt den Erfolg des Vorgehens. Die Inversen der Elevatoren sind schnell aufgeschrieben durch Vorzeichenumkehr aller Elemente abseits der Hauptdiagonalen:

bzw.

Das Nullenkreuz ist ein Pivotkreuz, das neben dem Pivotelement (an der Stelle i,j) nur Nullen aufweist:

 q1j  A11 A1j A1l A1m  A     →       B11 0 B1l B1m  B
︙ 
 qkj  Ak1 Akj Akl Akm Bk1 0 Bkl Bkm
︙ 
1  Ai1 Aij Ail Aim 0 Aij 0 0
︙ 
 qnj  An1 Anj Anl Anm Bn1 0 Bnl Bnm
  pi1 1 pil pim  

Der damit Verbundene Vorgang wird Reduktion der Spalte j bzw. Reduktion der Zeile i genannt. Bei fortgeführter Reduktion mit Hilfe weiterer Pivots bleiben die bereits erzeugten Nullenkreuze erhalten. Wenn r der Rang der Matrix A ist, dann überführen höchstens r Nullenkreuze die Matrix in eine Pivotmatrix, und dabei entsteht eine vollständige Absteigende Folge von Elevatoren. Der Aufwand für die Reduktion auf eine Pivotmatrix wächst mit der dritten Potenz der Größe der Matrix.[1]:85

Beispiel: Vorgegeben ist

mit Rang zwei und das erste gelb markierte Nullenkreuz

 q12   1  2  3   A     →        B11  0  B13   B
1 4 5 6 0 5 0
 p21   1   p23       

Man liest ab q12=-25, p21=-45 und p23=-65 mit den Elevatoren

und dem Ergebnis

Diese Matrix ist Startpunkt der zweiten und letzten Reduktion mit dem Nullenkreuz

 1   -35  0  35   B     →        -35  0  0   B'
q21 0 5 0 0 5 0
 1   p12   p13       

das das alte unberührt lässt. Mit q21 = p12 = 0 und p13 = 1 entstehen die Elevatoren

und die Pivotmatrix

wobei

und

ohne Weiteres nachzuprüfen ist. Die Elevatoren bilden eine Absteigende Folge von Elevatoren und daher können die Inversen ihrer Produkte durch Übertragung der signifikanten Spalten bzw. Zeilen nach Vorzeichenumkehr auf den Nebendiagonalen direkt aufgeschrieben werden:

Pivotregulierung

[Bearbeiten | Quelltext bearbeiten]

Mit der Pivotregulierung wird das Pivotelement durch Spalten- oder Zeilenkombination auf einen vorgegebenen Wert, oft eins, eingestellt.[1]:86 Die Pivotregulierung ist bei einer Matrix mit Rang r höchstens r−1 mal durchführbar; ihr Aufwand beträgt maximal n2/2 Operationen und ist gegenüber dem mit der dritten Potenz von n gehenden Aufwand für die Reduktionen mit Nullenkreuzen vernachlässigbar. Die Pivotmatrix enthält am Ende nur Nullen und Einsen und nur genau ein von null und eins verschiedenes Element. Bei der Pivotregulierung einer hermiteschen Matrix müssen Spalten und Zeilen mit jeweils konjugiert komplexen Faktoren kombiniert werden, damit auch die regulierte Matrix hermitesch bleibt.[1]:87ff

Beispiel: Die hermitesche Matrix

mit der imaginären Einheit i soll in Diagonalgestalt überführt werden. Weil beide Diagonalelemente null sind, ist eine Pivotregulierung unabdingbar. Gesucht ist p = a + ib, sodass

p  0  2+i   A
1   2−i  0
1 p
   →   
    1   B12   B
B12 0
 

wird. Der Überstrich bedeutet komplexe Konjugation. Die Bedingung entspricht

B11 = 1 = (a + ib)(2 + i) + (a − ib)(2 − i) oder b = 2a − 1/2

Zweckmäßig ist hier a = 1/4 zu wählen[1]:88, sodass p reell wird. Das Ergebnis ist dann

und nach wie vor hermitesch.

Weil der Rang der Matrix zwei beträgt, ist nur diese eine Pivotregulierung möglich. Die Überführung in Diagonalgestalt erfolgt mit einem Nullenkreuz mit dem Pivotelement B11 = 1 und den Faktoren q21 = -2 + i bzw. p12 = −2 − i und dem Endergebnis

Generalschema einer Äquivalenztransformation

[Bearbeiten | Quelltext bearbeiten]

Die manuelle Durchführung einer Äquivalenztransformation kann in einer erweiterten Matrix

 In  A
 O  Im 

geschehen, wo O die Nullmatrix ist und im Folgenden nicht mehr aufgeführt wird. Die Matrizen Im bzw. In sind die Einheitsmatrizen, mit denen die n×m-Matrix A multipliziert werden kann, sodass In A Im = A. Durch die Grundoperationen, die beliebig oft wiederholt werden können, geht die erweiterte Matrix über in

 L   B 
R

wo B die Identität B = LAR erfüllt.[1]:63

Die Grundoperationen werden in der erweiterten Matrix durchgeführt, d. h.

  • die Zeilenoperationen werden simultan in L und B (anfangs In bzw. A) und
  • die Spaltenoperationen simultan in B und R (anfangs A bzw. Im) angewendet.

Beispiel: Vorgelegt ist die Matrix

.

Diese wird mit den Einheitsmatrizen in die erweiterte Matrix eingetragen:

 1   1  2 3
 1  4 5 6
 1 
 1 
 1 

Grundoperation 1: Spaltentausch 2 und 3 liefert

 1  1  3   2 
 1  4 6 5
 1 
 1 
 1 

Man prüft nach:

Grundoperation 2: Multiplikation der ersten Zeile mit Skalar a ergibt

 a  a  3a   2a 
 1  4 6 5
 1 
 1 
 1 

und wieder ist

Grundoperation 3: Subtraktion der mit 4a multiplizierten ersten Zeile von der zweiten ergibt

a a  3a   2a 
 -4   1  0 -6 -3
 1 
 1 
 1 

entsprechend

Gauß’sches Eliminationsverfahren

[Bearbeiten | Quelltext bearbeiten]

Das Ziel der Äquivalenztransformation einer Matrix A ist beim Gauß’schen Eliminationsverfahren die Identität

PA = LR

mit Permutationsmatrix P, normierter unterer Dreiecksmatrix L und oberer Dreiecksmatrix R. Für das Generalschema einer Äquivalenztransformation wird das umgeformt in

PAS = L

mit der oberen Dreiecksmatrix S = R−1. Die erweiterte Matrix im Generalschema soll entsprechend

 P   L 
S

werden. Diese Struktur wird erreicht, indem

  1. die Permutationen sich auf Zeilenoperationen beschränken,
  2. die Überführung in Dreiecksform mit Linearkombinationen ausschließlich der Spalten geschieht, und
  3. die Normierung der unteren Dreiecksmatrix L am Schluss durch Multiplikation der Spalten erfolgt.

Im zweiten Schritt entsteht eine Absteigende Folge von Elevatoren mit ihren günstigen Eigenschaften nur dann, wenn die Linearkombinationen der Spalten ohne Unterbrechung durch Spaltentausch oder Spaltenmultiplikation durchgeführt werden.

Beispiel:

Die Gleichung

ist zu lösen. Das Generalschema führt in fünf Schritten auf die gewünschte Form (Pivots kursiv hervorgehoben):

  Reduktion Zeile 2, Zeilentausch 1↔2
 ↗   1  0  0  0   0  3  2  2
 →   0  1  0  0   -1  -1  -1  -1
    0  0  1  0   3  6  3  -3
    0  0  0  1   7  -5  1  6
     1  0  0  0
 0   1   0   0 
 0  0  1  0
 0  0  0  1
z1  1  -1  -1  -1
   
  Reduktion Zeile 3, Zeilentausch 2↔3
    0  1  0  0   -1  0  0  0
 ↗   1  0  0  0   0  3  2  2
 →   0  0  1  0   3  3  0  -6
    0  0  0  1   7  -12  -6  -1
     1  -1  -1  -1
 0   1   0   0 
 0  0  1  0
 0  0  0  1
z2  0  1  0  2
   
  Reduktion Zeile 3
    0  1  0  0   -1  0  0  0
    0  0  1  0   3  3  0  0
 →   1  0  0  0   0  3  2  8
    0  0  0  1   7  -12  -6  -25
     1  -1  -1  -3
 0   1   0   2 
 0  0  1  0
 0  0  0  1
z3  0  0  1  -4
  Normierung
    0  1  0  0   -1  0  0  0
    0  0  1  0   3  3  0  0
    1  0  0  0   0  3  2  0
    0  0  0  1   7  -12  -6  -1
     1  -1  -1  1
 0   1   0   2 
 0  0  1  -4
 0  0  0  1
d =   -1  1/3  1/2  -1
   
  Endergebnis
 0  1  0  0   1  0  0  0  L
 0  0  1  0   -3  1  0  0
 1  0  0  0   0  1  1  0
 0  0  0  1   -7  -4  -3  1
P  -1  -1/3  -1/2  -1
  S  0   1/3   0   -2 
 0  0  1/2  4
 0  0  0  -1
         

Die Zeilen z1,2,3 entsprechen drei Zeilenelevatoren ρ1,2,3 und die Normierung mit den Einträgen in d entspricht in ihrer Wirkung einer Diagonalmatrix D = diag(d). Die Matrix S ergibt sich aus deren Produkt:

S = ρ1ρ2ρ3D    →   S−1 = R = D−1(ρ1ρ2ρ3)−1

Die Inverse des Klammerausdrucks, der eine Absteigende Folge von Elevatoren enthält, kann sofort aufgeschrieben werden: Die Zeilen z1,2,3 werden mit umgekehrtem Vorzeichen in eine 4×4-Nullmatrix übertragen, sodass die kursiv hervor gehobenen Pivots auf deren Hauptdiagonale liegen, und die Hauptdiagonale mit Einsen belegt. Es entsteht die Inverse des Klammerausdrucks

Mit ihr und der Diagonalmatrix mit den Kehrwerten aus d, die die Zeilen dieser Inversen skalieren, berechnet sich

Damit lautet das Gauß’sche Eliminationsverfahren in Matrixform:

Das vorliegende Problem Ax = b wird mit P multipliziert, resultierend in PAx = Pb, und PA = LR eingesetzt: LRx = Pb. Aus Ly = Pb = (-10 12 20 24) ergibt sich y = (-10 -18 38 -4) durch Vorwärtseinsetzen und Rx = y liefert durch Rückwärtseinsetzen die Lösung x = (1 2 3 4).

Die Lösung kann abgekürzt werden, indem auf die geordnete Dreiecksstruktur von R und L verzichtet wird und A in eine Pivotmatrix transformiert wird, was in drei Schritten gelingt:

  Reduktion Zeile 2 und Spalte 1
 1  0 0 0 0 3 2 2
1  0  1  0 0  -1   -1   -1  -1
0 0  1  0 3 6 3  -3 
0 0 0  1  7 -5 1 6
1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 1
1 -1 -1 -1
   
Reduktion Zeile 3 und Spalte 2
-1   1  0 0 0 0 3 2 2
0 1 0 0  -1  0 0 0
1  0 3 1 0 0 3 0 -6
 0   7   0  1 0 -12 -6 -1
1 -1 -1 -1
0 1 0 0
0 0 1 0
0 0 0 1
0 1 0 2
Reduktion Zeile 1 und Spalte 3
1   1  -3  -1  0 0 0 2 8
0 1 0 0 -1 0 0 0
0 3 1 0 0 3 0 0
 0   19   4   1  0 0 -6 -25
1 -1 -1 -3
0 1 0 2
0 0 1 0
0 0 0 1
0 0 1 -4
         
Endergebnis
 1   -3   -1   0  0 0 2 0  Π
0 1 0 0  -1  0 0 0
0 3 1 0 0 3 0 0
3 10 1 1 0 0 0  -1 
S 1  -1   -1  1
0 1 0 2
0 0 1 -4
0 0 0 1
 

Die links der erweiterten Matrix stehenden Spalten und die unter der erweiterten Matrix stehenden Zeilen bilden je eine Absteigende Folge von Elevatoren, sodass die Produkte der Elevatoren S bzw. T einfach zu invertieren sind. Nämlich durch Eintrag dieser Spalten bzw. Zeilen mit umgekehrtem Vorzeichen in eine Nullmatrix, sodass die kursiv geschriebenen Pivots auf der Hauptdiagonale zu liegen kommen, und abschließende Belegung der Hauptdiagonalen mit Einsen. Mit L = S−1 sowie R = T−1 entsteht

SAT = Π → A = LΠR

oder ausgeschrieben

Vorwärtseinsetzen in Lz = b in der Reihenfolge 2,1,3,4 ergibt den Vektor z = (38 -10 -18 -4), Πy = z liefert y = (10 -6 19 4) und Rx = y schließlich durch Rückwärtseinsetzen die Lösung x = (1 2 3 4).

Die Form A = LΠR kann bei manueller Rechnung leichter mit dem Algorithmus von Banachiewicz berechnet werden, der vor der Erfindung der Computer dem hier gezeigten Algorithmus überlegen war.[1]:82

Gauß-Jordan-Algorithmus

[Bearbeiten | Quelltext bearbeiten]

Beim Gauß-Jordan-Algorithmus werden in der erweiterten Matrix im Generalschema einer Äquivalenztransformation

 L   B 
R

nur zwei Felder benutzt,

entweder   
 L   B 
   oder   
 B 
R

Im ersten Fall müssen die Spalten von L, im zweiten die Zeilen von R linear unabhängig sein, damit eine Transformation in eine Pivotmatrix gelingen kann. Der Algorithmus ist mit einem Risiko behaftet und muss ergebnislos abgebrochen oder irgendwie anders weitergeführt werden, wenn die lineare Unabhängigkeit nicht gegeben ist und infolge dessen während der Rechnung eine Nullspalte bzw. Nullzeile auftritt.

Anders als im Gauß’schen Eliminationsverfahren sind die signifikanten Spalten bzw. Zeilen der Elevatoren im Allgemeinen voll besetzt.[1]:83

Eigenspalten und Eigenzeilen einer singulären Matrix

[Bearbeiten | Quelltext bearbeiten]

Eine singuläre Matrix hat den Eigenwert null und alle Vektoren, die von der Matrix auf den Nullvektor abgebildet werden, erzeugen den Eigenraum zum Eigenwert null. Eine Vektorraumbasis zu diesem Eigenraum kann mit dem Generalschema einer Äquivalenztransformation ermittelt werden. Dieses eignet sich allgemeiner zur Berechnung aller Vektoren, die von einer beliebigen, auch nicht-quadratischen Matrix auf einen Nullvektor abgebildet werden.

Die n×m-Matrix A wird dazu mit Nullenkreuzen in eine Pivotmatrix Π überführt:[1]:107

LAR = Π

Eine Nullzeile von Π ist eine Zeile, die nur aus Nullen besteht, und eine Nullspalte eine nur aus Nullen bestehende Spalte von Π:

L11  L1n  0 0 0  Π
Li1  Lin  0 0 0 0 0
Lj1  Ljn  0 0 0 0 0
 Ln1   Lnn  0 0 0
L R11 R R R R1m
 Rm1 R R R Rmm 

In der erweiterten Matrix oben ist ein Beispiel mit zwei Nullzeilen und drei Nullspalten aufgeführt, die gelb unterlegt sind. In den grau unterlegten Feldern von Π ist in jeder Zeile und Spalte genau ein Element ungleich null vorhanden. Ist wie oben die i-te Zeile Nullzeile, dann ist Πik = 0 für k = 1,…,m. Der Vektor ei der Standardbasis wird dann in den Nullvektor o überführt:

eiΠ = eiLAR = o

Multiplikation von rechts mit R−1 liefert mit li := eiL:

eiLA = li A = o

Das heißt, dass die i-te Zeile li von L Linkseigenvektor von A zum Eigenwert null ist. Rechtsmultiplikation von LAR = Π mit dem Vektor eα der Standardbasis und Linksmultiplikation mit L−1 liefert analog

AReα =: Arα = o

wenn die α-te Spalte von Π, wie im obigen Beispiel, eine Nullspalte ist. Der Vektor rα ist die α-te Spalte von R und Rechtseigenvektor von A zum Eigenwert null. Wenn r der Rang von A ist, dann besitzt die n×m-Matrix A zum Eigenwert null n−r Linkseigenvektoren und m−r Rechtseigenvektoren. Diese werden Eigenzeilen bzw. Eigenspalten von A genannt und sind jeweils unter sich linear unabhängig, weil die Einheitsvektoren der Standardbasen es sind. Die Gesamtheit der Eigenzeilen spannt einen Links­eigenraum (auch Linksnullraum oder Zeilen­kern) der Dimension n−r und die Gesamtheit der Eigenspalten einen Rechtseigenraum (auch Rechtsnullraum oder Spaltenkern) der Dimension m−r auf.[1]:107 Diese Räume enthalten alle Vektoren, die von A in Nullvektoren transformiert werden.

Beispiel:

Vorgelegt ist die Matrix

Sie wird mit einem Nullenkreuz zur Pivotmatrix:

  Reduktion Zeile 2 und Spalte 3
 6   1  0  0   48  -24  -6
 1   0  1  0   -8  4  1
 -18   0  0  1   -144  72  18
   1  0  0
 0   1   0 
 0  0  1
   8  -4  1
   →   
  Endergebnis
 1  6  0   0  0  0  Π
 0  1  0   0  0  1
 0  -18  1   0  0  0
L  1  0  0
 0   1   0 
   8  -4  1

In der Pivotmatrix Π sind die Zeilen eins und drei Nullzeilen und die Spalten eins und zwei Nullspalten. Die Identitäten

(1 6 0)A = (0 -18 1)A = (0 0 0)
A(1 0 8) = A(0 1 -4) = (0 0 0)

sind unschwer nachzuprüfen. Alle Vektoren u und v, die von A vermöge

uA = (0 0 0)   bzw.    Av = (0 0 0)

in Nullvektoren abgebildet werden, besitzen die Form

u = α(1 6 0) + β(0 -18 1)   und    v = α(1 0 8) + β(0 1 -4)

mit irgendwelchem α, β ∈ ℝ.

Ermittlung des Ranges einer Matrix

[Bearbeiten | Quelltext bearbeiten]

Eine n×m-Matrix A kann durch Nullenkreuze in eine Pivotmatrix Π überführt werden:

LAR = Π

Die Anzahl der von null verschiedenen Einträge in Π ist gleich dem Rang r der Matrix und die Transformation in die Pivotmatrix benötigt höchstens r Nullenkreuze.[1]:75f Mit den Grundoperationen Permutation und Multiplikation mit einem Skalar kann die Pivotmatrix in die Normalform

 Ir     0 
 0     0 

überführt werden, die in der oberen linken Ecke die Einheitsmatrix Ir vom Rang r und sonst nur Nullen enthält.[1]:66 Ein Beispiel zur Berechnung der Pivotmatrix findet sich hier im Abschnitt Eigenspalten und Eigenzeilen einer singulären Matrix und bei Rang einer Matrix / Normalform.

Algorithmus von Banachiewicz

[Bearbeiten | Quelltext bearbeiten]

Der Algorithmus von Banachiewicz erzeugt die Nullenkreuze in einer Matrix A, indem bestimmte Dyaden von A subtrahiert werden. Die Zerlegung A = LΠR mit einer Pivotmatrix Π entsteht dabei direkt und mit weniger Schreibarbeit als beim Gauß’schen Eliminationsverfahren. Der Algorithmus kann mit Vorteil bei der Invertierung einer Summe zweier Matrizen eingesetzt werden[1]:452. Die Zerlegung findet sich für symmetrische Matrizen zuerst bei Doolittle, später in etwas abgewandelter Form bei Cholesky und für nichtsymmetrische Matrizen erstmals bei Banachiewicz.[1]:82

Zugrunde gelegt wird der Körper K mit der Standardbasis e1,…,n des Kn und ε1,…,m des Km. Bei einer beliebigen n×m-Matrix A mit inversem Pivotelement Zij = 1/Aij, dem 1×m-Zeilenvektor pj = Zij eiA und n×1-Spaltenvektor qi = Zij A εj ist in der Matrix

A1 = A − D1    mit    D1 = Aij qi pj

die Pivotzeile i und Pivotspalte j mit Nullen belegt. Das Verfahren wird mit A1 wiederholt, sodass A2 = A1 − D2 ein weiteres Nullenkreuz enthält, und so fort, bis nach spätestens r Schritten

Ar = A − D1 − D2 … − Dr = O

zur Nullmatrix O geworden ist und das Verfahren endet. Die Summe der Dyaden kann

k Dk = LΠR    mit    L = ∑qi ei,   Π = ∑Aij ei εj    und    R = ∑εj pj

geschrieben werden, wo die Indizes in den Summen ∑ jeweils die in den Reduktionsschritten vorkommenden Werte durchlaufen. Zum Schluss ist nach Konstruktion

A = LΠR

Beispiel: Die Zerlegung der Matrix

aus dem Beispiel im Abschnitt Gauß’sches Eliminationsverfahren läuft wie folgt. Mit dem ersten Pivot an der Stelle 21 mit Z21 = 1/A21 = -1 bekommt man

Das Pivot 3 an der Stelle 32 von A1 liefert

und das Pivot 2 an der Stelle 13 von A2 ergibt

Die vierte Reduktion hinterlässt die Nullmatrix:

Die Matrizen

können parallel zur schrittweisen Reduktion in Phantommatrizen aufgebaut werden. Wie gefordert ist A = LΠR oder ausgeschrieben:

  1. a b c d e f g h i j k l m n o p q r s t u v w x R. Zurmühl, S. Falk: Matrizen und ihre Anwendungen 1. Grundlagen, Für Ingenieure, Physiker und Angewandte Mathematiker. Springer, Berlin u. a. 1997, ISBN 3-540-61436-2.
  2. J. Liesen, V. Mehrmann: Lineare Algebra. Ein Lehrbuch über die Theorie mit Blick auf die Praxis. Springer Spektrum, Wiesbaden 2015, ISBN 978-3-658-06609-3, doi:10.1007/978-3-658-06610-9.