w wyl123ly 的博客
MD

20-线代-10-应用

30 KB 2026.10.17 原文件

线性代数 第 10 章 · 应用(40 题)

本章速览

5 篇 · 40 题:图与网络(10-1,9 题)、Markov 矩阵与稳态(10-2,9 题)、线性规划(10-3,6 题)、傅里叶级数与函数空间(10-4,7 题)、图形学与密码学(10-5,9 题)。

10-1 图与网络(9 题)

题号结论
10.1.1;、;独立回路
10.1.2;生成树 (目测 )
10.1.3电势 ;电流 ;
10.1.4
10.1.5KVL 的两种表述
10.1.6–10.1.9见解析

10.1.1 ( 的关联矩阵)

解

第 1 步:(,行=边)。

第 2 步:读数。 三个主元 ⇒ ;,基 (常电势);(基为空——树无回路)。

第 3 步:四个基本子空间。

  • (行空间,,维 ):;
  • :;
  • (维 );
  • 。

第 4 步:欧拉公式。 独立回路数

注意这里的欧拉公式针对几何图:。对树而言独立回路数 ✓( 无回路),与 一致。

答案 如上。

10.1.2 ( 的拉普拉斯矩阵与生成树)

解

第 1 步:。

第 2 步:特征值。 对 圈,:

第 3 步:生成树个数。

第 4 步:目测。 去掉任意一条边即得生成树 ⇒ 棵 ✓ 一致。

答案 如上。

10.1.3 (电阻网络)

解

第 1 步: 与接地。 同 10.1.2 的形式():

注入 ;接地节点 ()。

第 2 步:解方程(节点 1–3)。

由第三式 ;代入第二式 ;代入第一式 。故

第 3 步:电流。 :

第 4 步:功率守恒。

✓

第 5 步:为什么线性下降。 每个内部节点满足 邻边电流 ,即

这正是 的中心差分 ⇒ 解为线性函数。

答案 、。

10.1.4 ()

解

第 1 步:二次型。 由 :

第 2 步:零空间。 每条边上 在每个连通分量内为常数。

第 3 步:维数。 设连通分量数为 ,则 由各分量的示性向量张成 ⇒ 。

第 4 步:结论。 由秩—零化度:

10.1.5 (KVL 的两种表述)

解

第 1 步: 的含义。 存在节点电势 使 ,即每条边上有 (电势差)。

第 2 步:等价性。 沿任一回路 求和,电势差望远镜相消:

反之,若所有回路求和为零,则「沿路径积分与路径无关」⇒ 可定义单值电势 ⇒ 。

第 3 步:三角形反例。 取三角形 ,若 ,则沿回路求和 ⇒ 。物理含义:这种电压分布无法由任何电势实现,即违反 KVL——不存在这样的稳态电阻网络。

答案 得证。

10.1.6 (反向一条边)

解

第 1 步: 的变化。 第 行()变成 ,即该行取反(非零元位置由 变为 )。

第 2 步:节点方程。 中等式左边 的系数全变号 ⇒ 相当于把未知量换成 。

第 3 步:自由度与解集。 不变、 不变 ⇒ 自由度 不变;通解的形状不变,只需把 换成 (即环流方向反号)。基础解系(回路向量)的结构不变。

答案 该行取反;方程中 变号;自由度与基础解系结构不变。

10.1.7 (灌溉网)

解

第 1 步:(1) 总和。 ✓(可解的必要条件)。

第 2 步:(2) 自由度。 连通图:。

第 3 步:(3) 孤立节点。 封闭后节点 孤立且 。此时 的秩

(剩下 个节点仍连通),而增广矩阵多一列(含 所在方程常数)

⇒ 无解。

第 4 步:(4) 改数据。 新 ⇒ 仍无解(总量不为零是硬性障碍)。

答案 如上。

10.1.8 (Kruskal 与最小生成树)

解

第 1 步:(1) 排序。 权重 对应边 –,从小到大:。

第 2 步:逐步加边。 依次加入 (不成圈,收)、(收)、(收)——已得 条边,算法停止。

第 3 步:(2) 列无关。 生成树无回路 ⇒ 对应 3 列的关联矩阵子块满秩(),故线性无关。

第 4 步:(3) 与独立回路数。 补边数

生成树的边数 、补边数 ,二者之和为 ✓

答案 MST 为 (总权 ),其余见解析。

10.1.9 (两个可行方案之差)

解

第 1 步:差满足齐次方程。 若 ,则

第 2 步:零空间即回路空间。 由「沿独立回路绕行」的向量张成(维数 )。

第 3 步:物理结论。 两个可行流量方案的差别只能是环流(绕圈流动、净效果为零)——不改变任何节点的净注入。

10-2 Markov 矩阵与稳态(9 题)

题号结论
10.2.1 是随机矩阵; 稳态不唯一
10.2.2;稳态
10.2.3;不收敛;时间平均收敛
10.2.4三条证明
10.2.5正稳态 强连通
10.2.6–10.2.9见解析

10.2.1 (四个矩阵)

解

第 1 步:判随机性(列和为 )。 ✓; ✓; 列和 、 ✓; ✓。四个都是随机矩阵。

第 2 步:稳态。

  • :,幂迭代收敛();
  • :解 得 ,收敛();
  • :任意 都是稳态,稳态不唯一, 不收敛到唯一点。

答案 如上。

10.2.2 (二状态链的闭式)

解

第 1 步:特征值。 、:

第 2 步:稳态。 由 得 ,配合 :

第 3 步:闭式。 由 ,:

第 4 步:极限。 ⇒ 。

答案 如上。

10.2.3 (三周期链)

解

第 1 步:特征值。 是三轮换置换矩阵,:

第 2 步:为什么不收敛。 初值沿特征向量方向的分量按 旋转而不衰减,故 以周期 振荡。

第 3 步:稳态。 由对称性 。

第 4 步:时间平均。

(因 是秩 矩阵,列全等于 。)

答案 如上。

10.2.4 (对称随机矩阵)

解

第 1 步:(1) 双随机。 列和为 ,由 得行和 。

第 2 步:(2) 实特征值与 。 对称 ⇒ 可正交对角化 ⇒ 特征值全实。又对任意特征对,…更直接:由 (列和)得 。

第 3 步:(3) 唯一稳态。 ⇒ 不可约且非周期 ⇒ 单重 ⇒ 稳态唯一;由双随机性 ✓。

10.2.5 (正稳态与强连通)

解

第 1 步()。 设 。由 与 、,得所有满足 的 都有 。反复传播,与 互通的节点全为 ——若强连通则 ,矛盾。

第 2 步()。 强连通 ⇒ 不可约 ⇒ 由 Perron–Frobenius, 的(右)特征向量可取全正。

答案 得证。

10.2.6 ( 的 PageRank)

解

第 1 步:。 。

第 2 步:稳态。 用

第 3 步:零入链页面。 其分数来自均匀项,为

(原来 时为 。) 越小,均匀项越大,排名越「平均」。

答案 如上。

10.2.7 ( 与 的特征值关系)

解

第 1 步:特征方程。 设 、:

第 2 步:左乘 。 因 随机 ⇒ :

左边 ,故

(这一步用到 。)

第 3 步:回代。 均匀项消失,,即

故 是 的特征值。

10.2.8 (复特征值链)

解

第 1 步:(1) 随机性。 三列和都是 :、、 ✓

第 2 步:(2) 特征值。 特征多项式 :

复根的模 。

第 3 步:(3) 收敛性。 有自环(,概率 )⇒ 非周期 ⇒ 幂迭代收敛(不是周期病态,也不可约?——检查:;;,三状态互通 ⇒ 不可约 ✓)。

第 4 步:(4) 加阻尼。 的特征值为

后两者的模 ⇒ 必然收敛。

答案 如上。

10.2.9 ()

解

第 1 步:(1) 随机性。 列和 ✓

第 2 步:(2) 稳态不变。 若 ,则 ,故 ✓

第 3 步:(3) 更多初值收敛。 取周期链 、:

的幂对一般初值振荡不收敛;而 全正 ⇒ 任意初值都收敛到 。即「更多初值收敛」(这是 MCMC 中「取平均」思想的雏形)。

10-3 线性规划(6 题)

题号结论
基础 1标准形见解析
基础 2顶点 ;;(不唯一)
进阶 3对偶与互补松弛
进阶 4原问题 、对偶
思考 5、6见解析

基础 1 (化标准形)

解

第 1 步:目标。 改写成

第 2 步:约束方向。 两边乘 :

第 3 步:自由变量。 ()。

第 4 步:标准形。

答案 如上。

基础 2 (顶点枚举)

解

第 1 步:顶点。 两两约束取等的交点中满足全部约束者:

( 是 与 的交点。)

第 2 步:。

第 3 步:。

在 与 都取到 ⇒ 整条边都是最优解(不唯一),因为 与约束 平行。

答案 如上。

进阶 3 (对偶与互补松弛)

解

第 1 步:对偶形式。 原问题 、、 的对偶是

第 2 步:可行性验证。 代入 检查 与 (按第 3.2 节的具体数据代入即可)。

第 3 步:为什么 。 互补松弛要求

若原问题最优解使第 条约束严格不紧(),则必有 ——这条约束「没有起到限制作用」,其影子价格为 。

答案 如上。

进阶 4 (原问题与对偶)

解

第 1 步:原问题。

第 2 步:可行顶点。 、、、(后者是 与 的交点)。

第 3 步:目标值。

第 4 步:对偶。

第 5 步:对偶最优。 原问题第 、 条约束紧、第 条松 ⇒ ,解

对偶值 ⇒ 强对偶 ✓

第 6 步:互补松弛。 ⇒ 对偶第二约束紧: ✓; ⇒ 原第二约束可松: ✓

答案 、,最优值 。

思考 5 (等值线平行于约束边)

解

第 1 步:梯度方向。 目标 的等值线法向为 。

第 2 步:取等面。 若 (),则沿第 条约束面 移动时目标值不变(因为移动方向与 垂直)。

第 3 步:结论。 该面上任一顶点都是最优解 ⇒ 最优解集包含整条边。几何上:等值线与某条边平行时,目标沿该边恒定,故最优不唯一。

思考 6 ( 的形状)

解

第 1 步:对偶表示。 由强对偶(对 max 问题):

第 2 步:凹性。 是若干线性函数 的逐点最小 ⇒ 凹函数 ✓

第 3 步:分段线性。 对偶可行域的顶点有限, 在每个「最优顶点不变」的区域上是线性的;顶点切换处出现折点。

第 4 步:折点与基。 原问题最优基为 时 ; 变化使基更换 ⇒ 跳变 ⇒ 的斜率跳变(折点)。

10-4 傅里叶级数与函数空间(7 题)

题号结论
基础 1三组正交关系
基础 2(a)(c) ;(b) ;(d) 无必然为零的系数
进阶 3三角波级数;
进阶 4Leibniz 级数;
进阶 5偶延拓更快
思考 6、7见解析

基础 1 (三角函数的正交性)

解

第 1 步:余弦。 时用积化和差:

时 ✓

第 2 步:正弦。 同理 。

第 3 步:交叉项。

(整周期上正弦积分为零。)

基础 2 (哪些系数必为零)

解

第 1 步:(a) 。 偶函数 ⇒ 。

第 2 步:(b) 。 奇函数 ⇒ (含 )。

第 3 步:(c) 。 偶函数 ⇒ 。

第 4 步:(d) 。 既非奇也非偶 ⇒ 一般 都非零( 型,均非零)。

答案 (a)(c) ;(b) ;(d) 无必然为零者。

进阶 3 (三角波)

解

第 1 步:偶函数。 是偶函数 ⇒ 。

第 2 步:。

第 3 步:。

第 4 步:级数。

第 5 步:代入 。 左边 :

✓

答案 如上。

进阶 4 (Leibniz 与 Basel 级数)

解

第 1 步:锯齿波。 的傅里叶级数为

第 2 步:代入 。

(因 只在 时非零且符号交替。)故

第 3 步:帕塞瓦尔。 ,而 :

✓

答案 如上。

进阶 5 (偶延拓 vs 奇延拓)

解

第 1 步:奇延拓。 本身就是奇函数,级数为

在 处收敛到 ✓

第 2 步:偶延拓。 得 型(三角波)的余弦级数:

在 处也为 ✓

第 3 步:收敛速度。 偶延拓()连续、分段光滑,系数 ;奇延拓在 处有跳跃( 与 ),系数只有 。故偶延拓级数收敛更快。

答案 如上。

思考 6 (系数的衰减)

解

第 1 步:分部积分。

第 2 步:边界项消失。 以 为周期 ⇒ ,而 ⇒ 边界项为 。

第 3 步:界。 记 ,由柯西–施瓦茨:

同理 。

第 4 步:光滑性的作用。 每多一次分部积分(要求 多一阶可导)就多一个 因子 ⇒ 越光滑衰减越快( 函数系数 ,解析函数指数衰减)。

思考 7 (特征函数与对角化)

解

第 1 步:特征函数。

即 是 的特征函数,特征值 。

第 2 步:热方程被对角化。 把 代入 :

由正交性(各频率独立)得无穷多个解耦的一阶方程

每个都解为指数衰减。

第 3 步:与 的共同点。 两者都是特征分解:把耦合系统变换到特征基上变成对角(解耦)系统。有限维用 (特征向量矩阵),无限维用傅里叶基(特征函数系);热方程的 对应矩阵情形的 。

10-5 图形学与密码学(9 题)

题号结论
基础 1;
基础 2;
基础 3、 见解析;HI→WJ
进阶 4逆转置法向
进阶 5旋转时
进阶 6
思考 7–9见解析

基础 1 (旋转 + 平移)

解

第 1 步:顺序。 列向量左乘 ⇒ 右边先作用。「先旋转、后平移」写作

第 2 步:矩阵。

第 3 步:作用。

答案 ,。

基础 2 (旋转矩阵正交)

解

第 1 步:。

✓

第 2 步:逆。 正交 ⇒ ;而 正是把 换成 的矩阵 ⇒ 。几何上「转回去 = 反转同样的角」。

基础 3 (希尔密码)

解

第 1 步:行列式。 , ⇒ 模 可逆。

第 2 步:逆。 ():

第 3 步:加密 HI。 、:

第 4 步:解密。

✓

答案 如上。

进阶 4 (法向量的逆转置)

解

第 1 步:(a) 变换法向。 对角 ⇒ :

内积 ✓

第 2 步:(b) 直接用 变换法向。

✗ 不再垂直。

第 3 步:(c) 几何解释。 方向拉伸 倍后,原本垂直于平面的方向被「拉斜」——平面倾斜了,法向必须相应调整才保持垂直。逆转置 使内积保持不变:

答案 如上。

进阶 5 (旋转时无需逆转置)

解

第 1 步:正交性。 旋转 ⇒ 、。

第 2 步:逆转置。

第 3 步:结论。 故 ——旋转下法向可以直接用 变换。几何上:刚体旋转不改变夹角,法向随曲面一起转即可。

进阶 6 (扩展欧几里得)

解

第 1 步:辗转相除。

第 2 步:回代。

第 3 步:取模。

核对:pow(17,-1,3120) 给出 ✓

答案 。

思考 7 ( 上可逆的判据)

解

第 1 步:逆的公式。 ,在 中需 有逆元。

第 2 步:逆元存在条件。 。而 ,故

第 3 步:逐个判断。 四个矩阵的行列式分别为 、、、——都是奇数且不被 整除 ⇒ 都可逆。

思考 8 (投影不可逆 = 无法恢复三维)

解

第 1 步:投影矩阵。 透视/正交投影 满足 、 ⇒ ⇒ 不可逆。

第 2 步:四大子空间的语言。

  • 屏幕坐标空间 (可见的像);
  • 丢失的信息 (沿视线方向的分量);
  • 由于 ,不同的三维点可以映到同一屏幕点(差一个 中的向量)。

第 3 步:结论。 「投影不可逆」与「无法由屏幕坐标唯一恢复三维坐标」是同一件事:解 有无穷多解(特解 + )。

思考 9 (无噪声 LWE 可解)

解

第 1 步:问题退化。 噪声 时,——这是一个线性方程组。

第 2 步:求解步骤。

  1. 在 中选出 列,使其构成的子矩阵 在 上可逆();
  2. 取对应的 ,计算 (高斯消元,);
  3. 用其余方程验证。

第 3 步:复杂度与启示。 多项式时间可解。带噪声时 变成「含错的线性方程组」,一般情形下是 NP 困难(LWE 的安全性来源)。这也说明希尔密码(正是 的线性体制)在已知明文攻击下不安全:用 组明文—密文对即可解出密钥矩阵。