Author(s) :
Jörg Liesen
,
Petr Tichý
Preprint series of the Institute of Mathematics, Technische Universität Berlin
Preprint 34-2004
MSC 2000
- 15A09 Matrix inversion, generalized inverses
-
65F10 Iterative methods for linear systems
ZDM : N30
PACS : 02.60.Dc
CR : G.1.3
Abstract :
We investigate the convergence behavior of the conjugate gradient (CG) method and the minimal residual (MINRES) method when applied to a linear algebraic system with a symmetric definite tridiagonal Toeplitz coefficient matrix~$A$. Our main interest is to understand the behavior of the two methods for different right hand sides (initial residuals): The first one leads to the worst-case convergence quantity (relative $A$-norm of the error for CG, relative Euclidean residual norm for MINRES) in the next-to-last iteration step, and the second one has the property that its coordinates in the eigenvectors of $A$ are not biased towards a certain eigenvector direction (in other words, all these coordinates are of approximately equal size). We compare the results obtained for these right-hand sides with the classical convergence bound based on the condition number of $A$, and show when and why this bound is reasonably tight. For application of our results we choose the model problem of the one-dimensional Poisson equation with Dirichlet boundary conditions. For this problem we identify the data (source term and boundary conditions) that lead to the worst convergence quantities in the next-to-last steps of CG as well as MINRES when applied to the discretized problem. We also relate our results to previous work on the same model problem (particularly by Naiman, Babuska and Elman).
Keywords :
Krylov subspace methods, CG, MINRES, convergence analysis, Toeplitz matrices, Poisson equation