留痕数值分析

SHEET

公式速查

可打印。考前十分钟按顺序扫:先误差与有效数字,再插值公式,最后样条方程。公式下的条件同样要背。

本页目录

一、误差与有效数字

绝对误差与误差限

e∗=x∗−x,∣e∗∣≤ε∗  ⟺  x∈[x∗−ε∗, x∗+ε∗]e^*=x^*-x,\qquad \lvert e^*\rvert\le\varepsilon^*\;\Longleftrightarrow\;x\in[x^*-\varepsilon^*,\ x^*+\varepsilon^*]

相对误差以真值为分母;课件估计误差限时以近似值归一化

er∗=e∗x,εr∗=ε∗∣x∗∣e_r^*=\frac{e^*}{x},\qquad \varepsilon_r^*=\frac{\varepsilon^*}{\lvert x^*\rvert}

按真值计算的严格上界(∣x∗∣>ε∗\lvert x^*\rvert>\varepsilon^* 时):∣er∗∣≤ε∗/(∣x∗∣−ε∗)\lvert e_r^*\rvert\le\varepsilon^*/(\lvert x^*\rvert-\varepsilon^*)。

有效数字:写成 x∗=±0.a1a2⋯an×10mx^*=\pm0.a_1a_2\cdots a_n\times10^m(a1≠0a_1\ne0),若

∣x−x∗∣≤0.5×10m−n\lvert x-x^*\rvert\le0.5\times10^{m-n}

则 x∗x^* 有 nn 位有效数字。定理 1.1:

εr∗≤12a1×101−n\varepsilon_r^*\le\frac{1}{2a_1}\times10^{1-n}

判定顺序:定 mm → 定 a1a_1 → 数位数 nn → 比 0.5×10m−n0.5\times10^{m-n}。反解:让相对误差的估计上界不超过题设容许值,解出所需位数 nn,向上取整。

二、误差传播

ε(x1±x2)=ε1+ε2\varepsilon(x_1\pm x_2)=\varepsilon_1+\varepsilon_2
ε(x1x2)≈∣x2∣ε1+∣x1∣ε2,εr(x1x2)≈εr1+εr2\varepsilon(x_1x_2)\approx\lvert x_2\rvert\varepsilon_1+\lvert x_1\rvert\varepsilon_2,\qquad \varepsilon_r(x_1x_2)\approx\varepsilon_{r1}+\varepsilon_{r2}
ε ⁣(x1x2)≈∣x2∣ε1+∣x1∣ε2∣x2∣2,εr ⁣(x1x2)≈εr1+εr2\varepsilon\!\left(\frac{x_1}{x_2}\right)\approx\frac{\lvert x_2\rvert\varepsilon_1+\lvert x_1\rvert\varepsilon_2}{\lvert x_2\rvert^2},\qquad \varepsilon_r\!\left(\frac{x_1}{x_2}\right)\approx\varepsilon_{r1}+\varepsilon_{r2}

一元函数与条件数

ε(f(x∗))≈∣f′(x∗)∣ε(x∗),εr(f)≈∣x∗f′(x∗)f(x∗)∣εr(x∗)\varepsilon(f(x^*))\approx\lvert f'(x^*)\rvert\varepsilon(x^*),\qquad \varepsilon_r(f)\approx\left\lvert\frac{x^*f'(x^*)}{f(x^*)}\right\rvert\varepsilon_r(x^*)

三、数值稳定性

四条原则:避免相近数相减;避免大数吃小数;避免除以很小的数;减少运算次数、选稳定递推方向。

x+1−x=1x+1+x,1x−1x+1=1x(x+1)\sqrt{x+1}-\sqrt{x}=\frac{1}{\sqrt{x+1}+\sqrt{x}},\qquad \frac{1}{x}-\frac{1}{x+1}=\frac{1}{x(x+1)}
1−cos⁡x=2sin⁡2x2,ln⁡(x+1)−ln⁡x=ln⁡ ⁣(1+1x)1-\cos x=2\sin^2\frac{x}{2},\qquad \ln(x+1)-\ln x=\ln\!\left(1+\frac{1}{x}\right)

秦九韶:p(x)=(⋯((anx+an−1)x+an−2)x+⋯+a1)x+a0p(x)=(\cdots((a_nx+a_{n-1})x+a_{n-2})x+\cdots+a_1)x+a_0,nn 次乘法。

递推判据:若 en≈c en−1e_n\approx c\,e_{n-1},∣c∣>1\lvert c\rvert>1 正向不稳定,反向稳定;∣c∣<1\lvert c\rvert<1 相反。

四、插值的存在唯一性

n+1n+1 个互异节点上,次数不超过 nn 的插值多项式存在且唯一(范德蒙德行列式 ∏j<i(xi−xj)≠0\prod_{j<i}(x_i-x_j)\ne0)。

五、拉格朗日插值

li(x)=∏j≠ix−xjxi−xj,Ln(x)=∑i=0nf(xi)li(x)l_i(x)=\prod_{j\ne i}\frac{x-x_j}{x_i-x_j},\qquad L_n(x)=\sum_{i=0}^{n}f(x_i)l_i(x)

余项与误差限

Rn(x)=f(n+1)(ξ)(n+1)!ωn+1(x),∣Rn∣≤Mn+1(n+1)!∣ωn+1(x)∣R_n(x)=\frac{f^{(n+1)}(\xi)}{(n+1)!}\omega_{n+1}(x),\qquad \lvert R_n\rvert\le\frac{M_{n+1}}{(n+1)!}\lvert\omega_{n+1}(x)\rvert
ωn+1(x)=∏i=0n(x−xi),Mn+1=max⁡∣f(n+1)∣\omega_{n+1}(x)=\prod_{i=0}^{n}(x-x_i),\qquad M_{n+1}=\max\lvert f^{(n+1)}\rvert

六、牛顿插值

差商

f[xi,xj]=f(xj)−f(xi)xj−xi,f[x0,…,xk]=f[x1,…,xk]−f[x0,…,xk−1]xk−x0f[x_i,x_j]=\frac{f(x_j)-f(x_i)}{x_j-x_i},\qquad f[x_0,\ldots,x_k]=\frac{f[x_1,\ldots,x_k]-f[x_0,\ldots,x_{k-1}]}{x_k-x_0}

性质:对称;f[x0,…,xk]=f(k)(ξ)/k!f[x_0,\ldots,x_k]=f^{(k)}(\xi)/k!;mm 次多项式的 mm 阶差商为首项系数,更高阶为 00。

Nn(x)=f(x0)+∑k=1nf[x0,…,xk]∏i=0k−1(x−xi)N_n(x)=f(x_0)+\sum_{k=1}^{n}f[x_0,\ldots,x_k]\prod_{i=0}^{k-1}(x-x_i)

差分与等距节点

Δfi=fi+1−fi,f[x0,…,xk]=Δkf0k! hk\Delta f_i=f_{i+1}-f_i,\qquad f[x_0,\ldots,x_k]=\frac{\Delta^kf_0}{k!\,h^k}
Nn(x0+th)=∑k=0n(tk)Δkf0,Nn(xn+th)=∑k=0n(t+k−1k)∇kfnN_n(x_0+th)=\sum_{k=0}^{n}\binom{t}{k}\Delta^kf_0,\qquad N_n(x_n+th)=\sum_{k=0}^{n}\binom{t+k-1}{k}\nabla^kf_n

七、埃尔米特插值

n+1n+1 个节点、函数值与一阶导数共 2n+22n+2 个条件,确定次数不超过 2n+12n+1 的 H2n+1H_{2n+1}。

H2n+1=∑i=0n[f(xi)αi+f′(xi)βi]H_{2n+1}=\sum_{i=0}^{n}\left[f(x_i)\alpha_i+f'(x_i)\beta_i\right]
αi=[1−2li′(xi)(x−xi)]li2,βi=(x−xi)li2,li′(xi)=∑j≠i1xi−xj\alpha_i=[1-2l_i'(x_i)(x-x_i)]l_i^2,\qquad \beta_i=(x-x_i)l_i^2,\qquad l_i'(x_i)=\sum_{j\ne i}\frac{1}{x_i-x_j}
R2n+1(x)=f(2n+2)(ξ)(2n+2)!ωn+12(x)R_{2n+1}(x)=\frac{f^{(2n+2)}(\xi)}{(2n+2)!}\omega_{n+1}^2(x)

重节点差商表:节点写两遍,重复节点之间的一阶差商填导数。

八、分段插值与样条

分段线性:C0C^0,

∣f−Lh∣≤h28max⁡∣f′′∣=O(h2)\lvert f-L_h\rvert\le\frac{h^2}{8}\max\lvert f''\rvert=O(h^2)

三次样条:S∈C2[a,b]S\in C^2[a,b],每段三次,S(xi)=fiS(x_i)=f_i;共 4n4n 个未知量,需两个边界条件。

三弯矩法:Mi=S′′(xi)M_i=S''(x_i),hi=xi−xi−1h_i=x_i-x_{i-1},

μiMi−1+2Mi+λiMi+1=di,i=1,…,n−1\mu_iM_{i-1}+2M_i+\lambda_iM_{i+1}=d_i,\qquad i=1,\ldots,n-1
μi=hihi+hi+1,λi=1−μi,di=6f[xi−1,xi,xi+1]\mu_i=\frac{h_i}{h_i+h_{i+1}},\quad\lambda_i=1-\mu_i,\quad d_i=6f[x_{i-1},x_i,x_{i+1}]

边界:弯矩 M0,MnM_0,M_n 已知(自然边界 M0=Mn=0M_0=M_n=0);转角 S′(x0)=m0S'(x_0)=m_0,S′(xn)=mnS'(x_n)=m_n;周期要求 f0=fnf_0=f_n,并令 S′(x0+)=S′(xn−)S'(x_0^+)=S'(x_n^-),S′′(x0+)=S′′(xn−)S''(x_0^+)=S''(x_n^-)。

解出弯矩后

S(x)=Mi−1(xi−x)3+Mi(x−xi−1)36hi+(fi−1−Mi−1hi26)xi−xhi+(fi−Mihi26)x−xi−1hiS(x)=\frac{M_{i-1}(x_i-x)^3+M_i(x-x_{i-1})^3}{6h_i} +\left(f_{i-1}-\frac{M_{i-1}h_i^2}{6}\right)\frac{x_i-x}{h_i} +\left(f_i-\frac{M_ih_i^2}{6}\right)\frac{x-x_{i-1}}{h_i}
弯矩和转角边界:三对角方程组,可用追赶法,O(n)O(n)。周期边界:通常是循环三对角方程组,不能直接用普通追赶法。