臺灣博碩士論文加值系統

迭代法是一種重複改善線性系統 Ax=b 的近似解，最後會逐漸趨近真解的方法。在本篇論文中將回顧一些迭代法包括 IGCG、CGS、BICGSTAB等方法並探討是否會發生中斷的現象。再從中挑選幾種類型的 Krylov 子空間法來求解一些利用有限差分法離散化偏微分方程式所化為的大型線性稀疏系統，並比較其迭代的時間與收斂的速度。

Each iterative method uses successive procedure to produce a more accurate solution to a linear system at each iteration. In this paper, we review some famous iterative methods such as IGCG, CGS, and BICGSTAB and discuss at what situation the breakdown will occur. We also choose two partial differential equations with boundary value conditions as our test problems and discretisize them to linear systems by the central difference. Furthermore, we choose some types of Krylov subspace methods to solve these test problems, and compare the computing time and the rate of convergence of those Krylov subspace methods.

Chapter 1 Introduction 1
1-1 The Background 1
1-2 The Purpose 3
Chapter 2 Constructing Krylov Subspace methods 4
2-1 The Basic Properties of the Krylov Subspace
and Auxiliary Matrix 4
2-2 Stopping Criteria 9
Chapter 3 Krylov Subspace Methods 15
CG METHOD 15
CGNE AND CGNR METHODS\hfill 16
GMRES METHOD 16
IGCG METHODS 19
BICG METHOD 20
CGS METHOD 21
BICGSTAB METHOD 23
Chapter 4 Numerical Experiments 27
Chapter 5 Conclusion 32
Reference 33

[1] A. D. Gunawardena, S. K. Jain, and L. Snyder, Modified iterative methods for consistent linear systems, Linear Algebra Appl.,154-156 , 1991, pp. 123-143.
[2] C. C. Paige and M. A. Saunders, Solution of sparse indefinite systems of linear equations, SIAM J. Numer. Anal., Vol. 12, 1975, pp. 617-629.
[3] D. G. Luenberger, Hyperbolic pairs in the method of conjugate gradients, SIAM J. Appl. Math., Vol. 17, pp.1263-1267.
[4] D.M. Young and K.C. Jea, Generalized conjugate gradient acceleration of iterative methods, Part I. The symmetrizable case, Rep. CAN-162, Center for Numerical Analysis, The university of Texas at Austin.
[5] D.M. Young and K.C. Jea, Generalized conjugate gradient acceleration of iterative methods, Part II. The nonsymmetrizable case, Rep. CAN-163, Center for Numerical Analysis, The university of Texas at Austin.
[6] D.M. Young and K.C. Jea, On the simplification of generalized conjugate-gradient methods for nonsymmetrizable linear systems, Linear Algebra Appl., 52, 1983, pp. 399-417.
[7] E. Bodewig, Matrix Calculus, North-Holland, Amsterdam, 1956.
[8] H. A. Van Der Vorst, BI-CGSTAB: A fast and smoothly converging variant of BI-CG for the solution of nonsymmetric linear systems, SIAM J. Stat. Compu., Vol. 13, No. 2, 1992, pp. 631-644.
[9] H. C. Elman, Iterative methods for large, sparse, nonsymmetric systems of linear equation, Research Report 229, Yalu Univ., Dept. of Computer Sciences, 1982.
[10] J. R. Bunch and L. Kaufman, Some stable methods for calculating inertia and solving symmetric linear systems, Report CU-CS-063-75, Dept. of Math., Univ. of California at San Diego, 1975.
[11] J. Stoer and R. Freund, On the solution of large indefinite systems of linear equations by conjugate gradient algorithms, Institut fur Angewandte Math. und Statistik, Unic. Wurzburg, West Germany, 1981.
[12] L. H. Chuang and K. C. Jea, On the construction of Krylov subspace methods for solving large linear systems, Fu Jen Studies, pp.11-27.
[13] M. R. Hestenes and E. L. Stiefel, Methods for large sparse nonsymmetric systems of linear equations, J. Res. Nat. Bur. Standards 49, 1952, pp. 409-436.
[14] O. Axelsson, Conjugate gradient type method for unsymmetric and inconsistent systems of linear equations, Linear Algebra Appl., 29, 1980, pp. 1-16.
[15] O. Widlund, A Lanczos method for a class of nonsymmetric systems of linear equations, SIAM J. Numer. Anal., Vol. 15, No 4, 1978, pp.801-811.
[16] P. Concus and G. H. Golub, A generalized conjugate gradient method for the numerical solution of elliptic partial differential equations, in Sparse Matrix Computation, Academic, New York, 1976, pp.309-332
[17] P. K. W. Vinsome, ORTHOMIN, and iterative method for solving sparse sets of simultaneous linear equations, in 4th Symposium of Numerical Simulation of Reservoir Performance of the Society of Petroleum Engineers of AIME, Los Angeles, Calif., 1976, Paper SPE 5739.
[18] P. Sonneveld, CGS, a fast Lanczos-type solver for nonsymmetric linear systems, SIAM J. Sci. Stat. Compu., Vol. 10, 1989, pp. 36-52.
[19] R. Fletcher, Conjugate gradient methods for indefinite systems, Vol. 506, Lecture Notes Math., 1976, pp. 73-89.
[20] V. Faber and T. Manteuffel, Necessary and sufficient conditions for the existence of a conjugate gradient method, SIAM J. Numer. Anal., 21, Vol. 21, 1984, pp. 127-128.
[21] V. M. Fridman, The method of minimum iterations with minimum errors for a system of linear algebraic equations with a symmetrical matrix, USSR Computational Math. And Math. Phys. 2, 1963, pp. 362-363.
[22] Y. Saad, Krylov subspace methods for solving large unsymmetric linear systems, Mathematics Of Computation, Vol. 37, No. 155, 1981, pp. 105-126.
[23] Y. Saad and M. H. Schultz, Conjugate gradient-like algorithms for solving nonsymmetric linear systems, Mathematics Of Computation, Vol. 44, No. 170, 1985, pp. 417-424.
[24] Y. Saad and M. H. Schultz, A generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM J. Sci. Stat. Comput., v. 7, No. 3, 1986, pp. 856-870.