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

A Chasing Method for Solving Cyclic Tridiagonal Equations

利用LU分解的思想,首先将循环三对角方程组的系数矩阵A分解成3个矩阵的乘积LUD,其中L是下三角矩阵,U是单位上三角矩阵,D是拟对角矩阵(每行只有两个非零元素,前n-1行非零元位于主对角线和最后一列上,第n行非零位于第1列和最后一列上);然后,运用追赶法的思想依次用前代法("追")解出Lu=d的解,回代法("赶")解出Uv=u的解;再利用Dx=v的第一行和最后一行求出未知量xn,进而回代求解出所有未知量。该方法虽然将系数矩阵分解成3个矩阵的乘积,但计算过程并不复杂,总的算数运算量只有O(14n),小于传统算法的计算量(O(17n))。文章对数值计算的稳定性进行了分析,当矩阵A对角占优且2ai≤bi时,算法是数值稳定的。数值试验结果与理论分析相吻合。

Based on the idea of LU decomposition, the chasing method can be ascribed as the following three steps. Firstly, the coefficient matrix of cyclic tridiagonal equations was decomposed to the multiplication of three matrixes LUD. The matrixes L and U are lower and upper triangular matrix, respectively. While the matrix D is a quasi-diagonal matrix and there are two nonzero entries in the each row of matrix D. Secondly, forward substitution method is used to solve the equation Lu=d, and the backward substitution method is used to solve the equation Uv=u, and then the first and the last row of matrix D are used to solve the unknown variable xn. Now, all the other unknown variables can be solved through backward substitution. The process of matrix decomposition looks like complex, however, the algorithm implement shows that the computational process and programing do not complex. Most important thing is that the total arithmetic operations is 0（14n） and smaller than that of the classical algorithms（O（17n））. The statility analysis indicates that the chasing method developed in the paper is stable if the matrix A is diagonally dominant and the condition of 2｜ai｜≤ ｜bi｜ are satisfied. The numerical experiments indicate that the numerical results consistent with analytic results.