第2章 3.牛顿插值公式

牛顿插值公式邹昌文问题的提出01011010110)(,xxxxyxxxxyxLxx公式为为插值结点的一阶插值以)(001010xxxxyyy，且使原有项不变点现考虑增加一个插值结2x))(()(1012xxxxaLxL可令112002)(,)(yxLyxL显然222)(yxL利用插值条件))(()(120202010102xxxxaxxxxyyyy1201010202xxxxyyxxyya))(()(1012010102020010102xxxxxxxxyyxxyyxxxxyyyL其中的二阶均差关于称为2101201010202,,)(xxxxfxxxxyyxxyy121020210],[],[],,[xxxxfxxfxxxf记为一阶均差上的平均变化率，称为在为],[)(100101xxxfxxyy],[10xxf记为一般地构造以下基函数问题求作n次多项式使满足()nNx0102010121()1()()()()()()()nnnNxccxxcxxxxcxxxxxxxx01()(),,,niiNxfxin(2)(1)为了得到计算系数ci的一般方法,下面引进一般均差的概念.均差/divideddifference/的定义即阶均差，并记为的均差为处的，在结点阶均差的称],,,[)(],,,[1)(101210nnnnxxxfnxfxxxxxxfnxfnknkkkkkkkxxxxxxxxxf0110)())(()()(无关均差与结点的排列次序11101010111010],,...,[],,...,[],,...,[],...,,[],...,[kkkkkkkkkkkxxxxxfxxxfxxxxxfxxxfxxf均差表xif(xk)1阶2阶3阶4阶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)x4f(x4)f(x3,x4)f(x2,x3,x4)f(x1,x2,x3,x4)f(x0,x1,x2,x3,x4)┊┊┊┊┊┊……计算规律：任一个k(≥1)阶均差的数值等于一个分式的值，其分子为所求均差左侧的数减去左上侧的数，分母为所求均差同一行最左边的基点值减去由它往上数第k个基点值。243243432],[],[],,[xxxxfxxfxxxf143214324321],,[],,[],,,[xxxxxfxxxfxxxxf注意：均差表中，对角线上的均差是构造牛顿型插值公式的重要数据。粗线框出的部分在计算机上可存入二维数组例已知函数y=f(x)的观测数据如表，试构造差商表，并求f[2,4,5]及f[2,4,5,6]的值。x02456f(x)159-413解n=4,构造差商表xif(xi)1阶2阶3阶4阶0245621159-4132-13170-515-15526)5(151756)4(132021522459134594105051546)13(1700422525213106)1(5f[2,4,5]=-5f[2,4,5,6]=5牛顿基本插值公式000)()(],[xxxfxfxxf由)](,[)()(000xxxxfxfxf有110010],[],[],,[xxxxfxxfxxxf又代入得将],[10xxf))(](,,[)](,[)()(10100100xxxxxxxfxxxxfxfxf)](,[)()(01001xxxxfxfxN其中线性部分)()()()()()()()(1010101011001xfxxxxxfxfxfxNxfxN满足函数为插值结点的线性插值以为101,)()(xxxfxN)()11xLxN（即的余项)(1xN)()()(11xNxfxR))(](,,[1010xxxxxxxf))()((!2110)2(xxxxf)(!21],,[)2(10fxxxf))(](,,[)](,[)()(1021001002xxxxxxxfxxxxfxfxN同理有：)(!31],,,[)3(210fxxxxf次插值多项式为为插值结点的在一般地nxxxxfn,,)(10],[)()()(000xxfxxxfxf],,[)(],[],[101100xxxfxxxxfxxf],...,,[)(],...,[],...,,[0010nnnnxxxfxxxxfxxxf))...((...))(()()(10102010nnnxxxxaxxxxaxxaaxN12…………n11+(xx0)2+……+(xx0)…(xxn1)n1...))(](,,[)](,[)()(102100100xxxxxxxfxxxxfxfxf))...(](,...,[100nnxxxxxxf))()...(](,...,,[100nnnxxxxxxxxxfNn(x)Rn(x)ai=f[x0,…,xi]易知)()](,,[)()(10101nnnnxxxxxxxfxNxN)())(](,,[))(](,,[)](,[)()(1010102100100nnnxxxxxxxxxfxxxxxxxfxxxxfxfxN称为n次牛顿基本插值公式其余项也相同由唯一性，)()(xNxLnn)()!1(1],,,[)1(10nnfnxxxxf差分与等距结点的牛顿插值公式•当结点为等距时，为简化插值公式，引进差分的概念为结点设)1,0(,00niihxxhi)1,0()(nixfyii且11,01niyyyiii称：处的一阶向前差分为在ix21,012niyyyiii称：处的二阶向前差分为ixrniyyyyiriririr1,0)(1111一般地称：阶向前差分处的为rxi/forwarddifference/向后差分/backwarddifference/111iririryyyi1iiyyy中心差分/centereddifference/212111iririryyy其中)(221hiixyy同理可定义差分的重要性质：线性：例如gbfaxgbxfa))()((若f(x)是m次多项式，则是次多项式，而)0()(mkxfkkm)(0)(mkxfk差分值可由函数值算出：njjknjknfjnf0)1(njnjkjnknfjnf0)1(!)1)...(1(jjnnnjn其中/*binomialcoefficients*/函数值可由差分值算出：kjnjknfjnf0kkkhkfxxf!],...,[00knkknnnhkfxxxf!],...,,[1kkkhff0)()(由Rn表达式牛顿公式的向前差分形式)()(00thxNxNthxxnn则设)())(](,,[))(](,,[)](,[)(11010102100100nnxxxxxxxxxfxxxxxxxfxxxxfxfhitxxniihxxii)(,1,00又hnthtthxxxfhtthxxxfthxxfxfn)1()1(],,[)1(],,[],[)(10210100)1()1(!)1(!200200ntttnyttytyyn牛顿前差公式/Newton’sforward-differenceformula/牛顿后差公式/Newton’sbackward-differenceformula/将节点顺序倒置：))...(](,...,[...)](,[)()(101xxxxxxfxxxxfxfxNnnnnnnn设htxx0，则)()()(000xfkthtxNxNknknn),(,))...(1()!1()()(01)1(nnnnxxhntttnfxR设htxxn，则)()1()()(0nknkknnnxfkthtxNxN注：一般当x靠近x0时用前插，靠近xn时用后插，故两种公式亦称为表初公式和表末公式。也可写为以下简略形式