TITLE:
SVD-MPE: An SVD-Based Vector Extrapolation Method of Polynomial Type
AUTHORS:
Avram Sidi
KEYWORDS:
Vector Extrapolation, Minimal Polynomial Extrapolation, Singular Value Decomposition, Krylov Subspace Methods
JOURNAL NAME:
Applied Mathematics,
Vol.7 No.11,
July
21,
2016
ABSTRACT: An important problem that arises in
different areas of science and engineering is that of computing the limits of
sequences of vectors , where , N being very large. Such sequences arise, for
example, in the solution of systems of linear or nonlinear equations by
fixed-point iterative methods, and are simply the required solutions. In most cases
of interest, however, these sequences converge to their limits extremely
slowly. One practical way to make the sequences converge more quickly is to
apply to them vector extrapolation methods. Two types of methods exist in the
literature: polynomial type methods and epsilon algorithms. In most
applications, the polynomial type methods have proved to be superior convergence
accelerators. Three polynomial type methods are known, and these are the
minimal polynomial extrapolation (MPE), the reduced rank extrapolation (RRE),
and the modified minimal polynomial extrapolation (MMPE). In this work, we
develop yet another polynomial type method, which is based on the singular
value decomposition, as well as the ideas that lead to MPE. We denote this new
method by SVD-MPE. We also design a numerically stable algorithm for its
implementation, whose computational cost and storage requirements are minimal.
Finally, we illustrate the use of SVD-MPE with numerical examples.