计算方法第四章ppt课件.ppt

《计算方法第四章ppt课件.ppt》由会员分享，可在线阅读，更多相关《计算方法第四章ppt课件.ppt（62页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目第第4 4章章 插值法和曲线拟合插值法和曲线拟合4.1 4.1 插值法的基本理论插值法的基本理论4.2 4.2 拉格朗日插值多项式拉格朗日插值多项式4.3 4.3 牛顿均差插值多项式牛顿均差插值多项式4.4 4.4 三次样条插值三次样条插值4.5 4.5 曲线拟合的最小二乘法曲线拟合的最小二乘法认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目4.1.1 插值问题及代数多项式插值插值问题及代数多项式插值函数函数

2、y=f(x)给出一组函数值给出一组函数值 x:x0 x1 x2 xny:y0 y1 y2 yn其中其中x0,x1,x2,xn是区间是区间a,b上的互异点，要构造一上的互异点，要构造一个简单的函数个简单的函数(x)作为作为f(x)的近似表达式，使满足的近似表达式，使满足(插值原则、插值条件插值原则、插值条件)这类问题称为这类问题称为插值问题插值问题。-f(x)的的插值函数插值函数,f(x)-被插值函数被插值函数x0,x1,x2,xn-插值基点插值基点 求插值函数的方法称为求插值函数的方法称为插值法插值法。若若xa,b，需要计算，需要计算f(x)的近似值的近似值(x),则称则称x为为插值点插值点。

3、认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目当选择代数多项式作为插值函数时，称为代数多项式当选择代数多项式作为插值函数时，称为代数多项式插值问题插值问题:代数多项式插值问题代数多项式插值问题:设函数设函数y=f(x)在在a,b有定义有定义,且已知在且已知在n+1个点个点ax0 x1xnb上的函数值上的函数值y0,y1,yn.,要求要求一个次数不高于一个次数不高于n的多项式的多项式使满足插值原则使满足插值原

4、则 称称Pn(x)为为f(x)的的n次插值多项式次插值多项式。这样的插值多项式是否存在、唯一？这样的插值多项式是否存在、唯一？认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目定理定理4.1在在n+1个互异基点处满足插值原则且次数不超个互异基点处满足插值原则且次数不超过过n的多项式的多项式Pn(x)是存在并唯一的。是存在并唯一的。证证 其系数行列式其系数行列式 因此方程组存在唯一的解因此方程组存在唯一的解，因此，因此Pn(x)存在并唯一。存在并唯一。认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫

5、工作高度重视，已经展开了“精准扶贫”项目4.1.2插值多项式的误差插值多项式的误差截断误差截断误差：也称为也称为Pn(x)的的余项余项。定理定理4.2设函数设函数f(x)在包含基点在包含基点x0,x1,xn的区间的区间a,b上连续，在上连续，在(a,b)上具有上具有n+1阶导数，阶导数，Pn(x)为满为满足插值原则的足插值原则的n次插值多项式，则对任一点次插值多项式，则对任一点xa,b，总存在相应的点总存在相应的点(a,b)，使，使其中其中 证证 当当 x=xi(i=0,1,n)时时，由由 插插 值值 条条 件件 知知Rn(xi)=0，故结论显然成立。，故结论显然成立。当当x是是a,b上任一个

6、固定点，但不是插值基点时，上任一个固定点，但不是插值基点时，认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目作辅助函数作辅助函数根据罗尔定理，在根据罗尔定理，在F(t)的两个零点之间至少有一点使导的两个零点之间至少有一点使导数为数为0，即，即F(t)在区间在区间a,b上至少有上至少有n+2个互异的零点个互异的零点x,x0,x1,xn。F(n+1)()=f(n+1)()=0从而结论成立。从而结论成立。依此类推，可知依此类推，可知F(n+1)(t)在在(a,b)内至少有一个零点内至少有一个零点，则，则F(t)在在(a,b)内至少

7、有内至少有n个互异零点个互异零点F(t)在在(a,b)内至少有内至少有n+1个互异的零点个互异的零点认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目推推论论当当f(x)是是次次数数不不超超过过n的的多多项项式式时时，其其n次次插插值值多项式就是多项式就是f(x)本身。本身。证明证明因为因为f(n+1)(x)=0，从而，从而Rn(x)0，Pn(x)f(x)。误差公式的用法：误差公式的用法：，则截断误差估计为，则截断误差估计为 如果如果设设min x0,x1,xn=a，maxx0,x1,xn=b当插值点当插值点x(a,b)时称为

8、时称为内插内插，否则称为，否则称为外插外插。认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目例例 若利用若利用 在在100和和144的值，对的值，对 做一次做一次插值，估计误差是多少？插值，估计误差是多少？解解 插值基点插值基点x0=100,x1=144,插值点插值点 110.认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目4.2 4.2 拉格朗日插值多项式拉格朗日插值多项式4.2.1 4.2.1 线性插值和二次插值线性插值和二次插值4.2.2 n4.2.

9、2 n次拉格朗日插值次拉格朗日插值认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目4.2.1 4.2.1 线性插值和二次插值线性插值和二次插值1线性插值线性插值-n=1时的代数多项式插值时的代数多项式插值已知已知f(x0)=y0，f(x1)=y1,x0 x1xx0 x1yy0 y1要构造线性函数要构造线性函数 P1(x)=a0+a1 x ,使满足插值条件使满足插值条件 P1(x0)=y0,P1(x1)=y1.（线性插值多项式）（线性插值多项式）（拉格朗日线性（拉格朗日线性插值多项式）插值多项式）公式的结构：它是两个一次函数的

10、线性组合公式的结构：它是两个一次函数的线性组合（线性插值（线性插值基函数）基函数）认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目基函数的性质基函数的性质认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目线性插值多项式的截断误差为线性插值多项式的截断误差为 是在包含是在包含x,x0,x1 的区间内某数。的区间内某数。例例1 给定函数给定函数y=lnx在两点在两点10、11的值如下表，试用线性插值求的值如下表，试用线性插值求ln10.5的的近似值，并估计截断误

11、差。近似值，并估计截断误差。解解 f(x)=ln x,x0=10,x1=11,x=10.5ln 10.5P1(10.5)=x10 11y2.303 2.398认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目2二次插值二次插值-n=2时的代数多项式插值时的代数多项式插值已知已知f(x)在三个互异点在三个互异点x0,x1,x2的函数值的函数值y0,y1,y2 xx0 x1 x2yy0 y1 y2要构造次数不超过二次的多项式要构造次数不超过二次的多项式 使满足插值条件使满足插值条件 公式的构造：公式的构造：先对每个基点先对每个基点

12、xi构造构造二次插值基函数二次插值基函数li(i=0,1,2)，使满足，使满足认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目 （拉格朗日二次插值多项式（拉格朗日二次插值多项式）P2(x)的截断误差为的截断误差为是包含是包含x0,x1,x2,x的区间内某数。的区间内某数。认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目例例2已知函数已知函数y=f(x)的观测数据如表所示，试求的观测数据如表所示，试求其拉格朗日插值多项式，并计算其拉格朗日插值多项式，并计算f

13、(1.5)的近似值。的近似值。x0 1 2y2 -1 4解解 认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目 二次插值也称之为二次插值也称之为抛物插值抛物插值 。当三点当三点(x0,y0),(x1,y1),(x2,y2)位于一条直线上位于一条直线上时，显然插值函数的图形是直线。时，显然插值函数的图形是直线。认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目4.2.2 n次拉格朗日插值 作基点作基点xi的的n次插值基函数次插值基函数(i=0,1,n)：基函数

14、具有性质基函数具有性质:n次次拉格朗日插值多项式拉格朗日插值多项式 认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目计算框图：计算框图：认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目高次代数多项式插值的龙格（高次代数多项式插值的龙格（Runge)现象现象所以，七、八次以上的代数多项式插值很少使用。所以，七、八次以上的代数多项式插值很少使用

15、。认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目4.3 4.3 牛顿均差插值多项式牛顿均差插值多项式4.3.1 4.3.1 均差及均差表均差及均差表 4.3.24.3.2牛顿均差型插值多项式牛顿均差型插值多项式 认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目目的：构造具有如下形式的插值多项式：目的：构造具有如下形式的插值多项式：它满足递推性：它满足递推性：4.3.1均差及均差表均差及均差表一阶均差一阶均差 二阶均差二阶均差 例如设例如设 则则认识到了贫

16、困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目k阶均差阶均差 例如例如零阶均差定义为函数值本身，即零阶均差定义为函数值本身，即 均差具有均差具有对称性对称性：任意改变基点的次序后其值不变。例：任意改变基点的次序后其值不变。例如如 f0,2,4=f2,0,4=f4,2,0等等。等等。认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目均差表均差表 xif(xk)1阶阶2阶阶3阶阶 4阶阶x0f(x0)x1f(x1)f(x0,x1)x2f(x2)f(x1,x2)f(x0,

17、x1,x2)x3f(x3)f(x2,x3)f(x1,x2,x3)f(x0,x1,x2,x3)x4f(x4)f(x3,x4)f(x2,x3,x4)f(x1,x2,x3,x4)f(x0,x1,x2,x3,x4)计算规律计算规律：任一个：任一个k(1)阶均差的数值等于一个分式的值，其分子阶均差的数值等于一个分式的值，其分子为所求均差左侧的数减去左上侧的数，分母为所求均差同一行最左为所求均差左侧的数减去左上侧的数，分母为所求均差同一行最左边的基点值减去由它往上数第边的基点值减去由它往上数第k个基点值。个基点值。注意：均差表中，对角线上的均差是构造牛顿型插值公式的重要数据。注意：均差表中，对角线上的均差

18、是构造牛顿型插值公式的重要数据。粗线框出的部分在计算机上可存入二维数组粗线框出的部分在计算机上可存入二维数组认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目均差表的数据构成一个矩阵均差表的数据构成一个矩阵F：F00=f(x0)F10=f(x1),F11=fx0,x1F20=f(x2),F21=fx1,x2,F22=fx0,x1,x2F30=f(x3),F31=fx2,x3,F32=fx1,x2,x3,F33=fx0,x1,x2,x3 Fi,j-1=fxi-j+1,xi Fi-1,j-1=fxi-j,xi-1 计算机上计算均差

19、表的公式计算机上计算均差表的公式 一般有一般有 Fi,j=fxi-j,xi-j+1,xi-1,xi 认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目 例例4.4 已知函数已知函数y=f(x)的观测数据如表，试构造均差的观测数据如表，试构造均差表，并求表，并求f2,4,5及及f2,4,5,6的值。的值。x0 2 4 5 6f(x)1 5 9 -4 13解解n=4,构造均差表构造均差表 xif(xi)1阶阶2阶阶3阶阶4阶阶0245621159-4132-13170-515-15f2,4,5=-5f2,4,5,6=5认识到了贫困

20、户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目4.3.2牛顿均差型插值多项式牛顿均差型插值多项式根据线性插值的点斜式根据线性插值的点斜式牛顿均差型线性插值多项式：牛顿均差型线性插值多项式：设设 由由 可得可得 牛顿均差型二次插值多项式：牛顿均差型二次插值多项式：可得可得认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目牛顿均差型牛顿均差型n次插值多项式次插值多项式(n次牛顿均差插值多项式次牛顿均差插值多项式)计算牛顿均差插值多项式的步骤：计算牛顿均差插值多项式的步骤：

21、（1）作均差表）作均差表（2）根根据据公公式式计计算算牛牛顿顿型型插插值值多多项项式式（表表中中对对角角线上各均差值就是线上各均差值就是Pn(x)的各项系数）。的各项系数）。余项公式余项公式的牛顿形式：的牛顿形式：认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目例例4.5已知函数已知函数y=f(x)的观测数据如例的观测数据如例4.4，试用全部基点，试用全部基点构造牛顿均差插值多项式，并用二次插值求构造牛顿均差插值多项式，并用二次插值求f(3)的近似值。的近似值。解解用全部基点时，用全部基点时，n=4，先作均差表，先作均差表,

22、见例见例4.4。P4(x)=f(0)+f0,2(x-0)+f0,2,4(x-0)(x-2)+f0,2,4,5(x-0)(x-2)(x-4)+f0,2,4,5,6(x-0)(x-2)(x-4)(x-5)xif(xi)1阶阶2阶阶3阶阶4阶阶0245622-1317159-4130-515-151=1+2x-x(x-2)(x-4)+x(x-2)(x-4)(x-5)认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目用二次插值求用二次插值求f(3)时时n=2，x=3，作内插取，作内插取 x0=2,x1=4,x2=5f(3)P2(3)=

23、f(2)+f2,4(3 2)+f2,4,5(3-2)(3-4)=7-5(3-2)(3-4)=12若插值若插值基点等距基点等距分布，牛顿型插值多项式还分布，牛顿型插值多项式还可以利用可以利用差分差分得到简化得到简化,。认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目差分差分设设基点等距基点等距，xi=x0+th,i=0,1,n.h称为称为步长步长。一阶差分：一阶差分：一阶向前差分、一阶前差一阶向前差分、一阶前差 一阶向后差分、一阶后差一阶向后差分、一阶后差 二阶差分：二阶差分：二阶前差二阶前差 二阶后差二阶后差 k阶前差和阶前

24、差和k阶后差阶后差 零阶差分规定为零阶差分规定为 简记为简记为认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目例例4.6 设设f(x)=x2+x,取步长取步长h=0.5,计算计算解解利用差分可以简化等距基点的牛顿型插值公式，称利用差分可以简化等距基点的牛顿型插值公式，称为为前差（或后差）插值公式前差（或后差）插值公式。用数学归纳法可以证明前差、后差、均差之间的下述关系：用数学归纳法可以证明前差、后差、均差之间的下述关系：f(0)=f(0.5)-f(0)=0.75,f(0.5)=f(1)-f(0.5)=1.252f(0)=(f

25、(0)=f(0.5)-f(0)=1.250.75=0.5令令 x0=0,则则 x1=0.5,x2=1认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目4.4 4.4 三次样条插值三次样条插值4.4.1 4.4.1 4.4.1 4.4.1 三次样条插值函数的概念三次样条插值函数的概念三次样条插值函数的概念三次样条插值函数的概念4.4.2 4.4.2 4.4.2 4.4.2 三次样条插值函数的求法三次样条插值函数的求法三次样条插值函数的求法三次样条插值函数的求法认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国

26、家对扶贫工作高度重视，已经展开了“精准扶贫”项目4.4.1 4.4.1 4.4.1 4.4.1 三次样条插值函数的概念三次样条插值函数的概念三次样条插值函数的概念三次样条插值函数的概念 样条插值的思想：逐段选取适当的低次多项式，按一定样条插值的思想：逐段选取适当的低次多项式，按一定的光滑性要求连接起来构成插值函数。的光滑性要求连接起来构成插值函数。定义定义 设给定区间设给定区间a,b上上n+1个点个点 a=x0 x1m)即即 如果有向量如果有向量c使得使得 达到最小，则称达到最小，则称c为超定方程组的最小二乘解。为超定方程组的最小二乘解。定理定理4.3超定方程组超定方程组Ac=y 存在最小二乘

27、解，且即存在最小二乘解，且即为方程组为方程组ATAc=ATy 的解。当的解。当A的列向量线性无关时的列向量线性无关时ATA非奇异，这时有唯一的解。非奇异，这时有唯一的解。认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目称方程组称方程组ATAc=ATy 为方程组为方程组Ac=y 的的正则方程组正则方程组、正规正规方程组方程组、法方程组法方程组 曲线拟合的最小二乘法可以看成求下述超定方程组曲线拟合的最小二乘法可以看成求下述超定方程组的最小二乘解的问题的最小二乘解的问题:简写为简写为 一般计算步骤为：一般计算步骤为：(1)计算计算

28、，其中，其中(2)计算计算ATA,ATy，形成法方程组，形成法方程组ATAc=ATy(3)求解法方程组，输出求解法方程组，输出 c1,c2,cm,构成构成认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目例例已知观测数据已知观测数据(1,5),(2,0),(4,5),(5,6)，试用最小二乘，试用最小二乘法求形如法求形如的经验公式。的经验公式。解解 作超定方程组作超定方程组即即法方程组为法方程组为求得求得a=1.537650114b=6.432976311所求经验公式为所求经验公式为认识到了贫困户贫困的根本原因，才能开始对症下

29、药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目4.5.2 4.5.2 4.5.2 4.5.2 代数多项式拟合代数多项式拟合代数多项式拟合代数多项式拟合1直线拟合直线拟合.作超定方程组作超定方程组 n记号记号 指指对对i从从1到到n取和取和认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目法方程组为法方程组为 2二次拟合、抛物拟合二次拟合、抛物拟合 作超定方程组作超定方程组 有有法方程组为法方程组为 认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了

30、“精准扶贫”项目3一般情形一般情形 超定方程组的系数矩阵为超定方程组的系数矩阵为 认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目例例已已知实验数据表，试用最小二乘法求经验公式拟合这组数据。知实验数据表，试用最小二乘法求经验公式拟合这组数据。解解作散点图，容易看出数据点接近一条作散点图，容易看出数据点接近一条直线，因此设经验公式为直线，因此设经验公式为x2468y2112840其法方程组为其法方程组为解得解得得经验公式为得经验公式为y=-12.5+6.55xn=4,认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除

31、。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目 例例 已知一组观测数据表，试用最已知一组观测数据表，试用最小二乘法求一个多项式拟合这组数据。小二乘法求一个多项式拟合这组数据。解解作散点图，可以看出这些点接近一条抛物线，因此设所求的作散点图，可以看出这些点接近一条抛物线，因此设所求的多项式为多项式为其法方程组为其法方程组为得得c0=4.7143,c1=-2.7857,c2=0.5000 x0 1 2 3 4 5y5 2 1 1 2 3 认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目x0 1 2 3 4 5y5 2

32、 1 1 2 3 认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目例例求一个经验函数求一个经验函数(a,b为常数为常数),使它与观测数据拟合。使它与观测数据拟合。x12345678y14.320.527.436.649.164.687.8117.6解解对经验公式两边取对数得对经验公式两边取对数得令令u=ln y ,A=ln a ,B=b则函数则函数u=ln y(x)的经验公式形为的经验公式形为u=ln=A+Bx这是线性拟合，法方程组形为这是线性拟合，法方程组形为法方程组为法方程组为求得求得A=2.430482,B=0.2926,认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目