第五章-插值法

2013-12-2SCHOOLOFMATHEMATICS72-1第五章插值法第二节Lagrange插值第三节逐步线性插值第四节Newton插值第五节Hermite插值第一节引言第六节分段多项式插值第七节三次样条插值2013-12-2SCHOOLOFMATHEMATICS72-2第一节引言插值方法是数据处理、函数近似、计算机几何造型的常用工具；为其它数值方法（数值微积分、非线性方程数值解、微分方程数值解等）提供重要的理论基础。2013-12-2SCHOOLOFMATHEMATICS72-3一、插值问题设01(),(),,()nxxxϕϕϕ是定义在[a,b]上的n+1个线性无关的函数，()fx是定义在[a,b]上的函数，01,,,nxxx是[a,b]中的n+1个互异节点，已知(),0,1,,.iiyfxin==构造0011()()()()nnxcxcxcxϕϕϕϕ=+++插值函数：使之满足()(),0,1,,.iixfxinϕ==()xϕ()fx被插函数：01,,,nxxx插值节点：()()()rxfxxϕ=−插值余项：2013-12-2SCHOOLOFMATHEMATICS72-4构造n次多项式函数(),nPx注：插值多项式：(),0,1,,.niiPxyin==(,)(0,1,,)iixyin=型值点：()()()nrxfxPx=−插值余项：插值函数是多项式函数时，称为多项式插值：使之满足：()nPx插值条件：2013-12-2SCHOOLOFMATHEMATICS72-5二、插值多项式的存在性和唯一性满足插值条件的多项式存在且唯一．定理5.1.1（用Cramer法则易证，见P118）注：过n+1个点可唯一做一条n次代数曲线！x0x1x2x3x4Pn(x)f(x)2013-12-2SCHOOLOFMATHEMATICS72-6第二节Lagrange插值一、Lagrange插值多项式二、Lagrange插值余项Lagrange（法1736-1813）2013-12-2SCHOOLOFMATHEMATICS72-7一、Lagrange插值多项式设0()(),nniiiPxylx==∑1,,()0,.ijijlxij=⎧=⎨≠⎩()0,1,,in=()ilx其中满足：()nPx则满足插值条件(),0,1,,.niiPxyin==注：()?ilx=2013-12-2SCHOOLOFMATHEMATICS72-8110()()()()(),iiiinxxlxAxxxxxx−+=−−−−由于()0ilx=011,,,,,iinxxxx−+是的根，分析：设又()1,iilx=即所以011()()()()1,iiiiiiinAxxxxxxxx−+−−−−=0111,()()()()iiiiiiinAxxxxxxxx−+=−−−−111010()()()()().()()()()niiiiiiiiinxxxxxxlxxxxxxxxxxx−+−+−−−−=−−−−解得2013-12-2SCHOOLOFMATHEMATICS72-9定义5.2.1称为Lagrange插值基函数．0111100()()()()(),()()()()njnijiiiiijijiiniixxxxxxxxxlxxxxxxxxxxxx−+≠=−+−−−−−==−−−−−∏其中称0()()nniiiPxylx==∑为Lagrange插值多项式．()0,1,,in=2013-12-2SCHOOLOFMATHEMATICS72-10P120例5.2.1P161Ex1注：记01()()()(),nnxxxxxxxω=−−−则110()()()()(),iniiiiinixxxxxxxxxω−+′=−−−−故()(),()()niinixlxxxxωω=′−0()()()()nnniiinixPxyxxxωω==′−∑2013-12-2SCHOOLOFMATHEMATICS72-11二、Lagrange插值余项()(1)()()()()().1!nnnnxrxfxPxfnωξ+=−=+存在与x有关的(,),abξ∈使得若()定理5.2.2fx在包含插值节点的区间[a,b]上n+1阶可导，[,],xab∀∈则对证：当x为插值节点时，结论显然成立！()0,1,,ixxin≠=当时，令()()()()[()()].()nnnntFfPfxPxttxtωω=−−−2013-12-2SCHOOLOFMATHEMATICS72-12由Rolle定理知，显然F(t)具有n+1阶导数，01,,,,n即xxxx且有n+2个零点()()()()[()()].()nnnntFfPfxPxttxtωω=−−−()Ft′至少有n+1个零点，()Ft′′至少有n个零点，(1)()nFt+至少有1个零点,ξ(1)(1)()()[()()](0.(1)!0)nnnnnFffxPxxξωξ+++=−−−=()(1)()()()().1!nnnxfxPxfnωξ+−=+证毕！2013-12-2SCHOOLOFMATHEMATICS72-13(1)()0.nfξ+=Lagrange插值多项式就是其本身．推论若()事实上，fx是次数不超过n的多项式函数，则其n次P161Ex2()(1)()()()()01!nnnxfxPxfnωξ+−==+()().nPxfx⇒=00()(),0,1,,.nnkkiiiiiixylxxlxkn=====∑∑特别的，k=0时，f(x)≡xk(k=0,1,…,n)时，0()1.niilx=≡∑2013-12-2SCHOOLOFMATHEMATICS72-14小结：Lagrange插值法优点：缺点：结构紧凑、系数的几何意义明确，便于理论分析！不具有承袭性！（即插值节点的变化将引起整体公式的变化！）逐步线性插值Newton插值2013-12-2SCHOOLOFMATHEMATICS72-15第三节逐步线性插值一、Aitken插值二、Neville插值思想：把高次插值转化为多步线性插值！2013-12-2SCHOOLOFMATHEMATICS72-16一、Aitken插值（算法）Step1.()01,2,,ipin=00(,),(,)iixyxy过作线性插值000()()()()()iiiiiipxpxPxpxxxxx−=+−−注：Step2.()012,3,,ipin=1010(,),(,)iixpxp过作线性插值Step3.()0123,4,,ipin=201201(,),(,)iixpxp过作线性插值Stepn.012np1012,1012,2,(,),(,)nnnnnxpxp−−−过作线性插值2013-12-2SCHOOLOFMATHEMATICS72-17Aitken算法：0x01P123例5.3.1p012p012np1x2x3x0y1y2y3y02p03p013p0123pnxny0np01np012np2013-12-2SCHOOLOFMATHEMATICS72-18二、Neville插值（算法）0x01p012P125例5.3.2p012np1x2x3x0y1y2y3y12p23p123p0123pnxny1,nnp−2,1,nnnp−−3,2,1,nnnnp−−−2013-12-2SCHOOLOFMATHEMATICS72-19小结：逐步线性插值法优点：缺点：算法简单，易于求值！具有承袭性！不适合表示插值多项式本身！Newton插值2013-12-2SCHOOLOFMATHEMATICS72-20第四节Newton插值一、差商及性质二、Newton插值Newton（英1642-1727）2013-12-2SCHOOLOFMATHEMATICS72-21000121()()()()npxxxaaxxxax=+−+−−+考虑到插值法的承袭性，由00()(),nPxfx=可设插值多项式0111()()()nnxxxxxax−−+−−−解得00(),fax=由11()(),nPxfx=解得11010()(),fxfxxxa−=−由22()(),nPxfx=解得20120201021()()()()fxfxfxfxxxxxxax−−−−−=−2013-12-2SCHOOLOFMATHEMATICS72-22一、差商及性质定义5.4.1()()[,],jiijjifxfxfxxijxx−=≠−已知互异型值点：(,()),0,1,,iixfxin.=为f(x)在xi,xj处的一阶差商，称称[,][,][,,],jkijijkkifxxfxxfxxxikxx−=≠−为f(x)在xi,xj,xk处的二阶差商，称101010[,,][,,][,,,]kkkkfxxfxxfxxxxx−−=−为f(x)在x0,x1,…,xk处的k阶差商.2013-12-2SCHOOLOFMATHEMATICS72-23注1．零阶差商：[](),0,1,,.iifxfxin==重节点差商：[,]lim[,],0,1,,.iiiixxfxxfxxin→==N101011d[,,,,,][,,,,]dkkkmmfxxxxxfxxxxx−−=如：()()lim()iiixxifxfxfxxx→−′==−(1)[,]().kikiifxxfx−= 2013-12-2SCHOOLOFMATHEMATICS72-24注2．差商的计算：0x0[]fx1x1[]fx2x2[]fx3x3[]fx01[,]fxx12[,]fxx23[,]fxx012[,,]fxxx123[,,]fxxx0123[,,,]fxxxx差商表2013-12-2SCHOOLOFMATHEMATICS72-25•差商的性质性质1.若()(),FxCfx=0101[,,,][,,,].nnFxxxCfxxx=则（常数可提性）性质2.010101[,,,][,,,][,,,].nnnFxxxfxxxgxxx=+若()()(),Fxfxgx=+（代数和性质）则性质3.（对称性）任意调换01,,,nxxx的位置，01[,,,]nfxxx不变．00[,,,,,,][,,,,,,].nijinjfxxfxxxxxx=即2013-12-2SCHOOLOFMATHEMATICS72-26性质4.若()()(),fxxxϕψ=则性质5.110100()[,,,].()()()(),nniiiiiiiinxxxffxxxxxxxxx−+==−−−−∑性质6.（Leibniz公式）010110[,,,][,,,][,,,].nnjnjjjxfxxxxxxxxϕψ+==∑0[,,]nfxx可表示为0(),,()nfxfx的线性组合：01[,,,,]nfxxxx若是一个关于x的m次多项式，011[,,,,,]nnfxxxxx+则是一个关于x的m-1次多项式．特别的，n次多项式的一阶差商是n-1次多项式.2013-12-2SCHOOLOFMATHEMATICS72-27二、Newton插值定理5.4.1001001201()()[,]()[,,]()()npxfxfxxxxfxxxxxxx=+−+−−满足插值条件：多项式（Newton插值多项式）0101()()()[,,,,]()()().nnnnRxfxPxfxxxxxxxxxx=−=−−−01011[,,,]()()()nnfxxxxxxxxx−++−−−(),0,1,,.niiPxyin==插值余项：2013-12-2SCHOOLOFMATHEMATICS72-28证：(),0,1,,.niiPxyin==满足插值条件：()npx设1(),0,1,,1.niiPxyin−==−满足插值条件：1()npx−则为011,,,nxxx−1()()0nnPxPx−−=的根，则1011()()()()()nnnnPxPxaxxxxxx−−−=−−−(),nnnPxy=又带入解得101()()()nnnnnnnyPxaxxxx−−−=−−10011()()()()niininnnnylxxxxxxx−=−−Δ=−−−∑01()()