第4章_插值与拟合-牛顿法概要

第4章插值与拟合4.3差商与牛顿插值公式Lagrange插值多项式的基函数：)())(())(()())(())(()(11101110njjjjjjjnjjjxxxxxxxxxxxxxxxxxxxxxlnjxxxxnjiiiji,,2,1,0)()(0优点：形式对称，有很强的规律性，便于记忆。缺点：(1)重复计算多,导致计算量大；(2)插值基函数lj(x)依赖于所有节点，当增加插值节点时，原来已算出的所有lj(x)都需要重新计算，使计算量加大。差商及其性质牛顿插值公式牛顿插值余项差分以及等距节点牛顿插值多项式4.3差商与牛顿插值公式Newton(1624～1727)由线性代数知识可知,任何一个n次多项式都可表示成:这n+1个多项式的线性组合.问：是否可以将这n+1个多项式作为插值基函数？已知函数f(x)的插值节点xi及相应函数值,将上述线性无关的多项式取作Newton插值法的基函数,即令：),...,1,0(nifi101100)()())(()(1)(jkkjjxxxxxxxxxx),2,1(njNewton插值基函数则相应的插值多项式为:njjkkjnjjjnxxaaxaxP11000)()()(式中,为待定参数,它们可利用插值条件来求,即令：naaa,...,,10iinfxP)(可以求得：injjkkijinfxxaaxP1100)()(),...,1,0(ni000)(faxPn101101)()(fxxaaxPn00fa01011xxffa21202202102))(()()(fxxxxaxxaaxPn12010102022xxxxffxxffa323130331303203103))()(())(()()(fxxxxxxaxxxxaxxaaxPn23120101020213010103033xxxxxxffxxffxxxxffxxffaja依此类推,可求得.为标记、推导、记忆方便,给出差商定义,可得参数的一般表达式。),...,1,0(njaj这也太复杂了吧！为关于节点的一阶均差(差商)kixxxf,)(4.3.1差商及其性质1.差商的定义:设给定函数在个互异的节点处的函数值为,称1)(nxfnnfffxxx,...,,,...,,1010)(],[ijxxffxxfijijji)(],[],[],,[kjixxxxfxxfxxxfjkjikikji为关于节点的二阶差商kjixxxxf,,)(缺倒数第二个节点缺最后一个节点最后一个节点－倒数第二个节点称可见：一个高阶差商可由两个低一阶的差商得到],,,,[110kkxxxxf1110210],,,[],,,,[kkkkkxxxxxfxxxxf缺倒数第二个节点缺最后一个节点称kkxxxx,,,,110为关于节点的k阶差商)(xf最后一个节点－倒数第二个节点由此定义,显然:00fa01011xxffa12010102022xxxxffxxffa],[10xxf121020],[],[xxxxfxxf],,[210xxxf用归纳法可证：],...,,[10kkxxxfa将上述结果代入：njjkkjnxxxxxffxP110100)(],...,,[)()(xNninjjkkijinfxxaaxP1100)()(),...,1,0(ni2.差商的性质性质1：差商与函数值的关系f(x)关于的k阶差商是f(x)在这些点上函数值的线性组合,即kkxxxx,,,,110kjiiijkjjkkxxxfxxxxf001101)(],,,,[10101)(jjiiijjxxxf100011010110],[xxfxxfxxffxxf例如:可以用数学归纳法证明利用对称性,可对f(x)关于的k阶差商变形kxxx,...,,10],,,...,,[],,...,,[0211110kkkkkxxxxxfxxxxf00211211],,,,[],,,,[xxxxxxfxxxxfkkkkkk01210121],,,,[],,,,[xxxxxxfxxxxfkkkkkk注：上式是计算中常用的差商公式，可建立差商表.缺第一个节点缺最后一个节点最后一个节点－第一个节点性质2：对称性差商对于定义它的节点而言是对称的,也就是说任意调换节点的次序,差商的值不变3.差商的计算方法：差商表)()()()()()(4433221100xfxxfxxfxxfxxfxxfxkk四阶差商三阶差商二阶差商一阶差商],[10xxf],[21xxf],[32xxf],[43xxf],,[210xxxf],,[321xxxf],,[432xxxf],,,[3210xxxxf],,,[4321xxxxf],,,[410xxxf规定函数值为零阶差商!)(],...,,[)(10kfxxxfkk性质3:差商与函数导数之间的关系当f(k)(x)在包含节点x0,x1,…,xk的区间存在时,在x0,x1,…,xk之间必存在一点ξ,使得内容归纳Newton插值基函数:101100)()())(()(1)(jkkjjxxxxxxxxxx),2,1(njnjjkkjnjjjnxxaaxaxP11000)()()(并形式上给出Newton插值多项式:naaa,...,,10式中,待定.],...,,[10kkxxxfa通过引进均差/差商的概念,可以将系数表示为：4.3.2牛顿插值公式为f(x)关于节点的n次Newton插值多项式.),...,1,0(nixi1.定义:称)())(())(()()(110102010nnnxxxxxxaxxxxaxxaaxNnkkjjkxxx,,x,xfxf110100)(][)(nkkkxx,,x,xfxf1100)(][)(------(1)由插值多项式的唯一性,Newton插值公式的余项为:)()!1()(11xnMxRnnn实用的余项估计式：)()()()()(xLxfxNxfxRnnn)()!1()(1)1(xnfnn------(2)Lagrange插值多项式导数型余项若将视为一个节点,则由一阶均差定义),,1,0(,nixxi)](,[)()(000xxxxfxfxf)](,...,,[],...,,[],...,,[11011020nnnnxxxxxfxxxfxxxfxxxxfxxfxxxf101010],[],[],,[4.3.3牛顿插值余项)](,...,,[],...,,[],...,,[01010nnnnxxxxxfxxxfxxxf同理,由二阶均差定义有有)](,,[],[],[110100xxxxxfxxfxxfxxxfxfxxf000)()(],[因此可得:)]([)()(000xxx,xfxfxf)))(]([][()(0110100xxxxx,x,xfx,xfxf))(]([)]([)(10100100xxxxx,x,xfxxx,xfxfnjjnnkkjjkxxx,,x,x,xfxxx,,x,xfxf010110100)(][)(][)()()(xRxNnnNewton插值多项式差商型余项njjnnxxxxxxfxN010)(],,,,[)(------(3)4.3.4差分及其等距节点牛顿插值多项式定义4.4设f(x)在等距节点处的函数值为称,0khxxknk,,1,0,kfkkkfff12为f(x)在xk处的二阶向前差分为f(x)在xk处的一阶向前差分kkkfff1等距节点插值是比较常见的情况,为简化计算,引进差分的概念.依此类推:kmkmkmfff111为f(x)在xk处的m阶向前差分4433221100fxfxfxfxfxfxkk四阶差分三阶差分二阶差分一阶差分0f1f2f3f02f12f22f03f13f04f差分的计算方法:差分表在等距节点的前提下,差商与差分有如下关系:],,,[321iiiixxxxf221223hhffii33!3hfiiiiiiiiixxxxxfxxxf321321],,[],,[差商与差分的关系],[1iixxfhfiiiiixxff11],,[21iiixxxfiiiiiixxxxfxxf2121],[],[hhfhfii21222hfi依此类推：],,,[1miiixxxfmimhmf!差分表示的Newton插值公式Newton向前(差分)插值公式),,,1,0(,0nabhnkkhxxk记插值点：)0(0tthxxnxxx,,,10如果节点是等距的,即10)(kjjxx1000)(kjjhxthx------(7))(10kjkjth])[(10kjhjt由差商与向前差分的关系：],,,[10kxxxfkkhkf!0-----(6)以及)(0thxNn式(7)、(6)代入差商表示的插值公式：nkf10kkhkf(10kjjt![0kfk-----(8)Newton向前(差分)插值公式)(xNnnkkxxxff1100],,,[10)(kjjxx得差分表示的Newton插值公式化为：kkhkf!0)(10kjkjth