计算方法-Newton插值课件

第2次Newton插值计算方法(NumericalAnalysis)第2次Newton插值计算方法1牛顿插值多项式的概念差商及其性质牛顿插值多项式的系数与误差余项的导出利用牛顿插值多项式近似求解的例子牛顿插值多项式的概念2牛顿插值多项式的概念牛顿插值多项式的概念3§3均差与牛顿插值多项式拉格朗日插值多项式的优点与缺点优点：结构对称，使用方便。缺点：由于是用基函数构成的插值，要增加一个节点时，所有的基函数必须全部重新计算，不具备承袭性，还造成计算量的浪费。§3均差与牛顿插值多项式4例如：3个节点，抛物插值的情况：若要新增加一个节点，而进行3次插值的时候，则需要重新计算例如：3个节点，抛物插值的情况：若要新增加一个节点，而进行35试图改进：我们要构造一种具有承袭性的插值多项式P(x)来克服这个缺点，即，每增加一个新节点时，只需在P(x)原来的表达式中增加相应的一项即可，而不改变P(x)的原来已经存在的表达式部分。这就是牛顿插值多项式的特点。试图改进：我们要构造一种具有承袭性的插值多项式P(x)来克服6可以证明,可将满足插值条件p(x0)=y0,p(x1)=y1，…p(xn)=yn的n次插值多项式,写成如下形式:其中ak(k=0,1,2,…,n)为待定系数。……基函数：(x-x0),(x-x0)(x-x1),…，(x-x0)(x-x1)…(x-xn-1)可以证明,可将满足插值条件其中ak(k=0,1,2,…,7定义：给定n+1个插值节点x0,x1,…,xn,如下形式的插值多项式称为Newton插值多项式：（3.12）其中ak(k=0,1,2,…,n)为待定系数。无xn,将出现在系数中……它满足以下的递推公式：…定义：给定n+1个插值节点x0,x1,…,xn,8牛顿插值多项式Nn(x)是插值多项式p(x)的另一种表示形式,与Lagrange多项式相比它克服了“增加一个节点时整个计算工作重新开始”的缺点,节省乘除法运算次数,在Newton插值多项式中用到的差商等概念，又与数值计算的其他方面有密切的关系.要确定牛顿插值多项式Nn(x)系数，需要利用下一节差商的计算。Home牛顿插值多项式Nn(x)是插值多项式p(x)的另一种表示形式9差商及其性质差商及其性质103.1差商及其性质定义：函数y=f(x)在区间[xi

,xi+1]上的平均变化率称为f(x)关于xi

,xi+1的1阶差商。定义2阶差商定义m阶差商………3.1差商及其性质定义：函数y=f(x)在区间[xi,112阶差商f[xi,xj,xk]是指一般地,可定义[xi,xi+1,…,xi+n]上的n阶差商：2阶差商f[xi,xj,xk]是指一般地,可定义[xi12为了方便地计算差商，需要建立差商表。表中的箭头指向表示更高阶差商所需要的低阶差商的参与。xif[xi]f[xi,xi+1]f[xi,xi+1,xi+2]f[xi,xi+1,xi+2，xi+3]x0f(x0)x1f(x1)f[x0,x1]x2f(x2)f[x1,x2]f[x0,x1,x2]x3f(x3)f[x2,x3

]f[x1,x2,x3]f[x0,x1,x2

,x3]………f[x1,x2]-f[x0,x1]x2–x0f[x1,x2,x3]-f[x0,x1,x2]x3–x0为了方便地计算差商，需要建立差商表。表中的箭头xif[xi]13xif[xi]f[xi,xi+1]f[xi,xi+1,xi+2]f[xi,xi+1,xi+2

,xi+3]002832751256216例2.11求f(x)=x3在节点x=0,2,3,5,6上的各阶差商值。解:计算得如下表xif[xi]f[xi,xi+1]f[xi,xi+1,xi+14性质1函数f(x)的n阶差商f[x0,x1,…,xn]可由f(x0),f(x1),…,f(xn)的线性组合表示：差商的性质验证同学自己验证真漂亮性质1函数f(x)的n阶差商f[x0,x15这种求解差商的方法的优点是直接使用公式，缺点是计算量较大。应理解：右端分母中，xk-xk

项永远不出现。或者表示成以上公式可以利用如下的表达式直接验证这种求解差商的方法的优点是直接使用公式，缺点是计算量较大。应16性质2差商具有对称性,即在k阶差商中任意交换两个节点和的次序,其值不变。即：学生自己验证以上两个公式……性质2差商具有对称性,即在k阶差商即：学生自己验证以上17性质3

若f[x,x0,x1,…,xk]是x的m次多项式,则f[x,x0,x1,…,xk,xk+1]是x的m-1次多项式。注意：右端分子为m次多项式,且由差商的对称性可知，当x=xk+1时,分子为0,故分子含有因子xk+1–x，与分母相消后，右端为m-1次多项式。证：由差商定义

………常数性质3若f[x,x0,x1,…,xk]是x18性质4

若f(x)是n次多项式,则f[x,x0,x1,…,xn]恒为0。证：f(x)是n次多项式，则f[x,x0]是n-1次多项式,f[x,x0,x1]是n-2次多项式。f[x,x0,x1,…,xn]0依次递推…，f[x,x0,x1,…,xn-1]是n-n次（零次）多项式，即常数c.所以

性质4若f(x)是n次多项式,则f[x,x0,19性质5若f(x)存在k阶导数，则f(x)的k阶差商与其k阶导数之间有下列关系：证明：这个性质可直接用罗尔(Rolle)定理证明。Home…性质5若f(x)存在k阶导数，则f(x)的k阶差商20牛顿插值多项式的系数与误差余项的导出牛顿插值多项式的系数21牛顿插值多项式的系数与误差余项的导出的系数ak

(k=0,…,n)可根据以下插值条件推出。…

……………牛顿插值多项式的系数与误差余项的导出的系数ak(k=0,22一般，用数学归纳法可证明从上述各个公式中可以解出：将a1=f[x0,x1]代入下一个等式，得……一般，用数学归纳法可证明从上述各个公式中可以解出：将a123n次牛顿(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)式，得：整理，得整理，得：N2(x)R2(x)设x为区间[a,b]上的一点，可得：将(2)式代入(1)式27解释：由插值多项式的存在唯一性定理知，满足同一组插值条件的拉格朗日插值多项式P(x)与牛顿插值多项式Nn(x)实际上是同一个多项式的形式以后，所得的表达式是相同的。即将P(x)和Nn(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)不存在，则只有使用(*)式来表达误差。N29评论：牛顿插值公式计算方便，增加一个插值点，只要多计算一项，而Nn(x)的各项系数恰好是各阶差商值，很有规律。Home总结：n次牛顿(Newton)插值公式的表达式为余项………若f(n+1)(x)存在评论：牛顿插值公式计算方便，增加一个插值点，只要多计算一项，30利用牛顿插值多项式近似求解的例子利用牛顿插值多项式近似求解的例子31xif[xi]f[xi,xi+1]f[xi,xi+1,xi+2]f[xi,xi+1,xi+2,

xi+3]x0f(x0)x1f(x1)f[x0,x1]x2f(x2)f[x1,x2]f[x0,x1,x2]x3f(x3)f[x2,x3]f[x1,x2,x3]f[x0,x1,x2,x3]……………xif[xi]f[xi,xi+1]f[xi,xi+1,32xif[xi]f[xi,xi+1]f[xi,xi+1,xi+2]1142(2-1)/(4-1)=1/393(3-2)/(9-4)=1/5(1/5-1/3)/(9-1)=-1/60N2(x)=1+1/3(x-1)-1/60(x-1)(x-4)=-1/60x2+5/12x+3/5N2(7)=2.7例2.12已知x=1,4,9的平方根值，求解1：考虑f(x)=√x，利用差商表求差商xif[xi]f[xi,xi+1]f[xi,xi+1,33解2：利用公式求差商x149f(x)123用这种方法解得得系数与方法1的相同。解2：利用公式求差商x149f(x)123用这种方法解得得系34解3：利用拉格朗日方法求插值对多项式求2次插值对多项式x149f(x)123=-1/60x2+5/12x+3/5解3：利用拉格朗日方法求插值对多项式求2次插值对多项式x14354.4.1差商及其性质例2.13已知x=0,2,3,5对应的函数值为y=1,3,2,5,作三次Newton插值多项式。xif(xi)1阶差商2阶差商3阶差商0123132-2/3553/104.4.1差商及其性质例2.13已知x=0,36例2.14求的值，并估计其误差解：令，取x0=4,x1=9,x2=6.25xf(x)f[xi,xi+1]f[xi,xi+1,xi+2]42936.252.5,差商表例2.14求的值，并估计其误差解：令，取37在区间[4,9]上，由计算器计算结果：N2(7)=2.7，差一些例2.12中，计算结果为：代入x=7例2.14中，计算结果为：N2(7)=2.64848，好一些在区间[4,9]上，由计算器计算结果：N2(7)=2384.4.1差商及其性质例2.15已知f(x)=x7+x4+3x+1

求f[20,21,…27

]及f[20,21,…27,28

]分析：本题f(x)是一个多项式,故应利用差商的性质解:由差商与导数之间的关系4.4.1差商及其性质例2.15已知f(x)39例2.16给出f(x)的函数表如下，求4次Newton插

值多项式，并且由此计算f(0.596)的值,并

且估计误差R4(0.596).xif(xi)0.400.410750.550.578150.650.696750.800.888110.901.026521.051.25382例2.16给出f(x)的函数表如下，求4次Newton插x40xif(xi)1阶差商2阶差商3阶差商4阶差商0.400.410750.550.578151.116000.650.696751.186000.280000.800.888111.275730.358920.197300.901.026521.384100.433480.213030.031464次Newton插值多项式(需5个节点)如下：N4(x)=0.41075+1.116(x-0.4)+0.28(x-0.4)(x-0.55)+0.1973(x-0.4)(x-0.55)(x-0.65)+0.03146(x-0.4)(x-0.55)(x-0.65)(x-0.8)解：首先计算出差商表如下：xif(xi)1阶差商2阶差商3阶差商4阶差商0.400.441经计算得N4(0.596)=0.63192现在试图进行误差估计：R4(x)=|f[x,x0,x1,x2,x3,x4]ω5(x)|因为x=0.596，所以要进行以上的差商运算，需要知道f(0.596)的值，但是我们现在不知道f(0.596)的值。怎么办？可以利用f(0.596)≈N4(0.596)=0.63192来计算差商，见下页。经计算得现在试图进行误差估计：因为x=0.596，所以42xif(xi)1阶差商2阶差商3阶差商4阶差商5阶差商0.400.410750.550.578151.116000.650.696751.186000.280000.800.888111.275730.358920.197300.901.026521.384100.433480.213030.031460.5960.631921.298030.421910.214260.02674-0.02408R4(x)≈-0.02408X(0.596-0.4)X(0.596-0.55)X(0.596-0.65)X(0.596-0.8)X(0.596-0.9)=-0.02408X0.196

X0.046X(-0.054)X(-0.204)

X(-0.304)

≈0.000000727xif(xi)1阶差商2阶差商3阶差商4阶差商5阶差商0.443作业：P48:1,2作业：P48:1,244第2次Newton插值计算方法(NumericalAnalysis)第2次Newton插值计算方法45牛顿插值多项式的概念差商及其性质牛顿插值多项式的系数与误差余项的导出利用牛顿插值多项式近似求解的例子牛顿插值多项式的概念46牛顿插值多项式的概念牛顿插值多项式的概念47§3均差与牛顿插值多项式拉格朗日插值多项式的优点与缺点优点：结构对称，使用方便。缺点：由于是用基函数构成的插值，要增加一个节点时，所有的基函数必须全部重新计算，不具备承袭性，还造成计算量的浪费。§3均差与牛顿插值多项式48例如：3个节点，抛物插值的情况：若要新增加一个节点，而进行3次插值的时候，则需要重新计算例如：3个节点，抛物插值的情况：若要新增加一个节点，而进行349试图改进：我们要构造一种具有承袭性的插值多项式P(x)来克服这个缺点，即，每增加一个新节点时，只需在P(x)原来的表达式中增加相应的一项即可，而不改变P(x)的原来已经存在的表达式部分。这就是牛顿插值多项式的特点。试图改进：我们要构造一种具有承袭性的插值多项式P(x)来克服50可以证明,可将满足插值条件p(x0)=y0,p(x1)=y1，…p(xn)=yn的n次插值多项式,写成如下形式:其中ak(k=0,1,2,…,n)为待定系数。……基函数：(x-x0),(x-x0)(x-x1),…，(x-x0)(x-x1)…(x-xn-1)可以证明,可将满足插值条件其中ak(k=0,1,2,…,51定义：给定n+1个插值节点x0,x1,…,xn,如下形式的插值多项式称为Newton插值多项式：（3.12）其中ak(k=0,1,2,…,n)为待定系数。无xn,将出现在系数中……它满足以下的递推公式：…定义：给定n+1个插值节点x0,x1,…,xn,52牛顿插值多项式Nn(x)是插值多项式p(x)的另一种表示形式,与Lagrange多项式相比它克服了“增加一个节点时整个计算工作重新开始”的缺点,节省乘除法运算次数,在Newton插值多项式中用到的差商等概念，又与数值计算的其他方面有密切的关系.要确定牛顿插值多项式Nn(x)系数，需要利用下一节差商的计算。Home牛顿插值多项式Nn(x)是插值多项式p(x)的另一种表示形式53差商及其性质差商及其性质543.1差商及其性质定义：函数y=f(x)在区间[xi

,xi+1]上的平均变化率称为f(x)关于xi

,xi+1的1阶差商。定义2阶差商定义m阶差商………3.1差商及其性质定义：函数y=f(x)在区间[xi,552阶差商f[xi,xj,xk]是指一般地,可定义[xi,xi+1,…,xi+n]上的n阶差商：2阶差商f[xi,xj,xk]是指一般地,可定义[xi56为了方便地计算差商，需要建立差商表。表中的箭头指向表示更高阶差商所需要的低阶差商的参与。xif[xi]f[xi,xi+1]f[xi,xi+1,xi+2]f[xi,xi+1,xi+2，xi+3]x0f(x0)x1f(x1)f[x0,x1]x2f(x2)f[x1,x2]f[x0,x1,x2]x3f(x3)f[x2,x3

]f[x1,x2,x3]f[x0,x1,x2

,x3]………f[x1,x2]-f[x0,x1]x2–x0f[x1,x2,x3]-f[x0,x1,x2]x3–x0为了方便地计算差商，需要建立差商表。表中的箭头xif[xi]57xif[xi]f[xi,xi+1]f[xi,xi+1,xi+2]f[xi,xi+1,xi+2

,xi+3]002832751256216例2.11求f(x)=x3在节点x=0,2,3,5,6上的各阶差商值。解:计算得如下表xif[xi]f[xi,xi+1]f[xi,xi+1,xi+58性质1函数f(x)的n阶差商f[x0,x1,…,xn]可由f(x0),f(x1),…,f(xn)的线性组合表示：差商的性质验证同学自己验证真漂亮性质1函数f(x)的n阶差商f[x0,x59这种求解差商的方法的优点是直接使用公式，缺点是计算量较大。应理解：右端分母中，xk-xk

项永远不出现。或者表示成以上公式可以利用如下的表达式直接验证这种求解差商的方法的优点是直接使用公式，缺点是计算量较大。应60性质2差商具有对称性,即在k阶差商中任意交换两个节点和的次序,其值不变。即：学生自己验证以上两个公式……性质2差商具有对称性,即在k阶差商即：学生自己验证以上61性质3

若f[x,x0,x1,…,xk]是x的m次多项式,则f[x,x0,x1,…,xk,xk+1]是x的m-1次多项式。注意：右端分子为m次多项式,且由差商的对称性可知，当x=xk+1时,分子为0,故分子含有因子xk+1–x，与分母相消后，右端为m-1次多项式。证：由差商定义

………常数性质3若f[x,x0,x1,…,xk]是x62性质4

若f(x)是n次多项式,则f[x,x0,x1,…,xn]恒为0。证：f(x)是n次多项式，则f[x,x0]是n-1次多项式,f[x,x0,x1]是n-2次多项式。f[x,x0,x1,…,xn]0依次递推…，f[x,x0,x1,…,xn-1]是n-n次（零次）多项式，即常数c.所以

性质4若f(x)是n次多项式,则f[x,x0,63性质5若f(x)存在k阶导数，则f(x)的k阶差商与其k阶导数之间有下列关系：证明：这个性质可直接用罗尔(Rolle)定理证明。Home…性质5若f(x)存在k阶导数，则f(x)的k阶差商64牛顿插值多项式的系数与误差余项的导出牛顿插值多项式的系数65牛顿插值多项式的系数与误差余项的导出的系数ak

(k=0,…,n)可根据以下插值条件推出。…

……………牛顿插值多项式的系数与误差余项的导出的系数ak(k=0,66一般，用数学归纳法可证明从上述各个公式中可以解出：将a1=f[x0,x1]代入下一个等式，得……一般，用数学归纳法可证明从上述各个公式中可以解出：将a167n次牛顿(Newton)插值公式的表达式：………其余项为牛顿插值多项式的误差。……这里没有假设f(x)可导n次牛顿(Newton)插值公式的表达式：………其余项为68牛顿插值多项式余项公式的推导：设x为区间[a,b]上的一点，可得：…从前往后，将后式逐渐带入到前式,即得：根据1阶差商的定义根据2阶差商的定义牛顿插值多项式余项公式的推导：设x为区间[a,b]上的一点69推导完毕(下一页PPT有3个节点情况的详细推导)。…………………推导完毕(下一页PPT有3个节点情况的详细推导)。……………70设x为区间[a,b]上的一点，可得：将(2)式代入(1)式，得：牛顿插值多项式余项公式的仔细推导（以仅有3个插值节点的2次插值为例）：(1)(2)(3)(4)将(3)式代入(4)式，得：整理，得整理，得：N2(x)R2(x)设x为区间[a,b]上的一点，可得：将(2)式代入(1)式71解释：由插值多项式的存在唯一性定理知，满足同一组插值条件的拉格朗日插值多项式P(x)与牛顿插值多项式Nn(x)实际上是同一个多项式的形式以后，所得的表达式是相同的。即将P(x)和Nn(x)所得的多项式表达式，化为解释：的形式以后，所得的表达式是相同的。即将P(x)和Nn(72若f(n+1)(x)不存在，则只有使用(*)式来表达误差。Newton插值多项式的误差(不要求f(x)光滑)(*)(**)若f(n+1)(x)存在，则Lagrange插值多项式的误差仅在f(n+1)(x)存在情况下才成立。于是若f(n+1)(x)不存在，则只有使用(*)式来表达误差。N73评论：牛顿插值公式计算方便，增加一个插值点，只要多计算一项，而Nn(x)的各项系数恰好是各阶差商值，很有规律。Home总结：n次牛顿(Newton)插值公式的表达式为余项………若f(n+1)(x)存在评论：牛顿插值公式计算方便，增加一个插值点，只要多计算一项，74利用牛顿插值多项式近似求解的例子利用牛顿插值多项式近似求解的例子75xif[xi]f[xi,xi+1]f[xi,xi+1,xi+2]f[xi,xi+1,xi+2,

xi+3]x0f(x0)x1f(x1)f[x0,x1]x2f(x2)f[x1,x2]f[x0,x1,x2]x3f(x3)f[x2,x3]f[x1,x2,x3]f[x0,x1,x2,x3]……………xif[xi]f[xi,xi+1]f[xi,xi+1,76xif[xi]f[xi,xi+1]f[xi,xi+1,xi+2]1142(2-1)/(4-1)=1/393(3-2)/(9-4)=1/5(1/5-1/3)/(9-1)=-1/60N2(x)=1+1/3(x-1)-1/60(x-1)(x-4)=-1/60x2+5/12x+3/5N2(7)=2.7例2.12已知x=1,4,9的平方根值，求解1：考虑f(x)=√x，利用差商表求差商xif[xi]f[xi,xi+1]f[xi,xi+1,77解2：利用公式求差商x149f(x)123用这种方法解得得系数与方法1的相同。解2：利用公式求差商x149f(x)123用这种方法解得得系78解3：利用拉格朗日方法求插值对多项式求2次插值对多项式x149f(x)123=-1/60x2+5/12x+3/5解3：利用拉格朗日方法求插值对多项式求2次插值对多项式x14794.4.1差商及其性质例2.13已知x=0,2,3,5对应的函数值为y=1,3,2,5,作三次Newton插值多项式。xif(xi)1阶差商2阶差商3阶差商0123132-2/3553/104.4.1差商及其性质例2.13已知x=0,80例2.14求的值，并估计其误差解：令，取x0=4,x1=9,x2=6.25xf(x)f[xi,xi+1]f[xi,xi+1,xi+2]42936.252.5,差商表例2.14求的值，并估计其误差解：令，取81在区间[4,9]上，由计算器计算结果：N2(7)=2.7，差一些例2.12中，计算结果为：代入x=7例2.14中，计算结果为：N2(7)=2.64848，好一些在区间[4,9]上，由计算器计算结果：N2(7)=2824.4.1差商及其性质例2.15已知f(x)=x7+x4+3x+1

求f[20,21,…27

]及f[20,21,…27,28

]分析：本题f(x)是一个多项式,故应利用差商的性质解:由差商与导数之间的关系4.4