不精確迭代法求解特徵值問題

Inexact Iterative Methods For Solving Eigenvalue Problems

劉青松(Liu, Ching Sung)

指導教授 ： 林文偉 ； 何南國

國立清華大學/理學院/數學系/博士(2012年)

https://doi.org/10.6843/NTHU.2012.00327

摘要

第一章針對求解大型稀疏矩陣的特徵值問題所使用的不精確Arnoldi法跟Residual Arnoldi法，提出擾動及誤差分析，並說明它們的不同處。在數值實驗上，發現即便擾動很大時，估計的特徵值與真正的特徵值的誤差卻很小，這是跟傳統的擾動分析最大的不同。

第二章當矩陣為Hermitian或者skew-Hermitian時，提出一個保結構的不精確Arnoldi法來求解大型稀疏的特徵值問題；並結合上個章節所提出的擾動分析，提出一個保結構的向後誤差分析。數值結果發現，保結構的不精確Arnoldi法較不保結構的Arnoldi法更為精確。

第三章提出一個不精確的迭代法求解M矩陣的最小特徵值及相對應的特徵向量，然後證明不精確迭代法為全局線性或超線性收斂。在數值實驗上發現不精確迭代法較原本的迭代法提升了大約3倍的效率。

關鍵字

阿洛迪 ； 不精確迭代法 ； 保結構 ； 克雷洛夫子空間 ； 擾動 ； 非負矩陣

並列摘要

Recent studies on the numerical methods for solving large eigenvalue problems have shown the Arnoldi-like methods can tolerate various types of errors during computation. One of them is the inexact Arnoldi method and the other one is
the residual Arnoldi method. Both methods allow large errors with opposite allowable error patterns. Classical perturbation theorems that use first order approximation are not suitable in the analysis of those methods. In Chapter 1, we develop a perturbation
theorem for eigensystems, which makes no assumption on the error size, and use it to analyze the perturbations of both methods.

In Chapter 2, we study the Inexact Structure-Preserving Arnoldi Methods (ISPAM) for solving Hermitian and skew-Hermitian eigenvalue problems, by which the solutions can preserve the desirable numerical properties as those by the exact methods. The difference between ISPAM and IAM is in the approximation extraction stage, where ISPAM uses the structured Rayleigh quotients that preserve the structures of the original matrices. We provide the formulation for their backward errors, which are also Hermitian and skew-Hermitian, and analyze their allowable inexactness based on the residual gap hypothesis. The solutions obtained by ISPAM can be as accurate as those computed by IAM, under the same allowable error condition.

In Chapter 3, we present an inexact inverse iteration method to find the minimal eigenvalue and the associated eigenvector of an irreducible $M$-matrix. We propose two different relaxation strategies for solving the
linear system of inner iterations. For the convergence of these two iterations, we show they are globally linear and superlinear, respectively.

並列關鍵字

Arnoldi ； Inexact iterations ； Structure preserving ； Krylov subspace ； Perturbation ； Nonnegative matrix

參考文獻

[1] C. J. Alpert and S.-Z. Yao. Spectral partitioning: The more eigenvectors, the better. Design Automation Conference, pages 195 – 200, 1995.

[2] W. E. Arnoldi. The principle of minimized iteration in the solution of the matrix eigenvalue problem. Quart. Appl. Math., 9:17–29, 1951.

[3] A. Berman and R. J. Plemmons. Nonnegative matrices in the mathematical sciences. SIAM, Philadelphia, PA, 1994.

[5] A. Bouras and V. Frayss´e. Inexact matrix vector products in Krylov methods for solving linear systems: a relaxation strategy. 26(3):660–678, 2005.

[6] R. R. Coifman, S. Lafon, A. B. Lee, M. Maggioni, B. Nadler, F. Warner, and S. W. Zucker. Geometric diffusions as a tool for harmonic analysis and structure definition of data: Diffusion maps. PNAS, (21):7426–7431, 2005.