A convergence study for reduced rank extrapolation on nonlinear systems

DOI10.1007/S11075-019-00788-6zbMATH Open1442.65098arXiv1807.03199OpenAlexW2969266254MaRDI QIDQ2189405FDOQ2189405

Avram Sidi

Publication date: 15 June 2020

Published in: Numerical Algorithms (Search for Journal in Brave)

Abstract: Reduced Rank Extrapolation (RRE) is a polynomial type method used to accelerate the convergence of sequences of vectors $$. It is applied successfully in different disciplines of science and engineering in the solution of large and sparse systems of linear and nonlinear equations of very large dimension. If $$ is the solution to the system of equations $$, first, a vector sequence $$ is generated via the fixed-point iterative scheme $$, $m=0,1,ldots,$ and next, RRE is applied to this sequence to accelerate its convergence. RRE produces approximations $$ to $$ that are of the form $$ for some scalars $gamm{a}_i$ depending (nonlinearly) on $$ and satisfying $su{m}_{i=0}^{k}gamm{a}_i=1$. The convergence properties of RRE when applied in conjunction with linear $$ have been analyzed in different publications. In this work, we discuss the convergence of the $$ obtained from RRE with nonlinear $$ (i),when $noinfty$ with fixed $k$, and (ii),in two so-called {em cycling} modes.

Full work available at URL: https://arxiv.org/abs/1807.03199

Recommendations

• Convergence and Stability Properties of Minimal Polynomial and Reduced Rank Extrapolation Algorithms
• Nonlinear Schwarz iterations with reduced rank extrapolation
• Convergence theory of extrapolated iterative methods for a certain class of non-symmetric linear systems
• Model Reduction for a Class of Convergent Nonlinear Systems
• Componentwise fast convergence in the solution of full-rank systems of nonlinear equations
• A globally convergent inexact-Newton method for solving reducible nonlinear systems of equations
• Approximate norm descent methods for constrained nonlinear systems
• On the semiconvergence of extrapolated iterative methods for singular linear systems
• On the optimization of extrapolation methods for singular linear systems
• Convergence of extrapolated method for solving non-Hermitian linear systems

zbMATH Keywords

Krylov subspace methodsnonlinear equationsminimal polynomial extrapolationvector extrapolation methodsreduced rank extrapolationcycling mode

Mathematics Subject Classification ID

Iterative numerical methods for linear systems (65F10) Extrapolation to the limit, deferred corrections (65B05) Numerical solution of nonlinear eigenvalue and eigenvector problems (65H17)

Cites Work

• Title not available (Why is that?)
• Anderson Acceleration for Fixed-Point Iterations
• Extrapolation Methods for Vector Sequences
• Iterative Procedures for Nonlinear Integral Equations
• Title not available (Why is that?)
• Generalized inverses. Theory and applications.
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the Continuity of the Generalized Inverse
• Efficient implementation of minimal polynomial and reduced rank extrapolation methods
• Some results about vector extrapolation methods and related fixed-point iterations
• Extrapolation methods theory and practice
• Généralisations de la transformation de Shanks, de la table de Padé et de l'\(\varepsilon\)-algorithme
• Convergence acceleration for the iterative solution of the equations X = AX + f
• Acceleration Techniques for Iterated Vector and Matrix Problems
• Acceleration of Convergence of Vector Sequences
• Acceleration of the convergence of iterative processes and a method of solving systems of non-linear equations
• A Polynomial Extrapolation Method for Finding Limits and Antilimits of Vector Sequences
• LU implementation of the modified minimal polynomial extrapolation method for solving linear and nonlinear systems
• Perturbation theory for pseudo-inverses
• Title not available (Why is that?)
• On Error Bounds for Generalized Inverses
• Convergence Analysis for Anderson Acceleration
• The quadratic convergence of the topological epsilon algorithm for systems of nonlinear equations
• On a Device for Computing the e m (S n ) Transformation
• Row convergence theorems for generalised inverse vector-valued Padé approximants
• Extension and completion of Wynn's theory on convergence of columns of the epsilon table
• Upper bounds for convergence rates of acceleration methods with initial iterations
• Convergence and stability analyses for some vector extrapolation methods in the presence of defective iteration matrices
• Extrapolation vs. projection methods for linear systems of equations
• Convergence and Stability Properties of Minimal Polynomial and Reduced Rank Extrapolation Algorithms
• Computation of the periodic steady-state response of nonlinear networks by extrapolation methods
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the Solution of Systems of Equations by the Epsilon Algorithm of Wynn
• Accélération de la convergence en analyse numérique
• On the Convergence and Stability of the Epsilon Algorithm
• Analysis of some vector extrapolation methods for solving systems of linear equations
• Least-square acceleration of iterative methods for linear equations
• Vector Extrapolation Methods with Applications
• Convergence of intermediate rows of minimal polynomial and reduced rank extrapolation tables
• Minimal polynomial and reduced rank extrapolation methods are related
• Title not available (Why is that?)

Cited In (1)

• A survey of Shanks' extrapolation methods and their applications

Uses Software

• Anderson

This page was built for publication: A convergence study for reduced rank extrapolation on nonlinear systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2189405)