TY - JOUR

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

AU - Bellalij, M.

AU - Saad, Y.

AU - Sadok, H.

PY - 2009

Y1 - 2009

N2 - 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 KmHKm where Km 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.

AB - 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 KmHKm where Km 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.

KW - Convex optimization

KW - Interpolation

KW - KKT optimality conditions

KW - Krylov subspaces

KW - Min-max problem

KW - Polynomials of best approximation

UR - http://www.scopus.com/inward/record.url?scp=74549226033&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=74549226033&partnerID=8YFLogxK

M3 - Article

AN - SCOPUS:74549226033

VL - 33

SP - 17

EP - 30

JO - Electronic Transactions on Numerical Analysis

JF - Electronic Transactions on Numerical Analysis

SN - 1068-9613

ER -