A hybrid iterative method for symmetric positive definite linear systems
type: Item
instance of: scholarly article
title: A hybrid iterative method for symmetric positive definite linear systems
zbMATH Open document ID: 0853.65042
DOI: 10.1007/BF02142490
published in: Numerical Algorithms
publication date: 1997-01-05T00:00:00Z
review text: The method describes a combination of the conjugate gradient (CG) method and Richardson iteration to solve the system \(Ax= b\). Because of matrix-vector multiplications, the CG iterations are expensive as compared to the Richardson steps. After an approximate solution \(x_m\) and a corresponding residual \(r_m= b- Ax_m= p_m(A) r_0\) are obtained by \(m\) CG steps, Richardson iterations \(x_{k+ 1}= x_k+ \delta_k r_k\), \(r_k= b- Ax_k\), \(k= m\), \(m+ 1,\dots\) are computed. If \(I\) is an interval that approximately contains the eigenvalues of \(A\), then the \(\delta_k\) are chosen as the reciprocals of the Leja points \(z_k\) for the interval \(I\). The first \(m\) Leja points are defined as the zeros of the residual polynomial \(p_m(z)= (1- z/z_0)\cdots(1- z/z_{m- 1})\) and for \(k\geq m\), \(z_k\) is defined recursively as the \(z\in I\) that maximizes \(z|q_k(z)|\), where \(q_k(z)= (z- z_0)\cdots (z- z_{k- 1})\). This choice of the parameters \(\delta_k\) gives an asymptotically optimal rate of convergence, provided that the spectrum of \(A\) is included in \(I\). These Richaradson iterations are continued until convergence or until it is detected that the interval \(I\) is too small. In the latter case \(m\) new CG steps are performed, from which a new interval \(I\) is obtained and then Richardson iteration is resumed. It is explained in detail how to estimate \(I\) (i.e., the extreme eigenvalues of \(A\)) from the parameters generated by the CG steps. Usually \(m\) is relatively small so that a very efficient method results. Numerical results illustrate the method.
reviewed by: Adhemar Bultheel
Mathematics Subject Classification ID: 65F10
Mathematics Subject Classification ID: 15A42
zbMATH DE Number: 871276
zbMATH Keywords: symmetric positive definite linear systems
zbMATH Keywords: conjugate gradient method
zbMATH Keywords: numerical results
zbMATH Keywords: Richardson iteration
zbMATH Keywords: optimal rate of convergence
zbMATH Keywords: extreme eigenvalues
author: Daniela Calvetti
author: Lothar Reichel
MaRDI profile type: Publication
cites work: Hybrid procedures for solving linear systems
cites work: Q4309406
cites work: Adaptive Richardson iteration based on Leja points
cites work: Q3702408
cites work: Q3997799
cites work: Q5774541
cites work: A Hybrid Chebyshev Krylov Subspace Algorithm for Solving Nonsymmetric Systems of Linear Equations
cites work: Estimates of Eigenvalues for Iterative Methods
cites work: Q3359644
cites work: Chebyshev semi-iterative methods, successive overrelaxation iterative methods, and second order Richardson iterative methods. I, II
cites work: Calculation of Gauss Quadrature Rules
cites work: Q3909906
cites work: Sur certaines suites liées aux ensembles plans et leur application à la représentation conforme
cites work: A Hybrid GMRES Algorithm for Nonsymmetric Linear Systems
cites work: Approximate solutions and eigenvalue bounds from Krylov subspaces
cites work: The application of Leja points to Richardson iteration and polynomial preconditioning
cites work: Leapfrog variants of iterative methods for linear algebraic equations
cites work: Q5342712
full work available at URL: https://doi.org/10.1007/bf02142490
OpenAlex ID: W2011886482
description: scientific article; zbMATH DE number 871276