Iterative Methods For Large Sparse Saddle Point Linear Systems

Saddle point linear system is a symmetric and indefinite linear system of equations. It is also known as augmented system. It arises from many scientific research and engineering computations such as numerical solutions of partial differential equations, the optimization problems and least square problems. In practical applications, this system often is large and sparse, thus it is suitable to be solved by iterative methods. However, the special structure of this system makes some well-known algorithms, for instance, successive over-relaxation (SOR) method or conjugate gradient (CG) method invalid. Therefore, it is highly desirable to develop effective iterative methods for solving large sparse saddle point linear system.Uzawa method and MINRES method are two well-known algorithms for solving the saddle point linear systems. Uzawa method has a simple format but a low rate of convergence, while MINRES method is highly effective, but has a complex format. To find an algorithm which has a simpler format and higher efficiency is an open problem.The classical SOR method is simple in theory, has a little requirement for storage, and is easier to implement, hence it is welcomed by scientific researchers and computational engineers. Unfortunately, the SOR method can not be applied for solving the saddle point linear system because of the singularity of the diagonal part of the coefficient matrix. Recently the generalization of SOR method has been studied for solving the saddle point linear system. Li, Li and Evans proposed a generalized SOR (GSOR) method in 1998 for solving the augmented system derived from the least squares problem. Then in 2000, Li and Evans gave a more general GSOR method for solving the augmented system. In 2001, Golub, Wu and Yuan proposed a SOR-like method, which is a special case of the GSOR method given by Li and Evans in 2000. Therefore, we call both the GSOR method of Li and Evans, and the SOR-like method of Golub et al generalized SOR methods. Generalized SOR method has a simple format as well; moreover, it has a preconditioning matrix.In this thesis, firstly, the convergence analysis of the SOR-like method is reconsidered. By using an elementary method, the spectral radius of the iteration matrix is fully...