Please use this identifier to cite or link to this item:
For citation please use:
Main Title: Behavior of CG and MINRES for symmetric tridiagonal Toeplitz matrices
Author(s): Liesen, Jörg
Tichý, Petr
Type: Research Paper
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).
Subject(s): Krylov subspace methods
convergence analysis
Toeplitz matrices
Poisson equation
Issue Date: 1-Dec-2004
Date Available: 17-Dec-2021
Language Code: en
DDC Class: 510 Mathematik
MSC 2000: 15A09 Matrix inversion, generalized inverses
65F10 Iterative methods for linear systems
65F20 Overdetermined systems, pseudoinverses
Series: Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin
Series Number: 2004, 34
ISSN: 2197-8085
TU Affiliation(s): Fak. 2 Mathematik und Naturwissenschaften » Inst. Mathematik
Appears in Collections:Technische Universität Berlin » Publications

Files in This Item:
Format: Adobe PDF | Size: 1.36 MB
DownloadShow Preview

Item Export Bar

Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.