万物科技 学,以致用

线性代数 12 - 图和网络

2017-12-04
Geng

前面的内容虽然生动形象, 但是所有例子都是编造的, 并不是真的来自实际问题. 这次内容就是看看实际问题中, 线性代数能有什么作用.

基尔霍夫定律

  • 基尔霍夫电流定律又称为基尔霍夫第一定律:

所有进入某节点的电流的总和等于所有离开这节点的电流的总和。

注意, 这个是关于节点的定律.

  • 基尔霍夫电压定律又称为基尔霍夫第二定律:

沿着闭合回路所有元件两端的电势差(电压)的代数和等于零。

注意, 这个是关于的定律

这次的内容就是将基尔霍夫定律与线性代数联系起来

图(graph)由节点(node)与边(edge)组成.

看这个图:

这是一个有向图(每个边都有箭头指向). 我们可以构造一个矩阵来解析这个图, 这个矩阵就是关联矩阵(incidence matrix). 它告诉我们 $n$ 个点如何由 $m$ 个边连接起来.

上图的关联矩阵为:

注意这里的正负号.

假设这个矩阵为 $A$, 那么根据消元法方法, 可以发现前三行是线性相关的. 对照上图, 这三行形成了一个回路(Loop). 对于图来说, 回路意味着线性相关.

空间

现在研究下 $m \times n$ 矩阵 $A$ 的各种空间.

列空间和行空间

$A$ 的列在 $R^m$ 中, 列的线性组合构成列空间 $C(A)$, 是 $R^m$ 的子空间. 这些组合就是 $Ax$.

$A$ 的行在 $R^n$ 中, 行的线性组合构成列空间 $C(A^T)$.

研究 $Ax=0$, 可以得到:

这里的 $x$ 是节点电势, $A$ 就是各个边上电势差的矩阵. $Ax=0$ 研究的就是电势差什么时候全为零呢?

零空间和左零空间

$A$ 的零空间 $N(A)$ 包含所有满足 $Ax=0$ 的向量 $x$. $N(A)$ 是 $R^n$ 的子空间. 左零空间包含所有满足 $A^Ty=0$ 的向量 $y$. $N(A^T)$ 是 $R^m$ 的子空间.

$x$ 是各点电势, $y$ 是各边电流

根据之前的知识, 我们有如下关系:

$dim \ C(A)=dim \ C(A^T)$, $dim \ C(A)+dim \ N(A) = n$

零空间可以解得为: $x=C(1, 1, 1, 1)^T$.

对于 $Ax=0$ 来说, 零空间每一个向量都和行空间的任意向量垂直. 向量 $x=(1, 1, 1, 1)^T$ 垂直于所有行, 所以垂直于这个行空间, 而这个向量说明每个节点有相同的电压, 那么也就不会有电流了.

有向图和关联矩阵

假设一个 $m=6, n=4$ 的矩阵及其对应的图, 如下所示

将 $A$ 化简后为阶梯矩阵, 非零行成为矩阵 $B$, 其对应的图为:

$A$ 对应的图示完备的, 每对节点都有边连接. $B$ 对应的图示一个(🌲), 没有闭合回路. 这两个图是两个极端, 一个有最多的边: $\dfrac 1 2 n(n-1)$, 一个有最少边: $m=n-1$. 这个例子可以看出, 消元法将图变为了树

**如果行线性相关, 边构成一个回路. 线性无关的行来自树. **

对于列空间, 我们来看 $Ax=0$:

$Ax$ 的每一行都是各点沿着某一边的线性组合, 因为一条边最多两个点, 所以每行的形式都是 $x_i - x_j$

行空间

我们怎么知道向量 $v=(v_1, v_2, v_3, v_4)$ 是否在行空间呢? 笨方法就是做一个各行的线性组合, 快的方法是观察正交性:

当且仅当 $v$ 垂直于零空间的 $(1, 1, 1, 1)$ 时, 它在行空间, 也就是 $v$ 的各个元素相加为1

列空间

我们怎么知道一个向量 $b$ 是否在列空间呢? 笨方法就是解 $Ax=b$. 不过这样的话就无法洞察究竟.

观察方程 (1), $Ax$ 是一个差值的向量. 如果我们将这个差值沿着一个回路相加, 最后为 0. 沿着边 $1, 3, -2$ (注意方向) 相加:

电压定律: $(x_2-x_1) + (x_3-x_2) - (x_3 -x_1)=0$

$Ax$ 的围绕一个回路的元素相加为0.

对于方程 $Ax=b$ 来说, $b$就是 $A$ 的列向量, 那么因为回路相加为 0, 可以看出:

$b_1 + b_3 - b_2 = 0$

这就是基尔霍夫电压定律又称为基尔霍夫第二定律:

沿着闭合回路所有元件两端的电势差(电压)的代数和等于零。

零空间和左零空间

零空间可得到各点等电势, 那么左零空间呢?

$A^Ty = 0$, $y$ 是各边电流, 它的每一行都是各个边上的某个点的电流和.

这就是基尔霍夫电流定律又称为基尔霍夫第一定律:

所有进入某节点的电流的总和等于所有离开这节点的电流的总和。

欧拉公式

根据各个空间的维数, 可以得到欧拉公式(Euler’s Formula)。$零维(节点)-一维(边)+二维(回路)=1$

网络和$A^TCA$

电压差 $Ax$ 驱动电流, 由于电导率 $C$ 的存在, 决定了电流流动有多容易. 图可以通过关联矩阵 $A$ 来描述, 它告诉我们点和边的连接情况. 网络更进一步, 为每一边加入了传导率 $C$: 它的元素有 $C_1, C_2, … C_m$, 而且这是一个对角矩阵

欧姆定律

$电流 = 电导率 \times 电压$, 即 $y = CAx$. 因为 $A^Ty = 0$, 可得: $A^TCAx=0$

在今后的学习中, 我们将会经常看到类似的方程.

如果考虑外部激励, 那么将会是:

$A^TCAx=f$, $f$ 是外部激励.


Similar Posts

Comments

你可以请我喝喝茶,聊聊天,鼓励我

Wechat Pay
wechat

Thanks!