算法-数值分析复习：Newton插值

本篇文章适合个人复习翻阅，不建议新手入门使用

牛顿（Newton）插值

插值条件

n+1个插值节点 $x_0,x_1,\dots ,x_n$ 处函数值相同

基函数

{ ω i ( x ) } i = 0 n \{\omega_i(x)\}_{i=0}^n { ωi​(x)}i=0n​，其中$${\omega }_i(x)=(x-x_0)(x-x_1)\cdots (x-x_{i-1})$$称之为节点多项式

插值多项式

$$\prod _{n}f(x)=\sum _{i=0}^{n}f[x_0,x_1,\dots ,x_k]{\omega }_k(x)$$其中 $f[x_0,x_1,\dots ,x_k]$称为 $f$ 关于点$x_0,x_1,\dots ,x_k$的k阶牛顿差商

差商

差商的基本性质

• n阶差商为n次插值多项式的首项系数
• 差商值与节点排列顺序无关
• $$\begin{array}{rl}f[x_0,x_1,\dots ,x_n]& =\frac{f(x_n)-{\prod }_{n-1}f(x_n)}{{\omega }_n(x_n)}\\ & =\frac{{\prod }_{n}f(x_n)-{\prod }_{n-1}f(x_n)}{{\omega }_n(x_n)}\\ & =\sum _{i=0}^n\frac{f(x_i)}{{\omega }_{n+1}^{\prime }(x_i)}\end{array}$$
• $$f[x_0,x_1,\dots ,x_n]=\frac{f[x_0,\dots ,x_{n-1}]-f[x_1,\dots ,x_n]}{x_0-x_n}$$

证明思路：

第二条性质：
前两个等号容易得到；第三个等号：只需注意到

• n阶差商是n次Newton插值的首项系数
• 等式右端是Lagrange插值多项式的首项系数
• Newton插值、Lagrange插值是同一插值多项式的不同表达
• 多项式插值的唯一性（由Vandermonde行列式的性质易证）

第三条性质：归纳法可证

差商估计

$$f[x_0,x_1,\dots ,x_n]=\frac{f^{(m)}(\xi )}{m!}$$其中 ξ ∈ ( min ⁡ { x i } , max ⁡ { x i } ) \xi\in(\min\{x_i\},\max\{x_i\}) ξ∈(min{ xi​},max{ xi​})

证明思路：构造辅助函数 $f(x)-{\prod }_{n}f(x)$，使用 $n$次Rolle中值定理

差商的Leibniz公式

设$f(x)=\varphi (x)\psi (x)$，则
$$f[x_0,x_1,\dots ,x_n]=\sum _{i=0}^n\varphi (x_0,\dots ,x_i)\psi (x_i,\dots ,x_n)$$

证明思路：对 $f,\varphi ,\psi$ 分别进行Newton插值即可

余项估计

$$\begin{array}{rl}{R}_n(x)& =f(x)-\prod _{n}f(x)\\ & =f[x_0,x_1,\dots ,x_n,x]\prod _{i=0}^n(x-x_i)\\ & =f[x_0,x_1,\dots ,x_n,x]{\omega }_{n+1}(x)\end{array}$$

参考书籍：《数值分析》李庆扬 王能超 易大义 编