数值分析基础

大二下学期数值分析基础的复习笔记，目前已完结。

一、预备知识

1. 有效数字：误差不大到影响前 $n$ 位数字
2. 误差估计：$|y-\tilde{y}|\leq\sum_i \left|\frac{\partial f}{\partial x_i}\right||x_i-\tilde{x}_i|$
3. 避免：大数吃小数、相近数相减、与大数相乘、与小数相除
4. 特征值：$\text{trace}(A)=\sum \lambda_i$，$\det(A)=\prod \lambda_i,\sigma(A)={\lambda_i},\rho(A)=\max |\lambda_i|$
5. 实对称阵：特征值全为实数，可对角化，特征向量构成正交基
6. 内积：加法、数乘、共轭对称、正定
7. MGS：立刻投影
8. 范数：正定、齐次、三角不等式，p-范数 $||x||_p=(\sum |x_i|^p)^{1/p}$，$\infty$-范数 $||x||_\infty=\max_i |x_i|$
9. 范数等价：存在正常数使得 $c_1||x||_\alpha\leq ||x||_\beta\leq c_2||x||_\alpha,\forall x\in V$，有限维空间所有范数等价，由 Cauchy-Schwarz $|(x,y)^2|\leq (x,x)(y,y)$ 有 $||x||_1\leq \sqrt{n}||x||_2$
10. 距离：非负、对称、三角不等式，可由范数诱导 $d(x,y)=||x-y||$

二、线性方程组的直接法

1. 三对角矩阵 LU 分解：主次对角线，循环三对角加最后一行/列
2. 矩阵范数：正定、齐次、三角不等式、次可乘/相容 $||AB||\leq||A||\cdot||B||$
3. 矩阵范数与向量范数相容：$||Ax||\leq ||A||\cdot||x||$，F 范数 $\sqrt{\sum_{i,j} a_{ij}^2}=\sqrt{\text{trace}(A^TA)}=\sqrt{\sum \sigma_i^2}$ 与 2-范数相容
4. 从属于给定向量范数的矩阵范数：$||A||=\max_{x\neq 0} \frac{||Ax||}{||x||}$，与对应向量范数相容
5. 常用矩阵范数：$\infty$-范数/1-范数（行/列向量 1-范数最大值）、2-范数 $\sqrt{\rho(A^TA)}$（最大奇异值，对称阵为谱半径）
6. 谱半径与范数：$\rho(A)\leq ||A||$，且 $\forall\epsilon$ 存在范数使得 $||A||\leq \rho(A)+\epsilon$
7. 摄动引理：$||\cdot||$ 为从属范数，A 可逆，$||A^{-1}||\cdot||\delta A||\lt 1\Rightarrow A\pm\delta A$ 可逆且 $||(A\pm\delta A)^{-1}||\leq \frac{||A^{-1}||}{1-||A^{-1}||\cdot||\delta A||}$
8. 条件数：$\frac{|f(x+\delta x)-f(x)|}{|f(x)|}\leq \kappa(x)\frac{|\delta x|}{|x|}$，矩阵为 $||A||\cdot||A^{-1}||$，其中 $||\cdot||$ 为从属范数，描述 $\delta b$ 对 $x=A^{-1}b$ 的影响
9. 方程组扰动分析：$\frac{||\delta x||}{||x||}\leq \frac{\text{cond}(A)}{1-||A^{-1}||\cdot||\delta A||}\left(\frac{||\delta A||}{||A||}+\frac{||\delta b||}{||b||}\right)$
10. 条件数与特征值：$\text{cond}(A)\geq \frac{\lambda_{\max}}{\lambda_{\min}}$，$\mathrm{cond_2}(A)=\frac{\sigma_{\max}}{\sigma_{\min}}$，对称阵 $\mathrm{cond_2}(A)=\frac{\lambda_{\max}}{\lambda_{\min}}$

三、方程组的迭代法

1. 收敛阶：$\forall k\ge k_0$ 有 $\frac{||x^{(k+1)}-x^*||}{||x^{(k)}-x^*||^p}\leq C$，超线性 $p=1$ 且 $\lim\frac{||x^{(k+1)}-x^*||}{||x^{(k)}-x^*||}=0$
2. 线性定常单步迭代法：$x^{(k+1)}=Bx^{(k)}+f$，$\rho(B)\lt 1$ 或存在从属矩阵范数使得 $||B||\lt 1$ 时收敛，收敛率 $R_k(B)=-\ln||B^k||^{1/k}\to-\ln\rho(B)$
3. 压缩映射原理：转化为 $x=G(x)$，检查 $G$ 局部压缩、映内（多用 1-范数）
4. Newton 迭代：$x^{(k+1)}=x^{(k)}-F^\prime(x^{(k)})^{-1}F(x^{(k)})$，求解 $F^\prime(x^{(k)})\delta x=-F(x^{(k)})$，阻尼 $F^\prime(x^{(k)})^{-1}\Rightarrow [F^\prime(x^{(k)})+\lambda_k I]^{-1}$
5. Shamanskii 方法：每 $m$ 步更新一次 $F^\prime$，$+\infty$ 时为 chord
6. 线性方程组：$x=(I-M^{-1}A)x+M^{-1}b$，Richardson $M=I$，Damping $M=\alpha I$，Jacobi $M=\text{diag}(A)$，Gauss-Seidel $M=D+L$，SOR $M=\frac{1}{\omega}D+L$，有 $\rho(B_\omega)\geq |\omega-1|$
7. 对角占优：$|a_{ii}|\geq \sum_{j\neq i} |a_{ij}|$ 至少一个严格成立，有 Jacobi、Gauss-Seidel 收敛
8. 对称正定：有 Gauss-Seidel 收敛，$0\lt\omega\lt 2$ 时 SOR 收敛
9. 最速下降法：$\phi(x)=\frac{1}{2}x^TAx-b^Tx$，沿梯度方向线搜索，两次方向正交且 $||x^{(k)}-x^*||_A\leq\left(\frac{\lambda_1-\lambda_n}{\lambda_1+\lambda_n}\right)^k||x^{(0)}-x^*||_A$
10. 共轭梯度法：用 $A$-共轭向量组 $p^{(k)}=r^{(k)}+\beta_{k-1}p^{(k-1)}$，满足 $(r^{(k+1)},p^{(k)})=0$、剩余向量组正交、$||x^{(k)}-x^*||_A\leq2\left(\frac{\sqrt{\kappa}-1}{\sqrt{\kappa}+1}\right)^k||x^{(0)}-x^*||_A$

四、多项式插值

1. 插值方程：$\sum_{j=0}^n c_ja_j(x_i)=f(x_i)$，Lagrange $f(x_i)\prod_{i\neq j} \frac{x-x_i}{x_j-x_i}$，余项 $\frac{f^{(n+1)}(\xi(x))}{(n+1)!}\omega_{n+1}(x),\omega_{n+1}(x)=\prod_{i=0}^n (x-x_i)$
2. Newton 插值：$\sum_{j=0}^n f[x_0,\cdots,x_j]\omega_j(x),f[x_0]=f(x_0),f[x_0,\cdots,x_n]=\frac{f[x_1,\cdots,x_n]-f[x_0,\cdots,x_{n-1}]}{x_n-x_0}$ 或 $\frac{f^{(n)}(x_0)}{n!}$，余项 $f[x,x_0,\cdots,x_n]\omega_{n+1}(x)$
3. 分段低次插值：线性有 $a_i(x_j)=\delta_{ij}$ 且线性；$k$ 次有子区间上不超 $k$ 次且 $C^{k-1}[a,b]$
4. 三次样条：$f(x_i)$、节点 0,1,2 阶连续、边界条件 $n+1+3\cdot(n-1)+2=4n$，固支 $S^\prime(x_0,x_n)=f^\prime(x_0,x_n)$，自然 $S^{\prime\prime}(x_0,x_n)=0$，周期 $S^{(k)}(x_0)=S^{(k)}(x_n),k=0,1,2$
5. 三弯矩方程：$h_i=x_i-x_{i-1},\frac{h_i}{h_i+h_{i+1}}S_{i-1}^{\prime\prime}+2S_i^{\prime\prime}+\frac{h_{i+1}}{h_i+h_{i+1}}S_{i+1}^{\prime\prime}=6f[x_{i-1},x_i,x_{i+1}],1\leq i\leq n-1$，固支 $h_0=h_{n+1}=0$，周期 $h_1(2S_0^{\prime\prime}+S_1^{\prime\prime})+h_n(S_{n-1}^{\prime\prime}+2S_n^{\prime\prime})=6(f[x_0,x_1]-f[x_{n-1},x_n])$

五、函数逼近

1. 法方程：$\sum_{j=0}^n c_j(a_j,a_i)=(f,a_i)$，解有 $(f(x)-s^*(x),s(x))=0$，误差 $||\delta(x)||=||f(x)-s^*(x)||$
2. 周期函数的最佳平方逼近：$\frac{1}{2}a_0+\sum_{j=1}^n (a_j\cos jx+b_j\sin jx),a_j,b_j=\frac{1}{\pi}\int_{0}^{2\pi} f(x)\cos jx,\sin jx \mathrm{d}x$
3. 正交多项式：在 $[a,b]$ 上恰有 $n$ 个零点，Legendre $[-1,1],\rho=1$；Lagurre $\mathbb{R^+},\rho=e^{-x}$；Hermite $\mathbb{R},\rho=e^{-x^2},H_{n+1}(x)=2xH_n(x)-2nH_{n-1}(x)$
4. Chebyshev 多项式：$[-1,1],\rho=\frac{1}{\sqrt{1-x^2}},T_{n+1}(x)=2xT_n(x)-T_{n-1}(x)$，极值点 $\cos\frac{j}{n}\pi$ 交替 $\pm 1$，在首 1 $\mathcal{P}_n$ 中 $[-1,1]$ 上 $\infty$-范数最小，零点 $\cos\frac{2j-1}{2n}\pi$ 用于 Lagrange 插值
5. 最小二乘问题：离散内积 $\sum_{i=0}^m \rho(x_i)f(x_i)g(x_i)$ 下的最佳平方逼近，或 $x=(A^TA)^{-1}A^Tb=R^{-1}Q^Tb$，正则化误差 $||\delta(x)||^2_2+\lambda||x||^2_2\Rightarrow$ $A^TA+\lambda I$
6. 奇异值分解：$U,V$ 为 $AA^T,A^TA$ 特征向量，非列满秩最小二乘 $x=V_1\Sigma_r^{-1}U_1^Tb+V_2z=A^+b+V_2z$

六、数值积分

1. 插值型求积公式：中点、梯形、Simpson $\frac{b-a}{6}(1,4,1)$ 截断误差 $\frac{(b-a)^5}{2880}f^{(4)}(\xi)$，复合求积法分段低阶
2. 代数精度：对所有 $\mathcal{P_n}$ 精确但对某些 $\mathcal{P_{n+1}}$ 不精确
3. Newton-Cotes 公式：等距 Lagrange，梯形、Simpson、Simpson 3/8 $\frac{b-a}{8}(1,3,3,1)$，代数精度偶 $n+1$ 奇 $n$
4. Gauss 求积：节点 $x_0,\cdots,x_n$ 为带权 $\rho$ 在 $[a,b]$ 上的 $n+1$ 阶正交多项式零点，代数精度 $2n+1$，Gauss-Chebyshev 系数 $\frac{\pi}{n+1}$ 求含 $\frac{1}{\sqrt{1-x^2}}$ 的积分

七、常微分方程数值解

1. 定义：$\frac{\mathrm{d}y}{\mathrm{d}x}=f(x,y),x\in[a,b]$，令 $x_n=a+nh,h=\frac{b-a}{N}$，则 $y(x_{n+1})=y(x_n)+\int_{x_n}^{x_{n+1}} f(x,y(x))\mathrm{d}x=y(x_n)+hf(\xi)$，取 $\xi=x_n$ 得左矩形公式 $y(x_{n+1})=y(x_n)+hf(x_n,y(x_n))$，用 $x_i$ 代替得向前 Euler 公式 $y_{n+1}=y_n+hf(x_n,y_n)$
2. 截断误差：整体 $e_n=y(x_n)-y_n$，局部截断误差 $T_{n+1}=y(x_{n+1})-y(x_n)-h\varphi(x_n,y(x_n),h)$ 即以前各步无误差时计算 $x_{n+1}$ 的误差，$T_{n+1}=O(h^{p+1})$ 则方法为 $p$ 阶，$p\geq 1$ 相容，可用 Taylor 展开构造高阶方法 $\varphi=y^\prime(x_n)+\frac{h}{2}y^{\prime\prime}(x_n)+\cdots$
3. Runge-Kutta 方法：$\int_{x_n}^{x_{n+1}} f(x,y(x))\mathrm{d}x\approx \sum_{i=0}^s b_i f(x_i)\Rightarrow y_{n+1}=y_n+h\sum_{i=0}^s b_i f(x_n+c_ih,Y_i),Y_i=y_n+h\sum_{j=0}^s a_{ij}f(x_n+c_jh,Y_j)\approx y(x_n+c_ih),\sum_{j=1}^s a_{ij}=c_i$ 为 $s$ 级，$A$ 纯下三角则显式，下三角则半隐式，一级显式 RK 即向前 Euler，二级显示 RK 中点法/修正 Euler $f(x_n+\frac{1}{2}h,y_n+\frac{1}{2}hf(x_n,y_n))$ 或改进 Euler $\frac{1}{2}(f(x_n,y_n)+f(x_{n+1},y_n+hf(x_n,y_n)))$
4. 线性多步法：$y_{n+k}=-\sum_{j=0}^{k-1} \alpha_j y_{n+j}+h\sum_{j=0}^k \beta_j f(x_{n+j},y_{n+j})$，有局部截断误差 $T_{n+k}=c_0 y(x_n)+c_1hy^\prime(x_n)+\cdots,c_i=\frac{1}{i!}\sum_{j=0}^k \alpha_j j^i-\frac{1}{(i-1)!}\sum_{j=0}^k \beta_j j^{i-1}$，有第一/第二特征多项式 $\rho(\xi)=\sum_{j=0}^k \alpha_j \xi^j,\sigma(\xi)=\sum_{j=0}^k \beta_j \xi^j$
5. 线性齐次差分方程：$\alpha_k y_{n+k}+\cdots+\alpha_0 y_n=0$，特征方程 $\alpha_k \xi^k+\cdots+\alpha_0=0$，根 $\xi_j$ 重数 $m_j$ 则通解 $y_n=\sum_j P_{m_j-1}(n)\xi_j^n$
6. 初值/零稳定性：多步法给定 $k$ 个初值扰动后得到两组解 $u_n,v_n$，存在 $C,h_0$ 使得 $0\lt h\leq h_0$ 有 $\max_{n} |u_n-v_n|\leq C\max_{0\leq j\leq k-1} |u_j-v_j|$，等价于 $\rho(\xi)$ 的根模 $\leq 1$ 且 $=1$ 全为单根，$k$ 奇则不超 $k+1$ 阶，$k$ 偶则不超 $k+2$ 阶
7. 收敛性：对任一固定的 $x_n=x_0+nh$ 有 $\lim_{h\to 0} y_n=y(x_n)$，等价于相容+稳定，相容且 $\varphi$ 对 $y$ Lipschitz 则收敛
8. 绝对稳定性：求解试验方程 $y^\prime=\lambda y$ 的数值方法若对任意初值给定步长 $h$ 后有 $\lim_{n\to\infty} y_n=0$ 则该方法对步长 $h$ 绝对稳定，$z=h\lambda$ 在复平面上为绝对稳定区域，与实轴的交为绝对稳定区间，等价于使得稳定多项式 $\Pi(\xi;z)=\rho(\xi)-z\sigma(\xi)=0$ 的根模 $\leq 1$ 的 $z$