1、第一章第一章 曲线插值与曲线拟合曲线插值与曲线拟合刘云华121 引言引言2 拉格朗日插值多项式拉格朗日插值多项式3 分段低次拉格朗日插值分段低次拉格朗日插值4 Neville逐步插值方法逐步插值方法5 Newton插值插值6 Hermite插值和分段三次插值和分段三次Hermite插值插值7 曲线拟合曲线拟合 实际中,f(x)多样,复杂,通常只能观测到一些离散数据;或者f(x)过于复杂而难以运算。这时我们要用近似函数g(x)来逼近f(x)。自然地,希望g(x)通过所有的离散点 概念x0 x1x2x3x4xg(x)f(x)定义:为定义在区间 上的函数,为区间上n+1个互不 相同的点,为给定的某一
2、函数类。求 上的函数 满足)(xfba,0niix)(xgnixfxgii,0 ,)()(问题l是否存在唯一l如何构造l误差估计0000()()()()()()()nniiinnig xaxaxg xfxaxax设则00011000001111110011()()()()()()()()()()()()nnnnnnnnnnaxaxaxf xaxaxaxf xaxaxaxf x所以 有解,当且仅当系数行列式不为系数行列式不为00 niia存在唯一定理定理1.1:为n1个节点,n+1维空间,则插值函数存在唯一,当且仅当 0niix,10nspan0)()()()(0000nnnnxxxx1.与基函
3、数无关2.与原函数f(x)无关3.基函数个数与点个数相同特点:特点:,1)(2nnxxxspanx对应于对应于则则01100nijjinnnxxxxVandermonde行列式多项式插值的Lagrange型 如何找?在基函数上下功夫,取基函数为nniixl 0)(要求jijixlijji,1,0)(则)()()(0iniixfxlxg求niixl0)(,易知:)()()()(110niiiixxxxxxxxaxl)()()(1110niiiiiiixxxxxxxxa011011()()()()()()()()iiniiiiiiinxxxxxxxxlxxxxxxxx0()()nniixxx记()
4、()()()niniixlxxxxl线性插值01011010)(,)(xxxxxlxxxxxl)()()()()(11001xlxfxlxfxL12 xLy1 xfy x0 x0 x1),00(yx),11(yxy图图2-2 二次插值1200102()()()()()xxxxlxxxxx2001122()()()()()()()L xf x lxf x l xf x lx0211012()()()()()xxxxl xxxxx0122021()()()()()xxxxlxxxxx14这是一个二次函数,用二次函数 近似代替函数 ,在几何上就是通过曲线 上的三点 ,作一抛物线 近似地代替曲线 (图
5、图2-3),故三点插值三点插值(二次插二次插值值)。)(2xL)(xf)(xfy)(xfy),(),(),(221100yxyxyx)(2xLy 图图2-3 xLy2 xfy),11(yx),00(yxyxx0 x10),22(yx)3,3(),1,2(),0,0(),2,1(例:)31)(21)(01()3)(2)(0()(0 xxxxl)23)(03)(13()2)(0)(1()(3xxxxl)32)(02)(12()3)(0)(1()(2xxxxl)30)(20)(10()3)(2)(1()(1xxxxl)(3)(1)(0)(2)(3210 xlxlxlxlxg16例例 已知 分别用线性
6、插值和抛物插值求 的值。解解 因为115在100和121之间,故取节点x0=100,x1=121相应地有 y0=10,y1=11 故用线性插值求得的近似值为714.10100121100115*11121100121115*10)115(1151L100121100*11121100121*10)(1xxxL 12144,11121,1010011517723.10)121144)(100144()121115)(100115(*12)144121)(100121()144115)(100115(*11)144100)(121100()144115)(121115(*10)115(1152 L
7、115仿上,用抛物插值公式所求得的近似值为将所得结果与 的精确值10.7328相比较,可以看出抛物插值的精确度较好。为了便于上机计算,我们常将拉格朗日插值多项式改写成对称形式nknkjjjkjknxxxxyxL00)()(xLn算法:fx=0.0for(i=0;i=n;i+)tmp=1.0;for(j=0;ji;j+)tmp=tmp*(x-xj)/(xi-xj);for(j=i+1;j=n;j+)tmp=tmp*(x-xj)/(xi-xj);fx=fx+tmp*yi;return fx;011011()()()()()()()()iiniiiiiiinxxxxxxxxlxxxxxxxxLab0
8、2 Lagrange插值21(),5,51f xxx 55max()()max()(),5,0,10010iiixiif xp xf yp yyi 对函数构造插值,并求插值节点取为:105,0,1,ixi iNN (1)215cos,0,1,22iixiNN(2)对N=5,10,20,40比较以上两组节点的结果。Chebyshev点误差)()()(xLxfxRnn解:)()()(,0 ,0)(,0 ,)()(0nnininixxxxxkxRnixRnixLxf求?)(xk0)(and ,0,0)()()()()()(?)(,0anixxtxtaktLtftakainn设易知)(t有n+2个零点
9、)!1()()()!1)()()(0)(,)1()1()1()1(nfaknakfnnnn)()()!1()()(0)1(nnnxxxxnfxR由a的任意性例:例:已知已知233sin,214sin,216sin 分别利用分别利用 sin x 的的1次、次、2次次 Lagrange 插值计算插值计算 sin 50 并估计误差。并估计误差。解:解:0 x1x2x185500 n=1分别利用分别利用x0,x1 以及以及 x1,x2 计算计算4,610 xx利用利用216/4/6/214/6/4/)(1 xxxL这里这里)3,6(,sin)(,sin)()2(xxxfxxf而而)4)(6(!2)()
10、(,23sin21)2(1 xxfxRxx00762.0)185(01319.01 Rsin 50 =0.7660444)185(50sin10 L0.77614外推外推/*extrapolation*/的实际误差的实际误差 0.010010.010013,421 xx利用利用sin 50 0.76008,00660.018500538.01 R内插内插/*interpolation*/的实际误差的实际误差 0.005960.00596内插通常优于外推。选择内插通常优于外推。选择要计算的要计算的 x 所在的区间的所在的区间的端点,插值效果较好。端点,插值效果较好。n=223)()(21)()(
11、21)()()(4363463464363646342 xxxxxxxL)185(50sin20 L0.7654323cos21;)3)(4)(6(!3cos)(2 xxxxxxR 00077.018500044.02 Rsin 50 =0.76604442次插值的实际误差次插值的实际误差 0.000610.00061高次插值通常优于高次插值通常优于低次插值低次插值例子 P14P1726 4 分段低次插值分段低次插值 例2、例4表明,适当地提高插值多项式的次数,有可能提高计算结果的准确程度。但是决不可由此提出结论,认为插值多项式的次数越高越好。例如,对函数 先以 为节点作五次插值多项式P5(x
12、),再以 为节点作十次插值多项式P10(x),并将曲线 描绘在同一坐标系中,如图图2-52-5所示。)10,1,0(511iixi)11(2511)(2xxxf)5,1,0(521iixi)1,1)(),(,2511)(1052xxPyxPyxxf27 -1 0 1 x y 1y=1/(1+25x2)y=P5(x)图图2-52-5y=P10(x)28 这种分段低次插值叫分段线性插值分段线性插值。在几何上就是用折线代替曲线,如图图2-6所示。故分段线性插值又称折线插值折线插值.11111)()(iiiiiiiixxxxyxxxxyxPxf xy=f(x)yox0 x1xnx2图2-629 类似地
13、,为求 的近似值,也可选取距点 最近的三个节点 进行二次插值,即取这种分段低次插值叫分段二次插值分段二次插值。在几何上就是用分段抛物线代替曲线,故分段二次插值又称分段抛物插值分段抛物插值。为了保证 是距点 最近的三个节点,(4.2)中的 可通过下面方法确定:)(xfyx11,iiixxx)()()(11112ikjijjkjiikkxxxxyxPxf(4.2)11,iiixxxxixxxxnxxxxxjxxxxinnnjjjj1211210211212121130Neville逐步插值方法逐步插值方法通过两点插值逐步生成多点插值的方法两点插值31三点插值:由两个两点插值(x0,y0)(x1,y
14、1)与(x1,y1)(x2,y2)32多点Neville插值22Hermite插值在节点处已知函数值和导数值两点三次两点三次Hermite插值两点三次两点三次Hermite插值误差分析例子 P26p29三次样条插值 分段低阶插值,收敛性好,但光滑性不够理想。在工业设计中,对曲线光滑性要求高,如:流线型 设想这样一曲线:插值,次数不高于3次,整个曲线2阶连续导数,称为三次样条函数插值。每个小区间不高于3次,,)(123iiiiiiixxxdxcxbxaxS1,0ni有4n个未知数,我们的已知条件如下:(0)(0)(0)(0)(0)(0)()()iiiiiiiiS xS xS xS xSxSxS
15、xf x1,1nini,0 1,1ni1,1ni共3n-3+n+1=4n-2个条件给定端点弯距值给定端点转角值58曲线拟合的最小二乘法曲线拟合的最小二乘法 1 引引 言言 2 什么是最小二乘法什么是最小二乘法 3 最小二乘解的求法 59曲线拟合的最小二乘法曲线拟合的最小二乘法 1 引引 言言 在科学实验和生产实践中,经常要从一组实验数据 出发,寻求函数y=f(x)的一个近似表达式y=(x)(称为经验公式)。从几何上,就是希望根据给出的m个点 ,求曲线 y=f(x)的一条近似曲线 y=(x)。因此,这是一个曲线拟合的问题。多项式插值虽然在一定程度上解决了由函数表求函数的近似表达式问题,但用它来解
16、决这里提出的问题,有明显缺陷。首先,实验提供的数据通常带有测试误差。如要求近似曲线y=(x)严格地通过所给的每个数据点 ,就会使曲线保持原有的测试误差。当个别数据的误差较大时,插值效果显然是不理想的。其次,由实验提供的数据往往较多(即m较大),用插值法得到的近似表达式,明显地缺乏实用价值。),2,1)(,(miyxii),(yxii),(yxii60因此,怎样从给定的一组数据出发,在某个函数类中寻求一个“最好”的函数(x)来拟合这组数据,是一个值得讨论的问题。随着拟合效果“好”、“坏”标准的不同,解决此类问题的方法也不同。这里介绍一种最常用的曲线拟合方法,即最小二乘法。2 什么是最小二乘法什么
17、是最小二乘法 如前所述,在一般情况下,我们不能要求近似曲线 y=f(x)严格地通过所有数据点 ,亦即不能要求所有拟合曲线函数在 xi 处的偏差(亦称残差)都严格地趋于零。但是,为了使近似曲线尽量反映所给数据点的变化趋势,要求 i 都较小还是需要的。达到这一目标的途径很多,常见的有:(1)选取(x),使偏差绝对值之和最小,即),(yxiimin)(11miiimiiyx),2,1()(miyxiii(2.1)61 (2)选取(x),使偏差最大绝对值最小,即 (2.2)(3)选取(x),使偏差平方和最小,即 (2.3)为了方便计算、分析与应用,我们较多地根据“偏差平方和最小偏差平方和最小”的原则(
18、称为最小二乘原则最小二乘原则)来选取拟合曲线y=(x)按最小二乘原则选择拟合曲线的方法,称为 最小二乘法最小二乘法。本章要着重讨论的线性最小二乘问题,其基本提法是:对于给定数据表 x x1 x2 xm y y1 y2 ym min)(maxmax11iimiimiyxmin)(2112imiimiiyx62要求在某个函数类 (其中nm)中寻求一个函数 (2.4)使*(x)满足条件 (2.5)式中 是函数类 中任一函数。满足关系式(2.5)的函数 ,称为上述最小二乘问题的最小二最小二乘解乘解。由上可知,用最小二乘法解决实际问题包含两个基本环节两个基本环节:先根据所给数据点的变化趋势与问题的实际背
19、景确定函数类 ,即确定所具有的形式;然后按最小二乘法原则(2.3)求取最小二乘解 ,即确定其系数 。)(,),(),(10 xxxn)()()()(*1*1xaxaxaxnno)()()()(1100 xxxxnnaaa)(x)(x)(x),1,0(*nkakmiiimixiiyxyx121)(2*)(min)(63 3 最小二乘解的求法最小二乘解的求法 由最小二乘解(2.4)应满足条件(2.5)知,点 是多元函数的极小点,从而 满足方程组 即),(*1*0naaa2110)(),(minokiikknyxaaaaS*1*0,naaa0kaS),2,1,0(nk0)(.)()()(11001i
20、inniimiikyxaxaxax64亦即 若对任意的函数h(x)和g(x),引入记号 则上述方程组可以表示成 写成矩阵形式即 imiikinmiiknimiikmiiikyxxxaxxaxxa)()()(.)()()()(11111100miiixgxhgh1)()(),(),1,0)(,(),(.),(),(1100nkfaaaknknkk),(),(),(),(.),(.),(.),(.),(),(),(.),(),(101010111010 1000fffaaannnnnnnn(3.1)(3.2)65 方程组(3.2)称为法方程组法方程组。当 线性无关时,可以证明它有唯一解并且相应的函
21、数(2.4)就是满足条件(2.5)的最小二乘解。综上分析可得 定理定理1 对任意给定的一组实验数据 (其中 互异),在函数类 (线性无关)中,存在唯一的函数使得关系式(2.5)成立,并且其系数 可以通过解方程组(3.2)得到。作为曲线拟合的一种常用的情况,若讨论的是代数多项式拟合,即取 则由(3.1)知)(),.,(),(10 xxxn*11*00,.,nnaaaaaa),2,1)(,(miyxiiix)()(),.(),(10mnxxxnn,.,10)(.)()(*1*10*0*xaxaxann),.,1,0(*niainnxxxxx)(,.,)(,1)(1066故相应的法方程组为 nkjx
22、xxmikjimikijikj,1,0,),(11),1,0(),(1nkyxfmiikikmiinimiiimiinminiminiminiminimiimiiminimiiyxyxyaaaxxxxxxxxm11110121111112111.(3.3)67例例 1 某种铝合金的含铝量为 ,其熔解温度为 c,由实验测得 与 的数据如表表3-1左边三列。使用最小二乘法建立 与 之间的 经验公式。解解 根据前面的讨论,解决问题的过程如下:(1)将表中给出的数据点 描绘在坐标纸上,如图图3-1所示。(2)确定拟合曲线的形式。由图图3-1可以看出,六个点位于一条 直线的附近,故可以选用线性函数(直线
23、)来拟合这组实验 数据,即令180图 3-1y30026022030507090 xy0)6,2,1)(,(iyxii%xxxyy68 其中a,b为待定常数。(3)建立法方程组。由于问题归结为一次多项式拟合问题,故由 (3.3)知,相应的法方程组形如 经过计算(表表3-1)即得确定待定系数a,b的法方程组 (4)解法方程(3.5)得 a=95.3524 ,b=2.2337 代入(3.4)即得经验公式 y=95.3524+2.2337xbxax)(616161261616iiiiiiiiiiiyxybaxxx3.10117628.283656.39614589.3966baba(3.4)(3.5
24、)(3.6)69 yxiixiyixi2 i 136.91811361.616678.9 246.71972180.899199.9 363.72354057.6914969.5 477.82706052.8421006.0 584.02837056.0023772.0 687.52927656.2525550.0396.6145828365.28101176.3表表 3-170 所得经验公式能否较好地反映客观规律,还需通过实践来检验.由(3.6)式算出的函数值(称为拟合值拟合值)与实际值有一定的偏差。由表3-2可以看出,偏差的平方和平方和 ,其平方根(称为均方误差均方误差)在一定程度上反映了
25、所得经验公式的好坏。同时,由表表3-2还可以看出,最大偏差最大偏差 .如果认为这样的误差都允许的话,就可以用经验公式(3.6)来计算含铝量在36.987.5%之间的溶解度。否则,就要用改变函数类型或者增加实验数据等方法来建立新的经验公式。例例 2 在某化学放应里,测得生成物的浓度y%与时间t的数据表见表表3-3,是用最小二乘法建立t与y的经验公式。解解 将已知数据点 描述在坐标纸上,见图图3-2。由图3-2 及问题的物理背景可以看出,拟合曲线 应具下列特点:),2,1(2337.23524.95mixyii6704.26612ii164.52i22.3max61ii)16,2,1)(,(iyt
26、ii)(xy71i12345636.946.763.777.884.087.5177.78199.67237.64269.13282.98290.80181197235270283292-3.222.672.64-0.87-0.02-1.2010.377.136.970.760.00041.4426.6704xiyiyiyyiii2i2i表表 3-272 t12345678y4.006.408.008.809.229.509.709.86t910111213141516y10.0010.2010.3210.4210.5010.5510.5810.60表表 3-3 (1)曲线随着t的增加而上升,
27、但上升速度由快到慢。y10504812t16图图 3-273(2)当t=0时,反应还未开始,即y=0;当 时,y趋于某一常数.故曲线应通过原点(或者当t=0时以原点为极限点),且有一条水平 渐近线。具有上述特点的曲线很多。选用不同的数学模型,可以获得不同的拟合曲线与经验公式。下面提供两种方案:方案方案1:设想 是双曲线型的,并且具有下面的形式 (3.7)此时,若直接按最小二乘法原则去确定参数a和b,则问题 归结为求二元函数 的极小点,这将导致求解非线性方程组非线性方程组:t)(tybatty2161)(),(iiiiybattbaS(3.8)740)()(20)()(2161216122iii
28、iiiiiiiiiybattbattaSybattbattaS给计算带来了麻烦。可通过变量替换来将它转化为关于待定参数的线.性形函数。为此,将(3.7)改写成于是,若引入新变量则(3.7)式就是tbay1ttyy1,1)1()1()1()1(btay75同时,由题中所给数据 表表3-3可以算出新的数据表表表3-4这样,问题就归结为:根据数据表表3-4,求形如 的最小二乘解.参照例1的做法,解方程组)1()1(btayi123161.000000.500000.333330.062500.250000.156250.125000.09434ttii1)1(yyii1)1(161)1()1(161
29、)1(1612)1(161)1(161)1()(16iiiiiiiiiiiytybattt表表 3-476既得 a=80.6621,b=161.6822代入(3.7),既得经验公式 (3.9)方案方案2:设想 具有指数形式 为了求参数a和b 时,避免求解一个非线形方程组,对上式两边取对数 此时,若引入新变量 并记A=lna,B=b,则上式就是 6822.1616621.80tty)(ty)0,0(/baaeytbtbay lnlnttyy1,ln)2()2()2()2(BtAy(3.10)77又由数 表表3-3可算出新的数据表表3-5。表表 3-5于是将问题归为:根据数据表表3-5,求形如 的最小二乘解。参照方案1,写出相应的法方程组并解之,即得 A=-4.4807,B=-1.0567于是i123161.000000.500000.333330.062501.386291.856302.079442.36085ttii1)2(yyiiln)2(tyBA)2()2(0567.1011325.0BbaeA,小结 线形拟合 二次多项式拟合 指数曲线拟合 幂函数拟合 双曲函数拟合