插值法：原理与应用【精制材料】

1、插值法：原理与应用,Zhenhua Song,1,行业相关,插值的背景,1. 只有n个点处的函数值 希望找到一条通过这些点的曲线（连续、光滑） 2. 函数太麻烦，近似简化 找到一个好计算的函数，近似代替 3. 用多项式代替 多项式方便求值、求导、积分等,2,行业相关,插值 & 逼近 & 拟合,0. 给定n个不同的点，构造曲线 1. 插值：曲线依次通过n个点 2. 逼近：曲线最接近n个点 （接近：在某种意义下） 例：最小二乘法 3. 拟合：插值 + 逼近,3,行业相关,泰勒展开,在某一点x0处展开 只在x0处近似性较好 远离x0的点误差较大 需要n个点近似性较好 插值可以胜任,4,行业相关,一次

2、插值,用一次函数近似表示,5,行业相关,二次插值,用二次函数来表示,6,行业相关,多项式插值 ：示例,给定的n+1个不同的点 找到一个n次多项式， 依次通过这n+1个点 n次多项式必然唯一,7,行业相关,多项式插值：唯一性,设n次多项式为 = 0 + 1 + 2 2 + 在这n+1个点上，满足n+1个方程 0 = 0 + 1 0 + 2 0 2 + 0 1 = 0 + 1 1 + 2 1 2 + 1 2 = 0 + 1 2 + 2 2 2 + 2 = 0 + 1 + 2 2 + ,8,行业相关,多项式插值：唯一性,把上述线性方程组写成矩阵形式 1 0 0 2 0 1 1 1 2 1 1 2 2

3、 2 2 1 2 0 1 2 = 0 1 2 系数矩阵行列式不为0： 范德蒙行列式， 0 到 互不相同 方程组解唯一 多项式系数唯一 插值多项式唯一,9,行业相关,拉格朗日插值,一种多项式插值算法 n次多项式 不用求解线性方程组 基函数线性组合 = 0 , 0 + 1 , 1 + , + , , 0 , , 1 , , , , , 称为基函数,10,行业相关,拉格朗日插值：2点情形, 1 = 0 1, 0 + 1 1, 1 我们希望通过 0 , 0 , 1 , 1 这2个点 可以取 1, 0 0 =1, 1,1 0 =0 1, 0 1 =0, 1,1 1 =1. 这样， 1 0 = 0 1,

4、0 0 + 1 1, 1 1 = 0 ， 1 1 = 0 1, 0 1 + 1 1, 1 1 = 1 如何实现上述条件？,11,行业相关,基函数的构建：2点情形,条件： 1, 0 0 =1, 1,1 0 =0 1, 0 1 =0, 1,1 1 =1. 构造一次多项式 构造： 1, 0 = 1 0 1 , 1, 1 = 0 1 0 分子是一次多项式 满足 1, =0 的条件 分母是系数，满足 1, =1 = 的条件 实质：=+的直线,12,行业相关,基函数的构建：n+1点情形,条件： 1, =0 , 1, =1 = 构造n次多项式 构造： , = 0 1 1 +1 0 1 1 +1 注意，分子没

5、有 ，分母没有 符合条件约束 实质： 每个基函数都是n次多项式,13,行业相关,拉格朗日插值：n+1点情形,插值函数： = 0 , 0 + 1 , 1 + , + , 基函数： , = 0 1 1 +1 0 1 1 +1 简洁形式： = =0 0 , 0 = =0 0 =0, ,14,行业相关,拉格朗日插值：误差估计,拉格朗日是一种近似，存在误差。 对于近似代替函数的情形。 误差分析： = +误差项 如果 +1 , , 误差项= +1 +1 ! =0 ,15,行业相关,拉格朗日插值：示例,对 =1/在 0 =2, 1 =2.75, 2 =4插值,16,行业相关,Nevile迭代插值,对于给定的

6、n+1个点 0 , 1 , 通过递推求出n次插值多项式 设 1 , 2 , 是的不同自然数 1 , 2 , 是定义在 1 , 2 , , ,17,行业相关,Nevile迭代插值,对于给定的k+1个点 0 , 1 , 插值多项式 在k+1个点上 在除去点j的k个点上的插值多项式 在除去点i的k个点上的插值多项式 = ,18,行业相关,Nevile迭代插值, 0,1 , 0 , 1 , 2 , 3 , 1,2 , 2,3 , 0,1,2 , 1,2,3 , 0,1,2,3 ,19,行业相关,牛顿差商插值,n次多项式写成多项式和： = 0 + 1 0 + 2 0 1 + 0 1 1 确定系数，可确定

7、插值多项式 经过n+1个点确定唯一n次多项式 系数可以由差分确定,20,行业相关,牛顿差商插值：系数确定,多项式： = 0 + 1 0 + 2 0 1 + 0 1 1 取值： 0 = 0 = 0 1 = 1 = 0 + 1 1 0 1 = 1 0 1 0 1 为差分形式 所有系数都可以写成差商形式 定义符号：,21,行业相关,牛顿差商插值：系数确定,定义符号： = 零阶差商 , +1 = +1 +1 一阶差商 , +1 , +2 = +1 , +2 , +1 +2 二阶差商 , +1 , +2 , , + = +1 , +2 , + , +1 , +1 + k阶差商 在 0 处差分： 0 =

8、0 = 0 , 0 , 1 = 1 0 处阶差分= ,22,行业相关,牛顿差商插值：公式导出, = 0 + =1 0 , 1 , 2 , , =0 1 定义符号： = 零阶差商 , +1 = +1 +1 一阶差商 , +1 , +2 = +1 , +2 , +1 +2 二阶差商 , +1 , +2 , , + = +1 , +2 , + , +1 , +1 + k阶差商,23,行业相关,牛顿差商插值：系数求解, 0, 1, 2, 3, 0 , 1, 1 , 2, 2 , 3, 0 , 1 , 2, 1 , 2 , 3, 0 , 1 , 2 , 3,24,行业相关,牛顿差商插值：间距相等,当n+

9、1个点等距排列时： 设= +1 = 0 + 插值多项式变形： = 0 + =1 0 , 1 , 2 , , =0 1 其中 = 0 + 0 + = =0 1 = =0 1 ,25,行业相关,牛顿差商插值：间距相等,变形处理： =0 1 = =0 1 组合数 = ! ! 定义广义组合数 = 1 +1 ! = =0 1 ! 广义组合数：s可以是任意实数. =0 1 = ! = 0 + =1 0 , 1 , 2 , , ! ,26,行业相关,牛顿差商插值：反向差商,之前，当n+1个点等距排列时： 设= +1 = 0 + 对于反向差分： = + 多项式形式与= 0 +类似。,27,行业相关,Hermi

10、te插值,拉格朗日插值缺点 在n+1个点处与 值相同 导数等不同 目的： 找到一个多项式函数 不光函数值相同 k阶导数相同 数学语言： = ,=0,1, ,28,行业相关,拉格朗日插值缺点,插值多项式形状、走向差异较大,29,行业相关,Hermite插值 ：优势,只取1个点时： 取m阶导数信息，相当于泰勒展开 取n+1个点时： 不考虑导数信息，相当于拉格朗日插值 具有更广泛的应用 生成的Hermite插值多项式唯一 在n+1个点，第i个点 阶导数相同,30,行业相关,Hermite ：一阶导数相同,在n+1个点处函数值相同，切线相同 需要2n+1阶多项式 条件： 1 , 0 , 1 , 2 ,

11、 , 思想： 与拉格朗日基函数思想相似,31,行业相关,Hermite：一阶导数相同, 2+1 = =0 , + =0 , 当= 时， 为了保证 2+1 = , 令 , =1, , =0 , , =0, , =0. 为了保证 2+1 = , 令 , =0, , =0 令 , =1, , =0,32,行业相关,Hermite : 一阶导数相同, 2+1 = =0 , + =0 , 其中， , = 12 , , 2 , = , 2 , 为拉格朗日基函数（第j个，n次多项式）,33,行业相关,回忆拉格朗日基函数,插值函数： = 0 , 0 + 1 , 1 + , + , 基函数： , = 0 1 1

12、 +1 0 1 1 +1 基函数 , 性质 在 处值为0， 在 处值为1.,34,行业相关,Hermite ：其他,误差分析 如果 2+2 , = 2+1 + 0 2 2 2+2 2 2+2 后面即为误差项. 也可以用差分形式表达 形式与n次多项式牛顿差分类似 并不是次数越高越精确 误差反而可能变大,35,行业相关,三次样条插值 ：背景,给定n+1个点 0 , 0 , , ， 0 1 2 分成n段，每一段：是一个分段函数 在 0, 处，分段函数取值为 尽可能保持光滑,36,行业相关,线段连接：粗糙,相邻两点用线段连接 形成折线，不够光滑,37,行业相关,三次样条插值：特性,每一段 , +1 用

13、3次多项式 表示 = , +1 = +1 . 或者说 +1 = +1 +1 分段函数在 +1 处连续 暂不考虑分段函数两端的情况 +1 = +1 +1 . 分段函数在 +1 处一阶导数相同 +1 = +1 +1 . 分段函数在 +1 处二阶导数相同 具有较好的光滑性,38,行业相关,三次样条插值：边界,对于两端点，处理如下： 0 0 = 0 , = 0 0 =0, =0.,39,行业相关,三次样条插值：构建,对于某一段 ,（不考虑端点） 设 = + + 2 + 3 + + 2 + 3 = 处函数值相同 + +1 + +1 2 + +1 3 = +1 +1 处函数值相同 +1 + 2 +1 +

14、3 +1 2 = +1 +1 + 2 +1 +1 + 3 +1 +1 2 +1 两端一阶导数值相同 2 + 6 +1 = 2 +1 + 6 +1 +1 +1 两端二阶导数值相同,40,行业相关,三次样条插值：构建,所有条件，可以组成线性方程组 =, 为稀疏矩阵 求解线性方程组，得到唯一解 三次样条缺点： 估计误差不方便,41,行业相关,三次样条插值：应用, = , 0 =0, 1 =1, 2 =2, 3 =3,42,行业相关,改变某一个点 ,43,行业相关,改变某一个点 ：对比,多项式插值： 牵一发动全身，整个多项式都变了 三次样条插值： 在 附近有较大影响，远离 处影响不大,44,行业相关,

15、多项式插值：对比,45,行业相关,参数曲线,对于n+1个点 0 , 0 , 1 , 1 , , +1 满足参数方程 以为参数 = , = n+1个点对应n+1个参数取值： 0 1 2 ,46,行业相关,参数曲线：图像,47,行业相关,三次参数曲线：定义,输入： 点 0 , 0 , 1 , 1 0 , 0 处切线上某点 0 + 0 , 0 + 0 1 , 1 处切线上某点 1 + 1 , 1 + 1 输出 = 是t的3次函数, = 是t的3次函数. 0 = 0 , 0 = 0 1 = 1 , 1 = 1 输出三次参数曲线唯一,48,行业相关,三次参数曲线：构造,设 = = 0 + 1 + 2 2 + 3 3 = = 0 + 1 + 2 2 + 3 3 满足条件 0 = 0 = 0 , 0 = 0 = 0 1 = 1 = 0 + 1 + 2 + 3 1 = 1 = 0 + 1 + 2 + 3 0 = 0 , 1 = 1 , 0 = 0 , 0 = 0 方程解唯一存在 8个未知量，