Minimal polynomial and reduced rank extrapolation methods are related
- PDF / 666,399 Bytes
- 20 Pages / 439.642 x 666.49 pts Page_size
- 64 Downloads / 192 Views
Minimal polynomial and reduced rank extrapolation methods are related Avram Sidi1
Received: 6 April 2016 / Accepted: 9 August 2016 © Springer Science+Business Media New York 2016
Abstract Minimal Polynomial Extrapolation (MPE) and Reduced Rank Extrapolation (RRE) are two polynomial methods used for accelerating the convergence of sequences of vectors {x m }. They are applied successfully in conjunction with fixedpoint iterative schemes in the solution of large and sparse systems of linear and nonlinear equations in different disciplines of science and engineering. Both methods produce k approximations k s k to the limit or antilimit of {x m } that are of the form γ x with sk = i i i=0 i=0 γi = 1, for some scalars γi . The way the two methods are derived suggests that they might, somehow, be related to each other; this has not been explored so far, however. In this work, we tackle this issue and show that RRE the vectors s MPE k and s k produced by the two methods are related in more than one way, and independently of the way the x m are generated. One of our results states RRE MPE that RRE stagnates, in the sense that s RRE k = s k−1 , if and only if s k does not exist. MPE Another result states that, when s k exists, there holds RRE MPE μk s RRE k = μk−1 s k−1 + νk s k
with μk = μk−1 + νk ,
RRE MPE for some positive scalars μk , μk−1 , and νk that depend only on s RRE k , s k−1 , and s k , respectively. Our results are valid when MPE and RRE are defined in any weighted inner product and the norm induced by it. They also contain as special cases the known results pertaining to the connection between the method of Arnoldi and the method of generalized minimal residuals, two important Krylov subspace methods for solving nonsingular linear systems.
Communicated by: Raymond H. Chan Avram Sidi
[email protected] http://www.cs.technion.ac.il/∼asidi 1
Computer Science Department, Technion - Israel Institute of Technology, Haifa 32000, Israel
A. Sidi
Keywords Vector extrapolation methods · Minimal polynomial extrapolation (MPE) · Reduced rank extrapolation (RRE) · Krylov subspace methods · Method of Arnoldi · Method of generalized minimal residuals · GMRES Mathematics Subject Classification (2010) 65B05 · 65F10 · 65F50 · 65H10
1 Introduction Minimal Polynomial Extrapolation (MPE) of Cabay and Jackson [5] and Reduced Rank Extrapolation (RRE) of Kaniel and Stein [18], Eddy [7], and Me˘sina [19] are two polynomial methods of convergence acceleration for sequences of vectors.1 They have been used successfully in different areas of science and engineering in accelerating the convergence of sequences that arise, for example, from application of fixed-point iterative schemes to large and sparse linear or nonlinear systems of equations. These methods and others were reviewed by Smith, Ford, and Sidi [32], Sidi, Ford, and Smith [29] and, more recently, by Sidi [27]. Their convergence and stability properties were analyzed in the papers by Sidi [23, 26], Sidi and Bridger [28], and Sidi and Shapira [30, 31]. Their
Data Loading...
