Network Flows That Solve Linear Equations

Guodong Shi

doi:10.1109/TAC.2016.2612819

2017-06-01

105

Guodong Shi *

Brian D. O. Anderson

Uwe Helmke

DOI：10.1109/TAC.2016.2612819

原文链接

查看原文

摘要

En 中文

We study distributed network flows as solvers in continuous time for the linear algebraic equationz = Hy. Each node i has access to a row hT i of the matrix H and the corresponding entry zi in the vector z. The first consensus + projection flow under investigation consists of two terms, one from standard consensus dynamics and the other contributing to projection onto each affine subspace specified by the hi and zi. The second projection consensus flow on the other hand simply replaces the relative state feedback in consensus dynamics with projected relative state feedback. Without dwell-time assumption on switching graphs, we prove that all node states converge to a common solution of the linear algebraic equation, if there is any. The convergence is global for the consensus + projection flow while local for the projection consensus flow in the sense that the initial values must lie on the affine subspaces. If the linear equation has no exact solutions, we show that the node states can converge to a ball around the least-squares solution whose radius can be made arbitrarily small through selecting a sufficiently large gain for the consensus + projection flow for a fixed bidirectional graph. Semi-global convergence to approximate least-squares solutions is also demonstrated for switching balanced directed graphs under suitable conditions. It is also shown that the projection consensus flow drives the average of the node states to the least-squares solution with a complete graph. Numerical examples are provided as illustrations of the established results.

Keyword:

Networks

distributed computation

linear algebraic equations