《插值法与数值微分》PPT课件

实际中，f(x)多样，复杂，通常只能观测到一些离散数据；或者f(x)过于复杂而难以运算。这时我们要用近似函数g(x)来逼近f(x)。这个过程就是曲线拟合。插值法在工程及建筑设计中应用十分广泛。例如，已知一天24小时的逐时室外气温、综合温度、冷热负荷等值，需要知道其他任意时刻的值，即可应用插值计算求得；又如，我国工业企业采取通风和空气调节设计规范中，仅给出了有限个地区相应有限个方位的夏季太阳辐射热总强度值，以及透过窗玻璃的太阳总辐射强度值，至于其它任意方位（0-350）的中间值，也要用插值法求得。因此，插值法的研究很有必要。自然地，希望g(x)通过所有的离散点x0 x1x2x3x4xg(x)f(x)本章学习插值法本章学习插值法1图2曲线拟合几何意义()nP x()yf x01,nax xxb01,nyyy()nP x()0,1,niiPxyin01,nx xx,a b()f x01,nx xxn若节点互不相同，则满足插值条件的 次多项式存在且唯一。（证略）2图2插值函数几何意义0 x1x2xnxxy已知函数 在结点 上的函数值 ，要求一个一次多项式 使之满足 ，其几何意义就是通过A，B两点作一条直线近似代替曲线 。()yf x01,xx01,yy1()P x100111(),()P xyP xy()f x优点：优点：计算简单，以直线代替曲线。缺点：缺点：精度低，误差大。改进：改进：多用一些点。由解析几何，我们立即可以得到的 表达式1()P x011010110()xxxxP xyyxxxx1()P xx 这样的 一般是 的一次多项式，即一次函数。这种插值称为线性插值（或一次插值）。130453020 P(30)2.86.54.282045452000202.8xy解：取，11456.5xy，并将其代入线性插值公式，有2x1x0 x0y1y2()P x2()0,1,2iiP xyi几何意义：通过三点A、B、C的抛物线代替曲线2y这样的 是 的二次函数，其形式为：2()P xx22012()P xaa xa x其中 为待定常数。012aaa，若将A，B，C三点分别代入上式会得到一个有唯一解的三元一次方程，从而 即可确定，但求起来比较麻烦。012aaa，0111)B)()yyyP x0因为点A(x，(x，满足方程，故可设2101()()()()P xP xa xxxx，即01201010110()()()xxxxP xyya xxxxxxxxa其中 为待定常数。2002112222()()()()P xyP xyP xyaP x由上式不难看出，。若再用条件，就可求出常数，从而求得的表达式。0201122012010210122021()()()()()()()()()()()()()x x x xx x x xx x x xP xyyyx x x xx x x xxx xx20100202012001011021()+()()yyyyxxxxxxxxP xyxxxxxxxxxx稍加整理即得抛物插值公式。解:用线形插值求解问题1）00111001012111xyxy取，；，可求得115 121115 100115101110.71428100 121121 100与所求平方根的实际值比较，得到了具有三位有效数字的结果10.71428。用抛物插值求解问题2）001122100101211114412xyxyxy取，；，；，可求得1744359011510111210.722755519244831012与平方根实际值比较，具有四位有效数字，显然比线形插值的结果好。一般地说，抛物插值比线形插值近似程度要好些。()yf x()0,1,iiyf xin()nP x()nP x()niiP xy0,1,in3.()ix插值基函数的特点，带入插值节点时有：1xn.每一项都是关于 的 次多项式；21n.每个多项式有项；1()0ijjijxx-xij，故，应该有一些(的连乘积，()0jijx ijx以保证对于任意的（），有，()ix且还应该有自己的系数。0()()()()nniiiiinn+1Pxx yx yPx所以估计有个节点的一般形式的代数插值多项式应形如：，只要求出的表达形式也就求出了。0000()(0,1,)n()()1()00,1,nijiP xy inxxxin为了构造满足要求的多项式，我们先来解决一个简单问题：求一个 次多项式，使之满足条件，从而可设0001()niixaxxa（，为待定常数。00()1x再由，可求得10011()()nniiiiaxxxx111()0()10,2,ixxinn同理可作出满足条件，的 次多项式为()1()00,1,1,1,iiijxxjiinn一般地可作出满足条件，的 次多项式为1110011()()()nniiiiiixxxxx100()()()nniijjjjj ij ixxxxx3.3.拉格朗日插值公式：拉格朗日插值公式：010,1,1()()()()0,1,nniiinnxxxP xyin取便得到个多项式，。以这些多项式为基础，容易看出要构造满足条件，的多项式，只需取00()nnjniijijj ixxP xyxx 这就是所要求的插值多项式，称为拉格朗日（拉格朗日（Lagrange）插值多项式插值多项式。当n=1时，就得出线形插值多项式线形插值多项式，n=2时，就得出抛物插值多项式抛物插值多项式。（1 1）流程图：）流程图：（2 2）算法功能：）算法功能：用Lagrange插值公式，对给定的n组 数据进行插值计算。（3 3）算法简介：）算法简介：121122,(),(),()nnnnx xxyf xyf xyf xxf(x)对给定的 个插值节点及其对应的函数值使用拉格朗日插值公式，计算在 点处对应的函数值。,11()()()nnikn kn kkikii kxxyf xy LxLxxx，其中，12,nnx xx个元素的一维实数组，存放给指定的插值节点。（5 5）程序使用说明）程序使用说明：12,nnyy个元素的一维实数组，存放与插值节点相对应的函数值y。n整型量，给定插值节点的个数。X实型量，插值点。输出参数：y 实型指针，接受调用程序传送的一个实型量的地址，在程序结束时，该实型量返回计算结果。注：注：该实型量中原有内容将被破坏。()()nP xf x用近似代替，存在误差。()()()()nnnR xf xP xP x记：，称为插值多项式的余项。2.2.误差估计：误差估计：01011,min(,)max(,()()()()1)!nnk=nn0nnfR xxnxxx-xxx xxx xx对于给定的插值点 有，其中()=（），是与 有关的点，它位于与之间。xx)()()()(),()()()()(xxpxfxtxtptftnn当 为节点时，两边皆为0，显然成立。下设 不为节点。作辅助函数即使在这些点之间存在一点依次类推使个点个点之间存在在这个点处使在这个点个点之间存在在这再按罗尔定理使个之间存在个点在故按罗尔定理显然,0)(,;0,1;0,1,0)()()(,1,2,0)()()()()1(10101010 nnnnnnnnnnnxxxxnxxxx0)()()()()1()1()1(nnnnxpf(1)(1)(),()0;()1,()(1)!nnnnp ttnptttntn注意为 的 次多项式 必有为 的次多项式 必有；可知上式可化为(1)()()()(1)!0()nnf xpxfnx111|()|()|()|(1)!nnnnfxmMRxxn根据余项公式，若能估计出的上界，那么将有即即 问题得证。问题得证。这个定理所讲的余项用起来有一定的困难，因为实际计算时，只是给出 的一张数据表，并未给出具体的解析式子，故 并不知道，所以 也就无法得到。()f x()f x1()nf12|()|()()()(),0nif xMx-xx-xx-xx-xxxx那么提供的上界 这项要求显然是不切实际。但此结论在理论上有它的一定价值。其价值在于给出了余项的表达式，可以观察到，余项里含有因子，故当插值点 离插值节点 比较远时，效果可能较差若点 位于插值区间内，插值过程称为内插否则成为外推，一般说来，外推比内插效果差。012011,()xx xxxf xz仅以三个插值节点的情形为例。我们先用作线性插值，求出的一个近似值，记为。011010110 xxxxzyyxxxx02xx然后取 和 再求得一个结果：022020220 xxxxzyyxxxx1101()()()()2!ff xzxxxx2202()()()()2!ff xzxxxx2()()fxff1假定在插值区间内改变不大，将上面两个式子相除。消去近似相等的(与，结果有1122()()f xzxxf xzxx111212()()xxf xzzzxx()()nP xf x插值函数和函数的误差可以通过两个插值函数之差来估计。这种用计算的结果来估计误差的办法，通常称为事后估计，在计算中是常用的，这种估计误差的方法，将贯穿我们计算方法这门课程的始终。0101()xxxf xe令，写出的一次插值多项式，并估计插例：值误差。10101(0)1,(1)xxffe解：记，；01()xf xexx则以，为插值节点的一次插值多项式为1101101011010()11(1)0 11 0 xxxxxxP xyyeexxxxx ()()xxfxefxe 因为，所以误差为1111()()(0)(1)822411R xfxxx 11,)251(1)(2xxxf取等矩节点 ，作拉格朗日插值多项式 。当 时，函数 及插值多项式 的图形如下所示。由图可见，在区间，0.2上 比较接近 ,但在区间-1，1两端则误差很大。当 增大时，部分区间上插值多项式截断误差偏大的现象更重。这种现象称龙格现象龙格现象。),1,0(/21ninixi()nP x10n)(xfy 10()yPx10()Px)(xfn-11xy0龙格现象7n解决方法：分段插值01nxxxn应用低阶插值的关键是恰当地挑选插值结点。余项公式说明，选取的结点 离插值点 越近，误差 就越小，因而插值效果也就越好。因此，应当尽量在插值点的邻近选取插值结点。kxx|nR2.分段插值：把整个插值区间分成若干个小区间，在每 个小区间上进行低次插值。以三个节点为例，公式为：11111111111111()()()()()()()()()()()()iiiiiiiiiiiiiiiiiiiiixxxxxxxxy=yyxxxxxxxxxxxxyxxxx1x0 x0y1ynynx01nxxxixxf(x)若计算处的近似值1111,i-1iiiiixxxxxxx（）选取节点与，使，然后在小区间上作线性插值。11111()()iiiiiiiixxxxf xP xyyxxxx称为分段线性插值-4-3-2-101234-1-0.8-0.6-0.4-0.200.20.40.60.81112iiixxxx（）选取距点 最近的三个节点，作二次插值11211()()()iijkk ij ikjj kxxf xP xyxx 称为分段抛物插值，其节点的选取方法为：011111111|12,3,2kkkkkkkknnxxxkxxxxxxxikxxxxxxxnxxxkn，且，且。011,nxxx01,nxxx且1()()(),1,niniiNxNxf xin110()()()nnnqxaxxxx同样01 ()()()nnnqxaxxxx1()()()nnnNxNxqx承袭性承袭性：11()()()nnnNxNxqx1nP为实数01001 ()()()()nnnNxaa xxa xxxx而且有：0001011012012022021201001()()()()()()()()()()()()()()()nnnnnnnnnnnN xaf xN xaa xxf xN xaa xxa xxxxf xN xaa xxa xxxxf x这样：00()af x10110()()f xf xaxx20212120()()1f xf xaaxxxx30312323010()()11f xf xaaaxxxxxx10011010100()(),kkkkf xf xf x xxxf xxf xxf xxxx称为k阶差商称为1阶差商定义：差商差商00()af x1010110()(),f xf xaf x xxx20212120201021021()()11 ,f xf xaaxxxxf x xf x xf x x xxx由归纳：0,nnaf xx此处用到差商的一个性质：（用归纳法易证）对称性：00,kkiif xxf xx定义关键：找不同的元素相减作分母0,0,kiik是的任意排列00,()xf x11,()xf x22,()xf x,()nnxf x01,f x x21,f x x1,nnf xx210,f x x x12,nnnf xxx0,nf xx1、先构造差商表2点Newton型插值1010010()()()()()f xf xN xf xxxxx2、利用差商表的最外一行，构造插值多项式0010001()(),(),()()nnnNxf xf x xxxf xxxxxx00011 ()()(),()()()()nnnniniiiiiiinNxL xxf xf xxxxxxxxxx的系数一样性质2误差00100100 Newton()()(),()()()()()(),()()niinniinnnnnnnnxNxxaNtN tf xx a txtxNaf af aN af xx a axax另一方面设插值为则有为显然10(),(1)!nnffxxan性质310()()()()()(1)!nnnnfN xR xxxxxn同样的误差为00011(),()()()()niniiiiiiinf xf xxxxxxxxxx00,nniif xxf xx0(),()!nnff xxn0,()(),0,nnka knf xPxf xxkn推论：若什么是样条什么是样条:是 指飞机或轮船等的制造过程中为描绘出光滑的外形曲线(放样)所用的工具样条本质上是一段一段的三次多项式拼合而成的曲线在拼接处,不仅函数是连续的,且一阶和二阶导数也是连续的1946年,Schoenberg将样条引入数学,即所谓的样条函数一、三次样条插值函数定义1.01,nax xxba b为区间的一个分割(),:S xa b如果函数在区间上满足条件(1)(),(),(),S x S x Sxa b都在区间上连续1(2)(),kkS xxx在每个小区间上都是三次多项式(),S xa b则称为区间上的三次样条函数01(3)(),nf xx xx如果函数在节点处的函数值为(),0,1,jjf xyjn()S x而三次样条函数满足(),0,1,jjS xyjn()(),S xf xa b则称为在上的三次样条插值函数-(1)二、三次样条插值多项式01(),nf xx xx如果函数在节点处的函数值为(),0,1,jjf xyjn01,nax xxba b为区间的一个分割()(),S xf x如果是的三次样条插值函数 则其必满足(),1jjS xyjk klim()(),1,1jjjxxS xS xmjnlim()(),1,1jjxxSxSxjnlim()(),1,1jjjxxS xS xyjn-(2)()(42)S xn要满足上述四组 共个 条件(),S xa b在上必然是分段函数 即00111211(),(),(),nnnSxxx xS xxx xSxxxx()S x1(),(),kkkSxxx是上的 两点 三次样条插值多项式 满足()kjjSxy1lim()lim()kkkkxxxxSxSx1lim()lim()kkkkxxxxSxSx1lim()lim()kkkkxxxxSxSx1,2,1kn42n共个条件,1jk k-(3)-(4)1(),4kkkSxxx是上的三次样条插值多项式 应有 个待定的系数()4S xn即要确定必须确定个待定的系数少两个条件少两个条件并且我们不能只对插值函数在中间节点的状态进行限制也要对插值多项式在两端点的状态加以要求也就是所谓的边界条件:第一类(一阶)边界条件:00()S xf()nnS xf第二类(二阶)边界条件00()Sxf()nnS xf第三类(周期)边界条件0()()01lim()lim()nppnxxxxSxSx1,2p-(5)-(6)-(7)加上任何一类边界条件(至少两个)后()44S xnn确定必须确定个待定的系数的条件正好也是个一般使用第一、二类边界条件,即()kjjSxy1lim()lim()kkkkxxxxSxSx1lim()lim()kkkkkxxxxSxSxm1lim()lim()kkkkxxxxSxSx1,2,1kn0,1,jn1,2,1kn1,2,1kn00()S xf()nnS xf-(8)00()Sxf()nnS xf或常用第二类边界条件(),0,1,jjS xmjn设1(),()kkkf xxxSx逐个求在小区间上的三次插值多项式1(),kkkSxx xHermite将表示为上的两点三次插值多项式()kSx()()()()()3011011()()()()()kkkkkkkkkHxyxyxmxmx11112kkkkxxyxx21kkkxxxxkkmxx211kkkxxxx21kkkxxxx11kkmxx112kkkkxxyxx211kkkxxxx-(9)2132()()()kkkkkkhxxSxxxyh21132()()kkkkkhxxxxyh212()()kkkkxxxxmh2112()()kkkkxxxxmh加以整理后可得(),kSx对求二阶导数 并整理后得1136(2)()()kkkkkkxxxSxyyh12624kkkkxxxmh112642kkkkxxxmh-(10)-(11)10,1,1kkkhxxkn令，1lim()lim()kkkkxxxxSxSx1,2,1kn由条件lim()kkxxSx126()kkkyyh4kkmh12kkmh1lim()kkxxSx1216()kkkyyh112kkmh14kkmh由于以上两式相等,得111111112()kkkkkkkmmmhhhh112213()kkkkkkyyyyhh1,1kn1,1nn共个个方程个未知量111,kkhh用除上式的两边 并加以整理 得112kkkkkmmmkg1kkkkhhh11kkkkhhh1113()kkkkkkkkkyyyyghh1,1kn-(12)1,1kn1,1nn共个个方程个未知量(12)式称为基本方程组如果问题要求满足第一类(一阶)边界条件:00()S xf()nnS xf-(5)00mf nnmf-(5)基本方程组(12)化为n-1阶方程组1121102mmgf112kkkkkkmmmg2,3,2kn121112nnnnnnmmgf-(13)即将(13)式化为矩阵形式122334221222222nnn12321nnmmmmm11023211nnnngfggggf-(14)这是一个三对角方程组如果问题要求满足第二类(二阶自然)边界条件:00()Sxf()nnSxf-(6)00nff 时，称为自然边界条件由(11)式,可知0100010306(2)()()xxxSxyyh001020624xxxmh001120642xxxmh10206()yyh004mh102mh0f 11216()()nnnnnSxyyh 112nnmh14nnmhnf-(15)-(16)011(15)(16),nnm m mm式是关于的方程 整理后得1000100232yyhmmfh1111232nnnnnnnyyhmmfh0gng-(17)-(18)与基本方程组(12)联合,并化为矩阵形式,得112231121222212nn0121nnmmmmm0121nnggggg-(19)(19)式与(14)一样,都是三对角方程组,并且都严格对角占优可以使用追赶法求解,并且解是唯一的对于问题要求满足第三类(周期)边界条件请同学们自己思考现在回到(10)式01(14)(19),nm mm通过或式 解出后01,(10)nm mm将代入式011(),(),()()nSx S xSxS x便可得到从而得到三次样条插值函数例1.对于给定的节点及函数值01231245()1342kkkxf x0()()0(),(3)nSxSxS xf求满足自然边界条件的三次样条插值函数并求的近似值解:由(12)式可得1232131132231kkkkhhh11kkkkhhh1k 192g 272g 06g 36g 212/321/31/322/3120123mmmm0123gggg由(19)式得基本方程组0123177519,8448mmmm 解方程组得：将上述结果代入(10)式1113()kkkkkkkkkyyyyghh10000032yyhgfh11132nnnnnnyyhgfh320137()112884Sxxxxx 321137()124884S xxxxx 322345103()3345884Sxxxxx32137112884xxxx32137124884xxxx323451033345884xxxx()S x17(3)(3)4fS课后练习：课后练习：21 5,51yxx 使用不同的插值方法于函数