Some Effective Algorithms For Saddle Point Problems And Their Applications In Image Restoration

Saddle point problem arises in many scientific computing and engineering applications,such as computational fluid dynamics,finite element and finite difference discretization of elliptic PDEs,weighted and equality constrained least squares estimation,image restoration and so on.The solution of the saddle point system not only plays a vital role in solving the whole problem,but also has very important theoretical significance and practical application value.How to design a kind of efficient,robust and practical numerical solution based on the specific physical background and saddle point structure matrix is not only the core of modern science and engineering calculation,but also the research hotspot of current numerical calculation workers and engineering and technical personnel.In this dissertation,we study the numerical solution of a kind of saddle point problem in discrete partial differential equation,and apply the obtained solution to the solution of a class of structured linear system in image restoration problem.The first chapter gives the background significance of the study of the saddle point linear system,the research status,and summarizes the main research content,characteristics and innovation.The second chapter is based on the idea of relaxation preconditioning and the relaxation of positive definite Hermitian splitting method,a class of generalized relaxed positive definite Hermitian splitting(GRPSS)methods for large sparse non Hermitian saddle point problem are proposed.The eigenvalue distribution and convergence of the GRPSS preconditioned matrices are studied theoretically,and it is found that the GRPSS preconditioner is closer to the initial coefficient matrix than the RPSS preconditioner in some norm sense.Finally,the validity of this method is verified by numerical experiments,and the theoretical results are in good agreement with the experimental results.In the third chapter,we propose a class of modified relaxed splitting solution methods for generalized saddle point problem which arises from incompressible NavierStokes equations.The upper bound of the minimum polynomial dimension of the preconditioned matrix and the eigenvalue distribution of the preconditioned matrix are studied in detail.Compared with the GRS method,the preconditioned MRS method is closer to the original matrix under the premise that the computational complexity remains unchanged.Experiments show the feasibility and effectiveness of MRS method.However,it is necessary to solve the inverse of the two sub-matrices in solving the preconditioned subsystem corresponding to the MDS and MRS methods.In this chapter,we propose a new class of upper and lower triangular split(BULT)iterative methods.The theoretical analysis shows that the difficulty of matrix inversion of the above subsystems can be avoided when combined with Krylov subspace method.Thus,the efficiency of Krylov subspace method is greatly improved.In the fourth chapter,we propose a kind of modified SIMPLE(MS)preconditioned method for saddle point problem arising from steady-state incompressible Navier-Stokes equations.By analyzing the spectral properties of MS preconditioned matrix,under the appropriate conditions,all eigenvalues of the preconditioned matrices will be closely clustered near(1,0).Thus,overcoming the shortcomings of the relaxed HSS method where the remaining eigenvalues are widely distributed.Finally,it is proved from theory and experiment that MS pretreatment is more effective than some other good preconditioners.In the fifth chapter,we study the numerical solutions of two special saddle point systems,namely the complex linear system and the singular saddle point linear system system.A generalized PMHSS(GPMHSS)method is proposed for the complex linear system.The theoretical analysis shows that the spectral radius of the GPMHSS method is smaller than that of the PMHSS method and the ADPMHSS method under appropriate parameters.In addition,a class of augmented block triangular splitting(ABTS)preconditioned method is proposed for singular saddle point systems.This method corresponds to a proper splitting of the saddle point linear system and theoretical analysis shows that the ABTS preconditioned iterative method converges to the generalized inverse solution of the singular saddle point problem.At the same time,it is found that,when combined with the augmented block triangulation method and the GMRES method,the ABTS method can converge to the generalized inverse solution of the singular saddle point system.Finally,the optimal parameters of the ABTS method and the expression of the optimal convergence factor are given.In the sixth chapter,we study the upper and lower triangular(ULT)splitting iterative method for the linear system of saddle point structure in image restoration and give the optimal parameters and the optimal convergence factor under certain conditions.The experimental results show that the ULT method is more competitive and effective than the existing SHSS and RGHSS methods,and can be effectively applied to image restoration.In the seventh chapter,the generalized skew-Hermitian triangular splitting(GSTS)iterative method is firstly generalized and a modified generalized skew-Hermitian triangular splitting(MGSTS)iterative method is obtained.The convergence and quasioptimal parameters when using MGSTS to solve the image restoration problem are given theoretically.Finally,the validity and accuracy of this method in solving the image restoration problem are verified by numerical comparison.The eighth chapter summarizes the full text and sets out the direction and outlook for future work.