Some Stochastic Iterative Methods For Solving Linear Problems And Their Generalization

Randomized Kaczmarz algorithm(RK)have demonstrated its effectiveness for solving overdetermined and underdetermined consistent linear systems.And its randomized thought has been widely promoted and applied to other algorithms.But the selection rule which selects with probability proportional to||ai||22(i=1,2,...,m)in RK is not necessarily optimal in general.When ||ai||2 are equal,RK’s advantage is not clear.First of all,this paper presents a new randomized Kaczmarz algorithm(NRK),The row of the matrix A is randomly selected with probability proportional to the distance between the current estimation and the hyperplane.we prove that NRK linearly converges to the solution of the system and it is at least as well as RK proposed by Strohmer and Vershynin.Numerical experiments demonstrate this and even show that it largely outperforms RK.Secondly,this paper also presents maxmial correction Kaczmarz algorithm(MCK),unlike Kaczmarz algorithm,MCK makes the current iteration point project to the farthest hyperplane,thus accelerates the convergence speed.And respectively we prove its convergence and finite termination in theory and validate it experimentally.At the same time,the nonlinear maxmail correction Kaczmarz algorithm(NMCK)are presented to solve the nonlinear systems by the maximum correction thought.In order to reduce the computation of jacobian matrix,the nonlinear maxmail residual correction Kaczmarz algorithm(NMRCK)is presented,which is the improvement of NMCK and is a matrix-free algorithm.The numerical experiments show the effectiveness of above nonlinear algorithm for the preconditioned problems.