三次样条插值

插值与拟合前言函数是多种多样的，在科研与工程实际中有的函数表达式过于复杂而不便于计算，但又需要计算多点的函数值；有的函数甚至给不出数学式子，只能通过实验和测量得到一些离散数据（如某些点的函数值和导数值）。面对这种情况，很自然的一个想法就是构造某个简单的函数作为要考察的函数的近似。如果要求近似函数满足给定的离散数据，则称之为的插值函数。实用上，我们常取结构相对比较简单的代数多项式作为插值函数,这就是所谓的代数插值。设为给定的节点，，为相应的函数值，求一个次数不超过的多项式，使其满足，.这类问题称为插值问题。称为被插值函数，称为插值函数，称为插值节点01,nxxx)(iixfyni,1,0n)(xPnni,1,0()niiPxy一、问题提出01,nxxx()fx()nPx定理1设为给定的彼此互异的个插值节点，则存在唯一的次数不超过的多项式，满足条件,.nxxx10,1nn)(xPn()niiPxyni,1,0二、存在唯一性证明:设,其中为待定系数.利用插值条件,我们得到一个线性代数方程组,其中观察发现矩阵A是范德蒙矩阵,那么,由几代知识知道矩阵A的行列式为,由定理中条件,插值结点为彼此互异的,那么行列式不为零.故由Cramer法则知线性代数方程组存在唯一解.2012nnnPaaxaxax012,,,naaaa()niiPxyAab0011111nnnnnxxxxAxx0011,,nnayayabay0()()ijjinDetAxxAab三、Lagrange插值法011011()()()()(),0,1,()()()()iiniiiiiiinxxxxxxxxlxinxxxxxxxx0()()nniiiPxylx（1）Lagrange插值多项式可以表示为引入记号,易证,从而Lagrange插值多项式可表示为1'01()()()()nnniiinixPxyxxx)())(()()(1101niiiiiiinxxxxxxxxx)())(()(101ninxxxxxxx（2）插值误差估计定理2设在上连续，在内存在,节点，是拉格朗日插值多项式，则对任意,插值余项其中且依赖于.)()(xfn],[ba)()1(xfn),(babxxxan10)(xPn],[bax)()!1()()()()(1)1(xnfxPxfxRnnnn),(bax例2.求过点(2,0)(4,3)(6,5)(8,4)(10,1)的拉格朗日型插值多项式。解：用4次插值多项式对5个点插值001122334420436584101,,,,,,,,,,,,,,,xyxyxyxyxy0(4)(6)(8)(10)1()(4)(6)(8)(10)(24)(26)(28)(210)384xxxxlxxxxx1(2)(6)(8)(10)1()(2)(6)(8)(10)(42)(46)(48)(410)96xxxxlxxxxx2(2)(4)(8)(10)1()(2)(4)(8)(10)(62)(64)(68)(610)64xxxxlxxxxx3(2)(4)(6)(10)1()(2)(4)(6)(10)(82)(84)(86)(810)96xxxxlxxxxx4(2)(4)(6)(8)1()(2)(4)(6)(8)(102)(104)(106)(108)384xxxxlxxxxx40011223344()()()()()()Pxylxylxylxylxylx13(4)(6)(8)(10)(2)(6)(8)(10)3849654(2)(4)(8)(10)(2)(4)(6)(10)64961(2)(4)(6)(8)384xxxxxxxxxxxxxxxxxxxx于是有缺点:当增加或减少插值节点时,基函数需要重新构造,不便于实际的计算使用定义称为在两点处的一阶差商.（1）差商定义011201202[,][,][,,]fxxfxxfxxxxx()()[,],ijijijfxfxfxxijxx()fx四、Newton插值法,ijxx01112010[,][,,][,,]nnnnfxxxfxxxfxxxxx二阶差商n阶差商差商表一阶差商二阶差商三阶差商四阶差商kx0x1x2x3x4x()kfx0()fx2()fx1()fx3()fx4()fx01[,]fxx12[,]fxx23[,]fxx34[,]fxx012[,,]fxxx123[,,]fxxx234[,,]fxxx0123[,,,]fxxxx1234[,,,]fxxxx01234[,,,,]fxxxxx(2)Newton插值公式由差商定义把以上各式由后向前代入,可得[,]xab000()()[,]()fxfxfxxxx001011[,][,][,,]()fxxfxxfxxxxx010101[,,][,,][,,,]()nnnnfxxxfxxxfxxxxxx00100101()()[,]()[,,]()()nnnNxfxfxxxxfxxxxxxx010()()()[,,,]()()nnnnRxfxNxfxxxxxxxx例2:已知求满足以上插值条件的牛顿型插值多项式。解:12340-5-63一阶差商二阶差商三阶差商12340-5-63-5-19251xy()ifxix由上述差商表对角线上取得的值则牛顿三次插值多项式为00101201230,[,]5,[,,]2,[,,,]1,fxfxxfxxxfxxxx)2)(1(2)1(50)(xxxxNn)3)(2)(1(xxx343xx五、Hermite插值多项式给定的是节点上的函数值和导数值问题：已知iiyxf)(iiyxf)(1,0i求3次多项式，使得)(3xHiiyxH)(iiyxH)(1,0i120101010210101032121)(yxxxxxxxxyxxxxxxxxxH'120101'021010)()(yxxxxxxyxxxxxx*多项式插值的问题前面介绍了构造插值公式的方法，并分析了它们的余项。在实际应用插值函数作近似计算时，总希望插值公式余项的绝对值小一些，即使得逼近的精度好。从表达式看，似乎提高插值多项式的次数便可达到目的，但实际上并非如此。)(xR例如给定函数取其等距节点，构造的Lagrange插值多项式为当时，只能在内收敛，而在这个区间以外是发散的。这种畸形现象通常叫做Runge现象。如下图所示。3.63x1100,1,,ixinin21,55,1fxxx201()1nnijjpxlxxn()npx六、分段插值所谓分段插值，就是将被插值函数逐段多项式化。在每个子段上构造插值多项式，然后把它们装配在一，作为整个区间上的插值函数，即称为分段多项式。如果函数在每个子段上都是次式，则称为次式。1,iixx,abkSxkk一般（低次：k=1,2,3）（1）分段线性插值的构造（k=1)易知在每个子区间上是一次插值多项式分段线性插值的余项其中1[,](0,1,)iixxin2()()()8MhfxxRx()xmax''()axbMfx11111iiiiiiiiiixxxxxxxyxxxxyx,)(（2）分段抛物线插值（K=2）（3）分段三次Hermite插值(K=3)（4）三次样条插值在分段插值中，分段线性插值在节点上仅连续而不可导，分段三次埃尔米特插值有连续的一阶导数，如此光滑程度常不能满足物理问题的需要，而引入的样条函数则可以同时解决这两个问题,使插值函数既是低阶分段函数,又是光滑的函数。三次样条函数定义给定区间的一个划分，如果函数满足：ba,bxxxxann110)(xS（1）在每一小区间上是三次多项式；（2）在每个内节点上具有二阶连续导数；（3）iiyxS)(则称是在该区间上关于该划分的一个三次样条函数。)(xs)(xf其中四个待定系数为,子区间共有n个所以要确定S(x)需要4n个待定系数。另一方面,要求分段三次多项式S(x)及其导数和在整个插值区间a,b上连续,则要求它们在各个子区间的连接点上连续，即满足条件由样条函数的定义可知,三次样条插值函数S(x)是一个分段三次多项式,要求出S(x),在每个小区间xi,xi+1上要确定4个待定参数,若用Si(x)表示它在第i个子区间xi,xi+1上的表达式，则332210)(xaxaxaaxSiiiii1,,1,0ni3210,,,iiiiaaaa)(xS)(xS110,,,nxxx（1）插值条件（2）连接条件式共给出了4n-2个条件,而待定系数有4n个,因此还需要2个条件才能确定S(x),通常在区间端点上各加一个条件,称为边界条件,常用边界条件有三种类型。)()(iixfxSni,,1,0)0()0(1,,2,1)0()0()0()0(iiiiiixSxSnixSxSxSxSnxbxa,0第一种类型：给定两端点的一阶导数值：第二种类型：给定两端点f(x)的二阶导数值：作为特例,称为自然边界条件。满足自然边界条件的三次样条插值函数称为自然样条插值函数。第三种类型：当是以为周期的函数时，则要求S(x)也是周期函数,这时边界条件应满足当时，)()(),()(00nnxfxSxfxS)()(),()(00nnxfxSxfxS0)()(0nxSxS0xxn)()(0nxfxf)()(),()(00nnxSxSxSxS)(xf)(xf这样，由上给定的任一种边界条件加上插值条件和连接条件，就能得出4n个方程，可以惟一确定4n个系数。从而得到三次样条插值函数S(x)在各个子区间xi,xi+1上的表达式S(xi）(i=1,2,…,)。但是，这种做法当n较大时，计算工作很大，不便于实际应用。因此我们希望找到一种简单的构造方法。三次样条插值函数的求法设S(x)在节点xi处的二阶导数为因为在子区间xi-1,xi上是三次多项式,所以在此小区间上是x的线性函数,且因为用线性插值,可知其表达式为),,1,0()(niMxSii)()(xSxSi)(xSiiiiMxSMxS)(,)(11iixxx,11iiixxh1111)(iiiiiiiiixxxxMxxxxMxS记，则有iiiiiiihxxMhxxMxS11)(其中,Ai,Bi为积分常数,可利用插值条件确定,即要求Ai,Bi满足并记，则得)()(6)(6)()(13131iiiiiiiiiiixxBxxAhxxMhxxMxS)()(),()(11iiiixfxSxfxS)(61)(),(61)(21211iiiiiiiiiiiixfhBhMxSxfhAhMxSiiiiyxfyxf)(,)(112211611,611iiiiiiiiiihMyhBhMyhA连续两次积分得iiiiiiihxxMh