Some Studies On Iterative Methods And Preconditioning Techniques Of Saddle Point Problems

Saddle point problems arise widely in a variety of scientific and engineering applications,such as mixed finite element approximation of partial differential equations,the image reconstruction and registration,constrained optimization and so forth.Saddle point problems are a class of large sparse linear systems,and the solution of saddle point problems is one of the key issues of scientific and engineering computation.Therefore,studying the efficient methods for solving the numerical solutions of the saddle point problems is of great both theoretical and practical significance.Due to the indefiniteness and ill-conditioning of the coefficient matrices of the saddle point problems,the methods to solve them are mainly iterative methods and preconditioning techniques based on the splitting and special structures of the coefficient matrices currently.This doctoral dissertation deeply focuses on investigating the iterative methods and preconditioning techniques for saddle point problems,and develops several new iteration methods and preconditioners for saddle point problems.Our main works are as follows:1.The successive over-relaxation(SOR)-like iteration methods for solving the symmetric saddle point problems are investigated.By utilizing parameter accelerating technique and constructing a new splitting of the coefficient matrix,we propose the generalized accelerated SOR(GASOR)and the modified ASOR(MASOR)iteration methods,which reduce the correlation between the parameters in two iterative steps of the ASOR one and improve its convergence rate.The convergence and semi-convergence properties of the two new iteration methods are analyzed theoretically.Numerical experiments indicate that the new methods have faster convergence rates compared with some similar ones.2.The Hermitian and skew-Hermitian(HSS)-type iteration methods for solving the Hermitian saddle point problems are studied.By constructing the coefficient matrix of the first equation of the the parameterized preconditioned HSS(PPHSS)iteration scheme as a block lower triangular matrix,we develop the improved PPHSS(IPPHSS)iteration method,which overcomes the shortcoming that the first iteration step of the PPHSS method does not use the latest update solve vector,and improves its convergence rate.In addition,we construct the modified PHSS(MPHSS)iteration method by combining the IPPHSS iteration method with the accelerated HSS(AHSS)iteration method and processing its parameters appropriately,which overcomes the shortage that the optimal parameters of the IPPHSS iteration method are not obtained and further improves its computing efficiency,and the optimal and the practical formula of the parameters contained in the MPHSS iteration method are also proposed.Numerical results show that the proposed iteration methods are more effective than the similar ones.3.The Uzawa-type iteration methods for solving the non-Hermitian saddle point problems are studied.By combining the single-step HSS(SHSS)with the Uzawa iteration methods,and adopting matrix preconditioning strategy and using parameter accelerating technique in the second iteration step of the Uzawa iteration method,the generalized Uzawa-SHSS(GU-SHSS)iteration method is derived.This overcomes the shortcoming of the Uzawa-HSS iteration method where a shift skew-Hermitian linear system needs to be solved at each iteration step,which brings large computation costs.Besides,the convergence and semi-convergence intervals of the parameters for the GU-SHSS iteration method are studied.Numerical experiments are given to show that the GU-SHSS iteration method is superior to some Uzawa-type ones for solving the saddle point problems with non-Hermitian positive definite and Hermitian dominant(1,1)parts.4.The HSS-based preconditioners for the nonsymmetric saddle point problems are studied.We construct a two-parameter deteriorated positive definite and skew-Hermitian splitting(TDPSS)method,and then propose the generalized variant of the DPSS(GVDPSS)preconditioner by relaxing the TDPSS preconditioner.The difficulty that the parameter for the VDPSS preconditioner needs to be chosen to balance the proportion of the two sub-blocks of the different matrix between it and the original matrix can be avoided.The convergence conditions of the GVDPSS iteration method,the distribution of eigenvalues and the forms of the eigenvectors,and the upper bounds on the degree of the minimum polynomial of the GVDPSS preconditioned matrix are analyzed in details.Additionally,we also establish the implementation aspects and the method of choosing the parameters of the GVDPSS preconditioner.Numerical experiments are reported to show that the new preconditioner has better numerical performance compared with some similar ones.5.The shift-splitting-type preconditioners for the nonsymmetric saddle point problems are studied.We propose the parameterized generalized shift-splitting(PGSS)preconditioner on the basis of the GSS and modified SS(MSSP)ones,which contains some existing shift-splitting-type ones and improves the computational efficiencies of the the GSS and MSSP ones.For the nonsymmetric saddle point problems,we first analyze the eigenvalue distributions of the shift-splitting-type preconditioned matrices.And the choice for parameters of the PGSS iteration method and the PGSS preconditioner is also discussed.Numerical experiments are carried out to validate that the proposed iteration method and preconditioner are more stable and effective than some existing ones.