数值计算方法：拉格朗日插值法与牛顿插值法

拉格朗日插值法问题的提出01(),,,,,(),(0,1,,)()niyfxababxxxyfxinfx在实际问题中常遇到这样的函数，其在某个区间上是存在的。但是，通过观察或测量或实验只能得到在区间上有限个离散点上的函数值或者的函数表达式是已知的，但却很复杂而不便于计算，希望用一个简单的函数来描述。问题的提出010011()1,,,(),(0,1,,),()(),(0,1,,).()1,,,,,,,,()()()niiiinnyfxnxxxyfxinyPxPxyinyfxnxyxyxyxabRxfxPx插值问题的数学提法：已知函数在个点上的函数值求一个多项式，使其满足即要求该多项式的函数曲线要经过上已知的个点同时在其他上要估计误差插值问题()yfxn1,,,,,,,0011nnxyxyxy()()()RxfxPxn1该多项式的函数曲线要经过上已知的这个点同时在其它上要估计误差。当时,求一次多项式,yy0y1y2yn-1ynx0x1x2xn-1xnxf(x)P(x)一次插值y0y1x0x1P1(x)f(x)yx100111(),,,,nPxxyxy当时，求一次多项式要求通过两点二次插值yxy0y1y2x0x1x2f(x)P1(x)20011222(),,,,,,nPxxyxyxy当时，求二次多项式要求通过三点拉格朗日插值公式线性插值（一次插值）1111111111(),(),()()(),(),,,kkkkkkkkkkkkkkfxxxyfxyfxyPxyPxyPxxyxy已知函数在区间的端点上的函数值，求一个一次函数使得。其几何意义是已知平面上两点，求一条直线过该已知两点。线性插值插值函数和插值基函数1111111111111()()()(),()kkkkkkkkkkkkkkkkkkkkkkkkyyPxyxxxxxxxxyyPxyyxxxxxxxxlxlxxxxx由直线的点斜式公式可知：，把此式按照和写成两项:，记，称它们为一次插值基函数。线性插值基函数的特点：()klxkx1kx()klx1()kxl10011()klxkx1kx11111()()(),kkkkkkkkPxylxylxyyxx拉格朗日型插从而，此形式称之为。其中，插值基函数与、无关，而由插值结点、值多项式决定例子0101011lg101,lg201.3010lg12()lg()lg(10)1(20)1.3010102011.3010201101()(20)()(10)102010201010fxxfxxffxxyyxxlxxlxx例：已知，利用插值一次多项式求的近似值。解：，，，设，，，，则插值基本多项式为：，例子10011111.3010()()()(20)(10)101011.3010(12)(1220)(1210)1.06021010lg12lg10lg20lg121.0792).PxylxylxxxP于是，拉格朗日型一次插值多项式为：故即由和两个值的线性插值得到，且具有两位有效数字（精确解二次插值多项式111111221122111111(),,(),()()()()()(),,,,kkkkkkkkkkkkkkkkkkkkkyfxxxxyfxyfxyfxPxPxyPxyPxyxyxyxy已知函数在点上的函数值，。求一个次数不超过二次的多项式，使其满足，，。其几何意义为：已知平面上的三个点：，，求一个二次抛物线，使得该抛物线经过这三点。二次插值基本多项式11,,kkkxxx有三个插值结点，构造三个插值基本多项式，要求满足：（1）基本多项式为二次多项式；（2）它们的函数值满足下表：1kxkx1kxkx1kx1()klx()klx1()klx1000100011kx1()klx()klx1()klx二次插值基本多项式1kxkx1kx1()klx()klx1()klx111111111111111111()0,()0()()()()()()()1()()1()()1()()()()kkkkkkkkkkkkkkkkkkkkkkkkklxlxlxxxxxlxaxxxxlxaxxxxxxxxalxxxxxxx因为，故有因子，而其已经是一个二次多项式，仅相差一个常数倍，可设，又因为，故，得：，从而11111111111()()()()()()()()()()()kkkkkkkkkkkkkkkkxxxxxxxxxxlxlxxxxxxxxx，，拉格朗日型二次插值多项式2111122()()()()()(),1,,1kkkkkkiiPxylxylxylxPxPxyikkk由前述，拉格朗日型二次插值多项式：，是三个二次插值多项式的线性组合，因为它是次数不超过二次的多项式，且满足：例子2例：已知ixlgiiyxixlgiiyx10152011.17611.3010lg12利用此三值的二次插值多项式求的近似值012012101520(15)(20)1()1520(1015)(1020)50(10)(20)1()1020(1510)(1520)25(10)(15)1()1015(2010)(2015)50xxxxxlxxxxxlxxxxxlxxx解：设，，，则例2（续）ixlgiiyx200112221()()()()2015501.17611.301010201015255011.1761(12)122012151210122050251.3010121012151.076650lg12lg121.07923PxylxylxylxxxxxxxP故所以：利用三个点进行抛物线插值得到的的值，与精确值相比，具有位有效数字。拉格朗日型n次插值多项式0101(),,,,,,()()0,1,,1nnnniiyfxxxxyyyPxPxyinnn已知函数在n+1个不同的点上的函数值分别为，求一个次数不超过n次的多项式，使其满足，即个不同的点可以唯一决定一个次多项式。插值基函数0111(),(),,()()1()2()1,()0,niiiiiknnnlxlxlxlxlxnlxnlxki过个不同的点分别决定个次插值函数。每个插值基本多项式满足：（）是次多项式；（）而在其它个。插值基函数01101101101()0,()()()()()()()()()()()1()()()()()()()(ikiiiniiiniiiiniiiiilxkilxxxxxxxxxnlxaxxxxxxxxlxaxxxxxxxxlxxxxxx由于，故有因子：，因其已经是次多项式，故而仅相差一个常数因子。令：由，可以定出，进而得到：1)()iinxxxn次拉格朗日型插值多项式Pn(x)010100110()1(),(),,(),,,()()()()()()()0,1,,nnnnnnnkkknniiPxnnlxlxlxyyyPxylxylxylxylxPxnPxyin是个次插值基本多项式的线性组合，相应的组合系数是。即从而是一个次数不超过的多项式，且满足，例子01234012340(2,0)(4,3)(6,5)(8,4)(10,1)24681003541(4)(6)(8)(10)()(24)(26)(28)(210)1(4)(6)(8)(10)384xxxxxyyyyyxxxxlxxxxx例3：求过点的拉格朗日型插值多项式。解：用4次插值多项式对5个点插值：，，，，，，，，，；123(2)(6)(8)(10)()(42)(46)(48)(410)1(2)(6)(8)(10)96(2)(4)(8)(10)()(62)(64)(68)(610)1(2)(4)(8)(10)64(2)(4)(6)(10)()(82)(84)(86)(810)1xxxxlxxxxxxxxxlxxxxxxxxxlx，，4(2)(4)(6)(10)96(2)(4)(6)(8)()(102)(104)(106)(108)1(2)(4)(6)(8)384xxxxxxxxlxxxxx，；40011223344()()()()()()3(2)(6)(8)(10)965(2)(4)(8)(10)644(2)(4)(6)(10)961(2)(4)(6)(8)384Pxylxylxylxylxylxxxxxxxxxxxxxxxxx所以拉格朗日插值多项式的截断误差,()(),()()()()()()()0nnnniniiniabPxfxRxRxfxPxxxRxfxPx我们在上用多项式来近似替代函数其截断误差记作，。当在插值结点上时，估计截断误差。拉格朗日插值多项式的截断误差()(1)01(1)011()()[,]()(,)()[,]1()()()(1)!(,),()()()()nnnnnnnnnyfxnyfxabyfxabaxxxbPxnxabRxfxnabxxxxxxx定理：设函数的阶导数在上连续，在上存在；插值结点为，是次拉格朗日插值多项式；则对任意有：其中……例子1''2''2''12lg121lg10lg20lg12P121.0602,lg121.0792e1.07921.06020.0190()lg1(),10,20ln101|()|0.043ln10101|()(1210)(1220)|80.0430.3442fxxfxxxff分析例，例中计算的截断误差在例中，用和计算，估计误差：当时例子2'''43'''242lg10lg15lg20lg12.P121.0766,e1.07921.07660.00262()8.68610ln101|(12)||()(1210)(1215)(1220)|3!18.686102380.006956fxxRf在例中，用，和计算估计误差：故牛顿插值均差010101010101010112011202012()1,,,(),(),,(),,,()()1.(),[,][,][,]2.[,][,](),,nnnfxnxxxfxfxfxyyyfxfxfxxxfxxxxfxxfxxfxxfxxxxfxxxx设函数在个相异的点上的函数值分别为，或者记为一阶均差：称为关于结点的一阶均差，记为。二阶均差：一阶均差，的均差称为关于结点的二阶均差，0120111201001[,,]3.1[,,,][,,,][,,,]()1,,,nnnnnfxxxnnnfxxxfxxxfxxxxxfxnxxx记为。阶均差：递归地用阶均差来定义阶均差，称为关于个结点的均差。均差的性质010100110101010101100112012020102011001.11,,,[,,,]()()()()()()[,][,][,][,,]11()nnknkkkkkkknnnyyyyfxxxxxxxx