Verständnis der Konvergenzrate für iterative Methoden

Laut Wikipedia wird die Konvergenzrate als spezifisches Verhältnis der Vektornormen ausgedrückt. Ich versuche, den Unterschied zwischen "linearen" und "quadratischen" Raten zu verschiedenen Zeitpunkten (im Grunde genommen "am Anfang" der Iteration und "am Ende") zu verstehen. Könnte man sagen, dass:

• $e_{k+1}$$x_{k+1}$$\|e_k\|$

• Bei quadratischer Konvergenz ist die Norm des Fehlers des iterativen durch$e_{k+1}$$x_{k+1}$$\|e_k\|^2$

Eine solche Interpretation würde bedeuten, dass mit ein paar (wenigen) Iterationen des linear konvergenten Algorithmus A1 (zufällige Initialisierung angenommen) ein kleinerer Fehler erreicht würde als mit ein paar Iterationen des quadratisch konvergenten Algorithmus A2. Da sich der Fehler jedoch verringert und aufgrund der Quadrierung, würden spätere Iterationen einen kleineren Fehler bei A2 bedeuten.

Ist die obige Interpretation gültig? Beachten Sie, dass der Geschwindigkeitskoeffizient ignoriert wird .$\lambda$

$e_k$$\lambda$$k\to\infty$

Beispielsweise stellen Sie bei Optimierungsmethoden erster Ordnung häufig eine anfänglich schnelle Abnahme des Fehlers fest, die sich dann einpendelt. Bei der Newton-Methode hingegen kann es eine Weile dauern, bis die superlineare (oder quadratische) Konvergenz einsetzt (schließlich ist sie nur lokal superlinear konvergent). Aus diesem Grund ist es üblich, entweder mit ein paar Gradientenschritten zu beginnen, bevor Sie zu einer Newton-Methode wechseln, oder Homotopie- oder Quasi-Newton-Methoden zu verwenden, die sich anfangs als Methoden erster Ordnung verhalten und sich in eine Newton-Methode verwandeln, wenn Sie sich dem nähern Ziel.

$e_{k+1} \le \lambda_1 e_k$$\lambda_1<1$$e_{k+1} \le \lambda_2 e_k^2$$\lambda_2$$\lambda_2 e_1<1$- Das heißt, dass Ihre anfängliche Vermutung nahe genug ist. Dies ist ein häufig beobachtetes Verhalten: Quadratisch konvergente Algorithmen müssen "nah genug" an der Lösung gestartet werden, um zu konvergieren, während linear konvergente Algorithmen in der Regel robuster sind. Dies ist ein weiterer Grund, warum man häufig mit einigen Schritten eines linearen Konvergenzalgorithmus (z. B. der Methode mit dem steilsten Abstieg) beginnt, bevor man zu effizienteren Methoden (z. B. der Newton-Methode) übergeht.

Die Interpretation ist qualitativ korrekt.

Beachten Sie, dass lineare und quadratische Konvergenz in Bezug auf den schlimmsten Fall gegeben sind. Die Situation in einem bestimmten Algorithmus kann besser sein als die, die Sie aus der von Wolfgang Bangerth gegebenen Worst-Case-Analyse erhalten, obwohl die qualitative Situation normalerweise dieser Analyse entspricht.

In konkreten Algorithmen (z. B. bei der Optimierung) ist es oft sinnvoll, zuerst mit einer billigen, aber nur linear konvergenten Methode zu iterieren, bis der Fortschritt langsam wird, und dann mit einer quadratisch (oder zumindest superlinear) konvergenten Methode zu beenden. In der Praxis ist die superlineare Konvergenz in der Regel so gut wie die quadratische Konvergenz, nur weil der anfängliche, langsam konvergierende Teil tendenziell die Gesamtarbeit dominiert.