插值与拟合

方程求根 - 二分法

每次区间长度减半
于是 $\epsilon_n\leq \frac{b-a}{2^n}$

方程求根 - 不动点迭代法

$x_{n+1}=g(x_n)$，最终收敛到不动点 $r=g(r)$
收敛当且仅当在 $r$ 附近的一个邻域内有 $|g’(x)|<1$（泰勒展开+中值定理）
一次收敛，即 $S=\lim\frac{e_{i+1}}{e_i}<\infty$

方程求根 - 牛顿法

$x_{n+1}=x_n-\frac{f(x_n)}{f’(x_n)}$（本质是求切线的零点）
二次收敛，即 $S=\lim\frac{e_{i+1}}{e_i^2}<\infty$（先证明收敛公式局部收敛，再泰勒展开+中值定理）

插值 - Lagrange插值

思想：直接构造经过插值点的多项式
思路：对于每个插值点，找出一个多项式使得在该点位置取 $1$，在其余插值点位置取 $0$；将所有的多项式加权相加即可。该多项式至多为 $n-1$ 次的（代数基本定理）
具体：$L_k(x)=A(x-x_1)\cdots(x-x_{k-1})(x-x_{k+1})\cdots(x-x_n)$，$A$ 用于调节系数使得 $L_k(x_k)=1$
误差分析：对 $f$ 的插值结果为 $P$，则有：$$f(x)-P(x)=\frac{\prod_{i=1}^n(x-x_i)}{n!}f^{(n)}(x)$$

插值 - 秘密分享与信息传输

当允许丢包 $k$ 个时，需要 $k$ 个冗余进行还原
当允许损坏 $k$ 个时，需要 $2k$ 个冗余进行还原、$k$ 个冗余进行判别
证明思路同对手论证

插值 - Chebyshev插值

目的：最小化最大误差 $\max_{x\in[-1,1]} |\prod_{i=1}^n(x-x_i)|$
插值基点：上式最小值在 $x_i=\cos\frac{(2i-1)\pi}{2n}$ 时取到 $2^{-(n-1)}$
多项式：$T_n(x)=2^{n-1}(x-x_1)(x-x_2)\cdots(x-x_n)=\cos(n\arccos(x))$
递推形式：$T_{n+1}(x)=2xT_n(x)-T_{n-1}(x)$
唯一性：他是唯一一个能在 $\pm1$ 之间往返 $n+1$ 次的 $n$ 次多项式（定义域在 $[-1,1]$上）

最小二乘法

定义：$\min |Ax-b|_2$，可化简为：$A^\top Ax^*=A^\top b$
几何解释：找到 $b$ 在 $A$ 上的投影在 $A$ 中的线性组合形式
微积分解释：考虑梯度下降法时，梯度为 $0$ 的情况
变分法解释：考虑误差函数的变分最优性
计算：$(A^\top A)^{-1}$ 不便于计算，因此考虑将 $A$ 正交化，而后 $A^\top A=I$
傅里叶级数：$\varphi_0(x)=\frac12,\varphi_k(x)=\cos(kx),\varphi_{n+k}(x)=\sin(kx)$

FFT

拆分为 $DFT$ 和 $IDFT$ 两个过程，分别是计算插值和其逆过程
对于插值过程，考虑多项式拆分使得 $F(x)=E(x^2)+xO(x^2)$，计算 $F(\omega^i)$
对于逆过程，将 $\omega$ 换为 $\omega^{-1}$ 即可
$NTT$：使用原根代替 $\omega$，运算发生在 $\mathbb{Z}_p^*$ 上

线性矩阵操作

高斯消元法

思想：维护出一个上三角矩阵，逐行操作
$E_k\cdots E_2E_1Ax=E_k\cdots E_2E_1b$，其中 $E_k\cdots E_2E_1=L$ 为下三角矩阵；则 $A=LU$
最坏情况下时间复杂度为 $O(n^3)$

矩阵范数和条件数

$|A|F=\sqrt{\sum{x\in A}x^2}=\sqrt{tr(A^\top A)}$
$|A|p=\max{x\neq 0}\frac{|Ax|_p}{|x|p}=\max{|x|_p=1}|Ax|_p$
举例：$|A|1=\max{1\leq j\leq n}\sum_{i=1}^n|a_{i,j}|$（绝对值意义下最大列和）
举例：$|A|2=\max{|x|2\leq 1}\sqrt{x^\top A^\top Ax}=\sqrt{\lambda{\max}(A^\top A)}$；当 $A$ 正定时 $|A|_2=\lambda_\max(A)$
举例：$|A|\infty=\max{1\leq i\leq n}\sum_{j=1}^n|a_{i,j}|$（绝对值意义下最大行和）
$|A|{p\rightarrow q}=\max{x\neq 0}\frac{|Ax|_q}{|x|_p}$
$\text{cond}(A)=|A||A^{-1}|\geq|AA^{-1}|=1$
举例：$\text{cond}_2(A)=\frac{\sigma_\max(A)}{\sigma_\min(A)}$；特别地，对于对称正定 $A$，有 $\text{cond}_2(A)=\frac{\lambda_\max(A)}{\lambda_\min(A)}$

解线性方程 - Jacobi迭代

思想：对 $A$ 进行拆分：$A=L+D+U$，则 $Ax=b\Leftrightarrow (L+D+U)x=b$
迭代方程：$x_{n+1}=D^{-1}(b-(L+U)x_n)$
谱半径要求：$\rho(D^{-1}(L+U))<1$
收敛要求：严格对角占优，即 $\forall i,|a_{i,i}|>\sum_{j\neq i}|a_{i,j}|$

解线性方程 - Gauss-Seidel迭代

思想：在Jacobi迭代的基础上利用本次的新的下三角矩阵进行更新
迭代方程：$x_{n+1}=D^{-1}(b-Ux_n-Lx_{n+1})$
谱半径要求：$\rho((L+D)^{-1}U)<1$

谱分解

$Av_i=\lambda_iv_i\Rightarrow AV=VD\Rightarrow A=VDV^{-1}$
任意一组向量都可以唯一表示为任意一组正交基的线性组合

Courant-Fisher刻画

$\lambda_n(A)=\max_{x\neq 0}\frac{x^\top Ax}{x^\top x}$
$\lambda_1(A)=\min_{x\neq 0}\frac{x^\top Ax}{x^\top x}$
证明方法：考虑将 $x$ 表示为单位正交基 $v_i$ 的线性组合放缩即可
更一般地：$$\lambda_k(A)=\min_{dim(U)=k}\max_{x\in U,x\neq 0}\frac{x^\top Ax}{x^\top x}$$ $$\lambda_k(A)=\max_{dim(U)=n-k+1}\min_{x\in U,x\neq 0}\frac{x^\top Ax}{x^\top x}$$

Cayley-Hamilton定理

令 $A$ 的特征多项式为 $p_A(x)=\text{det}(A-xI)=c_0+c_1x^1+\cdots+c_nx^n$，则 $p_A(A)=O$
两边同乘 $A^{-1}$ 可证明 $A^{-1}$ 有多项式表示
证明（对于可对角化的 $A$）：$p_A(A)$ 的特征值全为 $0$，因此为 $O$

求特征值和特征向量 - 幂迭代

考虑 $A^kx=\lambda_1^k(\alpha_1v_1+(\frac{\lambda_2}{\lambda_1})^k\alpha_2v_2+\cdots+(\frac{\lambda_n}{\lambda_1})^k\alpha_nv_n)$
于是 $A^kx$ 在绝对值意义下最大特征值唯一时，收敛于 $v_1$ 方向
求出最大特征值后，考虑 $A’=(A-qI)^{-1}$ 的特征值

SVD

$AA^\top$ 的特征向量为 $u_1,\cdots,u_m$，组合为 $U\in\mathbb{R}^{m\times m}$
$A^\top A$ 的特征向量为 $v_1,\cdots,v_n$，组合为 $V\in\mathbb{R}^{n\times n}$
于是有 $U^\top U=I_m,V^\top V=I_n$
由于 $AA^\top$ 和 $A^\top A$ 有相同特征值，于是可得 $U^\top AV=\text{diag}(\sqrt{\lambda_1},\cdots,\sqrt{\lambda_n})$，即 $A=USV^\top$

解线性方程 - Richardson迭代

思想：$b+(1-a)b+(1-a)^2b+\cdots=\frac{b}{1-(1-a)}=a^{-1}b$
迭代方程：$x_{n+1}=(I-\alpha A)x_n+\alpha b$
共轭内积解释：该迭代方程是对于 $\min \frac12x^\top Ax-b^\top x$ 的梯度下降
谱半径要求：$\rho(I-\alpha A)=\max(|1-\alpha\lambda_1|,|1-\alpha\lambda_n|)<1$；令其二者互为相反数，则 $\alpha=\frac2{\lambda_1+\lambda_n}$

解线性方程 - 共轭梯度法

定义：$\langle x, y\rangle_A=x^\top Ay$，$|x|_A=\sqrt{x^\top Ax}$
目标：令 $Ax^*=b$，最小化 $|x-x^*|_A$
性质：共轭向量一定是线性无关的，因此组成一组基
空间：令 Krylov 子空间为 $K_0={0},K_i=\text{span}{b,Ab,\cdots,A^{i-1}b}$
算法：考虑从 Krylov 子空间中取出 $x$ 使得 $x=\text{argmin}_{x\in K_i}|x-x^*|_A^2$
最多迭代 $n+1$ 次即可得到精确解

谱图论

转移矩阵

设当前分布为 $x$，则 $x’=(AD^{-1})x$
定义：$W=AD^{-1}$
转化：$\mathcal{A}=D^{-\frac12}AD^{-\frac12}$，于是 $W^t=D^{-\frac12}\mathcal{A}^tD^{-\frac12}$，且 $\mathcal{A}$ 为实对称矩阵，可谱分解 $\mathcal{A}=V\Sigma V^\top$

稳态分布

稳态分布 $\mathop{\pi} \limits^{\rightarrow}$ 使得 $\mathop{\pi} \limits^{\rightarrow}=\mathop{\pi} \limits^{\rightarrow} P$
距离度量：$d_\text{tv}(p,q)=\frac12|p-q|1=\frac12\sum{i=1}^n|p_i-q_i|$
无向图随机游走的稳态分布为 $\mathop{\pi} \limits^{\rightarrow}=\frac{1}{2m}\mathop{d} \limits^{\rightarrow}$，因此有限的连通非二分图的回归时间为 $h_i=\frac{2m}{d_i}$
Lazy Random Walk：转移矩阵为 $\frac12I+\frac12AD^{-1}=\frac12(I+W)$

马尔可夫链

基本定理：对于一个非周期不可约的平稳马尔可夫过程，任意一个分布在 $t\rightarrow\infty$ 时都会收敛到唯一一个稳态分布 $\mathop{\pi} \limits^{\rightarrow}$，其中 $\pi_i=\frac{1}{h_i}$；其中 $h_i$ 为回归时间
非周期：存在一个状态使得状态函数 $\text{period}(i)=\text{gcd}{t|P_{i,i}^t>0}$ 为 $1$
不可约：有向马尔可夫图是强连通的

邻接矩阵

对于邻接矩阵的特征值，有 $d_\text{avg}(G)\leq \lambda_1\leq d_\text{max}(G)$；左侧考虑瑞利商，右侧考虑特征值放缩
若 $A$ 的特征值通过相反数两两可配对，是 $G$ 为二分图的充分必要条件

Laplace矩阵

定义1：$L=D-A$，其中 $D=\text{diag}(d_1,d_2,\cdots,d_n)$
定义2：$L=\sum_e L_e$；其中 $L_e$ 在 $i,j$ 和 $j,i$ 处为 $-1$，在 $i,i$ 和 $j,j$ 处为 $1$，在其余位置为 $0$
正定性：$L$ 半正定（定义推导），且一定有至少一个特征值为 $0$（全 $1$ 为特征向量）
连通性：$L$ 特征值中 $0$ 的重数为图的连通分支数（分块矩阵证明）

随机游走 - 谱分析（正则图）

令 $W=AD^{-1}=\frac1dA$ 为转移矩阵，设其特征值为 $\lambda_1,\cdots,\lambda_n$，对应特征向量为 $v_1,\cdots,v_n$
设初始分布为 $p=c_1v_1+c_2v_2+\cdots+c_nv_n$，考虑 $W^tp=c_1\lambda_1^tv_1+c_2\lambda_2^tv_2+\cdots+c_n\lambda_n^tv_n$
假设图为连通非二分图，即 $\lambda_2=\lambda_1-\epsilon_a$，$\lambda_n=-\lambda_1+\epsilon_b$
于是 $W^tp$ 收敛到 $c_1v_1$，收敛速度与 $|\epsilon_a|$ 和 $|\epsilon_b|$ 有关；$c_1v_1$ 特征值为 $1$，即为稳态分布

随机游走 - 混合时间

定义 $\epsilon$-混合时间为最小的 $t$ 使得 $d(p_t,\pi)_{\text{tv}}<\epsilon$
定义谱间隔 $\lambda=\min(1-\lambda_2,1-|\lambda_n|)$（即为上一节中的 $|\epsilon_a|$ 和 $|\epsilon_b|$）
则随机游走的 $\epsilon$-混合时间最多为 $\frac1\lambda\log(\frac{n}{\epsilon})$
直观上来看，谱间隔描述了最大特征值占据主导地位的程度；谱间隔越大，收敛越快

电阻电路网络 - 概念

电阻 $r_{u,v}$，电导率 $w_{u,v}=\frac1{r_{u,v}}$
基尔霍夫定律： $\sum_{u:vu\in E}i_{vu}=b_v$
欧姆定律：$\phi(u)-\phi(v)=i_{uv}r_{uv}$
合并：$b_v=(\text{d}w(v)-\sum{u:vu\in E}w_{uv})\phi(u)$
于是对于 $r_{uv}=1$ 的图，有 $\mathop{b}\limits^{\rightarrow}=L\mathop{\phi}\limits^{\rightarrow}$

电阻电路网络 - 伪逆

考虑连通的电阻电路网络，$L$ 有一重特征值 $0$
于是考虑 $L$ 的伪逆 $L^\dagger=\sum_{i=2}^n\frac{1}{\lambda_i}v_iv_i^\top$
又因为 $\langle\mathop{b}\limits^{\rightarrow}, \mathop{1}\limits^{\rightarrow}\rangle=0$，于是解集为 ${L^\dagger+c\mathop{1}\limits^{\rightarrow}}$

电阻电路网络 - 等效电阻与电势能

等效电阻定义：$R_\text{eff}(s,t)=\phi(s)-\phi(t)$
等效电阻计算：$R_\text{eff}(s,t)=b_{st}^\top L^\dagger b_{st}$
单调性：若将网络中电阻调大，则任意两点间等效电阻增大（加电阻视为从 $\infty$ 降低）
电势能：$E(s,t)=R_\text{eff}(s,t)\leq E(\mathop{g}\limits^\rightarrow)$，其中 $\mathop{g}\limits^\rightarrow$ 是任意 $s,t$ 流（最小化电势能）

随机游走 - 碰撞时间与往返时间

$h_{st}$ 记为从 $s$ 出发首次到达 $t$ 的期望时间
考虑向量 $\mathop{h_{*t}}\limits^\rightarrow$，由于 $h_{ut}=1+\frac1{d_u}\sum_{v\sim u}h_{vt}$，于是有 $L\mathop{h_{*t}}\limits^\rightarrow=(d_1,\cdots,d_{t-1},d_t-2m,d_{t+1},\cdots,d_n)$
在无向图中，有 $C_{st}=h_{st}+h_{ts}$，后两者不一定相等，通过上一条求解
考虑 $L(\mathop{h_{t}}\limits^\rightarrow+\mathop{h_{s}}\limits^\rightarrow)$，得到 $C_{st}=2mR_\text{eff}(s,t)\leq 2m$
遍历时间：最多为 $2m(n-1)$（考虑最小生成树上的往返拆分）

线性规划

举例 - 二分图匹配

目标：$\max \sum_{e\in E}c_ex_e$，其中 $c_e=-1$
约束：$\forall u\in V, \sum_{e\sim u}x_e\leq 1$（完美匹配时为等号）
约束：$\forall e\in E,0\leq x_e\leq 1$

举例 - 最小生成树

目标：$\max \sum_{e\in E}c_ex_e$，其中 $c_e=-w_e$
约束：$\forall S\subseteq V,\sum_{e\in G[S]}x_e\leq |S|-1$（无环约束）
约束：$\sum_{e\in E}x_e=|V|-1$（边数约束）
约束：$\forall e\in E,0\leq x_e\leq 1$

线性对偶

考虑线性规划问题：$\max c^\top x\quad \text{s.t.} \quad Ax\leq b,x\geq \mathop{0}\limits^\rightarrow$
对偶问题为：$\min b^\top x\quad \text{s.t.}\quad A^\top y\geq c,y\geq \mathop{0}\limits^\rightarrow$
强对偶性原理：以上两个问题的最优解相等

Min-Max原理

利用线性对偶的转化可以轻松证明一些结论
证明：二分图中最大匹配等于最小覆盖
证明：网络流中最大流等于最小割