第二章

拉普拉斯矩阵

$L=M J M^{-1}$

Jordan form matrix and transformation matrix

$$
J=\left[\begin{array}{llll}
\lambda_ {1} & & & \
& \lambda_ {2} & & \
& & \ddots & \
& & & \lambda_ {N}
\end{array}\right], M=\left[\begin{array}{llll}
v_ {1} & v_ {2} & \cdots & v_ {N}
\end{array}\right]
$$

特征值 $\lambda_{i}$ 和右特征向量$v_ {i}$ 满足

$$
\left(\lambda_ {i} I-L\right) v_ {i}=0
$$

Theorem 2.1 L has rank N-1, i.e., $λ_1 = 0$ is nonrepeated, if and only if graph G has a spanning tree

如果一个图G的拉普拉斯矩阵的秩是N-1，则$λ_1 = 0$ 不重复的条件是 图G含有spanning tree，spanning tree是指该图有不只一个子树包含图中所有的顶点

image-20210909200254551

且有以下推论：

  1. 因为 $L$ 所有的行自相加等于0，所以有

$$

$$

L \underline{1} c=0

$$

$$

其中$\underline{1} = [1…1]^T$, $c$是任意一个常数，这代表了每个$L$矩阵必然含有特征值$\lambda_1 = 0$对应有特征向量$\underline{1}c$,所以$\underline{1}c \in Nullspace(L)$，即拉普拉斯矩阵的零空间里必含$\underline{1}c$。

如果$Nullspace(L)$的维度是1，即拉普拉斯矩阵的秩为 $N-1$，则$\lambda_1= 0$是该拉普来说矩阵$L$无重复的特征值，且所对应的$\underline{1}c$是其零空间内唯一的特征向量。

  1. ⭐️拉普拉斯矩阵必然含有$\lambda_1 = 0$

  2. ⭐️如果图是强连接图，则图必有spanning tree且其拉普拉斯矩阵的秩为 $N-1$

  3. ⭐️如果图有spanning tree，则$|\lambda_2|>0$

  4. ⭐️如果图有spanning tree，则该图的拉不拉斯矩阵$L$有一个无重复的特征值:$\lambda_1 = 0$，而且其他的特征值都有实数部分大于0

  5. ⭐️所有的无向图都有对称的拉普拉斯矩阵$L$，所以它们的图拉普拉斯矩阵的特征值都是实数

  6. 拉普拉斯正则矩阵：用于两图比较特征值

    $\bar{L}=D^{-1} L=D^{-1}(D-A)=I-D^{-1} A$

Geršgorin Circle Criterion

Geršgorin Circle Criterion All eigenvalues of a matrix $E=\left[e_ {i j}\right] \in R^{N \times N}$ are located within the union of $\mathrm{N}$ disks

$$
\bigcup_ {i=1}^{N} {z \in C:\left|z-e_ {i i}\right| \leq \sum_ {j \neq i}\left|e_ {i j}\right|}
$$

矩阵E的所有特征值都在以对角线上元素为圆心，以每一行除掉对角线元素的加和绝对值为半径的圆的与集上面，对于拉普拉斯矩阵来说，每一个对角线元素都是该行其他节点的加和值乘以-1，则除去对角线元素，拥有最大加和绝对值得行是最大入度节点所在行，因为$L = D-A$，每一行的disk都以该行对角线元素的度值$d_i$为半径，$\lambda_i$为圆心的圆

image-20210909195419736

The $i$-th disk in the Geršgorin circle criterion is drawn with a center at the diagonal element $e_ {i i}$ and with a radius equal to the $i$-th absolute row sum with the diagonal element deleted, $\sum_ {j \neq i}\left|e_ {i j}\right|$. Therefore, the Geršgorin disks for the graph Laplacian matrix $L=D-A$ are centered at the in-degrees $d_ {i}$ and have radius equal to $d_ {i}$.

临界稳定性

齐次连续线性时不变系统为临界稳定的充份必要条件是：系统传递函数中每个极点的实部都为非正值，且其中有一个或多个极点实部为零，且均为相异的单根，而其他的极点实部为负值。若所有的极点实部都是负值，系统渐近稳定，若有极点实部为正，则系统不稳定。

若系统是以状态空间来表示，可以推导其若尔当标准型，再分析是否临界稳定：系统临界稳定当且仅当其对于实部为0的若尔当区块为标量。

费德勒特征值 The Fiedler Eigenvalue $\lambda_2$

费德勒特征值是是拉普拉斯矩阵的第二特征值$\lambda_2$ ，代表了图的几何连接性，对于确定在图上的动态系统的相互作用速度的有重要意义。

对于无向连接图：

$$
\lambda_ {2} \leq \frac{N}{N-1} d_ {\mathrm{min}}
$$

$d_ {min}$ :最小节点入度

$N$：节点数

$$
\lambda_ {2} \geq \frac{1}{\operatorname{Diam} G \times \operatorname{Vol} G}
$$

$DiamG$: 图中任意两点最远距离

$VolG$: 图中节点入度加和，即 $\operatorname{Vol} G=\sum_{i} d_ {i}$

一个图的费德勒特征值大，则在图上的动态系统达到稳态的时间就越短，即图中连接越多，任意两顶点间最远距离越短，则越容易达到稳态

单积分器共识动力学

在图上个节点，考虑节点$i$的控制有单一积分器的控制器设计：

$$
\dot{x}_ {i}=u_ {i}
$$

其中$a_ {ij}$是该点对邻居节点的边权重

$$
u_ {i}=\sum_ {j \in N_ {i}} a_ {i j}\left(x_ {j}-x_ {i}\right)
$$

$$
\dot{x}_ {i}=\sum_ {j \in N_ {i}} a_ {i j}\left(x_ {j}-x_ {i}\right)
$$

$$
\dot{x}_ {i}=-x_ {i} \sum_ {j \in N_ {i}} a_ {i j}+\sum_ {j \in N_ {i}} a_ {i j} x_ {j}=-d_ {i} x_ {i}+\left[\begin{array}{lll}
a_ {i 1} & \cdots & a_ {i N}
\end{array}\right ] \left[\begin{array}{c}
x_{1} \
\vdots \
x_{N}
\end{array}
\right]
$$

对于所有节点则有

$$
\begin{gathered}
\dot{x}=-D x+A x=-(D-A) x \
\dot{x}=-L x
\end{gathered}
$$

于是发现单一积分器的一致性就与图拉普拉斯矩阵有密切关系

$$
u=-L x
$$

$-L$作为系统矩阵而言，其所有特征值都在复空间左平面，原因是拉普拉斯矩阵$L$的特征值全部在右平面上，所以$-L$在左边，因此系统最终都是收敛稳定的，但有可能是不同的稳定方式。

于是，在系统平衡态的时候有：

$$
\dot x = f(x) = 0 \to 0 = -Lx_ {ss}
$$

因此全局的steady-state都存在于$L$的零空间里，也就是说，只要找到$L$的零空间的特征向量，就找到了该系统的稳态解。

如果$L$的秩是 $N-1$,则矢量$\underline{1}c$是其唯一的零空间解，所以有$x_ {ss} = \underline{1}c$ :

$$
x=\left[\begin{array}{c}
x_ {1} \
\vdots \
x_ {N}
\end{array}\right]=c \underline{1}=\left[\begin{array}{c}
c \
\vdots \
c
\end{array}\right]
$$

其中$c$是常数，且对于初阶系统而言，这个稳态的共识值为：

$$
c=\sum_ {i=1}^{N} p_ {i} x_ {i}(0)
$$

定理2.2 初阶系统共识收敛

本地投票协议$u_ {i}=\sum_ {j \in N_ {i}} a_ {i j}\left(x_ {j}-x_ {i}\right)$使系统$\dot{x}_ {i}=u_ {i}$保证收敛的充分必要条件是该系统所在的图有旋转树(spanning tree)，共识值是公式（15）

Consensus for First-order Systems The local voting protocolguarantees consensus of the single-integrator dynamics if and only if the graph has a spanning tree. Then, all node states come to the same steady-state values $x_ {i}=x_ {j}=c, \forall i, j .$ The consensus value is given by (15)

证明：

对于$\dot{x}=-L x$，其解为：

$$
x(t)=e^{-L t} x(0)=M e^{-J t} M^{-1} x(0)=\sum_ {i=1}^{N} v_ {i} e^{-\lambda_ {i} t} w_ {i}^{T} x(0)=\sum_ {i=1}^{N}\left(w_ {i}^{T} x(0)\right) e^{-\lambda_ {i} t} v_ {i}
$$

如果图有旋转树，则除了$\lambda_1 = 0$以外，拉普拉斯矩阵$L$ 其他的特征值都在右复平面，所以对于系统$-L$来说，所有的特征值都在零点和左平面，即系统是marginally stable的，于是当$t\rightarrow \infty$时有：

$$
x(t) \rightarrow v_ {2} e^{-\lambda_ {2} t} w_ {2}^{T} x(0)+v_ {1} e^{-\lambda_ {1} t} w_ {1}^{T} x(0)
$$

取$v_1 = \underline1$，$w_1 = [p_1\dots p_N]^T$,正则化使得$v_iw_i=1$，则有$\sum{p_i}=1$，然后有解：

$$
x(t) \rightarrow v_ {2} e^{-\lambda_ {2} t} w_ {2}^{T} x(0)+\underline{1} \sum_ {i=1}^{N} p_ {i} x_ {i}(0)
$$

其中第二项就是系统趋于稳定时得共识值，而第一项则代表了收敛速度，在$\tau = \frac{1}{\lambda_2}$时，第一项就变为定值，往后时刻只会比该值小，所以当$t\rightarrow\infty$时，$x(t)$逼近稳态值$\underline{1} \sum_{i=1}^{N} p_ {i} x_ {i}(0) =\underline{1}c $

对于在图上使用低阶控制器运动的动态系统而言：

  1. 节点状态收敛到一致的速度快慢大致取决于Fiedler特征值$\lambda_2$的大小

所有节点同步到初始态的平均值时第一特征向量即为稳态值

当所有节点都同步到初始状态节点的平均值时，也就是稳态时：$c=\frac{1}{N} \sum_{i} x_ {i}(0)$

因为在稳态时，$ \underline{1}w^T_1x(0)=\underline{1}\sum_{i=1}^{N} p_ {i} x_ {i}(0) = \underline{1}c=c\underline{1}$

即可以得到：$w^T_1x(0)=\sum_{i=1}^{N} p_ {i} x_{i}(0) = c = \frac{1}{N} \sum_ {i} x_ {i}(0)$

即$w^T_1 = c\underline1^T$

因为在无向图中，$\underline{1}^{T} L=0$

所以有：

$$
w_ {1}^{T} L=c \underline{1}^{T} L=0
$$

综上可以得出结论，稳态值为初始状态平均值的初阶系统，其拉普拉斯矩阵的第一特质值$\lambda_1=0$所对应的特征向量$w_1$，就是其稳态值$c\underline1$。

consensus leader

  1. consensus leader定义为图中spinning tree的根节点
  2. 所有节点都会向着leader节点状态进行同步
  3. 拉普拉斯矩阵第一特征值对应的特征向量，其大于零的部分对应的节点就是leader节点
  4. 一个图中可以有多个leader，但是最后同步状态不知道超哪个leader去，或者是朝着leader的平均值去？

Discrete–time dynamics

对于离散时间的单个节点而言，其运动有如下动力学

$$
x_ {i}(k+1)=x_ {i}(k)+u_ {i}(k)
$$

分布式本地控制器 $u_{i}(k)=\varepsilon \sum_ {j \in N_{i}} a_ {i j}\left(x_{j}(k)-x_ {i}(k)\right)$

closed-loop system

$$
\begin{aligned}
x_ {i}(k+1) &=x_ {i}(k)+\varepsilon \sum_ {j \in N_ {i}} a_ {i j}\left(x_ {j}(k)-x_ {i}(k)\right) \
&=\left(1-\varepsilon d_ {i}\right) x_ {i}(k)+\varepsilon \sum_ {j \in N_ {i}} a_ {i j} x_ {j}(k)
\end{aligned}
$$

global input

$$
u(k)=-\varepsilon L x(k)
$$

global dynamics

$$
x(k+1)=(I-\varepsilon L) x(k) \equiv P x(k)
$$

Perron matrix

$$
P=I-\varepsilon L
$$

$P$有所有特征值都在单位圈内的充要条件是：

$$
\varepsilon<1 / d_ {\text {Max }}
$$

image-20210914153739027

因为拉普拉斯矩阵的row sum是0，所以Perron matrix 的row sum是1，所以$\underline1$是perron matrix 的右特征向量，对应于特征值$\lambda_1$.

$$
P\underline1 = \underline1\
(I - P)\underline1 = 0
$$

在稳态的时候，离散系统的稳态状态：

$$
x_ {ss} = Px_ {ss}
$$

如果系统图有spinning tree，则$x_ {ss}= c\underline1$，可以得出$Pc\underline1 = c\underline1 \iff cP\underline1 = c\underline1 \iff P\underline1 = \underline1$，则系统中所有节点的值都达到稳态时共识值$c$，即$x_i = x_j=c,\space \forall \space i,j$

$$
w_ {1}=\left[p_ {1} \cdots p_ {N}\right]^{T} \text { be a left eigenvector of } P \text { for } \lambda_ {1}=1
$$

也就是对应在$L$的$\lambda_1=0$

$$
w^T_1x(k+1) = w^T_1Px(k) = w^T_1(I-\varepsilon L)x(k) = w^T_1x(k)-w^T_1 \varepsilon Lx(k)\\
$$

因为有spinning tree，所以公式（19）可用，即:

$$
w^T_1 \varepsilon Lx(k) =\varepsilon w^T_1 Lx(k),w^T_1 L = 0 \
$$

所以（28）等于：

$$
\quad w^T_1x(k+1)=w^T_1x(k)-w^T_1 \varepsilon Lx(k) = w^T_1x(k)
$$

所以前一个状态等于后一个状态，所有时刻的状态和左特征向量的矩阵乘积都相等，即共识值为一个定值：

$$
\bar{x} \equiv w_ {1}^{T} x=\left[p_ {1} \cdots p_ {N}\right]\left[\begin{array}{c}
x_ {1} \
\vdots \
x_ {N}
\end{array}\right]=\sum_ {i} p_ {i} x_ {i}
$$

$$
\sum_ {i} p_ {i} x_ {i}(0)=\sum_ {i} p_ {i} x_ {i}(k), \forall k
$$

本地控制协议 $u_{i}(k)=\frac{1}{1+d_ {i}} \sum_{j \in N_ {i}} a_{i j}\left(x_ {j}(k)-x_ {i}(k)\right)$

其中$d_i$是节点i的入度。

离散时间下的节点动力学：

$$
x_ {i}(k+1)=x_ {i}(k)+\frac{1}{1+d_ {i}} \sum_ {j \in N_ {i}} a_ {i j}\left(x_ {j}(k)-x_ {i}(k)\right)=\frac{1}{1+d_ {i}}\left(x_ {i}(k)+\sum_ {j \in N_ {i}} a_ {i j} x_ {j}(k)\right)
$$

相应的全局控制：

$$
u(k)=-(I+D)^{-1} L x(k)
$$

全局动力学为：

$$
x(k+1)=x(k)-(I+D)^{-1} L x(k)=(I+D)^{-1}(I+A) x(k) \equiv F x(k)
$$

矩阵$F$ 为正则化共识矩阵

$$
F=I-(I+D)^{-1} L=(I+D)^{-1}(I+A)
$$

对于F矩阵，如果图有spinning tree，则有如下性质：

  1. F矩阵有简单特征值$\lambda_1 = 1$
  2. 初$\lambda_1 =1$以外其他特征值都在零点圆心单位圆内
  3. 系统是临界稳定的，状态趋于稳态值
  4. $F\underline1 = (I-(I+D)^{-1}L)\underline1=\underline1$
  5. $\underline1$是$F$的第一特征值$\lambda_1$对应的右特征向量
  6. 所有特征值都在下图中灰色区域
image-20210914165751331

$$
w_ {1}^{T} x(k+1)=w_ {1}^{T} F x(k)=w_ {1}^{T} x(k)
$$

其中左特征向量$w_{1}=\left[p_ {1} \cdots p_ {N}\right]^{T}$ 对应$F$ 特征值 $\lambda_ {1}=1$

和上一个分布式protocol相似，共识值是一个运动常量，即：$\bar{x}=\sum p_{i} x_ {i}(k)$，不同的是分布式协议中$p_i$是矩阵Perron matrix $P$的第一左特征向量，而这里是共识矩阵 $F$的第一左特征向量。但是由于矩阵$F$中$(I+D)^{-1}$第 i 行除以了$1+d_i$，所以导致图$F$是不平衡的，所以尽管图$L$是平衡的，也不能达到所谓的平均共识，即以初始态平均值为共识值得稳态。但是如果所有的节点都有相同入度，则在平衡图上可以达到平均共识，因为$d_i$是相同的，这种情况称之为d-regular.

$$
w_ {i}^{T} F=w_ {i}^{T}\left(I-(I+D)^{-1} L\right)=w_ {i}^{T}
$$