Improved Distributed Algorithm For Solving Linear Equations

Solving a system of linear equations is a fundamental problem in numerical calculations and,therefore,has significant value in both theoretical research and engineering applications.Traditionally,such problems are often solved by centralized algorithms,such as Jacobi iteration,Gauss-Seidel iteration,and the Kaczmarz method.However,centralized algorithms have disadvantages such as excessive central computing power demand,low communication efficiency,and poor system stability,making it difficult to solve super-large-scale linear equations.As artificially constructed control systems tend to become larger and more complex,distributed algorithms based on multi-agent systems have received more and more attention as a viable alternative.Noted that the existing distributed algorithms have problems such as slow convergence speed,narrow application range,and limited initial value.To solve the above problems,two improved distributed algorithms are designed,and the research is carried out by a combination of theoretical analysis and numerical simulation.Aiming at the problem of the slow convergence speed of distributed algorithms,an idea to speed up the convergence rate is proposed.After conducting an in-depth investigation on the distributed algorithm for solving linear equations in the literature,a suitable object to be improved is chosen based on comparison and analysis.By introducing a relaxation factor and past state information to the consensus part,a novel algorithm based on special initialization is designed.First consider the stringent conditions,i.e.,undirected topology and linear equations with unique solutions;the effectiveness of the improved algorithm is preliminarily tested through numerical simulation,that is,it has exponential convergence characteristics and has a faster convergence compared with the original algorithm.The eigenvalue criterion is utilized to theoretically prove the convergence of the improved algorithm.By analyzing the spectral radius of the iterative matrix,the analytical expression of the optimal parameter is derived to achieve the fastest convergence rate.In view of the narrow application range of distributed algorithms,the convergence of the improved algorithm under directed topology and indefinite equations is further studied.When the communication topology of the multi-agent system is a directed graph,the corresponding convergence analysis turns into the problem of solving the characteristic roots of a quadratic equation with complex constant coefficients.When the object to be solved is an indeterminate equation,the decomposition in a direct sum is used to project the error system into two orthogonal subspaces.By investigating the convergence of the two subsystems separately,it shows that the improved algorithm can converge to one of the solutions.Through a special initialization step,the improved algorithm can converge to a special solution that is closest to the target vector.The corresponding conclusion is proved by mathematical induction and verified by a numerical example.Aiming at the problem of limited initial values of distributed algorithms,an iterative algorithm that allows arbitrary initial values is designed.For the case of well-posed equations,and under-determined equations,the convergence of the improved algorithm is proved by investigating the internal connection of the two improved algorithm error systems and using the eigenvalue criterion.By analyzing the spectral radius of the iterative matrix,the analytical expression of the optimal parameter is derived,which can achieve the fastest convergence rate.On this basis,the robustness of the two improved algorithms is compared from the algorithm expression viewpoint,and the design ideas and application scenarios of the distributed algorithm and the centralized algorithm are also compared,separately.Finally,based on the lemmas of matrix eigenvalue inequality,some parameter selection methods that do not depend on the specific object equation are proposed.