The Iterative Methods For Toeplitz-plus-Hankel Systems

The systems of linear equations with Toeplitz, Hankel, and Toeplitz-plus-Hankel coefficient matrices arise in many signal processing applications. Now Toeplitz-plus-Hankel system can be solved by direct methods and iteratived methods. For example, the inverse scattering problem can be formulated as Toeplitz, Hankel,and Toeplitz+Hankel systems of equations. By exploiting the special structures of Toeplitz or Hankel matrices, an n×n system of equations can be solved by fast direct methods based on Levinson or Shur algorithm with O(n2)operations. Direct algorithm for inverting n×n Toeplitz-plus-Hankel matrices with O(n2) complexity have also been derived. Although the computational complexity of these fast algorithms is lower than that of the Gaussian elimination with pivoiting with O(n3),their stability is not guaranteed when applied to indefinite or nonsymmetric matrices. So large linear systems are generally solved with iterative methods. In this paper we study precondictioned iterative methods for solving Toeplitz-plus-Hankel systems. A kind of new precondictioner suitable for Toeplitz-plus-Hankel matrices is proposed, and the spectral properties of precondictioned Toeplitz-plus-Hankel matrices are examined. It is showed that the eigenvalues of the precondictioned matrices are clustered around unity. The proposed preconditioner can be easily constructed and the preconditioning system can be solved by using fast Fourier transformations. An n×n Toeplitz-plus-Hankel system can be solved by precondictioned Krylov subspace methods with O(nlog n). The numerical experiments are given to demonstrate that the proposed precondictioners are more effective than in reference[2].The structure of this thesis is divided into five chapters as follows:In Chapter 1, we will first give a brief introduction for research backgrounds, current situation, research contents of such systems, and the innovation of the paper.In Chapter 2, we introduct some definitions, theorems, lemmas and basic properties, which will be used in sequel.In Chapter 3, Three basic iterative methods-conjugate gradient method(CG), conjugate gradient square(CGS), generalized minimal residual(GMRES)-and respective preconditioned iterative methods are all introduced. Then analyse the properties of these iterative methods,In Chapter 4, we discuss the construction of different preconditioners for different Toeplitz matrices and analyse the spectral properties of precondictioned matrices.In Chapter 5, we consider diffrent Toeplitz matrices, respectively, and analyze the data from numerical examples and give concluding remarks.