第04章插值法02牛顿插值

第四章 插值法教 师：周辉 陈汉明电子邮箱：办 公 室：地质楼524电 话：89731005地球物理与信息工程学院计算方法 引言 回顾拉格朗日插值方法，其插值公式为：001110011100()()()().()().()()().()().()nnkkknkknkkkkkkkkknnnikkikii kL xlx yxxxxxxxxxxyxxxxxxxxxxxxyxx 1,0,0,1,.,kiiklxin ik其中插值基函数满足第四章 插值法（1）优点：形式对称，计算较方便且易于编程拉格朗日插值多项式的特点（2）缺点：插值基函数依赖全部节点，每增加一个节点，基函数需要重新计算！01110111kknkkkkkkkknxxxxxxxxxxlxxxxxxxxxxx为了克服这个缺点，引入牛顿插值法。第四章 插值法 引言 4.2 牛顿（Newton）插值为了使牛顿插值多项式具有承袭性，令插值函数具有下列形式：来确定。0011010011()nnnnnNxaaaaaxxaxxxxxx其中 为待定系数，它们可由插值条件,0,1,njjNxf xjn称为牛顿插值基函数。为求出Nn(x)，利用插值条件，引出差商的概念。0111,1iiixxxxxin01,.,naaa上式中第四章 插值法4.2 牛顿（Newton）插值（1）函数 在点 处的零阶差商为：()f xix iif xfx（2）函数 在点 的一阶差商为：()f x,ijxx,ijijjiijijijjif xfxfxfxfxfxfxxxxxxxx（3）函数 在点 的二阶差商为：()f x,ijkxxx1.差商的定义第四章 插值法4.2 牛顿（Newton）插值,ijjkijjkijjkijkikikjkijijjkijjkijjkikjkiikjijkikijjkjiikijjifxfxfxfxfxxfxxxxxxfxxxxxxxxxfxfxxxfxfxxxxxxxxxxxxxfxxxfxxxfxxxxxxxfxfxxxxxxxx 01njkjjkkikjnjfxfxxxxxxx1.差商的定义第四章 插值法4.2 牛顿（Newton）插值（4）一般地，函数 在点 处的n 阶差商为：()f x01,.,nxxx0111010,nnnnf xxxf xxf xxxxx1.差商的定义第四章 插值法4.2 牛顿（Newton）插值 000000limlim,xxxxfxfxfxxfxxx故一阶差商是微商的离散形式。k 阶差商为 k-1 阶差商的差商。因而当 k-1 阶差商为常数时，k 阶差商为0。差商与插值节点的排列顺序无关，例如,ijjiijkjikkjifxxfxxfxxxfxxxfxxx2.差商的特点第四章 插值法4.2 牛顿（Newton）插值 010011.nnnN xaa x xa x xx xx x 利用插值条件，,0,1,njjNxf xjn 000af xf x 01101aa xxf x（1）取 时，（2）取 时，0 xx1xx 1010110 ,f xf xaf x xxx确定 n 阶牛顿多项式的系数，（零阶差商）（一阶差商）第四章 插值法4.2 牛顿（Newton）插值 0120220212aa xxa xxxxf x1201201220,f x xf x xaf x x xxx（3）取 时，2xx（二阶差商）00100120101011,.,nnnNxf xf xxxxf xxxxxxxf xxxxxxxxx因此猜测牛顿插值多项式为：第四章 插值法n阶差商二阶差商一阶差商4.2 牛顿（Newton）插值第四章 插值法 102020102202120101020101020212010102020211012100200212001002021102f xf xf xf xxxxxaxxxxf xf xf xf xxxxxxxxxxxxxf xf xxxf xf xxxxxxxxxx f xx f xx f xx f xx f xx f xx f xx f xxxxxxxx 10021102202110012012020112102021,x f xxxf xxxf xxxxxxxf xf xf xf x x xxxxxxxxxxxxx关于a2的推导4.2 牛顿（Newton）插值验证猜测，由差商的定义可知：000001011010120122011010,.,.,.,()nnnnf xf xf x xxxf x xf xxf x xxxxf x xxf xxxf x xxxxxf x xxxf xxxf x xxxx将代入得 001001011,+,=f xf xf xxxxf x xxxxxxNxR x第四章 插值法4.2 牛顿（Newton）插值将代入得 00100120101201222,+,+,=f xf xf xxxxf xxxxxxxf x xxxxxxxxxNxRx010120122,f x xxf xxxf x xxxxx 00100101,+,f xf xf xxxxf x xxxxxx第四章 插值法4.2 牛顿（Newton）插值 012010010010110101,nnnnf xf xf xxxxf xxxxxxxf xxxxxxxxxf xxxxxxxxxx类似逐次将各式代入前一公式可得：则可知 10000101120011,.,nnnNxf xf xxxxf xxxxxxxf xxxxxxxxx 0011,.,nnR xfxxxxxxxxxx为 n 次牛顿插值公式的余项。为满足插值条件 的牛顿插值多项式。,0,1,njjNxf xjn第四章 插值法4.2 牛顿（Newton）插值 拉格朗日和牛顿插值法都是多项式插值，根据上一小节的插值多项式唯一性定理，定理定理5.1：在n+1个互异节点 满足插值条件0,1,.,ix in,0,1,.,niipxf xin的次数不超过n的多项式 存在且唯一。nipx牛顿插值法应等价于拉格朗日插值法第四章 插值法4.2 牛顿（Newton）插值 101()nnnkkknxL xyxxx 10000101120011,.,nnnNxf xf xxxxf xxxxxxxf xxxxxxxxx1100()(),()()nnninkkiiii kxxxxxx其中，nnNxLx牛顿法拉格朗日法第四章 插值法4.2 牛顿（Newton）插值性质10101,kikjkjfxf xxxx无论如何安排插值节点的顺序，只要节点相同它们所对应的差商值是相同的。对比 与 的最高次项系数可得：()nNx()nL x01,kf xxx可表示为 的01,kfxfxfx线性组合，性质2 差商与插值节点的排列顺序无关（对称性），例如,ijjifxxfxx第四章 插值法4.2 牛顿（Newton）插值，因而当 f 有n+1阶导数时有以下等式，R xR x (1)011,1!nnnnff x xxxxn进一步可得到：又可知性质3 差商与导数的关系 010,!nnnff xxxxxn第四章 插值法4.2 牛顿（Newton）插值可知，每增加一个结点，Newton插值多项式只增加了一项，克服了Lagrange插值的缺点。注意：注意：n次代数插值问题的解是存在且唯一的，因此，Newton 插值多项式与Lagrange插值多项式只是形式上不同，若将它们按x 的幂展开，所得的多项式是完全一样的。并且由 10000101120011,.,nnnNxf xf xxxxf xxxxxxxf xxxxxxxxx第四章 插值法4.2 牛顿（Newton）插值牛顿插值法需要计算差商，可用差商表计算xi零阶差商一阶差商二阶差商三阶差商x0f(x0)x1f(x1)f x0,x1x2f(x2)f x1,x2f x0,x1,x2x3f(x3)f x2,x3f x1,x2,x3f x0,x1,x2,x3fx1,x2-fx0,x1x2 x0第四章 插值法4.2 牛顿（Newton）插值0.400.550.650.800.901.05()0.410750.578150.696750.88811 1.026521.25386kkxf x已知 f(x)=sh(x)的函数值如下表2 0.65 0.69675 1.1860 0.28003 0.80 0.88811 1.2757 0.3588 0.1974 0.90 1.02652 1.3841 0.4336 0.214 0.0345 1.05 1.25386 1.5156 0.5260 0.231 0.0340 0.40 0.410751 0.55 0.57815 1.1160k xif(xi)一阶差商 二阶差商 三阶差商四阶差商第四章 插值法解：差商表如下用牛顿插值公式求 f(0.596)=sh(0.596)的近似值。4.2 牛顿（Newton）插值 从差商表可看出，四阶差商为常数，故五阶差商为零，插值公式只会用到五个插值点（题中多出一个）。为保证插值精度，选取更靠近0.596的节点x0,x1,x2,x3,x4作为插值节点，根据牛顿插值公式得到：40.410751.11600.40 0.28000.400.55 0.1970.400.550.65 0.0340.400.550.650.80Nxxxxxxxxxxx将 代入上式得到0.596x 40.5960.5960.63192fN第四章 插值法