# Technical Report CS-2018-02

 TR#: CS-2018-02 Class: CS Title: A Convergence Study for Reduced Rank Extrapolation on Nonlinear Systems Authors: Avram Sidi PDF Currently accessibly only within the Technion network Abstract: Reduced Rank Extrapolation (RRE) is a polynomial type method used to accelerate the convergence of sequences of vectors $\{x_m\}$. 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 $s$ is the solution to the system of equations $x=f(x)$, first, a vector sequence $\{x_m\}$ is generated via the fixed-point iterative scheme $x_{m+1}=f(\xx_m)$, $m=0,1,\ldots,$ and next, RRE is applied to this sequence to accelerate its convergence. RRE producesapproximations $s_{n,k}$ to $s$ that are of the form $s_{n,k}=\sum^k_{i=0}\gamma_i x_{n+i}$ for some scalars $\gamma_i$ depending (nonlinearly) on $x_n, x_{n+1},\ldots, x_{n+k+1}$ and satisfying $\sum^k_{i=0}\gamma_i=1$. The convergence properties of RRE when applied in conjunction with linear $f(x)$ have been analyzed in different publications. In this work, we discuss the convergence of the $s_{n,k}$ obtained from RRE with nonlinear $f(x)$ (i)\,when $n\to\infty$ with fixed $k$, and (ii)\,in two so-called {\em cycling} modes. Copyright The above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/2018/CS/CS-2018-02), rather than to the URL of the PDF files directly. The latter URLs may change without notice.