Auswahl einer Methode zum Lösen linearer Gleichungen

31

Meines Wissens gibt es 4 Möglichkeiten, ein lineares Gleichungssystem zu lösen (korrigieren Sie mich, wenn es mehr gibt):

  1. Wenn die Systemmatrix eine quadratische Matrix mit vollem Rang ist, können Sie die Cramer-Regel verwenden.
  2. Berechnen Sie die Inverse oder die Pseudoinverse der Systemmatrix.
  3. Verwenden Sie Matrixzerlegungsmethoden (Gaußsche oder Gauß-Jordan-Eliminierung wird als LU-Zerlegung betrachtet).
  4. 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 Ax=b in konvertiert wird ATAx=ATb. 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.

Chaohuang
quelle
1
Hallo @chaohuang, und herzlich willkommen bei SciComp! Vielleicht möchten Sie diese Diskussion sehen: scicomp.stackexchange.com/questions/81/…
Paul
Hallo @Paul, danke für deine Kommentare, handelt es sich bei diesem Thread nur um spärliche Matrizen oder eine Matrix?
Chaohuang
6
Ihre Frage hat einen enormen Umfang und ist möglicherweise etwas zu weit gefasst für das Q & A-Format, das wir hier auf dem Stapelaustausch haben. Gibt es eine bestimmte Klasse von Matrixsystemen, an denen Sie interessiert sind?
Paul
3
@chaohuang Es gibt zahlreiche Bücher zu diesem Thema. Diese Frage ist ein bisschen so, als würde man einen Arzt fragen, wie er Behandlungen "allgemein" auswählt. Wenn Sie eine Frage stellen möchten, die nicht spezifisch für eine bestimmte Klasse von Problemen ist, sollten Sie sich mit der Arbeit vertraut machen, um etwas Genaues zu fragen. Erklären Sie andernfalls das spezifische Problem, mit dem Sie sich befassen.
Jed Brown
2
Aus den FAQ: Wenn Sie sich ein ganzes Buch vorstellen können, das Ihre Frage beantwortet, fragen Sie zu viel. Es gibt ganze Zeitschriften und Hunderte Bücher, mit dieser Frage verbunden sind .
David Ketcheson

Antworten:

45

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 erwartenAx~ :

  1. Wie genau muss es sein? Does haben , um das System zu Maschinengenauigkeit zu lösen, oder sind Sie zufrieden mit ~ x befriedigend (sagen wir) ~ x - x *< 10 - 3 , wobei x *x~x~x~x<103x ist die exakte Lösung?
  2. Wie schnell brauchst du das? Die einzige relevante Metrik hier ist die Uhrzeit auf Ihrer Computer - eine Methode, die perfekt auf einen riesigen Cluster skaliert, ist möglicherweise nicht die beste Wahl, wenn Sie nicht über eine dieser Karten verfügen, aber über eine dieser glänzenden neuen Tesla-Karten.

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

  • Die Struktur : Ist symmetrisch? Ist es dicht oder dünn? Banded?A
  • Die Eigenwerte : Sind sie alle positiv (dh ist positiv bestimmt)? Sind sie gruppiert? Haben einige von ihnen eine sehr kleine oder sehr große Größe?A

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:

  • 1000O(n2)O(n3)A symmetrisch und eindeutig positiv ist, würden Sie Cholesky verwenden.)

    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.

    A

  • AA

  • 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.)

Christian Clason
quelle
2
Ich mag deine Analogie zum Schraubenzieher!
Paul
@chaohuang Wenn dies Ihre Frage beantwortet, sollten Sie es akzeptieren. (Wenn nicht, können Sie gerne darauf hinweisen, was fehlt.)
Christian Clason
@ ChristianClason akzeptierte es. Ich wartete und hoffte, dass jemand etwas Licht in die Frage der rechteckigen Matrizen bringen könnte. Da es eine lange Zeit her ist, denke ich, wird es nie eine solche Antwort geben :(
Chaohuang
@ Chaohuang Vielen Dank. Wenn Sie immer noch an rechteckigen Matrizen interessiert sind, sollten Sie eine (verknüpfte) Frage zu "Wie wählt man eine Methode zur Lösung überbestimmter Systeme" stellen.
Christian Clason
Hier eine Referenz zur Verwendung von iterativen Methoden zur Lösung großer, spärlicher linearer Gleichungssysteme.
Chaohuang