西安科技大学 研究生 数值分析课件4插值法

1、 4 插值法插值法 （ Interpolation method ） 本章主要内容本章主要内容 4.1 函数插值的基本问题函数插值的基本问题 4.2 拉格朗日插值拉格朗日插值 4.3 牛顿插值牛顿插值 4.4 埃尔米特插值埃尔米特插值 4.5 分段低次插值分段低次插值 4.6 三次样条插值三次样条插值 重点：重点：各种插值算法的思路及插值公式的构造各种插值算法的思路及插值公式的构造 难点：难点：各种插值算法误差估计，样条插值各种插值算法误差估计，样条插值 插值法更多的插值法更多的是作为其它数是作为其它数值方法的基础值方法的基础 4.1 函数插值的基本问题函数插值的基本问题 4.1.1 插值问题

2、的基本概念插值问题的基本概念 函数插值的必要性函数插值的必要性n 使复杂函数简单化使复杂函数简单化n 使无解析式的函数（离散型、图形图像）获得解析式使无解析式的函数（离散型、图形图像）获得解析式n 为其他数值方法提供支持手段（如数值积分、微分）为其他数值方法提供支持手段（如数值积分、微分） 插值问题插值问题定义定义4-1 4.1 函数插值的基本问题函数插值的基本问题 4.1.1 插值问题的基本概念插值问题的基本概念 代数多项式插值问题代数多项式插值问题 由于多项式有其优良的特性，所以通常都是用多项式作为由于多项式有其优良的特性，所以通常都是用多项式作为插值函数。还有其它类型的插值函数，如有理函

3、数插值、插值函数。还有其它类型的插值函数，如有理函数插值、三角函数插值等三角函数插值等 函数插值涉及的基本问题函数插值涉及的基本问题n插值函数的存在唯一性问题插值函数的存在唯一性问题n插值函数的构造问题插值函数的构造问题n截断误差估计与收敛性问题截断误差估计与收敛性问题n数值稳定性问题数值稳定性问题 代数多项式插值函数的构造方法代数多项式插值函数的构造方法 拉格朗日插值法拉格朗日插值法 埃尔米特插值法埃尔米特插值法 牛顿插值法牛顿插值法 样条函数插值法样条函数插值法 分段低次插值法分段低次插值法4.1.2 插值函数的存在唯一性问题插值函数的存在唯一性问题 基函数基函数定义定义4-2 上也是线性

4、无关的。在上是线性无关的在如，上是线性无关的。在时成立，则称当且仅当上连续，如果在设,2)(,1)(, 1)(,)(,)(, 1)(,)(,),(),(00)()()(,)(,),(),(2210101010110010 xxxxxxxxxxxbaxxxkkkxkxkxkbaxbaxxxnnnnnnnniiinnnnnnnnxkxpxpHHxxxnHxxxnH01010)()()()(,),(),(1)(,),(),(，即均可由基函数唯一表示中的任一多项式的；注意：基函数是不唯一一组基函数。的是则个线性无关的多项式，中是合，次的多项式的全体的集是不超过设定义定义4-3 定理定理4-1 (插值函

5、数的存在唯一性定理插值函数的存在唯一性定理)在在n+1个互异基点处满足插值条件且次数不超过个互异基点处满足插值条件且次数不超过n次的多项式次的多项式pn(x)是存在唯一的。是存在唯一的。证明：证明：待定系数法，系数矩阵是待定系数法，系数矩阵是n+1阶范德蒙行列式，阶范德蒙行列式， 由于插值基点互异，行列式不为零，系数存在且唯一。由于插值基点互异，行列式不为零，系数存在且唯一。注意注意：次数不超过：次数不超过n次必不可少，否则，唯一性不保证；次必不可少，否则，唯一性不保证；定理表明：定理表明：插值函数与插值方法无关插值函数与插值方法无关 4.1.3 插值多项式的误差估计插值多项式的误差估计 定义

6、定义4-4 设设pn(x)是函数是函数f(x)的的n次插值多项式次插值多项式,其截断误差其截断误差 又称插值余项记为又称插值余项记为 Rn(x)=f(x)-pn(x) 定理定理4-2 （插值余项定理）（插值余项定理） 设函数设函数f(x)在包含插值基点在包含插值基点 及插值点及插值点x的区间的区间a,b上连续，在上连续，在(a,b)上具有上具有n+1阶导数，则必存在阶导数，则必存在依赖于依赖于x的点的点 ，使，使其中：其中： nxxx,10),(baniinnnnnxxxxxxxxxxnfxR01011) 1()()()()()()!1()()(推论：推论：当当f(x)是次数不超过是次数不超过

7、n 次的多项式时，次的多项式时，pn(x)=f(x)。4.1.3 插值多项式的误差估计插值多项式的误差估计 最大值估计最大值估计)()!1()(,)(1)1(xnMxRMxfMaxnnnbxa则设 事后估计事后估计)()()()()()()()()()()()()()()()(,)(,)()1(10)1(10010110)1(1)1()1()1()1(12110)1(xpxpxxxxxpxfxnRxpxxxxxpxxxxxfxxxxxpxfxpxfffxfxpxxxxpxxxfnnnnnnnnnnnnnnnnnnnn从而推得从而有则有变化不大，即设插值，即无法估计时，可作两次当 4.2 拉格朗

8、日拉格朗日(Lagrang)插值插值-Ln(x) 拉格朗日插值函数均可表示为一组拉格朗日插值函数均可表示为一组基函数基函数与函数值的线性组与函数值的线性组合，这些基函数与被插函数无关，只需用合，这些基函数与被插函数无关，只需用插值基点有来构造插值基点有来构造。4.2.1 拉格朗日线性插值拉格朗日线性插值L1(x) 线性插值及几何意义线性插值及几何意义 n=1时的时的n次多项式次多项式L1(x) 称为称为线性插值线性插值。此时，有两个互异的。此时，有两个互异的插值基点插值基点:x0，x1，插值条件插值条件为为: L1(x0)=y0, L1(x1)=y1 。 其其几何意义几何意义就是用过点就是用过

9、点(x0,y0)和和(x1,y1)的直线的直线y=L1(x)代替代替y=f(x)。 拉格朗日拉格朗日线性插值函数线性插值函数L1(x) 由两点式直线公式，整理可得由两点式直线公式，整理可得010110101)(xxxxyxxxxyxL4.2.1 拉格朗日线性插值拉格朗日线性插值L1(x) 线性插值线性插值基函数及几何意义基函数及几何意义 线性拉格朗日插值基函数。线性拉格朗日插值基函数。它们都是线性函数，且具有性质：它们都是线性函数，且具有性质： 其几何意义见图示。其几何意义见图示。01011010)(,)(xxxxxlxxxxxl称1 , 0,)(jixlijji 插值插值余项余项)(2)()

10、()()(1011xxxxfxLxfxR 例例4-1 证明：证明：)()(81)()()(1020111xfMaxxxxLxfxRxxx 例例4-1 已知已知ln10=2.303,ln11=2.398,求求ln10.5并估计误差。并估计误差。4.2.2 拉格朗日二次拉格朗日二次(抛物抛物)插值插值L2(x) 抛物插值抛物插值及几何意义及几何意义 插值基点：插值基点：x0，x1，x2（互异）（互异） 插值函数：二次多项式（抛物线）插值函数：二次多项式（抛物线） 插值条件：插值条件：L2(xi)=yi, i=0,1,2.2, 1 ,0,)(jixlijji 抛物插值基函数抛物插值基函数及几何意义及

11、几何意义 要求基函数要求基函数 l l0(x)，l l1(X)，l l2(x)均为不超过均为不超过2次的多项式，次的多项式， 且满足：且满足： 不难得到：不难得到： 其几何意义是明显的。其几何意义是明显的。)()()()()()()()()(120210221012012010210 xxxxxxxxxlxxxxxxxxxlxxxxxxxxxl4.2.2 拉格朗日二次拉格朗日二次(抛物抛物)插值插值L2(x) 拉格朗日拉格朗日抛物插值抛物插值公式公式 由抛物插值基函数的由抛物插值基函数的性质性质和插值函数的和插值函数的唯一性唯一性，得，得202211002)()()()()(iiixlyxly

12、xlyxlyxL 拉格朗日拉格朗日抛物插值抛物插值公式的截断误差公式的截断误差)()(! 3)()()()(21022xxxxxxfxLxfxR 例例4-3 利用利用9,16,25的平方根求的平方根求17和和5的平方根的近似值。的平方根的近似值。注意：外插与内插的误差比较。注意：外插与内插的误差比较。4.2.3 n次拉格朗日插值次拉格朗日插值 问题描述问题描述 插值基点：插值基点：x0，x1，xn（n+1个点互异）个点互异） 插值函数：不超过插值函数：不超过n次的多项式次的多项式 插值条件：插值条件：Ln(xi)=yi, i=0,1,2,nnjixlxxxxxxxxxxxxxxxxxxxxxl

13、ijjinijjjijniiiiiiniii, 1 , 0,)()()()()()()()()()(0110110且满足 基函数基函数ninijjjijiniiinnnxxxxyxlyxlyxlyxlyxL0001100)()()()()()()( 拉格朗日插值公式拉格朗日插值公式niiniinninininijjjiixxxyxxLxxxxxlxxx011110)()()()()()()()()()(则有，故由于4.2.3 n次拉格朗日插值次拉格朗日插值 拉格朗日插值余项估计拉格朗日插值余项估计 拉格朗日插值的特点：拉格朗日插值的特点：n基函数基函数整齐、对称整齐、对称,与被插函数无关与被插

14、函数无关,均为不超过均为不超过n次的多项式次的多项式n插值函数被表示为基函数与函数值的插值函数被表示为基函数与函数值的线性组合线性组合n不便于增加插值基点，因为不便于增加插值基点，因为基函数与插值基点和个数有关基函数与插值基点和个数有关n公式的公式的理论价值高理论价值高于牛顿插值于牛顿插值例例4-4 p70例例3 例例4-5 p71例例4例例4-6 p71例例5niinnnnnnxxxxxxxxxxnfxLxfxR01011)1()()()()()()!1()()()()(这里，4.2.4 拉格朗日插值在密钥管理中的应用拉格朗日插值在密钥管理中的应用 像导弹发射、金库等重要场所的通行检查都必须

15、有多人像导弹发射、金库等重要场所的通行检查都必须有多人参与才能生效，需要将密钥分配给多人管理，并且必须参与才能生效，需要将密钥分配给多人管理，并且必须有一定数目的掌管密钥的人同时到场才能恢复密钥。有一定数目的掌管密钥的人同时到场才能恢复密钥。 门限方案：门限方案：设秘密（密钥）设秘密（密钥）s被分成被分成n个部分信息，每一部个部分信息，每一部分信息称为一个子密钥或影子，由一个参与者持有，使得：分信息称为一个子密钥或影子，由一个参与者持有，使得：由由k个或多于个或多于k个参与者持有的部分信息可重构个参与者持有的部分信息可重构s。由少于由少于k个参与者持有的部分信息无法重构个参与者持有的部分信息无

16、法重构s。 称这种方案为（称这种方案为（k,n）秘密分割门限方案，）秘密分割门限方案，k称为门限方案称为门限方案的门限值。如果一个参与者或一组未经授权的参与者在猜的门限值。如果一个参与者或一组未经授权的参与者在猜测秘密测秘密s时，并不比局外人猜秘密时有优势，即如果时，并不比局外人猜秘密时有优势，即如果由少于由少于k个参与者持有的部分信息得不到秘密个参与者持有的部分信息得不到秘密s的任何信息。的任何信息。 则称这个门限方案是完善的，即（则称这个门限方案是完善的，即（k,n）秘密分割门限方案）秘密分割门限方案是完善的。是完善的。4.2.4 拉格朗日插值在密钥管理中的应用拉格朗日插值在密钥管理中的应

17、用 Shamir门限方案门限方案 Shamir门限方案和门限方案和中国剩余中国剩余门限方案是两个最具代表门限方案是两个最具代表性的门限方案。性的门限方案。 Shamir门限方案是基于多项式的门限方案是基于多项式的Lagrange插值公式的。插值公式的。 简要描述简要描述：给定一个：给定一个k-1次多项式，其常数项就是我们要次多项式，其常数项就是我们要保护的保护的秘密秘密，求出此多项式在，求出此多项式在n个相异点出的函数值，则个相异点出的函数值，则（xi，yi）,i=1,2,n就是就是n个个子密钥子密钥。插值理论：插值理论：对一个对一个k-1次多项式进行插值，当插值基点大次多项式进行插值，当插值

18、基点大于等于于等于k时，其多项式插值结果就是原多项式，从而可得时，其多项式插值结果就是原多项式，从而可得到其常数项（秘密），而少于到其常数项（秘密），而少于k个基点的多项式插值不能个基点的多项式插值不能还原给定的多项式，当然也就不能得到秘密。还原给定的多项式，当然也就不能得到秘密。例例 s=11,k=3,n=5,随机选取多项式随机选取多项式f(x)=4x2-7x+11，则则f(3)=26,f(-2)=41,f(1)=8,f(5)=74,f(10)=341,秘密为秘密为f(0)=11.4.3 牛顿牛顿( Newton)插值插值-Nn(x)4.3.1 问题与策略问题与策略 问题问题 由于拉格朗日公

19、式具有由于拉格朗日公式具有“对称性对称性”，但不具备，但不具备“承袭性承袭性”，即插值基点个数改变后所有基函数都改变。即插值基点个数改变后所有基函数都改变。 策略策略 引入不超过引入不超过n次多项式的次多项式的另一组基另一组基： 1，(x-x0)，(x-x0)(x-x1)，(x-x0)(x-x1)(x-xn-1) 作为插值公式的基函数，则牛顿插值公式可表示为：作为插值公式的基函数，则牛顿插值公式可表示为： Nn(x)=a0+a1(x-x0)+a2(x-x0)(x-x1)+an(x-x0)(x-x1)(x-xn-1) 主要工作主要工作 这样牛顿插值公式的主要工作就是计算插值公式中的系数这样牛顿插

20、值公式的主要工作就是计算插值公式中的系数 a0，a1，a2，an 待定系数法是不可取的，为此，引入待定系数法是不可取的，为此，引入均差（差商）。均差（差商）。4.3.2 均差及其计算均差及其计算 均差均差 定义定义4-5 。阶差商的，规定阶均差（差商），特别的关于点为函数的二阶均差（差商），关于点为函数的一阶均差（差商），关于点为函数称)(0,)(,)(,)()()(,1002111010iikkkkkkjikikjjikjijijijijixfxfkxxxxfxxxxxfxxxfxxxfxxxxfxxxxfxxfxxxfxxxfxxxfxfxxf 均差的性质均差的性质4.3.2 均差及其计算

21、均差及其计算 均差表均差表 例例4-7 xif(xi)一阶均差一阶均差二阶均差二阶均差三阶均差三阶均差四阶均差四阶均差x0 x1x2x3x4f(x0)f(x1)f(x2)f(x3)f(x4)fx0,x1fx1,x2fx2,x3fx3,x4fx0,x1,x2fx1,x2,x3fx2,x3,x4fx0,x1,x2,x3fx1,x2,x3,x4fx0,x1,x2,x3,x4 试试改变节点次序，试试改变节点次序，三阶差商的值相同吗？三阶差商的值相同吗？4.3.3 牛顿插值公式及余项牛顿插值公式及余项例例4-8 p75例例8 计算流程图计算流程图 p76 算法步骤算法步骤 p77提示：提示： 差商的性质

22、差商的性质(3)(3)说明了两种插说明了两种插值公式的余项值公式的余项是等价的是等价的4.4 埃尔米特埃尔米特(Hermite)插值插值4.4.1 埃尔米特插值的引入埃尔米特插值的引入 埃尔米特插值也叫做带指定微商值的插值指定微商值的插值。它是要构造一个插值函数，不但在给定的节点上取已知函数值，而且取已知微商值，使插值函数和被插函数的近似程度更好。例例4-8 (p87习题习题13)确定一个不超过确定一个不超过4次的多项式次的多项式p(x)，使使p(0)=p(0)=0, p(1)=p(1)=1,p(2)=1。解解:先确定满足由条件先确定满足由条件p(0)=0, p(1)=1,p(2)=1确定不超

23、过二确定不超过二次的多项式次的多项式 N(x)=0+x+(-1/2)x(x-1)=(-1/2)x2+(3/2)x再令再令 p(x)=N(x)+Ax(x-1)(x-2)+Bx2(x-1)(x-2)通过条件通过条件p(0)=0, p(1)=1,确定待定系数的确定待定系数的A=-3/4,B=1/4整理得整理得 p(x)=x2(x-3)2/4为满足的多项式。为满足的多项式。4.4 埃尔米特埃尔米特(Hermite)插值插值4.4.1 埃尔米特插值的引入埃尔米特插值的引入例例4-9 (p79例例10)求具有三个节点满足插值条件求具有三个节点满足插值条件 p(xj)=f(xj) (j=0,1,2)及及p(

24、x1)=f(x1) 的三次埃尔米特插值多项式及余项。的三次埃尔米特插值多项式及余项。解解:求求三次埃尔米特插值多项式的方法同例三次埃尔米特插值多项式的方法同例4-8. p(x)=f(x0)+fx0,x1(x-x0)+fx0,x1,x2(x-x0)(x-x1) +A(x-x0)(x-x1)(x-x2) 其中其中A可由导数条件求出。可由导数条件求出。为求余项，令为求余项，令 R(x)=f(x)-p(x)=k(x)(x-x0)(x-x1)2(x-x2)引入辅助函数引入辅助函数g(t)=f(t)-p(t)-k(x) (t-x0)(t-x1)2(t-x2)反复利用罗尔定理得求得反复利用罗尔定理得求得k(

25、x)，从而得到余项公式，从而得到余项公式)()()(!41)(2210)4(xxxxxxfxR4.4 埃尔米特埃尔米特(Hermite)插值插值4.4.2 两点三次埃尔米特插值两点三次埃尔米特插值 问题描述问题描述 求不超过求不超过3次的插值多项式次的插值多项式H(x)，满足插值条件，满足插值条件 H(xk)=yk=f(xk) , H(xk+1)=yk+1=f(xk+1) H(xk)=mk=f(xk), H(xk+1)=mk+1=f(xk+1) 构造思想：构造思想：借助拉格朗日插值的思想，先构造借助拉格朗日插值的思想，先构造4个满足个满足以下条件的不超过以下条件的不超过3次的埃尔米特插值基函数

26、。次的埃尔米特插值基函数。4.4 埃尔米特埃尔米特(Hermite)插值插值4.4.2 两点三次埃尔米特插值两点三次埃尔米特插值 两点三次两点三次埃尔米特多项式埃尔米特多项式 由埃尔米特插值基函数的性质，由埃尔米特插值基函数的性质，两点三次两点三次埃尔米特多项式埃尔米特多项式可写成可写成)()()()()(1111xmxmxyxyxHkkkkkkkk 基函数的确定基函数的确定 4个基函数都是不超过个基函数都是不超过3次的多项式，由次的多项式，由4个个条件可唯一确定，最条件可唯一确定，最终得到。终得到。例例4-10 p78例例94.4 埃尔米特埃尔米特(Hermite)插值插值4.4.2 两点三

27、次埃尔米特插值两点三次埃尔米特插值 插值余项插值余项 类似拉格朗日插值余项的证明，得到两点三次埃尔米特类似拉格朗日插值余项的证明，得到两点三次埃尔米特插值公式的余项为插值公式的余项为),()()(3841)()()(! 41)()()(141)4(212)4(kkkkkkxxxxfxRxxxxfxHxfxR用两点三次埃尔米特公式重作例4-94.5 分段低次插值分段低次插值4.5.1 龙格龙格(Runge)现象现象4.5.2 分段线性插值分段线性插值 分段线性插值就是过插值点用分段线性插值就是过插值点用折线折线来近似曲线。来近似曲线。 每个子区间每个子区间xk,xk+1上的线性插值余项上的线性插

28、值余项211)()(max81)()(21)()()(1kkxxxkkkkxxxfxxxxfxIxfxRkk 整体截断误差整体截断误差).(max,)(max8)()()(102kknkbxaxxhxfhxIxfxR 其中 当当f(x)为连续函数时，分段线性插值函数是为连续函数时，分段线性插值函数是一致连续一致连续的。的。4.5.3 分段三次埃尔米特插值分段三次埃尔米特插值).(max,)(max384)()()(10)4(4kknkbxaxxhxfhxIxfxR其中4.6 三次样条插值三次样条插值4.6.1 样条插值的背景和意义样条插值的背景和意义 工程实际中对插值函数的工程实际中对插值函数

29、的光滑性要求高，光滑性要求高，内点处要求一、二内点处要求一、二阶导数连续；阶导数连续； 但插值条件仅已知但插值条件仅已知n+1个节点处的函数值，个节点处的函数值，内点处的导函数值内点处的导函数值没有指定。没有指定。 m次样条函数次样条函数s(x)是一个分段函数，对于区间是一个分段函数，对于区间a,b的一个的一个 划分划分 a=x0 x11) 函数函数s(x)在每个子区间在每个子区间xi,xi+1上都是不超过上都是不超过m次的多项式，次的多项式，并且并且m-1阶导数阶导数s(m-1)(x)在内点在内点x1,xn-1处连续。处连续。 通常使用三次样条函数进行插值，称为通常使用三次样条函数进行插值，

30、称为三次样条插值函数；三次样条插值函数； 此时，三次样条函数同时满足插值条件此时，三次样条函数同时满足插值条件 s(xi)=f(xi) i=0,1,n 通常记通常记 s(x)=M(x)，称为，称为弯矩，呈折线弯矩，呈折线； s(x)=Q(x)，称为，称为剪力，呈台线剪力，呈台线； s(x)=m(x),一阶光滑。一阶光滑。4.6 三次样条插值三次样条插值4.6.2 三次样条插值的定解条件三次样条插值的定解条件 n个子区间，每个子区间是三次多项式，个子区间，每个子区间是三次多项式，共需共需4n个条件。个条件。 插值条件，插值条件，s(xi)=f(xi)， i=0,1,n，共共n+1个条件。个条件。

31、 内点处连续条件内点处连续条件: 零阶导连续零阶导连续 s(xi-0)=s(xi+0), i=1,n-1,共共n-1个条件。个条件。 一阶导连续一阶导连续 s(xi-0)=s(xi+0), i=1,n-1,共共n-1个条件。个条件。 二阶导连续二阶导连续 s(xi-0)=s(xi+0), i=1,n-1,共共n-1个条件。个条件。 共有共有4n-2个条件个条件! 为得到为得到4n个条件，需附加个条件，需附加2个条件，称为个条件，称为边界条件。边界条件。4.6 三次样条插值三次样条插值4.6.2 三次样条插值的定解条件三次样条插值的定解条件 第一种边界条件（第一种边界条件（固支条件固支条件） 已知两端点处的一阶导数值已知两端点处的一阶导数值 s(x0)=f(x0),s(xn)=