均差

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

均差也是一种算法，查尔斯·巴贝奇的差分机，是他在1822年发表的论文中提出的一种早期的机械计算机，在历史上意图用来计算对数表和三角函数表，它设计在其运算中使用这个算法^[4]。

定义[编辑]

给定n+1个数据点

<math>(x_0, y_0),\ldots,(x_{n}, y_{n})</math>

定义前向均差为：

<math>\begin{align}

\mathopen[y_\nu] &= y_\nu, \quad \nu \in \{ 0,\ldots,n\} \\
\mathopen[y_\nu,\ldots,y_{\nu+j}] &= \frac{[y_{\nu+1},\ldots , y_{\nu+j}] - [y_{\nu},\ldots , y_{\nu+j-1}]}{x_{\nu+j}-x_\nu}, \quad \nu\in\{0,\ldots,n-j\},\ j\in\{1,\ldots,n\} \\

\end{align}</math>

定义后向均差为：

<math>\begin{align}

\mathopen[y_\nu] &= y_{\nu},\quad \nu \in \{ 0,\ldots,n\} \\
\mathopen[y_\nu,\ldots,y_{\nu-j}] &= \frac{[y_\nu,\ldots , y_{\nu-j+1}] - [y_{\nu-1},\ldots , y_{\nu-j}]}{x_\nu - x_{\nu-j}}, \quad \nu\in\{j,\ldots,n\},\ j\in\{1,\ldots,n\} \\

\end{align}</math>

表示法[编辑]

假定数据点给出为函数 ƒ，

<math>(x_0, f(x_0)),\ldots,(x_{n}, f(x_{n}))</math>

其均差可以写为：

<math>\begin{align}

f[x_\nu] &= f(x_{\nu}), \qquad \nu \in \{ 0,\ldots,n \} \\
f[x_\nu,\ldots,x_{\nu+j}] &= \frac{f[x_{\nu+1},\ldots , x_{\nu+j}] - f[x_\nu,\ldots , x_{\nu+j-1}]}{x_{\nu+j}-x_\nu}, \quad \nu\in\{0,\ldots,n-j\},\ j\in\{1,\ldots,n\}

\end{align}</math>

对函数 ƒ 在节点 x₀, ..., x_n 上的均差还有其他表示法，如：

<math>\begin{matrix}

\mathopen [x_0,\ldots,x_n]f \\

\mathopen [x_0,\ldots,x_n;f] \\ \mathopen D[x_0,\ldots,x_n]f \\ \end{matrix}</math>

例子[编辑]

给定ν=0：

<math>

\begin{align}

 \mathopen[y_0] &= y_0 \\
 \mathopen[y_0,y_1] &= \frac{y_1-y_0}{x_1-x_0} \\
 \mathopen[y_0,y_1,y_2] &= \frac{\mathopen[y_1,y_2]-\mathopen[y_0,y_1]}{x_2-x_0} \\
 \mathopen[y_0,y_1,y_2,y_3] &= \frac{\mathopen[y_1,y_2,y_3]-\mathopen[y_0,y_1,y_2]}{x_3-x_0} \\
 \mathopen[y_0,y_1,\dots,y_n] &= \frac{\mathopen[y_1,y_2,\dots,y_n]-\mathopen[y_0,y_1,\dots,y_{n-1}]}{x_n-x_0}

\end{align} </math>

为了使涉及的递归过程更加清楚，以列表形式展示均差的计算过程^[5]：

<math>

\begin{matrix} x_0 & [y_0] = y_0 & & & \\

       &       & [y_0,y_1] &               & \\

x_1 & [y_1] = y_1 & & [y_0,y_1,y_2] & \\

       &       & [y_1,y_2] &               & [y_0,y_1,y_2,y_3]\\

x_2 & [y_2] = y_2 & & [y_1,y_2,y_3] & \\

       &       & [y_2,y_3] &               & \\

x_3 & [y_3] = y_3 & & & \\ \end{matrix} </math>

展开形式[编辑]

用数学归纳法可证明^[6]：

<math>

\begin{align} \mathopen[y_0] &= y_0 \\ \mathopen[y_0,y_1] &= \frac{y_0}{x_0-x_1} + \frac{y_1}{x_1-x_0} \\ \mathopen[y_0,y_1,y_2] &= \frac{y_0}{(x_0-x_1)(x_0-x_2)} + \frac{y_1}{(x_1-x_0)(x_1-x_2)} + \frac{y_2}{(x_2-x_0)(x_2-x_1)} \\ \mathopen[y_0, y_1,\dots, y_n] &=\sum_{j=0}^{n} \frac{y_j}{\prod_{k=0,\, k\neq j}^{n} (x_j-x_k)} \\ \end{align} </math> 此公式体现了均差的对称性质。^[7]故可推知：任意调换数据点次序，其值不变。^[8]

性质[编辑]

对称性：若<math>\sigma : \{0, \dots, n\} \to \{0, \dots, n\}</math>是一个排列则

<math>f[x_0, \dots, x_n] = f[x_{\sigma(0)}, \dots, x_{\sigma(n)}]</math>

线性：

<math>\begin{align}

(f+g)[x_0,\dots,x_n] &= f[x_0,\dots,x_n] + g[x_0,\dots,x_n] \\ (\lambda\cdot f)[x_0,\dots,x_n] &= \lambda\cdot f[x_0,\dots,x_n] \\ \end{align}</math>

莱布尼茨法则（英语：General Leibniz rule）：

均差中值定理（英语：Mean value theorem (divided differences)）：

<math> \exists \xi \in (\min\{x_0,\dots,x_n\},\max\{x_0,\dots,x_n\}) \quad f[x_0,\dots,x_n] = \frac{f^{(n)}(\xi)}{n!} </math>

等价定义[编辑]

通过对换 n 阶均差中(x₀,y₀)与(x_n-1,y_n-1)，可得到等价定义：

<math>

\begin{align}

 \mathopen[y_0,y_1,\dots,y_{n-1},y_n] &= \frac{\mathopen[y_1,y_2,\dots,y_n]-\mathopen[y_0,y_1,\dots,y_{n-1}]}{x_n-x_0} \\
 &= \frac{\mathopen[y_1,\dots,y_{n-2},y_0,y_n]-\mathopen[y_{n-1},y_1,\dots,y_{n-2},y_0]}{x_n-x_{n-1}} \\
 &= \frac{\mathopen[y_0,\dots,y_{n-2},y_n]-\mathopen[y_0,y_1,\dots,y_{n-1}]}{x_n-x_{n-1}} \\

\end{align} </math> 这个定义有着不同的计算次序：

<math>

\begin{align}

 \mathopen[y_0] &= y_0 \\
 \mathopen[y_0,y_1] &= \frac{y_1-y_0}{x_1-x_0} \\
 \mathopen[y_0,y_1,y_2] &=  \frac{\mathopen[y_0,y_2]-\mathopen[y_0,y_1]}{x_2-x_1} \\
 \mathopen[y_0,y_1,y_2,y_3] &= \frac{\mathopen[y_0,y_1,y_3]-\mathopen[y_0,y_1,y_2]}{x_3-x_2} \\
 \mathopen[y_0,y_1,\dots,y_n] &= \frac{\mathopen[y_0,\dots,y_{n-2},y_n]-\mathopen[y_0,y_1,\dots,y_{n-1}]}{x_n-x_{n-1}} \\
\end{align}

</math> 以列表形式展示这个定义下均差的计算过程^[9]：

<math>

\begin{matrix} x_0 & [y_0] = y_0 & & & \\

       &       & [y_0,y_1] &               & \\

x_1 & [y_1] = y_1 & & [y_0,y_1,y_2] & \\

       &       & [y_0,y_2] &               & [y_0,y_1,y_2,y_3]\\

x_2 & [y_2] = y_2 & & [y_0,y_1,y_3] & \\

       &       & [y_0,y_3] &               & \\

x_3 & [y_3] = y_3 & & & \\ \end{matrix} </math>

牛顿插值法[编辑]

File:Principia1846-466.png

《自然哲学的数学原理》的第三编“宇宙体系”的引理五的图例。这里在横坐标上有6个点H,I,K,L,M,N，对应着6个值A,B,C,D,E,F，生成一个多项式函数对这6个点上有对应的6个值，计算任意点S对应的值R。牛顿给出了间距为单位值和任意值的两种情况。

牛顿插值公式，得名于伊萨克·牛顿爵士，最早发表为他在1687年出版的《自然哲学的数学原理》中第三编“宇宙体系”的引理五，此前詹姆斯·格雷果里于1670年和牛顿于1676年已经分别独立得出这个成果。一般称其为连续泰勒展开的离散对应。

使用均差的牛顿插值法为^[10]：

<math>\begin{align}

N_n(x) &= y_0 + (xx}_{0})\left([{y}_{0}, {y}_{1}] + (xx}_{1})\left([{y}_{0}, {y}_{1},{y}_{2}] + \cdots\right)\right) \\

&=[y_0]+[{y}_{0}, {y}_{1}](xx}_{0})+\cdots+[{y}_{0},{y}_{1},\ldots,{y}_{n}]\prod_{k=0}^{n-1} (xx}_{k})

\end{align}</math> 可以在计算过程中任意增添节点如點(x_n+1,y_n+1)，只需計算新增的n+1階均差及其插值基函數，而无拉格朗日插值法需重算全部插值基函数之虞。

對均差採用展開形式^[11]：

<math>\begin{align}

N_n(x) &= y_0 + y_0\frac{xx}_{0}}{x_0-x_1}+ y_1\frac{xx}_{0}}{x_1-x_0}+\cdots+ \sum_{j=0}^{n} y_j  \frac{\prod_{k=0}^{n-1} (xx}_{k})} {\prod_{k=0,\, k\neq j}^{n} (x_j-x_k)} \\

\end{align}</math>

以2階均差牛頓插值為例：

<math>\begin{align}

N_2(x)&=y_0\left(1+ \frac{xx}_{0}}{x_0-x_1}+\frac{(x-x_0)(x-x_1)}{(x_0-x_1)(x_0-x_2)}\right) + y_1\left(\frac{xx}_{0}}{x_1-x_0}+\frac{(x-x_0)(x-x_1)}{(x_1-x_0)(x_1-x_2)}\right) + y_2\frac{(x-x_0)(x-x_1)}{(x_2-x_0)(x_2-x_1)} \\
&=y_0\frac{(x-x_1)(x-x_2)}{(x_0-x_1)(x_0-x_2)} + y_1\frac{(x-x_0)(x-x_2)}{(x_1-x_0)(x_1-x_2)} + y_2\frac{(x-x_0)(x-x_1)}{(x_2-x_0)(x_2-x_1)} \\
&= \sum_{j=0}^{2} y_j  \prod_{\begin{smallmatrix} k=0 \\ k\neq j \end{smallmatrix}}^{2} \frac{xx}_{k}} { x_j-x_k}  \\

\end{align}</math>

前向差分[编辑]

當數據點呈等距分佈的時候，這個特殊情況叫做“前向差分”。它們比計算一般的均差要容易。

定義[编辑]

給定n+1個數據點

<math>(x_0, y_0),\ldots,(x_{n}, y_{n})</math>

有著

定義前向差分為：

<math>\begin{align}

\triangle^{0}y_{i} &= y_{i} \\
\triangle^{k}y_{i} &= \triangle^{k-1}y_{i+1} - \triangle^{k-1}y_{i} , \quad 1 \le k \le n-i\\

\end{align}</math>

前向差分所对应的均差为^[12]：

<math>f[x_0, x_1, \ldots , x_k] = \frac{1}{k!h^k}\Delta^{(k)}f(x_0)</math>

例子[编辑]

<math>

\begin{matrix} y_0 & & & \\

   & \triangle y_0 &                   &                  \\

y_1 & & \triangle^{2} y_0 & \\

   & \triangle y_1 &                   & \triangle^{3} y_0\\

y_2 & & \triangle^{2} y_1 & \\

   & \triangle y_2 &                   &                  \\

y_3 & & & \\ \end{matrix} </math>

展開形式[编辑]

差分的展開形式是均差展開形式的特殊情況^[13]：

<math>\begin{align}

 \triangle^{k}y_{i} &= \sum_{j = 0}^{k} (-1)^{k-j} \binom{k}{j} y_{i+j}, \quad 0 \le k \le n-i

\end{align}</math> 這裡的表達式

<math>{n \choose k} = \frac{(n)_k}{k!} \quad\quad (n)_k=n(n-1)(n-2)\cdots(n-k+1)</math>

是二項式係數，其中的(n)_k是“下降階乘冪”，空積(n)₀被定義為1。

插值公式[编辑]

其對應的牛頓插值公式為：

<math>\begin{align}

f(x) &= y_0 + \frac {x-x_0} {h} \left( \Delta^1y_0 + \frac {x-x_0-h} {2h}\left(\Delta^2y_0 + \cdots \right) \right) \\

&= y_0 + \sum_{k=1}^n \frac{\Delta^ky_0}{k!h^k} \prod_{i=0}^{n-1} (x-x_0-ih) \\
&= y_0 + \sum_{k=1}^n \frac{\Delta^ky_0}{k!} \prod_{i=0}^{n-1} (\frac{x-x_0}{hi) \\
&= \sum_{k=0}^n {\frac{x-x_0}{h} \choose k}~ \Delta^k y_0 \\

\end{align}</math>

無窮級數[编辑]

牛頓在1665年得出並在1671年寫的《流數法》中發表了ln(1+x)的無窮級數，在1666年得出了arcsin(x)和arctan(x)的無窮級數，在1669年的《分析學》中發表了sin(x)、cos(x)、arcsin(x)和e^x的無窮級數；萊布尼茨在1673年大概也得出了sin(x)、cos(x)和arctan(x)的無窮級數。布魯克·泰勒在1715年著作《Methodus Incrementorum Directa et Inversa》^[14]中研討了“有限差分”方法，其中論述了他在1712年得出的泰勒定理，這個成果此前詹姆斯·格雷果里在1670年和萊布尼茨在1673年已經得出，而約翰·伯努利在1694年已經在《教師學報》發表。

他對牛頓的均差的步長取趨於0的極限，得出：

<math>

\begin{align} f(x) &= f(a) + \lim_{h \to 0}\sum_{k=1}^\infty \frac{\Delta_h^k[f](a)}{k!h^k} \prod_{i=0}^{k-1} ((x-a)-ih) \\

&= f(a) + \sum_{k=1}^\infty \frac{d^k}{dx^k}f(a) \frac{(x-a)^k}{k!} \\

\end{align} </math>

冪函數的均差[编辑]

使用普通函數記號表示冪运算，<math>p_n(x) = x^n</math>，有：

<math>

\begin{align} p_j[x_0,\dots,x_n] &= 0 \qquad \forall j<n\\ p_n[x_0,\dots,x_n] &= 1 \\ p_{n+1}[x_0,\dots,x_n] &= x_0 + \dots + x_n \\ p_{n+m}[x_0,\dots,x_n]&= \sum_{k_0+\cdots+k_n=m} \begin{matrix} \prod_{t=0}^nx_{t}^{k_{t}} \end{matrix} \\ \end{align} </math> 此中n+1元m次齊次多項式的記法同於多項式定理。

泰勒形式[编辑]

泰勒級數和任何其他的函數級數，在原理上都可以用來逼近均差。將泰勒級數表示為:

均差的泰勒級數為：

前<math>n</math>項消失了，因為均差的階高於多項式的階。可以得出均差的泰勒級數本質上開始於：

依據均差中值定理（英语：Mean value theorem (divided differences)），這也是均差的最簡單逼近。

皮亞諾形式[编辑]

均差還可以表達為

<math>f[x_0,\ldots,x_n] = \frac{1}{n!} \int_{x_0}^{x_n} f^{(n)}(t)B_{n-1}(t) \, dt</math>

這裡的B_n-1是數據點x₀,...,x_n的n-1次B樣條，而f⁽ⁿ⁾是函數f的n階導數。這叫做均差的皮亞諾形式，而B_n-1是均差的皮亞諾核。

註釋與引用[编辑]

^ Frank C. Wilson; Scott Adamson. Applied Calculus. Cengage Learning. 2008: 177. ISBN 0-618-61104-5.
^ Tamara Lefcourt Ruby; James Sellers; Lisa Korf; Jeremy Van Horn; Mike Munn. Kaplan AP Calculus AB & BC 2015. Kaplan Publishing. 2014: 237. ISBN 978-1-61865-686-5.
^ Thomas Hungerford; Douglas Shaw. Contemporary Precalculus: A Graphing Approach. Cengage Learning. 2008: 211–212. ISBN 0-495-10833-2.
^ Isaacson, Walter. The Innovators. Simon & Schuster. 2014: 20. ISBN 978-1-4767-0869-0.
^
<math>
\begin{array}{lcl} { \begin{matrix} x_0 & x_0^2 & & \\ & & x_0+x_1 & & \\ x_1 & x_1^2 & & 1 & \\ & & x_1+x_2 & & 0 \\ x_2 & x_2^2 & & 1 & \\ & & x_2+x_3 & & & \\ x_3 & x_3^2 & & & \\ \end{matrix} } \\ \\ { \begin{matrix} x_0 & x_0^n & \\ & & \sum_{i=0}^{n-1}x_0^{n-1-i}x_1^i \\ x_1 & x_1^n & \\ \end{matrix} } \\ \\ { \begin{matrix} x_0 & x_0^{n+1} & \\ & & \frac{x_1^{n+1x_1x_0^n+x_1x_0^n-x_0^{n+1}}{x_1-x_0} =x_1\frac {x_1^n-x_0^n}{x_1-x_0}+x_0^n=x_1\sum_{i=0}^{n-1}x_0^{n-1-i}x_1^i+x_0^n=\sum_{i=0}^{n}x_0^{n-i}x_1^i \\ x_1 & x_1^{n+1} & \\ \end{matrix} } \\ \\ { \begin{matrix} x_0 & x_0^{n+1} & & \\ & & \sum_{i=0}^{n}x_0^{n-i}x_1^i & \\ x_1 & x_1^{n+1} & & \frac {\sum_{i=0}^{n}x_1^{n-i}x_2^i - \sum_{i=0}^{n}x_0^{n-i}x_1^i}{x_2-x_0}=\frac{\sum_{i=0}^{n-1}x_1^{i}(x_2^{n-ix_0^{n-i})}{x_2-x_0}=\sum_{i+j+k=n-1}{x_0^{i}x_1^{j}x_2^{k}} \\ & & \sum_{i=0}^{n}x_1^{n-i}x_2^i & \\ x_2 & x_2^{n+1} & & \\ \end{matrix} } \\ \\ { \begin{matrix} x_0 & x_0^{n+1} & & & \\ & & \sum_{i=0}^{n}x_0^{n-i}x_1^i & & \\ x_1 & x_1^{n+1} & & \sum_{i+j+k=n-1}{x_0^{i}x_1^{j}x_2^{k}} & \\ & & \sum_{i=0}^{n}x_1^{n-i}x_2^i & & \frac {\sum_{i+j+k=n-1}{x_1^{i}x_2^{j}x_3^{k}} - \sum_{i+j+k=n-1}{x_0^{i}x_1^{j}x_2^{k}}}{x_3-x_0}=\sum_{i+j+k+l=n-2}{x_0^{i}x_1^{j}x_2^{k}x_3^{l}} \\ x_2 & x_2^{n+1} & & \sum_{i+j+k=n-1}{x_1^{i}x_2^{j}x_3^{k}} & \\ & & \sum_{i=0}^{n}x_2^{n-i}x_3^i & & \\ x_3 & x_3^{n+1} & & & \\ \end{matrix} } \\ \\ { \begin{matrix} x_0 & x_0^3 & & & & \\ & & x_0^2+x_0x_1+x_1^2 & & \\ x_1 & x_1^3 & & x_0+x_1+x_2 & & \\ & & x_1^1+x_1x_2+x_2^2 & & 1 & \\ x_2 & x_2^3 & & x_1+x_2+x_3 & & 0 \\ & & x_2^2+x_2x_3+x_3^2 & & 1 & \\ x_3 & x_3^3 & & x_2+x_3+x_4 & & \\ & & x_3^2+x_3x_4+x_4^2 & & & \\ x_4 & x_4^3 & & & & \\ \end{matrix} } \\ \\ { \begin{matrix} x_0 & x_0^4 & & & & & \\ & & x_0^3+x_0^2x_1+x_0x_1^2+x_1^3 & & & \\ x_1 & x_1^4 & & x_0^2+x_0x_1+x_1^2 +x_0x_2+x_1x_2+x_2^2 & & & \\ & & x_1^3+x_1^2x_2+x_1x_2^2+x_2^3 & & x_0+x_1+x_2+x_3 & \\ x_2 & x_2^4 & & x_1^2+x_1x_2+x_2^2 +x_1x_3 +x_2x_3+x_3^2 & & 1 & \\ & & x_2^3+x_2^2x_3+x_2x_3^2+x_3^3 & & x_1+x_2+x_3+x_4 & & 0 \\ x_3 & x_3^4 & & x_2^2+x_2x_3+x_3^2 +x_2x_4 +x_3x_4+x_4^2 & & 1 & \\ & & x_3^3+x_3^2x_4+x_3x_4^2+x_4^3 & & x_2+x_3+x_4+x_5 & & \\ x_4 & x_4^4 & & x_3^2+x_3x_4+x_4^2 +x_3x_5 +x_4x_5+x_5^2 & & & \\ & & x_4^3+x_4^2x_5+x_4x_5^2+x_5^3 & & & & \\ x_5 & x_5^4 & & & & & \\ \end{matrix} } \\ \\ { \begin{matrix} x_0 & x_0^5 & & & & & &\\ & & \sum_{i=0}^{4}x_0^{4-i}x_1^i & & & &\\ x_1 & x_1^5 & & \sum_{i+j+k=3}x_0^{i}x_1^jx_2^k & & & &\\ & & \sum_{i=0}^{4}x_1^{4-i}x_2^i & & \sum_{i+j+k+l=2}x_0^{i}x_1^jx_2^kx_3^l & & &\\ x_2 & x_2^5 & & \sum_{i+j+k=3}x_1^{i}x_2^jx_3^k & & \sum_{i=0}^4x_i & &\\ & & \sum_{i=0}^{4}x_2^{4-i}x_3^i & & \sum_{i+j+k+l=2}x_1^{i}x_2^jx_3^kx_4^l & & 1 &\\ x_3 & x_3^5 & & \sum_{i+j+k=3}x_2^{i}x_3^jx_4^k & & \sum_{i=1}^5x_i & & 0\\ & & \sum_{i=0}^{4}x_3^{4-i}x_4^i & & \sum_{i+j+k+l=2}x_2^{i}x_3^jx_4^jx_5^l & &1 &\\ x_4 & x_4^5 & & \sum_{i+j+k=3}x_3^{i}x_4^jx_5^k & & \sum_{i=2}^6x_i & &\\ & & \sum_{i=0}^{4}x_4^{4-i}x_5^i & & \sum_{i+j+k+l=2}x_3^{i}x_4^jx_5^kx_6^l & & &\\ x_5 & x_5^5 & & \sum_{i+j+k=3}x_4^{i}x_5^jx_6^k & & & &\\ & & \sum_{i=0}^{4}x_5^{4-i}x_6^i & & & & &\\ x_6 & x_6^5 & & & & & &\\ \end{matrix} } \\ \end{array} </math>
^
<math>
\begin{align} \mathopen[y_0] &= y_0 \\ \mathopen[y_0,y_1] &= \frac{y_1-y_0}{x_1-x_0} = \frac{y_0}{x_0-x_1} + \frac{y_1}{x_1-x_0}\\ &= \sum_{j=0}^{1} \frac{y_j} { \prod_{k=0,k\neq j}^{1} (x_j-x_k)} \\ \mathopen[y_0,y_1,y_2] &= \frac{\cfrac{y_1}{x_1-x_2} + \cfrac{y_2}{x_2-x_1} - \cfrac{y_0}{x_0-x_1} - \cfrac{y_1}{x_1-x_0}}{x_2-x_0} \\ &= \frac{y_0}{(x_0-x_1)(x_0-x_2)} + \frac{y_1}{(x_1-x_0)(x_1-x_2)} + \frac{y_2}{(x_2-x_0)(x_2-x_1)} \\ &= \sum_{j=0}^{2} \frac{y_j} {\prod_{k=0,k\neq j}^{2} (x_j-x_k)} \\ \mathopen[y_0, y_1,\dots, y_n] &=\sum_{j=0}^{n} \frac{y_j} {\prod_{k=0,k\neq j}^{n} (x_j-x_k)} \\ \mathopen[y_0, y_1,\dots, y_{n+1}] &=\frac{\sum_{j=1}^{n+1} \frac{y_j}{\prod_{k=1,\, k\neq j}^{n+1} (x_j-x_k)} - \sum_{j=0}^{n} \frac{y_j}{\prod_{k=0,\, k\neq j}^{n} (x_j-x_k)}}{x_{n+1x_0} \\ &= \frac{\frac {y_{n+1}}{\prod_{k=1}^{n} (x_{n+1x_k)} + \sum_{j=1}^{n} y_j\left(\frac{1}{\prod_{k=1,\, k\neq j}^{n+1} (x_j-x_k)\frac{1}{\prod_{k=0,\, k\neq j}^{n} (x_j-x_k)}\right) - \frac{y_0}{\prod_{k=1}^{n} (x_0-x_k)}}{x_{n+1x_0} \\ &= \frac{\frac {y_{n+1}}{\prod_{k=1}^{n} (x_{n+1x_k)} + \sum_{j=1}^{n} y_j\left(\frac{x_j-x_0}{\prod_{k=0,\, k\neq j}^{n+1} (x_j-x_k)\frac{x_j-x_{n+1}}{\prod_{k=0,\, k\neq j}^{n+1} (x_j-x_k)}\right) - \frac{y_0}{\prod_{k=1}^{n} (x_0-x_k)}}{x_{n+1}-x_0} \\ &= \frac{\frac {y_{n+1}}{\prod_{k=1}^{n} (x_{n+1}-x_k)} + \sum_{j=1}^{n} y_j\left(\frac{x_{n+1}-x_0}{\prod_{k=0,\, k\neq j}^{n+1} (x_j-x_k)}\right) - \frac{y_0}{\prod_{k=1}^{n} (x_0-x_k)}}{x_{n+1}-x_0} \\ &= \frac {y_{n+1}}{\prod_{k=0}^{n} (x_{n+1}-x_k)} + \sum_{j=1}^{n} \frac{y_j}{\prod_{k=0,\, k\neq j}^{n+1} (x_j-x_k)} + \frac{y_0}{\prod_{k=1}^{n+1} (x_0-x_k)}\\ &=\sum_{j=0}^{n+1} \frac{y_j}{\prod_{k=0,\, k\neq j}^{n+1} (x_j-x_k)} \end{align} </math>
^ 《数值分析及科学计算》薛毅（编）第六章第2节 Newton插值. P200.
^ 《数值分析及科学计算》薛毅（编）第六章第2节 Newton插值. P201.
^
<math>
\begin{matrix} x_0 & x_0^3 & & & & \\ & & x_0^2+x_0x_1+x_1^2 & & \\ x_1 & x_1^3 & & x_0+x_1+x_2 & & \\ & & x_0^2+x_0x_2+x_2^2 & & 1 & \\ x_2 & x_2^3 & & x_0+x_1+x_3 & & 0 \\ & & x_0^2+x_0x_3+x_3^2 & & 1 & \\ x_3 & x_3^3 & & x_0+x_1+x_4 & & \\ & & x_0^2+x_0x_4+x_4^2 & & & \\ x_4 & x_4^3 & & & & \\ \end{matrix} </math>
^ The Newton Polynomial Interpolation. [2019-04-19]. （原始内容存档于2019-04-19）.
^
<math>\begin{array}{lcl}
\begin{align} N_1(x) &=[y_0]+[{y}_{0}, {y}_{1}](x-{x}_{0}) = y_0 + y_0\frac{x-{x}_{0}}{x_0-x_1}+ y_1\frac{x-{x}_{0}}{x_1-x_0} = y_0(1 + \frac{x-{x}_{0}}{x_0-x_1})+ y_1\frac{x-{x}_{0}}{x_1-x_0} \\ &= y_0\frac{x-{x}_{1}}{x_0-x_1}+ y_1\frac{x-{x}_{0}}{x_1-x_0} = \sum_{j=0}^{1} y_j \prod_{ k=0 ,k \neq j}^{1} \frac{x-{x}_{k}} { x_j-x_k} \\ \end{align} \\ \begin{align} N_n(x) &= \sum_{j=0}^{n} y_j \prod_{k=0,k\neq j}^{n} \frac{x-{x}_{k}} { x_j-x_k} \\ \end{align} \\ \begin{align} N_{n+1}(x) &=N_n(x)+[{y}_{0},{y}_{1},\ldots,{y}_{n+1}]\prod_{k=0}^{n} (xx}_{k}) \\ &= \sum_{j=0}^{n} y_j \prod_{k=0, k\neq j}^{n} \frac{x-{字词转换器深度越限（10）x}_{k}} { x_j-x_k} + \sum_{j=0}^{n+1} y_j \frac{\prod_{k=0}^{n} (x-{x}_{k})} {\prod_{k=0,\, k\neq j}^{n+1} (x_j-x_k)} \\ &= \sum_{j=0}^{n} y_j \left( \frac{\prod_{k=0, k\neq j}^{n}(x-{x}_{k})} {\prod_{k=0, k\neq j}^{n}(x_j-x_k)} + \frac{\prod_{k=0}^{n} (x-{x}_{k})} {\prod_{k=0,\, k\neq j}^{n+1} (x_j-x_k)} \right) + y_{n+1} \frac{\prod_{k=0}^{n} (x-{x}_{k})} {\prod_{k=0}^{n} (x_{n+1x_k)} \\ &= \sum_{j=0}^{n} y_j \left( \frac{\left(\prod_{k=0, k\neq j}^{n}(xx}_{k})\right)(x_j-x_{n+1})} {\prod_{k=0, k\neq j}^{n+1}(x_j-x_k)} + \frac{\left(\prod_{k=0,k \neq j}^{n} (x-{字词转换器深度越限（10）x}_{k})\right)(x-x_j)} {\prod_{k=0,\, k\neq j}^{n+1} (x_j-x_k)} \right) + y_{n+1} \frac{\prod_{k=0}^{n} (x-{x}_{k})} {\prod_{k=0}^{n} (x_{n+1x_k)} \\ &= \sum_{j=0}^{n} y_j \frac{\left(\prod_{k=0, k\neq j}^{n}(xx}_{k})\right)(x-x_{n+1})} {\prod_{k=0, k\neq j}^{n+1}(x_j-x_k)} + y_{n+1} \frac{\prod_{k=0}^{n} (x-{字词转换器深度越限（10）x}_{k})} {\prod_{k=0}^{n} (x_{n+1x_k)} \\ &= \sum_{j=0}^{n+1} y_j \prod_{k=0,k\neq j}^{n+1} \frac{xNumerical Analysis 9th. 2011: 129.
^
<math>\begin{align}
\triangle^{k}y_{i} &= \sum_{j = 0}^{k} \frac{k!}{\prod_{l=0,\, l\neq j}^{k} (j-l)} y_{i+j}, \quad 0 \le k \le n-i \\ &= \sum_{j = 0}^{k} \frac{k!}{j!(-1)^{k-j}(k-j)!} y_{i+j}, \quad 0 \le k \le n-i \\ &= \sum_{j = 0}^{k} (-1)^{k-j} \binom{k}{j} y_{i+j}, \quad 0 \le k \le n-i \end{align}</math>
^ Methodus Incrementorum Directa et Inversa（页面存档备份，存于互联网档案馆）

参考书目[编辑]

Louis Melville Milne-Thomson. The Calculus of Finite Differences. American Mathematical Soc. 2000. Chapter 1: Divided Differences [1933]. ISBN 978-0-8218-2107-7.
Myron B. Allen; Eli L. Isaacson. Numerical Analysis for Applied Science. John Wiley & Sons. 1998. Appendix A. ISBN 978-1-118-03027-1.
Ron Goldman. Pyramid Algorithms: A Dynamic Programming Approach to Curves and Surfaces for Geometric Modeling. Morgan Kaufmann. 2002. Chapter 4:Newton Interpolation and Difference Triangles. ISBN 978-0-08-051547-2.

参见[编辑]

[WilsonAdamson2008-1] Frank C. Wilson; Scott Adamson. Applied Calculus. Cengage Learning. 2008: 177. ISBN 0-618-61104-5.

[RubySellers2014-2] Tamara Lefcourt Ruby; James Sellers; Lisa Korf; Jeremy Van Horn; Mike Munn. Kaplan AP Calculus AB & BC 2015. Kaplan Publishing. 2014: 237. ISBN 978-1-61865-686-5.

[HungerfordShaw2008-3] Thomas Hungerford; Douglas Shaw. Contemporary Precalculus: A Graphing Approach. Cengage Learning. 2008: 211–212. ISBN 0-495-10833-2.

[Isaacson2014-4] Isaacson, Walter. The Innovators. Simon & Schuster. 2014: 20. ISBN 978-1-4767-0869-0.

[5] 
<math>
\begin{array}{lcl} { \begin{matrix} x_0 & x_0^2 & & \\ & & x_0+x_1 & & \\ x_1 & x_1^2 & & 1 & \\ & & x_1+x_2 & & 0 \\ x_2 & x_2^2 & & 1 & \\ & & x_2+x_3 & & & \\ x_3 & x_3^2 & & & \\ \end{matrix} } \\ \\ { \begin{matrix} x_0 & x_0^n & \\ & & \sum_{i=0}^{n-1}x_0^{n-1-i}x_1^i \\ x_1 & x_1^n & \\ \end{matrix} } \\ \\ { \begin{matrix} x_0 & x_0^{n+1} & \\ & & \frac{x_1^{n+1x_1x_0^n+x_1x_0^n-x_0^{n+1}}{x_1-x_0} =x_1\frac {x_1^n-x_0^n}{x_1-x_0}+x_0^n=x_1\sum_{i=0}^{n-1}x_0^{n-1-i}x_1^i+x_0^n=\sum_{i=0}^{n}x_0^{n-i}x_1^i \\ x_1 & x_1^{n+1} & \\ \end{matrix} } \\ \\ { \begin{matrix} x_0 & x_0^{n+1} & & \\ & & \sum_{i=0}^{n}x_0^{n-i}x_1^i & \\ x_1 & x_1^{n+1} & & \frac {\sum_{i=0}^{n}x_1^{n-i}x_2^i - \sum_{i=0}^{n}x_0^{n-i}x_1^i}{x_2-x_0}=\frac{\sum_{i=0}^{n-1}x_1^{i}(x_2^{n-ix_0^{n-i})}{x_2-x_0}=\sum_{i+j+k=n-1}{x_0^{i}x_1^{j}x_2^{k}} \\ & & \sum_{i=0}^{n}x_1^{n-i}x_2^i & \\ x_2 & x_2^{n+1} & & \\ \end{matrix} } \\ \\ { \begin{matrix} x_0 & x_0^{n+1} & & & \\ & & \sum_{i=0}^{n}x_0^{n-i}x_1^i & & \\ x_1 & x_1^{n+1} & & \sum_{i+j+k=n-1}{x_0^{i}x_1^{j}x_2^{k}} & \\ & & \sum_{i=0}^{n}x_1^{n-i}x_2^i & & \frac {\sum_{i+j+k=n-1}{x_1^{i}x_2^{j}x_3^{k}} - \sum_{i+j+k=n-1}{x_0^{i}x_1^{j}x_2^{k}}}{x_3-x_0}=\sum_{i+j+k+l=n-2}{x_0^{i}x_1^{j}x_2^{k}x_3^{l}} \\ x_2 & x_2^{n+1} & & \sum_{i+j+k=n-1}{x_1^{i}x_2^{j}x_3^{k}} & \\ & & \sum_{i=0}^{n}x_2^{n-i}x_3^i & & \\ x_3 & x_3^{n+1} & & & \\ \end{matrix} } \\ \\ { \begin{matrix} x_0 & x_0^3 & & & & \\ & & x_0^2+x_0x_1+x_1^2 & & \\ x_1 & x_1^3 & & x_0+x_1+x_2 & & \\ & & x_1^1+x_1x_2+x_2^2 & & 1 & \\ x_2 & x_2^3 & & x_1+x_2+x_3 & & 0 \\ & & x_2^2+x_2x_3+x_3^2 & & 1 & \\ x_3 & x_3^3 & & x_2+x_3+x_4 & & \\ & & x_3^2+x_3x_4+x_4^2 & & & \\ x_4 & x_4^3 & & & & \\ \end{matrix} } \\ \\ { \begin{matrix} x_0 & x_0^4 & & & & & \\ & & x_0^3+x_0^2x_1+x_0x_1^2+x_1^3 & & & \\ x_1 & x_1^4 & & x_0^2+x_0x_1+x_1^2 +x_0x_2+x_1x_2+x_2^2 & & & \\ & & x_1^3+x_1^2x_2+x_1x_2^2+x_2^3 & & x_0+x_1+x_2+x_3 & \\ x_2 & x_2^4 & & x_1^2+x_1x_2+x_2^2 +x_1x_3 +x_2x_3+x_3^2 & & 1 & \\ & & x_2^3+x_2^2x_3+x_2x_3^2+x_3^3 & & x_1+x_2+x_3+x_4 & & 0 \\ x_3 & x_3^4 & & x_2^2+x_2x_3+x_3^2 +x_2x_4 +x_3x_4+x_4^2 & & 1 & \\ & & x_3^3+x_3^2x_4+x_3x_4^2+x_4^3 & & x_2+x_3+x_4+x_5 & & \\ x_4 & x_4^4 & & x_3^2+x_3x_4+x_4^2 +x_3x_5 +x_4x_5+x_5^2 & & & \\ & & x_4^3+x_4^2x_5+x_4x_5^2+x_5^3 & & & & \\ x_5 & x_5^4 & & & & & \\ \end{matrix} } \\ \\ { \begin{matrix} x_0 & x_0^5 & & & & & &\\ & & \sum_{i=0}^{4}x_0^{4-i}x_1^i & & & &\\ x_1 & x_1^5 & & \sum_{i+j+k=3}x_0^{i}x_1^jx_2^k & & & &\\ & & \sum_{i=0}^{4}x_1^{4-i}x_2^i & & \sum_{i+j+k+l=2}x_0^{i}x_1^jx_2^kx_3^l & & &\\ x_2 & x_2^5 & & \sum_{i+j+k=3}x_1^{i}x_2^jx_3^k & & \sum_{i=0}^4x_i & &\\ & & \sum_{i=0}^{4}x_2^{4-i}x_3^i & & \sum_{i+j+k+l=2}x_1^{i}x_2^jx_3^kx_4^l & & 1 &\\ x_3 & x_3^5 & & \sum_{i+j+k=3}x_2^{i}x_3^jx_4^k & & \sum_{i=1}^5x_i & & 0\\ & & \sum_{i=0}^{4}x_3^{4-i}x_4^i & & \sum_{i+j+k+l=2}x_2^{i}x_3^jx_4^jx_5^l & &1 &\\ x_4 & x_4^5 & & \sum_{i+j+k=3}x_3^{i}x_4^jx_5^k & & \sum_{i=2}^6x_i & &\\ & & \sum_{i=0}^{4}x_4^{4-i}x_5^i & & \sum_{i+j+k+l=2}x_3^{i}x_4^jx_5^kx_6^l & & &\\ x_5 & x_5^5 & & \sum_{i+j+k=3}x_4^{i}x_5^jx_6^k & & & &\\ & & \sum_{i=0}^{4}x_5^{4-i}x_6^i & & & & &\\ x_6 & x_6^5 & & & & & &\\ \end{matrix} } \\ \end{array} </math>

[6] 
<math>
\begin{align} \mathopen[y_0] &= y_0 \\ \mathopen[y_0,y_1] &= \frac{y_1-y_0}{x_1-x_0} = \frac{y_0}{x_0-x_1} + \frac{y_1}{x_1-x_0}\\ &= \sum_{j=0}^{1} \frac{y_j} { \prod_{k=0,k\neq j}^{1} (x_j-x_k)} \\ \mathopen[y_0,y_1,y_2] &= \frac{\cfrac{y_1}{x_1-x_2} + \cfrac{y_2}{x_2-x_1} - \cfrac{y_0}{x_0-x_1} - \cfrac{y_1}{x_1-x_0}}{x_2-x_0} \\ &= \frac{y_0}{(x_0-x_1)(x_0-x_2)} + \frac{y_1}{(x_1-x_0)(x_1-x_2)} + \frac{y_2}{(x_2-x_0)(x_2-x_1)} \\ &= \sum_{j=0}^{2} \frac{y_j} {\prod_{k=0,k\neq j}^{2} (x_j-x_k)} \\ \mathopen[y_0, y_1,\dots, y_n] &=\sum_{j=0}^{n} \frac{y_j} {\prod_{k=0,k\neq j}^{n} (x_j-x_k)} \\ \mathopen[y_0, y_1,\dots, y_{n+1}] &=\frac{\sum_{j=1}^{n+1} \frac{y_j}{\prod_{k=1,\, k\neq j}^{n+1} (x_j-x_k)} - \sum_{j=0}^{n} \frac{y_j}{\prod_{k=0,\, k\neq j}^{n} (x_j-x_k)}}{x_{n+1x_0} \\ &= \frac{\frac {y_{n+1}}{\prod_{k=1}^{n} (x_{n+1x_k)} + \sum_{j=1}^{n} y_j\left(\frac{1}{\prod_{k=1,\, k\neq j}^{n+1} (x_j-x_k)\frac{1}{\prod_{k=0,\, k\neq j}^{n} (x_j-x_k)}\right) - \frac{y_0}{\prod_{k=1}^{n} (x_0-x_k)}}{x_{n+1x_0} \\ &= \frac{\frac {y_{n+1}}{\prod_{k=1}^{n} (x_{n+1x_k)} + \sum_{j=1}^{n} y_j\left(\frac{x_j-x_0}{\prod_{k=0,\, k\neq j}^{n+1} (x_j-x_k)\frac{x_j-x_{n+1}}{\prod_{k=0,\, k\neq j}^{n+1} (x_j-x_k)}\right) - \frac{y_0}{\prod_{k=1}^{n} (x_0-x_k)}}{x_{n+1}-x_0} \\ &= \frac{\frac {y_{n+1}}{\prod_{k=1}^{n} (x_{n+1}-x_k)} + \sum_{j=1}^{n} y_j\left(\frac{x_{n+1}-x_0}{\prod_{k=0,\, k\neq j}^{n+1} (x_j-x_k)}\right) - \frac{y_0}{\prod_{k=1}^{n} (x_0-x_k)}}{x_{n+1}-x_0} \\ &= \frac {y_{n+1}}{\prod_{k=0}^{n} (x_{n+1}-x_k)} + \sum_{j=1}^{n} \frac{y_j}{\prod_{k=0,\, k\neq j}^{n+1} (x_j-x_k)} + \frac{y_0}{\prod_{k=1}^{n+1} (x_0-x_k)}\\ &=\sum_{j=0}^{n+1} \frac{y_j}{\prod_{k=0,\, k\neq j}^{n+1} (x_j-x_k)} \end{align} </math>

[7] 《数值分析及科学计算》薛毅（编）第六章第2节 Newton插值. P200.

[8] 《数值分析及科学计算》薛毅（编）第六章第2节 Newton插值. P201.

[9] 
<math>
\begin{matrix} x_0 & x_0^3 & & & & \\ & & x_0^2+x_0x_1+x_1^2 & & \\ x_1 & x_1^3 & & x_0+x_1+x_2 & & \\ & & x_0^2+x_0x_2+x_2^2 & & 1 & \\ x_2 & x_2^3 & & x_0+x_1+x_3 & & 0 \\ & & x_0^2+x_0x_3+x_3^2 & & 1 & \\ x_3 & x_3^3 & & x_0+x_1+x_4 & & \\ & & x_0^2+x_0x_4+x_4^2 & & & \\ x_4 & x_4^3 & & & & \\ \end{matrix} </math>

[10] The Newton Polynomial Interpolation. [2019-04-19]. （原始内容存档于2019-04-19）.

[11] 
<math>\begin{array}{lcl}
\begin{align} N_1(x) &=[y_0]+[{y}_{0}, {y}_{1}](x-{x}_{0}) = y_0 + y_0\frac{x-{x}_{0}}{x_0-x_1}+ y_1\frac{x-{x}_{0}}{x_1-x_0} = y_0(1 + \frac{x-{x}_{0}}{x_0-x_1})+ y_1\frac{x-{x}_{0}}{x_1-x_0} \\ &= y_0\frac{x-{x}_{1}}{x_0-x_1}+ y_1\frac{x-{x}_{0}}{x_1-x_0} = \sum_{j=0}^{1} y_j \prod_{ k=0 ,k \neq j}^{1} \frac{x-{x}_{k}} { x_j-x_k} \\ \end{align} \\ \begin{align} N_n(x) &= \sum_{j=0}^{n} y_j \prod_{k=0,k\neq j}^{n} \frac{x-{x}_{k}} { x_j-x_k} \\ \end{align} \\ \begin{align} N_{n+1}(x) &=N_n(x)+[{y}_{0},{y}_{1},\ldots,{y}_{n+1}]\prod_{k=0}^{n} (xx}_{k}) \\ &= \sum_{j=0}^{n} y_j \prod_{k=0, k\neq j}^{n} \frac{x-{字词转换器深度越限（10）x}_{k}} { x_j-x_k} + \sum_{j=0}^{n+1} y_j \frac{\prod_{k=0}^{n} (x-{x}_{k})} {\prod_{k=0,\, k\neq j}^{n+1} (x_j-x_k)} \\ &= \sum_{j=0}^{n} y_j \left( \frac{\prod_{k=0, k\neq j}^{n}(x-{x}_{k})} {\prod_{k=0, k\neq j}^{n}(x_j-x_k)} + \frac{\prod_{k=0}^{n} (x-{x}_{k})} {\prod_{k=0,\, k\neq j}^{n+1} (x_j-x_k)} \right) + y_{n+1} \frac{\prod_{k=0}^{n} (x-{x}_{k})} {\prod_{k=0}^{n} (x_{n+1x_k)} \\ &= \sum_{j=0}^{n} y_j \left( \frac{\left(\prod_{k=0, k\neq j}^{n}(xx}_{k})\right)(x_j-x_{n+1})} {\prod_{k=0, k\neq j}^{n+1}(x_j-x_k)} + \frac{\left(\prod_{k=0,k \neq j}^{n} (x-{字词转换器深度越限（10）x}_{k})\right)(x-x_j)} {\prod_{k=0,\, k\neq j}^{n+1} (x_j-x_k)} \right) + y_{n+1} \frac{\prod_{k=0}^{n} (x-{x}_{k})} {\prod_{k=0}^{n} (x_{n+1x_k)} \\ &= \sum_{j=0}^{n} y_j \frac{\left(\prod_{k=0, k\neq j}^{n}(xx}_{k})\right)(x-x_{n+1})} {\prod_{k=0, k\neq j}^{n+1}(x_j-x_k)} + y_{n+1} \frac{\prod_{k=0}^{n} (x-{字词转换器深度越限（10）x}_{k})} {\prod_{k=0}^{n} (x_{n+1x_k)} \\ &= \sum_{j=0}^{n+1} y_j \prod_{k=0,k\neq j}^{n+1} \frac{xNumerical Analysis 9th. 2011: 129.

[13] 
<math>\begin{align}
\triangle^{k}y_{i} &= \sum_{j = 0}^{k} \frac{k!}{\prod_{l=0,\, l\neq j}^{k} (j-l)} y_{i+j}, \quad 0 \le k \le n-i \\ &= \sum_{j = 0}^{k} \frac{k!}{j!(-1)^{k-j}(k-j)!} y_{i+j}, \quad 0 \le k \le n-i \\ &= \sum_{j = 0}^{k} (-1)^{k-j} \binom{k}{j} y_{i+j}, \quad 0 \le k \le n-i \end{align}</math>

[14] Methodus Incrementorum Directa et Inversa（页面存档备份，存于互联网档案馆）

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

均差

目录

定义[编辑]

表示法[编辑]

例子[编辑]

展开形式[编辑]

性质[编辑]

等价定义[编辑]

牛顿插值法[编辑]

前向差分[编辑]

定義[编辑]

例子[编辑]

展開形式[编辑]

插值公式[编辑]

無窮級數[编辑]

冪函數的均差[编辑]

泰勒形式[编辑]

皮亞諾形式[编辑]

註釋與引用[编辑]

参考书目[编辑]

参见[编辑]

导航菜单

均差

定义[编辑]

表示法[编辑]

例子[编辑]

展开形式[编辑]

性质[编辑]

等价定义[编辑]

牛顿插值法[编辑]

前向差分[编辑]

定義[编辑]

例子[编辑]

展開形式[编辑]

插值公式[编辑]

無窮級數[编辑]

冪函數的均差[编辑]

泰勒形式[编辑]

皮亞諾形式[编辑]

註釋與引用[编辑]

参考书目[编辑]

参见[编辑]

导航菜单

搜索