Several Iterative Methods For Solving Saddle Point Problems And Its Convergence Analysis

The large-scale sparse saddle point problems are often required to solve in the fields of operations research,cybernetics,scientific computing and en-gineering technology and so on.Because of the large scale and ill-condition,the solution of this kind of problem must be time consuming,high storage space and high computational complexity.The key to solving such problems is to establish the algorithms with short time,small computation and numerical stability.Due to the advantages of preserving the spa.rsity,saving the memory cost and easy imple-mentation,the iterative method for solving the saddle point problem has attracted more and more wide attention.It is well known that the convergence and convergence speed are the theoretical basis and prerequisite for the application of the algorithm.Therefore,to accelerate convergence rate and improve convergence five kinds of iterative methods for solv-ing saddle point problems are proposed based on their inherent,structures,Uzawa method,MHSS method,AOR method and generalized skew-Hermitian triangular splitting(GSTS)method,upper and lower triangular(ULT)splitting method and preconditioned technique.Meanwhile,the spectral properties of the preconditioned matrix are analyzed,and the convergence results of the proposed methods are ob-tained.The main work is as follows.1.Based on classical Uzawa method and AOR method,a Uzawa-AOR method for solving singular saddle point problems is proposed.The semi-convergence theo-rems of the proposed method is strictly proved and the eigenvalue distribution of the preconditioned matrix of the Uzawa-AOR method is analyzed.The feasibility and effectiveness of the Uzawa-AOR method are illustrated by numerical experiments.2 A generalized relaxation preconditioned modified accelerated HSS(PMAHSS)method for solving a class of saddle point problems is presented on the basis of the preconditioned HSS(PHSS)method of matrix splitting.The modified and acceler-ated technique is first used to improve the PHSS method,and a new preconditioner is then constructed by using preconditioned method.Moreover,the convergence of the proposed method is analyzed by the matrix theory.The numerical experiments show that the generalized relaxation PMAHSS method is feasible and effective.3.A Uzawa-MHSS method is designed to solve complex singular saddle point problems based on the classical Uzawa method and MHSS methods.The con-vergence condition of the proposed method is discussed,and its semi-convergence theorem is obtained.The spectral distribution of the preconditioned matrix of the Uzawa-MHSS methods is thoroughly studied.The numerical experiments show that the Uzawa-MHSS method is fast and effective.4.A GSTS-Uzawa method for solving a class of complex singular saddle point problems is proposed according to the classical Uzawa method and GSTS method,and its semi-convergence theorem is obtained and proved strictly.The spectral of the preconditioned matrix is analyzed and the better convergence is obtained by using the preconditioner to each step of GMRES method.The feasibility and effectiveness of the GSTS-Uzawa method are illustrated by numerical experiments.5.A modified ULT(MULT)splitting method is presented to solve the gen-eralized saddle point problem according to the ULT splitting iterative method and the modified and accelerated techniques,and is also extended to the general case such that it can solve more practical problems than the ULT splitting method.The convergence theorem of the proposed method is obtained and proved strictly,and the expressions of the optimal parameters and convergence factor of the proposed method are provided under mild conditions.The feasibility and effectiveness of the proposed method are illustrated by numerical experiments.