Cramer’sche Regel

aus Wikipedia, der freien Enzyklopädie

Du hast neue Nachrichten auf deiner Diskussionsseite.

Die Cramer’sche Regel oder Determinantenmethode ist eine mathematische Formel für die Lösung eines linearen Gleichungssystems. Sie ist bei der theoretischen Betrachtung linearer Gleichungssysteme hilfreich. Für die Berechnung einer Lösung ist der Rechenaufwand jedoch in der Regel zu hoch, da dabei verhältnismäßig viele Determinanten auftreten. Deshalb kommen dazu andere Verfahren aus der Numerischen Mathematik zum Einsatz. Die Cramer’sche Regel geht zurück auf Gabriel Cramer, der sie im Jahr 1750 veröffentlichte.

Ausgangspunkt für die Cramer’sche Regel ist stets ein lineares Gleichungssystem mit genausovielen Gleichungen wie Unbekannten. Man spricht hierbei von einem quadratischen linearen Gleichungssystem. Dieses System muss zusätzlich eindeutig lösbar sein, was sich am einfachsten überprüfen lässt, indem man die Determinante der Koeffizientenmatrix berechnet. Ist diese von Null verschieden, ist die Voraussetzung erfüllt, und die einzelnen Unbekannten berechnen sich nach der Cramer’schen Regel jeweils zu

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

Die Matrix $A i$ entsteht aus der Koeffizientenmatrix, indem man die $i$ -te Spalte durch die rechte Seite des Gleichungssystems ersetzt.

Inhaltsverzeichnis

1 Beispiel
2 Geschichte
3 Rechenaufwand
4 Beweis
5 Verallgemeinerung
6 Folgerungen aus der Cramer’schen Regel
- 6.1 Die Inverse einer Matrix
- 6.2 Lösung eines homogenen linearen Gleichungssystems
7 Quellen

[Bearbeiten] Beispiel

Diesem Beispiel liegt das folgende lineare Gleichungssystem zu Grunde:

1	$x 1$	+	2	$x 2$	=	3
4	$x 1$	+	5	$x 2$	=	6

Nach der Cramer’schen Regel berechnet sich dessen Lösung wie folgt:

Die senkrechten Striche sind eine gebräuchliche Notation der Determinante.

[Bearbeiten] Geschichte

Gabriel Cramer

Die Cramer’sche Regel wurde 1750 von Gabriel Cramer im Anhang 1 seines Buchs „Introduction a l′analyse de lignes courbes algebriques“ ^[1] veröffentlicht. Er gab darin explizit die Formeln für lineare Gleichungssysteme mit bis zu drei Gleichungen an und beschrieb, wie man die Lösungsformeln für Gleichungssysteme mit mehr Gleichungen erstellen kann. Da die Determinante noch nicht eingeführt war, verwendete er Brüche mit je einem Polynom im Zähler und Nenner. Wie der folgende Auszug aus der Originalarbeit zeigt, sind diese mit den Polynomen der Leibniz-Formel identisch.

An diesem Beispiel sieht man auch, dass Cramer noch nicht die heutige Notation linearer Gleichungssystem verwendete. Mit dieser lautet die Formel wie folgt:

$x_1 = \frac{b_1a_{22}a_{33} - b_1a_{32}a_{23} - b_2a_{12}a_{33} + b_2a_{32}a_{13} + b_3a_{12}a_{23} - b_3a_{22}a_{13}}{a_{11}a_{22}a_{33} - a_{11}a_{32}a_{23} - a_{21}a_{12}a_{33} + a_{21}a_{32}a_{13} + a_{31}a_{12}a_{23} - a_{31}a_{22}a_{13}}$

Cramer selbst war bewusst, dass lineare Gleichungssysteme nicht immer eindeutig lösbar sind.^[2] Étienne Bézout zeigte dann 1764, dass der Nenner null wird, wenn das Gleichungssystem nicht eindeutig lösbar ist.^[2] Des Weiteren gab Cramer keinen Beweis für seine Formel an. Diesen lieferte erst Augustin Louis Cauchy im Jahr 1815. Dabei führte er auch die heutzutage verwendete Notation der Cramer’schen Regel ein.

Gottfried Wilhelm Leibniz brachte die Cramer’sche Regel schon 1678 in einem Manuskript zu Papier. Dieses wurde allerdings erst später entdeckt und hatte somit kein Auswirkung auf die Entwicklung von Lösungsverfahren für lineare Gleichungssysteme.^[2] Colin Maclaurin beschrieb in seinem Werk „Treatise of Algebra“ die Spezialfälle der Cramer’schen Regel für lineare Gleichungssysteme aus zwei oder drei Gleichungen. Er hatte zwar die Idee, diese Formeln auf Gleichungssysteme mit mehreren Gleichungen zu erweitern, doch im Gegensatz zu Cramer fand er keine Regel, wie man die Vorzeichen in den dabei verwendeten Polynomen richtig setzt.^[3] Ende des 20. Jahrhunderts entfachte Carl Benjamin Boyer einen Streit unter Mathematik-Historikern, ob Maclaurin oder Cramer der Entdecker der Formel war. Er empfahl dabei auch eine Umbenennung in Maclaurin-Cramer-Regel.^[4]

[Bearbeiten] Rechenaufwand

Um mit der Cramer’schen Regel ein lineares Gleichungssystem mit $n$ Unbekannten zu lösen, müssen $n + 1$ Determinanten berechnet werden. Die Anzahl der auszuführenden arithmetischen Operationen hängt damit allein vom Algorithmus zur Berechnung der Determinanten ab.

Nimmt man die von Cramer verwendeten Polynome der Leibniz-Formel, so muss man für jede Determinante $(n-1) \cdot n!$ Multiplikationen und $n - 1$ Additionen durchführen. Schon bei einem System aus vier Gleichungen sind 360 Multiplikationen, vier Divisionen und 15 Additionen notwendig. Im Vergleich zu anderen Verfahren sind dies sehr viele Operationen. Auch unter Verwendung effektiver Algorithmen zur Determinantenberechnung ist der Rechenaufwand für die Lösung eines linearen Gleichungssystems mit der Cramer’schen Regel wesentlich höher als beispielsweise beim Gaußschen Eliminationsverfahren.

[Bearbeiten] Beweis

Für diesen Beweis verwendet man eine Matrix $X i$ , die entsteht, indem man die $i$ -te Spalte der Einheitsmatrix durch den Lösungsvektor $x$ des Gleichungssystems $A x = b$ ersetzt. So sieht $X 2$ für ein Gleichungssystem mit vier Gleichungen folgendermaßen aus:

$X_2 = \begin{pmatrix}1 & x_1 & 0 & 0 \\ 0 & x_2 & 0 & 0 \\ 0 & x_3 & 1 & 0 \\ 0 & x_4 & 0 & 1\end{pmatrix}$

Anhand dieses Beispiels lässt sich auch sehen, dass $A X i = A i$ gilt.

$\begin{matrix} A \cdot X_2 & = & \begin{pmatrix}a_{11} & a_{12} & a_{13} & a_{14} \\ a_{21} & a_{22} & a_{23} & a_{24} \\ a_{31} & a_{32} & a_{33} & a_{34} \\ a_{41} & a_{42} & a_{43} & a_{44}\end{pmatrix} \cdot \begin{pmatrix}1 & x_1 & 0 & 0 \\ 0 & x_2 & 0 & 0 \\ 0 & x_3 & 1 & 0 \\ 0 & x_4 & 0 & 1\end{pmatrix}\\ & = & \begin{pmatrix}a_{11} & a_{11}x_1 + a_{12}x_2 + a_{13}x_3 + a_{14}x_4 & a_{13} & a_{14} \\ a_{21} & a_{21}x_1 + a_{22}x_2 + a_{23}x_3 + a_{24}x_4 & a_{23} & a_{24} \\ a_{31} & a_{31}x_1 + a_{32}x_2 + a_{33}x_3 + a_{34}x_4 & a_{33} & a_{34} \\ a_{41} & a_{41}x_1 + a_{42}x_2 + a_{43}x_3 + a_{44}x_4 & a_{43} & a_{44}\end{pmatrix}\\ & = & \begin{pmatrix}a_{11} & b_1 & a_{13} & a_{14} \\ a_{21} & b_2 & a_{23} & a_{24} \\ a_{31} & b_3 & a_{33} & a_{34} \\ a_{41} & b_4 & a_{43} & a_{44}\end{pmatrix}\\ & = & A_2 \end{matrix}$

Da zusätzlich $det(X i) = x i$ gilt, folgt mit der Produktregel für Determinanten

$\begin{matrix} \det(A) & \cdot & \det(X_i) & = & \det(A_i)\\ \det(A) & \cdot & x_i & = & \det(A_i)\\ & & x_i & = & \frac{\det(A_i)}{\det(A)} \end{matrix}$

Da die Determinante $det(A)$ nach Voraussetzung von null verschieden ist, tritt keine Division durch Null auf.

[Bearbeiten] Verallgemeinerung

Eine Verallgemeinerung der Cramer’schen Regel stellt der folgende Satz dar:

Alle Komponenten $x_1,x_2,\ldots,x_n$ einer Lösung eines quadratischen linearen Gleichungssystems erfüllen jeweils die Gleichung

$\det(A) \cdot x_i = \det(A_i)$

Im Gegensatz zur ursprünglichen Cramer’schen Regel entfällt hier die Einschränkung auf ein eindeutig lösbares Gleichungssystem. Da zudem keine Division mehr auftritt, gilt der Satz auch bei Gleichungssystemen mit Koeffizienten aus einem kommutativen Ring.^[5]

[Bearbeiten] Folgerungen aus der Cramer’schen Regel

[Bearbeiten] Die Inverse einer Matrix

Hauptartikel: Reguläre Matrix

Die einzelnen Spalten der Inversen einer Matrix $A$ werden jeweils von der Lösung des Gleichungssystems $A x = e j$ mit dem $j$ -ten Einheitsvektor auf der rechten Seite gebildet. Berechnet man diese mit der Cramer’schen Regel, so erhält man unter Verwendung der Adjunkten $\operatorname{adj} (A)$ die Formel

$A^{-1} = \frac{\operatorname{adj} (A)}{\det(A)}$

Diese Formel zeigt auch eine Eigenschaft von Matrizen mit Einträgen aus einem kommutativen Ringe anstatt einem Körper. Diese sind demnach genau dann invertierbar, wenn $det(A)$ invertierbar ist.

[Bearbeiten] Lösung eines homogenen linearen Gleichungssystems

Mit Hilfe der Cramer’schen Regel lässt sich einfach zeigen, dass die triviale Lösung $x_1 = x_2 = \ldots = x_n = 0$ die einzige Lösungen eines jeden homogenen linearen Gleichungssystems mit $\det(A) \ne 0$ ist. Da bei allen Matrizen $A i$ in der $i$ -ten Spalte nur Nullen stehen, sind deren Spalten nicht mehr linear unabhängig, und es gilt deshalb $det(A i) = 0$ . Damit berechnen sich alle $x i$ zu null.

Aus der obigen Eigenschaft folgt direkt, dass der Kern eines linearen Gleichungssystems $A x = b$ mit $\det(A) \ne 0$ der Nullvektor ist und dieses deshalb eindeutig lösbar ist.

[Bearbeiten] Quellen

↑ Gabriel Cramer: Introduction a l’analyse de lignes courbes algebriques. Genf 1750, S. 657–659
↑ ^a ^b ^c Jean-Luc Chabert et al.: A History of Algorithms. Form the Pebble to the Microchip. Springer-Verlag, 1999, ISBN 3-540-63369-3, S. 284–287 (Diese Buch enthält eine englische Übersetzung von Cramers Originalveröffentlichung.)
↑ Antoni A. Kosinski: Cramer's Rule Is Due to cramer. In: Mathematics Magazine. Bd. 74, Nr. 4, Oktober 2001, S. 310–312
↑ Bruce A. Hedman: An Earlier Date for „Cramer’s Rule“ In: Historica Mathematica. Bd. 24, 1999, S. 365–368
↑ Serge Lang: Algebra. 2. Auflage. Addison-Wesley, 1984, ISBN 0-201-05487-6, S. 451

Von „http://de.wikipedia.org../../../c/r/a/Cramer%E2%80%99sche_Regel_6cb3.html“

Kategorien: Kommutative Algebra | Lineare Algebra | Satz (Mathematik)