Diskussion:Cramer’sche Regel

aus Wikipedia, der freien Enzyklopädie

Du hast neue Nachrichten auf deiner Diskussionsseite.

Um die Diskussionsseite übersichtlich zu halten, habe ich erledigte Sachen entfernt. In der folgenden Liste ist jeweils die letzte Version verlinkt, bevor das Thema entfernt wurde. Wenn jemand ein solches Thema weiterdiskutieren will, kann er es wieder in die Diskussionseite kopieren. --Squizzz 09:42, 6. Dez. 2006 (CET)

[Bearbeiten] 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, 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)

[Bearbeiten] Änderung vom 5. Oktober 2006

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

FarSide, du gibst an, dass

d e t (A) x i = d e t (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

d e t (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 $d e t (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)

Von „http://de.wikipedia.org../../../c/r/a/Diskussion%7ECramer%E2%80%99sche_Regel_f4c0.html“

Diskussion:Cramer’sche Regel

aus Wikipedia, der freien Enzyklopädie

[Bearbeiten] Komplexität

[Bearbeiten] Änderung vom 5. Oktober 2006

Views

Navigation

Mitmachen

Suche