Blog - 晨星博客

笔记代码: https://github.com/HenryJi529/NumericalAnalysis

误差

误差的大小和传播

来源与分类
1. 模型误差
2. 观测误差
3. 方法误差(截断误差)$\Leftarrow$求近似解
4. 舍入误差
传播与积累
1. 病态问题
2. 算法数值不稳定

误差与有效数字

绝对误差:
1. $e^* =x^ *-x$，
2. $|e^ * |$ 的上限记为 $\varepsilon^{*}$, 称为绝对误差限
相对误差:
1. $e_r^* = \frac{e^* }{x} = \frac{e^* }{x^* }$
2. $\varepsilon_r^* = \frac{\varepsilon^*}{|x^ *|}$ 相对误差上界:
有效数字
- 有效数字n$\Rightarrow$相对误差限 $$ \varepsilon_r^* \leq \frac{1}{2 a_1} \times 10^{-n+1} $$
- 相对误差限$\Rightarrow$有效数字 $$ \varepsilon_r^*=\frac{1}{2\left(a_1+1\right)} \times 10^{-n+1} $$

函数的误差估计

对于$y=f(x)$:

绝对误差:

\[ \left|e^* (y)\right| \approx\left|f^{\prime}\left(x^* \right)\right| \cdot\left|e^*(x)\right| \]
相对误差:

\[ \left|e_r^* (y)\right| \approx\left|\frac{x^* y^{\prime}\left(x^* \right)}{y\left(x^* \right)}\right| \cdot\left|e_r^*(x)\right| \]

运算注意事项

避免相近两数相减
避免小分母: 分母小会造成浮点溢出
避免大数吃小数(如: 从小到大相加)
先化简，再计算: 减少步骤，避免误差积累
选用稳定的算法

插值法

多项式插值

待定系数法

拉格朗日多项式插值

\[ L_n(x)=y_0 l_0(x)+y_1 l_1(x)+\cdots+y_n l_n(x) \]

拉格朗日基函数:

\[ l_i\left(x_j\right)=\delta_{i j} \text{[Kronecker Delta]} \Rightarrow l_i(x)=\prod_{\substack{j \neq i \\ j=0}}^n \frac{\left(x-x_j\right)}{\left(x_i-x_j\right)} \]

易得，基函数满足:

\[ \sum_i l_i(x)=1 \]

余项:

\[ R_n(x)=K(x) \prod_{i=0}^n\left(x-x_i\right) \]

构造$\varphi(t)$:

\[ \varphi(t)=R_n(t)-K(x) \prod_{i=0}^n\left(t-x_i\right) \]

由于:

\[ \varphi(t) \text { 有 } n+2 \text { 个不同的零点 } x_0 \ldots x_n x \Rightarrow \varphi^{(n+1)}\left(\xi_x\right)=0, \xi_x \in(a, b) \]

\[ \Rightarrow R_n^{(n+1)}\left(\xi_x\right)-K(x)(n+1) ! = f^{(n+1)}\left(\xi_x\right)-L_n^{(n+1)}\left(\xi_x\right)-K(x)(n+1) !=0 \Rightarrow K(x)=\frac{f^{(n+1)}\left(\xi_x\right)}{(n+1) !} \]

可得:

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

缺点: 增加或减少节点时，基函数都需要重新计算

牛顿插值

\[ p_n(x)=p_{n-1}(x)+u_n(x) \]

差商:
1. 表达式:
  - 零阶:
    
    \[ f[x_0] = f(x_0) \]
  - 一阶:
    
    \[ f\left[x_i, x_j\right]=\frac{f\left(x_i\right)-f\left(x_j\right)}{x_i-x_j} \quad\left(i \neq j, x_i \neq x_j\right) \]
  - 二阶:
    
    \[ f\left[x_i, x_j, x_k\right]=\frac{f\left[x_i, x_j\right]-f\left[x_j, x_k\right]}{x_i-x_k} \quad(i \neq k) \]
  - k+1阶:
    
    \[ \begin{aligned} f\left[x_0, \ldots, x_{k+1}\right] & =\frac{f\left[x_0, x_1, \ldots, x_k\right]-f\left[x_1, \ldots, x_k, x_{k+1}\right]}{x_0-x_{k+1}} \\ & =\frac{f\left[x_0, \ldots, x_{k-1}, x_k\right]-f\left[x_0, \ldots, x_{k-1}, x_{k+1}\right]}{x_k-x_{k+1}} \end{aligned} \]
2. 性质:
  1. 可以表示为函数值的线性组合
    
    \[ f\left[x_0, \cdots, x_k\right]=\sum_{j=0}^k \frac{f\left(x_j\right)}{\left(x_j-x_0\right) \cdots\left(x_j-x_{j-1}\right)\left(x_j-x_{j+1}\right) \cdots\left(x_j-x_k\right)}=\sum_{j=0}^k \frac{f\left(x_j\right)}{\omega_{k+1}^{\prime}\left(x_j\right)} \]
    
    其中: $\omega_{k+1}(x)=\prod_{i=0}^k\left(x-x_i\right)$
  2. 差商具有对称性
    
    \[ f\left[x_0, x_1, \cdots, x_k\right]=f\left[x_1, x_0, x_2 \cdots, x_k\right]=\cdots=f\left[x_1, \cdots, x_k, x_0\right] \]
  3. n阶差商与n阶导数的关系
    
    \[ f\left[x_0, x_1 \cdots, x_n\right]=\frac{f^{(n)}(\xi)}{n !} \quad \xi \in[a, b] \]
  4. 若 $f(x)$ 是 $n$ 次多项式, 则其 $\boldsymbol{k}$ 阶差商 $f\left[x_0, x_1 \cdots, x_{k-1}, x\right]$ 当 $k \leq n$ 时是一个 $n-k$ 次多项式, 而当 $k>n$ 时恒为零.
3. 计算:
插值公式

基函数:

\[ \begin{aligned} & \varphi_0(x)=1 \\ & \varphi_{i+1}(x)=\left(x-x_i\right) \varphi_i(x), i=0,1, \cdots, n-1 \end{aligned} \]

插值公式:

\[ N_n(x)=f\left(x_0\right)+f\left[x_0, x_1\right]\left(x-x_0\right)+ f\left[x_0, x_1, x_2\right]\left(x-x_0\right)\left(x-x_1\right)+\cdots \]

余项:

由唯一性可知 $N_n(x) \equiv L_n(x)$, 只是算法不同, 故其余项也相同，即

\[ f\left[x, x_0, \ldots, x_n\right] \omega_{n+1}(x)=\frac{f^{(n+1)}\left(\xi_x\right)}{(n+1) !} \omega_{n+1}(x) \]

等距节点公式: 更适合通过差分编程实现

埃尔米特插值

不仅要求函数值重合, 而且要求若干阶导数也重合。即: 要求插值函数 $\varphi(x)$ 满足

$\varphi\left(x_i\right)=f\left(x_i\right)$, $\varphi^{\prime}\left(x_i\right)=f^{\prime}\left(x_i\right)$, $\ldots$, $\phi^{\left(m_i\right)}\left(x_i\right)=f^{\left(m_i\right)}\left(x_i\right)$.

$N$ 个条件可以确定 $N-1$ 阶多项式。
要求在1个节点 $x_0$ 处直到 $m_0$ 阶导数都重合的插值多项式即为Taylor多项式

\[ \varphi(x)=f\left(x_0\right)+f^{\prime}\left(x_0\right)\left(x-x_0\right)+\ldots+\frac{f^{\left(m_0\right)}\left(x_0\right)}{m_{0} !}\left(x-x_0\right)^{m_0} \]

其余项为 $R(x)=f(x)-\varphi(x)=\frac{f^{\left(m_0+1\right)}(\xi)}{\left(m_0+1\right) !}\left(x-x_0\right)^{\left(m_0+1\right)}$

思路:

转换成牛顿差值
转换成拉格朗日插值
阶数小时可以直接待定系数法

分段低次插值

在区间$[a, b]$上用插值值多项式$P_n(x)$近似函数$f(x)$, 是否$P_n(x)$的次数越高, 逼近效果越好呢, 回答是否定的。

由于次数越高计算工作量也越大, 积累误差也越大(龙格现象); 在整个区间上作个高次多项式, 当局部插值节点的值有微小误差时, 就可能引起整个区间上函数值的较大变化, 使计算不稳定。

本站服务

误差