解大型線性系統之Krylov子空間法的性能比較

COMPARISONS OF PERFORMANCE USING THE KRYLOV SUBSPACE METHODS FOR SOLVING LARGE LINEAR SYSTEMS

鄧偉宏(Wei-Hong Deng)

指導教授 ： 莊陸翰

大同大學/電機資訊學院/應用數學學系所/碩士(2006年)

摘要

迭代法是一種藉由反覆地修正近似解，而使近似解逐漸收斂至正確解的數值法。近年來因為計算機科學的不斷發展，迭代法不管是在理論或實作上都有不小的進展。本論文將探討求解大型稀疏線性系統 Ax = b 的一群迭代法，其被稱為Krylov子空間法。論文中將依序介紹Krylov子空間的基本性質及介紹六種近代比較著名的Krylov子空間法：GMRES(m)，CGS，BICGSTAB，QMR，TFQMR，QMRCGSTAB，並在4.2節中選用數個二維及三維的偏微分方程式作為這些數值法的測試問題，各數值法的收斂情形以圖表展示，以供比較它們之間的性能差異及優劣。此外，亦在4.3節中將討論可附加於上述數值法而使收斂曲線平滑化的兩個算子：QMR算子及TFQMR算子，我們進一步對兩個算子的差異及效果進行比較，並將比較的結果展示給有興趣使用這些迭代法及算子的讀者做參考。

關鍵字

大型線性系統

並列摘要

The iterative methods are a group of numerical methods that improve approximative solutions of a linear system, repetitively, such that converge to the exact solution. Recently, because of the great development of computing science, it has a great development in the practice and theorem of iterative methods. This thesis discusses a kind of iterative methods that solve large sparse linear systems, called Krylov subspace methods. In this thesis, we will discuss some properties of Krylov subspace and introduce six recently typical Krylov subspace iterative methods: GMRES(m), CGS, BICGSTAB, QMR, TFQMR, QMRCGSTAB. Besides, in Section 4.2, we will choose two 2-dimensional and two 3-dimensional PDE’s as test problems, and show the difference of convergent situation of these numerical methods by some figures and tables. Furthermore, in Section 4.3, we will discuss two operators that can be used to smooth the convergent curves of above methods, they are called QMR and TFQMR operators. We also compare the performance of these operators, the numerical results can be consulted by reader that is interested in using these methods and operators.

並列關鍵字

LARGE LINEAR SYSTEM

參考文獻

[1] O. Axelsson. Conjugate gradient type-methods for unsymmetric and inconsistent systems of linear equations. Linear Algebra and its Applications, 29:1-16, 1980.

[2] M. R. Hestences and E. Stiefel, Method of conjugate gradients for solving linear systems, J. Res. Nat. Bur. Standards, No. 49, 409-436, 1952.

[3] Y. Saad and M. H. Schultz. GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems. SIAM J. Sci. Statist. Comput. 7:856-869, 1986.

[5] P. Sonneveld. CGS: a fast Lanczos-type solver for nonsymmetric linear systems. SIAM J. Sci. Statist. Comput. 10:36-52, 1989.

[6] Y. Saad A flexible inner-outer preconditioned GMRES Algorithm. SIAM J. Sci. Statist. Comput. 14,:461-469, 1993.