Numerical Solution of Eigenvalue Problems

本研究致力于提高两个特定特征值问题的求解方法的精度。第一个是经典的对称特征值问题。最近的结果表明，存在一大类对称特征值问题，对于这些对称特征值问题，小的结构扰动会导致相对意义上的特征值的小变化。这类矩阵被称为“行为良好的”。我们将研究寻找一个矩阵“良好行为”的充要条件的问题。另一个令人担忧的问题是，只有几种算法被证明能够在“行为良好”的矩阵集合的子集上实现相对精度。调查将试图发现这套算法是否可以扩大。我们考虑了库本、多加拉、杰瑟普、索伦森和唐的分而治之的方法。这些算法已经建立了良好的绝对误差界，对角占优问题和奇异值分解的相对误差界还有待于证明。另一个大的问题领域涉及非对称矩阵的特征向量问题。这个问题出现在马尔可夫建模问题的数值解中。关于高斯消元的准确的一般界已被证明。这些都允许将标准稀疏矩阵技术直接应用于该问题。然而，对于几乎无耦合的情况，需要证明更好的结构摄动界。

This research concerns the improvement of the accuracy of methods to solve two particular eignenvalue problems. The first is the classical symmetric eigenvalue problem. Recent results have shown that there is a large class of symmetric eigenvalue problems for which small structured perturbations result in small changes in the eigenvalues in the relative sense. This class of matrices is called "well- behaved". The problem of finding a neccessary and sufficent condition for a matrix to be "well-behaved" will be investigated. Another concern is that only a few algorithms have been shown to achieve relative accuracy on a subset of the set of "well- behaved" matrices. The investigation will try to discover if that set of algorithms can be expanded. The divide and conquer approaches of Cuppen, Dongarra, Jessup, Sorensen, and Tang are considered. Good absolute error bounds on these algorithms have already been established and it remains to show tighter relative error bounds for diagonal dominant problems and for the singular value decomposition. The other large problem area concerns the eigenvector problem for non-symmetric matrices. The problem arises in the numerical solution of Markov modeling problems. Accurate general bounds on Gaussian elimination have been proven. These allow for the straighforward application of standard sparse matrix techniques to this problem. However, better structured perturbation bounds need to be proved for the nearly uncoupled case.