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
    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
    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
    0 references
    0 references
    0 references