Haltekriterien für iterative lineare Löser, die auf nahezu singuläre Systeme angewendet werden

Betrachte mit nahezu singulär, was bedeutet, dass es einen sehr kleinen Eigenwert von gibt. Das übliche einer iterativen Methode basiert auf dem Residuum und die Iterationen anhalten können, wenn mit der Iterationsnummer. Aber in dem Fall, den wir betrachten, könnte es einen großen Fehler , der in dem mit dem kleinen Eigenwert assoziierten Eigenraum lebt, was einen kleinen Rest ergibt . Angenommen, der anfängliche Rest ist groß, dann kann es vorkommen, dass wir anhalten $Ax=b$ $A$ $\lambda_0$ $A$ $r_n:=b-Ax_n$ $\|r_n\|/\|r_0\|<tol$ $n$ $v$ $\lambda_0$ $Av=\lambda_0v$ $r_0$ $\|r_n\|/\|r_0\|<tol$ aber der Fehler $x_n-x$ ist immer noch groß. Was ist in diesem Fall eine bessere Fehleranzeige? Ist $\|x_{n}-x_{n-1}\|$ Ein guter Kandidat?

linear-algebra Hui Zhang
quelle

Vielleicht möchten Sie über Ihre Definition von "fast singulär" nachdenken. Die Matrix (mit und der Identitätsmatrix) hat einen sehr kleinen Eigenwert, ist aber weit davon entfernt, singulär zu sein, wie jede Matrix sein könnte.

I \cdot ϵ

$I \cdot \epsilon$

ϵ ≪ 1

$\epsilon\ll 1$

I

$I$

David Ketcheson

Auchscheint die falsche Schreibweise. ist typischer, nein?

| | r_{n} / r_{0} | |

$||r_n/r_0||$

| | r_{n} | | / | | r_{0} | |

$||r_n||/||r_0||$

Bill Barth

Ja, du hast recht, Bill! Ich werde diesen Fehler korrigieren.

Hui Zhang

Was ist mit? und was ist dein Algorithmus genau?

‖ b - A x ‖ / ‖ b ‖

$\| b - Ax \| / \| b \|$

Shuhalo

Nachtrag: Ich denke, der folgende Aufsatz befasst sich ziemlich genau mit den schlecht konditionierten Systemen, über die Sie sich Sorgen machen, zumindest wenn Sie CG verwenden: Axelson, Kaporin: Fehler-Normschätzung und Stopp-Kriterien in vorkonditionierten konjugierten Gradienteniterationen. DOI: 10.1002 / nla.244

shuhalo

Antworten:

Bitte verwenden Sie niemals den Unterschied zwischen aufeinanderfolgenden Iterationen, um ein Stoppkriterium zu definieren. Diese Fehldiagnose führt zu einer Stagnation der Konvergenz. Die meisten nicht symmetrischen Matrixiterationen sind nicht monoton, und selbst GMRES in exakter Arithmetik ohne Neustart kann für eine beliebige Anzahl von Iterationen (bis zur Dimension der Matrix) stagnieren, bevor sie plötzlich konvergieren. Siehe Beispiele in Nachtigal, Reddy und Trefethen (1993) .

Eine bessere Möglichkeit, die Konvergenz zu definieren,

In der Regel interessiert uns die Genauigkeit unserer Lösung mehr als die Größe des Rests. Insbesondere möchten wir garantieren, dass die Differenz zwischen einer Näherungslösung und der exakten Lösung erfüllt für einige Benutzer angegebenen . Es stellt sich heraus, dass dies erreicht werden kann, indem ein so gefunden wird, dass wobei der kleinste singuläre Wert von , bedingt durch $x_n$ $x$

| x_{n} - x | < c

$|x_n - x| < c$

c

$c$

x_{n}

$x_n$

| EIN x_{n} - b | < c ϵ

$|A x_n - b| < c\epsilon$

ϵ

$\epsilon$

A

$A$

\begin{aligned} | x_{n} - x | & = | A^{- 1} A (x_{n} - x) | \\ \leq \frac{1}{ϵ} | A x_{n} - A x | \\ = \frac{1}{ϵ} | A x_{n} - b | \\ < \frac{1}{ϵ} \cdot c ϵ = c \end{aligned}

$\begin{align} |x_n - x| &= |A^{-1} A (x_n - x)| \\ & \le \frac 1 \epsilon |A x_n - A x| \\ & = \frac 1 \epsilon |A x_n - b| \\ & < \frac 1 \epsilon \cdot c \epsilon = c \end{align}$

wobei wir verwendet haben, dass der größte Singularwert von (zweite Zeile) ist und dass genau (dritte Zeile) löst . $1/\epsilon$ $A^{-1}$ $x$ $A x = b$

Abschätzen der kleinste Einzelwert $\epsilon$

Eine genaue Schätzung des kleinsten Singularwerts ist normalerweise nicht direkt aus dem Problem verfügbar, kann jedoch als Nebenprodukt eines konjugierten Gradienten oder einer GMRES-Iteration geschätzt werden. Es ist zu beachten, dass, obwohl Schätzungen der größten Eigenwerte und Singularwerte normalerweise nach nur wenigen Iterationen recht gut sind, eine genaue Schätzung des kleinsten Eigen- / Singularwerts normalerweise erst erhalten wird, wenn die Konvergenz erreicht ist. Vor der Konvergenz wird die Schätzung im Allgemeinen deutlich größer sein als der wahre Wert. Dies deutet darauf hin , dass Sie müssen tatsächlich die Gleichungen lösen , bevor Sie die richtigen Toleranz definieren . Eine automatische Konvergenztoleranz , die eine vom Benutzer bereitgestellte Genauigkeit nimmt $\epsilon$ $c\epsilon$ $c$ Für die Lösung und Schätzungen könnte der kleinste singuläre Wert mit dem aktuellen Stand der Krylov-Methode zu früh konvergieren, da die Schätzung von viel größer war als der wahre Wert. $\epsilon$ $\epsilon$

Anmerkungen

Die obige Diskussion funktioniert auch, wenn durch den links-vorkonditionierten Operator und den vorkonditionierten Rest oder wenn der rechts-vorkonditionierte Operator und der Fehler $A$ $P^{-1}A$ $P^{-1} (A x^n - b)$ $A P^{-1}$ $P (x_n - x)$ . Wenn ein guter Vorkonditionierer ist, wird der vorkonditionierten Operator gut konditionierte. Für links Präkonditionierung, bedeutet dies den vorkonditionierten Rest klein gemacht werden kann, aber der wahre Rest möglicherweise nicht. Für die richtige Vorkonditionierung giltwird leicht klein gemacht, aber der wahre Fehler $P^{-1}$ $|P(x_n - x)|$ $|x_n-x|$ möglicherweise nicht. Dies erklärt, warum die linke Vorkonditionierung besser ist, um Fehler klein zu machen, während die rechte Vorkonditionierung besser ist, um den Rest klein zu machen (und um instabile Vorkonditionierer zu debuggen).
In dieser Antwort finden Sie weitere Informationen zu Normen, die durch GMRES und CG minimiert wurden.
Die Schätzungen der extremalen Einzelwerte können unter Verwendung überwacht werden -ksp_monitor_singular_valuemit jedem PETSc Programm. Siehe KSPComputeExtremeSingularValues () singuläre Werte von Code zu berechnen.
Wenn GMRES mit singulären Werten zu schätzen, ist es entscheidend, dass Neustarts nicht verwendet werden (zB -ksp_gmres_restart 1000 , in PETSc).

Jed Brown
quelle

'' funktioniert auch, wenn A durch einen vorkonditionierten Operator ersetzt wird '' - Dies gilt jedoch nur für den vorkonditionierten Rest

wenn

verwendet wird. zum vorkonditionierten Fehler

, wenn

verwendet wird.

P^{- 1} r

$P^{-1}r$

P^{- 1} A

$P^{-1}A$

P^{- 1} δ x

$P^{-1}\delta x$

A P^{- 1}

$AP^{-1}$

Arnold Neumaier

Guter Punkt, ich habe meine Antwort bearbeitet. Beachten Sie, dass Sie mit dem rechtskonditionierten Fall

steuern können , indem Sie den Vorkonditionierer abwickeln (indem Sie

anwenden ).

P δ x

$P\delta x$

P^{- 1}

$P^{-1}$

Jed Brown

Ein anderer Weg , um dieses Problem zu betrachten , ist , die Werkzeuge zu prüfen , aus diskreten inversen Problemen, das heißt, die Probleme beinhalten die Lösung oder , wo sehr schlecht konditioniert ist (dh das Verhältnis zwischen dem ersten und dem letzten Singulärwert $Ax=b$ $\min ||Ax-b||_2$ $A$ $\sigma_1/\sigma_n$ groß ist ).

Hier haben wir verschiedene Methoden zur Auswahl des Abbruchkriteriums, und für ein iteratives Verfahren, würde ich das L-Kurve Kriterium empfehlen, da es nur Mengen handelt, die bereits verfügbar sind (HAFTUNGSAUSSCHLUSS: Mein Berater diese Methode Pionierarbeit geleistet, so dass ich auf jeden Fall bin voreingenommen gegen es). Ich habe dies mit Erfolg in einem iterativen Verfahren verwendet.

Die Idee ist es, die Restnorm zu überwachen und die Lösung Norm , wobei das $\rho_k=||Ax_k-b||_2$ $\eta_k=||x_k||_2$ $x_k$ $k$ -te Iteration ist. Wie Sie Iterierte, diese die Form eines L in einem loglog (rho, eta) Grundstück und an der Stelle , an der Ecke des L zu zeichnen beginnen , ist die optimale Wahl.

Auf diese Weise können Sie ein Kriterium implementieren, bei dem Sie nach dem Überqueren der Ecke ein Auge auf die Steigung von $(\rho_k,\eta_k)$ ), und dann die Iterierte wählen , die an der Ecke lag.

Die Art und Weise, wie ich es gemacht habe, beinhaltete das Speichern der letzten 20 Iterationen und wenn der Gradient $abs(\frac{\log(\eta_k)-\log(\eta_{k-1})}{\log(\rho_k)-\log(\rho_{k-1})})$ war größer als ein gewisser Schwellwert 20 für aufeinanderfolgende Iterationen, wusste ich , dass ich auf dem vertikalen Teil der Kurve war und daß ich die Ecke passiert hatte. Ich habe dann die erste Iteration in meinem Array (dh die vor 20 Iterationen) als meine Lösung genommen.

Darüber hinaus gibt es weitere Einzelheiten der Verfahren zur Ecke zu finden, und diese Arbeit besser, aber eine beträchtliche Anzahl von Iterierten erfordern speichern. Spielen Sie mit ihm ein bisschen herum. Wenn Sie in Matlab sind, können Sie die Toolbox Regularisierung Werkzeuge verwenden, die einige dieser implementiert (insbesondere die „Ecke“ Funktion anwendbar ist).

Beachten Sie, dass dieser Ansatz besonders für große Probleme geeignet ist, da die zusätzliche Rechenzeit winzig ist.

OscarB
quelle

Danke vielmals! Im loglog (rho, eta) -Diagramm beginnen wir also rechts von der L-Kurve und enden oben auf L, oder? Ich weiß nur nicht , das Prinzip hinter diesem Kriterium. Können Sie erklären , warum es immer wie eine L - Kurve verhalten und warum wir um die Ecke wählen?

Hui Zhang

| | A x - b | |_{2} = | | e | |_{2}

$||Ax-b||_2=||e||_2$

e

$e$

b_{e x a c t} = b + e

$b_{exact}=b+e$ . Für weitere Analysen siehe Hansen, PC & O'Leary, DP (1993). Die Verwendung der L-Kurve bei der Regularisierung diskreter, schlecht gestellter Probleme. SIAM Journal on Scientific Computing, 14. Beachten Sie, dass ich den Beitrag gerade leicht aktualisiert habe.

OscarB

@HuiZhang: es ist nicht immer ein L. Wenn die Regularisierung nicht eindeutig ist , kann es ein Doppel - L sein, um zwei Kandidaten für die Lösung führt, eine mit Brutto featurse besser gelöst, das andere mit bestimmten Details besser gelöst. (Und natürlich können weitere komplexe Formen auftreten.)

Arnold Neumaier

Gilt die L-Kurve für schlecht konditionierte Probleme, bei denen es eine eindeutige Lösung geben sollte? Das heißt, ich bin in Problemen interessiert Ax = b , wobei b bekannt ist „genau“ und A fast singulär , aber immer noch technisch umkehrbar. Mir scheint, wenn Sie so etwas wie GMRES verwenden, ändert sich die Norm Ihrer aktuellen Schätzung von x im Laufe der Zeit nicht allzu sehr, insbesondere nach den ersten, jedoch vielen Iterationen. Es scheint mir , dass der vertikale Teil der L-Kurve tritt auf, weil in einem schlecht gestellten Problem keine eindeutige / gültige Lösung ist; Wäre dieses vertikale Merkmal bei allen schlecht konditionierten Problemen vorhanden?

Nukeguy

An einem Punkt, erreichen Sie eine solche vertikale Linie, in der Regel , weil die numerische Fehler in Ihrer Lösungsmethode Ergebnis in || Ax-b || nicht abnehmend. Sie haben jedoch Recht, dass bei solchen rauschfreien Problemen die Kurve nicht immer wie ein L aussieht, was bedeutet, dass Sie in der Regel nur wenige Ecken zur Auswahl haben und eine über die andere wählen kann schwierig sein. Ich glaube, dass das Papier, auf das ich oben in meinem Kommentar verwiesen habe, kurz rauschfreie Szenarien behandelt.

OscarB

Haltekriterien für iterative lineare Löser, die auf nahezu singuläre Systeme angewendet werden

Antworten:

Eine bessere Möglichkeit, die Konvergenz zu definieren,

Abschätzen der kleinste Einzelwertϵϵ\epsilon

Anmerkungen

Abschätzen der kleinste Einzelwert $\epsilon$