数值分析与计算方法-第一章-插值法课件

本章内容 1.1 Lagrange插值多项式 1.2 Newton插值多项式 1.3 分段低次插值第一章第一章 插值法插值法/*Interpolation Method*/Start from here 本章内容第一章本章内容第一章 插值法插值法Sta 实际问题中，某些变量之间的函数关系是存在的，只能由实际问题中，某些变量之间的函数关系是存在的，只能由测量或实验得到一系列的离散点上的函数值：测量或实验得到一系列的离散点上的函数值：问题的提出问题的提出（1）有的函数没有表达式，只是一种表格函数，而我们需要的有的函数没有表达式，只是一种表格函数，而我们需要的函数值可能不在该表格中。函数值可能不在该表格中。（2）如果函数表达式本身比较复杂，计算量会很大；如果函数表达式本身比较复杂，计算量会很大；对于这两种情况，我们都需要寻找一个计算方便且表达简单对于这两种情况，我们都需要寻找一个计算方便且表达简单的函数的函数 来近似代替来近似代替 ，求求 的方法称为的方法称为插值插值法法。实际问题中，某些变量之间的函数关系是存在的，只能由测实际问题中，某些变量之间的函数关系是存在的，只能由测的性质近似代替的性质近似代替 性质性质一、插值法基本思想一、插值法基本思想个互异节点上的值，若存在一个个互异节点上的值，若存在一个简单函数简单函数插值节点；插值节点；为为 的插值函数；的插值函数；被插函数被插函数插值条件插值条件求求 的方法称为的方法称为插值法插值法。的性质近似代替的性质近似代替 性质一、插值法基本思想个互异节性质一、插值法基本思想个互异节x0 x1x2x3x4xP(x)f(x)几何意义：几何意义：xx0 x1x2x3x4xP(x)f(x)几何意义：几何意义：x注：注：简单函数简单函数常指：多项式函数、分段多项式函数、有理函数；常指：多项式函数、分段多项式函数、有理函数；相应插值法称为：相应插值法称为：代数插值代数插值法、法、分段插值分段插值、有理函数插值有理函数插值；特别特别：所求所求 是过两点的直线是过两点的直线线性插值线性插值 所求所求 是过三点的二次曲线是过三点的二次曲线抛物插值抛物插值 我们主要介绍我们主要介绍代数插值代数插值（插值函数为（插值函数为多项式多项式 的插值），的插值），相应的相应的 称为称为插值多项式插值多项式。注：简单函数常指：多项式函数、分段多项式函数、有理函数；特别注：简单函数常指：多项式函数、分段多项式函数、有理函数；特别二、插值多项式二、插值多项式的存在唯一性的存在唯一性证明：证明：只要证得只要证得 存在唯一即可，由存在唯一即可，由Th4.1 个互异节点，则满足插值个互异节点，则满足插值多项式多项式条件条件二、插值多项式的存在唯一性证明：只要证得二、插值多项式的存在唯一性证明：只要证得 存在唯一即存在唯一即注：注：若若不限定次数不限定次数，则插值多项式，则插值多项式不唯一不唯一；如：如：若若 满足插值条件，则满足插值条件，则 亦满亦满足足 法则，法则，n+1个插值条件唯一确定一个个插值条件唯一确定一个n次次插值多项式。插值多项式。Vandermond行列式行列式注：若不限定次数，则插值多项式不唯一；如：若注：若不限定次数，则插值多项式不唯一；如：若 一、一、Lagrange插值多项式插值多项式 由由Th4.1Th4.1知，知，中系数的计算只需求解一个中系数的计算只需求解一个 元方元方 程组，程组，待定系数法计算复杂待定系数法计算复杂，且难以得到，且难以得到 式；下面来介绍式；下面来介绍构造法构造法。的简单表达的简单表达的构造的构造 1.2 Lagrange插值多项式插值多项式/*Lagrange Polynomial*/一、一、Lagrange插值多项式插值多项式 由由Th4.1知，知，中系数中系数niyxPiin,.,0,)(=求求 n 次多项式次多项式 使使得得条件：条件：无重合节点，即无重合节点，即n=1已知已知 x0,x1;y0,y1，求，求使得使得111001)(,)(yxPyxP=可见可见 P1(x)是过是过(x0,y0)和和(x1,y1)两点的两点的直线直线。)()(0010101xxxxyyyxP +=101xxxx 010 xxxx =y0+y1l0(x)l1(x)=10)(iiiyxl1 1、基本插值多项式、基本插值多项式:Lagrange插值多项式插值多项式niyxPiin,.,0,)(=求求 n 次多项式次多项式 与与 有关有关，而与而与 无关无关插值基函数插值基函数/基本插值多项式基本插值多项式n 1希望找到希望找到n次次多项式多项式li(x)，i=0,n 使得使得 li(xj)=ij；然后令然后令=niiinyxlxP0)()(，则显然有，则显然有Pn(xi)=yi。li(x)每个每个 li(x)有有 n 个根个根 x0 xi-1、xi+1 xn =j i jiiiixxCxl)(11)(n n次次Lagrange 插值插值多项式多项式节点节点y与与 有关，而与有关，而与 无关无关n 1希望找到希望找到n2 2、插值余项、插值余项-Th4.2设设 个节点个节点 若若 在在 连续，连续，在在 内存在，则内存在，则 插值多项式的余项插值多项式的余项证明：证明：的零点的零点设设引入引入辅助函数辅助函数 则则至少有至少有 个互异零点：个互异零点：2、插值余项、插值余项-Th4.2设设 个节点个节点 数值分析与计算方法数值分析与计算方法-第一章第一章-插值法课件插值法课件若若 则则若若 本身是次数本身是次数不超过不超过n的多项式，的多项式，则，则，即即 通常是次数为通常是次数为n的多项式，特殊情形下可能的多项式，特殊情形下可能小于小于n,如如过三点的过三点的 若三点共线，则若三点共线，则 是一条直线是一条直线(一次一次)则有余项则有余项若若 则若则若 本身是次本身是次例例1：已知已知分别利用分别利用 sin x 的的1次、次、2次次 Lagrange 插值计算插值计算 sin 50 并估计误差。并估计误差。解：解：n=1分别利用分别利用x0,x1 以及以及 x1,x2 计算计算利用利用这里这里而而sin 50 =0.7660444)185(50sin10 p pL0.77614利用利用sin 50 0.76008,内插内插通常优于通常优于外推外推。选择。选择要计算的要计算的 x 在区间的内部，在区间的内部，插值效果较好。插值效果较好。例例1：已知分别利用：已知分别利用 sin x 的的1次、次、2次次 Lagrang二次二次插值比插值比一次一次插插值精度高值精度高n=2)185(50sin20 p pL0.76543但绝对不是次数越但绝对不是次数越高就越好高就越好二次插值比一次插值精度高二次插值比一次插值精度高n=2)185(50sin20 Lagrange插值多项式的缺点：插值多项式的缺点：基函数计算复杂；且已得的基函数计算复杂；且已得的 无用，需重新算过；无用，需重新算过；对于计算对于计算 高次插值精度未必高；高次插值精度未必高；RungeRunge现象现象比较比较n-1次及次及n次插值多项式次插值多项式若非常接近，则以若非常接近，则以n次插值次插值否则增加节点计算否则增加节点计算通常方法：实用通常方法：实用后验估计后验估计不知道选择多少个插值节点为宜；不知道选择多少个插值节点为宜；Lagrange插值多项式的缺点：插值多项式的缺点：基函数计算复杂；且已得的基函数计算复杂；且已得的 本节内容提要本节内容提要基本思想基本思想 NewtonNewton插值多项式的构造插值多项式的构造 均差均差(差商差商)定义、计算、性质定义、计算、性质 NewtonNewton插值多项式的误差插值多项式的误差差分及等距节点插值公式差分及等距节点插值公式1.3 Newton插值多项式插值多项式/*Newtons Interpolation*/本节内容提要本节内容提要1.3 Newton插值多项式插值多项式一、一、基本思想基本思想 缺点：缺点：增加节点时，需要计算增加节点时，需要计算 ，而已得的，而已得的 不能被利用；不能被利用；为此我们考虑对为此我们考虑对LagrangeLagrange插值多项式插值多项式进行进行改写改写；由唯一性，仅是由唯一性，仅是形式上形式上的变化的变化 已知已知n+1个互异插值节点个互异插值节点 由插值多项由插值多项式的存在唯一性，可以构造式的存在唯一性，可以构造Lagrange插值多项式：插值多项式：期望期望：的计算只需要对的计算只需要对 作一个简单的修正作一个简单的修正.一、基本思想一、基本思想 缺点：增加节点时，需要计算缺点：增加节点时，需要计算 ，而已得的，而已得的考虑考虑是次数是次数 的多项式，且的多项式，且有有由新增节点可以计算出由新增节点可以计算出 从而从而考虑是次数考虑是次数 的多项式，且有由新增节点可以的多项式，且有由新增节点可以数值分析与计算方法数值分析与计算方法-第一章第一章-插值法课件插值法课件此公式仍然比较麻烦！此公式仍然比较麻烦！此公式仍然比较麻烦！此公式仍然比较麻烦！二、二、差商（均差）差商（均差）1 1、定义定义：称称 为为 关于节点关于节点 的的一阶差商一阶差商/均均差差记作记作 表示表示 在区间在区间 上的变化率。上的变化率。称一阶差商称一阶差商 的差商为的差商为 关于关于节点节点 的的二阶差商二阶差商，记作：，记作：二、差商（均差）二、差商（均差）1、定义：、定义：称称 注：注：为统一记号，规定：为统一记号，规定：称为零阶差商称为零阶差商类比：类比：导数：导数：差商（均差）：差商（均差）：一般地，称一般地，称n-1阶差商的差商为阶差商的差商为n阶差商阶差商，有：，有：注：为统一记号，规定：注：为统一记号，规定：称为零阶差商类比：导数：差商（称为零阶差商类比：导数：差商（实际计算过程为（实际计算过程为（建立差商表建立差商表）f x0,x1f x1,x2 f xn 1,xnf x0,x1,x2 f xn 2,xn 1,xnf x0,xn xn+1 f(xn+1)f xn,xn+1 f xn 1,xn,xn+1 f x1,xn+1 f x0,xn+1f(x0)f(x1)f(x2)f(xn 1)f(xn)x0 x1x2xn 1xn零阶差商零阶差商 一阶差商一阶差商 二阶差商二阶差商 n阶差阶差商商2 2、差商的计算差商的计算 实际计算过程为（建立差商表）实际计算过程为（建立差商表）f x0,x1f x-3-1/21/205/61/4-1/6-7/60-1/121/180例例1 1：解：解：可见，求各阶均差是方便的，且可见，求各阶均差是方便的，且 位于差商表的对角线上。位于差商表的对角线上。-3-1/21/205/61/4-1/6-7/60-1/123 3、差商性质差商性质 /*Property of divided difference*/n阶差商可以表示为阶差商可以表示为 的线性组合的线性组合性质性质1 1证明：证明：数学归纳法数学归纳法n=13、差商性质、差商性质/*Property of divided 数值分析与计算方法数值分析与计算方法-第一章第一章-插值法课件插值法课件得证。得证。得证。得证。性质性质2 差商具有对称性，即差商具有对称性，即 的值与节点的值与节点 的顺序无关。的顺序无关。由性质由性质1 1易知：调换两个节点的位置，相当于右端易知：调换两个节点的位置，相当于右端改变求改变求和次序。和次序。性质性质4 4n阶差商和阶差商和n阶导数之间存在如下关系：阶导数之间存在如下关系：性质性质3n 次多项式次多项式的的 k 阶差商阶差商 当当 时是时是 n-k 次多项式，而当次多项式，而当 kn 时时其值恒等于零。其值恒等于零。用用fx,x0,xl=xm验证即可验证即可性质性质2差商具有对称性，即差商具有对称性，即 证明：证明：证明：证明：三、三、NewtonNewton插值多项式插值多项式/*Newtons Interpolation*/1 1、定义：、定义：12 n 11+(x x0)2+(x x0)(x xn 1)n 1Nn(x)Rn(x)ai=f x0,xi 三、三、Newton插值多项式插值多项式/*Newtons Inter例例2：解：解：先求差商表（上例已求出），先求差商表（上例已求出），4 4次牛顿插值次牛顿插值多项式为：多项式为：例例2：解：解：先求差商表（上例已求出），先求差商表（上例已求出），4次牛顿插值多项式为次牛顿插值多项式为2、余项余项：带余项的带余项的Newton插值公式插值公式 证明：证明：2、余项：、余项：带余项的带余项的Newton插值公式插值公式 证明：证明：比较可知，比较可知，与与 的确只是形式上的不同，的确只是形式上的不同，Newton插值多项式便于计算，而插值多项式便于计算，而Lagrange插值插值多项式多用于理论推导。多项式多用于理论推导。注注：性质性质2 2比较可知，比较可知，与与 的确只是形式上的不的确只是形式上的不例：例：习题习题4-8设设 互不相同，证互不相同，证明明并写出并写出 的的n次次Newton插值多项式。插值多项式。例：习题例：习题4-8设设 证明证明(归纳法归纳法)设设 时成立，即时成立，即证明证明(归纳法归纳法)设设 时成立，即时成立，即得证。得证。得证。得证。的的n次次Newton插值多项式插值多项式的的n次次Newton插值多项式插值多项式 本节内容提要本节内容提要基本概念 有限差(向前差分、向后差分、中心差分)差分的计算 差分的性质等距节点插值公式 1.4 差分与等距节点插值公式差分与等距节点插值公式 /*Interpolation Formulae with Equal Spacing*/本节内容提要本节内容提要1.4 差分与等距节点插值公式差分与等距节点插值公式 上节谈论了节点任意分布的上节谈论了节点任意分布的Newton插值公式，实际应插值公式，实际应用时常碰到等距节点的情形，即：用时常碰到等距节点的情形，即：步长步长 此时公式可进一步简化，同时可以避开除法运算，此时公式可进一步简化，同时可以避开除法运算，引入差分的概念。引入差分的概念。前前 言言 上节谈论了节点任意分布的上节谈论了节点任意分布的Newton插值公式，实际应插值公式，实际应称称为为 在在 处以处以h为步长的二阶向前差分，简称二阶为步长的二阶向前差分，简称二阶差分差分设等距节点设等距节点 处的函数值为处的函数值为 称称 处以处以h为步长的一阶向前差分，简称一阶差分，记作：为步长的一阶向前差分，简称一阶差分，记作：一、差分一、差分1 1、定义：、定义：称设等距节点称设等距节点 注：注：类似可以定义：类似可以定义：一般地，称一般地，称 为为 处以处以h为步长的为步长的m阶向前差分，简称阶向前差分，简称m阶差分。阶差分。一阶后差：一阶后差：二阶后差：二阶后差：m阶后差：阶后差：注：注：类似可以定义：一般地，称类似可以定义：一般地，称 前差、后差、中心差前差、后差、中心差 统称为统称为有限差有限差；有限差算子有限差算子 一阶中心差：一阶中心差：二阶中心差：二阶中心差：m阶中心差：阶中心差：为统一记，规定零阶有限差为：为统一记，规定零阶有限差为：前差、后差、中心差前差、后差、中心差 统称为有限差；一阶中心差：统称为有限差；一阶中心差：为统为统 2 2、差分的计算（以前差为例）、差分的计算（以前差为例）列差分表列差分表 2、差分的计算（以前差为例）、差分的计算（以前差为例）列差分表列差分表例：例：解：解：3579222000例：例：解：解：32003 3、性质性质 归纳法证明归纳法证明 利用利用函数值函数值表示高阶表示高阶有限差有限差：利用利用各阶差分各阶差分表示表示函数值函数值：差商差商与与差分差分之间的关系：之间的关系：3、性质、性质 归纳法证明归纳法证明 利用函数值表示高阶有限差：利用函数值表示高阶有限差：证明：证明：证明：证明：将将Newton插值公式中各阶差商用相应差分代替，可插值公式中各阶差商用相应差分代替，可得各种形式的等距节点插值多项式，以下介绍常用得各种形式的等距节点插值多项式，以下介绍常用Newton前插与后插公式。前插与后插公式。记节点记节点则则二、等距节点插值公式二、等距节点插值公式由由Newton插值公式：插值公式：将将Newton插值公式中各阶差商用相应差分代替，可记插值公式中各阶差商用相应差分代替，可记NewtonNewton前插公式前插公式上述公式中用上述公式中用差分差分代替代替差商差商Newton前插公式上述公式中用差分代替差商前插公式上述公式中用差分代替差商例例：解解：求二次牛顿前求二次牛顿前插公式插公式取差分表第一行数据，取差分表第一行数据，得得Newton前插公式：前插公式：例：例：解：求二次牛顿前插公式取差分表第一行数据，得解：求二次牛顿前插公式取差分表第一行数据，得Newto例：例：例：例：解：解：3579222000取差分表第一行数据，得取差分表第一行数据，得Newton前插公式：前插公式：解：解：3200取差分表第一行数据，得取差分表第一行数据，得Newton前插公式：前插公式：牛顿牛顿向后插值向后插值公式公式/*Newtons backward-difference formula*/当插值点当插值点 位于插值区间右端点位于插值区间右端点 附近时附近时 令令将节点顺序将节点顺序倒置倒置：上述公式中用上述公式中用差分差分代替代替差商差商称之为牛顿称之为牛顿向后插值向后插值公式公式 牛顿向后插值公式牛顿向后插值公式/*Newtons backwar注：注：一般当一般当 x 靠近靠近 x0 时用前插公式，靠近时用前插公式，靠近 xn 时用后插公式，故时用后插公式，故两种公式亦称为两种公式亦称为表初公式表初公式和和表末公式表末公式。插值插值余项余项注注：若插值点位于节点中部，则可利用中心差分构造：若插值点位于节点中部，则可利用中心差分构造 StirlingStirling插值插值、BesselBessel插值插值等；等；用于用于高精度要求高精度要求的函数插值，现已少用！的函数插值，现已少用！注：一般当注：一般当 x 靠近靠近 x0 时用前插公式，靠近时用前插公式，靠近 xn 时用后时用后例例 给定给定f(x)在等距节点上的函数值表如下在等距节点上的函数值表如下:xi 0.4 0.6 0.8 1.0 f(xi)1.5 1.8 2.2 2.8分别用分别用Newton向前和向后差分公式求向前和向后差分公式求f(0.5)及及f(0.9)的近似值的近似值 解解 先构造向前差分表如下先构造向前差分表如下:xi fi fi 2 2fi 3 3fi 0.4 1.5 0.6 1.8 0.3 0.8 2.2 0.4 0.1 1.0 2.8 0.6 0.2 0.1 x0=0.4,h=0.2,x3=1.0.分别用差分表中分别用差分表中对角线上对角线上的值的值和和最后一行最后一行的值的值,得得Newton向前和向后插值公式如下向前和向后插值公式如下:例例 给定给定f(x)在等距节点上的函数值表如下在等距节点上的函数值表如下:解解 先构先构(1)(2)当当 x=0.5时时,用公式用公式(1),(1),这时这时t=(x-x0)/h=0.5.将将t=0.5代代入入(1),(1),得得 f(0.5)N3(0.5)=1.64375.当当x=0.9时时,用公式用公式(2),(2),这时这时t=(x3-x)/h=0.5.将将t=0.5代代入入(2),(2),得得 f(0.9)N3(0.9)=2.46875.go 分段分段(1)(2)当当 x=0.5时时,用公式用公式(1),这时这时t=(x-本节内容提要本节内容提要Hermite插值 方法概述、几何意义、误差估计1.5 埃尔米特插值埃尔米特插值/*Hermite Interpolation*/本节内容提要本节内容提要1.5 埃尔米特插值埃尔米特插值不仅要求函数值重合，而且要求若干阶不仅要求函数值重合，而且要求若干阶导数导数也重合。也重合。即：要求插值函数即：要求插值函数 (x)满足满足 (xi)=f(xi),(xi)=f (xi),(mi)(xi)=f(mi)(xi).注：注：N 个条件可以确定个条件可以确定 阶多项式。阶多项式。N 1要求在要求在1个节点个节点 x0 处直到处直到m0 阶导数都重合的插阶导数都重合的插值多项式即为值多项式即为Taylor多项式多项式其余项为其余项为一般只考虑一般只考虑 f 与与f 的值。的值。不仅要求函数值重合，而且要求若干阶导数也重合。注：不仅要求函数值重合，而且要求若干阶导数也重合。注：N 个个例：例：设设 x0 x1 x2,已知已知 f(x0)、f(x1)、f(x2)和和 f(x1),求多项式求多项式 P(x)满足满足 P(xi)=f(xi)，i=0,1,2，且且 P(x1)=f(x1),并估计误差。并估计误差。模仿模仿 Lagrange 多项式的思想，设多项式的思想，设解：解：首先，首先，P 的阶数的阶数=3 +=213)()()()()(=0iiixhx1f xhxfxP h0(x)有根有根x1,x2，且且 h0(x1)=0 x1 是重根。是重根。)()()(22100 xxxxCxh =又又:h0(x0)=1 C0 h2(x)h1(x)有根有根 x0,x2 )()()(201xxxxBAxxh +=由余下条件由余下条件 h1(x1)=1 和和 h1(x1)=0 可解。可解。与与h0(x)完全类似。完全类似。(x)h1有根有根 x0,x1,x2 h1)()()(2101xxxxxxCx =h1又又:(x1)=1 C1 可解。可解。其中其中 hi(xj)=ij,hi(x1)=0,(xi)=0,(x1)=1 h1 h1与与 Lagrange 分析分析完全类似完全类似例：设例：设 x0 x1 x2,已知已知 f(x0)、f(一般地，已知一般地，已知 x0,xn 处有处有 y0,yn 和和 y0,yn，求，求 H2n+1(x)满足满足 H2n+1(xi)=yi，H2n+1(xi)=yi。解：解：设设+=ni)()()(=0iixhxhyixH2n+1 n=0iyi其中其中 hi(xj)=ij,hi(xj)=0,(xj)=0,(xj)=ij hi hihi(x)有根有根 x0,xi,xn且都是且都是2重根重根 )()()(2xlBxAxhiiii+=由余下条件由余下条件 hi(xi)=1 和和 hi(xi)=0 可解可解Ai 和和 Bi (x)hi有根有根 x0,xn,除了除了xi 外都是外都是2重根重根 hi)()(iili2(x)xxCx=hi又又:(xi)=1 Ci=1 hi)(x)(ili2(x)xx=设设则则一般地，已知一般地，已知 x0,xn 处有处有 y0,yx0 x1x2x3x4xH9(x)f(x)全导数的全导数的Hermite插值多项式的插值多项式的几何意义几何意义如如n=1时时Hermite插值多项式插值多项式 为为x0 x1x2x3x4xH9(x)f(x)全导数的全导数的He 求求Hermite多项式的基本步骤：多项式的基本步骤：写出相应于条件的写出相应于条件的hi(x)、hi(x)的组合形式；的组合形式；对每一个对每一个hi(x)、hi(x)找出尽可能多的条件给出的根；找出尽可能多的条件给出的根；根据多项式的总阶数和根的个数写出表达式；根据多项式的总阶数和根的个数写出表达式；根据尚未利用的条件解出表达式中的待定系数；根据尚未利用的条件解出表达式中的待定系数；最后完整写出最后完整写出H(x)。余项余项：带余项的带余项的HermiteHermite插值公式插值公式 例例已知已知 且在且在 处有处有求一个次数不超过求一个次数不超过3的多项式的多项式 求求Hermite多项式的基本步骤：多项式的基本步骤：写出相应于条件的写出相应于条件的h解解至少至少3次多项式，次多项式，三个零点，那三个零点，那么么解至少解至少3次多项式，次多项式，由导数插值条件由导数插值条件由导数插值条件由导数插值条件余项，记余项，记 的单根，的单根，的二重根，的二重根，在插值区间内有在插值区间内有5个零点个零点由由RolleTH，在区间内至少存在一个零在区间内至少存在一个零点点则有则有余项，记余项，记 的单根，在插值区间内有的单根，在插值区间内有5个零点由个零点由Rolle 本节内容提要本节内容提要分段线性插值 方法概述、几何意义、误差估计分段二次插值 几何直观、方法概述、误差估计三次样条插值简介 1.3 分段低次插值分段低次插值/*piecewise Interpolation*/本节内容提要本节内容提要1.3 分段低次插值分段低次插值1 1、从插值余项角度分析、从插值余项角度分析随着节点个数增加到随着节点个数增加到某个值某个值，误差反而会增加。，误差反而会增加。一、高次插值评述一、高次插值评述 为了提高为了提高插值精度插值精度，一般来说应该，一般来说应该增加增加插值节点的个数，插值节点的个数，这从插值余项的表达式也可以看出，但不能简单地这样认为，这从插值余项的表达式也可以看出，但不能简单地这样认为，原因是原因是前提条件是前提条件是 有有足够阶连续导数足够阶连续导数(即函数足够光滑即函数足够光滑)，但随着节点个数的增加，这个条件一般很难成立但随着节点个数的增加，这个条件一般很难成立。1、从插值余项角度分析随着节点个数增加到某个值，误差反而会增、从插值余项角度分析随着节点个数增加到某个值，误差反而会增注意下面图中注意下面图中曲线曲线的变化情况！的变化情况！例：例：在在 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)注意下面图中例：注意下面图中例：在在 5,5上考察上考察 RungeRunge现象现象：注：注：高次插值可能出现：在插值区间高次插值可能出现：在插值区间中部误差较小中部误差较小，而在而在端点附近误差较大端点附近误差较大的情形。的情形。RungeRunge现象现象RungeRunge现象说明并非节点越多（插值多项式次数现象说明并非节点越多（插值多项式次数越高），误差越小；越高），误差越小；高次插值的缺点高次插值的缺点RungeRunge现象的存在；现象的存在；克服方法克服方法分段低次插值分段低次插值；Runge现象：注：高次插值可能出现：在插值区间中部误差较小现象：注：高次插值可能出现：在插值区间中部误差较小分段插值的构造方法分段插值的构造方法将将插值区间插值区间划分为若干个小区间（通常取划分为若干个小区间（通常取等距划分等距划分）采用采用低次低次插值插值在区间在区间 上得到上得到分段函数分段函数分段插值的构造方法将插值区间划分为若干个小区间（通常取等距划分段插值的构造方法将插值区间划分为若干个小区间（通常取等距划一、分段线性插值一、分段线性插值/*piecewise linear interpolation*/1 1、方法概述：、方法概述：在每个区间在每个区间 上，用上，用1次多项式次多项式(直线直线)逼近逼近 f(x):分段分段线性线性插值插值函数函数一、分段线性插值一、分段线性插值/*piecewise linear in2 2、几何意义：、几何意义：分段线性插值从整体上看，逼近效果是较好的，但失分段线性插值从整体上看，逼近效果是较好的，但失去了原函数的去了原函数的光滑性光滑性。2、几何意义：、几何意义：分段线性插值从整体上看，逼近效果是较好的，但分段线性插值从整体上看，逼近效果是较好的，但3 3、误差估计：、误差估计：3、误差估计：、误差估计：只依赖于二阶导函数的界只依赖于二阶导函数的界 只依赖于二阶导函数的界只依赖于二阶导函数的界1 1、几何直观：、几何直观：二、分段二次插值二、分段二次插值/*Piecewise Square Interpolation*/分段抛物线弧段近似分段抛物线弧段近似 1、几何直观：、几何直观：二、分段二次插值二、分段二次插值/*Piecewise S在每个区间在每个区间 上，用上，用2次多项式次多项式(抛物线抛物线)逼近逼近 f(x)。2 2、方法概述：、方法概述：在每个区间在每个区间 分段分段二次插值二次插值函数函数分段二次插值函数分段二次插值函数3 3、误差估计：、误差估计：3、误差估计：、误差估计：收敛性好，计算简单；亦可根据其具体情况收敛性好，计算简单；亦可根据其具体情况 在不在不同区间上采用不同次数的插值公式；同区间上采用不同次数的插值公式；分段函数虽然在节点处连续但未必可导，因而分段函数虽然在节点处连续但未必可导，因而 光光滑度较差滑度较差。克服方法克服方法 三次样条插值三次样条插值优点优点缺点缺点 收敛性好，计算简单；亦可根据其具体情况优点缺点收敛性好，计算简单；亦可根据其具体情况优点缺点 分段插值存在着一个缺点分段插值存在着一个缺点,就是会导致插值函数就是会导致插值函数在子区间的端点在子区间的端点(衔接处衔接处)不光滑不光滑,即导数不连续即导数不连续,对于一对于一些实际问题些实际问题,不但要求一阶导数连续不但要求一阶导数连续,而且要求二阶导数而且要求二阶导数连续。为了满足这些要求连续。为了满足这些要求,人们引入了人们引入了样条插值样条插值的概念。的概念。1.5 样条插值函数样条插值函数 分段插值存在着一个缺点分段插值存在着一个缺点,就是会导致插值函数在就是会导致插值函数在所谓所谓“样条样条”(SPLINE)是工程绘图中的一种工具是工程绘图中的一种工具,它是有它是有弹性的细长木条弹性的细长木条,绘图时绘图时,用细木条连接相近的几个结点用细木条连接相近的几个结点,然后再进行拼接然后再进行拼接,连接全部结点连接全部结点,使之成为一条光滑曲线使之成为一条光滑曲线,且在结点处具有连续的曲率。样条函数就是对这样的曲且在结点处具有连续的曲率。样条函数就是对这样的曲线进行数学模拟得到的。它除了要求给出各个结点处的线进行数学模拟得到的。它除了要求给出各个结点处的函数值外函数值外,只需提供两个边界点处导数信息只需提供两个边界点处导数信息,便可满足对便可满足对光滑性的不同要求。光滑性的不同要求。所谓所谓“样条样条”(SPLINE)是工程绘图中的一种工具是工程绘图中的一种工具,它是有弹它是有弹一、样条函数的定义一、样条函数的定义 设设f(x)是区间是区间 a,b 上的一个连续可微函数上的一个连续可微函数,在区间在区间 a,b上给定一组基点上给定一组基点:a=x0 x1x2xn=b设函数设函数 s(x)满足条件满足条件 (1)s(x)在每个子区间在每个子区间xi,xi+1(i=0,1,2,n-1)上是次数上是次数不超过不超过m的多项式的多项式;(2)s(x)在区间在区间a,b上有上有m-1阶连续导数阶连续导数;则称则称s(x)是定义在是定义在a,b上的上的m次样条函数。次样条函数。x0，x1，x2,称为样条结点称为样条结点,其中其中x1,xn-1称为内结点称为内结点,x0,xn 称为边界称为边界结点。当结点。当m=3时时,便成为最常用的三次样条函数。便成为最常用的三次样条函数。一、样条函数的定义一、样条函数的定义 二、三次样条插值函数二、三次样条插值函数 设设y=f(x)在点在点 x0，x1，x2,xn的值为的值为 y0，y1，y2,yn，若函，若函数数S(x)满足下列条件：满足下列条件：(1)S(x)在每个子区间上是不超过在每个子区间上是不超过3次的多项式；次的多项式；(2)S(xi)=f(xi)=yi,i=0,1,2,n (1.1)(3)S(x)C2a,b.则称则称 S(x)为函数为函数 f(x)的三次样条插值函数的三次样条插值函数,简称三次样条。简称三次样条。二、三次样条插值函数二、三次样条插值函数 构造三次样条插值函数的方法有很多，这里介绍一个常构造三次样条插值函数的方法有很多，这里介绍一个常用的方法：三弯矩插值法用的方法：三弯矩插值法记记Mi=S(xi),f(xi)=fi=yi,考虑它在任一考虑它在任一区间区间xi,xi+1上的形式上的形式.根据三次样条的定义可知根据三次样条的定义可知 ,S(x)的二阶导数的二阶导数 S(x)在每一在每一个子区间个子区间xi,xi+1(i=0,1,2,n-1)上都是线性函数上都是线性函数.于是在于是在xi,xi+1 上上 S(x)=Si(x)的二阶导数表示成的二阶导数表示成 其中其中 hi=xi+1xi .对对 S(x)连续积分两次连续积分两次,并利用插值条件并利用插值条件 S(xi)=yi,得到得到 三、三次样条函数的构造三、三次样条函数的构造 构造三次样条插值函数的方法有很多，这里介绍一个常用的构造三次样条插值函数的方法有很多，这里介绍一个常用的 因此，只要能求出所有的因此，只要能求出所有的 M i，就能求出样条插值函数，就能求出样条插值函数 S(x).下面考虑下面考虑 Mi 的求法的求法 因此，只要能求出所有的因此，只要能求出所有的 M i，就能求出样条插值函数，就能求出样条插值函数 则由连续性则由连续性 S(xi-)=S(xi+),(i=1,2,n-1)得得 iMi-1+2Mi+iMi+1=di其中其中 上面的方程组有上面的方程组有n-1个方程，但有个方程，但有n+1个变量个变量 Mi，故需两个故需两个方程才能求唯一解，为此引入下列边界条件方程才能求唯一解，为此引入下列边界条件则由连续性上面的方程组有则由连续性上面的方程组有n-1个方程，但有个方程，但有n+1个变量个变量 Mi下面介绍几种常用的边界条件下面介绍几种常用的边界条件 第一型边界条件：第一型边界条件：已知已知 f(x)在两端点的导数在两端点的导数 f(a)和和 f(b)，要求，要求 S(a)=f(a),S(b)=f(b)第二型边界条件：第二型边界条件：已知已知f(x)在两端点的二阶导数在两端点的二阶导数 f“(a)和和 f(b)，要求，要求 S(a)=M0=f(a),S(b)=Mn=f(b)特别当特别当 S(a)=S(b)=0时，时，S(x)称为自然三次样条称为自然三次样条 第三型边界条件：第三型边界条件：已知已知 f(x)是以是以 b-a为周期的周期函数为周期的周期函数 ，要求，要求 S(x)满满 足周期条件足周期条件 S(a)=S(b),S(a+)=S(b-),S(a+)=S(b-)下面介绍几种常用的边界条件下面介绍几种常用的边界条件 三三次次样样条条插插值值问问题题加加上上第第 i 型型边边界界条条件件称称为为第第 i i 型型插插值值问问题题（i=1,2,3）可可以以证证明明第第i i型型插插值值问问题题的的解解是是存存在在且且唯唯一一的的。它们对应如下的三对角方程组：它们对应如下的三对角方程组：2 0 M0 d0 1 2 1 M1 d1 .=.(*).n-1 2 n-1 Mn-1 dn-1 n 2 Mn dn 三次样条插值问题加上第三次样条插值问题加上第 i 型边界条件称为第型边界条件称为第 i 型插值问型插值问对于第一型插值问题，取对于第一型插值问题，取 0=1，n=1,对于第二型插值问题，取对于第二型插值问题，取 0=0，n=0 对于第一型插值问题，取对于第一型插值问题，取 0=1，n=1,对于第三型插值问题，利用周期性，可导出对于第三型插值问题，利用周期性，可导出其中其中 以上各组条件与方程组以上各组条件与方程组(*)(*)联立，可以解出未知参数联立，可以解出未知参数M0，M1,Mn，然后代入，然后代入S(x)表达式，即可求得样条函数表达式，即可求得样条函数 。上面构造方法中上面构造方法中Mi相应于力学中细梁在相应于力学中细梁在xi处截面的弯矩，每一处截面的弯矩，每一个方程中又至多出现相邻的三个个方程中又至多出现相邻的三个Mi，通常称为，通常称为三弯矩法三弯矩法。总结以上论述，可得求三次样条的步骤为：总结以上论述，可得求三次样条的步骤为：（1 1）确定边界条件，判定是第几型插值问题；）确定边界条件，判定是第几型插值问题；（2 2）根据所确定的条件计算各值，形成方程组）根据所确定的条件计算各值，形成方程组(*)(*)；（3 3）解三对角方程组）解三对角方程组(*)(*)，求得，求得M0，M1，M2,Mn；（4 4）将求得的）将求得的Mi值代回值代回S(x)的表达式中，的表达式中，从而可求得函数从而可求得函数y=f(x)在任一点的近似值在任一点的近似值S(x)。以上各组条件与方程组以上各组条件与方程组(*)联立，可以解出未知参数联立，可以解出未知参数M0，M1 四、例题四、例题 例例1 1 已知函数已知函数 f(x）的数值表如下：的数值表如下：x 2 4 6 f(x)3 7 13 f(x)1 -1 试求试求 f(x)在在 2,6 上的三次样条插值函数及求上的三次样条插值函数及求 四、例题四、例题解：这是第一类边界条件的问题解：这是第一类边界条件的问题 ，n=2,hi=h,由公式由公式1=1=1/2，d1=3/2；n=0=1，d0=3,d2=-12得方程组得方程组 2 M0 +M1 =3 0.5 M0 +2M1 +0.5 M2=1.5 M1 +2 M2 =-12解得解得 M0 =0.25 ,M1 =2.5 M2=-7.25数值分析与计算方法数值分析与计算方法-第一章第一章-插值法课件插值法课件故所求的三次样条插值函数故所求的三次样条插值函数 -(1/48)(x-4)3+(5/24)(x-2)3 -(17/12)(x-4)+(8/3)(x-2),x2，4S(x)=-(5/24)(x-6)3-(29/48)(x-4)3 -(8/3)(x-6)+(107/12)(x-4),x4，6 故所求的三次样条插值函数故所求的三次样条插值函数例例2已知已知 f(x)在若干点处的值为：在若干点处的值为：f(0)=0,f(2)=16,f(4)=36,f(6)=54,f(10)=82,以及以及f(0)=8,f(10)=7.试试求求 f(x)的三次样条插值函数的三次样条插值函数s(x)以及以及 f(3),f(8)的近似值。的近似值。数值分析与计算方法数值分析与计算方法-第一章第一章-插值法课件插值法课件 解：构造一阶均差表解：构造一阶均差表 i xi f(xi)fxi,xi-1 1 0 0 8 2 2 16 10 3 4 36 9 4 6 54 7 5 10 82 由于由于 h1=h2=h3=2,h4=4,因此因此 d1=fx1,x2-f(0)=0，d2=fx2,x3-fx1,x2=2,数值分析与计算方法数值分析与计算方法-第一章第一章-插值法课件插值法课件 d1=fx1,x2-f(0)=0，d2=fx2,x3-fx1,x2=2,d3=fx3,x4-fx2,x3=-1,d4=fx4,x5-fx3,x4=-2,d5=f(10)-fx4,x5=0.方程组应为方程组应为 4 2 0 0 0 m1 04 2 0 0 0 m1 0 2 8 2 0 0 m2 2 2 8 2 0 0 m2 2 0 2 8 2 0 m3 =6 0 2 8 2 0 m3 =6 0 0 2 12 4 m4 -2 0 0 2 12 4 m4 -2 0 0 0 4 8 m5 0 0 0 0 4 8 m5 0解出解出 m1=-1,m2=2，m3=-1,m4=-1,m5=0.5因此可得因此可得 d1=fx1,x2-f(0)=0，d2=fx2 8X-1/2X2+1/4X3,X0,2 16+9(X-2)+(X-2)2+1/4(X-2)3,X2,4 S(X)=36+10(X-4)-1/2(X-4)2,X4,6 54+8(X-6)-1/2(X-6)2+1/16(X-6)3,X6,10 S(3)=S2(3)=25.75 S(8)=S4(8)=68.5 8