解循环三对角线性方程组的追赶法

An Algorithm for Solving Circulant Tridiagonal Systems

循环三对角、循环 Toeplitz三对角线性方程组的求解在科学与工程计算中有着广泛的应用 .运用矩阵分解给出此类方程组的直接解法 ;通过分析其特性 ,给出了达到机器精度的截断算法 ,其计算复杂度几乎等同于求解一个三对角线性方程组的计算复杂度 .数值实验的结果与理论分析的结果十分吻合 .该算法还推广到求解拟三对角线性方程组 .

An algorithm for solving circulant tridiagonal systems is proposed. The algorithm is based on the direct factorization of coefficient matrix. When the system is diagonally dominant, the truncated version of this algorithm provides an approximate solution which equals to the exact solution within machine accuracy and the number of its arithmetic operations is O(8n) -- nearly the same as the number of arithmetic operations for solving a tridiagonal system. The analytic results match closely with the results measured from the numerical experiments.