Meines Wissens gibt es 4 Möglichkeiten, ein lineares Gleichungssystem zu lösen (korrigieren Sie mich, wenn es mehr gibt):
- Wenn die Systemmatrix eine quadratische Matrix mit vollem Rang ist, können Sie die Cramer-Regel verwenden.
- Berechnen Sie die Inverse oder die Pseudoinverse der Systemmatrix.
- Verwenden Sie Matrixzerlegungsmethoden (Gaußsche oder Gauß-Jordan-Eliminierung wird als LU-Zerlegung betrachtet).
- Verwenden Sie iterative Methoden, z. B. die konjugierte Gradientenmethode.
Tatsächlich möchten Sie fast nie die Gleichungen mit der Cramer-Regel lösen oder die Inverse oder Pseudoinverse berechnen, insbesondere für hochdimensionale Matrizen. Die erste Frage ist daher, wann Sie Zerlegungsmethoden bzw. iterative Methoden verwenden müssen. Ich denke, es hängt von der Größe und den Eigenschaften der Systemmatrix ab.
Die zweite Frage ist nach Ihrem Kenntnisstand, welche Art von Zerlegungsmethoden oder iterativen Methoden für eine bestimmte Systemmatrix im Hinblick auf numerische Stabilität und Effizienz am besten geeignet sind.
Beispielsweise wird das konjugierte Gradientenverfahren verwendet, um Gleichungen zu lösen, bei denen die Matrix symmetrisch und positiv bestimmt ist, obwohl es auch auf beliebige lineare Gleichungen angewendet werden kann, indem in konvertiert wird . Auch für eine positiv definierte Matrix können Sie die Cholesky-Zerlegungsmethode verwenden, um die Lösung zu suchen. Aber ich weiß nicht, wann ich die CG-Methode und wann ich die Cholesky-Zerlegung wählen soll. Meiner Meinung nach sollten wir die CG-Methode für große Matrizen verwenden.
Für rechteckige Matrizen können wir entweder QR-Zerlegung oder SVD verwenden, aber ich weiß auch nicht, wie ich eine davon auswählen soll.
Für andere Matrizen kann ich jetzt keinen geeigneten Löser auswählen, wie Hermitian / Symmetric-Matrizen, Sparse-Matrizen, Band-Matrizen usw.
quelle
Antworten:
Ihre Frage ist ein bisschen so, als würden Sie fragen, welchen Schraubendreher Sie je nach Laufwerk wählen sollen (Steckplatz, Phillips, Torx, ...): Abgesehen davon, dass es zu viele gibt , hängt die Wahl auch davon ab, ob Sie nur eine Schraube festziehen oder einen zusammenbauen möchten ganze Reihe von Bibliotheksregalen. Als Teilantwort auf Ihre Frage sollten Sie jedoch einige Punkte beachten, wenn Sie eine Methode zur Lösung des linearen Systems A x = b auswählenAx=b . Ich werde mich auch auf invertierbare Matrizen beschränken; Die Fälle von über- oder unterbestimmten Systemen sind eine andere Sache und sollten eigentlich getrennte Fragen sein.
Wie Sie richtig bemerkt, Option 1 und 2 sind direkt aus: Computing und ist die inverse Matrix Anwendung eine enorm schlechte Idee, da es sehr viel teurer und oft numerisch weniger stabil ist als einer der anderen Algorithmen anwenden. Das lässt Sie mit der Wahl zwischen direkten und iterative Methoden. Das erste, was zu beachten ist, ist nicht die Matrix , sondern was Sie von der numerischen Lösung ˜ x erwartenA x~ :
Da es kein kostenloses Mittagessen gibt, müssen Sie sich normalerweise für einen Kompromiss zwischen beiden entscheiden. Danach schauen Sie sich die Matrix (und Ihre Hardware) an, um eine gute Methode (bzw. die Methode, für die Sie eine gute Implementierung finden können) zu finden. (Beachten Sie, wie ich es vermieden habe, hier "am besten" zu schreiben ...) Die relevantesten Eigenschaften sind hierA
In diesem Sinne müssen Sie dann die (große) Literatur durchsuchen und die verschiedenen Methoden bewerten, die Sie für Ihr spezifisches Problem finden. Hier einige allgemeine Bemerkungen:
Dies gilt auch für (große) Sparse-Matrizen, wenn keine Speicherprobleme auftreten: Sparse-Matrizen weisen im Allgemeinen keine spärliche LU-Zerlegung auf, und wenn die Faktoren nicht in den (schnellen) Speicher passen, werden diese Methoden unbrauchbar.
Wenn Sie lineare Systeme wiederholt mit derselben Matrix und verschiedenen rechten Seiten lösen müssen, können direkte Methoden immer noch schneller sein als iterative Methoden, da Sie die Zerlegung nur einmal berechnen müssen. (Dies setzt eine sequentielle Lösung voraus. Wenn Sie alle rechten Seiten gleichzeitig haben, können Sie Block-Krylov-Methoden verwenden.)
Dies sind natürlich nur sehr grobe Richtlinien: Für jede der obigen Aussagen gibt es wahrscheinlich eine Matrix, für die das Gegenteil zutrifft ...
Da Sie in den Kommentaren nach Referenzen gefragt haben, finden Sie hier einige Lehrbücher und Übersichtsartikel, um Ihnen den Einstieg zu erleichtern. (Weder diese noch die Menge sind umfassend; diese Frage ist viel zu weit gefasst und hängt zu stark von Ihrem speziellen Problem ab.)
quelle
Der Entscheidungsbaum in Abschnitt 4 des entsprechenden Kapitels im NAG Library Manual beantwortet (teilweise) einige Ihrer Fragen.
quelle
Die Eigenbibliotheksdokumentation hat auch eine schöne Übersichtsseite mit vielen Informationen zu verschiedenen Matrixzerlegungen:
http://eigen.tuxfamily.org/dox/group__TopicLinearAlgebraDecompositions.html
quelle