The Study Of The Iterative Methods For Real Symmetric Positive Definite Toeplitz Systems

It is shown by Huckle that every real symmetric Toeplitz matrix admits a trigonometric transformation splitting(TTS),i.e.,T = 1/2(Cn+?Cn+R2)+ 1/2(SnI?SnI + R2),where Cn,SnI are discrete trigonometric transformation matrices and R2 is a rank-2 matrix.Based on such a TTS,this paper mainly uses the shifted TTS classical iterative method and the TTS alternating direction iterative method for solving real symmetric positive definite Toeplitz systems.We use the fast algorithm of discrete trigonometric transformation matrices with the real vector,at each iteration,the storage and calculation of the shifted TTS classical iterative method and the TTS alternating direction iterative method are half of the shifted CSCS classical iterative method and the CSCS alternating direction iterative method,respectively.For the shifted TTS classical iterative method,we prove that there is always a shift parameter ? such that the proposed iterative method converges.The numerical experiments show that this method performs better than the shifted CSCS classical iterative method and much better than the Gauss-Seidel(GS)classical iterative method.Furthermore,we also study the solution of real symmetric positive definite Toeplitz matrices by the preconditioned conjugate gradient method(PCG).Based on the shifted TTS classical iterative method,a new shifted Sine preconditioner is proposed,the spectral properties of the preconditioned matrix are given,and the arithmetic complexity is discussed.The numerical experiments show that our preconditioner significantly accelerates the convergences of the CG methods,and are more effective than T.Chan,circulant preconditioner.For the TTS alternating direction iterative method,theoretical analysis indicate that if the generating function f(x)of the n×n Toeplitz matrix T is a real positive even function,then this method will converge unconditionally to the unique solution of the linear systems for sufficient large n.Moreover,we derive an upper bound of spectral radius of iterative matrix for the TTS alternating direction iterative method which is dependent solely on the spectra of the two TTS matrices involved.The numerical experiments show that our method works better than CSCS alternating direction iterative method and much better than the symmetric Gauss-Seidel(SGS)alternating direction iterative method.Then,we extend our method to solve the mn × mn double symmetric BTTB linear equations,deriven the trigonometric transformation splitting form and given the alternating direction iteration scheme of the double symmetric BTTB matrix.The theoretical analysis shows that the method will unconditionally convergent to the exact solution of the linear equations when the splitting matrices are positive definite,the computational complexity of each iteration is O(mnlogmn)real operations.This thesis consists of four chapters:In Chapter 1,we give a brief introduction for research backgrounds,status and contents of Toeplitz linear system of equations as well as the innovation of this thesis.In Chapter 2,we review some basic definitions and theorems frequently used in the sequel.In Chapter 3,we develop the shifted classical TTS iterative method for real symmetric positive definite Toeplitz systems.In Chapter 4,we propose alternating direction iterative method for real symmetric positive definite Toeplitz systems.