Further analysis of minimum residual iterations

DOI10.1002/(SICI)1099-1506(200003)7:2%3C67::AID-NLA186%3E3.0.CO;2-8MaRDI QIDQ2760331zbMATH OpenFDO

Authors Y. Saad

Publication date 19 December 2001

Published in Numerical Linear Algebra with Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/(SICI)1099-1506(200003)7:2%3C67::AID-NLA186%3E3.0.CO;2-8

zbMATH Keywords

algorithmscondition numberconvergenceerror boundshighly non-normal matricesKrylov subspace techniquesminimal residual methodsnumerical examples

Mathematics Subject Classification ID

Iterative numerical methods for linear systems (65F10) Numerical computation of matrix norms, conditioning, scaling (65F35)

Review text

The convergence behaviour of a number of algorithms based on minimizing residual norms over Krylov subspaces is not well understood. Residual or error bounds currently available are either to loose or depend on unknown constants which can be very large. Such estimates are unavailable in practice. NEWLINENEWLINENEWLINEThe author takes another look at traditional as well as alternative ways of obtaining upper bounds on residual norms. Numerical experiments for two bidiagonal matrices demonstrate priorities of the alternative bounds. Furthermore, the author derives upper bounds for the residual norm from Chebyshev polynomials. The main difference between the classical and new estimates is that these new ones do not involve the condition number of the matrix of eigenvectors. The theory shows that the usual tools provided by norms and spectral analysis are insufficient for analysing the behaviour of iterative processes for systems with highly non-normal matrices. The foregoing theory is applied to obtaining a posteriori estimates by using the Arnoldi matrix. Numerical examples illustrating the behaviour of the various Chebyshev bounds on two simple examples conclude the paper.

Recommendations

• Residual and backward error bounds in minimum residual Krylov subspace methods
• Expressions and bounds for the GMRES residual
• On the residual norm in FOM and GMRES
• Computable Convergence Bounds for GMRES
• Superlinear convergence in minimum residual iterations

Cited in

(13)

• Alternating oblique projections for coupled linear systems
• GMRES algorithms over 35 years
• Residual and backward error bounds in minimum residual Krylov subspace methods
• On the residual norm in FOM and GMRES
• Expansion par minimisation du résidu dynamique
• Convergence conditions for a restarted GMRES method augmented with eigenspaces
• Further analysis of the remedian algorithm
• Estimating the Attainable Accuracy of Recursively Computed Residual Methods
• scientific article; zbMATH DE number 827951 (Why is no real title available?)
• Relations between Galerkin and Norm-Minimizing Iterative Methods for Solving Linear Systems
• Analysis of two-grid methods: the nonnormal case
• A Fourier Transform Analysis of Convergence Properties of Multigrid V-Cycle Algorithm
• By how much can residual minimization accelerate the convergence of orthogonal residual methods?

Describes a project that uses

Uses Software

• eigs

This page was built for publication: Further analysis of minimum residual iterations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2760331)