The Research On Improvement And Its Application Of Kaczmarz Algorithm For Solving Large-Scale Nonlinear Equations

The Kaczmarz algorithm only needs to use one row of the equations when solving large-scale linear equations,which greatly reduces the amount of calculation.And its randomized version is more widely used and improved.Firstly,on the basis of Kaczmarz algorithm,this thesis proposes the Kaczmarz method with oblique projection(KO)algorithm and the randomized Kacmarz method with oblique projection(RKO)algorithm.These two algorithms can solve large-scale linear coherent problems with high convergence rate.The convergence properties of the KO algorithm and the RKO algorithm are verified by theoretical analysis and numerical experiments.Secondly,according to the iterative process of Kaczmarz algorithm to solve large-scale linear problems,this thesis proposes a kind of randomized Kaczmarz algorithms for solving large-scale well-posed or over-determined nonlinear systems of equations.This kind of algorithms are matrixfree algorithms,because they do not need to calculate the Jacobi matrix at the iterative point in each iteration process,but only needs to calculate one of the whole.Especially when the scale of nonlinear equations is relatively large,the advantages of these algorithms become more and more obvious.Each algorithm is named according to the way it selects the rows of the Jacobi matrix.Theoretical analysis shows that these algorithms can linearly converge to the exact solution of the problem in expectation when the classical local tangential cone condition is satisfied.In addition,these algorithms proposed in this paper are similar to the Stochastic Gradient Descent(SGD)algorithm in the iterative formula.The two types of algorithms are also compared in theoretical analysis and numerical experiment.Finally,this thesis proposes a nonlinear coordinate descent algorithm based on column operation.The nonlinear coordinate descent(NCD)algorithm selects one of the columns for iteration in the order of Jacobi matrix columns during each iteration.The nonlinear randomized coordinate descent(NRCD)and nonlinear uniform randomized coordinate descent(NURCD)algorithms select one of the columns for iteration each time according to different random probabilities.This paper shows the convergence properties of this type of algorithms through theoretical analysis and example experiments.