Geodesic
On the worst-case convergence of MR and CG for symmetric positive definite tridiagonal Toeplitz matrices
Electronic transactions on numerical analysis, Tome 20 (2005), pp. 180-197.

Voir la notice de l'article provenant de la source Electronic Library of Mathematics

Summary: We study the convergence of the minimal residual (MR) and the conjugate gradient (CG) method when applied to linear algebraic systems with symmetric positive definite tridiagonal Toeplitz matrices. Such systems arise, for example, from the discretization of one-dimensional reaction-diffusion equations with Dirichlet boundary conditions. Based on our previous results in [J. Liesen and P. Tich$\acute y, BIT$, 44 (2004), pp. 79-98], 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 also 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 , and finally we discuss the MR and CG convergence for the special case of the one-dimensional Poisson $\textcent $equation with Dirichlet boundary conditions.
Classification : 15A09, 65F10, 65F20
Keywords: Krylov subspace methods, conjugate gradient method, minimal residual method, convergence analysis, tridiagonal Toeplitz matrices, Poisson equation 
@article{ETNA_2005__20__a4,
     author = {Liesen, J\"org and Tich\'y, Petr},
     title = {On the worst-case convergence of {MR} and {CG} for symmetric positive definite tridiagonal {Toeplitz} matrices},
     journal = {Electronic transactions on numerical analysis},
     pages = {180--197},
     publisher = {mathdoc},
     volume = {20},
     year = {2005},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/ETNA_2005__20__a4/}
}
TY  - JOUR
AU  - Liesen, Jörg
AU  - Tichý, Petr
TI  - On the worst-case convergence of MR and CG for symmetric positive definite tridiagonal Toeplitz matrices
JO  - Electronic transactions on numerical analysis
PY  - 2005
SP  - 180
EP  - 197
VL  - 20
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/ETNA_2005__20__a4/
LA  - en
ID  - ETNA_2005__20__a4
ER  - 
%0 Journal Article
%A Liesen, Jörg
%A Tichý, Petr
%T On the worst-case convergence of MR and CG for symmetric positive definite tridiagonal Toeplitz matrices
%J Electronic transactions on numerical analysis
%D 2005
%P 180-197
%V 20
%I mathdoc
%U http://geodesic.mathdoc.fr/item/ETNA_2005__20__a4/
%G en
%F ETNA_2005__20__a4
Liesen, Jörg; Tichý, Petr. On the worst-case convergence of MR and CG for symmetric positive definite tridiagonal Toeplitz matrices. Electronic transactions on numerical analysis, Tome 20 (2005), pp. 180-197. http://geodesic.mathdoc.fr/item/ETNA_2005__20__a4/