Numerical-Method-Review

这是一篇计算方法期末复习的小笔记. 课程资料取自 > 计算方法 Numerical method (Spring 2024) By 刘景铖

函数求根

不动点迭代法

从 出发，迭代公式为

Theorem 1.1: 若 在 上连续可导，, 且 ，则 在 上的不动点迭代 .

牛顿法

迭代公式为

具有二次收敛性：

插值

拉格朗日插值

任意给定 个点， 过这 个点的 次多项式 有且仅有一个.

存在性证明：

令， 其中 .

则 .

唯一性用反证法证明.

假设存在另一个 次多项式 也满足过这 个点， 则 也是一个 次多项式，且过这 个点.

由于 有 个零点，所以 . 然而 是一个 次多项式，至多有 个零点，矛盾.

多项式插值与自纠错码

发送 个信息位，且至多发生 位错误， 那么如果需要检测传输过程是否出错，需要发送 个信息位. 同时，若是需要纠错，那么需要发送 个信息位.

切比雪夫插值

假设函数定义在 上，要选取使得：

Theorem 2.1: 令 ，则 . 此时上式取到最小值 .

特别的：. 其迭代公式为 .

范数

向量范数

对于向量 ： - 范数： . - 范数： . - 范数： . - 一般情况， 范数： .

矩阵范数

对于矩阵 ： - Frobenius 范数： . - 算子范数： . - 范数： .

对于算子范数，有： - ，即最大列和. - . - ，即最大行和.

矩阵的条件数

条件数是衡量矩阵 的数值稳定性的一个重要指标. 对于矩阵 ， 为误差向量，其条件数定义为：

特别的对于 2-条件数，有：

解线性方程组

高斯消元法

即 分解，将矩阵 分解为 为下三角矩阵， 为上三角矩阵.

Jacobi 迭代法

将矩阵 分解为 三部分，其中 为对角矩阵， 为下三角矩阵， 为上三角矩阵. 迭代公式为 .

Theorem 3.1: 若 为严格对角占优矩阵，则 Jacobi 迭代法收敛. 严格对角占优矩阵指的是对于任意 ，有 .

Gauss-Seidel 迭代法

迭代公式为 .

谱半径

考虑迭代方程为

对于迭代矩阵 ，其谱半径定义为 . > Theorem 3.2: 谱半径 当且仅当

• Jacobi 迭代法的迭代矩阵为
• Gauss-Seidel 迭代法的迭代矩阵为 $

最小二乘法

希望使得求解方程的误差最小，即

即等价于法线方程的解：

要想求解 ，不会直接计算 的逆，而是使用 QR 分解. 即 ，其中 为正交矩阵， 为上三角矩阵.

此时 ，所以

这需要用到 Gram-Schmidt 正交化方法来先求 : 假设 为矩阵 的列向量,则有：

再通过单位化得到 ： 矩阵 即为：

最后再来求解 ，对于正交矩阵 , 有 (即 )，因此有： 这是容易计算的，因此得到了 和 ，进而可以求解 .

正交系统里的最小二乘法：离散三角级数

给定数据 ，希望找到一个三角级数： 同样使用最小二乘法建模可以得到：

傅里叶变换

给定最多为 次的多项式 的系数，目标是求出其乘积 的系数.

单位根

次单位根 . - 1 次单位根： - 2 次单位根： - 4 次单位根： - 8 次单位根：

从上往下是开方的过程，从下往上是平方的过程.

离散傅里叶变换

输入多项式系数 ，选定为次单位根. 输出多项式在 个单位根上的取值.

逆变换即为用插值从 求出 . 复杂度为 .

快速傅里叶变换

运用分治的思想，将 个单位根分为两部分，分别计算其值，再合并，复杂度为 .

给定多项式:

FFT(A, w):
    if w == 1: return A(1)
    express A(x) in the form of A_even(x^2) + xA_odd(x^2)
    A_even = FFT(A_even, w^2)
    A_odd = FFT(A_odd, w^2)
    for j in range(n):
        A(j) = A_even(j) + w^j * A_odd(j)
    return A(w^0), A(w^1), ..., A(w^n)

其逆变换为：

IFFT(A, w):
    if w == 1: return A(1)
    express A(x) in the form of A_even(x^2) + xA_odd(x^2)
    A_even = IFFT(A_even, w^2)
    A_odd = IFFT(A_odd, w^2)
    for j in range(n):
        A(j) = A_even(j) + w^(-j) * A_odd(j)
    return 1/(n+1) * (A(w^0), A(w^1), ..., A(w^n))

特征值与特征向量

特征值的 min-max 刻画 (Courant-Fischer 定理)

对于实对称矩阵 ，其特征值 .

• 最大特征值：.
• 最小特征值：.
• 第 大特征值：.

对于最大特征值的 min-max 刻画证明：

因为 为实对称矩阵，所以可以设 的两两正交的特征向量为 ，对应的特征值为 ，那么： 并且有： 因此有：

正定矩阵

• 对于矩阵 ，若对于任意非零向量 ，有 ，则称 为正定矩阵.
• 若 ，则称 为半正定矩阵.

Theorem: 实数对称矩阵 为正定矩阵当且仅当其所有特征值均为正.

• 迹：矩阵 的迹定义为 .
• 行列式：矩阵 的行列式定义为 .
• Frobenius 范数：矩阵 的 Frobenius 范数定义为 .

在 是正定矩阵的情况下，有： 条件数有：

计算特征值与特征向量：幂迭代法

对于矩阵 ，其特征值 ，对应的特征向量为 ，且这些特征向量线性无关.

因此:

随着 的增大， 会趋近于 ，因此 会趋近于 .

最终得到一个近似的特征向量 ，要求解其近似的特征值 ， 由最小二乘法要最小化，即法线方程：

但此时仅近似得到了最大的特征值.

求解更多的特征值

相似矩阵

若 ，则 与 相似，它们有相同的特征值.

并且 QR 分解可以将矩阵 分解为 ，其中 为正交矩阵， 为上三角矩阵. 其给出了一个相似矩阵 ，在于下面的事实：

奇异值分解(SVD)

对于矩阵 ，其奇异值分解为 ，其中 为正交矩阵， 为对角矩阵.

Theorem: 与 有相同的非零特征值，且非零特征值为 的奇异值的平方.

将与的特征值记作，记 的正规正交的单位特征向量为 ， 的正规正交的单位特征向量为 ，则有：

那么将 作为列向量分别组合为 ，且有：

Lemma: 存在常数 使得：

注意到： 有两种写法：

因此有：

同理有： 由于(假设 )： 因此可以写出$： 即：

SVD 与 Rayleigh Quotient Iteration

对于矩阵 范数:

回顾： 特别地，正定矩阵 的二范数为 .

对于矩阵 的条件数:

回顾： 特别地，正定矩阵 的条件数为 .

Richardson 迭代法

对于线性方程组 ，迭代公式为：

Hessian 矩阵 & 凸函数

Hessian 矩阵

对于函数 ，其 Hessian 矩阵定义为： - 对于凸函数，其 Hessian 矩阵为半正定矩阵. 即对于任意 ，有 . 对于一个点, - 若 为正定矩阵，则 为局部极小值点. - 若 为负定矩阵，则 为局部极大值点.

共轭梯度法

给定正定矩阵 ，可以定义内积为： - 线性：. - 对称：. - 正定：.

称 为 共轭的向量，若对于任意 ，有：

其定义的范数为：

Theorem: 对于正定矩阵 ，其共轭向量一定线性无关.

共轭梯度法的目标是去近似 ，满足 那么要解 ，即找出：

那么共轭梯度法的迭代过程为：

随机游走

马尔科夫链

记 为时间 的状态， 为从状态 转移到状态 的概率，那么有：

记 为时间 状态为 的概率，那么有：

转移矩阵 ，其中 为邻接矩阵， 为度数矩阵. 有：

注意是可能不是一个对称的矩阵，但 对应一个相似且对称的矩阵：

• 对于有限的马尔可夫链，若其对应的有向图是强连通的，则称其为不可约的.
• 如果对于任意状态 ，所有 时刻返回 状态 的最大公约数为 ，则称其为非周期的.

Theorem: 若马尔可夫链是不可约的，且非周期的话，则一定存在足够大的常数 ，使得对于任意 ，有：

稳态分布

若马尔可夫链是不可约的，且非周期的，那么存在唯一的稳态分布 ，使得 - 随着 的增大，从任意初始状态出发，最终都会收敛到 . - ，其中 为状态 的期望回归时间.

Theorem: 对于任意有限的，连通的无向图(非二分图)，其稳态分布 ，其中 为度数向量， 为边数.

回归时间

对于状态 ，定义其回归时间为：

混合时间

对于马尔可夫链，其混合时间定义为：

特别的对于 的马尔可夫链，其混合时间: 其中，， 分别为矩阵第二大和最小的特征值.

惰性随机游走(Lazy Random Walk)

对于无向图 ，其邻接矩阵为 ，其度数矩阵为 ， 那么其转移矩阵为 . 即：

谱图论(Spectral Graph Theory)

邻接矩阵

对于无向图 ，其邻接矩阵 定义为：

图的邻接矩阵 的最大特征值 满足：

• 对于二分图，若 是其特征值，且重数为 ，则 也是其特征值，重数为 .

Lemma: 设图 的邻接矩阵 特征值为 ，若 ，那么图 是二分图.

拉普拉斯矩阵(Laplacian Matrix)

对于无向图 ，其度数矩阵 定义为： 其拉普拉斯矩阵 定义为： - 拉普拉斯矩阵是半正定矩阵. - 拉普拉斯矩阵的最小特征值为

Theorem: 图 是连通的，当且仅当其拉普拉斯矩阵特征值为 0 的重数为 1.

Perron-Frobenius 定理

对于非负矩阵 ，不可约且非周期： - 最大特征值为正，重数为 . - 对应的特征向量中，每个维度都是非零且同号的. -

Cheeger 不等式

对于无向图 ，其拉普拉斯矩阵 ，其特征值为 ，那么有： 其中 为图 的 Cheeger 常数.

电阻电路网络

给定一个无向图，每条边上有一个电阻 . - 基尔霍夫定律：所有进入某节点的电流的总和，等于所有离开这节点的电流的总和. 即内部流出的电流等于外部流入的电流. - 欧姆定律：把节点的电势记作 ，那么有：

• 两者合并有(在 情况下)： 即为

矩阵表示

给定电阻 ，若从节点 s 注入 的电流，并从节点 t 流出，通过计算： 可以模拟电阻电路网络内部的电流电压.

拉普拉斯矩阵的伪逆

Lemma: 若 ，则存在向量 使得 .

证明：假设 ，其中 ，那么由于拉普拉斯矩阵的 ，因此有： 即 .

因此对于拉普拉斯矩阵 ，其伪逆为：

等效电阻

对于电阻电路网络，若两个节点 之间的等效电阻为 ，那么有： 其中 满足 ，且 为 注入 电流后， 流出的电流.

Lemma: 等效电阻 为拉普拉斯矩阵 的伪逆 的第 行第 列元素. 即 . 向量 ，其余为 .

电势能

对于电阻电路网络，其电势能为： > Theorem: 电势能 ，其中 为节点 之间的等效电阻.

Thompson Principle

单位电流最小化所有能量.即： 其中， 为任意电流.

单调性

• 电势能 随着电阻增大而增大： 即若，则:

电阻电路的三角不等式

对于电阻电路网络，其等效电阻满足三角不等式：

随机游走的 Commute Time & Hitting Time

返程时间(Commute Time)：从节点 到节点 再返回节点 所需的时间:

Theorem: 对于任意节点 ，有： 其中 为边数.

Hitting Time：从节点 到节点 的时间:

即对于这一系列向量：

对于这一系列向量：

线性规划(Linear Programming)

线性规划标准型：

对偶问题

对于上述的标准型，其对偶问题为：

弱对偶性

对于标准型与对偶问题，有：

强对偶性

对于标准型与对偶问题，若标准型有最优解 , 对偶问题有最优解 , 那么有：

Farkas Lemma: 无解当且仅当存在 ，使得 .

组合优化问题线性规划示例

二分图完美匹配

该 LP 问题的最优解一定为整数解. 否则，可以通过对"环"的调整，使得其最优解为整数解.

最小生成树

二分图最大匹配 & 最小点覆盖

两者互为对偶问题.

最大匹配：

最小点覆盖：

最大流 & 最小割

两者互为对偶问题.

表示流量, 表示流入节点 的边， 表示流出节点 的边. 表示边 是否在割中， 表示节点 是否在源点 代表的集合 之中.

最大流：

最小割：

零和问题

对于两个玩家，分别为 ，有：

Theorem: 对于零和博弈，其最优解为纳什均衡. 即使一个玩家知道对方的策略之后，也不能找到比 当前策略严格更优的策略

Von Neumann Minimax Theorem

即在零和游戏中，无论谁先宣布自己的策略，都会达到均衡解. 证明即由于这两边可以写成一对对偶问题，由强对偶性可得.

左边可以写为：

右边可以写为：

即得证.

常用矩阵求导公式 (未求证正确性)

• 且 是对称矩阵，
• 且 不是对称矩阵，
• ，且 不是 的函数，
• ，,且