Chap-2.插值

掌握重点

掌握插值和代数插值的概念
熟练掌握差商的定义
掌握线性插值、二次插值与n次插值的推导过程、计算过程、在计算机上如何实现以及误差估计
掌握分段插值的概念、计算过程，在计算机上如何实现以及误差估计
了解Hermite插值和分段三次Hermite插值的推导过程和计算过程
掌握三次样条插值的推导过程和计算过程
了解求数值微分的方法。

插值和代数插值

设函数$y=f(x)$在区间$[a,b]$上有定义且已知在点$a\le x_0<x_1<…<x_n\le b$上的值$y_0，y_1,…,y_n$，若存在一简单函数$P(x)$，使 $P(x_i)=y_i，i=0,1,...,n$

成立，就称$P(x)$为$f(x)$的插值函数，点$x_0，x_1，…,x_n$称为插值节点，包含插值节点的区间$[a,b]$称为插值区间，求插值函数$P(x)$的方法称为插值法。若$P(x)$是次数不超过$n$的代数多项式，即 $P(x)=a_0+a_1x+\cdots+a_{n}x^{n}$ 其中$a_i$为实数,就称$P(x)$为插值多项式,相应的插值法称为多项式插值。若$P(x)$为分段的多项式,就称为分段插值.若$P(x)$为三角多项式,就称为三角插值。

简单来说，就是根据数据表构造出一个函数$\varphi(x)$来近似替代$f(x)$,如果这个$\varphi(x)$是一个代数多项式，则称为代数插值。

线性插值、二次差值、n次差值的拉格朗日形式

线性插值

给定区间$[x_0,x_1]$，端点值$y_0=f(x_0),\quad y_1=f(x_1)$，求插值多项式，使其满足$L_1(x_0)=y_0,\quad L_1(x_1)=y_1$

拉格朗日形式：由直线两点式方程转换而来 $L_1(x)=\frac{x-x_1}{(x_0-x_1)}y_0+\frac{x-x_0}{(x_1-x_0)}y_1 \\ 令l_0=\frac{x-x_1}{(x_0-x_1)}y_0 \quad l_1=\frac{x-x_0}{(x_1-x_0)}y_1 \\ L_1(x)=l_0(x)y_0+l_1(x)y_1$ 我们称$l_0(x),l_1(x)$为线性插值基函数，$y_0,y_1$为系数，在节点$x_0,x_1$上分别满足 $l_0(x_0)=1\quad l_1(x_0)=0 \\ l_0(x_1)=0\quad l_1(x_1)=1$

二次差值

给定区间$[x_0,x_1]$，端点值$y_0=f(x_0),\quad y_1=f(x_1),\quad y_2=f(x_2)$，求插值多项式，使其满足$L_2(x_0)=y_0,\quad L_2(x_1)=y_1,\quad L_2(x_2)=y_2$，基函数形式表示为： $L_2(x)=l_0(x)y_0+l_1(x)y_1+l_2(x)y_2 \\ 基函数应该为二次函数，在节点上分别满足条件 \\ \left\{ \begin{aligned} l_0(x_0)=1 & l_1(x_0)=0 & l_2(x_0)=0 \\ l_0(x_1)=0 & l_1(x_1)=1 & l_2(x_1)=0 \\ l_0(x_2)=0 & l_1(x_2)=0 & l_2(x_2)=1 \\ \end{aligned} \right.$ 以$l_0(x)$为例，使用待定系数法求基函数 $\because l_1(x_0)=0,l_2(x_0)=0 \quad \therefore 设 l_0(x)=A(x-x_1)(x-x_2) \\ 又\because l_0(x_0)=1 \quad \therefore A=\frac{1}{(x_0-x_1)(x_0-x_2)}$ 综上，二次插值的拉格朗日形式为 $L_2(x)=\frac{(x-x_1)(x-x_2)}{(x_0-x_1)(x_0-x_2)}y_0+ \\ \frac{(x-x_0)(x-x_2)}{(x_1-x_0)(x_1-x_2)}y_1+ \frac{(x-x_0)(x-x_1)}{(x_2-x_0)(x_2-x_1)}y_2+$

n次差值

通过上述类似的推导方法，可以得到$n$次插值基函数为： $l_k(x)=\frac{(x-x_0)\cdots(x-x_{k-1})(x-x_{k+1})\cdots(x-x_n)} {(x_k-x_0)\cdots(x_k-x_{k-1})(x_k-x_{k+1})\cdots(x_k-x_n)}$ 拉格朗日插值多项式$L_n(x)$为： $L_n(x)=\sum\limits_{k=0}^{n}y_kl_k(x) \\ 其中 \quad l_k(x)=\frac{w_{n+1}(x)}{(x-x_k)w_{n+1}'(x_k)} \\ w_{n+1}(x)=(x-x_0)\cdots(x-x_k)\cdots(x-x_n) \\ w_{n+1}'(x_k)=(x_k-x_0)\cdots(x_k-x_{k-1})(x_k-x_{k+1})\cdots(x_k-x_n)$

插值余项和误差估计

插值余项定义：若在$[a,b]$上用$L_n(x)$近似$f(x)$，其截断误差为$R_n(x)=f(x)-L_n(x)$，也称为插值多项式的余项
定理：设$f^{(n)}(x)$在$[a,b]$上连续，$f^{(n+1)}(x)$在$(a,b)$内存在，节点$a\le x_0<\cdots<x_n\le b$；$L_n(x)$是满足条件的插值多项式，对任何$x\in [a,b]$，插值余项 $R_n(x)=f(x)-L_n(x)=\frac{f^{(n+1)}(\xi)}{(n+1)!}w_{n+1}(x)$ $\xi \in(a,b)$，且依赖于$x$

证明：由插值函数的定义可知，余项在插值节点的值为0，即$R_n(x_k)=0$，由待定系数法，可以得到余项的多项式形式 $R_n(x)=K(x)(x-x_0)\cdots(x-x_n)=K(x)w_{n+1}(x)$ 将$x$当作$[a,b]$上的一个固定点，设函数 $\varphi(t)=f(t)-L_n(t)-K(x)(t-x_0)\cdots(t-x_n)$ 根据$f$的假设可以知道$\varphi ^{(n)}(t)$在$[a,b]$上连续，$\varphi^{(n+1)}(t)$在$(a,b)$内存在，$\varphi(x_k)=0$

根据罗尔定理：$\varphi ‘(t)$在$\varphi(t)$的两个零点之间至少有一个零点

已知$\varphi(t)$在$x_0,\cdots ,x_n$以及不动点$x$处均为零，共$n+2$个零点，所以$\varphi’(t)$在$[a,b]$内至少有$n+1$个零点，然后对$\varphi’(t)$再次用罗尔定理，以此类推

$\varphi^{(n+1)}(x)$内至少有一个零点，记为$\xi\in(a,b)$使得 $\varphi^{(n+1)}(\xi)=f^{(n+1)}(\xi)-(n+1)!K(x)=0 \\ K(x)=\frac{f^{(n+1)}(\xi)}{(n+1)!}$

余项表达式只有在$f(x)$的高阶导数存在时才能应用，求出$\max\limits_{a\le x\le b}\vert f^{(n+1)}(x)\vert =M_{n+1}$，插值多项式逼近原函数的截断误差限为 $\vert R_n(x)\vert \le \frac{M_{n+1}}{(n+1)!}\vert w_{n+1}(x)\vert$
定理：对于$f(x)=x^k,(k\le n)$，由于$R_n(x)=x^k - \sum\limits_{i=0}^n x_i^k l_i(x)=0$，所以 $x^k = \sum\limits_{i=0}^n x_i^k l_i(x),k\le n$

差商

拉格朗日插值的缺点：利用插值基函数可以容易得到拉格朗日插值多项式，公式结构紧凑，但当插值节点增减时，计算要全部重新进行

设计一种逐次生成插值多项式的方法，先考察$n=1$的情形，满足$P_1(x_0)=f(x_0),P_1(x_1)=f(x_1)$，点斜式表示为

\[P_1(x)=f(x_0)+\frac{f(x_1)-f(x_0)}{x_1-x_0}(x-x_0) \\ 可以当作零次插值 P_0(x)=f(x_0)的修正 \\ P_1(x)=P_0(x)+a_1(x-x_0) \\ a_1=\frac{f(x_1)-f(x_0)}{x_1-x_0}是函数f(x)的差商\]

然后考虑$n=2$的情况$P_2(x_0)=f(x_0)=P_1(x_0),P_2(x_1)=f(x_1)=P_1(x_1),P_2(x_2)=f(x_2)$，可以表示为

\[P_2(x)=P_1(x)+a_2(x-x_0)(x-x_1) \\ a_2= \frac{P_2(x_2)-P_1(x_2)}{(x_2-x_0)(x_2-x_1)} \\ = \frac{f(x_2)-(f(x_0)+\frac{f(x_1)-f(x_0)}{x_1-x_0}(x_2-x_0))} {(x_2-x_0)(x_2-x_1)} \\ =\frac{\frac{f(x_2)-f(x_0)}{x_2-x_0}-\frac{f(x_1)-f(x_0)}{x_1-x_0}} {x_2-x_1} \\ a_2是函数f(x)的差商\]

推广到一般情况，$f(x)$有$n+1$个插值节点，$n$次插值多项式$P_n(x)$满足条件$P_n(x_i)=f(x_i)$，插值多项式表示为 $P_n(x)=a_0+a_1(x-x_0)+\cdots+a_n(x-x_0)\cdots(x-x_{n-1})$ 和拉格朗日插值不同，$P_n(x)$由基函数${1,x-x_0,\cdots,(x-x_0)\cdots(x-x_{n-1})}$逐次递推得到，为了给出系数$a_i$的表达式，需要引入差商的定义
一阶差商定义： $f[x_0,x_k]=\frac{f(x_k)-f(x_0)}{x_k-x_0}$ 为函数$f(x)$关于点$x_0,x_k$的一阶差商

二阶差商定义： $f[x_0,x_1,x_k]=\frac{f[x_0,x_k]-f[x_0,x_1]}{x_k-x_1}$ $k$阶差商定义： $f[x_0,x_1,\cdots,x_k]=\frac {f[x_0,x_1,\cdots,x_{k-2},x_{k}]-f[x_0,x_1,\cdots,x_{k-2},x_{k-1}]} {x_k-x_{k-1}}$
差商的基本性质：
- $k$阶差商可以表示为函数值$f(x_0),\cdots,f(x_{k})$的线性组合 $f[x_0,\cdots,x_k]=\sum\limits_{j=0}^k \frac{f(x_j)}{(x_j-x_0)\cdots(x_j-x_{j-1})(x_j-x_{j+1})\cdots(x_j-x_k)} \\ = \sum\limits_{j=0}^k\frac{x_j}{w_{k+1}'(x_j)}$ 归纳法证明，此性质也可以证明均差和节点的排列次序无关，称为均差的对称性
- 通过上一个性质可以得到 $f[x_0,\cdots,x_k]=\frac {f[x_1,\cdots,x_k]-f[x_0,\cdots,x_{k-1}]}{x_k-x_0}$
- 若$f(x)$在$[a,b]$上存在$n$阶倒数，且节点$x_0,\cdots,x_n \in[a,b]$，则$n$阶差商和导数的关系为 $f[x_0,\cdots,x_n]=\frac{f^{(n)}(\xi)}{n!}$ 罗尔定理证明
差商计算可以列出差商表（通过上面第二条性质） $\begin{vmatrix} x_k & f(x_k) & 一阶差商 & 二阶差商 & 三阶差商 & 四阶差商\\ x_0 & f(x_0) & & & &\\ x_1 & f(x_1) & f[x_0,x_1] & & &\\ x_2 & f(x_2) & f[x_1,x_2] & f[x_0,x_1,x_2] & &\\ x_3 & f(x_3) & f[x_3,x_2] & f[x_1,x_2,x_3] & f[x_0,x_1,x_2,x_3] &\\ x_4 & f(x_4) & f[x_4,x_3] & f[x_2,x_3,x_4] & f[x_1,x_2,x_3,x_4] & f[x_0,x_1,x_2,x_3,x_4]\\ \end{vmatrix}$

线性插值、二次差值、n次差值的牛顿形式

牛顿插值多项式定义： $P_k(x)=P_{k-1}(x)+f[x_0,\cdots,x_k](x-x_0)\cdots(x-x_{k-1}) \\ 递推得到牛顿插值多项式 \\ P_n(x)=f(x_0)+f[x_0,x_1](x-x_0)+f[x_0,x_1,x_2](x-x_0)(x-x_1)+\cdots \\ +f[x_0,\cdots,x_n](x-x_0)\cdots(x-x_{n-1}) \\ 插值余项为 \\ R_n(x)=f[x,x_0,\cdots,x_n]w_{n+1}(x)$ 推导过程：根据差商定义，将$x$当作$[a,b]$上的一点，即$x_{-1}$，根据差商性质第二条 $f(x)=f(x_0)+f[x,x_0](x-x_0) \\ f[x,x_0]=f[x_0,x_1]+f[x,x_0,x_1](x-x_1) \\ \vdots \\ f[x,x_0,\cdots,x_{n-1}]=f[x_0,\cdots,x_n]+f[x,x_0,\cdots,x_n](x-x_n) \\ 递推得到 \\ f(x)=f(x_0)+f[x_0,x_1](x-x_0)+\cdots+f[x_0,\cdots,x_n] (x-x_0)\cdots(x-x_{n-1}) \\+f[x,x_0,\cdots,x_n](x-x_0)\cdots(x-x_{n}) \\ =P_n(x)+R_n(x)$

Hermite插值

要求插值函数在插值节点上的值相同，也要求在插值节点的一阶导数相同。

定理：设$f\in C^n[a,b]$，$x_0\cdots x_n$为区间内的相异节点，则$f[x_0,x_1,\cdots,x_n]$是其变量的连续函数（证明略）

根据差商的定义，有 $\lim\limits_{x\rightarrow x_0}f[x_0,x]= \lim\limits_{x\rightarrow x_0}\frac{f(x)-f(x_0)}{x-x_0}=f'(x_0) \\$
$n$重节点差商定义：根据上面的定理，定义重节点均差 $f[x_0,x_0]=\lim\limits_{x\rightarrow x_0}f[x_0,x]=f'(x_0)$ 同理可推 $\lim\limits_{x\rightarrow x_0}f[x_0,x_0,x]= \lim\limits_{x\rightarrow x_0}\frac{f[x,x_0]-f[x_0,x_0]}{x-x_0} =\lim\limits_{x\rightarrow x_0}\frac{f'(x)-f'(x_0)}{x-x_0}=f''(x_0) \\ f[x_0,x_0,x_0]=\lim\limits_{x_1\rightarrow x_0 x_2 \rightarrow x_0} f[x_0,x_1,x_2]=\frac{1}{2}f''(x_0)$ 一般地 $f[x_0,x_0,\cdots,x_0]=\frac{1}{n!}f^{(n)}(x_0)$
泰勒多项式定义：在牛顿差商插值多项式中，若令所有的$x_i\rightarrow x_0$，从$n$重节点差商可以得到泰勒多项式 $P_n(x)=f(x_0)+f'(x_0)(x-x_0)+\cdots+\frac{f^{(n)}(x_0)}{n!}(x-x_0)^n$ 由于泰勒多项式是在$x_0$附近逼近$f(x)$的带导数的插值多项式，其满足条件$P_n^{(k)}(x_0)=f^{(k)}(x_0)$，所以它是一个埃尔米特插值多项式，其余项为 $R_n(x)=\frac{f^{(n+1)}(\xi)}{(n+1)!}(x-x_0)^{n+1}$ 泰勒插值是牛顿插值的极限形式

三次Hermite插值

三次Hermite插值函数定义：给定$f(x)$的函数表，构造函数$H(x)$满足条件 $\begin{vmatrix} x & x_0 & x_1 \\ y=f(x) & y_0 & y_1 \\ y'=f'(x) & m_0 & m_1 \end{vmatrix}$
- $H(x)$不超过3次的代数多项式
设$H(x)=y_0h_0(x)+y_1h_1(x)+m_0H_0(x)+m_1H_1(x)$，满足 $\begin{vmatrix} & 函数值 & & 导数值 & \\ & x_0 & x_1 & x_0 & x_1 \\ h_0(x) & 1 & 0 & 0 & 0 \\ h_1(x) & 0 & 1 & 0 & 0 \\ H_0(x) & 0 & 0 & 1 & 0 \\ H_1(x) & 0 & 0 & 0 & 1 \\ \end{vmatrix}$ 得到 $h_0=(1+2\frac{x-x_0}{x_1-x_0})(\frac{x-x_0}{x_1-x_0})^2 \\ h_1=(1+2\frac{x-x_1}{x_0-x_1})(\frac{x-x_1}{x_0-x_1})^2 \\ H_0=(x-x_0)(\frac{x-x_1}{x_0-x_1})^2 \\ H_1=(x-x_1)(\frac{x-x_0}{x_1-x_0})^2 \\$
Hermite插值误差

设$H(x)$是$f(x)$的三次Hermite插值，$[a,b]$是包含$x_0,x_1$的任一区间，总存在一点$\xi \in (a,b)$，使得 $R(x)=f(x)-H(x)=\frac{f^{4}(\xi)}{4!}(x-x_0)^2(x-x_1)^2$
$2n+1$次插值及其余项

分段插值

对于给定的$n+1$个节点可以构造出唯一的$n$阶插值多项式，但并不是差值多项式的次数越高，误差就越小。所以可以分区间分段进行差值，在每个分段内部进行低次的差值。

分段线性插值

分段线性插值就是通过折线段连接插值节点逼近$f(x)$，在每个小区间$[x_k,x_{k+1}]$上可以表示为 $I_h(x)=\frac{x-x_{k+1}}{x_k-x_{k+1}}f_k+\frac{x-x_{k}}{x_{k+1}-x_{k}}f_{k+1}\\ x_k\le x\le x_{k+1}$ 误差估计通过插值余项可以得到 $\max\limits_{x_k\le x\le x_{k+1}}\vert f(x)-I_h(x)\vert \le \frac{M_2}{2}\max\limits_{x_k\le x\le x_{k+1}}\vert (x-x_k)(x-x_{k+1})\vert \\ M_2=\max\limits_{a\le x\le b}\vert f''(x)\vert$

分段三次Hermite

分段线性插值函数的导数是间断的，如果在插值节点上除了知道函数值$f(x_k)$，还知道导数值$f’(x_k)=m_k$，可构造一个导数连续的分段插值函数，每个小区间上$I_h(x)$是三次多项式

（太复杂了不考）

基函数这一部分应该了解就可以，不要求完全写出。

误差：

计算机算法实现：

三次样条插值

分段三次Hermite插值只有一阶导数连续，二阶导数不连续。而且实际过程中难以给出导数条件。三次样条差值利用二阶导数相等和边界情况创造条件，进行插值。

三次样条函数定义：函数$S(x)\in C^2[a,b]$，在每个小区间$[x_j,x_{j+1}]$上是三次多项式，则称$S(x)$是节点$x_0,\cdots,x_n$上的三次样条函数；$S(x_j)=y_j$成立
根据定义可知，每个小区间上的三次样条函数有4个待定系数，所有区间总共$4n$个参数；样条函数满足连续型条件，总共$4n-2$个条件 $S(x_j)=y_j \\ S(x_j-0)=S(x_j+0)\\ S'(x_j-0)=S'(x_j+0)\\ S''(x_j-0)=S''(x_j+0)$ 需要再增加2个条件才能确定$S(x)$，通常在端点上个加上一个条件（边界条件），有一下三种：
- $S’(x_0)=f_0’,S’(x_n)=f_n’$
- $S’‘(x_0)=f_0’‘,S’‘(x_n)=f_n’’$
  
  特殊的，$S’‘(x_0)=S’‘(x_n)=0$称为自然边界条件
- 周期样条函数（省略）

样条插值函数的建立

有多种方法可以构造三次样条插值函数，满足插值条件和相应的边界条件

分段三次埃米尔特插值：假定$S’(x_j)=m_j$，满足$S(x_j)=y_j$，得到 $S(x)=\sum\limits_{j=0}^{n}[y_j\alpha_j(x)+m_j\beta_j(x)] \\ \alpha_k(x)=(1+2\frac{x-x_{k+1}}{x_k-x_{k+1}})(\frac{x-x_k}{x_{k+1}-x_k})^2\\ \beta_k(x)=(x-x_k)(\frac{x-x_{k+1}}{x_k-x_{k+1}})^2$ $\alpha_j(x),\beta_j(x)$之前得到的插值基函数，通过之前的插值条件和边界条件，构造关于$m_j$的三对角方程组，解$m_j$得到所求的三次样条函数$S(x)$

（后面太复杂不考）

Chap-2.插值

Chap-2.插值

掌握重点

插值和代数插值

线性插值、二次差值、n次差值的拉格朗日形式

线性插值

二次差值

n次差值

插值余项和误差估计

差商

线性插值、二次差值、n次差值的牛顿形式

Hermite插值

三次Hermite插值

分段插值

分段线性插值

分段三次Hermite

三次样条插值

数值微分

CATALOG

FEATURED TAGS