Analysis of some Krylov subspace methods for normal matrices via approximation theory and convex optimization

M. Bellalij, Y. Saad, H. Sadok

Research output: Contribution to journalArticlepeer-review

3 Scopus citations

Abstract

Krylov subspace methods are strongly related to polynomial spaces and their convergence analysis can often be naturally derived from approximation theory. Analyses of this type lead to discrete min-max approximation problems over the spectrum of the matrix, from which upper bounds on the relative Euclidean residual norm are derived. A second approach to analyzing the convergence rate of the GMRES method or the Arnoldi iteration, uses as a primary indicator the (1, 1) entry of the inverse of K m HK m where K m is the Krylov matrix, i.e., the matrix whose column vectors are the first m vectors of the Krylov sequence. This viewpoint allows us to provide, among other things, a convergence analysis for normal matrices using constrained convex optimization. The goal of this paper is to explore the relationships between these two approaches. Specifically, we show that for normal matrices, the Karush-Kuhn-Tucker (KKT) optimality conditions derived from the convex maximization problem are identical to the properties that characterize the polynomial of best approximation on a finite set of points. Therefore, these two approaches are mathematically equivalent. In developing tools to prove our main result, we will give an improved upper bound on the distances of a given eigenvector from Krylov spaces.

Original languageEnglish (US)
Pages (from-to)17-30
Number of pages14
JournalElectronic Transactions on Numerical Analysis
Volume33
StatePublished - 2008

Keywords

  • Convex optimization
  • Interpolation
  • KKT optimality conditions
  • Krylov subspaces
  • Min-max problem
  • Polynomials of best approximation

Fingerprint

Dive into the research topics of 'Analysis of some Krylov subspace methods for normal matrices via approximation theory and convex optimization'. Together they form a unique fingerprint.

Cite this