Nachlesen

Cramersche Regel

Die Cramersche Regel ist ein Verfahren zur Lösung von linearen Gleichungssystemen mit n Gleichungen und n Unbekannten. Die Voraussetzung für die Anwendung der Cramerschen Regel ist, dass die Determinante der Koeffizientenmatrix des LGS von null verschieden ist. Unter dieser Bedingung lässt sich jede Unbekannte als Quotient zweier Determinanten angeben.

Die Regel ist nach dem Schweizer Mathematiker Gabriel Cramer (1704–1752) benannt, der sie 1750 in seiner Einleitung zur Kurventheorie Introduction à l'analyse des lignes courbes algébriques veröffentlichte. Als numerisches Lösungsverfahren ist die Cramersche Regel aufgrund ihres hohen Rechenaufwands weniger geeignet; ihre Bedeutung liegt vor allem im theoretischen Bereich.

Definition

Gegeben sei eine natürliche Zahl $n \in \N$, ein Körper $\mathcal{K}$, aus dem sämtliche Elemente stammen – beispielsweise rationale, reelle oder komplexe Zahlen –, sowie ein lineares Gleichungssystem mit $n$ Gleichungen und $n$ Unbekannten $x_1, \ldots, x_n \in \mathcal{K}$:

\begin{align*} \begin{alignedat}{4} a_{11}x_1 &\ + &\ \ldots &\ + &\ a_{1n}x_n &\ = &\ b_1 \\[0.5em] \vdots\quad &\ &\ \ddots &\ &\ \vdots\quad &\ &\ \vdots\ \ \\[0.5em] a_{n1}x_1 &\ + &\ \ldots &\ + &\ a_{nn}x_n &\ = &\ b_n. \end{alignedat} \end{align*}

In Matrixform lautet dieses Gleichungssystem $Ax = b$ mit

A = \begin{bmatrix} a_{11} & \ldots & a_{1n} \\[0.25em] \vdots & \ddots & \vdots \\[0.25em] a_{n1} & \ldots & a_{nn} \end{bmatrix},\ x = \begin{pmatrix} x_1 \\[0.25em] \vdots \\[0.25em] x_n \end{pmatrix} \text{ und } b = \begin{pmatrix} b_1 \\[0.25em] \vdots \\[0.25em] b_n \end{pmatrix}.

Die Cramersche Regel besagt: Ist die Koeffizientenmatrix $A$ invertierbar und besitzt folglich die Determinante $\det(A) \neq 0_\mathcal{K}$, so ist das lineare Gleichungssystem eindeutig lösbar. Für die Einträge $x_i$ des Lösungsvektors $x = {(x_1, \ldots, x_n)}^T$ gilt dann (für $1 \leq i \leq n$):

x_i = \frac{\det(A_i)}{\det(A)}

Die Matrizen $A_i$ entstehen aus der Matrix $A$, indem die $i$-te Spalte durch den Vektor $b$ ersetzt wird.

A_i = \begin{bmatrix} a_{11} & \ldots & a_{1,i-1} & b_1 & a_{1,i+1} & \ldots & a_{1n} \\[0.25em] \vdots & \ddots & \vdots & \vdots & \vdots & \ddots & \vdots \\[0.25em] a_{n1} & \ldots & a_{n,i-1} & b_n & a_{n,i+1} & \ldots & a_{nn} \end{bmatrix}

Beispiele

Beispiel 1: Lineares Gleichungssystem mit zwei Unbekannten

Im ersten Beispiel wird die Cramersche Regel verwendet, um das folgende lineare Gleichungssystem mit zwei Gleichungen und zwei Unbekannten zu lösen.

\begin{align*} \begin{alignedat}{3} x_1 &\ + &\ x_2 &\ = &\ 1 \\[0.5em] 2x_1 &\ + &\ 3x_2 &\ = &\ 5 \end{alignedat} \end{align*}

Für die $2 \times 2$ Koeffizientenmatrix $A$ und den Vektor $b$ ergeben sich somit:

A = \begin{bmatrix} 1 & 1 \\ 2 & 3 \end{bmatrix} \text{ und } b = \begin{pmatrix} 1 \\ 5 \end{pmatrix}.

Zunächst wird die Determinante der Matrix $A$ berechnet, um zu überprüfen, ob die Cramersche Regel angewendet werden kann. Für die gesuchte Determinante $\det(A)$ gilt:

\begin{align*} \det(A) &= 1 \cdot 3 - 1 \cdot 2 \\[0.5em] &= 1. \end{align*}

Da $\det(A) = 1 \neq 0$ gilt, kann das Gleichungssystem mithilfe der Cramerschen Regel (eindeutig) gelöst werden. Die hierfür benötigten Hilfsmatrizen $A_1$ und $A_2$ ergeben sich, indem die erste bzw. die zweite Spalte von $A$ durch $b$ ersetzt wird.

\begin{align*} A_1 &= \begin{bmatrix} 1 & 1 \\ 5 & 3 \end{bmatrix} \\[0.75em] A_2 &= \begin{bmatrix} 1 & 1 \\ 2 & 5 \end{bmatrix} \end{align*}

Für die Determinanten der Matrizen $A_1$ und $A_2$ ergibt sich:

\begin{align*} \det(A_1) &= 1 \cdot 3 - 1 \cdot 5 \\[0.5em] &= -2 \\[0.75em] \det(A_2) &= 1 \cdot 5 - 1 \cdot 2 \\[0.5em] &= 3. \end{align*}

Mit der Cramerschen Regel können abschließend die gesuchten Lösungen des linearen Gleichungssystem bestimmt werden; es gilt:

\begin{align*} x_1 &= \frac{\det(A_1)}{\det(A)} \\[0.5em] &= \frac{-2}{1} \\[0.5em] &= -2 \\[0.75em] x_2 &= \frac{\det(A_2)}{\det(A)} \\[0.5em] &= \frac{3}{1} \\[0.5em] &= 3. \end{align*}

Das lineare Gleichungssystem besitzt somit als einzige Lösung $x_1 = -2$ und $x_2 = 3$.

Beispiel 2: Lineares Gleichungssystem mit drei Unbekannten

Das zweite Beispiel demonstriert die Cramersche Regel am folgenden linearen Gleichungssystem mit drei Gleichungen und drei Unbekannten.

\begin{align*} \begin{alignedat}{4} x_1 &\ - &\ 2x_2 &\ - &\ 4x_3 &\ = &\ 2 \\[0.5em] &\ &\ 2x_2 &\ + &\ 2x_3 &\ = &\ -4 \\[0.5em] 2x_1 &\ - &\ 2x_2 &\ - &\ 5x_3 &\ = &\ 1 \end{alignedat} \end{align*}

Für die $3 \times 3$ Koeffizientenmatrix $A$ und den Vektor $b$ ergeben sich somit:

A = \begin{bmatrix} 1 & -2 & -4 \\ 0 & 2 & 2 \\ 2 & -2 & -5 \end{bmatrix} \text{ und } b = \begin{pmatrix} 2 \\ -4 \\ 1 \end{pmatrix}.

Zunächst wird die Determinante der Matrix $A$ berechnet, um zu überprüfen, ob die Cramersche Regel angewendet werden kann. Für die gesuchte Determinante $\det(A)$ ergibt sich mithilfe der Regel von Sarrus:

\begin{align*} \det(A) &= 1 \cdot 2 \cdot (-5) + (-2) \cdot 2 \cdot 2 + (-4) \cdot 0 \cdot (-2) \\[0.5em] &\quad {} - (-4) \cdot 2 \cdot 2 - 1 \cdot 2 \cdot (-2) - (-2) \cdot 0 \cdot (-5) \\[0.5em] &= -10 - 8 + 0 + 16 + 4 - 0 \\[0.5em] &= 2. \end{align*}

Da $\det(A) = 2 \neq 0$ gilt, kann das Gleichungssystem mithilfe der Cramerschen Regel (eindeutig) gelöst werden. Die hierfür benötigten Hilfsmatrizen $A_1$, $A_2$ und $A_3$ ergeben sich, indem die erste, zweite bzw. die dritte Spalte von $A$ durch $b$ ersetzt wird.

\begin{align*} A_1 &= \begin{bmatrix} 2 & -2 & -4 \\ -4 & 2 & 2 \\ 1 & -2 & -5 \end{bmatrix} \\[0.75em] A_2 &= \begin{bmatrix} 1 & 2 & -4 \\ 0 & -4 & 2 \\ 2 & 1 & -5 \end{bmatrix} \\[0.75em] A_3 &= \begin{bmatrix} 1 & -2 & 2 \\ 0 & 2 & -4 \\ 2 & -2 & 1 \end{bmatrix} \end{align*}

Für die Determinanten der Matrizen $A_1$, $A_2$ und $A_3$ ergibt sich:

\begin{align*} \det(A_1) &= 2 \cdot 2 \cdot (-5) + (-2) \cdot 2 \cdot 1 + (-4) \cdot (-4) \cdot (-2) \\[0.5em] &\quad {} - (-4) \cdot 2 \cdot 1 - 2 \cdot 2 \cdot (-2) - (-2) \cdot (-4) \cdot (-5) \\[0.5em] &= -20 - 4 - 32 + 8 + 8 + 40 \\[0.5em] &= 0 \\[0.75em] \det(A_2) &= 1 \cdot (-4) \cdot (-5) + 2 \cdot 2 \cdot 2 + (-4) \cdot 0 \cdot 1 \\[0.5em] &\quad {} - (-4) \cdot (-4) \cdot 2 - 1 \cdot 2 \cdot 1 - 2 \cdot 0 \cdot (-5) \\[0.5em] &= 20 + 8 + 0 - 32 - 2 - 0 \\[0.5em] &= -6 \\[0.75em] \det(A_3) &= 1 \cdot 2 \cdot 1 + (-2) \cdot (-4) \cdot 2 + 2 \cdot 0 \cdot (-2) \\[0.5em] &\quad {} - 2 \cdot 2 \cdot 2 - 1 \cdot (-4) \cdot (-2) - (-2) \cdot 0 \cdot 1 \\[0.5em] &= 2 + 16 + 0 - 8 - 8 - 0 \\[0.5em] &= 2 \\[0.75em] \end{align*}

Mit der Cramerschen Regel können abschließend die gesuchten Lösungen des linearen Gleichungssystem bestimmt werden; es gilt:

\begin{align*} x_1 &= \frac{\det(A_1)}{\det(A)} \\[0.5em] &= \frac{0}{2} \\[0.5em] &= 0 \\[0.75em] x_2 &= \frac{\det(A_2)}{\det(A)} \\[0.5em] &= \frac{-6}{2} \\[0.5em] &= -3 \\[0.75em] x_3 &= \frac{\det(A_3)}{\det(A)} \\[0.5em] &= \frac{2}{2} \\[0.5em] &= 1. \end{align*}

Das lineare Gleichungssystem besitzt somit als einzige Lösung $x_1 = 0$, $x_2 = -3$ und $x_3 = 1$.

Beweis

Für den Beweis der Cramerschen Regel wird zunächst eine Hilfsmatrix $X_i$ eingeführt (mit $1 \leq i \leq n$), die aus der Einheitsmatrix $E_n$ dadurch entsteht, dass die $i$-te Spalte durch den Lösungsvektor $x$ des Gleichungssystems $Ax = b$ ersetzt wird.

X_i = \begin{bmatrix} 1 & \ldots & x_1 & \ldots & 0 \\[0.25em] \vdots & \ddots & \vdots & \ddots & \vdots \\[0.25em] 0 & \ldots & \underbrace{x_n}_{i\text{-te Spalte}} & \ldots & 1 \end{bmatrix}

Oder etwas kompakter:

X_i = \left[\begin{array}{ccccccc} \mid & & \mid & \mid & \mid & & \mid \\[0.25em] e_1 & \ldots & e_{i-1} & x & e_{i+1} & \ldots & e_n \\[0.25em] \mid & & \mid & \mid & \mid & & \mid \end{array}\right]

Die Multiplikation der Matrizen $A$ und $X_i$ liefert die Matrix $A_i$, deren $i$-te Spalte durch den Vektor $b$ ersetzt ist:

\begin{align*} A \cdot X_i &\overset{(1)}{=} \begin{bmatrix} a_{11} & \ldots & a_{1n} \\ \vdots & \ddots & \vdots \\ a_{n1} & \ldots & a_{nn} \end{bmatrix} \cdot \left[\begin{array}{ccccccc} \mid & & \mid & \mid & \mid & & \mid \\[0.25em] e_1 & \ldots & e_{i-1} & x & e_{i+1} & \ldots & e_n \\[0.25em] \mid & & \mid & \mid & \mid & & \mid \end{array}\right] \\[0.75em] &\overset{(2)}{=} \left[\begin{array}{ccccccc} a_{11} & \cdots & a_{1,i-1} & (a_{11}x_1 + \ldots + a_{1n}x_n) & a_{1,i+1} & \cdots & a_{1n} \\[0.25em] \vdots & \ddots & \vdots & \vdots & \vdots & \ddots & \vdots \\[0.25em] a_{n1} & \cdots & a_{n,i-1} & (a_{n1}x_1 + \ldots + a_{nn}x_n) & a_{n,i+1} & \cdots & a_{nn} \end{array}\right] \\[0.75em] &\overset{(3)}{=} \left[\begin{array}{ccccccc} a_{11} & \cdots & a_{1,i-1} & b_1 & a_{1,i+1} & \cdots & a_{1n} \\[0.25em] \vdots & \ddots & \vdots & \vdots & \vdots & \ddots & \vdots \\[0.25em] a_{n1} & \cdots & a_{n,i-1} & b_n & a_{n,i+1} & \cdots & a_{nn} \end{array}\right] \\[0.75em] &\overset{(4)}{=} A_i \end{align*}

Erklärungen zu den Schritten
(1)	Einsetzen der Matrizen $A$ und $X_i$
(2)	Multiplikation der Matrizen
(3)	Ersetzen von $a_{k1}x_1 + \ldots + a_{kn}x_n = b_k$ (für $1 \leq k \leq n$) Dies entspricht der $k$-ten Gleichung des linearen Gleichungssystems
(4)	Ersetzen der Matrix durch $A_i$

Für die Determinante der Matrix $X_i$ gilt $\det(X_i)=x_i$, wie durch Nachrechnen leicht überprüft werden kann – beispielsweise durch Entwicklung nach der $i$-ten Spalte mit dem Laplaceschen Entwicklungssatz, da die hierbei entstehenden Untermatrizen stets obere bzw. untere Dreiecksmatrizen sind, was die Berechnung stark vereinfacht. Mithilfe des Determinantenproduktsatzes und der geforderten Eigenschaft $\det(A) \neq 0_{\mathcal{K}}$ folgt:

\begin{align*} \det(A_i) &= \det(A \cdot X_i) \\[0.5em] &= \det(A) \cdot \det(X_i) \\[0.5em] &= \det(A) \cdot x_i \\[1em] \implies x_i &= \frac{\det(A_i)}{\det(A)} \end{align*}

Hinweis: Die Division durch $\det(A)$ im letzten Schritt kann etwas allgemeiner formuliert werden. Gemäß Voraussetzung muss $\det(A) \neq 0_\mathcal{K}$ gelten – es darf sich also nicht um das Nullelement des zugrundeliegenden Körpers $\mathcal{K}$ handeln. Hieraus folgt, dass das multiplikative Inverse $ {\det(A)}^{-1}$ existiert. Anstelle der Division durch $\det(A)$ kann die letzte Umformung somit ebenfalls über die Multiplikation mit dem Inversen $ {\det(A)}^{-1}$ erfolgen. Die Cramersche Regel kann folglich auch für Gleichungssysteme angewendet werden, deren Koeffizienten aus einem beliebigen Körper $\mathcal{K}$ stammen. Wird zusätzlich gefordert, dass es sich bei $\det(A)$ um eine Einheit handelt, so können die Elemente statt aus einem Körper auch aus einem kommutativen Ring stammen.

Bemerkungen zum Rechenaufwand

Das Lösen eines linearen Gleichungssystems mit $n$ Unbekannten mithilfe der Cramerschen Regel erfordert die Berechnung von $n + 1$ Determinanten. Der Rechenaufwand der Cramerschen Regel wird von diesen Determinantenberechnungen dominiert und hängt wesentlich vom eingesetzten Verfahren zum Bestimmen der Determinanten ab.

Bei Verwendung der Leibniz-Formel – Cramer hat sie ursprünglich eingesetzt – sind für jede einzelne Determinante $(n-1) \cdot n!$ Multiplikationen sowie $n! - 1$ Additionen erforderlich. Dasselbe gilt für den Laplaceschen Entwicklungssatz:

Bei einem Gleichungssystem mit vier Unbekannten entfallen allein auf die Berechnung der Determinanten bereits $5 \cdot 72 = 360$ Multiplikationen und $5 \cdot 23 = 115$ Additionen.
Bei fünf Unbekannten sind es bereits $6 \cdot 480 = 2880$ Multiplikationen und $6 \cdot 119 = 714$ Additionen.

Selbst mit einem effizienteren Algorithmus zur Determinantenberechnung – etwa über eine LU-Zerlegung – übersteigt der Rechenaufwand der Cramerschen Regel deutlich den Rechenaufwand des Gaußschen Eliminationsverfahrens.

Als numerisches Lösungsverfahren besitzt die Cramersche Regel daher weniger praktische Bedeutung. Sie ist vor allem ein theoretisches Hilfsmittel – etwa beim Beweis von Aussagen über die Struktur von Lösungsmengen oder in der symbolischen Mathematik, wo exakte Ausdrücke gefragt sind.