Determinantenberechnung

Determinantenberechnungsmethoden

Determinantenberechnung

Determinantenberechnungsmethoden

Nach den Grundlagen der Determinante geht es nun um die praktische Berechnung. Welche Methode geeignet ist, hängt von der Form der Matrix ab.

Für kleine Matrizen können wir direkte Formeln verwenden. Für größere Matrizen benötigen wir jedoch effizientere Strategien.

Grundlegender Fall einer Matrix erster Ordnung

Für Matrizen der Größe $1 \times 1$ ist die Determinante sehr einfach. Wenn $A \in \mathbb{R}^{1 \times 1}$ mit $A = (a_{11})$ , dann:

\det A = a_{11}

Dies ist der grundlegendste Fall, der als Grundlage für die Berechnung von Determinanten größerer Matrizen dient.

Submatrix-Konzept

Vor der Kofaktorentwicklung benötigen wir den Begriff der Untermatrix. Für $A \in \mathbb{R}^{n \times n}$ und $i, j \in \{1, 2, \ldots, n\}$ entsteht die Untermatrix $A_{ij}$ der Größe $(n-1) \times (n-1)$ , indem Zeile $i$ und Spalte $j$ aus $A$ entfernt werden.

Betrachten wir ein Beispiel für eine $3 \times 3$ -Matrix. Angenommen, wir haben:

A = \begin{pmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{pmatrix}

Um die Submatrix $A_{12}$ zu erhalten, entfernen wir Zeile $1$ und Spalte $2$ :

A_{12} = \begin{pmatrix} \cancel{a_{11}} & \cancel{a_{12}} & \cancel{a_{13}} \\ a_{21} & \cancel{a_{22}} & a_{23} \\ a_{31} & \cancel{a_{32}} & a_{33} \end{pmatrix}

Für die Submatrix $A_{23}$ entfernen wir Zeile $2$ und Spalte $3$ :

A_{23} = \begin{pmatrix} a_{11} & a_{12} & \cancel{a_{13}} \\ \cancel{a_{21}} & \cancel{a_{22}} & \cancel{a_{23}} \\ a_{31} & a_{32} & \cancel{a_{33}} \end{pmatrix}

Dieser Vorgang gilt für alle Kombinationen von Zeilen und Spalten, die entfernt werden.

Kofaktorentwicklung

Die gebräuchlichste direkte Methode zur Berechnung von Determinanten ist die Kofaktorentwicklung. Wir können nach einer beliebigen festen Zeile $i$ entwickeln:

\det A = \sum_{j=1}^{n} (-1)^{i+j} a_{ij}\det A_{ij}

Alternativ können wir nach einer beliebigen festen Spalte $j$ entwickeln:

\det A = \sum_{i=1}^{n} (-1)^{i+j} a_{ij}\det A_{ij}

Der Term $(-1)^{i+j}\det A_{ij}$ ist der Kofaktor von $a_{ij}$ . Der Faktor $(-1)^{i+j}$ erzeugt das abwechselnde Schachbrettmuster der Vorzeichen. Eine Zeile oder Spalte mit vielen Nullen verringert die Anzahl der zu berechnenden Minoren.

Beispiel für die Kofaktorentwicklung dritter Ordnung

Für eine $3 \times 3$ -Matrix sieht die Kofaktorentwicklung beispielsweise so aus:

A = \begin{pmatrix} 2 & 1 & 3 \\ 0 & 4 & 1 \\ 1 & 2 & 0 \end{pmatrix}

Wir wählen die erste Zeile zur Erweiterung:

\det A = 2 \cdot (-1)^{1+1} \det A_{11} + 1 \cdot (-1)^{1+2} \det A_{12} + 3 \cdot (-1)^{1+3} \det A_{13}

Wir können nach jeder Zeile oder Spalte entwickeln. Meist wählen wir eine Zeile oder Spalte mit vielen Nullen, weil dadurch weniger Terme berechnet werden müssen.

Dreieckige und diagonale Matrizen

Für einige spezielle Matrizentypen wird die Determinantenberechnung sehr einfach:

Obere Dreiecksmatrix

Für obere Dreiecksmatrix $R$ :

R = \begin{pmatrix} r_{11} & * & \cdots & * \\ 0 & r_{22} & \cdots & * \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & r_{nn} \end{pmatrix}

Seine Determinante ist:

\det R = r_{11} \cdot r_{22} \cdot \ldots \cdot r_{nn}

Untere Dreiecksmatrix

Für die untere Dreiecksmatrix $L$ :

L = \begin{pmatrix} l_{11} & 0 & \cdots & 0 \\ * & l_{22} & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ * & * & \cdots & l_{nn} \end{pmatrix}

Seine Determinante ist:

\det L = l_{11} \cdot l_{22} \cdot \ldots \cdot l_{nn}

Diagonale Matrix

Für Diagonalmatrix $D$ :

D = \begin{pmatrix} d_{11} & 0 & \cdots & 0 \\ 0 & d_{22} & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & d_{nn} \end{pmatrix}

Seine Determinante ist:

\det D = d_{11} \cdot d_{22} \cdot \ldots \cdot d_{nn}

Für alle drei Matrizentypen ist die Determinante gleich dem Produkt aller Hauptdiagonalelemente.

Elementarmatrizen

Elementarmatrizen sind Matrizen, die aus der Identitätsmatrix mit einer elementaren Zeilenoperation erhalten werden. Die Determinanten elementarer Matrizen haben leicht zu berechnende Werte:

Zeilenskalierungsmatrix $S_i(\lambda)$ , mit $\lambda \neq 0$ , die Zeile $i$ mit $\lambda$ multipliziert:

$\det S_i(\lambda) = \lambda$
Zeilenvertauschungsmatrix $Q_i^j$ , die die Zeilen $i$ und $j$ vertauscht:

$\det Q_i^j = -1$
Transvektionsmatrix $P_i^j(\lambda)$ , die die Operation $R_i \leftarrow R_i + \lambda R_j$ ausführt:

Eine einzelne Zeilenvertauschung wechselt das Vorzeichen der Determinante. Das Addieren eines Vielfachen einer Zeile zu einer anderen lässt die Determinante dagegen unverändert.

Gaußsche Eliminierung zur Determinantenberechnung

Bei einer dichten Matrix ist die Gauß-Elimination, beziehungsweise eine LU-Zerlegung, eine der effizientesten Methoden. Sie überführt die Matrix in obere Dreiecksform; anschließend werden die Diagonalelemente multipliziert.

Angenommen, wir verwenden nur Zeilenadditionen und Zeilenvertauschungen, um $A$ in eine obere Dreiecksmatrix $R$ zu überführen. Bei $p$ Zeilenvertauschungen gilt:

\det A = (-1)^p \cdot \det R

Da $R$ eine obere Dreiecksmatrix ist:

\det R = r_{11} \cdot r_{22} \cdot \ldots \cdot r_{nn}

Deshalb:

\det A = (-1)^p \cdot r_{11} \cdot r_{22} \cdot \ldots \cdot r_{nn}

Falls ein Algorithmus während der Elimination eine Zeile skaliert, muss dieser Skalierungsfaktor ebenfalls erfasst und aus dem Endergebnis herausgerechnet werden. In numerischen Berechnungen verwendet man üblicherweise partielle Pivotisierung, um einen Nullpivot zu vermeiden und den Einfluss von Rundungsfehlern zu verringern.

Methodeneffizienz

Für eine dichte $n \times n$ -Matrix benötigt die Elimination oder LU-Zerlegung ungefähr $\frac{2}{3}n^3 + O(n^2)$ Gleitkommaoperationen. Das anschließende Multiplizieren der Diagonaleinträge erfordert nur $O(n)$ zusätzliche Arbeit. Eine naive rekursive Kofaktorentwicklung kann dagegen wie $O(n!)$ wachsen.

Für große unstrukturierte Matrizen ist die Elimination mit Pivotisierung daher deutlich praktischer als die rekursive Kofaktorentwicklung.

Vollständiges Berechnungsbeispiel

Das folgende Beispiel zeigt die Determinantenberechnung mit Gauß-Elimination:

A = \begin{pmatrix} 0 & 3 & 3 \\ 2 & 2 & 0 \\ 1 & 0 & 1 \end{pmatrix}

Schritt $1$ : Vertausche die Zeilen $1$ und $3$ , um einen Pivot ungleich Null zu erhalten:

\begin{pmatrix} 1 & 0 & 1 \\ 2 & 2 & 0 \\ 0 & 3 & 3 \end{pmatrix}

Schritt $2$ : Eliminiere die erste Spalte, indem du $2$ mal Zeile $1$ von Zeile $2$ subtrahierst:

\begin{pmatrix} 1 & 0 & 1 \\ 0 & 2 & -2 \\ 0 & 3 & 3 \end{pmatrix}

Schritt $3$ : Eliminiere die zweite Spalte, indem du $1{,}5$ mal Zeile $2$ von Zeile $3$ subtrahierst:

\begin{pmatrix} 1 & 0 & 1 \\ 0 & 2 & -2 \\ 0 & 0 & 6 \end{pmatrix} = R

Da es einen Zeilentausch gibt ( $p = 1$ ):

\det A = (-1)^1 \cdot \det R

\det P_i^j(\lambda) = 1