Analysis of some vector extrapolation methods for solving systems of linear equations (Q1347029)

There are known some so called vector extrapolation methods for solving nonsymmetric systems of linear equations, \(Ax = f\), where \(A\) is an \(N \times N\) nonsingular matrix and \(f \in \mathbb{R}^N\). Two of them, the ``reduced rank extrapolation'' (briefly, RRE) and the ``minimal polynomial extrapolation'' (MPE) are considered in more detail and compared to each other in the present paper. They both are Krylov subspace methods. The authors begin by stating the common part of the two procedures. Writing \(A = M - L\), the system \(Ax = f\) takes the form \(x = Bx + b\) where \(B = M^{-1} L\), \(b = M^{-1} f\). For the \(k\)th iterate \(x_k\), defined by the sequence \(x_{k+1} = Bx_k + b\), there is a scheme which in appearance is the same in both methods. The convergence of \(\{x_k\}\) is achieved in a finite number of iterations. The residual of \(x_k\) is defined by \(b - Cx_k\) with \(C = I - B\). It is denoted by \(r_k\) for RRE and by \(\rho_k\) for MPE. New expressions of the residuals constitute an essential part of the contribution of this paper. It turns out that RRE is an orthogonal projection method. \(|r_k |\) has an expression of the form \(|r_k|= \sin \theta_k |r_0|\). Thus \(|r_k |\leq |r_0|\); even \(|r_k |\leq |r_{k-1}|\) holds always true. This means that RRE cannot break down at all. There may occur a stagnation, however. In fact, \(r_k = r_0\) if and only if \((r_0, C^j r_0) = 0\) for \(j =1, 2, \dots, k\). Further, \(|r_{2j} |= |r_{2j + 1}|\), \(j = 0, 1, 2, \dots,\) for all \(r_0\), whenever \(C\) is a skew symmetric nonsingular matrix. MPE, in turn, is an oblique projection method. A relation \(|\rho_k |^2 = (1 - \cos^2 \varphi_k) \cos^{-2} \varphi_k |\rho_0|^2\) is valid and indicates that MPE breaks down when \(\cos \varphi_k = 0\). Another disadvantage of the MPE is the fact that \(|\rho_k|\leq |\rho_0 |\) only if \(\varphi_k \in [0, \pi/4]\). From \(r_0 = \rho_0\) it always follows that \(|r_k|\leq |\rho_k|\). There is a set \(r_0 = \rho_0\) such that a breakdown in the MPE corresponds to a stagnation of the RRE. Finally, in section 5, the authors consider an algorithm called imcomplete form of RRE. A special case of it turns out to be mathematically equivalent to GMRES\((m)\), i.e. to the restarted version of the GMRES method. They prove that GMRES\((m)\) converges for any initial vector \(x_0\) whenever \(C\) is a nonsingular skew symmetric matrix and \(m \geq 2\). The last section contains some numerical examples.