Invert 4x4 Matrix - Numerisch stabilste Lösung benötigt

Question

Ich möchte eine 4x4 Matrix invertieren. Meine Nummern werden im Festkommaformat gespeichert (1.15.16 um genau zu sein).

Mit Gleitkommaarithmetik ich normalerweise nur die adjungierte Matrix und dividieren durch die Determinante (z. B. Brute Force die Lösung). Das hat bei mir bisher funktioniert, aber wenn ich mit Festkommazahlen zu tun habe, bekomme ich aufgrund der verwendeten Multiplikationen einen inakzeptablen Präzisionsverlust.

Hinweis: In der Festpunktarithmetik werfe ich immer einige der am wenigsten signifikanten Bits von unmittelbaren Ergebnissen weg.

Also - Was ist die numerisch stabilste Möglichkeit, eine Matrix zu invertieren? Mir macht die Performance wenig aus, aber einfach zum Gleitkomma zu gehen, würde meine Zielarchitektur verlangsamen.

Answer 1

Ich denke, die Antwort darauf hängt von der genauen Form der Matrix ab. Eine Standard-Dekompositionsmethode (LU, QR, Cholesky etc.) mit Pivotisierung (ein essentielles) ist ziemlich gut am Fixpunkt, besonders für eine kleine 4x4-Matrix. Siehe das Buch "Numerical Recipes" von Press et al. für eine Beschreibung dieser Methoden.

This paper gibt einige nützliche Algorithmen, aber ist leider hinter einer Paywall. Sie empfehlen eine (geschwenkte) Cholesky-Zerlegung mit einigen zusätzlichen Merkmalen, die zu kompliziert sind, um sie hier aufzulisten.

Answer 2

Plain alte Gaussian Beseitigung würde gut funktionieren.

Es hängt davon ab, welche Bibliotheken/Klassen/Strukturen Sie verwenden. Sie können sich die GSL ansehen.

Answer 3

Um Verkürzungsfehler und andere Nachteile zu minimieren, verwenden Sie "Pivoting" - siehe das Kapitel über das Invertieren von Matrizen in Numerischen Rezepten. Sie haben die beste Erklärung, die ich bisher gefunden habe.

Answer 4

Meta-Antwort: Ist es wirklich eine allgemeine 4x4-Matrix? Wenn Ihre Matrix eine spezielle Form hat, dann gibt es direkte Formeln zum Invertieren, die schnell sind und die Operation herunterzählen.

Zum Beispiel, wenn es eine Standard homogenen von Grafiken Koordinatentransformation, wie:

[ux vx wx tx] 
[uy vy wy ty] 
[uz vz wz tz] 
[ 0 0 0 1] 

(mit einer Zusammensetzung von Dreh vorausgesetzt, Skalierung, Translation Matrizen)

dann gibt es ein easily-derivable direct formula, die

ist

[ux uy uz -dot(u,t)] 
[vx vy vz -dot(v,t)] 
[wx wy wz -dot(w,t)] 
[ 0 0 0  1 ] 

(ASCII-Matrizen aus der gelinkten Seite gestohlen.)

Sie können das wahrscheinlich nicht für den Genauigkeitsverlust im Fixpunkt schlagen.

Wenn Ihre Matrix aus einer Domäne stammt, in der Sie wissen, dass sie mehr Struktur hat, dann gibt es wahrscheinlich eine einfache Antwort.

Answer 5

Wenn die Matrix eine affine Transformation darstellt (dies ist bei 4x4-Matrizen oft der Fall, solange Sie keine Skalierungskomponente einführen), ist die Umkehrung einfach die Transponierte des oberen 3x3-Rotationsteils mit der letzten negierten Spalte . Wenn Sie eine generalisierte Lösung benötigen, ist es wahrscheinlich am einfachsten, in die Gaußsche Eliminierung zu schauen.

Answer 6

Sie könnten eine Verdoppelung auf 1,31 in Erwägung ziehen, bevor Sie Ihren normalen Algorithmus ausführen.Es wird die Anzahl der Multiplikationen verdoppeln, aber du machst eine Matrix-Invertierung und alles, was du tust, ist ziemlich eng mit dem Multiplikator in deinem Prozessor verbunden.

Für alle, die die Gleichungen für eine 4x4-Invertierung finden möchten, können Sie ein symbolisches Mathe-Paket verwenden, um sie für Sie aufzulösen. Der TI-89 wird es sogar tun, obwohl es einige Minuten dauern wird.

Wenn Sie uns eine Vorstellung davon geben, was die Matrix Invert für Sie bedeutet und wie sie in den Rest Ihrer Verarbeitung passt, könnten wir Alternativen vorschlagen.

-Adam

Answer 7

Lassen Sie mich eine andere Frage stellen: Sie müssen Sie auf jeden Fall die Matrix invertieren (nennen wir es M), oder müssen Sie die inverse Matrix verwenden, um andere Gleichungen zu lösen? (z. B. Mx = b für bekanntes M, b) Oft gibt es andere Möglichkeiten, dies zu tun, ohne explizit das Inverse berechnen zu müssen. Oder wenn die Matrix M eine Funktion der Zeit ist & es ändert sich langsam dann können Sie die vollständige inverse einmal berechnen & gibt es iterative Möglichkeiten, es zu aktualisieren.

Answer 8

Ich möchte die Frage, die Jason S aufgeworfen hat, abbrechen: Sind Sie sicher, dass Sie Ihre Matrix invertieren müssen? Dies ist fast nie notwendig. Nicht nur das, es ist oft eine schlechte Idee. Wenn Sie Ax = b lösen müssen, ist es numerisch stabiler, das System direkt zu lösen, als b mit A inverse zu multiplizieren.

Auch wenn Sie Ax = b immer und immer für viele Werte von b zu lösen haben, ist es immer noch keine gute Idee zu invertieren A. Sie können Faktor A (zB LU-Faktorisierung oder Cholesky-Faktorisierung) und speichern Sie die Faktoren, Sie wiederholen diese Arbeit nicht jedes Mal, aber Sie würden das System immer noch mit der Faktorisierung lösen.