5插值上.ppt

第五章,插值法 （上）,第五章目录,§1 拉格朗日（Lagrange）插值 1.1 插值多项式的存在性和唯一性 1.2 插值多项式的误差估计 1.3 Lagrange插值多项式 §2 牛顿（Newton）插值 2.1 差商 2.2 Newton插值方式 2.3 差分 2.4 差距节点的插项公式,§3 Hermite插值 3.1 Hermite插值 3.2 误差估计 3.3 Hermite插值的一般方式 §4 多项式插值的缺陷 4.1 多项式插值的缺陷 4.2 分段多项式插值 §5 样条函数 5.1 样条函数的概念 5.2 三次样条函数,插值法概述,函数常被用来描述客观事物变化的内在规律数量 关系，如宇宙中天体的运行，地球上某地区平均气温的 变化等等，但在生产和科研实践中碰到的大量的函数中， 不仅仅是用解析表达式表示的函数，还经常用数表和图 形来表示函数，其中函数的数表形式在实际问题中应用 广泛，主要原因是有相当一部分函数是通过实验或观测 得到的一些数据，这些数据只是某些离散点 xi 上的值（ 包括函数值f (xi)，导数值f (xi)等,i = 0,1,2,n),虽然其函 数关系是客观存在的，但却不知道具体的解析表达式， 因此不便于分析研究这类数表函数的性质，也不能直接 得出其它未列出点的函数值，我们希望能对这样的函数 用比较简单的表达式近似地给出整体的描述。,插值法概述(续1）,如行星在太空中的定位问题：当行星在空间运行时， 可通过精密观测仪器在不同的时间ti(i = 1,2,)观测到行 星所在位置S(ti)，无论花费多少人力物力，所得到的只 是一批离散数据(ti,S(ti),i=1,2,)，而行星是在作连续运 动，它在任一时间t（与ti不同）的位置S(t)，我们只能再 去通过观测得到，插值逼近是利用这组离散数据(ti,S(ti) 构造一个简单的便于计算的近似函数（解析表达式）， 用它可求任何时间的函数值（称为插值），对这个近似 解析表达式也能求导，讨论其各种性质。,又如：据资料记载，某地区每隔10年进行一次人口普查， 自1930年到1990年的统计结果如下：,插值法概述（续2）,另一方面，有些函数，虽然有解析表达式，但因其过于 复杂，不便于计算和分析，同样希望构造一个既能反映函 数的特性又便于计算的简单函数，近似代替原来的函数。 如在积分 中，当f (x)很复杂，要计算 积分I是很困难的，构造近似函数使积分容易计算，并且 使之离散化能上机计算求出积分I，都要用到插值逼近。,年 份: 1930 1940 1950 1960 1970 1980 1990 人口 （百万）: 1 23 1 32 1 51 1 80 2 03 2 27 2 52,通过对上述数据的观察和分析，我们希望能估计出这六十年期间任何一年（例如1965年）的人口总数，或者预测2000年该地区的人口数量 。利用插值方法就可以解决这一类问题。,代数插值,解决上述问题的方法有两类：一类是对于一组离散点(xi,f (xi) (i = 0,1,2,n)，选定一个便于计算的函数形式(x)，如多项式，分段线性函数，有理式，三角函数等，要求(x)通过点(xi)=f (xi) (i = 0,12,n),由此确定函数(x)作为f (x)的近似。这就是插值法。另一类方法在选定近似函数的形式后，不要求近似函数过已知样点，只要求在某种意义下它在这些点上的总偏差最小。这类方法称为曲线（数据）拟合法，将在下一章介绍。,本章主要讨论构造插值多项式的几种常用的方法及 其误差 用插值法求函数的近似表达式时，首先要选定 函数的形式。可供选择的函数很多，常用的是多项式 函数。因为多项式函数计算简便，只需用加、减、乘 等运算，便于上机计算，而且其导数与积分仍为多项式。,代数插值（续1）,用多项式作为研究插值的工具，称为代数插值，其 基本问题是： 已知函数f (x)在区间a,b上n+1个不同点x0,x1,xn处的 函数值yi = f (xi) (i=0,1,n),求一个次数不超过n的多项式：,使其满足在给定点处与f(x)相同，即满足插值条件：,n(x)称为插值多项式，xi(i=0,1,2,n)称为插值节点，a,b称为插值区间。,代数插值（续2）,从几何上看（如图5-1所示），n次多项式插值就是 过n+1个点yi = f (xi)(i=0,1,n)，作一条多项式曲线 y = (x)近似曲线y = f (x) :,代数插值（续3）,插值法是求函数值的一种逼近方法，是数值分析中的 基本方法之一，作为基础，后面微分，积分，微分方程在 进行离散化处理时，要用到，作为一种逼近方法，本身也 有广泛的应用价值，如在拱桥建设中，拱轴，拱腹的设计 节点与具体施工设计点常常可能不重合。如图5-2所示。,假定 ： 设计给出的节点为xi = 2,4,6, 8, 10，施工设计拱架点为xi = 1.5, 3.5, 5.5, 8, 10,部分节点不重合，此时y = f (xi)如何求？这就是插值问题。,又如在软土地区修建铁路，公路，将不可 避免地会出现后期沉降（工后沉降）问题，其 工后沉降的大小，沉降速率都直接影响铁路， 公路的养护运营，行车速度等，因此要对其进 行严格控制。 通过对已建成路基面标高（路肩）进行测 量观测，可得到一批数据，对这些数据进行分 析（包括作插值），可推算出： 某一时刻路基沉降（如3年，5年）的沉 降值； 不同时期路基沉降速率； 最终沉降值。,代数插值应用举例,代数插值应用举例（续）,插值用于数码相机增加图像的分辩率：,如果要将一幅数码图像放大，也就是使 其具有更多的像素，而多出来的像素原本 是不存在的,需要根据周围像素的色值计算 出来，这个计算的过程即为插值。,§1 拉格朗日（Lagrange）插值,1.1 插值多项式的存在性和唯一性,插值中，首先要解决的问题是：满足插值条件（5-2） 的插值多次式n(x)是否存在？如果存在，是否唯一？n次 多项式n(x)有n +1个待定系数，利用给出的n+1个不同的 节点x0, x1, , xn，由插值条件（5-2）可得关于系数 a0,a1,an的n +1个方程 ：,插值多项式的存在性和唯一性（续）,其系数行列式 ：,由唯一性的上述简单证明，可以得到下面几点：,关于唯一性证明的几点说明,1：插值多项式的唯一性表明，对同一组节点，它们的 插值多项式是唯一的，可能由不同的方法，会得到不 同形式的插值多项式，但它们之间一定可以相互转化， 一定会相同，当然误差也一样。 2：n +1组节点只能确定一个不超过n次的多项式，若n 次，如设为n+1(x)，则有n+2有待定参数a0,a1,an, an+1 需确定，而n +1个组节点，只构成n +1个插值条 件，即 构成n+1个方程，只能确定n+1个变量的方程组。 3：上述证明是构造性的（给出解决问题的方法）即 以 通过解线性方程组来确定插值多项式，但这种方法的计 算量偏大，计算步骤较多，容易使舍入误差增大。因此 实际计算中不采用这种方法，而用下面介绍的几种常用 的方法。,1.2 插值多项式的误差估计,插值多项式与被插函数之间的差：,称为截断误差，又称为插值余项。,假定f (x)在区间a,b上n +1次连续可导，对a,b上任意点x， 且x xi(i=0,1,n)，构造辅助函数：,插值多项式的误差估计（续）,在（a, b）内至少有一个零点，设为，即：,因为n(t)为至多n次多项， n+1(t)为最高次项系数为1的 n +1次多项式，因而：,又由插值条件（5-2），Rn(xi) = 0 (i=0,1,n)，故函数(t) 在区间a,b内至少有n+2个零点x,x0,x1,xn。由罗尔 （Rolle）中值定理，函数 在(a, b)内至少有n +1个零点。反复使用Rolle中值定理，可以得出：,插值多项式的误差估计（续）,于是有：,所以：,当x = xi (i=0,1,n)，时，上式自然成立，因此，上式对 a,b上的任意点都成立。这就是插值多项式的误差估计。,插值余项定理,定理5.1,设x0, x1, xn是区间a, b上的互异节点，n(x)是过 这组节点的n次插值多项式。如果f (x)在a, b上n+1 次连续可导，则对a,b内任意点x，插值余项为：,观察插值多项式的余项公式，容易看出它与台劳（Taylor）余项有相似之外。事实上，插值余项（5-4）的导出过程与Taylor余项的导出也类似。这并不偶然，因为两者都是研究用多项式近似一个函数的误差。只是Taylor多项式要求在同一点上各阶导数值相等，而插值多项式则要求在个不同点上函数值相等。,插值余项定理（续）,另外，从余项Rn(x)中的n+1(x)知，当点x位于x0, x1, xn 的中部时，比较小，精度要高一些；而位于两端时，精度 要差一点；若x位于x0, x1, xn的外部，一般称为外插， 此时精度一般不理想，使用时必须注意。,为更好理解误差估计式（5-4），来看一下，若f (x)为一 个n次多项式，对于区间a,b，从上选取n +1个点xi(i=0,1,2,n)，由yi =f (xi)可得一组点(xi,yi)(i=0,1,2,n)，由它们按插值条件（5-2）构成一个n次插多项式n(x)，问f (x)（n次多项式）与n(x)之间相差多少(n(x)f (x)？,1.3 Lagrange插值多项式,对(xi,yi)(i=0,1,2,n)按插值条件（5-2）构造n次插 值多项式，有几种方法，可得相应的插值多项式，下 面从最简单的情形开始。 n =1时，只有两个节点:x0, x1，对应于y0, y1，由前所 述，插值多项式应设为1(x) = a0+a1x，且满足插值条件 ：,所以，n =1时两个节点的插值多项式为：,（紧接下屏）,Lagrange插值多项式（续1）,其几何意义，就是以过两点(x0, y0)，(x1, y1)的直线 y = 1(x)近似曲线y = f (x)，故这种插值又称为线性插值， 如图5-3所示 ：,由于1(x)为直线，由过两点的直线的点斜式可得：,Lagrange插值多项式（续2）,显然，1(x)，N1(x)与L1(x)都是同一条直线，应相同， 也可以验证1(x)，N1(x)和L1(x)满足插值条件（5-2）。 线性插值多项式的上述几种形式中，式（5-6）与式 （5-7）由于形式上较简单，将以它们为基础，推广到n+1 个节点的一般情况，分别得到牛顿插值多项式Nn(x)和 拉格朗日插值多项式Ln(x)。,为了将两点插值公式L1(x)推广到一般情况，引入 插值基函数l0(x)，l1(x)，则：,L1(x)是两个函数值的线性 组合，组合系数为 两个插值基函数：,式（5-7）揭示了拉格朗日插值方法的特点，即将插值多项式表示为插值节点x0，x1对应的函数值y0，y1的线性组合，而组合系数就是插值基函数l0(x), l1(x)。所以插值问题可分解为基函数的插值问题。,插值基函数,这里，l0(x),l1(x),l2(x)是二次插值基函数，应满足插值条件：,当n =2时，已知函数表如下，,求满足插值条件L2(xi) = yi (i=0,1,2,)的二次的插值多项式L2(x),插值基函数（n =2）（续1）,按此插值条件，每个基函数的零点都是插值节点， 借助零点构造多项式，可写出三个插值基函数。例如， 由于x1,x2为l0(x)的两个零点，故可设：,同理可得：,插值基函数（续2）,所以：L2(x) = l0(x)y0+ l1(x)y1+ l2(x)y2满足插值条件（5-2）由多项式插值的唯一性知，L2(x)即为所求的二次插值多项式，由于其几何意义为以抛物线L2(x)近似曲线y = f (x)，如图5-4所示，故又称为抛物插值。,将上述利用插值基函数 求插值多项式的方法推广到 一般情况，当节点增多到 n +1个时，对(xi,yi)(i=0,1,2, ,n) 设n次插值多项式：,插值基函数（续3）,即li(x)有n个零点xj (j=0,1,n,j i) 且li(xi)=1，故它必定是以下形式：,其中li(x)为插值基函数(i = 0,1,2,n)， 它们的次数不超过n，且满足：,Lagrange插值多项式,代入（5-9）式，得:,Lagrange插值多项式（续）,事实上，因为每个插值基函数 li（x)(i=0,1,n)都是n次多项式， 故Ln(x)是至多n次多项式，由:,即Ln(x)满足插值条件（5-2），称式（5-10）为 Lagrange插值多项式，具优点是形式对称，含义直观， 便于在计算机上实现，式（5-4）为插值余项。,插值举例,例1,已知函数 y = ln x 的函数表如下：,解线性插值。取两个节点x0=11，x1=12，插值基函数为:,分别用Lagrange线性插值和抛物线插值求ln11.5的近似值 ，并估计截断误差。,例1(续）,抛物线插值。取x0=11，x1=12，x2=13，插值多项式为:,插值举例（续）,例2,证明上式的左端为插值基函数的线性组合，其组合系数 均为1。 显然，函数f(x) 1在这n +1个节点取值为1，即 yi=f (xi) 1 (i=0,1,n)由式（5-10）知，它的n次Lagrange 插值多项式为：,对任意x，插值余项为：,所以：,§2 牛顿（Newton）插值,Lagrange插值多项式是从直线的对称式出发，利用插 值基函数的方法得到的，但从计算的角度来说，直线的点 斜式（5-6）更为方便，因此，能否由此出发，构造一类计 算简单的插值公式呢？,牛顿（Newton）插值（续1）,这是一个递推公式，它表明当增加一个节点时，新的插值多项式只在原插值多项式基础上增加一项，这种情况如果能推广到n次多项式Nn(x)，则Nn(x)可写作为：,上述插值多项式的系数a0,a1,an如何求，是否有规律？事实上，这些系数的确定，可利用插值条件：,牛顿（Newton）插值（续2）,2.1 差商,定义5.1,类似于高阶导数的定义，称 一阶差商的差商:,为f (x)关于点xi,xj,xk的二阶差商，记为f xi,xj,xk。,称为f (x)关于点x0,x1,xk的k阶差商。,一般地：,差商计算,差商的性质,（1）各阶差商均具有线性性质，即若f (x)=a (x)+b (x)， 则对任意常数k，都有：,（2）k阶差商f x0,x1,xk可表成f (x0),f (x1),f(xk)的线性组合：,差商的性质（续）,（3）各阶差商均具有对称性，即改变节点的位置， 差商值不变，如:,（4）若f (x)是n次多项式，则一阶差商f x,xi是n 1次多项式。,事实上，如果f (x)是n次多项式，则p (x) = f (x) f (xi) 也是n次多项式，且p (xi) = 0, xi为其零点p (x)可分解为 p (x) = (xxi) pn1 (x) ， 其中pn1 (x)为n 1次多项式，所以：,为n 1次多项式。,差商表的计算,计算各阶差商，可以按照下表进行：,表5-1,2.2 Newton插值公式,由各阶差商的定义，依次可得:,记：,（紧接下屏）,Newton插值多项式及其余项,显然，Nn(x)是至多n次的多项式。而由：,即得f (xi)= Nn(xi) (i=0,1,n)。这表明Nn(x)满足插值条件（5-2），因而它是f (x)的n次插值多项式。这种形式的插值多项式称为Newton插值多项式。所需差商为表5-1第一条斜线上的含x0的各阶差商。 Newton插值的优点是：每增加一个节点，插值多项式只增加一项（便于边分析误差边调整插值点）即：,因此便于递推运算。而且Newton插值的计算量小于Lagrange插值，还可方便估计误差。,由于f(x) 未知，因此事实上无法估计误差可利用：,在f(x,x0,x1,xn) 中用其他节点代替x得到一个粗略的 误差估计式：,如利用x1,x2,x3，x4四个节点构造三次插值多项式,误差近似为,Newton插值多项式及其余项（续）,由插值多项式的唯一性可知，n次Newton插值多项式与n次Lagrange插值多项式是相等的，即Nn(x) = Ln(x)，它们只是表示形式不同。因此Newton余项与Lagrange余项也是相等的，即：,由此可得差商与导数的关系：,Newton插值多项式的计算,表5-2,Newton插值多项式可按表5-2计算。,n次Newton插值多项式Nn(x)为表5-2中对角线上的差商值 与右端因子乘积的和。,Newton插值公式计算举例,例3,用Newton插值公式计算例1中的ln11.5。,解 如果仍取点x0=11, x1=12, x2=13,作抛物线插值， 按表5-2计算，结果如下：,Newton插值公式计算例3续,若加节点x=10,14, ln10=2.3026, ln14=2.6391，用ln x的 四次Newton插值多项式近似,则:,按表5-2计算结果如下:,2.3 差分,上面讨论的是节点任意分布的Newton插值公式，但在 实际应用中，经常碰到等距节点的情形，即相邻两个节 点之差（称为步长）为常数，这时，Newton插值公式的 形式会简单一些，而关于节点间函数的平均变化率（差 商）可用函数值之差（差分）来表示，避免了除法运算。,定义5.2,设有等距节点xk =x0+kh (k=0,1,n)，步长h为常数，fk = f (xk)，称相邻两个节点xk, xk+1处的函数值的增量fk+1 fk(k = 0,1,n-1)为函数f (x)在点xk处以h为步长的一阶差分，记为fk，称为向前差分：,定义5.2（续）,一般，以k阶差分定义k +1阶差分：,常用的差分还有两种：,向后差分：,差分的其它种类,它们的m阶差分：,对向后差分,差分计算造表,计算时可分别造表计算 ：,表5-3 向前差分表,差分计算造表（续1）,表5-4,差分计算造表（续2）,表5-5,表5-6,差分计算举例,例4,0.007550,注 ：（1）前差，后差，中心差之间是 紧密联系的，都在一个表中，差分值所在 的列数为差分的阶数。要确定某个差分值 是哪个点的差分，则：,对向前差分：要看左上斜线上函数值对应的自变量值 对向后差分：要看左下斜线上函数值对应的自变量值 对中心差分：要看左方水平线上的自变量值，若正好 是空档，则是相邻两个自变量值的算术 平均值。,作y = ln x的差分表，步长h = 0.1,差分的性质,差分有一些重要性质，常用的有（与微分形式相似）：,（2）各阶差分均可表成函数值的线性组合。,（1）各阶差分均具有线性性，即若f (x)=a (x)+b (x)， 则对任意正整数m，都有：,差分的性质（续1）,（3）各种差分之间可以互化，这由差分表即可看出。向后差分与中心差分化成向前 差分的公式如下：,（4）可用 差分表示 差商。,差分的性质（续2）,一般地有：,结合式（5-14），可得差分与导数的关系：,2.4 等距节点插值公式,设已知节点xk =x0+kh (k=0,1,2,n)，将式（5-15）代入插值公（5-12），得：,如果插值节点是等距的，则插值公式可用差分表示。 但在进行插值时，一般不可能将给出的所有点都作为插值点，总是希望运用较少的点达到应有的精度，所以，当被插值点靠近数据表头时，当然考虑用表初的那些点作为插值点，而当被插值点接近数据表尾时，应先选用表尾的那些点作插值点，这样就有Newton向前及向后插值公式。,Newton向前插值公式,式（5-17）称为Newton向前插值公式，其余项为：,若令x =x0+th，则上式又可变形为：,Newton向后插值公式,完全类似地，也可以用向后差分表示Newton插值公式。 令x = xn+th x x0,xn，则有：,式（5-19）称为Newton向后插值公式，其余项为：,Newton向前、向后插值公式均是Newton插值公式在等距节点时的变形。实际计算时，也可列表进行。将表5-7中对角线上的差分值与对应行右端因子乘积求和即得Newton向前插值公式，而Newton向后插公式则为最后的节点所在行的各阶差分值与对应列下端因子乘积之和。,表5-7见下屏：,表5-7,Newton向前、向后插值公式 举例,例5,已知f (x)=Sin x的函数表如下，分别用Newton向前、 向后插值公式求Sin0.57891的近似值：,解 取x0=0.4,x1=0.5,x2=0.6,x3=0.7，按表5-6计算得:,（紧接下屏）,Newton向前、向后插值公式 举例（续1）,Newton向前插值公式为：,Newton向前、向后插值公式 举例（续2）,Newton向后插值公式为：,由于用的是同一组节点，因此Newton向前插值公式与 Newton向后插值公式的结果是完全相同的。,Newton向前、向后插值公式 举例（续3）,如果被插值点x在表中间，同样可以选择靠近x的点,推出插值公式,等距节点插值公式有很多应用，例如，很多工程设计计算时需要查各种函数表，用计算机求值时，就必须解决机器查表问题，如果将整个函数表装入内存，势必占用很多单元，如果用解析表达式近似函数，又可能精度达不到要求，这时一般都把较大表距的函数值表存入，根据需要用插值公式求插值点上的函数值。,第五章,结（上）束,