计算方法-Newton插值课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2020/4/23,#,第,2,次,Newton,插值,计算方法,(Numerical Analysis),第2次 Newton 插值计算方法,1,牛顿,插值多项式的概念,差商及其,性质,牛顿插值多项式的系数与误差余项的导出,利用牛顿插值多项式近似求解的例子,牛顿插值多项式的概念,2,牛顿插值多项式的概念,牛顿插值多项式的概念,3,3,均差与牛顿插值多项式,拉格朗日插值多项式的优点与缺点,优点,：结构对称，使用方便。,缺点,：由于是用基函数构成的插值，要增加一个节点时，所有的基函数必须全部重新计算，不具备承袭性，还造成计算量的浪费。,3 均差与牛顿插值多项式,4,例如：,3,个节点，抛物插值的情况：,若要新增加一个节点，而进行,3,次插值的时候，则需要重新计算,例如：3个节点，抛物插值的情况：若要新增加一个节点，而进行3,5,试图改进,：我们要构造一种具有,承袭性,的插值多项式,P(x),来克服这个缺点，,即，每增加一个新节点时，只需在,P(x),原来的表达式中增加相应的一项即可，而不改变,P(x),的原来已经存在的表达式部分。,这就是,牛顿插值多项式的特点,。,试图改进：我们要构造一种具有承袭性的插值多项式P(x)来克服,6,可以证明,可将满足插值条件,p(x,0,)=y,0,p(x,1,)=y,1,，,p(x,n,)=y,n,的,n,次插值多项式,写成如下形式,:,其中,a,k,(k=0,1,2,n),为待定系数。,基函数：,(x-x,0,),(x-x,0,)(x-x,1,),，,(x-x,0,)(x-x,1,),(x-x,n-1,),可以证明,可将满足插值条件其中ak(k=0,1,2,7,定义：,给定,n+1,个插值节点,x,0,x,1,x,n,如下形式的插值多项式称为,Newton,插值多项式,：,（,3.12,）,其中,a,k,(k=0,1,2,n),为待定系数。,无,x,n,将出现在系数中,它满足以下的递推公式：,定义：给定n+1个插值节点x0 ,x1 ,xn,8,牛顿插值多项式,N,n,(x),是,插值多项式,p(x),的另一种表示形式,与,Lagrange,多项式相比,它克服了“增加一个节点时整个计算工作重新开始”的缺点,节省乘除法运算次数,在,Newton,插值多项式中用到的差商等概念，又与数值计算的其他方面有密切的关系.,要确定牛顿插值多项式,N,n,(x),系数，需要利用下一节差商的计算。,Home,牛顿插值多项式Nn(x)是插值多项式p(x)的另一种表示形式,9,差商及其性质,差商及其性质,10,3.1,差商及其性质,定义：函数,y=f(x),在区间,x,i,x,i+1,上的平均变化率,称为,f(x),关于,x,i,x,i+1,的,1,阶差商,。,定义,2,阶差商,定义,m,阶差商,3.1 差商及其性质定义：函数y=f(x)在区间xi,11,2,阶差商,f,x,i,x,j,x,k,是指,一般地,可定义,x,i,x,i+1,x,i+n,上的,n,阶差商：,2阶差商 fxi,xj,xk是指一般地,可定义xi,12,为了方便地计算差商，需要建立差商表。表中的箭头,指向表示更高阶差商所需要的低阶差商的参与。,x,i,f,x,i,f,x,i,x,i+1,f,x,i,x,i+1,x,i+2,f,x,i,x,i+1,x,i+2,，,x,i+3,x,0,f(x,0,),x,1,f(x,1,),f,x,0,x,1,x,2,f(x,2,),f,x,1,x,2,f,x,0,x,1,x,2,x,3,f(x,3,),f,x,2,x,3,f,x,1,x,2,x,3,f,x,0,x,1,x,2,x,3,f,x,1,x,2,-,f,x,0,x,1,x,2,x,0,f,x,1,x,2,x,3,-,f,x,0,x,1,x,2,x,3,x,0,为了方便地计算差商，需要建立差商表。表中的箭头xifxi,13,x,i,fx,i,fx,i,x,i+1,fx,i,x,i+1,x,i+2,fx,i,x,i+1,x,i+2,x,i+3,0,0,2,8,3,27,5,125,6,216,例,2.11,求,f(x,)=,x,3,在节点,x,=0,2,3,5,6上,的各阶差商值。,解:计算得如下表,xifxifxi,xi+1fxi,xi+1,xi+,14,性质1,函数,f(x),的,n,阶差商,f,x,0,x,1,x,n,可由,f(x,0,),f,(,x,1,),f(x,n,),的线性组合表示：,差商的性质,验证,同学自己验证,真漂亮,性质1 函数 f(x)的 n 阶差商 f x0,x,15,这种求解差商的方法的优点是直接使用公式，缺点是计算量较大。,应理解：右端分母中，,x,k,-x,k,项永远不出现。,或者表示成,以上公式可以利用如下的表达式直接验证,这种求解差商的方法的优点是直接使用公式，缺点是计算量较大。应,16,性质2,差商具有对称性,即在,k,阶差商,中任意交换两个节点 和 的次序,其值不变。,即：,学生自己验证以上两个公式,性质2 差商具有对称性,即在k阶差商 即：学生自己验证以上,17,性质3,若,f,x,x,0,x,1,x,k,是,x,的,m,次多项式,则,f,x,x,0,x,1,x,k,x,k+1,是,x,的,m-1,次多项式。,注意,：右端分子为,m,次多项式,且由差商的对称性可知，当,x=x,k+1,时,分子为0,故分子含有因子,x,k+1,x，,与分母相消后，右端为,m-1,次多项式。,证：由差商定义,常数,性质3 若fx,x0,x1,xk 是 x,18,性质4,若,f(x),是,n,次多项式,则,f,x,x,0,x,1,x,n,恒为0。,证：,f(x),是,n,次多项式，则,f,x,x,0,是,n-1,次多项式,f,x,x,0,x,1,是,n-2,次多项式。,f,x,x,0,x,1,x,n,0,依次递推,，,f,x,x,0,x,1,x,n-1,是,n-n,次（零次）多项式，即常数,c.,所以,性质4 若 f(x)是n次多项式,则fx,x0,19,性质5,若,f(x),存在,k,阶导数,，则,f(x),的,k,阶差商 与其,k,阶导数之间有下列关系：,证明,：这个性质可直接用罗尔,(Rolle),定理证明。,Home,性质5 若f(x)存在k阶导数，则f(x)的k阶差商,20,牛顿插值多项式的系数,与误差余项的导出,牛顿插值多项式的系数,21,牛顿插值多项式的系数与误差余项的导出,的系数,a,k,(k=0,n),可根据以下插值条件推出。,牛顿插值多项式的系数与误差余项的导出 的系数ak(k=0,22,一般，用数学归纳法可证明,从上述各个公式中可以解出：,将,a,1,=fx,0 ,x,1,代入下一个等式，得,一般，用数学归纳法可证明 从上述各个公式中可以解出：将a1,23,n,次牛顿(,Newton),插值公式的表达式：,其余项,为牛顿插值多项式的误差。,这里没有假设,f(x),可导,n次牛顿(Newton)插值公式的表达式：其余项 为,24,牛顿插值多项式余项公式的推导：,设,x,为区间,a,b,上的一点，可得：,从前往后，将后式逐渐带入到前式,即得：,根据,1,阶差,商的定义,根据,2,阶差,商的定义,牛顿插值多项式余项公式的推导：设x为区间a,b上的一点,25,推导完毕,(,下一页,PPT,有,3,个节点情况的详细推导,),。,推导完毕(下一页PPT有3个节点情况的详细推导)。,26,设,x,为区间,a,b,上的一点，可得：,将,(2),式代入,(1),式，得：,牛顿插值多项式余项公式的仔细推导（以仅有,3,个插值节点 的,2,次插值为例）：,(1),(2),(3),(4),将,(3),式代入,(4),式，得：,整理，得,整理，得：,N,2,(x),R,2,(x),设x为区间a,b上的一点，可得：将(2)式代入(1)式,27,解释：,由插值多项式的存在唯一性定理知，满足同一组插值条件的拉格朗日插值多项式,P(x),与牛顿插值多项式,N,n,(x),实际上是同一个多项式,的形式以后，所得的表达式是相同的。,即将,P(x),和,N,n,(x),所得的多项式表达式，化为,解释：的形式以后，所得的表达式是相同的。即将P(x)和Nn(,28,若,f,(n+1),(x),不存在,，,则只有使用,(*),式来表达误差。,Newton,插值多项式的误差,(,不要求,f(x),光滑,),(*),(*),若,f,(n+1),(x),存在，,则,Lagrange,插值多项式的误差,仅在,f,(n+1),(x),存在情况下才成立。,于是,若f(n+1)(x)不存在，则只有使用(*)式来表达误差。N,29,评论：,牛顿插值公式计算方便，增加一个插值点，只要多计算一项，而,N,n,(x),的各项系数恰好是各阶差商值，很有规律。,Home,总结：,n,次牛顿(,Newton),插值公式的表达式为,余项,若,f,(n+1),(x),存在,评论：牛顿插值公式计算方便，增加一个插值点，只要多计算一项，,30,利用牛顿插值多项式近似求解的例子,利用牛顿插值多项式近似求解的例子,31,x,i,fx,i,fx,i,x,i+1,fx,i,x,i+1,x,i+2,fx,i,x,i+1,x,i+2,x,i+3,x,0,f(x,0,),x,1,f(x,1,),fx,0,x,1,x,2,f(x,2,),fx,1,x,2,fx,0,x,1,x,2,x,3,f(x,3,),fx,2,x,3,fx,1,x,2,x,3,fx,0,x,1,x,2,x,3,xifxifxi,xi+1fxi,xi+1,32,x,i,f,x,i,f,x,i,x,i+1,f,x,i,x,i+1,x,i+2,1,1,4,2,(2-1)/(4-1)=1/3,9,3,(3-2)/(9-4)=1/5,(1/5-1/3)/(9-1)=-1/60,N,2,(x)=1+1/3(x-1)-1/60(x-1)(x-4),=-1/60 x,2,+5/12x+3/5,N,2,(7)=2.7,例,2.12,已知,x=1,4,9,的平方根值，求,解,1,：考虑,f(x)=x,，利用差商表求差商,xifxifxi,xi+1fxi,xi+1,33,解,2,：利用公式求差商,x,1,4,9,f(x),1,2,3,用这种方法解得得系数与方法,1,的相同。,解2：利用公式求差商x149f(x)123用这种方法解得得系,34,解,3,：利用拉格朗日方法求插值对多项式,求,2,次插值对多项式,x,1,4,9,f(x),1,2,3,=-1/60 x,2,+5/12x+3/5,解3：利用拉格朗日方法求插值对多项式求2次插值对多项式x14,35,4.4.1 差商及其性质,例,2.13,已知,x,=0,2,3,5,对应的函数值为,y,=1,3,2,5,作三次,Newton,插值多项式。,x,i,f(x,i,),1,阶差商,2,阶差商,3,阶差商,0,1,2,3,1,3,2,-2/3,5,5,3/10,4.4.1 差商及其性质 例2.13 已知 x=0,36,例,2.14,求 的值，并估计其误差,解：令,，取,x,0,=4,x,1,=9,x,2,=6.25,x,f(x),f,x,i,x,i+1,fx,i,x,i+1,x,i+2,4,2,9,3,6.25,2.5,差商表,例2.14 求 的值，并估计其误差解：令，取,37,在区间 4,9 上，,由,计算器计算结果：,N,2,(7)=2.7,，差一些,例,2.12,中，计算结果为：,代入,x=7,例,2.14,中，计算结果为：,N,2,(7)=2.64848,，好一些,在区间 4,9 上，由计算器计算结果：N2(7)=2,38,4.4.1 差商及其性质,例,2.15,已知,f(x)=x,7,+x,4,+3x+1,求,f,2,0,2,1,2,7,及,f,2,0,2,1,2,7,2,8,分析：本题,f(x),是一个多项式