pipette
ENEnglish

When Windowed Anderson Acceleration Converges Faster

Gilad Lerman, Teng Zhang

Preprint

En palabras de los autores

Windowed Anderson acceleration AA() combines at most recent iterates by least squares. For a real affine contraction with , we determine exactly when AA() converges from every starting point with an asymptotic factor below . We give a polynomial criterion for this improvement and an equivalent spectral condition: there is no probability distribution on the phases of the eigenvalues of modulus whose first cosine moments are . If such a distribution exists, we construct a starting point from which AA() reproduces fixed-point iteration at every step. Otherwise, over a fixed number of consecutive steps, every run contracts the residual norm by a common factor strictly smaller than the corresponding power of . The polynomial criterion also gives explicit convergence-rate bounds with constants independent of the dimension. When equals the spectral radius, this characterizes improvement over the asymptotic convergence factor of fixed-point iteration. For general affine contractions, the asymptotic factor never exceeds the numerical radius of , and a related moment condition gives a uniform upper bound strictly below that radius.

Resultado principalEl resumen no menciona limitaciones.

Apareció: jueves, 22 de octubre. arXiv. Preprint, todavía sin revisión por pares.