四章-多项式插值与数值逼近课件

第四章多项式插值与函数逼近/*Polynomial

Interpolationand

ApproximationofFunctions*/本章主要内容：1、Lagrange插值方法2、Newton插值方法3、Hermite插值方法4、三次样条插值方法5、函数逼近:最佳平方逼近和最佳一致逼近第四章多项式插值与函数逼近本章主要内容：1

实际问题中经常要涉及到函数值的计算问题： （1）如果函数表达式本身比较复杂，且需要多次重复计算时，计算量会很大；（2）有的函数甚至没有表达式，只是一种表格函数，而我们需要的函数值可能不在该表格中。对于这两种情况，我们都需要寻找一个计算方便且表达简单的函数来近似代替，这就是数值逼近问题。

问题背景问题背景2§1插值问题

/*InterpolationProblem*/（插值的定义）已知定义于区间上的实值函数在个互异节点

处的函数值，若函数集合中的函数满足则称为在函数集合中关于节点的一个插值函数，并称为被插值函数,[a,b]为插值区间，为插值节点，（*）式为插值条件。设外插法：内插法：用计算被插值函数在点处的近似值用计算被插值函数在点处的近似值§1插值问题/*Interpolation3插值类型代数插值：集合为多项式函数集x0x1x2x3x4xg(x)

f(x)几何意义：有理插值：集合为有理分式函数集三角插值：集合为三角函数集插值类型代数插值：集合为多项式函数集x0x1x2x3x4代数插值的存在唯一性设即代入插值条件：代数插值的存在唯一性设即代入插值条件：5方程组的系数矩阵是Vandermonde矩阵方程组存在唯一解，因此满足插值条件(*)的不超过n次的插值多项式是唯一存在的.方程组的系数矩阵是Vandermonde矩阵方程组6截断误差插值余项设在区间[a,b]上连续，在区间[a,b]上存在,是满足插值条件（*）的不超过n次的插值多项式，则对存在，满足其中。且当在区间[a,b]有上界时，有代数插值的插值余项/*Remainder*/截断误差插值余项设在区间[a,b]上连续，7§2代数插值多项式的构造方法一、拉格朗日多项式

/*LagrangePolynomial*/niyxPiin,...,0,)(==求n次多项式使得条件：无重合节点，即n=1已知x0

,x1

;

y0

,

y1

，求使得111001)(,)(yxPyxP==可见P1(x)是过(x0

,y0)和(x1,y1

)两点的直线。)()(0010101xxxxyyyxP---+=101xxxx--010xxxx--=y0

+y1l0(x)l1(x)==10)(iiiyxl称为拉氏基函数

/*LagrangeBasis*/，满足条件li(xj)=ij§2代数插值多项式的构造方法一、拉格朗日多项式/*8与有关，而与无关n

1希望找到li(x)，i=0,…,n使得

li(xj)=ij；然后令==niiinyxlxP0)()(，则显然有Pn(xi)=

yi

。li(x)每个li(x)

有n个根x0…

xi-1

、

xi+1…xn-==jijiiiixxCxl)(11)(LagrangePolynomial节点f与有关，而与无关n1希望找9例如也是一个插值多项式，其中可以是任意多项式。（2）Lagrange插值多项式结构对称，形式简单.（3）误差估计注：（1）若不将多项式次数限制为n

，则插值多项式不唯一。（4）当插值节点增加时，拉氏基函数需要重新计算，

n较大时，计算量非常大,故常用于理论分析。例如10二、

牛顿插值

/*Newton’sInterpolation*/Lagrange

插值虽然易算，但若要增加一个节点时，全部基函数li(x)都需重新算过。将Ln(x)改写成的形式，希望每加一个节点，只附加一项上去即可。????差商(亦称均差)

/*divideddifference*/1阶差商

/*the1stdivideddifferenceoffw.r.t.xi

andxj

*/2阶差商二、牛顿插值/*Newton’sInterpola1111101010111010],,...,[],,...,[],,...,[],...,,[],...,[++--+++--=--=kkkkkkkkkkkxxxxxfxxxfxxxxxfxxxfxxf(K+1)阶差商：事实上其中差商的值与xi的顺序无关！11101010111010],,...,[],,...,[1212…………n+11+(x

x0)2+……+(x

x0)…(x

xn1)n+1Nn(x)Rn(x)ai=

f[x0,…,xi]312…………n+11+(xx0)2+…13注：

由唯一性可知Nn(x)Ln(x)，只是算法不同，故其余项也相同，即

实际计算过程为（建立差商表）f[x0,x1]f[x1,x2]…………f[xn1,xn]f[x0,x1,x2]……f[xn2,xn1,xn]f[x0,…,xn]

xn+1

f(xn+1)f[xn,xn+1]f[xn1,xn,xn+1]f[x1,…,xn+1]f[x0,…,xn+1]f(x0)f(x1)f(x2)…f(xn1)f(xn)x0x1x2…xn1xn注：由唯一性可知Nn(x)Ln(x)，只是算法14例3：已知函数的函数表：

xi12345yi=f(xi)14786写出4次Newton插值多项式解：构造差商表例3：已知函数的函数表：15§4分段插值

/*piecewiseInterpolation*/一、高次插值评述1、从插值余项角度分析为了提高插值精度，一般来说应该增加插值节点的个数，这从插值余项的表达式也可以看出，但不能简单地这样认为，原因有三个：插值余项与节点的分布有关；余项公式成立的前提条件是有足够阶连续导数（即函数足够光滑），但随着节点个数的增加，这个条件一般很难成立；随着节点个数的增加，可能会增大。随着节点个数增加到某个值，误差反而会增加。§4分段插值/*piecewiseInterpo16注意下面图中曲线的变化情况！例3：在[5,5]上考察的Ln(x)。取

-5

-4

-3

-2

-1

0

1

2

3

4

5

-0.5

0

0.5

1

1.5

2

2.5

n

越大，端点附近误差越大，称为Runge现象Ln(x)

f(x)注意下面图中例3：在[5,5]上考察17§5三次样条插值/*CubicSplineInterpolation*/

许多实际工程技术中一般对精度要求非常高，（1）要求近似曲线在节点连续；（2）要求近似曲线在节点处导数连续，即充分光滑。

分段插值不能保证节点的光滑性，而Hermite插值需要知道节点处的导数值，实际中无法确定。

问题背景§5三次样条插值/*CubicSplineInt18一、三次样条函数的力学背景

在工程技术和数学应用中经常遇到这样一类数据处理问题：在平面上给定了一组有序的离散点列，要求用一条光滑曲线把这些点按次序连接起来。........压铁弹性木条.数据点形象地称之为样条曲线一、三次样条函数的力学背景在工程技术和数学应用中经常19

在力学上，通常均匀细木条可以看作弹性细梁，压铁看作是作用在梁上的集中载荷，“样条曲线”就模拟为弹性细梁在外加集中载荷作用下的弯曲变形曲线。设细梁刚度系数为，弯矩为，样条曲线的曲率为由力学知识：当时（即“小挠度”的情况）上述微分方程简化为：是线性函数因此，“样条曲线”可近似认为是三次多项式在力学上，通常均匀细木条可以看作弹性细梁，压铁看作是20二、三次样条函数定义及求法设在区间上给定一个分割，定义在上的函数如果满足下列条件：(1)在每个小区间内是三次多项式(2)在整个区间上，为二阶连续可导函数，即在每个节点处则称为三次样条函数二、三次样条函数定义及求法设在区间上给21假设现在已知函数在节点处的函数值：如果三次样条函数满足则称为插值于的三次样条函数，简称三次样条插值函数。如何求的三次样条插值函数:4n个未知数3n-1个条件假设现在已知函数在节点处的函数值：如果三次样条函数22线性插值函数1、M连续方程与的表达式记因为在每一个子区间上都是线性函数

两边积分两边再积分一次？线性插值函数1、M连续方程与的表达式记因为23由其中代入插值条件：由其中代入插值条件：24写成方程组的形式：上述方程组称为的M连续方程n-1个方程n+1个未知数三弯矩方程写成方程组的形式：上述方程组称为的M连续方程n25M、m连续方程的求解：需要补充附加条件3、边界条件/*boundaryconditions*/已知端点的斜率：已知端点的二阶导数：设是以为周期的周期函数，对附加周期性条件：

即要求三次样条插值函数在端点处函数值、一阶导数值和二阶导数值相同。M、m连续方程的求解：需要补充附加条件3、边界条件/*bou26M连续方程在各类边界条件下的求解方法对于第一类边界条件由得M连续方程在各类边界条件下的求解方法对于第一类边界条件由得27从而得到方程组（三对角）：可用追赶法求解从而得到方程组（三对角）：可用追赶法求解28注：三次样条与分段Hermite插值的根本区别在于S(x)自身光滑，不需要知道f的导数值（除了在2个端点处的函数值）；而Hermite插值依赖于f在许多插值节点的导数值。f(x)H(x)S(x)注：三次样条与分段Hermite插值的根本区别在于S(x29四章-多项式插值与数值逼近课件30性质3（误差估计）设函数，是区间的一个分割，是关于的带有Ⅰ型(斜率边界)或Ⅱ型(二阶导数边界)边界条件的插值函数，则有误差估计其中

是分割比，并且系数与是最优估计。

性质说明：三次样条插值函数本身连同它的一、二、三阶导数分别收敛到及其相应导数，具有强收敛性。性质3（误差估计）设函数，是31第四章多项式插值与函数逼近/*Polynomial

Interpolationand

ApproximationofFunctions*/本章主要内容：1、Lagrange插值方法2、Newton插值方法3、Hermite插值方法4、三次样条插值方法5、函数逼近:最佳平方逼近和最佳一致逼近第四章多项式插值与函数逼近本章主要内容：32

实际问题中经常要涉及到函数值的计算问题： （1）如果函数表达式本身比较复杂，且需要多次重复计算时，计算量会很大；（2）有的函数甚至没有表达式，只是一种表格函数，而我们需要的函数值可能不在该表格中。对于这两种情况，我们都需要寻找一个计算方便且表达简单的函数来近似代替，这就是数值逼近问题。

问题背景问题背景33§1插值问题

/*InterpolationProblem*/（插值的定义）已知定义于区间上的实值函数在个互异节点

处的函数值，若函数集合中的函数满足则称为在函数集合中关于节点的一个插值函数，并称为被插值函数,[a,b]为插值区间，为插值节点，（*）式为插值条件。设外插法：内插法：用计算被插值函数在点处的近似值用计算被插值函数在点处的近似值§1插值问题/*Interpolation34插值类型代数插值：集合为多项式函数集x0x1x2x3x4xg(x)

f(x)几何意义：有理插值：集合为有理分式函数集三角插值：集合为三角函数集插值类型代数插值：集合为多项式函数集x0x1x2x3x35代数插值的存在唯一性设即代入插值条件：代数插值的存在唯一性设即代入插值条件：36方程组的系数矩阵是Vandermonde矩阵方程组存在唯一解，因此满足插值条件(*)的不超过n次的插值多项式是唯一存在的.方程组的系数矩阵是Vandermonde矩阵方程组37截断误差插值余项设在区间[a,b]上连续，在区间[a,b]上存在,是满足插值条件（*）的不超过n次的插值多项式，则对存在，满足其中。且当在区间[a,b]有上界时，有代数插值的插值余项/*Remainder*/截断误差插值余项设在区间[a,b]上连续，38§2代数插值多项式的构造方法一、拉格朗日多项式

/*LagrangePolynomial*/niyxPiin,...,0,)(==求n次多项式使得条件：无重合节点，即n=1已知x0

,x1

;

y0

,

y1

，求使得111001)(,)(yxPyxP==可见P1(x)是过(x0

,y0)和(x1,y1

)两点的直线。)()(0010101xxxxyyyxP---+=101xxxx--010xxxx--=y0

+y1l0(x)l1(x)==10)(iiiyxl称为拉氏基函数

/*LagrangeBasis*/，满足条件li(xj)=ij§2代数插值多项式的构造方法一、拉格朗日多项式/*39与有关，而与无关n

1希望找到li(x)，i=0,…,n使得

li(xj)=ij；然后令==niiinyxlxP0)()(，则显然有Pn(xi)=

yi

。li(x)每个li(x)

有n个根x0…

xi-1

、

xi+1…xn-==jijiiiixxCxl)(11)(LagrangePolynomial节点f与有关，而与无关n1希望找40例如也是一个插值多项式，其中可以是任意多项式。（2）Lagrange插值多项式结构对称，形式简单.（3）误差估计注：（1）若不将多项式次数限制为n

，则插值多项式不唯一。（4）当插值节点增加时，拉氏基函数需要重新计算，

n较大时，计算量非常大,故常用于理论分析。例如41二、

牛顿插值

/*Newton’sInterpolation*/Lagrange

插值虽然易算，但若要增加一个节点时，全部基函数li(x)都需重新算过。将Ln(x)改写成的形式，希望每加一个节点，只附加一项上去即可。????差商(亦称均差)

/*divideddifference*/1阶差商

/*the1stdivideddifferenceoffw.r.t.xi

andxj

*/2阶差商二、牛顿插值/*Newton’sInterpola4211101010111010],,...,[],,...,[],,...,[],...,,[],...,[++--+++--=--=kkkkkkkkkkkxxxxxfxxxfxxxxxfxxxfxxf(K+1)阶差商：事实上其中差商的值与xi的顺序无关！11101010111010],,...,[],,...,[4312…………n+11+(x

x0)2+……+(x

x0)…(x

xn1)n+1Nn(x)Rn(x)ai=

f[x0,…,xi]312…………n+11+(xx0)2+…44注：

由唯一性可知Nn(x)Ln(x)，只是算法不同，故其余项也相同，即

实际计算过程为（建立差商表）f[x0,x1]f[x1,x2]…………f[xn1,xn]f[x0,x1,x2]……f[xn2,xn1,xn]f[x0,…,xn]

xn+1

f(xn+1)f[xn,xn+1]f[xn1,xn,xn+1]f[x1,…,xn+1]f[x0,…,xn+1]f(x0)f(x1)f(x2)…f(xn1)f(xn)x0x1x2…xn1xn注：由唯一性可知Nn(x)Ln(x)，只是算法45例3：已知函数的函数表：

xi12345yi=f(xi)14786写出4次Newton插值多项式解：构造差商表例3：已知函数的函数表：46§4分段插值

/*piecewiseInterpolation*/一、高次插值评述1、从插值余项角度分析为了提高插值精度，一般来说应该增加插值节点的个数，这从插值余项的表达式也可以看出，但不能简单地这样认为，原因有三个：插值余项与节点的分布有关；余项公式成立的前提条件是有足够阶连续导数（即函数足够光滑），但随着节点个数的增加，这个条件一般很难成立；随着节点个数的增加，可能会增大。随着节点个数增加到某个值，误差反而会增加。§4分段插值/*piecewiseInterpo47注意下面图中曲线的变化情况！例3：在[5,5]上考察的Ln(x)。取

-5

-4

-3

-2

-1

0

1

2

3

4

5

-0.5

0

0.5

1

1.5

2

2.5

n

越大，端点附近误差越大，称为Runge现象Ln(x)

f(x)注意下面图中例3：在[5,5]上考察48§5三次样条插值/*CubicSplineInterpolation*/

许多实际工程技术中一般对精度要求非常高，（1）要求近似曲线在节点连续；（2）要求近似曲线在节点处导数连续，即充分光滑。

分段插值不能保证节点的光滑性，而Hermite插值需要知道节点处的导数值，实际中无法确定。

问题背景§5三次样条插值/*CubicSplineInt49一、三次样条函数的力学背景

在工程技术和数学应用中经常遇到这样一类数据处理问题：在平面上给定了一组有序的离散点列，要求用一条光滑曲线把这些点按次序连接起来。........压铁弹性木条.数据点形象地称之为样条曲线一、三次样条函数的力学背景在工程技术和数学应用中经常50

在力学上，通常均匀细木条可以看作弹性细梁，压铁看作是作用在梁上的集中载荷，“样条曲线”就模拟为弹性细梁在外加集中载荷作用下的弯曲变形曲线。设细梁刚度系数为，弯矩为，样条曲线的曲率为由力学知识：当时（即“小挠度”的情况）上述微分方程简化为：是线性函数因此，“样条曲线”可近似认为是三次多项式在力学上，通常均匀细木条可以看作弹性细梁，压铁看作是51二、三次样条函数定义及求法设在区间上给定一个分割，定义在上的函数如果满足