数值分析课件第2章

上一页下一页湘潭大学数学与计算科学学院1第二章函数基本逼近（一）——插值逼近上一页下一页湘潭大学数学与计算科学学院2§1引言函数逼近:•数学中的基本问题,最活跃的研究领域之一•数值计算中函数表示的重要方法讨论如何用简单函数近似代替复杂函数简单函数曲线拟合离散数据的方法、理论及其实现。上一页下一页湘潭大学数学与计算科学学院3讨论如何用简单的函数()x()fx一个复杂的函数近似地代替的方法、理论及其实现.近似代替又叫做逼近.()x()fx被逼近的函数或被近似的函数逼近的函数或近似的函数即上一页下一页湘潭大学数学与计算科学学院4函数逼近是数值分析的许多分支的理论基础.例如:数值积分;数值微分;微分方程数值解;曲线曲面拟合;函数值近似计算;等等上一页下一页湘潭大学数学与计算科学学院5从逼近论的观点，通常有两种意义下的逼近：局部逼近整体逼近1、局部逼近所谓局部逼近就是求函数()fx在某点附近的近似最常用的逼近方法：Taylor逼近方法理论依据：Taylor定理上一页下一页湘潭大学数学与计算科学学院6()fx0x00(,)Ixx1n,xI定理1.1设n为一非负整数，在点某一邻域有阶连续导数，有则对的()()()nnfxpxRx()npx()nRx这里，n次Taylor逼近多项式和误差余项分别为()00000()()()()()(),1!!nnnfxfxpxfxxxxxn0(1)(1)101()()()()(),!(1)!nxnnnnxfRxxtftdtxxnn其中为0x与x之间的某个点.(1.1)(1.2)(1.3)上一页下一页湘潭大学数学与计算科学学院7注意：()npx1、Taylor逼近多项式满足以下逼近要求00()(),0,1,,.kknkkdpxdfxkndxdx()fx0x2、Taylor逼近是一种局部逼近在一点处的信息.仅利用了被逼近的函数下面举例说明Taylor多项式的逼近效果.上一页下一页湘潭大学数学与计算科学学院8例1在区间[1,1]上，求函数xe在00x附近的Taylor多项式1()px,2()px及其逼近误差1()Rx,2()Rx.解由(1.2)式和(1.3)式易求得()00000()()()()()(),1!!nnnfxfxpxfxxxxxn0(1)(1)101()()()()(),!(1)!nxnnnnxfRxxtftdtxxnn(1.2)(1.3)1()1,pxx22()1,2xpxx12111()(),2xRxepxxe23221()(),6xRxepxxe其中1和2在x与0之间.直观理解可以参见下图。上一页下一页湘潭大学数学与计算科学学院9(a)xe的一次和二次Taylor逼近函数(b)xe的一次和二次Taylor逼近误差(a)(b)上一页下一页湘潭大学数学与计算科学学院10因此，Taylor逼近适合作函数的局部逼近.由此可见：误差不是均匀分布的.当x越偏离x0误差就越大即当x越接近x0误差就越小；我们将主要讨论整体逼近问题:即对定义域上的所有点.近似函数对被逼近函数的逼近函数曲线对样本数据的拟合考虑:上一页下一页湘潭大学数学与计算科学学院11(0.5,0)(1,0.25)(1.5,1).ABC、和例2求区间[0,1.5]上的二次（抛物）曲线,要求该曲线过样本点解设所求抛物线的方程为2,yabxcx利用待定系数法，可得21.4yxx此例将引出所谓的Lagrange型多项式插值问题,这时给定的样本数据仅包含函数值.上一页下一页湘潭大学数学与计算科学学院12例3求区间[0,1]上的三次曲线，要求该函数曲线过且其一阶导函数曲线过样本点(0,0)(1,1)和(即函数曲线在0,1点处的斜率分别为0和1).(0,1)A(1,0),B和样本点23,yabxcxdx23143.yxx解设所求的三次曲线为类似于例2的计算，可得上一页下一页湘潭大学数学与计算科学学院13上例将引出所谓的Hermite型多项式插值问题此时样本数据包含：1、函数值2、一阶导数值.更广泛的还有所谓的Birkhoff插值问题.注意：上一页下一页湘潭大学数学与计算科学学院141,0,1121(2,0)(1,)(0,)(1,)636ABCD、、、(2,0)E[2,2]例4求区间上的二阶连续可微的分段三次多项式），要求该曲线过点和，且在A、E两点的导数为0.曲线（其内部段点分别为解注意所求函数为偶函数，利用待定系数法，[0,2]x上的表示式为可得该函数在y3212,0123xxx32142,1263xxxx上一页下一页湘潭大学数学与计算科学学院15其图形如下图所示.此例将引出所谓的样条插值问题：即求满足一定的整体光滑（或连接）条件的分段插值多项式.上一页下一页湘潭大学数学与计算科学学院20逼近问题主要由以下三个要素构成：(1)被逼近函数（或样本数据）(2)逼近函数空间简单函数：主要是指可以用四则运算进行计算的函数，通常为（代数或三角）多项式、分段多项式和有理多项式函数.简单函数所属的函数空间上一页下一页湘潭大学数学与计算科学学院21(3)逼近方式插值逼近：要求逼近函数曲线通过样本数据点(有时还要求在样本数据点处，等于给定的导数值)本章将在插值逼近方式下，讨论相应的逼近问题.上一页下一页湘潭大学数学与计算科学学院22插值问题涉及的基本内容：1.问题提法2.问题的适定性(解的存在、唯一性)3.解的构造(或表示)及其相关算法4.误差分析(逼近度刻化)及稳定性分析首先,对逼近函数取为代数多项式，样本数据仅包含被逼近函数的函数值的情形，讨论相应的插值问题.上一页下一页湘潭大学数学与计算科学学院23§2Lagrange插值一、问题的提法二、适定性和Lagrange插值公式三、Newton插值公式上一页下一页湘潭大学数学与计算科学学院24一、问题的提法(),0,1,,,iifxyin],[),(baIxxf1n已知：或其个样本值nxxx,,10且彼此互异。01nnaaxax记所有次数不超过n的代数多项式.nP的全体为上一页下一页湘潭大学数学与计算科学学院25插值问题：求,nnPp满足(),0,1,,.niipxyin00,xy,iixy,nnxy()fx()npx01,,nxxx称为被插函数，为n次多项式插值函数，为插值节点，的Lagrange插值问题。并称而上述问题被称为01,,nxxx关于节点上一页下一页湘潭大学数学与计算科学学院26二、适定性和Lagrange插值公式定理2.1插值问题的解是存在且唯一的.证明：（构造性证明）（1）存在性首先构造特殊插值多项式,)(niPxl,,1,,0)(,kikixlkiki.,,1,0,nki克罗内克尔(Kronecker)符号.:,ki(2.1)上一页下一页湘潭大学数学与计算科学学院27n1希望找到li(x)，i=0,…,n使得li(xj)=ij；然后令niiinyxlxP0)()(，则显然有Pn(xj)=yj。li(x)每个li有n个根x0…xi-1xi+1…xnnjjijiixxCxl0)()(jijiiiixxCxl)(11)(njijjijixxxxxl0)()()(niiinyxlxL0)()(Lagrange多项式与有关，而与无关节点f上一页下一页湘潭大学数学与计算科学学院28(2)唯一性设n次多项式()()nnLxQx和()()()0,1,2,,niiniLxfxQxin():()(),nnnGxLxQxP记()()()0,0,1,.ininiGxLxQxin且均为插值问题的解,则有由高等代数基本知识知，若一个n次代数多项式至少存在n+1个根，则它一定恒为零.()0,()().nnGxLxQx故即唯一性得证.上一页下一页湘潭大学数学与计算科学学院29称为f(x)的n次多项式插值的Lagrange公式也称为Lagrange插值多项式.0()()nniiiLxylx称为n次多项式插值问题的基函数(Lagrange因子))()()()('ininixxxxxl其中0()().nnjjxxx上一页下一页湘潭大学数学与计算科学学院30例当n=1时，线性插值公式11001()()()xxLxyxx0110()()xxyxx上一页下一页湘潭大学数学与计算科学学院31当n=2时，抛物插值公式12200102()()()()()xxxxLxyxxxx0211012()()()()xxxxyxxxx0122021()()()()xxxxyxxxx上一页下一页湘潭大学数学与计算科学学院32插值余项设节点)1(nf在(a,b)内存在,考察截断误差)()()(xLxfxRnn],[baCfnbxxxan10，且f满足条件,Rolle’sTheorem:若充分光滑，，则存在使得。)(x0)()(10xx),(10xx0)(推广：若0)()()(210xxx),(),,(211100xxxx使得0)()(10),(10使得0)(0)()(0nxx存在),(ba使得0)()(nRn(x)至少有个根n+1niinxxxKxR0)()()(任意固定xxi(i=0,…,n),考察niixtxKtRnt0)()()()((t)有n+2个不同的根x0…xnx),(,0)()1(baxxn!)1()()()1(nxKRxnn注意这里是对t求导!)1)(()()()1()1(nxKLfxnnxn!)1()()()1(nfxKxnniixnnxxnfxR0)1()(!)1()()(上一页下一页湘潭大学数学与计算科学学院33niyxPiin,...,0,)(求n次多项式使得nnnxaxaaxP10)(条件：无重合节点，即jixxji首先找到li(x)，i=0,…,n使得li(xj)=ij；然后令niiinyxlxP0)()(，则显然有Pn(xj)=yj。存在性定理(唯一性)满足的n阶插值多项式是唯一存在的。niyxPii,...,0,)(上一页下一页湘潭大学数学与计算科学学院34li(x)每个li有n个根x0…xi-1xi+1…xnnjjijiixxCxl0)()(jijiiiixxCxl)(11)(njijjijixxxxxl0)()()(niiinyxlxL0)()(Lagrange多项式与有关，而与无关节点f上一页下一页湘潭大学数学与计算科学学院35000010(()()()...()()()()()())()ninnniinnnjjjjijijiijxxxxxxxxxxLxyyxxxxxxx若上式可改成()jlx上一页下一页湘潭大学数学与计算科学学院36设节点)1(nf在(a,b)内存在,其截断误差)()()(xLxfxRnn],[baCfnbxxxan10，且f满足条件,niixnnxxnfxR0)1()(!)1()()(插值余项/*Remainder*/上一页下一页湘潭大学数学与计算科学学院37注：通常不能确定x,而是估计,x(a,b)将作为误差估计上限。1)1()(nnMxfniinxxnM01||)!1(当f(x)为任一个次数n的多项式时，,可知，即插值多项式对于次数n的多项式是精确的。0)()1(xfn0)(xRn上一页下一页湘潭大学数学与计算科