Stochastic Iterative Methods For Solving Linear And Nonlinear Algebraic Equations

Randomized Kaczmarz algorithm(RK)is a simple and fast algorithm to solve the overdetermined or underdetermined consistent linear systems.And it is a simple algorithm to solve consistent nonlinear systems.This kind of random iterative methods uses some probability criterion to determine the action row of each iteration,its advantage is that each iteration only uses the selected row to iterate,the amount of calculation is less than before,which is suitable for solving large-scale problems.Recently,two effective probability criterion have been proposed to improve the classical RK algorithm.This paper uses the relaxation idea to further improve the above two new RK algorithms.First of all,this thesis uses the relaxation idea to improve New Randomized Kaczmarz algorithm(NRK),presents the New Randomized Kaczmarz relax Algorithm(NRKr),and gives corresponding numerical experiments.The second method proposed in this thesis is the Maximal Correction Kaczmarz relax Algorithm(MCKr)for solving linear problems.Due to the different values of the relaxation parameters,the MCKrf algorithm(fixed relaxation parameter)and MCKrd algorithm(dynamic relaxation parameter)and their convergence proofs are given in this paper.Aiming at the nonlinear problem,this thesis presents the Nonlinear Maximal Correction Kaczmarz relax Algorithm(NMCKr)and gives its convergence analysis.Numerical experiments are performed to demonstrate the advantages of the improved algorithm in solving linear and nonlinear problems.Secondly,this thesis considers the above improved method combined with the threshold operator to solve the sparse problem.In this paper,the MCKrf algorithm is combined with the hard threshold operator,soft threshold operator and m threshold operator respectively,and the corresponding algorithm for solving the sparse problem is given and compared by numerical experiments.Combining the advantages of different algorithms,this thesis gives the Maximal Correction Kaczmarz relax mix Algorithm(MCKrm),and demonstrates the advantages of the algorithm by numerical experiments.