Minimal polynomial and reduced rank extrapolation methods are related

详细信息    查看全文

• 作者：Avram Sidi
• 关键词：Vector extrapolation methods ; Minimal polynomial extrapolation (MPE) ; Reduced rank extrapolation (RRE) ; Krylov subspace methods ; Method of Arnoldi ; Method of generalized minimal residuals ; GMRES
• 刊名：Advances in Computational Mathematics
• 出版年：2017
• 出版时间：February 2017
• 年：2017
• 卷：43
• 期：1
• 页码：151-170
• 全文大小：
• 刊物类别：Computer Science
• 刊物主题：Computational Mathematics and Numerical Analysis; Mathematical Modeling and Industrial Mathematics; Mathematical and Computational Biology; Computational Science and Engineering; Visualization;
• 出版者：Springer US
• ISSN：1572-9044
• 卷排序：43

文摘

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 fixed-point 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 approximations s_k to the limit or antilimit of {x_m} that are of the form \(\boldsymbol {s}_{k}={\sum }^{k}_{i=0}\gamma _{i}\boldsymbol {x}_{i}\) with \({\sum }^{k}_{i=0}\gamma _{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 the vectors \(\boldsymbol {s}_{k}^{\textit {{\tiny {MPE}}}}\) and \(\boldsymbol {s}_{k}^{\textit {{\tiny {RRE}}}}\) 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 that RRE stagnates, in the sense that \(\boldsymbol {s}_{k}^{\textit {{\tiny {RRE}}}}=\boldsymbol {s}_{k-1}^{\textit {{\tiny {RRE}}}}\), if and only if \(\boldsymbol {s}_{k}^{\textit {{\tiny {MPE}}}}\) does not exist. Another result states that, when \(\boldsymbol {s}_{k}^{\textit {{\tiny {MPE}}}}\) exists, there holds$$\mu_{k}\boldsymbol{s}_{k}^{\textit{{\tiny{RRE}}}}=\mu_{k-1}\boldsymbol{s}_{k-1}^{\textit{{\tiny{RRE}}}}+ \nu_{k}\boldsymbol{s}_{k}^{\textit{{\tiny{MPE}}}}\quad \text{with}\quad \mu_{k}=\mu_{k-1}+\nu_{k}, $$for some positive scalars μ_k, μ_k−1, and ν_k that depend only on \(\boldsymbol {s}_{k}^{\textit {{\tiny {RRE}}}}\), \(\boldsymbol {s}_{k-1}^{\textit {{\tiny {RRE}}}}\), and \(\boldsymbol {s}_{k}^{\textit {{\tiny {MPE}}}}\), 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.KeywordsVector extrapolation methodsMinimal polynomial extrapolation (MPE)Reduced rank extrapolation (RRE)Krylov subspace methodsMethod of ArnoldiMethod of generalized minimal residualsGMRESCommunicated by: Raymond H. Chan