Technical Report CS0701

TR#:CS0701
Class:CS
Title: UPPER BOUNDS FOR CONVERGENCE RATES OF VECTOR EXTRAPOLATION METHODS ON LINEAR SYSTEMS WITH INITIAL ITERATIONS
Authors: A. Sidi and Y. Shapira
PDF - RevisedCS0701.revised.pdf
Abstract: The application of the minimal polynomial extrapolation (MPE) and the reduced rank extrapolation (RRE) to a vector sequence obtained by the linear iterative technique $x_{j+1} = Ax_j + b,\ j = 1,2,...,$ is considered. Both methods produce a two-dimensional array of approximations $s_{n,k}$ to the solution of the system $(I-A)x=b$. Here $s_{n,k}$ is obtained from the vectors $x_j, n \leq j \leq n+k+1$. It was observed in an earlier publication by the first author that the sequence $s_{n,k}, k = 1,2,...,$ for $n > 0$, but fixed, possess better convergence properties than the sequence $s_{0,k}, k = 1,2,...$ . A detailed theoretical explanation for this phenomenon is provided in the present work. This explanation is heavily based on approximations by incomplete polynomials. It is demonstrated by numerical examples when the matrix $A$ is sparse that cycling with $s_{n,k}$ for $n > 0$, but fixed, produces better convergence rates and costs less computationally than cycling with $s_{0,k}$. It is also illustrated numerically with a convection-diffusion problem that the former may produce excellent results where the latter may fail completely. As has been shown in an earlier publication, the results produced by $s_{0,k}$ are identical to the corresponding results obtained by applying the Arnoldi method or GMRES to the system $(I-A) x = b$.
CopyrightThe 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/1991/CS/CS0701), 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 1991
To the main CS technical reports page

Computer science department, Technion
admin