Accelerated Greedy Kaczmarz Iteration Algorithms For Systems Of Linear And Nonlinear Equations

Many practical problems in scientific and engineering computing,such as structural analysis,network analysis,data analysis,data fitting,and numerical solutions of differential equations,can ultimately be reduced to systems of linear or nonlinear equations.The solutions to these problems can ultimately be reduced to systems of linear or nonlinear equations.Therefore,studying efficient algorithms for solving these problems is of great practical importance.Based on some previous work,we propose a series of new methods for solving such problems efficiently and give their convergence theorems.First,according to the criterion of selecting target rows of the greedy randomized Kaczmarz(GRK)method,we propose the multi-step greedy randomized Kaczmarz(MGRK)method and the accelerated greedy Kaczmarz(AGK)method for solving consistent overdetermined or underdetermined systems of linear equations and prove that they converge to the unique least-norm solutions of systems of linear equations.Numerical experiments show that the MGRK method outperforms the GRK method,and the MGRK method outperforms the maximum weighted residual Kaczmarz(MWRK)method for large dense underdetermined system of linear equations.Numerical experiments also show that the AGK method outperforms the GRK,MWRK and fast deterministic block Kaczmarz(FDBK)method.Second,based on the criterion of selecting the objective columns of the greedy randomized coordinate descent(GRCD)method,we propose the multi-step greedy randomized coordinate descent(MGRCD)method and the accelerated greedy coordinate descent(AGCD)method for solving the overdetermined linear least square problem.We prove that these two methods converge to unique least square solutions for overdetermined systems of linear equations with column full rank coefficient matrix.Numerical experiments show that both the MGRCD and AGCD methods outperform the maximum distance coordinate descent(AMDCD)and GRCD methods,and the AGCD method also outperforms the CGLS and LSQR algorithms for the large sparse ill-conditioned systems of linear equations.Third,motivated by the idea of the GRK method,we propose the nonlinear greedy randomized Kaczmarz(NGRK)method and the nonlinear relaxed greedy randomized Kaczmarz(NRGRK)method for solving systems of nonlinear equations and analyze the convergence of the NGRK method.To improve the computational efficiency of the NGRK and NRGRK methods,we design the multi-step nonlinear greedy randomized Kaczmarz(MNGRK)method and the accelerated nonlinear greedy Kaczmarz(ANGK)method,and also analyze their convergence.In addition,inspired by the idea of the maximum distance coordinate descent(MDCD)method,we propose the nonlinear maximum distance Kaczmarz(NMDK)method and prove its convergence.To further improve the convergence speed of the NMDK method,we give an accelerated version of the NMDK method,namely the accelerated nonlinear maximum distance Kaczmarz(ANMDK)method.Numerical experiments show that the ANGK and ANMDK methods are more efficient than the nonlinear Kaczmarz method,the nonlinear randomized Kaczmarz method and the Gauss-Newton method.Finally,we establish the Newton-AGK method and the Newton-AGCD method to solve systems of nonlinear equations by using the AGK method and the AGCD method as an inner iteration of the inexact Newton(IN)method,respectively.Numerical experiments demonstrate their local quadratic convergence.In contrast to the classical IN method,our proposed two inexact Newton methods can also solve overdetermined systems of nonlinear equations.