插值方法（多项式插值）
最后更新时间:
引言
例子：容格函数
情形
- 函数以表格的形式呈现
- 函数有解析式但太复杂不便于计算
插值函数的目的是: (1)用更精炼的函数描述离散数据 (2)构造既能反映函数本身性质又能便于计算的简单函数 ## 插值方法概括 由于多项式函数的形式最简单且便于计算,本节主要讨论的都是多项式插值理论和构造方法. - Lagrange插值方法.由基函数构造,容易拓展到高维 - Newton插值方法.适合增减插值节点的情况 - Hermit插值方法. - 分段插值方法.为避免Runge现象. # 插值问题 ## 插值问题定义 - 被插值函数 - 插值节点 - 插值条件 - 插值多项式 - 插值余项,也即误差 ## 插值多项式的存在唯一性定理 定理:给定互异的n+1个节点及其对应函数值，则存在唯一次数不超过n的多项式满足已给定的n+1个插值条件。
定理证明：Vandermond矩阵 实际求解线性方程组不会这样做（ 待定系数法） - 这个矩阵是病态的 - 待定系数法计算量大 - 存在唯一性指的是待定的系数是存在且唯一的，多项式的表示形式是多样的不唯一的
余项公式定理
这个定理用来说明插值多项式对被插值函数的逼近程序的好坏.
定理:设\(x_0,x_1,\cdots,x_n\)是\([a,b]\)内\(n+1\)个互不相同的插值节点,且\(x\in[a,b]\).又设\(f\in C^{n+1}([a,b])\).则插值多项式\(p_n\in P_n\)在\(x\)点处的插值余项为,
\[ R_n(x)=f(x)-p_n(x)=\frac{f^{(n+1)}(\xi_x)}{(n+1)!}\pi_{n+1}(x) \]
其中,\(\xi_x\in(a,b)\),\(\pi_{n+1}(x)\)为\(n+1\)次节点多项式,即,
\[ \pi_{n+1}(x)=\prod_{i=0}^{n}(x-x_i) \]
证明:构造辅助函数.
\[ \phi(T)=f(T)-p_n(T)-\frac{f(x)-p_n(x)}{\pi_{n+1}(x)}\pi_{n+1}(T),T\in [a,b] \]
容易验证,辅助函数有\(n+2\)个零点,分别\(x,x_0,x_1,\cdots,x_n\).应用Rolle定理, 可以证明存在\(\xi_x\in(a,b)\),使得,
\[ \phi^{(n+1)}(\xi_x)=0 \]
于是对辅助函数求n+1次导有,
\[ \phi^{(n+1)}(\xi_x)=f^{(n+1)}(\xi_x)-0-\frac{f(x)-p_n(x)}{\pi_{n+1}(x)}(n+1)!=0 \]
整理后得证.
- 这个定理说明了插值多项式对被插值函数逼近程度的好坏
- 证明是构造函数之后用Rolle定理
- 首系数为1的n+1次多项式求n+1次导结果为\((n+1)!\)
Lagrange插值方法
Lagrange插值方法主要避免了待定系数法的两个问题: - 求解线性方程组的计算量大 - 范德蒙德矩阵是病态的,所以待定系数法得到的插值多项式是不可靠的 ## L插值定理 定理:设\(x_0,x_1,\cdots,x_n\)为\(n+1\)个互异节点,被插值函数\(f(x)\)在插值节点的函数值已知.那么存在唯一次数不超过\(n\)的L插值多项式\(L_n(x)\in P_n\),满足插值条件,
\[ L_n(x_k)=f(x_k),k=0,1,\cdots,n \]
而\(L_n(x)\)多项式形如,
\[ L_n(x)=\sum_{k=0}^{n}l_{k,n}(x)f(x_k) \]
其中,
\[ l_{k,n}(x)=\prod_{i=0,i\neq k}^{n}\frac{x-x_i}{x_k-x_i},k=0,1,\cdots,n \]
证明:由基函数要满足如下性质:
\[ l_{k,n}(x_j)=\left\{\begin{matrix} 1,j=k\\ 0,j\neq k \end{matrix}\right. \quad j,k=0,1,\cdots,n \]
易知,\(l_{k,n}(x)\)含有因子\(\prod_{i=0,i\neq k}^{n}(x-x_i)\),又由于这个因子与\(l_{k,n}(x)\)的次数相同为n,因此两者间只差一个常数.又由\(l_{k,n}(x_k)=1\)可以推得定理结论.
- 插值基函数 也叫特征多项式
- 基函数这三个字其实体现的就是一种正交性
- 被插值函数为多项式的插值多项式就是它本身，从余项公式为0可以看出
- 变形形式 记\(\pi_{n+1}(x)=\prod_{i=0}^{n}(x-x_i)\),则基函数可以表示成,
\[ l_{k,n}(x)=\frac{\pi_{n+1}(x)}{x-x_k}\cdot \frac{1}{\pi_{n+1}'(x_k)},k=0,1,\cdots,n \]
L插值算法
2.3.2.1 可以发现插值基函数只与节点有关，可以提前计算出所需要的基函数 多元插值的方法（后面介绍
Neville插值方法(略过了?)
Newton插值方法
引出
给定n+1个节点，Newton插值的目的同样是要找到一个次数不超过n次的多项式\(N_n(x)\)，既满足插值条件，且同时\(N_n(x)\)可以表示成\(N_{n-1}(x)\)和一个次数不超过n次的多项式的和的形式，也即，
\[ N_n(x)=N_{n-1}(x)+q(x) \]
优点
- 本质是L插值多项式的等价形式
- 牛顿法最大的优点是当需要增加一个节点时可以在原来的基础上加上一项，而拉格朗日法则要完全重新计算（基函数，整个插值多项式都要重新算） ## 牛顿差商 由插值条件知，
\[ q(x_i)=N_n(x_i)-N_{n-1}(x_i)=0,\quad i=0,1,\cdots,n-1 \]
因此,\(q(x)\)应该含有因子\(\prod_{i=0}^{n-1}(x-x_i)\),由于两者都是n次的多项式,所以他们之间只相差一个常数,而这可以用插值条件\(N_n(x_n)=y_n\)确定.
\[ N_n(x_n)=N_{n-1}(x_n)+q(x_n) \]
\[ y_n-N_{n-1}(x)=q(x_n)=a_n\prod_{i=0}^{n-1}(x_n-x_i)=a_n\pi_n(x_n) \]
故有,
\[ a_n=\frac{y_n-N_{n-1}(x_n)}{\pi_n(x_n)} \]
系数\(a_n\)被称为牛顿差商. 记为,
\[ a_n=f[x_0,x_1,\cdots,x_n],n\geq1 \]
牛顿差商是什么
Newton差商实际上是多项式的一个系数。 有了牛顿差商,我们可以把牛顿插值多项式改写一下,
\[ N_n(x)=N_{n-1}(x)+a_n\pi_n(x)=\sum_{i=0}^{n}a_i\pi_i(x) \]
其中,我们规定\(f[x_0]=y_0,\pi_0(x)=1\).
由插值多项式的唯一性,可知,Newton插值多项式跟Lagrange插值多项式是等价的.
差商的性质
公式
\[ a_n=\frac{y_n-N_{n-1}(x_n)}{\pi_n(x_n)} \]
虽然给出了一种计算差商的办法,但是要用到\(N_{n-1}(x_n)\),这并不便于计算. 通过对牛顿差商性质的了解,我们可以给出更加实用的Newton插值多项式的构造方法. #### Newton差商性质 - 差商与节点的排序无关 首项系数与 Lagrange插值多项式的首项系数一致 L插值多项式的首系数也是N插值多项式的首系数,也就是n阶Newton差商.
\[ f[x_0,x_1,\cdots,x_n]=\sum_{i=0}^{n}\frac{y_i}{\pi_{n+1}'(x_i)} \]
- 差商具有线性性质，若\(f=\alpha g+\beta h\),那么
\[ f[x_0,x_1,\cdots,x_n]=\alpha g[x_0,x_1,\cdots,x_n]+\beta h[x_0,x_1,\cdots,x_n] \]
- 递推公式
\[ f[x_i,x_{i+1},\cdots,x_n]=\frac{f[x_{i+1},\cdots,x_n]-f[x_i,\cdots,x_{n-1}]}{x_n-x_i},n\geq 1 \]
- 差商与高阶导数的联系 设\(f\in C^n[a,b],x_i,i=0,1,\cdots,n\)是\([a,b]\)中互异节点,则存在\(\xi\in[a,b]\)使得,
\[ f[x_0,x_1,\cdots,x_n]=\frac{f^{(n)}(\xi)}{n!} \]
值得注意的是,如果所有节点\(x_0,x_1,\cdots,x_n\)都重合(认为是一种极限过程),这牛顿差商退化成,
\[ f[x,x,\cdots,x]=\frac{f^{(n)}(x)}{n!} \]
进而,Newton插值多项式退化成Taylor多项式. - Leibniz公式,若\(f=gh\)，那么
\[ f[x_0,x_1,\cdots,x_n]=\sum_{j=0}^{n}g[x_0,x_1,\cdots,x_j]\cdot h[x_j,x_1,\cdots,x_n] \]
Newton插值算法
差商表 1. 构建差商表 2. 取对角线
Horner方法 将Newton插值多项式写成嵌套形式
N插值多项式的误差
\[ R_n(x)=f[x_0,x_1,\cdots,x_n,\textbf{x}]\pi_{n+1}(x) \]
证明: 关于\(x_0,x_1,\cdots,x_n\)以及\(x\)构造\(N_{n+1}(x)\),
\[ N_{n+1}(t)=N_{n}(t)+f[x_0,x_1,\cdots,x_n,x]\pi_{n+1}(t) \]
这里我们应该要注意到插值多项式\(N_{n+1}(t)\)在\(t=x\)处的插值条件就是
\[ N_{n+1}(x)=f(x) \]
因此将式子中的t用x替换,即得,
\[ N_{n+1}(x)-N_{n}(x)=f[x_0,x_1,\cdots,x_n,x]\pi_{n+1}(x) \]
\[ f(x)-N_{n}(x)=f[x_0,x_1,\cdots,x_n,x]\pi_{n+1}(x) \]
于是,就证明了\(R_n(x)=f[x_0,x_1,\cdots,x_n,\textbf{x}]\pi_{n+1}(x)\). # 差分与等距节点 当插值节点等距的时候,可以对Newton插值多项式进一步化简.为此,我们需要引入差分的概念.
基本概念
差分
定义:设在等距节点\(x_i=x_o+ih,i=0,1,2,\cdots,n\)上,已知函数\(f(x)\)的值为\(y_0,y_1,\cdots,y_n\),其中\(y>0\)为相邻两个节点的步长.称,
\[ \Delta^1f_i=f_{i+1}-f_i,i=0,1,2,\cdots,n \]
- 零阶差分 定义为:\(\Delta^0f_i=f_i,i=0,1,2,\cdots,n\)
- m阶向前差分
\[ \Delta^mf_i=\Delta^{m-1}f_{i+1}-\Delta^{m-1}f_i=\Delta^{m-1}(f_{i+1}-f_i)=\Delta^{m-1}\Delta^{1}f_i,i=0,1,2,\cdots,n \]
差分性质
- 差分与牛顿差商的关系
\[ f[x_0,x_1,\cdots,x_m]=\frac{\Delta^mf_0}{m!h^{m}} \]
\[ f[x_i,x_{i+1},\cdots,x_{i+m}]=\frac{\Delta^mf_i}{m!h^{m}} \]
- 高阶差分与函数值的关系
\[ \Delta^mf_i=\sum_{j=0}^{m}(-1)^{j}C_{j}^{m}f_{i+m-j} \]
Newton向前差分公式
\[ N_n(x)=\sum_{i=0}^{n}f[x_0,x_1,\cdots,x_i]\pi_i(x)=\sum_{i=0}^{n}\frac{\Delta^if_0}{i!h^{i}}\pi_i(x) \]
再做线性替换\(x=x_0+th,\quad 0\leq t\leq n\),则\(x-x_i=(t-i)h,i=0,1,2,\cdots,n\),上面的公式可以简化为,
\[ N_n(x_0+th)=\sum_{i=0}^{n}\frac{\Delta^if_0}{i!h^{i}}\pi_i(x_0+th)=\sum_{i=0}^{n}\frac{\Delta^if_0}{i!h^{i}}\prod_{j=0}^{i-1}(h(t-j))=\sum_{i=0}^{n}\frac{\Delta^if_0}{i!}\prod_{j=0}^{i-1}(t-j) \]
类似的,可以把插值余项公式简化成,
\[ R_n(x)=\frac{h^{n+1}f^{(n+1)}(\xi_x)}{(n+1)!}\prod_{j=0}^{n}(t-j) \]
注:类似向前差分,我们可以定义向后差分,
\[ \nabla^1f_i=f_{i}-f_{i-1} \]
有差不多的结论,区别在于,向前差分公式适合在右侧增加节点,向后差分公式则是向左.
Hermit插值
满足插值条件和导数条件的插值
Hermit插值与前面插值方法最大的区别就是,在插值节点处除了满足插值条件外,还需要满足导数插值条件. ## 几何意义 这种方式构造的插值函数,除了过插值节点外,还保持了在节点处的光滑性 ## 构造H多项式 2.7.3.1 一种构造 2.7.3.2 Newton 插值余项 一般情况下，同次数的尔米特多项式比拉格朗日多项式更精确 # Runge现象和分段插值 容格现象启示：不要轻易使用高次插值多项式. ## 分段插值 主要思想是将插值区间划分成一个个小区间,在每个小区间上用低次的插值多项式逼近函数. 最简单的一种方法就是分段线性插值.
分段线性插值
分段插值的几何意义就是:在每个小区间内用直线段连起来. 定义:(分段插值函数)
函数空间维数
2.8.2.1.1 自由度条件 2.8.2.1.2 连续性条件 ### 分段线性插值多项式具有一致收性
分段线性和分段三次hermit插值
样条插值
弹性势能最小的插值方式，稳定性很好 分段线性插值多项式的光滑性差,只有连续性. 而分段3次Hermit插值具有一阶可导性,但是要知道节点处的导数值才行.
3次样条插值多项式
定义: 设\(f(x)\)为定义在区间\([a,b]\)内的函数,已知\(f(x)\)在区间\([a,b]\)内的\(n+1\)个互异的点\(a\leq x_0<x_1<\cdots<x_n\leq b\)处的函数值为\(y(x_i)=y_i,i=0,\cdots,n\).设\(s_3(x)\)是定义在区间\([a,b]\)上的函数,若\(s(x)\)满足以下条件, - (局部性质)\(s(x)\)在每个小区间\([x_i,x_{i+1}],i=0,\cdots,n-1\)内是次数不超过3次的多项式 - (插值条件)\(s(x)\)满足插值条件\(s(x_i)=y_i,i=0,\cdots,n\) - (整体性质)\(s(x)\)是插值区间上的二阶连续可导函数
则称\(s(x)\)是插值区间内的3次样条插值函数,简称3次样条.
定义如下函数空间
\[ S^{2,3}=\{s\in C[a,b]|s_{I_i}\in P_3(I_i),I_i=[x_i,x_{i+1}],i=0,\cdots,n-1]\} \]
该空间的维度为\(4n-(3n-3)=n+3\),即3次样条自由度为\(n+3\),插值条件提供了\(n+1\)个自由度,于是发现,我们还需要额外的两个自由度.
边界条件
由于求解仍缺少两个自由度,而缺少的只能由插值区间\([a,b]\)的两个端点给出,我们称由端点给出的条件为边界条件.
边界条件通常有三类: - 自然边界条件
\[ s''(x_0)=s''(x_n)=0 \]
这样构造的样条称为自然样条. - 固支边界条件
\[ s''(x_0)=y'_0\quad s''(x_n)=y'_n \]
固支边界条件包含了更多信息,通常比自然条件更精确, 这样构造的样条称为固支样条. - 循环边界条件
\[ s(x_0)=s(x_n) \]
\[ s'(x_0)=s'(x_n) \]
\[ s''(x_0)=s''(x_n) \]
这样构造的样条称为周期样条.
三次样条的构造
三弯矩构造法(解线性方程组)
三弯矩构造法利用3次样条在内部节点上的二阶连续可导性化简计算,将问题化简为求解线性方程组.
构造过程: 记3次样条在节点处的二阶导数值为\(M_i=s''(x_i),i=0,\cdots,n\).由于\(s''(x)\)在每个小区间上都是一次多项式,故有,
\[ s''_i(x)=\frac{x_{i+1}-x}{h_i}M_i+\frac{x-x_{i}}{h_i}M_{i+1} \]
其中\(h_i=x_{i+1}-x_i\),将上面的式子积分两次,有
留空（）
总之利用完插值条件和一阶连续可导的条件后,得到,
\[ \mu_{i+1}M_i+2M_{i+1}+\lambda_{i+1}M_{i+2}=d_{i+1} \]
其中
\[ \begin{cases} \mu_{i+1}=\frac{h_i}{h_i+h_{i+1}}\\ \\ \lambda_{i+1}=\frac{h_{i+1}}{h_i+h_{i+1}}\\ \\ d_{i+1}=6f[x_i,x_{i+1},x_{i+2}] \end{cases} \]
接下来考虑边界条件 (1) 自然边界 即已知\(M_0=M_n=0\),所以得到的线性方程组为,
(2) (3)