数值计算

工程数学数值计算方法

第一章 有效数字与相对误差限

记录有效数字及误差限的基础概念。

第二章 方程求根

不动点迭代法

求解方程 \(f(x)=0\) 的迭代过程：

• 等价转化为 \(x=g(x)\) 的形式；
• 选择一个初始值 \(x_0\)；
• 递推 \(x_{n+1}=g(x_n)\)。

若 \(x^*\) 是 \(g(x)\) 的根，且 \(g\) 在该处可导：

\[ g’(x^*)=g’‘(x^*)=\cdots=g^{(k-1)}(x^*)=0,\quad g^{(k)}(x^*) \neq 0 \]

则迭代达到 \(k\) 阶收敛。

全局收敛定理：若 \(g(x)\) 在 \([a,b]\) 上连续，在 \((a,b)\) 上可导，且存在 \(L < 1\) 使得 \(\lvert g’(x) \rvert \le L\)，则迭代全局收敛。

局部收敛定理：若 \(x^*\) 是方程 \(x=g(x)\) 的根，且 \(g’(x^*)\) 在该处连续并满足 \(\lvert g’(x^*) \rvert < 1\)，则迭代局部收敛。

牛顿迭代法及其变体

• 基本形式：\(x_{n+1}=x_n-\frac{f(x_n)}{f’(x_n)}\)。
• 含重根时：
  • 基本牛顿迭代局部线性收敛；
  • 修正形式 \(x_{n+1}=x_n-m\frac{f(x_n)}{f’(x_n)}\) 至少达到二阶收敛。

化简牛顿法与弦割法

• 化简牛顿法：固定 \(f’(x_0)\)，迭代 \(x_{n+1}=x_n-\frac{f(x_n)}{f’(x_0)}\)。
• 弦割法：用差商近似导数， \[ f’(x_n)\approx \frac{f(x_n)-f(x_{n-1})}{x_n-x_{n-1}},\quad x_{n+1}=x_n-\frac{f(x_n)(x_n-x_{n-1})}{f(x_n)-f(x_{n-1})}. \]

第三章 线性方程组的解法

迭代法

向量范数：

• \(\left\lVert x\right\rVert_p=\Big(\sum_{i=1}^{n} \lvert x_i \rvert^p \Big)^{1/p}\)
• \(\left\lVert x\right\rVert_{\infty}=\max_{1\le i \le n}\lvert x_i \rvert\)
• \(\left\lVert x\right\rVert_1=\sum_{i=1}^{n}\lvert x_i \rvert\)

矩阵范数：

• \(\left\lVert A\right\rVert_p=\max_{x\neq 0}\frac{\left\lVert Ax\right\rVert_p}{\left\lVert x\right\rVert_p}\)
• \(\left\lVert A\right\rVert_1=\max_{1\le j\le n}\sum_{i=1}^{n}\lvert a_{ij} \rvert\) （最大列和）
• \(\left\lVert A\right\rVert_{\infty}=\max_{1\le i\le n}\sum_{j=1}^{n}\lvert a_{ij} \rvert\) （最大行和）
• \(\left\lVert A\right\rVert_2=\sqrt{\lambda_{\max}}\)

常见迭代格式 \(x^{(k+1)}=Bx^{(k)}+g\)：

• Jacobi 法：\(B_J=-D^{-1}(L+U)=I-D^{-1}A, \quad g_J=D^{-1}b\)
• Gauss-Seidel 法：\(B_G=-(D+L)^{-1}U, \quad g_G=(D+L)^{-1}b\)

收敛判据：

• \(\rho(B) < 1\) 为充要条件；
• \(B\) 为严格对角占优矩阵或某一范数小于 1 可作为充分条件。

直接法

对线性方程组 \(Ax=b\)：

• LU 分解（Doolittle）：\(A=LU\)，将行变换记录在 \(L\)，得到上三角 \(U\)，最终求解 \(Ly=b\)、\(Ux=y\)。
• 改进平方根法（Cholesky）：\(A=LDL^{\mathsf T}\)，先解 \(Ly=b\)，再解 \(Dz=y\)，最后求 \(L^{\mathsf T}x=z\)。
• 平方根法：对正定对称矩阵求 \(A=LL^{\mathsf T}\)。
• 追赶法：针对三对角矩阵的高效解法，本质仍是 LU 分解流程。

第四章 插值与拟合

拉格朗日插值

\[ L(x)=\sum_{i=0}^{n} y_i \prod_{j=0,j\neq i}^{n} \frac{x-x_j}{x_i-x_j} \]

插值余项：

\[ R_n(x)=f(x)-p_n(x)=\frac{f^{(n+1)}(\xi)}{(n+1)!}\prod_{i=0}^{n}(x-x_i) \]

牛顿插值与差商

\[ N(x)=\sum_{i=0}^{n} f[x_0,x_1,\dots,x_i] \prod_{j=0}^{i-1}(x-x_j) \]

其中差商定义为：

• \(f[x_i]=f(x_i)\)
• \(f[x_i,x_{i+1}]=\frac{f(x_{i+1})-f(x_i)}{x_{i+1}-x_i}\)
• \(f[x_i,\dots,x_{i+k}]=\frac{f[x_{i+1},\dots,x_{i+k}]-f[x_i,\dots,x_{i+k-1}]}{x_{i+k}-x_i}\)

厄米特插值

通过同时匹配函数值与导数值构造插值多项式，可采用待定系数法求解。余项亦可视作将导数值点视为重复节点后应用经典公式。

最小二乘法

对于超定方程组 \(Ax=b\)，最小二乘解 \(\bar x\) 满足：

\[ A^{\mathsf T}A \bar x = A^{\mathsf T}b. \]

例如对 \(y = ae^{bx}\)，两边取对数得到 \(\ln y = \ln a + bx\)，可转化为线性方程组交由最小二乘求解。

第五章 数值积分

代数精度与截断误差

• 代数精度：若对所有次数不超过 \(m\) 的多项式成立，则称公式具有 \(m\) 次代数精度。
• 梯形公式截断误差：\(R(f) = -\frac{(b-a)^3}{12}f’’(\xi)\)
• Simpson 公式截断误差：\(R(f) = -\frac{(b-a)^5}{2880}f^{(4)}(\xi)\)

常见权系数：

梯形公式：

\[ T(f)=(b-a)\Big(\tfrac{1}{2}f(a)+\tfrac{1}{2}f(b)\Big) \]

Simpson 公式：

\[ S(f)=(b-a)\Big(\tfrac{1}{6}f(a)+\tfrac{4}{6}f\Big(\tfrac{a+b}{2}\Big)+\tfrac{1}{6}f(b)\Big). \]

复合梯形与复合 Simpson 公式：将区间等分为 \(n\) 份（\(h = \frac{b-a}{n}\)），分段应用并累加。

\[ R_{T_n}[f,h]=-\frac{(b-a)h^{2}}{12}f’’(\xi), \quad R_{S_n}[f,h]=-\frac{(b-a)h^{4}}{2880}f^{(4)}(\xi). \]

数值微分

两点公式：

• \(f’(x_0)=\frac{f(x_1)-f(x_0)}{h}\)（向前差商）
• \(f’(x_1)=\frac{f(x_1)-f(x_0)}{h}\)（向后差商）

三点公式：

• \(f’(x_0)=\frac{-3f(x_0)+4f(x_1)-f(x_2)}{2h}\)
• \(f’(x_1)=\frac{-f(x_0)+f(x_2)}{2h}\)（中心差商）
• \(f’(x_2)=\frac{f(x_0)-4f(x_1)+3f(x_2)}{2h}\)

第六章 微分方程数值解法

考虑初值问题

\[ \begin{cases} y’(x)=f(x,y),\
y(a)=y_0 \end{cases} \]

设步长为 \(h\)，常用方法包括：

• 欧拉法：\(y_{n+1}=y_n+h f(x_n,y_n)\)
• 隐式欧拉法：\(y_{n+1}=y_n+h f(x_{n+1},y_{n+1})\)
• 梯形公式：\(y_{n+1}=y_n+\frac{h}{2}\big(f(x_n,y_n)+f(x_{n+1},y_{n+1})\big)\)

• 改进欧拉法（预测-校正）：

  \[ \begin{cases} y_{n+1}^{(0)}=y_n+h f(x_n,y_n),\
  y_{n+1}=y_n+\frac{h}{2}\big(f(x_n,y_n)+f(x_{n+1},y_{n+1}^{(0)})\big). \end{cases} \]