Vorzeichen einer Determinante, numerische Lib
-
Hallo,
welche Möglichkeiten gibt es, um das _Vorzeichen_ der Determinante einer 4x4-
Matrix trotz Rundungsfehlern genau zu bestimmen? Der Zahlentyp ist 'double'.
Grundsätzlich exakte Zahlen aus GMP zu verwenden, bloß weil die Genauigkeit
in seltenen Fällen nicht ausreicht, ist zu langsam. Ich suche etwas in der
Größenordnung von Boost, Lapack, ... Wer kann sowas?Danke,
-
Kannst du mal sagen, wozu du das brauchst? Es scheint mir nicht sinnvoll zu sein, das Vorzeichen der Determinanten "genau trotz Rundungsfehlern" zu bestimmen und dann ganz normal mit der Matrix weiterzurechnen. Wenn das Vorzeichen instabil ist, dann ist die Matrix annähernd singulär und wird dir trotzdem weiter Probleme machen.
-
Bashar schrieb:
Kannst du mal sagen, wozu du das brauchst? Es scheint mir nicht sinnvoll zu sein, das Vorzeichen der Determinanten "genau trotz Rundungsfehlern" zu bestimmen und dann ganz normal mit der Matrix weiterzurechnen. Wenn das Vorzeichen instabil ist, dann ist die Matrix annähernd singulär und wird dir trotzdem weiter Probleme machen.
Ein Studienprojekt. Mit der Matrix wird nicht weitergerechnet, das Vorzeichen
ist bereits das gewünschte Ergebnis.
-
Gibts da gar nichts?
-
Abgesehen davon, dass ich den Sinn in der Übung nicht sehe ...
1. Determinanten berechnet man am besten über eine Zerlegung der Matrix (QR-Zerlegung oder LU-Zerlegung). Die Determinante einer Dreiecksmatrix ist nämlich das Produkt der Diagonalelemente. Zeilenvertauschung bedeutet Negation der Determinante. etc etc etc.
2. Exaktheit. Du wirst in einigen Fällen nicht um so etwas wie GMP rumkommen. Dazu kannst Du die double-Werte als Brüche darstellen und exakt in Q (Menge der rationalen Zahlen) rechnen. In vielen Fällen wird das Ergebnis, also das Vorzeichen der Determinante, nicht anders aussehen, als wenn Du normal mit doubles rechnen würdest. Um zu erkennen, welche Fälle das sind, kannst Du Boost.Interval verwenden. Per Interval-Arithmetik kannst Du ein Interval bestimmen, in dem die Determinante mit Sicherheit drin liegt. Sind die Intervallgrenzen beide positiv, ist die Determinante sicher positiv. Sind sie beide negativ, ist die Det sicher negativ. Hast Du eine positive und eine negative Intervall-Grenze, so müsstest Du die exakte Berechnung anschmeißen, um zum richtigen Ergebnis zu kommen. Ich würde erwarten, dass Du die meisten Fälle über Interval-Arithmetik erschlagen kannst. Das sollte auch effizienter sein, als die exakte Berechnung der Determinante.
Also, mit anderen Worten, Interval-Arithmetik sollte verhältnismäßig schnell sein und in diesem Fall zu einer von drei Antworten führen:
- Determinante ist positiv
- Determinante ist negativ
- Vorzeichen der Determinante ist nicht bekannt.
-
krümelkacker schrieb:
Per Interval-Arithmetik kannst Du ein Interval bestimmen, in dem die Determinante mit Sicherheit drin liegt.
Super, das habe ich gesucht, danke. Ich habe Boost.Interval schon mal gesehen
aber selbst nicht die Verbindung hergestellt, daß es genau dieses Problem löst
Neben dem dynamischen Mitrechnen des maximalen Fehlers wäre nun noch ein
statischer Test gut. So könnte man einen dreistufigen Prozeß machen, der
zuerst mit double rechnet. Wenn fabs(result)>errorBound, dann ist das Ergebnis
zuverlässig, sonst rechnet man mit Intervall-Arithmetik. Versagt auch dieser
Filter, dann fällt man erst auf exakte Arithmetik zurück. Bloß müßte man dann
den Wert errorBound anhand der übelsten zu erwartenden Werte festlegen. Das
dürfte komplex sein.lg