A Hybrid Preconditioner For Symmetric Positive Definite Toeplitz-like Systems

Toeplitz and Toeplitz-related systems arise in a variety of applications in mathematics and engineering, especially in signal and image processing. The direct methods and iterative methods are two main tools for solving Toeplitz systems. For the low-order systems, generally, direct method is the best choice. But for the high-order systems, iterative methods become more effective methods.We consider the solutions of symmetric positive definite Toeplitz-plus-diagonal systems (Tn+Dn)χ=b, where Tn is a Toeplitz matrix and Dn is positive diagonal. However, unlike the case of Toeplitz systems, no fast direct solvers have been developed for solving such kinks of systems. In this paper, we consider the preconditioning conjugate gradient method with hybrid preconditioners for solving such classes of systems. The proposed preconditioners can be easily constructed and implemented efficiently using fast Fourier transforms.We will first give a brief introduction for research background and current situation of such systems, and give some of the basic knowledge and iterative methods. Then we show that the iterative convergence of the proposed method.We give numerical examples to illustrate the feasibility of the proposed methodThe outline of the best of the paper is as follows:In Chapter1, we will first give a brief introduction for research backgrounds and current situation of such systems.In Chapter2, we introduces some definitions, theorems, lemmas and basic properties, these will be used in sequel.In Chapter3, Six basic iterative methods, conjugate gradient method and preconditioned conjugate gradient method are all introduced.In Chapter4, we analyze the spectra of the preconditioned matrices, which has a clustered spectra and show that our proposed preconditioners are effective.In Chapter5, we consider the central diagonals of Dn, these diagonals are distributed uniformly and normal distribution in the interval (0,1), respectively. The number of iterations, the time of iterations and the spectral radius of the preconditioned matrices for different methods are given to illustrate the effectiveness of the proposed preconditioner.At last, we analyze the data from numerical examples and give concluding remarks.