...
多项式插值有三种：Lagrange 插值，Newton 插值，Hermite 插值。
PART 1 定义
已知 \(n+1\) 个点 \((x_0,y_0),(x_1,y_1),\cdots,(x_n,y_n)\)，求一个插值多项式 \(f_{n}(x)=a_0+a_1x+a_2x^2+\cdots+a_{n}x^{n}\)，使得 \(f_{n}(x_i)=y_i\) 成立。
写成方程组的形式
\[\begin{cases}
a_0+a_1x_0+a_2x^2_0+\cdots+a_{n}x^{n}_0=y_0\\
a_0+a_1x_1+a_2x^2_1+\cdots+a_{n}x^{n}_1=y_1\\
\cdots\\
a_0+a_1x_n+a_2x^2_n+\cdots+a_{n}x^n_n=y_n
\end{cases}
\]
注意到左边是范德蒙德行列式，当所给的 \(n+1\) 个点互异时，插值多项式是唯一的，插值多项式的阶数定义为该多项式的次数。
PART 2 Lagrange 插值
Lagrange 方法的核心是将 \(n+1\) 个 \(n\) 次基函数线性组合得到 \(n+1\) 个点的插值。
对于任意点 \((x_i,y_i)\)，构造基函数 \(l_i(x)\)
\[\color{darkorange}{l_i(x)=\prod_{j=0\\j\ne i}^n \frac{x-x_j}{x_i-x_j}}
\]
可以发现类似布尔函数
\[l_i(x)=\begin{cases}
1,x=x_i\\
0,x= x_k(k\ne i)
\end{cases}
\]
这告诉我们 \(l_i(x)\) 在第 \(i\) 个点上取值为 \(1\)，在其他点上取值为 \(0\)，那么将所有的 \(y_il_i(x)\) 相加一定就是插值多项式了，记作
\[\color{darkorange}{
L_n(x)=\sum_{i=0}^n y_il_i(x)}
\]
我们也可以从克莱默法则出发证明
\[\begin{aligned}
L_{n}(x)
=&\sum_{k=0}^{n}\frac{|A_{k}|}{|A|}x^k\\
=&\sum_{k=0}^{n}\frac{\displaystyle\sum_{i=0}^n y_i A_{ik} }{\displaystyle\prod_{0\leq l<j\leq n}(x_j-x_l)}x^k\\
=&\sum_{i=0}^{n}\frac{\displaystyle\sum_{k=0}^{n} x^k A_{ik} }{\displaystyle\prod_{0\leq l<j\leq n}(x_j-x_l)}y_i\\
=&\sum_{i=0}^{n}\prod_{j=0\\j\ne i}^n \frac{x-x_j}{x_i-x_j}y_i
\end{aligned}
\]
当我们用插值方法近似 \(f(x)\) 时会产生误差余项 \(R_n(x)\)
\[R_n(x)=f(x)-L_n(x)
\]
我们对 \(R_n(x)\) 进行估计。
考虑到给定的 \(n+1\) 个点都是 \(R_n(x)\) 的零点，我们设
\[R_n(x)=k(x)\prod_{i=0}^{n}(x-x_i)
\]
引入辅助函数
\[\varphi(t)=f(t)-L_n(t)-k(x)\prod_{i=0}^{n}(t-x_i)
\]
这是一种在中值证明中常见的变量当作常量的处理方法。
那么
\[\varphi^{(n+1)}(t)=f^{(n+1)}(t)-(n+1)!k(x)
\]
且
\[\varphi(x_1)=\varphi(x_2)=\cdots=\varphi(x_{n+1})=\varphi(x)=0
\]
由罗尔定理
\[\varphi^{(n+1)}(\xi)=0
\]
因此
\[k(x)=\dfrac{f^{(n+1)}(\xi)}{(n+1)!}
\]
也就是说
\[\color{darkorange}{R_n(x)=\dfrac{f^{(n+1)}(\xi)}{(n+1)!}\prod_{i=0}^{n}(x-x_i)}
\]
其中 \(\xi\) 仅是与 \(x\) 有关的常数。
PART 3 Newton 插值
Newton 方法的核心是在 \(n\) 个点的插值多项式上增加 \(1\) 个点递推得到 \(n+1\) 个点的插值。
定义均差
\[f[\alpha_1,\alpha_2,\cdots,\alpha_k]=\dfrac{f[\alpha_2,\cdots,\alpha_k]-f[\alpha_1,\cdots,\alpha_{k-1}]}{\alpha_k-\alpha_1}
\]
任意调换节点的次序不改变均差的值。
对于一个点 \((\alpha_1,f(\alpha_1))\)
有零阶插值多项式 $$f_0(x)=f(\alpha_1) $$
对于两个点 \((\alpha_1,f(\alpha_1)),(\alpha_2,f(\alpha_2))\)
在 \(\alpha_1\) 的基础上加入 \(\alpha_2\) 有一阶插值多项式
\[f_1(x)=f_0(x)+f[\alpha_1,\alpha_2](x-\alpha_1)
\]
对于三个点 \((\alpha_1,f(\alpha_1)),(\alpha_2,f(\alpha_2)),(\alpha_3,f(\alpha_3))\)
在 \(\alpha_1,\alpha_2\) 的基础上加入 \(\alpha_3\) 有二阶插值多项式
\[f_2(x)=f_1(x)+f[\alpha_1,\alpha_2,\alpha_3](x-\alpha_1)(x-\alpha_2)
\]
对于 \(n+1\) 个点 \((\alpha_1,f(\alpha_1)),(\alpha_2,f(\alpha_2)),\cdots,(\alpha_{n+1},f(\alpha_{n+1}))\)
在 \(\alpha_1,\alpha_2,\cdots,\alpha_{n}\) 的基础上加入 \(\alpha_{n+1}\) 有 \(n\) 阶插值多项式
\[\color{darkorange}{
f_n(x)=f_{n-1}(x)+f[\alpha_1,\alpha_2,\cdots,\alpha_{n+1}]\prod_{i=1}^{n}(x-\alpha_i)}
\]
这时如果构造函数
\[g(x)=f(x)-f_n(x)
\]
那么
\[g(\alpha_1)=g(\alpha_2)=\cdots=g(\alpha_{n+1})=0
\]
由罗尔定理
\[g^{(n)}(\xi)=0
\]
亦即
\[\color{darkorange}{f[\alpha_1,\alpha_2,\cdots,\alpha_{n+1}]=\dfrac{f^{(n)}(\xi)}{n!}}
\]
发现了吗？如果让 \(\alpha_1,\alpha_2,\cdots,\alpha_n\) 无限接近，插值多项式就是泰勒公式
\[f(x)=f(\alpha_1)+f'(\alpha_1)(x-\alpha_1)+\dfrac{f''(\alpha_1)}{2!}(x-\alpha_1)^2+\cdots
\]
PART 4 Hermite 插值
这仅仅是增加了高阶导数的情况。
我们同样借助均差理解
\[f[a,a]=\lim_{h\rightarrow0}f[a,a+h]=\lim_{h\rightarrow0}\frac{f(a+h)-f(a)}{h}=f'(a)
\]
\[f[a,a,b]=\lim_{h\rightarrow0}\frac{f[a+h,b]-f[a,a+h]}{b-a}=\frac{f[a,b]-f'(a)}{b-a}
\]
\[f(x)=f(a)+f[a,b](x-a)+f[a,a,b](x-a)(x-b)+\cdots
\]
PART 5 习题
\(\rm Qn1\quad\) 设 \(f(x)\) 在 \([0,1]\) 上二阶可导，证明：对任意 \(t\in(0,1)\)，都存在 \(\eta\in(0,1)\) 使得 \(\dfrac{f''(\eta)}{2}=\dfrac{f(0)}{t}-\dfrac{f(t)}{t(1-t)}+\dfrac{f(1)}{1-t}\)
\(\rm Sol\quad\) 选择 \(0,t,1\) 作 Newton 插值
\[f[0,t,1]=\frac{f''(\eta)}{2}
\]
化简即得
\[\dfrac{f''(\eta)}{2}=\dfrac{f(0)}{t}-\dfrac{f(t)}{t(1-t)}+\dfrac{f(1)}{1-t}
\]
\(\rm Qn2\quad\) 设函数 \(f(x)\) 在 \((0,1)\) 上存在三阶导数，\(0<a<b<1\)，证明存在 \(\xi\in(a,b)\) 使得 \(f(b)=f(a)+\dfrac12(b-a)(f'(a)+f'(b))-\dfrac{(b-a)^3}{12}f'''(\xi)\)
\(\rm Sol\quad\) 选择 \(a,a,b,b\) 作 Hermite 插值
\[f[a,a,b,b]=\dfrac{f'''(\xi)}{6}
\]
化简即得
\[f(b)=f(a)+\dfrac12(b-a)(f'(a)+f'(b))-\dfrac{(b-a)^3}{12}f'''(\xi)
\]
\(\rm Qn3\quad\) 设函数 \(f(x)\) 在 \([a,b]\) 上 \(p+q\) 次连续可微，在 \((a,b)\) 内有 \(p+q+1\) 阶导数，且 \(f(a)=f'(a)=\cdots=f^{(p)}(a)=f(b)=f'(b)=\cdots=f^{(q)}(b)=0\)，证明存在 \(\xi\in(a,b)\) 使得 \(f^{(p+q+1)}(\xi)=0\)
\(\rm Sol\quad\) 选择 \(\underbrace{a,\cdots,a}_{p+1},\underbrace{b,\cdots,b}_{q+1}\) 作 Hermite 插值
\[f[\underbrace{a,\cdots,a}_{p+1},\underbrace{b,\cdots,b}_{q+1}]=\dfrac{f^{(p+q+1)}(\xi)}{(p+q+1)!}=0
\]
因此
\[f^{(p+q+1)}(\xi)=0
\]
\(\rm Qn4\quad\) 设 \(f(x)\in C[a,b]\)，且 \(f(a)=f(b)=0\) ，求证：$$\left|\int_a^b f(x)\text dx\right|\leq\dfrac{(b-a)^3}{12}\text{max}|f''(x)|$$
\(\rm Sol\quad\) 选择 \(a,b\) 作 Lagrange 插值
\[\begin{aligned}
f(x)=\dfrac{f''(\xi)}{2}(x-a)(x-b)
\end{aligned}
\]
那么
\[\begin{aligned}
\left|\int_a^b f(x)\text dx\right|=&\left|\int_a^b \dfrac{f''(\xi)}{2}(x-a)(x-b)\text dx\right|\\ \leq&
\dfrac{1}{2}\text{max}|f''(x)|\left|\int_a^b (x-a)(x-b)\text dx\right|\\=&
\dfrac{(b-a)^3}{12}\text{max}|f''(x)|
\end{aligned}
\]
\(\rm Qn5\quad\) 已知函数 \(f(x)\) 在 \([a,b]\) 上三阶可导，且 \(f(a)=f'(a)=f(b)=0\)，\(|f'''(x)|\leq M\) 在 \([a,b]\) 上恒成立，求证：
\[\left|\int_a^b f(x)\text dx\right|\leq\dfrac{M(b-a)^4}{72}
\]
\(\rm Sol\quad\) 选择 \(a,a,b\) 作 Hermite 插值
\[\begin{aligned}
f(x)=&f_2(x)+R_2(x)\\=&f_1(x)+f[a,a,b](x-a)(x-b)+\dfrac{f'''(\xi)}{6}(x-a)^2(x-b)\\
=&\dfrac{f'''(\xi)}{6}(x-a)^2(x-b)
\end{aligned}
\]
那么
\[\begin{aligned}
\left|\int_a^b f(x)\text dx\right|=&\left|\int_a^b \dfrac{f'''(\xi)}{6}(x-a)^2(x-b)\text dx\right|\\ \leq&
\dfrac{M}{6}\left|\int_a^b (x-a)^2(x-b)\text dx\right|\\=&
\dfrac{M(b-a)^4}{72}
\end{aligned}
\]
\(\rm Qn6\quad\) 函数 \(f''(x)\in C[0,1]\)，\(f(0)=f(1)=0，f'(1)=\dfrac{a}{2}\)，证明 \(\displaystyle{\int_0^1 x[f''(x)]^2\text dx\geq \frac{a^2}{2}}\)
\(\rm Sol\quad\) 选择 \(0,1,1\) 作 Hermite 插值
\[\begin{aligned}
f(x)=&f_2(x)+R_2(x)\\f''(x)=&a+R_2''(x)
\end{aligned}
\]
那么
\[\begin{aligned}
\int_0^1 x[f''(x)]^2\text dx=&a^2\int_0^1 x\text dx+2a\int_0^1 xR_2''(x)\text dx+\int_0^1 x[R_2''(x)]^2\text dx\\
=&\frac{a^2}{2}+2a\left(xR_2'(x)\bigg|_0^1-\int_0^1 R_2'(x)\text dx\right)+\int_0^1 x[R_2''(x)]^2\text dx\\
\geq&\frac{a^2}{2}
\end{aligned}
\]
\(\rm Qn7\quad\) 证明恒等式
\[\sum_{k=0}^n\binom nk \frac{(-1)^k}{k-m}=(-1)^m\binom nm(H_m-H_{n-m})
\]
\(\rm Sol\quad\) 选择 \(-m,-m+1,\cdots,-m+n\) 对常数 \(1\) 作 Lagrange 插值
\[\begin{aligned}
1=&\sum_{i=0}^n\prod_{j=0\\j\ne i}^n \frac{x-(-m+j)}{(-m+i)-(-m+j)}\\
=&\frac1{n!}\sum_{i=0}^n \binom ni (-1)^{n-i}\prod_{j=0\\j\ne i}^n(x+m-j)
\end{aligned}
\]
当 \(i\ne m\) 时 \(\displaystyle\prod_{j=0\\j\ne i}^n(x+m-j)\) 的一次项系数为
\[(-1)^{n-m}\frac{(n-m)!m!}{m-i}
\]
当 \(i=m\) 时为
\[(-1)^{n-m}m!(n-m)!\sum_{j=0\\j\ne m}^n\frac{1}{m-j}
\]
它们相加为 \(0\)，移项即得
\[\sum_{k=0}^n\binom nk \frac{(-1)^k}{k-m}=(-1)^m\binom nm(H_m-H_{n-m})
\]