Analysis of some vector extrapolation methods for solving systems of linear equations (Q1347029)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Analysis of some vector extrapolation methods for solving systems of linear equations |
scientific article |
Statements
Analysis of some vector extrapolation methods for solving systems of linear equations (English)
0 references
29 April 1996
0 references
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.
0 references
reduced rank extrapolation
0 references
minimal polynomial extrapolation
0 references
vector extrapolation methods
0 references
nonsymmetric systems of linear equations
0 references
Krylov subspace methods
0 references
convergence
0 references
orthogonal projection method
0 references
algorithm
0 references
GMRES method
0 references
numerical examples
0 references