Diskussion:Cramersche Regel

Komplexität

Was bedeutet: "Der Aufwand der Cramerschen Regel beträgt O(nn!)."? Gruß, --Laudrin 11:50, 6. Jan 2006 (CET)

Der Satz trifft eine Aussage über die maximale Laufzeit des Algorithmus (das O(nn!) ist mit dem Artikel Landau-Symbole verlinkt, der diese Schreibweise erklärt). Ich habe das im neuen Artikel ein bisschen präzisiert. Allerdings weiß ich nicht, ob die Abschätzung stimmt und für welchen Algorithmus zur Berechnung der Determinante sie gilt. Ich werde es aber bei Gelegenheit rausfinden. --Squizzz 11:55, 20. Jan 2006 (CET)

So, auch hier sage ich noch etwas, unten habe ich ja shcon "meinen Senf" dazu gegeben: Die Laufzeit ist falsch angegeben. O(nn!)!! Naja, wenn ich das doof genug implementiere und n-mal über die Matrix renne, dann ist das vielleicht richtig. Aber so ist ja die O-Notation auch nicht zu verwenden. Es muss davon ausgegangen werden, dass alle Determinanten der Matrix Ai berechnet werden müssen. Laufzeit also O(n!). Vielleicht ist es auch nur ein Tippfehler mit "O(nn!)" gewesen.

Da keiner die falsche Laufzeit geändert hat, habe ich sie nun korrigiert. --Genscher 01.06.2006

Prinzipiell danke für die Korrektur, allerdings kann ich die Laufzeitangabe O(n!) immer noch nicht nachvollziehen. Ohne auf einen Algorithmus zur Berechnung der Determinante kann man meines Erachtens keine solche Aussage treffen. Deshalb habe ich die Aussage ganz gelöscht. Wenn sie wieder rein soll, dann bitte mit Quellenangabe oder zumindest Hinweis auf einen Algorithmus zur Berechnung der Determinante. --Squizzz 11:21, 1. Jun 2006 (CEST)

Es geht um eine prinzipielle Mindestzahl an nötigen Operationen. Hab bei Google kurz was gefunden [1] (pdf), hab aber gerade nicht mehr Zeit.--G 21:36, 1. Jun 2006 (CEST)

Hab jetz was gefunden: Hat man ein n-reihige Determinante braucht man n (n-1) reihige Determinanten (also bei einer 10 reihigen Det. braucht man zehn neunreihige Determinanten). In der Zweireihigen Det. hat man dann auch noch 2 Mulitplikationen also braucht man n*(n-1)*...*2=n! Multiplikationen. Für die Berechnung der Lösungen eines n-reihigen LGS bracht man n+1 Determinanten. Führt man Det. also auf zweireihige Determinanten zurück braucht man (n+1)*n! = (n+1)! Multiplikationen. (Quelle: Barth, Krumbacher, Barth: Anschauliche Analytische Geometrie).--G 14:10, 2. Jul 2006 (CEST)

Es gibt Verfahren zur divisionsfreien (oder fast div-freien) Berechnung von Determinanten, die mit $O(n^{4})$ Multiplikationen auskommen. Berechnet man die Determinante mit dem Gauss-Algorithmus, so benötigt man $O(n^{3})$ Multiplikationen und Divisionen. Das simultane Berechnen aller Determinanten mit Gauss ist zum direkten Lösen des Gleichungssystems mit Gauss äquivalent.--LutzL 12:02, 12. Okt. 2006 (CEST)

Weißt du zufällig etwas konkreteres oder hast du Quellen, die man angeben könnte?--G 16:56, 20. Okt. 2006 (CEST)

Es gibt den divisionsfreien Berkowitz-Algorithmus (1984). Dann gibt es ein relativ unbekanntes, aber recht einfaches Verfahren, da in gewissem Sinne das Horner-Schema umkehrt. D.h. es werden die Newton-Identitäten auf die Spuren der Matrixpotenzen angewandt, um die Koeffizienten des char. Polynoms zu erhalten. Dabei wird durch die Zahlen 2,...,n dividiert, dieses Verfahren ist also nur eingeschränkt divisionsfrei.

Start: i=0,C1=I,a[0]=1

Iteration von i=1 bis n

C=C1, C1=M*C, a[i]=-Spur(C1)/i

next i

Ergebnis: $P(X)=a[0]*X^{n}+a[1]x^{n-1}+\dots +a[n]$ ist das charakteristische Polynom, $M^{\#}=(-1)^{n-1}C$ ist die komplementäre oder adjunkte Matrix, $\det M=(-1)^{n}a[n]$ ist die Determinante.

Die Berechnung der Determinante kann vereinfacht werden, indem vorher gewisse Zeilenoperationen ausgeführt werden. Wendet man diese simultan auf die Determinante der Systemmatrix und die Zählerdeterminanten an, so ergibt sich dieselbe Rechnung wie beim Gauß- oder Gauß-Bareiss-Algorithmus. Letzterer ist so exakt wie der Datentyp und benötigt O(n³) Operationen

• S. J BERKOWITZ: On Computing the determinant in small parallel time using a small number of processors. In: Information Processing Letters. 18. Jahrgang, 1984, S. 147–150. 
• J. ABDELJAOUED: The Berkowitz Algorithm, Maple and Computing the Characteristic Polynomial in an Arbitrary Commutative Ring. In: Maple User Journal(?). 1996. 
• H. Cohen: A course in computational algebraic number theory. 1993. 

--LutzL 08:46, 23. Okt. 2006 (CEST)

Fehler im Artikel

Eine Frage zu inhomogenen LGS:

x+y+z = 1

x+y+z=2

x+y+z=3

hat keine Lösung, aber laut Wikipedia-Seite unendlich viele Lösungen!! Zitat Wiki-Seite: "unendlich viele Lösungen, falls det(A) = 0 und det(Ai) = 0 für alle i = 1, 2, ..., n," In meinem Gegenbeispiel sind alle Det(A)=0 und alle det(Ai)=0!

Also ist das hier beschriebene inkorrekt!

Stimmt, es ist auch möglich, dass ein Gleichungssystem dessen Determinanten den Wert 0 haben, keine Lösung hat.--G 17:15, 13. Jan 2006 (CET)

Antwort: Die fehlerhafte Aussage wurde vom Benutzer G in der Version 12574936 vom 13. Januar 2005 beseitigt. --Squizzz 11:55, 20. Jan 2006 (CET)

Ich habe nochmal bei meinem Lin. Algebra Prof. nachgefragt, wie's jetzt genau ist. Die "Fehlerhafte Aussage" ist zu 90% Prozent richtig. Ich fand die Übersicht halt sehr schön. Sie könnte doch wieder im Artikel aufgenommen werden! Sie müsste halt nur in einem Punkt abgeändert werden: Falls det(A) = 0 und nicht alle det(Ai) = 0 kann man mit der Cramerschen Regel keine Aussage über die Lösung machen. Da muss man mit Gauß ansetzen, der nämlich für alle Fälle zu einer Lösung führt (d.h. "keine Lösung", "unendlich viele Lösungen", "eine eindeutige Lösung"). Das ist auch der Unterschied zwischen Cramer und Gauß. Cramer eignet sich zum schnellen prüfen, ob überhaupt eine Lösung vorhanden ist (jedenfalls bei kleinen n's). Gauß-Allgorithmus ist aufwendiger, dafür aber vollständig.

Finde auch, dass es wieder rein sollte. Steht in den meisten Büchern dabei. Außerdem steht oben schon das mit den Lösungsmöglichkeiten homogener Systeme, das sollte man dann da auch gleich aufgreifen.--G 17:48, 21. Jan 2006 (CET)

Nein, Cramer eignet sich nicht dazu zu gucken, ob überhaupt eine Lösung vorhanden ist. Grundsätzlich muss man zwischen homogenem und inhomogenem Gleichungssystem unterscheiden:

• Im homogenen Fall suchen wir ein 'x' mit 'Ax = 0'. Dass hier 'x = 0' auf jeden Fall eine Lösung ist sollte auf den ersten Blick klar sein ('A . 0 = 0') und gilt auch dann, wenn 'det(A)=0'. Der Absatz, in dem das (für den Spezialfall 'det(A) != 0' aus der Cramerschen Regel gefolgert wird sollte daher meiner Meinung nach raus. Falls 'det(A) = 0' gilt, gibt es unendlich viele Lösungen (sofern das Gleichungssystem über einem unendlichen Körper, z.B. den reellen Zahlen, betrachtet wird). Das folgt aber nicht aus der Cramerschen Regel! Die Lösungen des homogenen Gleichungssystems heißen übrigens Kern.
• Im inhomogenen Fall ist 'b != 0'. Dann gibt es, falls 'det(A) != 0' ist, für jedes solche 'b' genau eine Lösung, die liefert Cramer. Falls 'det(A) = 0' ist gibt es für manche 'b' (auf jeden Fall für 'b = 0') unendlich viele Lösungen, es gibt aber auch für manche 'b' gar keine Lösung. Das folgt aber wieder nicht aus der Cramerschen Regel.

FarSide 17:39, 5. Okt 2006 (CEST)

Bitte lies den Artikel aufmerksam. Dort steht, dass der Nullvektor die (einzige) Lösung eines eindeutig lösbaren homogenen LGS ist. --Squizzz 18:22, 5. Okt 2006 (CEST)

Gleichungssysteme mit det(A) = 0

Die Aussagen über diese Gleichungssysteme sind zwar korrekt, allerdings ergeben sie sich nicht aus der cramerschen Regel. Deshalb habe ich sie wieder entfernt.

Auch die Aussage „ein hom. LGS besitzt die triviale Lösung oder unendlich viele Lösungen“ ergibt sich nicht (vollständig) aus der cramerschen Regel. Diese sagt nur aus, dass im Falle, dass das hom. LGS genau eine Lösung besitzt, dies die triviale Lösung besitzt. Der Fall mit den unendlich vielen Lösungen ergibt sich aus der linearen Abhängigkeit der Spaltenvektoren im Fall det(A) = 0. --Squizzz 17:32, 6. Feb 2006 (CET)

Inversion von Matrizen

Das Thema "Inversion von Matrizen" gehört meiner Meinung nach sehr wohl zur Cramerschen Regel, da in vielen Texten vor allem aus der Ringtheorie unter dem Stichwort "Cramersche Regel" genau das gemeint ist. Insbesondere das Regularitätskriterium für Matrizen über einem Ring (Determinante ist Einheit) sollte entweder hier stehen oder von hier darauf verwiesen werden. FarSide 10:13, 9. Jul 2006 (CEST)

Änderung vom 5. Oktober 2004

Betrifft: http://de.wikipedia.org/w/index.php?title=Cramersche_Regel&curid=217215&diff=22251109&oldid=22209280

FarSide, du gibst an, dass

$det(A)x_{i}=det(A_{i})$

die Cramersche Regel ist. Dies kann ich in der Literatur so nicht finden. Dort wird immer die Lösungsformel

$x_{i}={\frac {\det(A_{i})}{\det(A)}}$

als Cramersche Regel bezeichnet. Entsprechende Literaturstellen sind

• Detlef Wille: Repetitorium der Linearen Algebra. Teil 1. Binomi-Verlag, S. 114 Satz 3
• Siegfried Bosch: Lineare Algebra. Springer-Verlag, S. 149 Korollar 6

Ich habe deshalb vorerst deine Änderung rückgängig gemacht. Insbesondere da du beim eindeutig lösbaren homogenen LGS einen kleine Ungenauigkeit eingebaut hast. Kannst du jedoch deine Aussage belegen, dann nehme ich sie gerne wieder auf. --Squizzz 18:20, 5. Okt 2006 (CEST)

Die angegebene Formel hat den Vorteil, dass sie auch dann richtig ist, wenn $\det A$ nicht invertierbar ist. Referenz: Lang, Algebra, XIII.4.4.--Gunther 22:43, 5. Okt 2006 (CEST)

Die beiden Formeln sind praktisch identisch, wenn du deine Version mit $det(A)$ multiplizierst erhältst du die Version von FarSide.--G 23:21, 5. Okt 2006 (CEST)

Das war nicht die Frage.--Gunther 23:23, 5. Okt 2006 (CEST)

Hallo, erstmal entschuldigung, dass ich das "die Lösung" durch "eine Lösung" ersetzt habe und es noch nichtmal in die Zusammenfassung der Änderung geschrieben hab. Hab nochmal drüber geschlafen und bin zu folgendem gekommen:

• Die Quellenangabe für meine Version ist in der Tat der Lang, und sie hat den Vorteil, immer zu gelten.
• Daraus folgt eine Bedingung, der mögliche Lösungen genügen müssen, (erstmal) nicht die Existenz einer Lösung.
• Im Fall $\det(A)\neq 0$ kann es für jedes $b$ nur eine Lösung geben, die durch $x_{i}={\frac {\det(A_{i})}{\det(A)}}$ bestimmt ist.
• An dieser Stelle kommt der letzte Absatz ins Spiel: Dass $0$ eine Lösung ist gilt immer und ist auch ohne Cramersche Regel offensichtlich. Dass es keine weitere Lösung geben kann folgt im Fall $\det(A)\neq 0$ daraus, dass für $b=0$ alle $\det(A_{i})=0$ sind. Das bedeutet, dass die Spalten von A linear unabhängig sind und den ganzen $\mathbb {R} ^{n}$ aufspannen. Deshalb muss es für jedes $b$ eine Lösung geben, die wir somit durch $x_{i}={\frac {\det(A_{i})}{\det(A)}}$ bestimmt haben.

Ich werde mich gleich mal daran versuchen, dass in den Artikel einzubauen, ohne den enzyklopädischen Charakter zu verletzen. Die von mir angegebene Form der Cramerschen Regel gilt auch für $\det(A)=0$ und, was für Anwendungen in der Algebra wichtiger ist, auch für Matrizen mit Einträgen aus kommutativen Ringen, wo nicht unbedingt dividiert werden kann. In diesem Fall folgt immer noch die Invertierbarkeit von Matrizen, falls $det(A)$ eine Einheit ist. In diesem Zusammenhang wird die Regel z.B. in Matsumura, Commutative Algebra, zitiert. Darauf sollte auch im Artikel hingewiesen werden (sie frühere Änderung und früherer Kommentar von mir), bin aber für andere Meinungen offen. FarSide 07:33, 6. Okt 2006 (CEST)

Danke für eure Hinweise. Ich komme jedoch erst am Montag dazu in den Lang reinzuschauen und mir ein Urteil über anstehende Änderungen zu bilden. Wer will kann ja schon mal die allgemeinere Verwendung einbauen. --Squizzz 09:47, 6. Okt 2006 (CEST)

Ich habe nun einmal wahllos zwanzig Bücher aus dem Lineare-Algebra-Regal genommen und festgestellt, dass fast immer die Quotientenformel als Cramersche Regel bezeichnet wird. An eine Kopie des Originals von Cramer bin ich nicht gekommen. Lang nimmt in seinem Buch Algebra die allgemeine Form, bezeichnet jedoch selbst in der 2. Auflage seiner Linear Algebra die Quotientenformel explizit als Cramersche Regel. Da ich auf Grund dessen davon ausgehe, dass die Quotientenformel im Allgemeinen mit den Begriff Cramersche Regel in Verbindung gebracht wird, habe ich diesbezüglich wieder den alten Zustand des Artikels hergestellt und auf die allgemeine Form am Ende der Einleitung verwiesen. Können damit alle gut leben? --Squizzz 23:55, 16. Okt. 2006 (CEST)

OK, dass die Cramersche Regel meist in der Quotientenform angegeben wird, lässt sich nicht bestreiten. Trotzdem finde ich meine Beschreibung, die erst die Produktform angibt und dann zwei Zeilen später auf den (wichtigen) Spezialfall $\det(A)\neq 0$ eingeht, besser. Squizzz, Du schreibst, die Regel ließe sich "erweitern" auf die Produktformel. Dabei kehrt man aber nur zur ursprünglichen Form zurück, die man vorher eingeschränkt hat. Außerdem gehen die meisten Bücher über Lineare Algebra von Matrizen mit Einträgen in einem Körper (typischerweise R oder C) aus, die Regel gilt aber auch in kommutativen Ringen. Hier ist das Hindernis bei einer Division nicht "Division durch null", sondern es geht um Kürzung gleicher Teiler.

Die Quotientenform ist sicher die gebräuchlichste und für Ingenieure, Physiker, Informatiker, Numeriker... also fast alle auch die relevante. Aber eine mathematisch saubere Formulierung ist weder länger noch schwerer verständlich (finde ich), warum also darauf verzichten? Die Darstellung bei MathWorld ist übrigens ähnlich.

Ich bin aber schonmal froh, dass wenigstens der Beweis, den nochmal jemand eingebaut hat, nicht wieder mit "kein Mehrwert" diskussionslos rausgeschmissen wurde. -- FarSide 03:21, 17. Okt. 2006 (CEST)