Convergence Analysis of Krylov Subspace Iterations with Methods from Potential Theory
Convergence Analysis of Krylov Subspace Iterations with Methods from Potential Theory
复制标题
DOI：
10.1137/s0036144504445376
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
A. Kuijlaars
中科院分区：
文献类型：
--
作者：
A. Kuijlaars
Krylov子空间迭代是解线性方程组和计算大型矩阵特征值的最著名和最广泛使用的数值方法之一。这些方法是多项式方法，其收敛行为与多项式在矩阵谱上的行为有关。这导致了多项式逼近理论中的一个极值问题：给定次数的一次多项式在谱上能有多小？本文介绍了最近发展起来的一种在对称矩阵情况下分析这个极值问题的方法。它是基于关于谱的全局信息的，在某种意义上，本征值被假定为按照一定的度量分布。然后，根据迭代次数，计算特征值的Lanczos方法找到位于某一区域内的特征值，这是通过位势理论中的约束平衡问题来描述的。同样的约束平衡问题也描述了求解线性系统的共轭梯度和其他迭代方法的超线性收敛。
Krylov subspace iterations are among the best-known and most widely used numerical methods for solving linear systems of equations and for computing eigenvalues of large matrices. These methods are polynomial methods whose convergence behavior is related to the behavior of polynomials on the spectrum of the matrix. This leads to an extremal problem in polynomial approximation theory: How small can a monic polynomial of a given degree be on the spectrum? This survey gives an introduction to a recently developed technique to analyze this extremal problem in the case of symmetric matrices. It is based on global information on the spectrum in the sense that the eigenvalues are assumed to be distributed according to a certain measure. Then, depending on the number of iterations, the Lanczos method for the calculation of eigenvalues finds those eigenvalues that lie in a certain region, which is characterized by means of a constrained equilibrium problem from potential theory. The same constrained equilibrium problem also describes the superlinear convergence of conjugate gradients and other iterative methods for solving linear systems.