《数值计算方法》课件5插值法

5.1函数插值的基本问题

5.1.1函数插值问题

函数插值的必要性

使复杂函数简单化使无解析式的函数（离散型、图形图像）获得解析式为其他数值方法提供支持手段（如数值积分、微分）

插值问题定义5-1

5.1函数插值的基本问题

5.1.1函数插值问题

代数多项式插值问题由于多项式有其优良的特性，所以通常都是用多项式作为插值函数。还有其它类型的插值函数，如有理函数插值、三角函数插值等

函数插值涉及的基本问题插值函数的存在唯一性问题插值函数的构造问题截断误差估计与收敛性问题

代数多项式插值函数的构造方法

拉格朗日插值法

埃尔米特插值法

牛顿插值法

样条函数插值法

分段低次插值法5.1.2插值函数的存在唯一性问题

基函数定义5-2

定义5-3

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

5.2拉格朗日(Lagrang)插值----Ln(x)

拉格朗日插值函数均可表示为一组基函数与函数值的线性组合，这些基函数与被插函数无关，只需用插值基点有来构造。5.2.1拉格朗日线性插值L1(x)

线性插值及几何意义

n=1时的n次多项式L1(x)称为线性插值。此时，有两个互异的插值基点:x0，x1，插值条件为:L1(x0)=y0,L1(x1)=y1。其几何意义就是用过点(x0,y0)和(x1,y1)的直线y=L1(x)代替y=f(x)。

拉格朗日线性插值函数L1(x)

由两点式直线公式，整理可得5.2.1拉格朗日线性插值L1(x)

线性插值基函数及几何意义

线性拉格朗日插值基函数。它们都是线性函数，且具有性质：其几何意义见图示。

插值余项留给读者自己证明：例5-2已知sin30o=0.5,sin45o=0.707107,求sin50o的近似值。5.2.2拉格朗日二次(抛物)插值L2(x)

抛物插值及几何意义

插值基点：x0，x1，x2（互异）插值函数：二次多项式（抛物线）插值条件：L2(xi)=yi,i=0,1,2.

抛物插值基函数及几何意义

要求基函数

l0(x)，l1(X)，l2(x)均为2次多项式，且满足：不难得到：

其几何意义是明显的。5.2.2拉格朗日二次(抛物)插值L2(x)

拉格朗日抛物插值公式由抛物插值基函数的性质和插值函数的唯一性，得

拉格朗日抛物插值公式的截断误差例

利用9,16,25的平方根求17和5的平方根的近似值。注意：外插与内插的误差比较。例5-3已知sin30o=0.5,sin45o=0.707107,sin60o=866025，用抛物插值法求sin50o的近似值。5.2.3n次拉格朗日插值

问题描述插值基点：x0，x1，…，xn（n+1个点互异）插值函数：不超过n次的多项式插值条件：Ln(xi)=yi,i=0,1,2,…,n

基函数

拉格朗日插值公式例5-4p935.2.4插值余项的误差估计

定义5-5

设pn(x)是函数f(x)的n次插值多项式,其截断误差又称插值余项记为Rn(x)=f(x)-pn(x)

定理5-2（插值余项定理）

设函数f(x)在包含插值基点及插值点x的区间[a,b]上连续，在(a,b)上具有n+1阶导数，则必存在依赖于x的点，使其中：

不难写出线性插值和抛物插值的余项公式。5.2.4插值余项的误差估计关于余项公式的几点说明（1）由插值函数唯一性定理和余项定理知：只要插值条件给定，插值函数是唯一存在（不论用什么样的插值方法），其余项也是相同的。即余项公式（5-17）对后面将要讨论的牛顿插值法也使用。（2）由余项定理不难得到下面几个推论：例5-6p955.2.4插值余项的误差估计关于余项公式的几点说明（3）拉格朗日插值基函数的另一种表示（4）余项的最大估计与事后估计插值函数被表示为基函数与函数值的线性组合基函数整齐、对称,与被插函数无关,且均为n次多项式公式的理论价值高于牛顿插值，在其它数值方法中用到的插值函数大多都用拉格朗日插值公式表示不便于增加插值节点，因为基函数与插值节点和个数有关不便于估计插值余项，因为余项与被插函数的n+1阶导数有关5.2.5拉格朗日插值的特点同一函数在不同的基函数下的表示形式是不同的。不同的插值方法选取的基函数是不同的。如何构造插值基函数是掌握插值方法的关键。5.2.6拉格朗日插值在密钥管理中的应用

像导弹发射、金库等重要场所的通行检查都必须有多人参与才能生效，需要将密钥分配给多人管理，并且必须有一定数目的掌管密钥的人同时到场才能恢复密钥。

门限方案：设秘密（密钥）s被分成n个部分信息，每一部分信息称为一个子密钥或影子，由一个参与者持有，使得：

由k个或多于k个参与者持有的部分信息可重构s。

由少于k个参与者持有的部分信息无法重构s。称这种方案为（k,n）秘密分割门限方案，k称为门限方案的门限值。如果一个参与者或一组未经授权的参与者在猜测秘密s时，并不比局外人猜秘密时有优势，即如果

由少于k个参与者持有的部分信息得不到秘密s的任何信息。则称这个门限方案是完善的，即（k,n）秘密分割门限方案是完善的。5.2.6拉格朗日插值在密钥管理中的应用

Shamir门限方案

Shamir门限方案和中国剩余门限方案是两个最具代表性的门限方案。

Shamir门限方案是基于多项式的Lagrange插值公式的。

简要描述：给定一个k-1次多项式，其常数项就是我们要保护的秘密，求出此多项式在n个相异点出的函数值，则（xi，yi）,i=1,2,…,n就是n个子密钥。

插值理论：对一个k-1次多项式进行插值，当插值基点大于等于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.5.3牛顿(Newton)插值----Nn(x)5.3.1问题与策略

问题

由于拉格朗日公式具有“对称性”，但不具备“承袭性”，即插值基点个数改变后所有基函数都改变。插值余项与被插函数的n+1阶导数有关

策略

引入不超过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)

主要工作

牛顿插值公式的主要工作就是计算插值公式中的系数

a0，a1，a2，…，an

待定系数法是不可取的，为此，引入均差（差商）。

特例：线性和抛物牛顿插值公式的构造5.3.2均差及其计算

均差定义5-6

均差的性质5.3.2均差及其计算

均差表

例5-7xif(xi)一阶均差二阶均差三阶均差四阶均差…x0x1x2x3x4…f(x0)f(x1)f(x2)f(x3)f(x4)…f[x0,x1]f[x1,x2]f[x2,x3]f[x3,x4]…f[x0,x1,x2]f[x1,x2,x3]f[x2,x3,x4]…f[x0,x1,x2,x3]f[x1,x2,x3,x4]…f[x0,x1,x2,x3,x4]…………………试试改变节点次序，三阶差商的值相同吗？5.3.3牛顿插值公式及余项差商的性质(3)说明了两种插值公式的余项是等价的5.3.3牛顿插值公式及余项由插值多项式的唯一性定理可知，满足相同插值条件的拉格朗日插值多项式与牛顿插值多项式本质上是同一个插值多项式，只是由于插值基函数选择不同使得其具有不同的表示形式。相比拉格朗日插值，牛顿插值具有以下优点：插值多项式具有承袭性，便于增加插值节点；插值余项更具一般性，对于表格函数或导数不存在的情形都适用；插值公式中每一项的系数就是各阶差商，计算量小，便于程序实现。例5-8P100

牛顿插值算法步骤p100

牛顿插值算法流程框图p1005.4埃尔米特(Hermite)插值5.4.1含有导数条件的插值

为了更好地近似被插值函数，许多实际问题不仅要求插值函数与被插函数在插值节点处函数值相等，还要求插值节点处的导数值也相等。一般来说，如果给出n+1个含有函数值和导数值的插值条件，就可以构造出次数不超过n次的埃尔米特插值多项式。称这种带有导数条件的插值为埃尔米特(Hermite)插值。例5-9求具有三个节点满足插值条件p(xj)=f(xj)(j=0,1,2)及p’(x1)=f’(x1)的三次埃尔米特插值多项式，并证明余项例5-10P102例5-11P1035.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次埃尔米特插值基函数。5.4.2两点三次埃尔米特插值

两点三次埃尔米特多项式

由埃尔米特插值基函数的性质，两点三次埃尔米特多项式可写成

基函数的确定

4个基函数都是不超过3次的多项式，由4个条件可唯一确定，最终得到。例5-12p104用两点三次埃尔米特插值公式解例5-105.4埃尔米特(Hermite)插值5.4.2两点三次埃尔米特插值

插值余项类似拉格朗日插值余项的证明，得到两点三次埃尔米特插值公式的余项为用两点三次埃尔米特公式重作例5-1，求sin50o的近似值。5.5分段低次插值5.5.1龙格(Runge)现象

龙格现象：插值节点增多，其插值精度未必提高

龙格现象的实质：插值多项式Pn(x)不收敛与f(x)

龙格现象的应对：

分段低次插值。各小区间连接处导数不连续分段埃尔米特插值。要提供个节点处的导数值分段光滑插值。样条插值有理分式插值。5.5分段低次插值5.5.2分段线性插值

分段线性插值就是过插值点用折线来近似曲线。

每个子区间[xk,xk+1]上的线性插值余项

整体截断误差

当f(x)为仅连续函数时，分段线性插值函数仍是一致收敛的。5.5.3分段三次埃尔米特插值

整体截断误差对于分段三次埃尔米特插值，可以证明：当f(x)一阶导数连续时，不仅I(x)一致收敛与f(x)，而且I’(x)也一致收敛于f’(x)。它广泛应用于外形设计。5.6三次样条插值

工程实际中对插值函数的光滑性要求高，内点处要求一、二阶导数连续；

但插值条件仅已知n+1个节点处的函数值，内点处的导函数值没有指定。

m次样条函数s(x)是一个分段函数，对于区间[a,b]的一个划分a=x0<x1<…<xn=b(n>1)

函数s(x)在每个子区间[xi,xi+1]上都是不超过m次的多项式，并且m-1阶导数s(m-1)(x)在内点x1,…,xn-1处连续。

通常使用三次样条函数进行插值，称为三次样条插值函数；

此时，三次样条函数同时满足插值条件

s(xi)=f(xi)i=0,1,…,n

通常记

s’’(x)=M(x)，称为弯矩，呈折线；s’’’(x)=Q(x)，称为剪力，呈台线；s’(x)=m(x),一阶光滑。5.6三次样条插值5.6.1三次样条插值的定解条件

n个子区间，每个子区间是三次多项式，共需4n个条件。

插值条件，s(xi)=f(xi)，i=0,1,…,n，共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个条件。二阶导连续s’’(xi-0)=s’’(xi+0),i=1,…,n-1,共n-1个条件。

共有4n-2个条件!

为得到4n个条件，需附加2个条件，称为边界条件。5.6三次样条插值5.6.1三次样条插值的定解条件

第一种边界条件（固支条件）已知两端点处的一阶导数值s’(x0)=f’(x0),s’(xn)=f’(xn)

第二种边界条件已知两端点处的二阶导数值s’‘(x0)=f’’(x0),s’‘(xn)=f‘’(xn)特别地，令s’‘(x0)=s’‘(xn)=

0，称为自然边界条件。

第三种边界条件（周期条件）s’(x0+0)=s’(xn-0),s’’(x0+0)=s’’(xn-0)例5-13已知函数f(x)在三个点处的值为

f(-1)=1,f(0)=0,f(1)=1在区间[-1,1]上，求f(x)在自然边界条件下的三次样条插值多项式。5.6.1三次样条插值的定解条件5.6三次样条插值5.6.2三次样条插值函数的构造方法一：m法即三转角法

基本思路：以插值点处的一阶导数mj为待定系数。

构造过程：

先每个子区间采用两点三次埃尔米特插值写出样条函数Sj(x)；它隐含了插值和零阶连续条件和内点处一阶导数连续条件；再对Sj(x)求二阶导数，利用内点处二阶导数连续

Sj-1’’(xj-0)=Sj’’(xj+0)j=1,2,…,n-1

最后得到关于待定参数mj的三对角线性方程组。

特点：求解第一种边界条件有利。例5-14p111方法二：M法即三弯矩法

基本思路：以插值点处的二阶导数Mj为待定系数。

构造过程：先用分段线性插值公式写出样条函数S(x)的二阶导函数M(x),它隐含了内点处的二阶导数连续条件;再对M(x)

作两次不定积分,得S(x),由插值和连续条件确定2n个积分常数,

然后对S(x)求一阶导数，用一阶导数内点处的连续条件

Sj-1’(xj-0)=Sj’(xj+0)j=1,2,…,n-1

最后得到关于待定参数Mj的三对角线性方程组。

特点：求解第二种边界条件有利。5.6三次样条插值5.6.2三次样条插值函数的构造5.7二元函数插值方法5.7.1双线性插值

问题：假设已知函数f(x,y)在下图所示矩形区域的顶点Ai的函数值，寻求一插值函数P(x,y)满足这4个插值条件。

求解思路：利用拉格朗日插值的思想构造4个基函数，满足：插值函数：令P(x,y)=a+bx+cy+dxy上式对x和y均为线性的，故称为双线性函数