On the worst-case convergence of MR and CG for symmetric positive definite tridiagonal Toeplitz matrices. (English) Zbl 1119.65320

Liesen, Jörg; Tichý, Petr

ETNA, Electron. Trans. Numer. Anal. 20, 180-197 (2005).

Summary: We study the convergence of the minimal residual (MR) and the conjugate gradient (CG) when applied to linear algebraic systems with symmetric positive definite tridiagonal Toepliiz matrices. Such systems arise, for example, from the discretization of one-dimensional reaction-dififusion equations with Dirichlet boundary conditions. Based on our previous results [J. Liesen and P. Tichý, BIT 44, 79–98 (2004; Zbl 1053.65021)], we concentrate on the next-to-last iteration step, and determine the initial residuals and initial errors for the MR and CG method, respectively, that lead to the slowest possible convergence. By this we mean that the methods have made the least possible progress in the next-to-last iteration step.
Using these worst-case initial vectors, we discuss which source term and boundary condition in the underlying reaction-diffusion equation are the worst in the sense that they lead to the worst-case initial vectors for the MR and CG methods. Moreover, we determine (or very tightly estimate) the worst-case convergence quantities in the next-to-last step, and compare these to the convergence quantities obtained from average (or unbiased) initial vectors. The spectral structure of the considered matrices allows us to apply our worst-case results for the next-to-last step to derive worst-case bounds alse for other iteration steps.
We present a comparison of the worst-case convergence quantities with the classical convergence bound based on the condition number of \(A\), and finally we discuss the MR and CG convergence for the special case of the one-dimensional Poisson equation with Dirichlet boundary conditions.

MSC:

65F10	Iterative numerical methods for linear systems
65F35	Numerical computation of matrix norms, conditioning, scaling
65N06	Finite difference methods for boundary value problems involving PDEs
35J05	Laplace operator, Helmholtz equation (reduced wave equation), Poisson equation
35J25	Boundary value problems for second-order elliptic equations

Keywords:

Krylov subspace methods; conjugate gradient method; minimal residual method; convergence; tridiagonal Toeplitz matrices; Poisson equation; reaction-dififusion equations

Citations:

Zbl 1053.65021

Software:

CSDP; SDPT3