均差

均差（Divided differences）是递归除法过程。在数值分析中，可用于计算牛顿多项式形式的多项式插值的系数。在微积分中，均差与导数一起合称差商，是对函数在一个区间内的平均变化率的测量[1][2][3]. (维基百科)

说实话我不知道为什么除维基百科外其他地方都是直接称为差商,在这里我还是采用维基百科的说法”均差”

给出经过若干个数据点$(xi,f(x_i))$的函数$f(x)$，对于两个数据点$x_i,x_j$，其一阶均差$f[x_i,x_j]=\frac{f(x_i)-f(x_j)}{x_i-x_j}$；对于三个数据点，其二阶均差$f[x_0,x_1,x_2]=\frac{f[x_0,x_1]-f[x_1,x_2]}{x_0-x_2}$…对于$(n+1)$个数据点,其$n$阶均差$f[x_0,x_1…x_{n-1},x_{n}]=\frac{f[x_0,x_1…x_{n-1}]-f[x_1,x_2…x_n]}{x_0-x_n}$(Chang, 2014).

在这里我们默认均差都为前向均差，所以我们需要注意减法的方向

性质

性质1:

$f[x_0,x_1…x_k]= \sum_{i=0}^k \frac{f(x_i)}{(x_i-x_0)(x_i-x_1)…(x_i-x_{i-1})(x_i-x_{x+1})…(x-x_k)}$ $(*)$

这个性质可以对高阶均差进行更方便的计算，在牛顿插值法中就可以运用这种计算

• 证明

  首先我们需要记住定义式$f[x_0,x_1…x_{k-1},x_{k}]=\frac{f[x_0,x_1…x_{k-1}]-f[x_1,x_2…x_k]}{x_0-x_k}$，接着我们使用数学归纳法验证这条性质的正确性:

  <1>当$n=1$时,即一阶均差,根据定义$f[x_0,x_1]=\frac{f(x_0)-f(x_1)}{x_0-x_1}$

  此时根据性质$1$,$f[x_0,x_1]=\frac{f(x_0)}{(x_0-x_1)}+\frac{f(x_1)}{(x_1-x_0)}=\frac{f(x_0)-f(x_1)}{x_0-x_1}$,等式成立

  <2>设$n=k$阶均差时 (*)式成立

  则当$n=k+1$时

  • 等式左边记为(1)式$f[x_0…x_{k+1}]=\frac{f[x_0…x_k]-f[x_1..x_{k+1}]}{x_0-x_{k+1}}=\frac{\sum_{i=0}^{k}\frac{f(x_i)}{(x_i-x_0)…(x_i-x_{i-1})(x_i-x_{i+1})…(x_i-x_{k})}-\sum_{i=1}^{k+1}\frac{f(x_i)}{(x_i-x_1)…(x_i-x_{i-1})(x_i-x_{i+1})…(x_i-x_{k+1})}}{x_0-x_{k+1}}$

  • 等式右边记为(2)式

    $f[x_0…x_{k+1}]=\sum_{i=0}^{k+1} \frac{f(x_i)}{(x_i-x_0)…(x_i-x_{i-1})(x_i-x_{i+1})…(x_i-x_k)}$

    观察(1)式中的的两个和式,分成三个部分解决证明其与(2)式相等

  • 对于$i=0$时, 此时只有左边的和式有$\frac{f(x_0)}{(x_0-x_1)…(x_0-x_k)(x_0-x_{k+1})}$(已经把大分母$x_0-x_{k+1}$除下来)。显然等于(2)式 $i=0$时的式子

  • 对于$i=k+1$时，此时只有右边的和式中有$-\frac{f(x_{k+1})}{(x_0-x_{k+1})(x_{k+1}-x_{1})…(x_{k+1}-x_{k})}=\frac{f(x_{k+1})}{(x_{k+1}-x_0)(x_{k+1}-x_{1})…(x_{k+1}-x_{k})}$

    (也是已经把大分母除下来了)。显然等于(2)式$i=k+1$时的式子

  • 对于$1<=i<=k$时，我们对于其中的任意一项进行考虑，

    左边和式$(\frac{f(x_i)}{(x_i-x_0)(x_i-x_1)…(x_i-x_{i-1})(x_i-x_{i+1})…(x_i-x_k)}-\frac{f(x_i)}{(x_i-x_1)…(x_i-x_{i-1})(x_i-x_{i+1})..(x_i-x_k)(x_i-x_{k+1})})(\frac{1}{x_0-x_{k+1}})$

    $=(\frac{f(x_i)((x_i-x_{k+1})-(x_i-x_0))}{(x_i-x_0)(x_i-x_1)…(x_i-x_{i-1})(x_i-x_{i+1})…(x_i-x_k)(x_i-x_{k+1})})(\frac{1}{x_0-x_{k+1}})$

    $=\frac{f(x_i)}{(x_i-x_0)(x_i-x_1)…(x_i-x_{i-1})(x_i-x_{i+1})…(x_i-x_k)(x_i-x_{k+1})}$

    显然对于(2)式中和式任意的第$i$项($1<=i<=k$)

    因此$k+1$阶均差依旧满足此性质

    由<1><2>知该性质成立

性质2

调整点的顺序,均差不会改变。称其具有轮换对称性 (Chang, 2014)

$e.g.$ $f[x_0,x_1,x_2]=f[x_1,f_2,x_0]$

References

1. 维基百科, 均差 , from 维基百科 on website,

   ​ retrieved from April/04/2019, https://zh.wikipedia.org/wiki/%E5%9D%87%E5%B7%AE

2. Leon Chang (2014) , Newton插值法 , from Leon’s Blog on website,

   ​ retrieved from Dec/06/2014, http://leonfocus.github.io/newton-interpolation/

差分

咕