计算方法期末复习

mengnankkzhou2025-06-182025-06-26

计算方法——公式汇总

绝对误差

Δ=∣x∗−x∣\Delta = \bigl|x^* - x\bigr|
相对误差

δ=∣x∗−x∣∣x∗∣\delta = \frac{\bigl|x^ - x\bigr|}{\lvert x^\rvert}
四舍五入误差限（保留到第 nn 位有效数字）

Δmax⁡=12×10−n,δmax⁡=Δmax⁡∣x∣\Delta_{\max} = \tfrac12 \times 10^{-n}, \quad \delta_{\max} = \frac{\Delta_{\max}}{\lvert x\rvert}
有效数字与相对误差关系
若已知相对误差 ε\varepsilon，则有效数字位数 nn 满足

12 10−(n−1) ≤ ε < 12 10−(n−2).\frac12 \,10^{-(n-1)} \;\le\; \varepsilon \;<\; \frac12 \,10^{-(n-2)}.
误差传播
- 乘除法：
  
  δ(f(x1,…,xk))≈∑i=1kδ(xi).\delta\bigl(f(x_1,\dots,x_k)\bigr) \approx \sum_{i=1}^k \delta(x_i).
- 加减法：
  
  Δ(f(x1,…,xk))≈∑i=1kΔ(xi).\Delta\bigl(f(x_1,\dots,x_k)\bigr) \approx \sum_{i=1}^k \Delta(x_i).
- 例：若 A=LWA = L W，则
  
  Δ(A) ≤ ∣W∣ Δ(L)+∣L∣ Δ(W),δ(A)≈δ(L)+δ(W).\Delta(A) \;\le\; |W|\,\Delta(L) + |L|\,\Delta(W), \quad \delta(A)\approx\delta(L)+\delta(W).

根存在性
若 ff 在 [a,b][a,b] 连续且

f(a) f(b)<0,f(a)\,f(b) < 0,

则 (a,b)(a,b) 内至少有一实根。
二分法误差界

∣xn−x∗∣≤b−a2n,n≥⌈log⁡2b−aε⌉.\bigl|x_n - x^*\bigr| \le \frac{b-a}{2^n}, \quad n \ge \bigl\lceil \log_2\tfrac{b-a}{\varepsilon}\bigr\rceil.
不动点迭代
写成 x=g(x)x = g(x)，迭代

xn+1=g(xn),x_{n+1} = g(x_n),

收敛条件：∣g′(x)∣<1\lvert g’(x)\rvert < 1（根附近）。
牛顿法

xn+1=xn−f(xn)f′(xn).x_{n+1} = x_n - \frac{f(x_n)}{f’(x_n)}.

如为重根 mm，可修正为

xn+1=xn−m f(xn)f′(xn).x_{n+1} = x_n - m\,\frac{f(x_n)}{f’(x_n)}.
割线法

xn+1=xn−f(xn) xn−xn−1f(xn)−f(xn−1).x_{n+1} = x_n - f(x_n)\, \frac{x_n - x_{n-1}}{f(x_n) - f(x_{n-1})}.

高斯消去法
增广矩阵 [A∣b][A\mid b] → 逐列消元 → 回代求解。
列主元策略
每列选绝对值最大的元素作为主元，交换后再消元。
Jacobi 迭代
令 A=D+L+UA=D+L+U，则

xi(k+1)=1aii(bi−∑j≠iaij xj(k)).x_i^{(k+1)} = \frac{1}{a_{ii}} \Bigl(b_i - \sum_{j\ne i} a_{ij}\,x_j^{(k)}\Bigr).
Gauss–Seidel 迭代

xi(k+1)=1aii(bi−∑jiaij xj(k)).x_i^{(k+1)} = \frac{1}{a_{ii}} \Bigl( b_i - \sum_{ji} a_{ij}\,x_j^{(k)} \Bigr).
SOR（超松弛方法）

xi(k+1)=(1−ω) xi(k)+ωaii(bi−∑jiaij xj(k)),x_i^{(k+1)} = (1-\omega)\,x_i^{(k)} + \frac{\omega}{a_{ii}} \Bigl( b_i - \sum_{ji} a_{ij}\,x_j^{(k)} \Bigr),

其中 1<ω<21<\omega<2。

拉格朗日插值
给定 (x0,y0),…,(xn,yn)(x_0,y_0),\dots,(x_n,y_n)，

L(x)=∑j=0nyj ℓj(x),ℓj(x)=∏i=0, i≠jnx−xixj−xi.L(x) = \sum_{j=0}^n y_j\,\ell_j(x), \quad \ell_j(x) = \prod_{i=0,\,i\ne j}^n \frac{x - x_i}{x_j - x_i}.
牛顿插值
利用差商，

Pn(x)=f[x0]+f[x0,x1] (x−x0)+⋯+f[x0,…,xn] ∏i=0n−1(x−xi).P_n(x) = f[x_0] + f[x_0,x_1]\,(x-x_0) + \cdots + f[x_0,\dots,x_n]\,\prod_{i=0}^{n-1}(x-x_i).
插值余项

Rn+1(x)=f(x)−Pn(x)=f(n+1)(ξ)(n+1)!∏i=0n(x−xi),ξ∈[a,b].R_{n+1}(x) = f(x) - P_n(x) = \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{i=0}^n (x - x_i),\quad \xi\in[a,b].

一元线性拟合（直线）
设 y=ax+by = a x + b，构造正则方程：

{a∑xi2+b∑xi=∑xiyi,a∑xi+nb=∑yi.\begin{cases} a\sum x_i^2 + b\sum x_i = \sum x_i y_i,\ a\sum x_i + nb = \sum y_i. \end{cases}
二次多项式拟合
设 y=a0+a1x+a2x2y = a_0 + a_1 x + a_2 x^2，正则方程：

{na0+(∑xi)a1+(∑xi2)a2=∑yi,(∑xi)a0+(∑xi2)a1+(∑xi3)a2=∑xiyi,(∑xi2)a0+(∑xi3)a1+(∑xi4)a2=∑xi2yi.\begin{cases} n a_0 + (\sum x_i)a_1 + (\sum x_i^2)a_2 = \sum y_i,\ (\sum x_i)a_0 + (\sum x_i^2)a_1 + (\sum x_i^3)a_2 = \sum x_i y_i,\ (\sum x_i^2)a_0 + (\sum x_i^3)a_1 + (\sum x_i^4)a_2 = \sum x_i^2 y_i. \end{cases}
加权最小二乘
使加权残差平方和最小：

min⁡∑iwi(yi−P(xi))2.\min \sum_{i} w_i \bigl(y_i - P(x_i)\bigr)^2.