Multi-Step And Modified Fast Algorithms For Solving Large-Scale Systems Of Nonlinear And Linear Equations

Complex mathematical problems encountered in practical engineering applications often boil down to solving large systems of nonlinear and linear equations,so it is of great theoretical and practical importance to solve these systems of equations quickly.In this paper,we examine the advantages and shortcomings of the existing methods,makes efficient use of the data generated by each iteration,prioritizes the rows with large residuals and proposes several methods for selecting the set of row indicators of the system of equations,and obtains several improved Kaczmarz methods and improved coordinate descent methods for solving nonlinear and linear systems of equations,respectively.First,based on the existing nonlinear randomized Kaczmarz(NRK)method and the nonlinear uniformly randomized Kaczmarz(NURK)method,the multi-step nonlinear randomized Kaczmarz(MNRK)method and the multi-step nonlinear uniformly randomized Kaczmarz(MNURK)method are proposed by using the idea of selecting multiple nonlinear systems of equations per iteration for the nonlinear problems.And their convergences are proved.Both new methods retain the advantages of the original method(wide range of adaptation,no need to calculate the full Jacobi matrix),and extend selecting one nonlinear row indicator per iteration to multiple row indicators,thus improving the efficiency of data utilization per iteration.On the other hand,the modified multi-step nonlinear Kaczmarz(MMNK)method and the multi-step nonlinear residual average Kaczmarz(MNRAK)method are also obtained by using the idea of preferring larger residual components for iteration,respectively.Numerical experiments show that the four newly proposed methods have better numerical performances than the comparing methods when dealing with overdetermined and square nonlinear systems of equations with the singular Jacobi matrices.Second,the modified randomized Kaczmarz(MRK)method for solving consistent linear systems of equations is proposed by simplifying the search of the set of row indicators for general linear systems of equations.Then,the idea of selecting multiple row indicators for nonlinear problems is applied to linear problems,thus the multi-step modified randomized Kaczmarz(MMRK)method and multi-step uniformly randomized Kaczmarz(MURK)method are proposed respectively,and their convergences are proved.Furthermore,the multi-step residual average Kaczmarz(MRAK)method for systerms of linear equations is obtained by taking the set of row indicators in the MNRAK method.The numerical results show that the three newly proposed methods outperform the compared methods in dealing with randomly generated matrices and large sparse matrices.Finally,the residual average coordinate descent(RACD)method is obtained for the overdetermined linear problem by simplifying the index by finding the mean of the residuals,and then the accelerated residual average coordinate descent(ARACD)method is proposed in order to reduce the number of residual calculations and improve the operational efficiency.The numerical experiments show that the ARACD method converges faster than the compared methods,and the optimal parameters do not need to be calibrated for each experiment,thus eliminating the need for additional time.