函数的数值逼近课件.ppt

《函数的数值逼近课件.ppt》由会员分享，可在线阅读，更多相关《函数的数值逼近课件.ppt（82页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第四章第四章 函数的数值逼近函数的数值逼近4.0 4.0 4.0 4.0 插值与拟合插值与拟合插值与拟合插值与拟合4.1 4.1 4.1 4.1 插值的基本理论插值的基本理论插值的基本理论插值的基本理论4.2 Lagrange4.2 Lagrange4.2 Lagrange4.2 Lagrange插值多项式插值多项式插值多项式插值多项式4.3 4.3 4.3 4.3 分段插值与保形插值分段插值与保形插值分段插值与保形插值分段插值与保形插值4.4 4.4 4.4 4.4 样条插值样条插值样条插值样条插值4.5 4.5 4.5 4.5 曲线拟合的最小二乘方法曲线拟合的最小二乘方法曲线拟合的最小二乘

2、方法曲线拟合的最小二乘方法4.6 4.6 4.6 4.6 函数的最佳平方逼近函数的最佳平方逼近函数的最佳平方逼近函数的最佳平方逼近14.0 插值与拟合插值与拟合1 1、问题的提出、问题的提出、问题的提出、问题的提出 函数没有明确的表达式函数没有明确的表达式 函数有明确的表达式，但不是（分段）有理函数函数有明确的表达式，但不是（分段）有理函数2 2、插值与拟合、插值与拟合、插值与拟合、插值与拟合 插值问题：作一条曲线，其类型是事先人为给定的插值问题：作一条曲线，其类型是事先人为给定的（比如：代数多项式），使该曲线经过所有已知点。（比如：代数多项式），使该曲线经过所有已知点。拟合问题：作一条指定类

3、型的曲线，使该曲线能在拟合问题：作一条指定类型的曲线，使该曲线能在“一定意义一定意义”下逼近已知点。下逼近已知点。下一页零件2图4.1 心形图上一页34.1 插值的基本理论插值的基本理论1 1、插值问题的提法、插值问题的提法、插值问题的提法、插值问题的提法 基本提法：对于给定函数表yny1y0y=f(x)xnx1x0 x表4.1（其中f(x)在区间a,b 上连续，x0,x1,xn 是a,b 上n+1 个互异点），要求在某函数类(x)中求一个函数(x)，使 （4.1)4 根据给出的函数表根据给出的函数表(4.1)，求不高于，求不高于n 次的代数多项式次的代数多项式 (4.2)使使 (4.3)几何

4、意义几何意义：通过曲线：通过曲线y=f(x)上的上的n+1 个点个点Mi(xi,yi)(i=0,1,n)，作一条，作一条n 次代数多项式曲线次代数多项式曲线y=Pn(x)近似代替曲线近似代替曲线y=f(x)，如图，如图(4.2)所示。所示。图 4.22 2、多项式插值问题的基本提法、多项式插值问题的基本提法、多项式插值问题的基本提法、多项式插值问题的基本提法满足插值条件满足插值条件(4.3)的多项式的多项式(4.2)，称为函数，称为函数f(x)在结在结点点xi(i=0,1,n)上的上的 n 次插值多项式次插值多项式。63 3、插值多项式的存在唯一性、插值多项式的存在唯一性、插值多项式的存在唯一

5、性、插值多项式的存在唯一性 由插值条件由插值条件(4.3)知，插值多项式知，插值多项式Pn(x)的系数的系数a0,a1,an 满足线性方程组满足线性方程组 (4.4)其系数行列式其系数行列式7 系数行列式系数行列式 D D 是一个是一个n+1 n+1 阶的阶的VandermondVandermond行列式，行列式，因因结点互异，故结点互异，故D0D0。再。再由由CramerCramer法则，线性法则，线性方程组有唯一方程组有唯一解。于是有解。于是有 定理定理1.当插值结点互异时，满足插值条件当插值结点互异时，满足插值条件(4.3)的的n 次插值多项式次插值多项式Pn(x)存在且唯一。存在且唯一

6、。8证：证：证：证：由插值条件由插值条件(4.3)可知，可知，Rn(xi)=0 (i=0,1,n)故可设故可设 Rn(x)=k(x)n+1(x)(4.6)其中其中k(x)为待定函数。为待定函数。对于对于a,b 上异于上异于xi 的任一点的任一点x，作辅助函数，作辅助函数F(t)=f(t)Pn(t)k(x)n+1(t)则则 F(t)在在a,b 上具有上具有n+1 阶导数阶导数F(n+1)(t)=f(n+1)(t)k(x)(n+1)!(4.7)且且F(x)=F(x0)=F(x1)=F(xn)=0即即F(t)在在a,b 上至少有上至少有n+2 个互异的零点个互异的零点x,x0,x1,xn.由由洛尔定

7、理洛尔定理知，知，F(t)在两个零点间在两个零点间 F(t)至少有一至少有一个零点，故个零点，故F(t)在在(a,b)上至少有上至少有n+1个互异零点。对个互异零点。对F(t)再应用洛尔定理，依次类推，可知再应用洛尔定理，依次类推，可知F(n+1)(t)在在(a,b)内至少有一个零内至少有一个零10点点，即，即F(n+1)()=0.于是，由于是，由(4.7)式知，式知，f(n+1)()k(x)(n+1)!0代入代入(4.6)式，即得结论。式，即得结论。对于对于x=xi(i=0,1,n)，(4.5)式显然成立。式显然成立。故故11且条件且条件 满足条件满足条件(4.8)式的式的n 次代数多项式次

8、代数多项式lk(x)(k=0,1,n),称为在称为在n+1 个结点个结点xi(i=0,1,n)上的上的n n 次次次次插值基函数插值基函数插值基函数插值基函数。这时可确定系数这时可确定系数a.于是，于是，13于是，于是，特例，当n=1 时，称为线性插值线性插值当n=2 时，称为抛物插值抛物插值，图像如下1516例解:18且19Lagrange插值多项式的缺点：插值基函数计算复杂高次插值的精度不一定高无承袭性。增加一个节点，所有的基函数都要重新计算202 2、Newton Newton 插值插值插值插值 为了克服Lagrange插值的缺点，我们把多项式构造成如下形式：这种形式的插值多项式称为n

9、n 次次次次Newton Newton 插值多项式插值多项式插值多项式插值多项式，记为Nn(x),即其中系数ai(i=0,1,n)可由插值条件 Nn(xi)=yi(i=0,1,n)确定。引入差商（均差）的概念。(4.10)21定义1.称 为函数f(x)关于点xi,xj 的一阶差商；称 (i,j,k 互异)为f(x)在点xi,xj,xk 处的二阶差商；一般地，称为f(x)在点xi0,xi1,xim 处的m 阶差商；特别地，规定零阶差商f xi =f(xi).差商的性质差商的性质.m 阶差商可表为函数值阶差商可表为函数值f(xi0),f(xi1),f(xim)的线的线性组合，即性组合，即(4.12

10、)(4.11)22 为了便于计算与应用，通常采用表格形式计算差商，如表(4.2).xkf(xk)一阶差商二阶差商三阶差商四阶差商x0f(x0)x1f(x1)f x0,x1x2f(x2)f x1,x2f x0,x1,x2x3f(x3)f x2,x3f x1,x2,x3f x0,x1,x2,x3x4f(x4)f x3,x4f x2,x3,x4f x1,x2,x3,x4f x0,x1,x2,x3,x4:表(4.2)24 用差商表示Newton 插值多项式的系数。事实上，由插值条件Nn(x0)=f(x0)可得 a0=f(x0).再由插值条件Nn(x1)=f(x1),即 a0+a1(x1-x0)=f(x

11、1)进一步由插值条件Nn(x2)=f(x2),即 a0+a1(x2-x0)a2(x2-x0)(x2-x1)=f(x2)25 一般地，可由归纳法证明（自己验证）故满足插值条件Nn(xi)=f(xi)(i=0,1,n)的n 次Newton 插值多项式为(4.14)例例例例2 2 给出f(x)的函数表（见下表），试用线性插值，抛物插值和4次Newton插值求f(0.596)的近似值，并估计它们的截断误差。x0.400.550.650.800.901.05f(x)0.410750.578150.696750.888111.026521.2538226故用线性插值得f(0.596)N1（0.596）=0

12、.41075 1.11600(0.596-0.40)=0.629486用抛物插值得f(0.596)N2（0.596）N1(0.596)+0.28000(0.596-0.40)(0.596-0.55)0.63201048用4次Newton插值得f(0.596)N4（0.596）28|R1(x)|fx0,x1,x22(0.596)|2.53103|R2(x)|fx0,x1,x2,x33(0.596)|9.61105|R4(x)|fx0,x55(0.596)|3.63109 这说明插值多项式的次数越高，误差越小，越可能接这说明插值多项式的次数越高，误差越小，越可能接这说明插值多项式的次数越高，误差越

13、小，越可能接这说明插值多项式的次数越高，误差越小，越可能接近真实值。近真实值。近真实值。近真实值。N2(0.596)+0.19733(0.596-0.4)(0.596 0.55)(0.596-0.65)+0.03134(0.596-0.4)(0.596-0.55)(0.596-0.65)(0.596-0.8)0.63192 由差商的性质，插值多项式的余项分别为29例题例题 4考虑在区间考虑在区间-1,1上的函数上的函数构造等距节点上的构造等距节点上的Lagrange插值多项式。插值多项式。目的目的 观察当插值节点逐渐增多时，插值多项式对原函数的拟观察当插值节点逐渐增多时，插值多项式对原函数的拟

14、合变化情况。合变化情况。tryrunge.m314.3 4.3 分段插值与保形插值分段插值与保形插值 1 1、分段插值、分段插值、分段插值、分段插值 引例引例引例引例 fenduanex2.m fenduanex2.m 给定给定n+1 个结点个结点a=x0 x1xn=b上的函数值上的函数值y0,y1,yn，求一折线函数，求一折线函数Ih(x)满足：满足：则称则称Ih(x)为为分段线性插值函数分段线性插值函数。32 由定义可知Ih(x)在每一个小区间xk,xk+1上可表示为若用插值基函数表示，则在整个区间a,b上Ih(x)为33342 2、保形插值保形插值保形插值保形插值 给定a,b 上的一种分

15、划及f(x)在分划点上的函数值f(xk)=yk,及f(xk)=dk(k=0,1,n),则作一个分段三次分段三次Hermite 插值多项式插值多项式 P(x),满足条件 P(x)C1a,b；P(xk)=yk,P(xk)=dk,k=0,1,n；P(x)在每个小区间上是三次多项式。在每个小区间上是三次多项式。根据前面的结果，不难作出各个点上的插值基函数。根据前面的结果，不难作出各个点上的插值基函数。3536dk未知？37dk的取法的取法记记第第k个小区间的区间长度个小区间的区间长度第第k个小区间分段线性插值斜率个小区间分段线性插值斜率如果如果 与与 符号相同，符号相同，则令则令如果如果 与与 符号相

16、反，符号相反，则令则令极值点保持原来曲线的走向38121517211816654321考虑函数表考虑函数表生成它的保形插值多项式。生成它的保形插值多项式。例题例题 5Chap4_3.m394.4 4.4 样条插值样条插值对于给定函数表xx0 x1xny=f(x)y0y1yn表4.2（其中 ），若函数若函数S(x)C2a,b满足条件：满足条件：S(x)在每个子区间xi-1,xi(i=1,2,n)上都是不高于三次的多项式；S(x),S(x),S(x)在区间a,b 上连续；S(xi)=yi(i=0,1,n).（A1）则称S(x)为函数f(x)关于结点x0,x1,xn 的三次样条插值三次样条插值函数函

17、数。40 条件表明S(x)是一个分段三次多项式分段三次多项式，用S Si i(x)(x)表示S(x)在第i i 个子区间上的表达式，则Si(x)形如其ai,bi,ci,di 待定，子区间共有n 个，需确定4n 个系数。另外，根据条件，有共有4n-2个方程，显然要确定S(x)还差两个条件。41 边界条件的取法边界条件的取法边界条件的取法边界条件的取法 .特别地，当 时，称为自自然边界条件然边界条件。.当原函数f(x)以b-a 为周期的周期函数，则要求S(x)也是周期函数。42 样条插值函数的建立样条插值函数的建立样条插值函数的建立样条插值函数的建立 构造满足插值条件（A-1）及相应边界条件的三次

18、样条插值函数S(x)的表达式可以有多种方法。例如，可以直接利用分段三次Hermite插值，只要假定S(xj)=mj(j=0,1,n),于是其中 是插值基函数。利用插值条件及相应的边界条件，则可得关于mj(j=0,1,n)的三对角方程组，求出mj则得到所求的三次样条函数S(x).利用利用S(x)S(x)的二阶导数值的二阶导数值S(x)=S(x)=MMj j(j(j=0,1,n)=0,1,n)表示表示S(x)S(x)43交互实验：插值方法比较目的：通过比较几种不同插值方法，使大家对四目的：通过比较几种不同插值方法，使大家对四种插值效果在感性上有所认识，便于以后使用。种插值效果在感性上有所认识，便于

19、以后使用。tryinterp.m44实例：考察某种纤维的强度与其拉伸倍数的关系实例：考察某种纤维的强度与其拉伸倍数的关系,下表下表是实际测定的是实际测定的24个纤维样品的强度与相应的拉伸倍数个纤维样品的强度与相应的拉伸倍数是记录是记录:4.5 4.5 曲线拟合的最小二乘方法曲线拟合的最小二乘方法45纤维强度随拉伸倍数增加而增加并且24个点大致分布在一条直线附近-(1)46必须找到一种度量标准来衡量什么曲线最接近所有数据点必须找到一种度量标准来衡量什么曲线最接近所有数据点一、最小二乘法的基本概念一、最小二乘法的基本概念一般使用一般使用在回归分析中称为残差在回归分析中称为残差称为平方误差称为平方误

20、差47在回归分析中称为残差平方和在回归分析中称为残差平方和从而确定从而确定(1)中的待定系数中的待定系数注意注意(1)式是一条直线式是一条直线因此将问题一般化因此将问题一般化48仍然定义平方误差仍然定义平方误差49我们选取的度量标准是我们选取的度量标准是-(2)-(3)5051二、法方程组二、法方程组由由可知可知因此可假设因此可假设因此求最小二乘解转化为因此求最小二乘解转化为二次函数二次函数52由多元函数取极值的必要条件得即53-(4)即54引入记号引入记号则由内积的概念可知则由内积的概念可知-(5)-(6)显然内积满足交换律显然内积满足交换律55方程组方程组(4)便可化为便可化为-(7)将其

21、表示成矩阵形式将其表示成矩阵形式-(8)56并且其系数矩阵为对称阵并且其系数矩阵为对称阵所以法方程组的系数矩阵非奇异所以法方程组的系数矩阵非奇异,即即根据根据Cramer法则法则,法方程组有唯一解法方程组有唯一解57即是的最小值所以因此58作为一种简单的情况,基函数之间的内积为平方误差59 回到本节开始的实例回到本节开始的实例，从散点图可以看出，从散点图可以看出纤维强度和拉伸倍数之间近似与线性关系纤维强度和拉伸倍数之间近似与线性关系故可选取线性函数故可选取线性函数为拟合函数，其基函数为为拟合函数，其基函数为建立法方程组建立法方程组根据内积公式，可得根据内积公式，可得60法方程组为解得平方误差为

22、61拟合曲线与散点的关系如右图:62三、数据拟合的三、数据拟合的Matlab实现实现1、polyfit()p=polyfit(x,y,n)其中其中x,y是数据点，是数据点，n是拟合多项式次是拟合多项式次数，数，p是多项式系数（由高到低）是多项式系数（由高到低）2、polyval()y=polyval(p,x)其中其中p是拟合多项式系数，是拟合多项式系数，y是拟合多项是拟合多项式在式在x点的值。点的值。注意：注意：当已知当已知n个点处的函数值，而拟合多项式的次数为个点处的函数值，而拟合多项式的次数为n-1时，则拟合函数时，则拟合函数polyfit()就是计算就是计算n-1阶插值多项式的阶插值多项

23、式的值。值。Least.m63应用实例：人口预测应用实例：人口预测概念：内插、外推概念：内插、外推censusgui.m644.6 4.6 函数的最佳平方逼近函数的最佳平方逼近 设有函数设有函数 ，总可以在一定，总可以在一定意义下，确定的空间中求已知函数的近似，这类问题称为意义下，确定的空间中求已知函数的近似，这类问题称为函数逼近函数逼近。例如例如是是n+1维的线性空间。在维的线性空间。在Pn上定义内积上定义内积其中其中 称为权函称为权函数。数。65若存在若存在 ，使，使得得 则称则称 为函数为函数 的最的最佳平方逼近多项式。佳平方逼近多项式。考虑一般的最佳平方逼近问题考虑一般的最佳平方逼近问

24、题是一线性空间。是一线性空间。66若存在若存在 ，使，使得得 则称则称 为函数为函数 在在上的最佳平方逼近上的最佳平方逼近多项式。多项式。即求解函数即求解函数的极值问题。该函数取得极值的必要条件是的极值问题。该函数取得极值的必要条件是67类似前面讨论类似前面讨论用内积符号写出来，即用内积符号写出来，即称为最佳平方逼近问题的法方程。称为最佳平方逼近问题的法方程。定理：设法方程的解为定理：设法方程的解为 ，则，则确为函数确为函数 在在上的最佳平方逼近多项式。上的最佳平方逼近多项式。68小小 结结函数的数值逼近：函数的数值逼近：插值问题插值问题 Lagrange插值插值 Newton插值插值 分段插

25、值和保形插值分段插值和保形插值 样条插值样条插值拟合拟合 最小二乘拟合最小二乘拟合 最佳平方逼近最佳平方逼近69作作 业业P 90 2、5（a）补充：补充：1、求一个次数不高于、求一个次数不高于4次的多项式次的多项式P(x)，使它满足，使它满足P(0)=P(0)=0,P(1)=P(1)=1,P(2)=1.2、用最小二乘法求一形如、用最小二乘法求一形如y=a+bx2的多项式，使与下列数的多项式，使与下列数据相拟合：据相拟合：xi1925313844yi19.032.349.073.397.8703、求解矛盾方程组、求解矛盾方程组71补充补充补充补充：HermiteHermite插值插值插值插值

26、插值函数在节点上插值函数在节点上函数值、对应的导数值、甚至高阶导函数值、对应的导数值、甚至高阶导数值相等数值相等，则满足这种要求的插值多项式称为，则满足这种要求的插值多项式称为Hermite Hermite 插值插值插值插值多项式多项式多项式多项式。下面只讨论函数值与导数个数相等的情形。下面只讨论函数值与导数个数相等的情形。设在设在 上，上，yi=f(xi),mi=f(xi)(i=0,1,n)，要求插值多项式，要求插值多项式H(x)满足条件满足条件 (A1)这里给出这里给出2n+2 个个相互独立相互独立的条件，可唯一确定一个次数不的条件，可唯一确定一个次数不超过超过2n+1 的多项式的多项式H

27、2n+1(x)=H(x),其形式为其形式为72 采用基函数方法确定系数。采用基函数方法确定系数。先求插值基函数先求插值基函数 及及 共有共有2n+2 个，每个基函数都是个，每个基函数都是2n+1 次多项式，且满足条次多项式，且满足条件件(A2)于是，满足于是，满足插值条件插值条件(A1)的插值多项式的插值多项式H2n+1(x)可写成用插值基函数表示的形式可写成用插值基函数表示的形式 下面确定下面确定 及及 ，利用，利用Lagrange 插值基函数插值基函数li(x),令令(A3)73由由(A2)整理得：整理得：解出：解出：由由两端取对数再求导，得两端取对数再求导，得74于是，于是，同理可得，同

28、理可得，定理定理定理定理 满足条件满足条件满足条件满足条件(A(A1)1)的插值多项式的插值多项式的插值多项式的插值多项式H H2n+12n+1(x)(x)是唯一的。是唯一的。是唯一的。是唯一的。证明：证明：用用反证法反证法。假设。假设H2n+1(x)及及 均满足条均满足条件件(A1),于是，于是，在点在点xi(i=0,1,n)均有二重根，即均有二重根，即 有有2n+2 个根，个根，但但 是不高于是不高于2n+1 次多项式，故次多项式，故 唯一性得证。唯一性得证。(A4)(A5)75定理定理定理定理 若若f(x)在在(a,b)内有内有2n+2 阶导数存在，则阶导数存在，则Hermite 插值多

29、项式余项插值多项式余项其中其中 且与且与x有关。有关。（证明方法类似前面，自证）（证明方法类似前面，自证）特例，当特例，当n=1 n=1 时，可取节点为时，可取节点为xk 及及xk+1，插值多项式为，插值多项式为H3(x),满足条件满足条件相应的插值基函数为相应的插值基函数为 ，它们满足条件，它们满足条件(A6)(A7)7677 根据根据(A4)及及(A5)的一般表达式，可得到的一般表达式，可得到(A8)(A9)78 于是，满足插值条件于是，满足插值条件(A7)式的插值多项式为式的插值多项式为(A10)其余项其余项R3(x)=f(x)-H3(x),由由(A6)式得式得79例例例例 求满足求满足P(xj)=f(xj)(j=0,1,2)及及P(x1)=f(x1)的插的插值多项式及其余项表达式。值多项式及其余项表达式。解：解：解：解：由给定条件，可确定次数不超过由给定条件，可确定次数不超过3的插值多项式。因的插值多项式。因此多项式通过点此多项式通过点(x0,f(x0),(x1,f(x1)及及(x2,f(x2)，根据根据Newton插值算法，故其形式为插值算法，故其形式为其中其中A为待定常数，可由条件为待定常数，可由条件P(x1)=f(x1)确定，代入上确定，代入上式，计算可得式，计算可得80为了求出余项R(x)=f(x)-P(x)的表达式，可设其中k(x)为待定函数。构造8182