TR#: | CS-2018-02 |

Class: | CS |

Title: | A Convergence Study for Reduced Rank Extrapolation on Nonlinear Systems |

Authors: | Avram Sidi |

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.

To the list of the CS technical reports of 2018

To the main CS technical reports page