Gleichungssystem lösen

Hallo!

Ich möchte in C++ eine Funktion zum Lösen von Linearen Gleichungssystemen (LGS) schreiben. Dabei will ich die Methode "Gaussian Elimination with partial pivoting" verwenden. Der Pseudocode dieses Verfahrens ist auf der Wiki-Seite dargestellt: http://en.wikipedia.org/wiki/Gaussian_elimination

Bei diesem Algo muss man immer mal wieder 2 Zeilen einer Matrix vertauschen. Jetzt frage ich mich: Wie mache ich das am effizientesten? Ich bezweifle mal, dass eine physikalische Kopie zweier Zeilen wirklich clever ist. Ich habe daran gedacht, dass ich auf jede Zeile der Matrix einen Pointer anlege und beim Tauschen zweier Zeilen dann lediglich die 2 Pointer, die auf die Zeilen zeigen, tausche. Nur das Problem: Wie kann ich dann das Tauschen von Spalten realisieren? Wenn ich zuerst 2 Zeilen tausche (und damit nur 2 Zeiger umbiege) und dann 2 Spalten tausche, dann reicht es ja nicht nur 2 Spaltenzeiger umzubiegen, denn dann wäre die Änderung in den Zeilen nicht angekommen.

Kurzum: Wie realisiere ich am effizienesten einen Zeilen/Spaltentausch in einer Matrix (so dass auch der Zugriff auf ein Element per "operator [][]" schnell ist?

SeppJ

Und wozu willst du beim Gausschen Eliminationsverfahren zwei Spalten vertauschen? Dadurch bekommst du eine ganz anderes Gleichungssystem mit anderen Lösungen.

SeppJ schrieb:

Und wozu willst du beim Gausschen Eliminationsverfahren zwei Spalten vertauschen? Dadurch bekommst du eine ganz anderes Gleichungssystem mit anderen Lösungen.

Beim Eliminationsverfahren will ich das ja nicht. Ich würde es nur einfach generell gerne in meine Matrixklasse einbauen. Oder braucht man sowas nie?

Löser2000 schrieb:

SeppJ schrieb:

Und wozu willst du beim Gausschen Eliminationsverfahren zwei Spalten vertauschen? Dadurch bekommst du eine ganz anderes Gleichungssystem mit anderen Lösungen.

Beim Eliminationsverfahren will ich das ja nicht. Ich würde es nur einfach generell gerne in meine Matrixklasse einbauen. Oder braucht man sowas nie?

Außer beim Berechenen der Determinante ist mir kein Verfahren bekannt wo man sowohl Zeilen- als auch Spaltenoperationen anwendet. Das heißt es genügt, wenn du eines der beiden (effizient) anbietest und eine Möglichkeit die Matrix zu transponieren.
Übrigens kannst du Zeilen bzw. Spalten auch elementweise Tauschen, aber deine Pointer-Idee ist schon ganz gut. So hast du ein effizienten Zeilentausch und für den Spaltentausch kannst du immernoch das weniger effiziente elementweise Austauschen nehmen.

SeppJ

Löser2000 schrieb:

Beim Eliminationsverfahren will ich das ja nicht. Ich würde es nur einfach generell gerne in meine Matrixklasse einbauen. Oder braucht man sowas nie?

Man kann natürlich Fälle konstruieren, wo dies irgendwie Sinn macht, aber normalerweise braucht man das nie. Erst recht nicht, wenn die Matrix eine zu lösende Gleichung darstellt, denn durch Spalten vertauschen verändert sich die Lösung.

Bashar

SeppJ schrieb:

Und wozu willst du beim Gausschen Eliminationsverfahren zwei Spalten vertauschen? Dadurch bekommst du eine ganz anderes Gleichungssystem mit anderen Lösungen.

Nicht "ganz anders", du vertauschst damit lediglich die Unbekannten. Die am Ende wieder richtig zuzuordnen ist leicht.

Also, normalerweise verwendet man zum Lösen von Linearen Gleichungssystemen die LR-Zerlegung (englisch: LU decomposition). Das ist im Prinzip der Gauß-Algorithmus nur so angewendet, dass man ihn auf unterschiedliche Variablen bei gleicher Matrix effizienter einsetzen kann.

Die Sache mit deinem Problem: Der Algorithmus hat einen Aufwand von O(n^3). Du machst maximal n Zeilenvertauschungen. Das sind maximal n(n-1)/2 Elementvertauschungen, wenn du die Elemente direkt in der Matrix vertauscht. Es stellt sich also erstens die Frage, ob dein Programm überhaupt durch die Vertauschungen merklich ausgebremst wird.

Auf der anderen Seite verlängert ein zusätzlicher Pointer den Zugriff auf jedes Matrix Element. Und dieser werden sehr viel öfter gebraucht, als die Vertauschungen. Möglicherweise machst du deinen Algorithmus damit sogar langsamer.

Vielleicht schaust du erstmal, wie dein Algorithmus läuft, wenn du die Zeilen direkt vertauschst. Wenn es dann noch nicht schnell genug läuft, kannst du mal mit einem Profiler an das Programm gehen und gucken, ob du noch was heraus holen kannst.

Erstmal danke für deinen konstruktiven Beitrag ProgChild!

Genau deine Gedanken gingen mir auch durch den Kopf. Das Problem mit dem Pointer ist ja auch, dass nicht nur die Zugriffe auf Elemente während des Lösens des LGS langsamer sind, sondern sie die Zugriffe auf die Matrix IMMER ausbremsen. 99% meiner Matrizen werde ich ja nie einsetzen um ein LGS zu lösen und dennoch wäre jeder Zugriff immer einen Tick langsamer, nur damit das Lösen eines LGS (vielleicht) schneller wäre..

Noch etwas zu deinem Vorschlag mit der LU decomposition. Mir haben mehrere Leute gesagt, dass das direkte Lösen eines allgemeinen LGS am effizientesten per "Gaussian Elimination with parial pivoting" geht. Mir wurde gesagt, dass die LU Decomposition für das einmalige Lösen (was ich ja brauche) langsamer ist und nur Vorteile hat, wenn man das gleiche LGS mit wechselnden "rechten Seiten" lösen muss. Stimmt das?
Ferner habe ich gelesen, dass LU Decomposition im Grunde nur ein modifizierter Gauss Algo ist. Ich weiß, dass bei der LR Zerlegung die Matrix A in 2 triangulare Matrizen zerlegt wird, aber ich finde leider keine Beschreibung WIE dieser Algo geht (selbst im Wiki-Artikel steht nichts).

Anmerkung zu meinem Posting: Habe jetzt eine Beschreibung der LR-Zerlegung gefunden. So wie ich das sehe IST die LR-Zerlegung der ganz normale Gauss-Algorithmus, dh man erzeugt eine obere Dreiecksmatrix. Nur merkt man sich ferner die Zahlen, mit denen man die 0er erzeugt hat und schreibt sie in eine 2. Matrix L unterhalb der Hauptdiagonalen. Dieses L und R kann man dann benutzen um ein LGS mit gleichem A und anderem d schnell zu lösen. Stimmt das?

Löser2000 schrieb:

Stimmt das?

Ja. Wenn du Pivotisierung verwendest, musst du natürlich auch noch speichern, welche Zeilen du vertauscht hast, damit du den Vektor d umsortieren kannst.

Löser2000 schrieb:

Noch etwas zu deinem Vorschlag mit der LU decomposition. Mir haben mehrere Leute gesagt, dass das direkte Lösen eines allgemeinen LGS am effizientesten per "Gaussian Elimination with parial pivoting" geht. Mir wurde gesagt, dass die LU Decomposition für das einmalige Lösen (was ich ja brauche) langsamer ist und nur Vorteile hat, wenn man das gleiche LGS mit wechselnden "rechten Seiten" lösen muss. Stimmt das?

Ja es ist ein wenig langsamer. Aber eigentlich nicht in einer Größenordnung, dass es sonderlich ins Gewicht fallen sollte.

Löser2000 schrieb:

Ferner habe ich gelesen, dass LU Decomposition im Grunde nur ein modifizierter Gauss Algo ist. Ich weiß, dass bei der LR Zerlegung die Matrix A in 2 triangulare Matrizen zerlegt wird, aber ich finde leider keine Beschreibung WIE dieser Algo geht (selbst im Wiki-Artikel steht nichts).

http://en.wikipedia.org/wiki/LU_decomposition unter dem Punkt External links. Dazu sollte man eigentlich recht viel finden.

Man beachte, dass eine LU-Zerlegung nicht für jede Matrix existiert.

Wichtig ist, dass du deine Matrix so speicherst, dass die Zeilen zusammenhängend im Speicher stehen, dann fällt der Zugriff über einen Zeiger nicht wirklich ins Gewicht, dank Caching.

Profi-Progger schrieb:

Man beachte, dass eine LU-Zerlegung nicht für jede Matrix existiert.

Mit Pivotisierung für jede invertierbare Matrix.

Profi-Progger schrieb:

Wichtig ist, dass du deine Matrix so speicherst, dass die Zeilen zusammenhängend im Speicher stehen, dann fällt der Zugriff über einen Zeiger nicht wirklich ins Gewicht, dank Caching.

Die Frage ist halt, ob es überhaupt etwas bringt.