NGMRES convergence analysis and proof of acceleration for contractive and noncontractive iterations
Abstract
This paper gives the first convergence analysis and proof of acceleration for nonlinear GMRES (NGMRES) applied to contractive and noncontractive fixed point iterations (FPIs) for solving general nonlinear systems. Our main results are that in both the contractive and noncontractive cases, the ratio gain of the optimization problem is the mechanism responsible for accelerating (or enabling) convergence. Our analysis also reveals a second important quantity related to the optimization problem, which directly predicts the linear convergence rate at each iteration and proves it is at most 1; hence only higher order terms are responsible for NGMRES non-convergence. Numerical results for several challenging nonlinear test problems are given that illustrate the theory, show how the acceleration improves convergence, show that the quantity predicting the linear convergence rate is remarkably accurate and moreover can be useful for adaptively choosing NGMRES depth, show how restarts can improve convergence in noncontractive iterations, show how NGMRES is naturally suited for finding distinct solutions of a multi-solution PDE, and that NGMRES can perform better than Anderson acceleration when applied to superlinear FPIs.
Related
- On a blended Anderson / NGMRES acceleration for the Navier-Stokes Picard iteration: convergence analysis and adaptive depth selection
- A nonmonotone globalization framework for Anderson acceleration for contractive and nonexpansive fixed point problems
- Weak and Strong Convergence of an Implicit Iteration for Hemi-Contractive Semigroups in Banach Spaces
- Convergence of alternating score-system iterations for regularized Landau particle dynamics
- Convergence and acceleration of a nonlinear fixed-point iteration for computing the Fitness Centrality of general graphs
BibTeX
@misc{he2026ngmres,
title = {{NGMRES convergence analysis and proof of acceleration for contractive and noncontractive iterations}},
author = {Y. He and L. Rebholz and M. Xiao},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2607.14268},
eprint = {2607.14268},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2607.14268},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - NGMRES convergence analysis and proof of acceleration for contractive and noncontractive iterations
AU - Y. He
AU - L. Rebholz
AU - M. Xiao
PY - 2026
DA - 2026/09/04
PB - arXiv
DO - 10.48550/arxiv.2607.14268
UR - https://arxiv.org/abs/2607.14268
AB - This paper gives the first convergence analysis and proof of acceleration for nonlinear GMRES (NGMRES) applied to contractive and noncontractive fixed point iterations (FPIs) for solving general nonlinear systems. Our main results are that in both the contractive and noncontractive cases, the ratio gain of the optimization problem is the mechanism responsible for accelerating (or enabling) convergence. Our analysis also reveals a second important quantity related to the optimization problem, which directly predicts the linear convergence rate at each iteration and proves it is at most 1; hence only higher order terms are responsible for NGMRES non-convergence. Numerical results for several challenging nonlinear test problems are given that illustrate the theory, show how the acceleration improves convergence, show that the quantity predicting the linear convergence rate is remarkably accurate and moreover can be useful for adaptively choosing NGMRES depth, show how restarts can improve convergence in noncontractive iterations, show how NGMRES is naturally suited for finding distinct solutions of a multi-solution PDE, and that NGMRES can perform better than Anderson acceleration when applied to superlinear FPIs.
ER -