Cramersche Regel

Die Cramersche 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 Cramersche Regel ist nach Gabriel Cramer benannt, der sie im Jahr 1750 veröffentlichte, jedoch wurde sie bereits vorher von Leibniz gefunden.

Regel

Gegeben sei ein lineares Gleichungssystem^[1] mit gleich vielen Gleichungen wie Unbekannten in der Form

${\displaystyle {\begin{matrix}a_{11}x_{1}+a_{12}x_{2}\,+&\cdots &+\,a_{1n}x_{n}&=&b_{1}\\a_{21}x_{1}+a_{22}x_{2}\,+&\cdots &+\,a_{2n}x_{n}&=&b_{2}\\&&&\vdots &\\a_{n1}x_{1}+a_{n2}x_{2}\,+&\cdots &+\,a_{nn}x_{n}&=&b_{n}\end{matrix}}}$

bzw. in Matrixschreibweise ${\displaystyle Ax=b}$ mit

${\displaystyle A={\begin{pmatrix}a_{11}&a_{12}&\cdots &a_{1n}\\a_{21}&a_{22}&\cdots &a_{2n}\\\vdots &\vdots &\ddots &\vdots \\a_{n1}&a_{n2}&\cdots &a_{nn}\end{pmatrix}}\,,\quad x={\begin{pmatrix}x_{1}\\x_{2}\\\vdots \\x_{n}\end{pmatrix}}\,,\quad b={\begin{pmatrix}b_{1}\\b_{2}\\\vdots \\b_{n}\end{pmatrix}}\,.}$

Vorausgesetzt sei außerdem, dass die quadratische Koeffizientenmatrix ${\displaystyle A}$ regulär (invertierbar) ist. Dies ist genau dann der Fall, wenn ${\displaystyle \det(A)\neq 0}$ ist.

Dann ist das Gleichungssystem eindeutig lösbar und die Komponenten ${\displaystyle x_{i}}$ des eindeutig bestimmten Lösungsvektors ${\displaystyle x}$ sind gegeben durch

${\displaystyle x_{i}={\frac {\det(A_{i})}{\det(A)}}}$ für alle ${\displaystyle i}$.

Hierbei ist ${\displaystyle A_{i}}$ die Matrix, die gebildet wird, indem die ${\displaystyle i}$-te Spalte der Koeffizientenmatrix ${\displaystyle A}$ durch die rechte Seite des Gleichungssystems ${\displaystyle b}$ ersetzt wird:

${\displaystyle A_{i}={\begin{pmatrix}a_{1,1}&\cdots &a_{1,i-1}&b_{1}&a_{1,i+1}&\cdots &a_{1,n}\\a_{2,1}&\cdots &a_{2,i-1}&b_{2}&a_{2,i+1}&\cdots &a_{2,n}\\\vdots &&\vdots &\vdots &\vdots &&\vdots \\a_{n,1}&\cdots &a_{n,i-1}&b_{n}&a_{n,i+1}&\cdots &a_{n,n}\end{pmatrix}}}$

Beispiele

Geschichte

Die Cramersche Regel wurde 1750 von Gabriel Cramer im Anhang 1 seines Buchs „Introduction à l′analyse des lignes courbes algébriques“^[2] 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 Gleichungssysteme verwendete. Mit dieser lautet die Formel wie folgt:

${\displaystyle x_{1}={\frac {b_{1}a_{22}a_{33}-b_{1}a_{32}a_{23}-b_{2}a_{12}a_{33}+b_{2}a_{32}a_{13}+b_{3}a_{12}a_{23}-b_{3}a_{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.^[3] Étienne Bézout zeigte dann 1764, dass der Nenner null wird, wenn das Gleichungssystem nicht eindeutig lösbar ist.^[3] 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 Cramerschen Regel ein.

Gottfried Wilhelm Leibniz brachte die Cramersche Regel schon 1678 in einem Manuskript zu Papier. Dieses wurde allerdings erst später entdeckt und hatte somit keine Auswirkung auf die Entwicklung von Lösungsverfahren für lineare Gleichungssysteme.^[3] Colin Maclaurin beschrieb in seinem Werk „Treatise of Algebra“, das 1748 veröffentlicht wurde, die Spezialfälle der Cramerschen 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.^[4] Im 20. Jahrhundert 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.^[5]

Rechenaufwand

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

Werden die Determinanten wie von Cramer mit Hilfe der Leibniz-Formel berechnet, so sind für jede Determinante ${\displaystyle (n-1)\cdot n!}$ Multiplikationen und ${\displaystyle n!-1}$ Additionen notwendig. Schon bei einem System aus vier Gleichungen sind 360 Multiplikationen, 115 Additionen und 4 Divisionen notwendig. Im Vergleich zu anderen Verfahren sind dies sehr viele Operationen. Auch unter Verwendung effizienter Algorithmen zur Determinantenberechnung ist der Rechenaufwand für die Lösung eines linearen Gleichungssystems mit der Cramerschen Regel wesentlich höher als beispielsweise beim gaußschen Eliminationsverfahren.

Bei der Berechnung einer ${\displaystyle n\times n}$-Matrix auf einem Rechner mit ${\displaystyle 10^{8}}$ Gleitkommaoperationen pro Sekunde (100 Mflops) würden sich die folgenden Rechenzeiten ergeben^[6]:

Beweis

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

${\displaystyle 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 ${\displaystyle AX_{i}=A_{i}}$ gilt.

${\displaystyle {\begin{aligned}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{aligned}}}$

Da zusätzlich ${\displaystyle \det(X_{i})=x_{i}}$ gilt, folgt mit der Produktregel für Determinanten

${\displaystyle {\begin{matrix}\det(A)&\cdot &\det(X_{i})&=&\det(A_{i})\\\det(A)&\cdot &x_{i}&=&\det(A_{i})\\&&x_{i}&=&\det(A_{i})\cdot \det(A)^{-1}\end{matrix}}}$

Da die Determinante ${\displaystyle \det(A)}$ nach Voraussetzung nicht das Null-Element ist, existiert ${\displaystyle \det(A)^{-1}}$.

Verallgemeinerung

Eine Verallgemeinerung – und gleichzeitig einen Schritt im Beweis – der Cramerschen Regel stellt der folgende Satz dar: Gegeben sei ein quadratisches lineares Gleichungssystem der Form

${\displaystyle Ax=b}$.

Ist ${\displaystyle x=(x_{1},x_{2},\ldots ,x_{n})}$ eine Lösung dieses linearen Gleichungssystems, dann gilt

${\displaystyle \det(A)\cdot x_{i}=\det(A_{i})}$ für jedes ${\displaystyle i}$.

Die Matrix ${\displaystyle A_{i}}$ entsteht aus der Koeffizientenmatrix ${\displaystyle A}$, indem die ${\displaystyle i}$-te Spalte von ${\displaystyle A}$ durch die rechte Seite des Gleichungssystems ${\displaystyle b}$ ersetzt wird.

Es entfällt die Einschränkung auf ein eindeutig lösbares Gleichungssystem. Da zudem keine Division mehr auftritt, gilt der Satz für alle Gleichungssysteme mit Koeffizienten aus einem kommutativen Ring.^[7] Diese Verallgemeinerung wird nicht mehr Cramersche Regel genannt.

Folgerungen aus der Cramerschen Regel

Einzelnachweise

1. ↑ Vorausgesetzt wird, dass die Koeffizienten reelle oder komplexe Zahlen sind oder – allgemeiner – Elemente eines Körpers.
2. ↑ Gabriel Cramer: Introduction à l’analyse des lignes courbes algébriques. Genf 1750, S. 657–659.
3. 1 2 3 Jean-Luc Chabert et al.: A History of Algorithms. From the Pebble to the Microchip. Springer-Verlag, 1999, ISBN 3-540-63369-3, S. 284–287 (Dieses Buch enthält eine englische Übersetzung von Cramers Originalveröffentlichung.).
4. ↑ Antoni A. Kosinski: Cramer's Rule Is Due to cramer. In: Mathematics Magazine. Bd. 74, Nr. 4, Oktober 2001, S. 310–312.
5. ↑ Bruce A. Hedman: An Earlier Date for „Cramer’s Rule“ In: Historica Mathematica. Bd. 24, 1999, S. 365–368.
6. ↑ W. Dahmen, A. Reusken: Numerik für Ingenieure und Naturwissenschaftler, Springer, 2006, ISBN 3-540-25544-3
7. ↑ Serge Lang: Algebra. 2. Auflage. Addison-Wesley, 1984, ISBN 0-201-05487-6, S. 451.