Vorkonditionierung und Auswirkungen auf die Präzision der Lösung von LSE

8

In meinen Kursen zur numerischen Analyse wurde mir beigebracht, dass die Haupt- und Hauptmotivation für die Vorkonditionierung linearer Gleichungssysteme darin besteht, die Konvergenzrate iterativer Löser für diese LSE zu erhöhen.

Aber gibt es einen Einfluss auf die Genauigkeit der berechneten Lösung?

Ich kann mich an ein Ergebnis zur Genauigkeit der berechneten Lösung der Gaußschen Eliminierung erinnern, das in Matrixberechnungen von Golub und Van Loan (S. 122) zu finden ist. Die Bedingungsnummer (in Bezug auf eine bestimmte Norm) beeinflusst tatsächlich die Genauigkeit der von diesem Algorithmus berechneten numerischen Lösung.

Man könnte erwarten, dass etwas Ähnliches für Lösungen gilt, die beispielsweise durch konjugierte Gradienten erhalten werden. Ich glaube, ich habe dies in einem Computerexperiment beobachtet. Als ich die Conjugate-Gradientenmethode (lange) auf einem nicht vorkonditionierten System ausführen ließ, bis ein Stoppkriterium erfüllt war, zeigte die berechnete Lösung immer noch einen hohen Rest. Ich frage mich also, ob niedrigere Bedingungszahlen nicht nur zu niedrigeren Laufzeiten führen, sondern auch zu einem niedrigeren Rest (oder Fehler) in der berechneten Lösung. Beachten Sie, dass dies notwendigerweise eine Frage der numerischen Stabilität ist, was erfordert, dass wir in ungenauen Arithmetiken arbeiten.

(Ich habe die gleiche Frage zu math.SE gestellt, aber ich denke, dass diese Seite angemessener sein könnte.)

linear-algebra condition-number Shuhalo
quelle
1
κ
Sie haben den Punkt meiner Frage verpasst, der möglicherweise darauf zurückzuführen ist, dass ich das Wort ausgelassen habe. Ich habe es korrigiert, bitte lesen Sie die Frage jetzt noch einmal. - Beachten Sie, dass ich nicht nach der Konvergenzrate frage, sondern nach der 'Qualität' der Lösung, wie auch immer man dies definieren kann.
Shuhalo

Antworten:

5

Die Genauigkeit der Gaußschen Eliminierung ist nicht an die Bedingungsnummer gebunden. Es gibt ein Beispiel für eine gut konditionierte Matrix in Trefethen und Bau (und wahrscheinlich auch anderswo), für die die Gaußsche Eliminierung in Bezug auf die Matrixgröße exponentiell instabil ist.

ABxκ(A)κ(B)κ(AB)

Vorkonditionierung macht jedenfalls zwei Dinge:

  1. Dadurch wird die Lösung in einer kleinen Anzahl von Vektoren gut dargestellt, die zu Beginn der Iteration auftreten.
  2. Es macht die Norm, in der wir die Optimalität über einen Unterraum bewerten, näher an der Norm des Fehlers als an der Norm des Residuums.

Es liegt an Ihnen, ob der Fehler klein oder der Rest klein sein soll.

Jed Brown
quelle