Distributed Algorithms For Solving A Linear Equation Based On Consensus Theory

In recent decades,due to the rapid development of computer technologies and the commercial applications of distributed multi-agent systems,the big data,drones,power systems and other industries have rapidly developed.Among the theoretic reserach avenues of the numerical computations involving real numbers,solving linear equation problem is of fundamental importance.Using distributed algorithms to solve linear equation has too many advantages in a distributed networks compared to centralized or parallel networks.Various factors make the study of solving linear equation by distributed algorithms become necessary.In this thesis,the problem of solving linear equation is regarded as a distributed parameter estimation problem,and the most effective algorithm for solving distributed parameter estimation problem is the “consensus+innovation” algorithm.At present,the researches on the “consensus+innovation” algorithm are mostly under undirected graphs.However,in practical applications,these conditions are harsher,so the study of the “consensus+innovation” algorithm under the directed graph is very necessary.In this thesis,the main results are as follows:For regarding solving the linear equation as a distributed parameter estimation problem,this thesis deeply studies the feasibility of solving the linear equations by the “consensus+innovation” algorithm.For the harsher communication requirements,in this thesis,we firstly explore “consensus+innovation” algorithm under a strongly connected graph.We prove that it can converge to the solution of the linear equation by selecting Lyapunov function.After that we explore it under not strongly connected but contains a directed spanning tree.For the slower interation speed,we carry out the “consensus+innovation”algorithm with different weight to achieve the purpose of speeding up the interations.For the two weight,we firstly exporle the selection method under undierected.Then it is extended to the directed graph,and we carry out the range of one of the parameters.The convergence speed of the iterative algorithm is related to the calculation of each iteration,then the time complexity of each iteration is discussed.The correctness of the algorithm is verified by simulation,and “consensus+innovation” algorithm compare to Jacobi interation.According to the concept of “innovation” and “residual” involving on System Identification,this thesis also propose the “consensus+residual” algorithm under a strongly connected graph.We prove that it can converge to the solution of the linear equation by selecting Lyapunov function.After that we explore it under not strongly connected but contains a directed spanning tree.The convergence speed of the iterative algorithm is related to the calculation of each iteration,then the time complexity of each iteration is discussed.The correctness of the algorithm is verified by simulation.