当前课程知识点：线性代数(2) > 第八讲：图与网络 > 8.3 网络和加权Laplacian矩阵 > 8.3 网络和加权Laplacian矩阵
大家好
刚才我们讨论了图和矩阵
特别地 对于一个图呢
我们可以赋予一个关联矩阵A
我们也可以引入拉普拉斯矩阵
它等于A＾TA
这是个半正定阵
那么现在我们来讨论
这些的加权版本
也就是说一个图呢
我们可以给每条边赋予一个数
那么这样子呢是有实际意义的
当一个图赋予每一个边
某一个数的时候
我们当然这些数我们假设是大于0的
那么这个图呢
我们就成为一个网络
所以一个图
加上它每条边上赋予的这个数
这个数我们叫权
就是说加权的图就是一个网络
那么一个网络它引入这些数
是有实际意义的
比如说当这条边是弹簧的时候
那么这个c_i就是弹性系数
那么边呢
是我们现在考虑的电路的时候
那么这个c_i就是电导等等
那么C等于
有了这些数以后
我们可以构成一个对角阵
C等于c_1到c_m
m是图的边的个数
那么这时候我们可以考虑
刚才的拉普拉斯矩阵
它的加权形式
也就是说A＾TCA
我们称为加权的拉普拉斯矩阵
那么大家可以看到
当A是我们上一节的
差分矩阵那种形式的时候
那么A＾TCA呢
就是上一节的刚度矩阵
那么现在呢在这一节呢
我们讨论的这个A呢
是我们使用关联矩阵
那么这个A＾TCA呢
它也刻画了
我们这个电路的一些性质
我们先来回忆一下
相关的物理定律
第一个就是
我们刚才说过的欧姆定律
欧姆定律说一条电路上的电流
等于电导乘上电势差
一条边上的电流
等于电导乘上电势差
我们中学有时候也写成
电压等于电流乘上电阻
那么电阻就是电导的倒数
我们同学有的经常看到
电流乘上电阻等于电压
那么我们现在使用的是
电流等于电压乘上电导
而第二个呢是关于
图或网络的科尔霍夫电压定律
他说每一条回路
上面的电势差之和为零
我们刚才说了回路
它是不是按方向的
只要是若干条边首尾相接
它们起点和终点一样
就叫一条回路
那么每条回路上的电势差
之和为零
科尔霍夫电流定律是说
每一个顶点流入的电流
和流出的电流
当这整个系统是平衡的时候
是一样的
我们将使用这三个物理定律
把它使用在我们对电路图讨论上
我们讨论的时候
还是使用跟弹簧
质体位移相似的一个框架
也就是说u到e 再到y 最后到f
那么u表示的是各个顶点的电势
e表示的是每条边上的电势差
而y呢是每条边上的电流
f是从每个顶点流入的外部电流
我们现在先通过一个例子
来说明这个计算
我们考虑右边这个电路图
这当然是抽象版本
它有四个顶点 有五条边
那么我们可以先写出关联矩阵
这个四列代表四个顶点
五行代表了五条边
1 2 3 4 5
比如说第5条边
它是从③指向④的
那么在3这一块呢
第3列我们写-1 第4列就写1
那么我们现在设各顶点的电势
为u_1 u_2 u_3 u_4
这样我们把它合在一起
就可以做成一个向量u
有四个分量
那么我们第一步要做的是
从u到e
e就是各条边上的电势差
那么给了各个顶点的电势
那么各个边的电势差
我们当然很容易计算了
我们写出这个电势差
那么我们写成e等于
我们这又增加了一个负号
这是为了跟后面的计算电流
为了匹配的
因为电流总是从电势高的
流向电势的低的
所以电流它的方向呢
如果我们用电势高的电势
减去电势差
那么得到的才是合理的
所以e等于
相邻顶点的电势之差得到这个
这些就是我们的电势差
那么我们可以写出
它的相应的一个矩阵形式
那么这个矩阵呢我们可以写出来
我们把这个负号写在前面
那么这是-1 1 0 0
这个是0 -1 1 0
这个是-1 0 1 0
这是-1 0 0 1
0 0 -1 1
那大家可以看到
这个矩阵就是我们的关联矩阵
所以实际上呢
这个电势差就等于关联矩阵
乘上各点的电势形成的向量
这样我们完成了第一步
从u到e的过渡
下面我们利用欧美定律
来计算一下从e到y
也就是说从各个边上的电势差
来计算各个边上的电流
那么这个呢
我们假设各个边上的电导为
c_1 c_2 c_3 c_4 c_5
那么我们就可以得到
电流向量就是y_i等于c_i乘上e_i
也就是说电流等于电导乘以电压
或者电势差
那么我们把它写成矩阵的形式呢
就如y等于这个对角阵乘上e
而最后我们来看一下
从各个边上的电流我们来计算
进入各个顶点的外部电流
我们可以看到此时f等于0
那么我们来检查一下
各个顶点的流出和流入电流
由科尔霍夫电流定律
每一个顶点流入的电流
等于流出的电流
那么我们确切地写一下
关于刚才我们这张图上来看
在第一个顶点只有流出的
没有流入的
我们流入我们就前面打个负号
第二个顶点呢
从1这条边流入 从2这条边流出
所以y_1-y_2=0
而3这个顶点呢
是从2 3两条边流入
第5条边流出
所以y_2+y_3-y_5=0
而由此呢
我们可以把它
写成一个矩阵的形式
那大家可以看到
这个矩阵应该是
它反映了四个顶点的情况
所以它应该是四行
那么五列
那么确切地写一下
那么我们可以看到
第一个是y_1 0 -1 -1 0
第二个呢是1 -1 0 0 0
第三个呢是0 1 1 0 -1
第四个是0 0 0 1 1
那么这个矩阵我们仔细看一下
我们看它的每一列只有1和-1
那么实际上每一列
它恰好对应的是
我们原来图的五条边
所以这个矩阵
实际上就是我们的A＾T
所以最后呢我们可以看到
我们可以写成一个矩阵的形式
就是A＾Ty=0
好 我们把刚才这些讨论
总结一下
我们首先给出四个顶点的电势
然后由四个顶点的电势
使用关联矩阵左乘以后
我们得到了各个边上的电势差
那么确切的电势差应该
等于-Au
然后我们使用这个电势差
或者电压我们来计算
各个边上电流
那么这个呢
从我们的欧姆定律反映出来了
就是y_i=c_i×e_i
也就是电流等于电导乘上电压
最后因为y部的电流没有流入
所以f是等于0的
但是我们确切地来算一下
而发现用科尔霍夫电流定律
我们可以计算出
f=A＾y 是等于0的
那么它使用的这个矩阵
正好和这个矩阵互为转置
我们得到了一个相同的框架
好 下面我们再来看一个
这个电路图呢
它有外部的电流源
和外部的电压源的情形
比如右边这个电路图
它有外部的电流元源f_2
还有电压源b_3
或者b_3是个电池
那么此时我们再来计算一下
当这个出于平衡状态的时候
我们设各点的电势为
u_1 u_2 u_3 u_4
那么我们可以得到这个向量u
那么我们来计算一下
各个边上的电势差
那么这时候呢我们看
这个1 2 4 5这几条边呢
跟原来计算没有区别
就是把相应的两个端点电势
作个差就行了
u_2 u_3 u_4-u_3 u_4-u_1
那么第3条边呢大家注意
它上面放了一块电池
所以
这个电池本身产生的电势差b_3
那么所以呢
在第3条边上差生的电势差
应该是b_3-u_3-u_1
所以我们写成了令b等于
这个向量b=d-Au
那么这时候这个矩阵呢
还是关联矩阵
好 下面我们再来计算
第二部分e跟y的关系
那么这时候e是等于b-Au
那么使用欧姆定律呢
还是y等于一个对角阵乘上b减Au
其中C呢就等于c_1到c_5
c_5是电导
最后我们来计算一下y跟f的关系
那么刚刚上一个例子中呢f是0
那么在这个例子中呢
我们看f将不再是0
因为有一条外部的电流源f_2
从2到4
我们使用科尔霍夫的电流定律
流入等于流出
那么我们来看各个顶点
特别地我们要看顶点②
大家看在顶点②中呢
1 2两条边
一条是流入 一条流出
所以是y_1-y_2
而同时呢
我们有一个外部的电流源
从2到4
那么就从2流出的
所以是减去f_2 最后等于0
顶点④呢有4 5是流入的
所以y_4+y_5
另外还有个外部电流源流入f_2
所以y_4+y_5+f_2=0
那这样我们就可以得到
一个矩阵的形式
这个矩阵形式呢我们看到f_2
我们把它拿出来
跟刚才有点区别
所以我们可以写成
把f_2移到右边 左边只留下y_i
所以我们可以把左边
写成一个-1 0 -1 0 -1
1 -1 0 0 0
0 1 1 -1 0
0 0 0 1 1
乘上y_1到y_5 等于f_2
这一块是0 f_2 0 -f_2
那么我们写成这个矩阵形式呢
这个它就是A＾T
这就是我们的y
我们把这个外部电流源
这个向量呢我们用f表示
A＾Ty等于f
那么现在的情况呢
跟刚才的区别在于有了f和b
那么我们可以把这个代进去
就得到了f=A＾TC
再乘上B-Au
那么我们在这块大家可以看到
实际上呢我们也可以把
外部的电流源放进来
因为外部和内部是相对的
当你把外部电流源放进来以后呢
大家看2到4
那条就产生了一个新的边
那么我们的关联矩阵呢
就可以换成一个更大的关联矩阵
当你用更大的一个关联矩阵
乘的时候
那么这时候的f呢实际上
就在作为一个新的边上的电流
那么这时候你可以看到
它也产生了一个新的平衡
所以我们也可以
通过引入一条新的边
把原来的A关联矩阵加宽一行
那么我们就可以重新表达
这个A＾Ty等于f
那么电压和电流的平衡方程呢
我们根据这个刚才表达式呢
我们可以写成一个
这两个形式
如果刚才第一种情况呢
b等于0的时候
那么我们可以看到
y就等于-CAu
那么如果f等于0的时候呢
A ＾y就是0
这两种没有外部电流源和电压源的情形
我们总结一下
这张图体现了
有一个外部的电压源
和外部的电流源输入进来的时候
这时候这张图
我们还是相同的框架
但是有新的两个源
那么刚度矩阵我们确切地算一下
那么这样一个矩阵呢
它仍然是半正定的情形
特别地 如果我们取c_1 c_2 c_3
都取1的时候
那么大家可以看到
这个k就变成了下面这种形式
那么这个形式的证法
就回到了我们的拉普拉斯矩阵
因为这时候C是一个单位阵
所以L就等于A＾TA
那么根据拉普拉斯矩阵的特点呢
我们看到
这个3就表示经过
顶点①的三条边
c_1+c_3+c_5就是当
最开始那个刚度
加权的A＾TCA的形式呢
c_1+c_3+c_5就对应着这个边
1 3 5经过顶点①
c_1+c_2就对应着边1和2
经过顶点②
类似于我们上一讲的
这个K也是一个对称的正半定阵
但是它不是正定的
因为我们知道A这个矩阵呢
它的每一边或者每一行的和
是等于0的
这样A乘上这个1 1
这个向量以后等于0
说明A是列相关的
从而我们推出K不是正定阵
给定一个网络
也就是刚才我们说的
一个图上每一边加一个正数
这个正数我们叫权
那么假设这个网络有n个顶点
c_1到c_m是m条边上的权
那么一般地这个K呢
等于关联矩阵的转置乘上C
再乘上A
那么确切地写出来呢
K的第i行第j列的元素就是连接
i和j的边的权值和的相反数
比如说i不等于j的时候
那么K_ij呢 当i等于j的时候
是经过i这条边的权值之和
当i和j不相等
i和j而且不相邻
也就是说没有边相连接它们
那么K_ij就是等于0的
那么我们可以确切地算一下
一般的给一个向量
n维向量 A＾TKx
它可以写成
这样一个平方和的形式
因为这个K_ij我们知道
当i不等于j的时候
它取的是相反数
所以-K_ij实际上是个正数
或者是非负的
所以我们可以看到
x＾TKx是大于等于0的
从这个角度也可以看出
K呢是一个正半定阵
-1.1 实对称矩阵A正定的充要条件
-1.2 典型例题
--1.2 典型例题
-1.3 半正定矩阵及其判别条件
-1.4 二次型
--1.4 二次型
-1.5* 有心二次曲线(central conic)
-1.6* 三维空间中的二次曲面-6类基本的二次曲面
-1.7 二次型的分类
-1.8 矩阵的合同
-1.9* 惯性定理的证明
-1.10 惯性定理的应用 —— 实对称矩阵的特征值与主元符号
--1.10 惯性定理的应用 —— 实对称矩阵的特征值与主元符号
-1.11* 正（负）定矩阵在函数极值问题中的应用
-第一讲：正定矩阵--课后习题
-2.1 引言
--2.1 引言
-2.2 相似矩阵的性质
-2.3 Jordan标准形
-2.4 定理的证明
-2.5 Jordan标准形的应用
-第二讲：相似矩阵--课后习题
-3.1 引言
--3.1 引言
-3.2 奇异值分解(Singular Value Decomposition)
--3.2 奇异值分解(Singular Value Decomposition)
-3.3 例题
--3.3 例题
-3.4 奇异值分解的应用
-第三讲：奇异值分解--课后习题
-4.1 线性变换的定义和性质
-4.2 线性变换的运算
-4.3 线性变换的矩阵表示
-4.4 线性变换与矩阵之间的关系
-第四讲：线性变换 I--课后习题
-5.1 恒同变换与基变换
-5.2 图像压缩——基变换的应用
-5.3 线性变换在不同基下的矩阵
-5.4 矩阵分解与基变换
-5.5 线性变换的核与像
-5.6 不变子空间
-5.7* 幂零变换
-5.8* Jordan标准形
-第五讲：线性变换 II--课后习题
-6.1 伪逆
--6.1 伪逆
-6.2 Moore – Penrose 伪逆
-6.3 最小二乘法
-第六讲：伪逆--课后习题
-7.1 简介
--7.1 简介
-7.2 弹簧模型
--7.2 弹簧模型
-7.3 变量的线性关系
-7.4 刚度矩阵
--7.4 刚度矩阵
-7.5 从离散到连续
-第七讲：工程中的矩阵--课后习题
-8.1 简介
--8.1 简介
-8.2 图和矩阵
--8.2 图和矩阵
-8.3 网络和加权Laplacian矩阵
-8.4 关联矩阵的四个基本子空间
-8.5 注记
--8.5 注记
-第八讲：图与网络--课后习题
-9.1 问题引入
--9.1 问题引入
-9.2 Markov矩阵
-9.3 正Markov矩阵
-9.4 正矩阵
-第九讲：Markov矩阵和正矩阵--课后习题
-10.1 引言
--10.1 引言
-10.2 内积空间
-10.3 傅里叶级数
-10.4 投影
--10.4 投影
-10.5 关于Fourier变换的注记
-第十讲：Fourier级数--课后习题
-11.1 引言
--11.1 引言
-11.2 平移
--11.2 平移
-11.3 伸缩
--11.3 伸缩
-11.4 旋转
--11.4 旋转
-11.5 投影和反射
-第十一讲：计算机图像--课后习题
-12.1 引言
--12.1 引言
-12.2 复矩阵
--12.2 复矩阵
-12.3 复正规阵
-12.4 离散Fourier变换
-12.5 快速Fourier变换
-第十二讲：复数与复矩阵--课后习题
-结课寄语
--结课寄语
