插值

hbghlyj

谈插值法-王九逵
假定$t(x)$是一个不超过$n$次的多项式函数,再假定我们已经知道$t(x)$在$n+1$个不同的点$x_0,x_1,\ldots,x_n$的值为$y_0,y_1,\ldots,y_n$,我们计算它在另一点 $\bar{x}$ 的值 $ t( \bar{x} )$,这个问题叫作插值 (Interpolation) 问题.
让我们再用解析几何的语言把问题重新叙述一下;如果我们把$(x_i,y_i)$看成平面上一点$P_i$的坐标,问题便可改述成下形式:给了平面上的$n+1$个点$P_0, P_1,\cdots,P_n$,其横坐标两两相异,我们想找一条代表$n$次多项式的曲线通过这些点.

大凡我们碰到一个数学问题时,我们首先想知道这问题有没有解,如果有解,其次我们便想知道解是不是唯一的,如果确只有唯一解,我们还想用把这解用某种办法找出来,最后,如果我们能用某种方式解这问题,我们还想找到一个便捷的方法.

插值问题的解一定存在,而且是唯一的;这是很容易证明的事,假定所求的多项式为$$t(x) = a_0 x^n + a_1 x^{n-1} + \cdots + a_n ,$$那么条件$t(x_i) = y_i$可以改写成\begin{align} &a_0 x^n_0 +a_1 x^{n-1}_0 + \cdots + a_n = y_0, \\ &a_0 x^n_1 +a_1 x^{n-1}_1 + \cdots + a_n = y_1, \\ &\cdots\quad\cdots\quad\cdots\quad\cdots\\ &a_0 x^n_n + a_1 x^{n-1}_n + \cdots + a_n = y_n \end{align}这可以看成$n+1$个未知数 $a_0,a_1,\cdots,a_n$ 的一次联立方程组.其系数的行列式为$$\left|\begin{array}{ccccc}x_{0}^{n} & x_{0}^{n-1} & \cdots & x_{0} & 1 \\ x_{1}^{n} & x_{1}^{n-1} & \cdots & x_{1} & 1 \\ \cdots & \ldots & \cdots & \ldots & \ldots \\ x_{n}^{n} & x_{n}^{n-1} & \cdots & x_{n} & 1\end{array}\right|=\left(x_{0}-x_{1}\right)\left(x_{0}-x_{2}\right) \cdots\left(x_{n-1}-x_{n}\right) \neq 0$$所以联立方程式有唯一的解,我们可以用消元法求出唯一的一组系数 $a_0, a_1,\cdots,a_n$. 有了这些系数后,对任意 ${\bar{x}}$ 我们都能把 $ t( \bar{x} )$ 计算出来.
所以插值问题不但确定唯一的解,而且在理论上我们总可以解它.但事实上如果未知数一多,解联立方程式的消元法就变得非常棘手.因此我们希望找出一些比消元法更简捷的方法来解插值问题.

牛顿的差商插值公式

和插值问题很有关系的一个观念是差商(difference quotient 或 divided difference), 设$ x_0,x_1,\cdots,x_n $是两两不同的一串实数,再设$ f(x) $是对一切$ x $值都有意义的函数.令$$f_i(x) = \frac{ f(x) -f(x_i) }{x-x_i} , i=0,1,2,\cdots$$则$ f_i(x) $叫$ f(x) $关于$ x_i $的一阶差商,从解析几何的观点来看,$f_i(x)$表示连接$ (x_i,f(x_i)) $和$ (x,f(x)) $两点的直线的斜率,对一切 $\neq x_i$ 的$ x $值,$f_i(x) $都是有意义的.
我们可以作$ f_i $的一阶差商$$f_{i,j} (x) = \frac{f_i(x)-f_i(x_j)}{x-x_j} , \qquad j \neq i$$这叫作$ f(x) $的二阶差商,除了$x_i,x_j$两点以外,$f_{i,j}(x) $都有意义.仿此我们可以作$ f(x) $的逐次高阶差商 $f_{i,j,\cdots,k}(x)$.
把 0,1,2,\ldots 依次作新足标 (subscript),可以将$f(x)$的逐次差商排成下列图形:$$\begin{array}{ccccccc} x_0 & f(x_0) &&&&& \\ x_1 & f(x_1) &f_0(x_1)&&&& \\ x_2 & f(x_2) &f_0(x_2)&f_{0,1}(x_2)&&& \\ x_3 & f(x_3) &f_0(x_3)&f_{0,1}(x_3)&f_{0,1,2}(x_3)&& \\ x_4 & f(x_4) &f_0(x_4)&f_{0,1}(x_4)&f_{0,1,2}(x_4)&f_{0,1,2,3}(x_4)& \\ x_5 & f(x_5) &f_0(x_5)&f_{0,1}(x_5)&f_{0,1,2}(x_5)&f_{0,1,2,3}(x_5)& f_{0,1,2,3,4}(x_5)\\ \cdots &\cdots & \cdots & \cdots & \cdots & \cdots& \cdots \\ \end{array}$$这样的图形叫$ f $的差商表 (lozenge diagram),表中第三行以后每项都是其左边一项与该项所在行顶上一项的差被最左行对应项除的商.例如$$f_{0,1}(x_4)= \frac{f_0(x_4) - f_0(x_1)}{x_4 - x_1}$$从逐次差商的定义我们可以得到\begin{align}(*)\qquad f ( x _ { n + 1 } ) &= f ( x _ { 0 } ) + f _ { 0 } ( x _ { n + 1 } ) ( x _ { n + 1 } - x _ { 0 } ) \\ &= f ( x _ { 0 } ) + f _ { 0 } ( x _ { 1 } ) ( x _ { n + 1 } - x _ { 0 } ) + \\& f _ { 0,1 } ( x _ { n + 1 } ) ( x _ { n + 1 } - x _ { 0 } ) ( x _ { n + 1 } - x _ { 1 } ) \\&=\ldots \ldots \ldots \ldots \ldots \\&= f ( x _ { 0 } ) + f _ { 0 } ( x _ { 1 } ) ( x _ { n + 1 } - x _ { 0 } ) + \\&f _ { 0,1 } ( x _ { 2 } ) ( x _ { n + 1 } - x _ { 0 } ) ( x _ { n + 1 } - x _ { 1 } ) + \\&\ldots \ldots \ldots \ldots \ldots \ldots \ldots + \\&f _ { 0,1 , \cdots , n - 1 } ( x _ { n } ) ( x _ { n + 1 } - x _ { 0 } ) ( x _ { n + 1 } - x _ { 1 } ) \\&\ldots ( x _ { n + 1 } - x _ { n - 1 } ) + R\end{align}式中$$R=f_{0,1,\cdots,n}(x_{n+1})(x_{n+1}-x_0)(x_{n+1}-x_1) \cdots (x_{n+1} - x_n)$$现在让我们看一看$ x,x_2,x_3 $关于 0,2,7,-3,8 诸点的差商表:\begin{array} { r r r r r r r r r r r } { x } & { x } & & & & & { x } & { x ^ { 2 } } & & & { }& \\ { 0 } & { 0 } & & & & & { 0 } & { 0 } & & & &\\ { 2 } & { 2 } & { 1 } & & & & { 2 } & { 4 } & { 2 } & & &\\ { 7 } & { 7 } & { 1 } & { 0 } & & & { 7 } & { 49 } & { 7 } & { 1 } & { }& \\ { - 3 } & { - 3 } & { 1 } & { 0 } & { 0 } & & { - 3 } & { 9 } & { - 3 } & { 1 } & { 0 }&\\ { 8 } & { 8 } & { 1 } & { 0 } & { 0 } & { 0 } & { 8 } & { 64 } & { 8 } & { 1 } & { 0 }&0 \end{array} \begin{array} { r r r r r } { x } & { x ^ { 3 } } &&&&\\ { 0 } & { 0 } & & & &\\ { 2 } & { 8 } & { 4 } &&&\\ { 7 } & { 343 } & { 49 } & { 9 } &&\\ { - 3 } & { - 27 } & { 9 } & { - 1 } & { 1 }&\\ { 8 } & { 512 } & { 64 } & { 10 } & { 1 } &0\end{array}从这些表的观察,我们可以猜想:如果$k>n$,则$ x_n $的第$k$阶差商必恒为0,事实上这是对的,我们可以用数学归纳法来证明:
很明显的$x^0 \equiv 1$的各阶差商都是0,假如我们已经知道定理对$ x_0,x_1,\cdots,x_{n-1} $都成立,令$f(x) = x^n$因为$$f_0(x)=\frac{x^n-x_0^n}{x-x_0} =x^{n-1}+x_0x^{n-2}+\cdots+x_0^{n-1}$$是一个$n-1$次的多项式,所以$f_0$的$n$阶以上差商都是0,因此如果$k>n$,则$k-1>n-1$,于是$$f_{0,1,\cdots,k}(x)=\frac{f_{0,1,\cdots,k-1}(x_k)-f_{0,1,2,\cdots,k-1}(x_0)}{x_0 - x_k} = 0$$从而有

定理(牛顿)

$n$次多项式的第$n+1$阶以上的差商全是0.

现在回到公式(*),假定$f(x)=t(x)$是一个$n$次多项式,则$R=0$,以$\bar{x}$代$x_{n+1}$便得\begin{array} { l }{ t ( \overline { x } ) = t ( x _ { 0 } ) + t _ { 0 } ( x _ { 1 } ) ( \overline { x } - x _ { 0 } ) }\\{ + t _ { 0,1 } ( x_2 ) ( \overline { x } - x _ { 0 } ) ( \overline { x } - x _ { 1 } ) + \cdots }\\{ + t _ { 0,1 , \cdots , n - 1 } ( x _ { n } ) ( \overline { x } - x _ { 0 } ) ( \overline { x } - x _ { 1 } ) \cdots ( \overline { x } - x _ { n - 1 } ) } \end{array}这便是牛顿的插值公式.

一般说来,牛顿插值公式并不十分好用──这是由于制作差商表时要作很多次除法的缘故,但若$x_i = a+ih$,其中$a$及$h$为定数,我们用$y_i$表示$t(x_i)$,用$\triangle y_i$表示$y_{i+1}-y_i$,用$\triangle^2 y_i$表示$\triangle y_{i+1} - \triangle y_i$等等,这些$\triangle^k y_i$叫作$y_i$的差分(finite differences),而牛顿插值公式可以改写为$$t(a+sh) = y_0 + {s \choose 1} \triangle y_0+ {s \choose 2} \triangle^2 y_0 + \cdots+ {s \choose n} \triangle^n y_0$$式中$${s \choose k} = \frac{s(s-1) \cdots (s-k+1)}{1 \cdot 2 \cdot \ldots \cdot k}$$这叫作牛顿的差分插值公式,是数值分析 (numerical analysis) 中的一个基本公式.

拉格朗日 (Lagrange) 的插值公式

拉格朗日研究差商时,得到了一个表示$f_{0,1,\cdots,n-1}(x_0)$的漂亮的公式,因而把牛顿的差商插值公式改进了不少,他的观察是这样的:由定义\begin{align} f_0(x_1) &= \frac{f(x_1) - f(x_0)}{x_1-x_0} \\ &= f(x_0) \frac{1}{x_0 - x_1} + f(x_1) \frac{1}{x_1 - x_0} \end{align}从而\begin{array} { l }{ f _ { 0,1 } ( x _ { 2 } ) }\\{ = f _ { 0 } ( x _ { 2 } ) \frac { 1 } { x _ { 2 } - x _ { 1 } } + f _ { 0 } ( x _ { 1 } ) \frac { 1 } { x _ { 1 } - x _ { 2 } } }\\{ =\left[ f ( x _ { 0 } ) \frac { 1 } { x _ { 0 } - x _ { 2 } } + f ( x _ { 2 } ) \frac { 1 } { x _ { 2 } - x _ { 0 } } \right] \frac { 1 } { x _ { 2 } - x _ { 1 } } }\\{ +\left[ f ( x _ { 0 } ) \frac { 1 } { x _ { 0 } - x _ { 1 } } + f ( x _ { 1 } ) \frac { 1 } { x _ { 1 } - x _ { 0 } } \right] \frac { 1 } { x _ { 1 } - x _ { 2 } } }\\{ = f ( x _ { 0 } )\left( \frac { 1 } { x _ { 0 } - x _ { 2 } } - \frac { 1 } { x _ { 0 } - x _ { 1 } } \right) \frac { 1 } { x _ { 2 } - x _ { 1 } } + f ( x _ { 1 }) }\\{ \frac { 1 } { ( x _ { 1 } - x _ { 0 } ) ( x _ { 1 } - x _ { 2 } ) } + f ( x _ { 2 } ) \frac { 1 } { ( x _ { 2 } - x _ { 0 } ) ( x _ { 2 } - x _ { 1 } ) } }\\{ = f ( x _ { 0 } ) \frac { 1 } { ( x _ { 0 } - x _ { 1 } ) ( x _ { 0 } - x _ { 2 } ) } + f ( x _ { 1 } ) }\\{ \frac { 1 } { ( x _ { 1 } - x _ { 0 } ) ( x _ { 1 } - x _ { 2 } ) } + f ( x _ { 2 } ) \frac { 1 } { ( x _ { 2 } - x _ { 0 } ) ( x _ { 2 } - x _ { 1 } ) } } \end{array}看到了这样的结果以后,我们更猜想到一般公式该呈下形:$$(**) \qquad f_{0,1,\cdots,n-1}(x_n) = \sum^{n}_{i=0} f(x_i) \frac{1}{\prod_{j \neq i} (x_i-x_j)}$$其实确是如此,我们可以用数学归纳法证明这个结果.从上文我们看出这公式当$n=0$或$1$时是对的,假设这公式当$n-1$时成立,那么$f_{0,1,\cdots, n-1}(x_n)= f_{0,1,\cdots, n-2,n} (x_{n-1})\frac{1}{x_{n-1} -x_n}$ + $f_{0,1,\cdots, n-2}(x_n)$ $\frac{1}{x_n - x_{n-1}}$,应用数学归纳法的假定, 我们把 $f_{0,1,\cdots,n-2,n}(x_{n-1})$ 和 $f_{0,1,\cdots, n-2}(x_n)$ 展开,再分别用 $\frac{1}{x_{n-1} -x_n}$ 和 $\frac{1}{x_n - x_{n-1}} $ 乘展开式,便得到两式子, 我们分别用$A$和$B$表示,$A$的最末项是\begin{array} { l }{ f ( x _ { n - 1 } ) \frac { 1 } { \prod _ { j < n - 1 } ( x _ { n - 1 } - x _ { j } ) } \cdot \frac { 1 } { x _ { n - 1 } - x _ { n } } }\\{ = f (x_{ n - 1 } ) \frac { 1 } { \prod _ { j \neq n - 1 } ( x _ { n - 1 } - x _ { j } ) } } \end{array}$B$的最末项是\begin{array} { l }{ f ( x _ { n } ) \frac { 1 } { \prod _ { j < n - 1 } ( x _ { n } - x _ { j } ) } \cdot \frac { 1 } { x _ { n } - x _ { n - 1 } } }\\{ = f ( x _ { n } ) \frac { 1 } { \prod _ { j \neq n } ( x _ { n } - x _ { j } ) } } \end{array}而$A$中其余各项与$B$中的对应项的和是\begin{array} { l }{ f ( x _ { i } ) \frac { 1 } { \prod _ { j \neq i } ( x _ { i } - x _ { j } ) }\left( \frac { x _ { i } - x _ { n } } { x _ { n - 1 } - x _ { n } } + \frac { x _ { i } - x _ { n - 1 } } { x _ { n } - x _ { n - 1 } }\right) }\\{ = f ( x _ { i } ) \frac { 1 } { \prod _ { j \neq i } ( x _ { i } - x _ { j } ) } \quad ( i \neq n - 1 , n ) } \end{array}将各项合并起来,我们便得到了公式(**).
我们推出牛顿插值公式的法子是把牛顿定理施用到公式(*)上去,我们现在却想把牛顿定理施用到公式(**)上去,设$t(x)$为一个不超过$n$次的多项式,$x_0, x_1,\ldots,x_n,\bar{x}$为$n+2$个相异的点,由牛顿定理知$$t_{0,1,\cdots,n}(\bar{x}) =0$$从 (**) ,这式子表示$$\frac { t ( \overline { x } ) } { ( \overline { x } - x _ { 0 } ) ( \overline { x } - x _ { 1 } ) \cdots ( \overline { x } - x _ { n } ) } + \sum _ { i = 0 } ^ { n } t ( x _ { i } ) \frac { 1 } { \prod _ { j \neq i } ( x _ { i } - x _ { j } ) ( x _ { i } - \overline { x } ) } = 0$$所以$$t(\bar{x}) = \sum^{n}_{i=0} t(x_i) \frac{\prod_{j \neq i} (\bar{x} - x_j)}{ \prod_{j \neq i} (x_i- x_j)}$$这公式便是拉格朗日的插值公式.
这公式容易直接验证,在纯数学及应用数学上,这公式都有很大的用处.

埃德肯 (Aitken) 的插值法

上述的牛顿的插值公式拉格朗日插值公式虽然都很重要,但在计算的便捷上,远远不如埃德肯的插值法.
仍设$(x_0,y_0),(x_1,y_1),\ldots,(x_n,y_n)$为平面上的$n+1$个点,其横坐标两两不同,设$t(x)$为满足$$t(x_i)=y_i, \quad i=0,1,\cdots,n$$的$n$次多项式,$r(x)$为满足$$r(x_i)=y_i, \quad i=0,1,\cdots,n-1$$的$n-1$次多项式,$s(x)$为满足$$s(x_i)=y_i, \quad i=0,1,\cdots,n-2,n$$的$n-1$次多项式,则由牛顿差商插值公式得$$t(\bar{x})=r(\bar{x})+t_{0,1,\cdots,n-1}(x_n)(\bar{x}-x_0)\cdots(\bar{x}-x_{n-1})$$同理$$t(\bar{x})=s(\bar{x})+t_{0,1,\cdots,n-2,n}(x_{n-1})(\bar{x}-x_0) \cdots(\bar{x}-x_{n-2})(\bar{x}-x_n)$$但从差商的定义显然有$$t_{0,1,\cdots,n-1}(x_n) = t_{0,1,\cdots,n-2,n}(x_{n-1})$$因此$$(\bar{x}-x_n)t(\bar{x})+A=(\bar{x}-x_n)r(\bar{x}),$$$$(\bar{x}-x_{n-1})t(\bar{x})+A=(\bar{x}-x_{n-1})s(\bar{x})$$式中$$A=t_{0,1,\cdots,n-1}(x_n)(\bar{x}-x_0)(\bar{x}-x_n)$$故得$$t ( \overline { x } ) = \frac { \left| \begin{array} { l l } { ( \overline { x } - x _ { n } ) r ( \overline { x } ) } & { 1 } \\ { ( \overline { x } - x _ { n - 1 } ) s ( \overline { x } ) } & { 1 } \end{array} \right| } { \left| \begin{array} { l l } { \overline { x } - x _ { n } } & { 1 } \\ { \overline { x } - x _ { n - 1 } } & { 1 } \end{array} \right| } = \frac { \left| \begin{array} { l l } { ( \overline { x } - x _ { n - 1 } ) } & { r ( \overline { x } ) } \\ { ( \overline { x } - x _ { n } ) } & { s ( \overline { x } ) } \end{array} \right| } { \left| \begin{array} { l l } { \overline { x } - x _ { n - 1 } } & { 1 } \\ { \overline { x } - x _ { n } } & { 1 } \end{array} \right| }$$应用此公式,Aitken得到他计算$t( \bar{x} )$的方法:他仿照差商制成一表:\begin{array} { c c c c c } { \overline { x } - x _ { 0 } } & { y _ { 0 } } & { } & { } & { } \\ { \overline { x } - x _ { 1 } } & { y _ { 1 } } & { y _ { 0,1 } } & { } & { } \\ { \overline { x } - x _ { 2 } } & { y _ { 2 } } & { y _ { 0,2 } } & { y _ { 0,1,2 } } & { } \\ { \overline { x } - x _ { 3 } } & { y _ { 2 } } & { y _ { 0,3 } } & { y _ { 0,1,3 } } & { y _ { 0,1,2,3 } } \\ { \ldots } & { \ldots } & { \ldots } & { \ldots } & { \ldots } \end{array}其中各元素都可写作如上二行列式之商,例如$$y _ { 0,1,3 } = \frac { \left| \begin{array} { l l } { \overline { x } - x _ { 1 } } & { y _ { 01 } } \\ { \overline { x } - x _ { 3 } } & { y _ { 03 } } \end{array} \right| } { \left| \begin{array} { l l } { \overline { x } - x _ { 1 } } & { 1 } \\ { \overline { x } - x _ { 3 } } & { 1 } \end{array} \right| }$$表的右下角便给出 $ t( \bar{x} )$ 的值了.

用插值法求函数的近似值

设一函数$f(x)$在$n+1$个点$x_0,x_1,\ldots,x_n$的值为已知.这可能是查表或由实验方法得到的,我们常常希望知道$f(x)$在另外一点$\bar{x}$的值$f(\bar{x})$.如果$f(x)$是$n$次多项式,那么 $f(\bar{x})$便可用插值法求得,如果$f(x)$不是$n$次多项式呢?我们常常把$f(x)$假想成$n$次多项式$t(x)$,计算$f(\bar{x})$的值.用来当作$f(\bar{x})$,那么从公式(*)知所得的误差便是$R$项.但$R$会不会比较小呢?让我们从一个实例来看:设\begin{array}{l}f(x) = \frac{1}{1+x^2}, x_i = -5 + \frac{10}{n}i,y_i = f(x_i),\\i = 0,1,\cdots,n\end{array}下表列出一些$f(\bar{x})$及对不同分法所得的$t( \bar{x} )$的值

橫座標	1.02	2.34	3	3.88	4.15	4.91
縱座標	.490100	.154426	.100000	.062288	.054877	.039282
間隔數	補		間		法
2	.959985	.789400	.653846	.420985	.337596	.072765
3	.282394	.237239	.201357	.139718	.117644	.047542
5	.497362	.245889	.100000	.-039084	-.054607	.015979
8	.549575	.095381	.304934	.-088744	-.493703	-.436237
13	.504128	.180056	.059542	.210689	.138629	-.719234
21	.487368	.160295	.088963	-.131822	.430804	-16.8226
34	.490012	.154238	.108813	-.824165	3.45266	10063.8
50	.487850	.154304	.100000	6.75082	13.3392	-4418379

观察这表我们可以看出当 x 趋近于 0 时,误差实在不大,但当 x=4.91 时,误差随分点数增加到不可言喻的程度,所以用插值法求近似值,虽属可行,但未必有把握行得到.到底在什么条件下才行得通呢?这还是数学上一个没有完全解决的问题.