迭代精化下求解三对角Toeplitz线性方程组的快速算法
A Fast Algorithm for Solving Tridiagonal Toeplitz Linear Systems with Iterative Refinement
DOI: 10.12677/PM.2020.105052, PDF,    科研立项经费支持
作者: 李 姗, 刘仲云：长沙理工大学数学与统计学院，湖南 长沙；张育林：Minho大学数学中心，布拉加，葡萄牙
关键词: Toeplitz矩阵；迭代精化；快速算法；Toeplitz Matrices； Iterative Refinement； Fast Algorithm
摘要: 本文主要讨论如何对三对角Toeplitz线性方程组 进行高精度数值求解。由于系数矩阵A这种比较特殊的结构，使得我们可以设计出快速求解 的直接算法。我们将该算法应用到实际例子的计算过程中，发现大部分例子计算效果显著，但部分例子的计算精度还不能达到计算机机器精度。针对这类达不到计算机机器精度的例子，本文将在快速求解三对角Toeplitz线性方程组 的直接算法基础上，进一步进行迭代精化，从而提高这类例子的计算精度。数值实验表明通过迭代精化，我们算法计算精度可以达到计算机机器精度。
Abstract: This paper mainly discusses how to numerically solve tridiagonal Toeplitz linear systems   efficiently. Since the coefficient matrix A has a special structure, we can design a direct algorithm to quickly solve  . We will apply the above algorithm to the calculation of practical examples and find that the calculation precision of some examples is not as high as that of computer's ma-chine accuracy. In order to improve the precision of algorithm, this paper further carries out iter-ative refinement to quickly solve the tridiagonal Toeplitz linear equations of  . Numerical experiments show that the computational accuracy of our algorithm can reach computer's machine accuracy by iterative refinement.
文章引用：李姗, 刘仲云, 张育林. 迭代精化下求解三对角Toeplitz线性方程组的快速算法[J]. 理论数学, 2020, 10(5): 425-432. https://doi.org/10.12677/PM.2020.105052

参考文献

[1] Saad, Y. (2000) Iterative Methods for Sparse Linear Systems. 2nd Edition, SIAM, Philadelphia, PA.
[2] Yan, W.-M. and Chung, K.-L. (1994) A Fast Algorithm for Solving Special Tridiagonal Systems. Computing, 52, 203-211. [Google Scholar] [CrossRef] 
[3] Garey, L.E. and Shaw, R.E. (2001) A Parallel Method for Linear Equa-tions with Tridiagonal Toeplitz Coefficient Matrices. Computer & Mathematics with Applications, 42, 1-11. [Google Scholar] [CrossRef] 
[4] Kim, H.J. (1990) A Parallel Algorithm Solving a Tridiagonal Toeplitz Linear System. Parallel Computing, 13, 289-294. [Google Scholar] [CrossRef] 
[5] Benner, P., Li, R.C. and Truhar, N. (2009) On the ADI Method for Sylvester Equations. Journal of Computational and Applied Mathematics, 233, 1035-1045. [Google Scholar] [CrossRef] 
[6] Kurschner, P., Benner, P. and Saak, J. (2014) Self-Generating and Efficient Shift Parameters in ADI Methods for Large Lyapunov and Sylvester Equations. Electronic Transactions on Numerical Analysis, 43, 142-162.
[7] Levenberg, N. and Reichel, L. (1993) A Generalized ADI Iterative Method. Numerische Mathematik, 66, 215-233. [Google Scholar] [CrossRef] 
[8] Lu, A. and Wachspress, E.L. (1991) Solution of Lyapunov Equations by Alternating Direction Implicit Iteration. Computers and Mathematics with Applications, 21, 43-58. [Google Scholar] [CrossRef] 
[9] Horn, R.A. and Johnson, C.R. (1985) Matrix Analysis. Cambridge University Press, Cambridge.
[10] Bai, Z.-Z., Golub, G.H. and Ng, M.K. (2003) Hermitian and Skew-Hermitian Splitting Methods for Non-Hermitian Positive Definite Linear Systems. SIAM Journal on Matrix Analysis and Applications, 24, 603-626. [Google Scholar] [CrossRef] 
[11] Garey, L.E., Majedi, M. and Shaw, R.E. (2008) A Parallel Sewing Method for Solving Tridiagonal Toeplitz Strictly Diagonally Dominant Systems. I.P.D.P.S., 1-8. [Google Scholar] [CrossRef] 
[12] Demmel, J.W. 应用数值线性代数[M]. 王国荣, 译. 北京: 人民邮电出版社, 2007.

为你推荐