The Multistage Iterative Methods For Solving Toeplitz Systems

How to effectively solve Toeplitz systems has been one of the most populartopics in matrix computation. Toeplitz matrices have been extensively applied invarious fields of science, such as auto-control theory, digital signal processing, imagerestoration, etcs. In recent years, the researchers in all over the world have beenworking with stable algorithms with less float operations and errors for solvingToeplitz systems. With the rapid development of information technology, parallelcomputation has becoming a main approach to large scale linear systems. Accordingto the special structure and properties of Toeplitz matrices, the multistage iterativealgorithms for solving Toeplitz systems are developed in this paper, which isespecially suitable for parallel computing. The paper consists of three main contents:the multistage iterative method for solving Toeplitz systems, the construction ofmultistage splittings of Toeplitz matrices and the analysis of convergence of themultistage iterative method.This thesis consists of six chapters which are organized as follows:The first chapter is an introduction, in which the research backgrounds, themotivation of the theme’s choice, the main contents and the innovations of the paperare described.The second chapter is the preliminaries, where some notation, definitions, andsome known results frequently used in the thesis are briefly introduced.In the third chapter we discuss the multistage method for solving Toeplitz systems.We first describe the multistage iterative methods. Then, exploiting the Toeplitzstructure, we construct the splittings for the multistage method.In the forth chapter we discuss the convergence of the resulting method and weshow that the corresponding splittings at each level is P-regular, and the resultingmethod is convergent when the number of iteration at each level is even. Next we alsodiscuss the convergence of the multistage method when the coefficient matrix of theToeplitz systems is H-Matrix.In the fifth chapter we give some rough estimation on the numbers of the inneriterations and the nested two-stage iteration respectively. Some numerical examplesillustrate the effectiveness of our methods when the coefficient matrix of the Toeplitzsystems is symmetric positive definite matrix or H-Matrix respectively.In the last chapter we make some extensions for the multistage iterative methodsfor solving systems whose coefficient matrices are block Toeplitz matrices withToeplitz blocks.