对称Toeplitz系统的快速W变换基预条件子

１．引言考虑下列Ｎ阶线性方程组其中T_N=(t_i,j)　是Ｎ×Ｎ阶实对称正定（ＳＰＤ）Ｔｏｅｐｌｉｔｚ矩阵，即０，１，…，Ｎ－１）且Ｔ_Ｎ的所有特征值为正数．Ｔｏｅｐｌｉｔｚ系统已广泛应用于数字信号处理，时间序列分析（参见［１］）以及微分方程的数值解（参见［２１］等领域．八十年代以前，考虑到Ｔｏｅｐｌｉｔｚ矩阵的特殊性，人们主要用Ｌｅｖｉｎｓｏｎ递推技术及其变形或者分而治之思想直接求解方程组（１．１），计算复杂性为Ｏ（Ｎ~（２））或Ｏ（ＮｌｏｇＮ~（２））（参见［３］）；比Ｇａｕｓｓ法运算量级Ｏ（Ｎ~（３）…

FAST W TRANSFORM BASED PRECONDITIONER FOR SYMMETRIC TOEPLITZ SYSTEMS

A new matrix algebra W, including the set of real symmetric skewcirculant matrices, is introduced. It is proved that all the matrices of W can be simultaneously diagonalized by the discrete W transform matrix. As an application, the use of preconditioned iterative method (preconditioner W1_(T_n) belongs to matrix class W) to solve a system of equations with a Toeplitz coefficients matrix is developed. If generating function f(x) is nonnegative piecewise continuous and has enumerable zero points, we conclude that the spectrum of iterative matrix have a cluster at one. The results of numerical tests with this preconditioner are presented.Our preconditioner is comparable, and if f(x) is not smooth that superior, to Strang's circulant preconditioner and Huckle's skewcirculant preconditioner.