Author(s) :
Jörg Liesen
,
Petr Tichý
Preprint series of the Institute of Mathematics, Technische Universität Berlin
Preprint 342004
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 worstcase convergence quantity (relative $A$norm of the error for CG, relative Euclidean residual norm for MINRES) in the nexttolast 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 righthand 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 onedimensional 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 nexttolast 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