数值插值方法 (2).ppt

数值插值方法现在学习的是第1页，共63页第五章第五章 插值方法插值方法插值的基本概念插值的基本概念Lagrange插值插值分段低次插值分段低次插值Hermite插值插值三次样条插值三次样条插值现在学习的是第2页，共63页5.1 代数插值问题代数插值问题例例.某地区某年夏季时节间隔某地区某年夏季时节间隔 30 天的日出日落时天的日出日落时间为间为 5月月1日日 5月月31日日 6月月30日日日出日出 5：51 5：17 5：10日落日落 19：04 19：38 19：50插值插值：研究用简单函数为各种离散数据建立连续数学：研究用简单函数为各种离散数据建立连续数学模型的方法。模型的方法。现在学习的是第3页，共63页日照时间的变化设为日照时间的变化设为 y(x)=a0+a1x+a2x2,求出求出a0,a1,a2，即可得到，即可得到5、6月份的日照时月份的日照时间的变化规律。间的变化规律。根据三组数据根据三组数据:(1,15.2167),(31,14.35),(61,14.6667)导出关于导出关于a0,a1,a2的线性方程组的线性方程组现在学习的是第4页，共63页定义定义 已知函数已知函数已知函数已知函数y=f(x)在在在在a,b有定义，且已知它在有定义，且已知它在有定义，且已知它在有定义，且已知它在n+1个个个个互异节点互异节点互异节点互异节点a x0 x1xnb上的函数值上的函数值上的函数值上的函数值 y0=f(x0)，y1=f(x1),yn=f(xn)，若存在一个次数不超过若存在一个次数不超过若存在一个次数不超过若存在一个次数不超过n n次的多项式次的多项式次的多项式次的多项式 Pn(x)=a0+a1x+a2x2+anxn满足条件满足条件满足条件满足条件 Pn(xk)=yk (k=0,1,n)则称则称则称则称Pn(x)为为为为f(x)f(x)的的的的n n次插值多项式。次插值多项式。次插值多项式。次插值多项式。点点点点x x0 0,x x1 1,x xn n称称称称插插插插值值值值节节节节点点点点，f(x)f(x)为为为为被被被被插插插插值值值值函函函函数数数数。a a,b b 称称称称插插插插值值值值区区区区间间间间，点点点点x x称称称称插插插插值值值值点点点点。插插插插值值值值点点点点在在在在插插插插值值值值区区区区间间间间内内内内的的的的叫叫叫叫内内内内插插插插，否否否否则则则则叫叫叫叫外插外插外插外插。现在学习的是第5页，共63页设设设设 P Pn n (x x)=)=a a0 0+a a1 1x x+a a2 2x x2 2+a an nx xn n是是是是y y=f f(x x)在在在在 a a,b b 上的上的上的上的n n+1+1个互异节点个互异节点个互异节点个互异节点x x0 0,x x1 1,x xn n的插值多项式，的插值多项式，的插值多项式，的插值多项式，则求则求则求则求P Pn n(x x)问题归结为求系数问题归结为求系数问题归结为求系数问题归结为求系数a a0 0,a a1 1,a an n。定理定理 n次插值问题的解是存在而且唯一的。次插值问题的解是存在而且唯一的。证明：证明：由插值条件：由插值条件：由插值条件：由插值条件：P Pn n (x xk k)=)=y yk k (k k=0,1,=0,1,n n)得关于得关于得关于得关于a a0 0,a a1 1,a an n的的的的n n+1+1阶线性方程组阶线性方程组阶线性方程组阶线性方程组现在学习的是第6页，共63页故故Pn(x)存在且唯一。存在且唯一。因因故上式不为故上式不为0。据据Cramer法则，方程组解存在且唯一。法则，方程组解存在且唯一。其系数行列式是其系数行列式是Vandermonde行列式行列式现在学习的是第7页，共63页给定插值节点给定插值节点 x0,x1，y0=f(x0)，y1=f(x1).求线性插值多项式求线性插值多项式L1(x)=a0+a1x，使满足，使满足:L1(x0)=y0,L1(x1)=y1.5.2 Lagrange插值插值一、线性插值与抛物插值一、线性插值与抛物插值1.线性插值：线性插值：n=1情形情形y=L1(x)的几何意义就是过点的几何意义就是过点(x0,y0)，(x1,y1)的的直线。直线。L1(x)的表达式：的表达式：点斜式点斜式:两点式两点式:现在学习的是第8页，共63页由两点式可以看出，由两点式可以看出，L1(x)是由两个线性函数是由两个线性函数的线性组合得到，其系数分别为的线性组合得到，其系数分别为y0，y1。即。即显然，显然，l0(x)及及l1(x)也是线性插值多项式，在节点也是线性插值多项式，在节点x0,x1上满足条件：上满足条件：l0(x0)=1,l0(x1)=0.l1(x0)=0,l1(x1)=1.称称l0(x)及及l1(x)为线性插值基函数。为线性插值基函数。(j,k=0,1)即即现在学习的是第9页，共63页l0(x0)=1,l0(x1)=0,l0(x2)=0.l1(x0)=0,l1(x1)=1,l1(x2)=0.l2(x0)=0,l2(x1)=0,l2(x2)=1.2.抛物插值：抛物插值：n=2情形情形假定插值节点为假定插值节点为x0,x1,x2，求二次插值多项式求二次插值多项式 L2(x)，使使 L2(xj)=yj (j=0,1,2)y=L2(x)的的几何意义几何意义就是过就是过(x0,y0)，(x1,y1)，(x2,y2)三点的抛物线。三点的抛物线。采用采用基函数方法基函数方法，设，设L2(x)=l0(x)y0+l1(x)y1+l2(x)y2此时基函数此时基函数l0(x),l1(x),l2(x)是二次函数，且在节点上满是二次函数，且在节点上满足：足：现在学习的是第10页，共63页满足上式的插值基函数很容易求出。如求满足上式的插值基函数很容易求出。如求l0(x),因因x1,x2 为其零点，故可表为为其零点，故可表为故故即即(j,k=0,1,2)其中其中A为待定系数，由为待定系数，由l0(x0)=1,得得现在学习的是第11页，共63页显然显然 L(x)=l0(x)y0+l1(x)y1+l2(x)y2 满足条件满足条件L2(xj)=yj (j=0,1,2)同理同理将将l0(x),l1(x),l2(x)代入得代入得现在学习的是第12页，共63页取取x0=4,y0=2，x1=9,y1=3，x2=16,y2=4.取取x0=4,x1=9,x2=16例例已知已知求求解解（1）线性插值：线性插值：取取x0=4,x1=9（2）抛物插值：抛物插值：现在学习的是第13页，共63页设有设有n+1个互异节点个互异节点x0 x1xn，且，且yi=f(xi)(i=0,1,2,n)构造构造Ln(x)，使，使 Ln(xj)=yj (j=0,1,2,n)二、二、Lagrange插值多项式插值多项式定义定义若若n次多项式次多项式lj(x)(j=0,1,n)在在n+1个节点个节点x0 x1xn上满足条件上满足条件(j,k=0,1,n)则称这则称这n+1个个n次多项式次多项式l0(x),l1(x),ln(x)为节点为节点x0,x1,xn上的上的n次次插值基函数插值基函数。现在学习的是第14页，共63页由由n=1,2时的讨论可得时的讨论可得(k=0,1,2,n)或记为或记为(k=0,1,2,n)故满足插值条件的多项式为故满足插值条件的多项式为称称Lagrange插值多项式插值多项式。现在学习的是第15页，共63页定理定理 设设 f(x)在在a,b上具有上具有n阶连续导数阶连续导数,且且f(n+1)(x)存在存在,节点节点a x0 x1时时Ln在在-5,5上不收上不收敛。敛。Runge证明了，存在一个常数证明了，存在一个常数c3.63，使得当，使得当|x|c时，时，lim(Ln(x)=f(x)(x)；而当；而当|x|c时，时，Ln(x)发散。发散。下图给出当下图给出当n=10时，时，y=L10(x)及及f(x)=1/(1+x2)在在-5,5上的图形。上的图形。现在学习的是第27页，共63页取取xk=-5+k 计算计算:f(xk)(k=0,1,10)构造构造L10(x).取取:tk=-5+0.05k (k=0,1,200),计算计算:L10(tk)L10(t)f(t)f(x)现在学习的是第28页，共63页x=-5:5;y=1./(1+x.2);t=-5:0.05:5;y1=1./(1+t.2);n=length(t);for i=1:n z=t(i);s=0;for k=1:11 Lk=1;u=x(k);for j=1:11 if j=k,Lk=Lk*(z-x(j)/(u-x(j);end end s=s+Lk*y(k);end y2(i)=s;endplot(x,y,ko,t,y1,t,y2,r)现在学习的是第29页，共63页一、分段线性一、分段线性Lagrange插值插值构造构造Lagrange线性插值线性插值1.分段线性插值的构造分段线性插值的构造设插值节点为设插值节点为xi，函数值为，函数值为yi，i=0,1,2,nhi=xi+1-xi，i=0,1,2,n-1，任取两个相邻的节点任取两个相邻的节点xk，xk+1，形成一个插值区间，形成一个插值区间xk，xk+1,k=0,1,2,n-1现在学习的是第30页，共63页显然显然我们称由上式构成的插值多项式我们称由上式构成的插值多项式L1(x)为为分段线性分段线性Lagrange插值多项式插值多项式。i=0,1,2,n现在学习的是第31页，共63页内插外插外插现在学习的是第32页，共63页故也称折线插值故也称折线插值故也称折线插值故也称折线插值,如右图：如右图：如右图：如右图：但曲线的光滑性较差，且但曲线的光滑性较差，且但曲线的光滑性较差，且但曲线的光滑性较差，且在节点处有尖点。在节点处有尖点。如果增加节点的数量，减小如果增加节点的数量，减小如果增加节点的数量，减小如果增加节点的数量，减小步长步长步长步长,会改善插值效果。会改善插值效果。会改善插值效果。会改善插值效果。因此因此因此因此则则则则现在学习的是第33页，共63页由前述余项定理可知，由前述余项定理可知，n次次Lagrange插值多项式的插值多项式的余项为：余项为：2.分段线性插值的误差估计分段线性插值的误差估计则分段线性插值则分段线性插值L1(x)的余项为的余项为现在学习的是第34页，共63页二、分段二次二、分段二次Lagrange插值插值1.分段二次插值的构造分段二次插值的构造设插值节点为设插值节点为xi，函数值为，函数值为yi，i=0,1,2,nhi=xi+1-xi，i=0,1,2,n-1，任取三个相邻的节点任取三个相邻的节点xk-1，xk，xk+1，以，以 xk-1，xk+1为为插值区间构造二次插值区间构造二次Langrange插值多项式：插值多项式：现在学习的是第35页，共63页2.分段二次插值的误差估计分段二次插值的误差估计由于那么分段二次插值L2(x)的余项为：现在学习的是第36页，共63页例:解:(1).分段线性Lagrange插值的公式为现在学习的是第37页，共63页同理现在学习的是第38页，共63页(2).分段二次Lagrange插值的公式为现在学习的是第39页，共63页现在学习的是第40页，共63页5.4 埃尔米特插值（埃尔米特插值（Hermite）Newton插值和插值和Lagrange插值虽然构造比较简单，插值虽然构造比较简单，但都存在插值曲线在节点处有尖点，不光滑，插但都存在插值曲线在节点处有尖点，不光滑，插值多项式在节点处不可导等缺点。值多项式在节点处不可导等缺点。已知节点处函数值及对应节点导数值，求使其函数值已知节点处函数值及对应节点导数值，求使其函数值及导数值均相等的插值多项式。及导数值均相等的插值多项式。埃尔米特插值的基本思想为：埃尔米特插值的基本思想为：设设a x0 x1xnb上，上，(j=0,1,2,n)求求H(x)，使使(j=0,1,2,n)现在学习的是第41页，共63页共有共有2n+2个条件，可唯一确定一次数个条件，可唯一确定一次数 2n+1的多项式的多项式H2n+1(x)H(x)。形式：形式：一般来说，一般来说，Hermite插值多项式的次数如果太高会插值多项式的次数如果太高会影响收敛性和稳定性，因此影响收敛性和稳定性，因此2n+1不宜太大，仍用不宜太大，仍用分段插值。分段插值。故仅考虑故仅考虑n=1的情况，即三次的情况，即三次Hermite插值。插值。现在学习的是第42页，共63页一、三次一、三次Hermite插值公式插值公式考虑只有两个节点的插值问题：考虑只有两个节点的插值问题：设设f(x)在节点在节点x0，x1处的函数值为处的函数值为y0，y1；在节点；在节点x0，x1处的一阶导数值为处的一阶导数值为y0，y1。两个节点最高可以用两个节点最高可以用3次次Hermite多项式多项式H3(x)作为作为插值函数。插值函数。H3(x)应满足条件：应满足条件：采用基函数方法构造。采用基函数方法构造。现在学习的是第43页，共63页H3(x)应用四个插值基函数表示。应用四个插值基函数表示。设设H3(x)的插值基函数为的插值基函数为0(x)，1(x)，0 0(x x)，1(x)，则则其中其中现在学习的是第44页，共63页可知可知x1是是0(x)的二重零点，即可假设的二重零点，即可假设 由由可得可得现在学习的是第45页，共63页Lagrange插值基函数同理可得同理可得现在学习的是第46页，共63页将以上结果代入将以上结果代入得两个节点的三次得两个节点的三次Hermite插值公式：插值公式：现在学习的是第47页，共63页二、三次二、三次Hermite插值的余项插值的余项定理：定理：设设f(x)在区间在区间a,b上有定义，上有定义，f(x)在在(a,b)内有内有4阶阶导数，导数，H3(x)是满足插值条件是满足插值条件(j=0,1)的三次的三次Hermite插值函数，则对任意的插值函数，则对任意的xa,b，H(x)的插值余项为的插值余项为证明：证明：由由(i=0,1)现在学习的是第48页，共63页可知，可知，x0，x1均为均为R3(x)的二重零点，因此可设的二重零点，因此可设其中其中K(x)待定待定构造辅助函数构造辅助函数i=0,1因此因此(t)至少有至少有5个零点。个零点。连续连续4次使用次使用Rolle定理可得，至少存在一点定理可得，至少存在一点x0,x1，使得使得现在学习的是第49页，共63页即即所以所以,两点三次两点三次Hermite插值的余项为插值的余项为现在学习的是第50页，共63页例1.解:现在学习的是第51页，共63页作为多项式插值，三次已是较高的次数，次数再高就有作为多项式插值，三次已是较高的次数，次数再高就有可能发生可能发生Runge现象，因此，对有现象，因此，对有n+1个节点的插值问题，个节点的插值问题，我们可以使用分段两点三次我们可以使用分段两点三次Hermite插值。插值。现在学习的是第52页，共63页设节点设节点x0 x1xn，分段插值函数，分段插值函数Hn(x)在两个在两个相邻节点构成的小区间相邻节点构成的小区间xj,xj+1(j=0,1,n-1)上满足条件：上满足条件：三、分段三次三、分段三次Hermite插值插值用三次用三次Hermite插值，当插值，当x xj,xj+1 时，有时，有现在学习的是第53页，共63页其中其中现在学习的是第54页，共63页3.5 三次样条插值三次样条插值样条：样条：是是 指飞机或轮船等的制造过程中为描绘出光滑指飞机或轮船等的制造过程中为描绘出光滑的外形曲线的外形曲线(放样放样)所用的工具。所用的工具。样条本质上是一段一段的三次多项式拼合而成的曲样条本质上是一段一段的三次多项式拼合而成的曲线，在拼接处，不仅函数是连续的，且一阶和二阶线，在拼接处，不仅函数是连续的，且一阶和二阶导数也是连续的。导数也是连续的。1946年，年，Schoenberg将样条引入数学，即所谓的将样条引入数学，即所谓的样条函数。样条函数。因分段线性插值导数不连续，埃尔米特插值导数因分段线性插值导数不连续，埃尔米特插值导数连续但需要已知，故引入样条插值概念。连续但需要已知，故引入样条插值概念。现在学习的是第55页，共63页一、三次样条插值函数的定义一、三次样条插值函数的定义定义：定义：给定区间给定区间a,b上的一个划分：上的一个划分：a=x0 x1xn=b，已知函数，已知函数f(x)在点在点xj上的函数上的函数值为值为 f(xj)=yj,(j=0,1,2,n)如果存在分如果存在分段函数段函数满足下述条件：满足下述条件：现在学习的是第56页，共63页(1)S(x)在每一个子区间在每一个子区间xj-1,xj (j=0,1,2,n)上是上是一个三次多项式；一个三次多项式；(2)S(x)在每一个内接点在每一个内接点xj(j=0,1,2,n)上具有直上具有直到二阶的连续导数；到二阶的连续导数；则称则称S(x)为节点为节点x0,x1,xn 上的上的三次样条函数三次样条函数。若若S(x)在节点在节点x0,x1,xn 上还满足插值条件：上还满足插值条件：(3)S(xj)=yj (j=0,1,2,n)则称则称S(x)为为三次样条插值函数三次样条插值函数。（即全部通过样点的。（即全部通过样点的二阶连续可微的分段三次多项式函数）二阶连续可微的分段三次多项式函数）现在学习的是第57页，共63页三次样条插值多项式的确定：三次样条插值多项式的确定：由由(1)知，知，S(x)在每一个小区间在每一个小区间xj-1,xj 上是一三上是一三次多项式，若记为次多项式，若记为Sj(x),则可设则可设要确定函数要确定函数S(x)的表达式，须确定的表达式，须确定4n个未知系数个未知系数aj，bj，cj，dj(j=1,2,n)。由由(2)知，知，S(x)，S(x)，S(x)在内节点在内节点x1,x2,xn-1上连上连续，则续，则j=1,2,n-1现在学习的是第58页，共63页可得可得3n-2个方程，又由条件个方程，又由条件(3)j=1,2,n得得n+1个方程，共可得个方程，共可得4n-2个方程。个方程。要确定要确定4n个未知数，还差两个方程。个未知数，还差两个方程。通常在端点通常在端点x0=a,xn=b处各附加一个条件，称处各附加一个条件，称边界边界条件条件，常见有三种：，常见有三种：(1)自然边界条件：自然边界条件：(2)固定边界条件：固定边界条件：自然样条（最光滑）(3)周期边界条件：周期边界条件：共共4n个方程，可唯一地确定个方程，可唯一地确定4n个未知数。个未知数。现在学习的是第59页，共63页例例 已知已知f(x):f(-1)=1,f(0)=0,f(1)=1，求，求f(x)在在-1,1上的三次自然样条插值函数。上的三次自然样条插值函数。解解设设由插值条件和函数连续条件得：由插值条件和函数连续条件得：现在学习的是第60页，共63页由一阶及二阶导数连续得：由一阶及二阶导数连续得：由自然边界条件得：由自然边界条件得：联立上面联立上面8个方程，求解得个方程，求解得故故现在学习的是第61页，共63页P137-138习题五：习题五：1 ，2，4，5。补充题见下页：补充题见下页：本章作业现在学习的是第62页，共63页1.1.当当当当x=1,-1,2 x=1,-1,2 时，时，时，时，f(x)=0,-3,4f(x)=0,-3,4，求，求，求，求f(x)f(x)的二次插值多项式。的二次插值多项式。的二次插值多项式。的二次插值多项式。2.2.已知函数已知函数已知函数已知函数 y=f(x)y=f(x)满足如下条件：满足如下条件：满足如下条件：满足如下条件：i i0 01 12 2 x xi i -1-10 01 1 y yi i -1-10 01 1 y yi i 0 0求一个次数不超过求一个次数不超过求一个次数不超过求一个次数不超过3 3次的次的次的次的HermiteHermite插值多项式插值多项式插值多项式插值多项式HH3 3(x)(x)，使得，使得，使得，使得HH3 3(x(xi i)=y)=yi i，(i=0,1,2),(i=0,1,2),HH3 3(x(x1 1)=y)=y1 1。3.3.考虑下述的插值问题：求二次多项式考虑下述的插值问题：求二次多项式考虑下述的插值问题：求二次多项式考虑下述的插值问题：求二次多项式P(x)P(x)，满足：，满足：，满足：，满足：P(xP(x0 0)=)=y y0 0，P(xP(x1 1)=y)=y1 1，P(xP(x2 2)=y)=y2 2，其中其中其中其中x x0 0 x x2 2，y y0 0、y y1 1、y y2 2 是已知数据。并给出使这一问题的是已知数据。并给出使这一问题的是已知数据。并给出使这一问题的是已知数据。并给出使这一问题的解存在且唯一的条件。解存在且唯一的条件。解存在且唯一的条件。解存在且唯一的条件。现在学习的是第63页，共63页