第四章2分段插值和数据拟合

1、第第4章章 数据近似数据近似4.2 分段插值分段插值 将整个区间划分为多个小区间 连结相邻两区间的点称为节点用相对少的数据点进行插值,可以使误差较小u 随着插值点数的增加,插值多项式的误差增加u ,在每个小区间上得到插值多项式再将得到的插值多项式连接在一起,形成整个区间上的一条连续曲线称为分段多项式第第4章章 数据近似数据近似4.2 分段插值分段插值 在每一个区间上使用一次多项式作为插值多项式,即每段为一条直线,此插值方法称为分段线性插值.4.2.1 分段线性插值分段线性插值012-1., , ,niiaxxxxba bnxixx 设则节点把分成 个小区间 当插值点在第 个小区间上时11-11

2、11 ( ),1,2,.,iiiiiiiiiiiLagrangexxxxgxyy xxx inxxxx采用一次插值多项式 111 ( ),(),1,2,.,iiiiiiiNewtongxyy xxxxxxx in 采用插值多项式第第4章章 数据近似数据近似4.2 分段插值分段插值分段线性插值的误差4.2.1 分段线性插值分段线性插值12,max( )iiixx xMy x 式中 1max ()()iixxxxx2,211()()8iiiiME gxx因此10121222,11 ( )( )( ) , ,1 ()8maxmax( ) ,max()3.3niiiiia x bi ng xaxxxb

3、y xy xa bE gMMMy xxx 设是在上插值的分段线性插值多项式若在上连续 则有误差估计其中 定理2,11 ()()()2iiiiME gxxxx211()4iixx2,28iM第第4章章 数据近似数据近似4.2 分段插值分段插值 分段线性插值比用多项式插值优越4.2.1 分段线性插值分段线性插值 缺点是插值出的曲线整体上的光滑程度较差,同时可以保证插值的准确度,随着n的增大,误差会越来越小并且计算量较少第第4章章 数据近似数据近似4.2 分段插值分段插值4.2.2 分段二次插值分段二次插值2-112-1-111 , ,( ),( )(,),( ,),(,)(1,3,., -1)ii

4、iiiiiiiia bgxxxgxxyx yxyin 若将区间分成偶数个子区间 在每相邻的两个子区间上作二次插值多项式即在子区间上是以为插值点的插值多项式Newton形式余项为21-11-111( ),(),()()iiiiiiiiiigxyy xxxxy xx xxxxx2 ( )-( )iy xgx11( )()()()3!iiiiyxxxxxx111 ,iiiiixx xxx第第4章章 数据近似数据近似4.2 分段插值分段插值4.2.2 分段二次插值分段二次插值201332311( ) , ()( ).( ) , , ()12 max( ) ,max()iniiia x bi ngxa

5、b axxxby xyxa bME gMyxxx 设是在区间上的插值的分段二次插值多项式若在上连续 则有误定理3.差计4估式中 证明:2111, ()()4iiiixxxxxxx当时3111()()()2iiixxxxxx 31111 ,()()()2iiiiixx xxxxxxx同理,当时 332() 12ME g因此,证毕211( ) ( )-( )()()(),3!iiiiiyy xgxxxxxxx由余项知3211 () ()()()6iiiME gxxxxxx1()ixx2 第第4章章 数据近似数据近似4.2 分段插值分段插值4.2.2 分段二次插值分段二次插值 分段二次插值具有分段一

6、次插值的同样优点,即当节点增多使子区间长度减少时,分段二次插值的误差也随之减小 缺点是插值出的曲线整体上的光滑程度仍较差第第4章章 数据近似数据近似4.2 分段插值分段插值4.2.3 三次样条插值三次样条插值第第4章章 数据近似数据近似4.2 分段插值分段插值4.2.3 三次样条插值三次样条插值-1 ,iiix xx 在每一个子区间上是一个三次多项式 这些多项式的曲线在节点 处 光滑 地连接起来 这样的分段三次多项式称为三次样条函数( ,) (0,1,2,., )iix yin 通过数据点 ( )s x的三次样条是满足插值条件( ),0,1,2,.,iis xyin 02( ) nxxs xd

7、x并使 达到最小的分段多项式0()()0ns xs x 满足条件的三次样条函数称为自然三次样条 自然三次样条是插值所有数据点的最光滑的函数第第4章章 数据近似数据近似4.2 分段插值分段插值3.2.3 三次样条插值三次样条插值f(x)H(x)S(x)注：注：三次样条与分段三次样条与分段 Hermite 插值的根本区别在于插值的根本区别在于S(x)自自身光滑身光滑，不需要知道，不需要知道 f 的导数值（除了在的导数值（除了在2个端点可能需个端点可能需要）；而要）；而 Hermite 插值依赖于插值依赖于f 在所有插值点的导数值。在所有插值点的导数值。定义定义 设设 a x0 x1 xn b, s

8、(x) C2a,b, 且在每个且在每个 xi , xi+1 上为上为。若它同时还满足。若它同时还满足s(xi ) f (xi )，i 0,1,n. 则则 s 称为称为 f 的的(cubic spline interpolant).第第4章章 数据近似数据近似4.2 分段插值分段插值4.2.3 三次样条插值三次样条插值( )s x计算三次样条函数-132( ),( )iiiiiiis xxxs xa xbxc xd 三次样条函数在每个小区间上求函数 ,其二阶导数必定为一次多项式( )iiiMxs x记为在 处的二阶导数值1iixx,则在区间, 上,有-1-1-( )iiiiiiixxx xs x

9、MMhh1iiihxx其中,将上式积分两次，依次得( )is x由于是三次多项式33-1-1-( )( )66iiiiiiixxx xs xMMxhh22-1-1-( )-22iiiiiiiixxx xs xMMchh第第4章章 数据近似数据近似4.2 分段插值分段插值4.2.3 三次样条插值三次样条插值( ),x由于是一次多项式 因此可以设为112( )iiiixxxxxcchh ( )iiis xy由插值条件得到3126iiiiiihxxMchh226iihMc33-1-1- ( )66iiiiiiiiixxxxMMxhh226iiihcyM2-11111,(),6iiiiiihs xyc

10、yM同理由有22111, ( )66iiiiiiiiiihxxhxxxyMyMhh因此第第4章章 数据近似数据近似4.2 分段插值分段插值4.2.3 三次样条插值三次样条插值( )is x因此得到的表达式为33-1-122111-1-( )66 ,66iiiiiiiiiiiiiiiiiiixxx xs xMMhhhxxhxxyMyMxxxhh ( )s xn是由以上在 个区间上的分段函数构成0 ( ),( )( ),ns xs xs xxx满足插值条件 且和在区间上是连续的 ( )1,0,1,.,is xnM in共有个参数需要确定第第4章章 数据近似数据近似4.2 分段插值分段插值4.2.3

11、 三次样条插值三次样条插值( )s x由的连续性要求22-111-1-1-( ) ,226iiiiiiiiiiiiiiixxx xyyMMs xMMhxxxhhh 因此221111111111-( ) ,226iiiiiiiiiiiiiiixxx xyyMMsxMMhxx xhhh ( )isx_ ( )( ),1,2,.,1iisxsxin ,有22-111-1- 226iiiiiiiiiiiiiixxxxyyMMMMhhhh 1126iiiiiiiiM hyyMMhh( )isx2211111111- 226iiiiiiiiiiiiiixxxxyyMMMMhhhh 11111 26iiii

12、iiiiM hyyMMhh 第第4章章 数据近似数据近似4.2 分段插值分段插值4.2.3 三次样条插值三次样条插值11111112626iiiiiiiiiiiiiiiiM hyyMMM hyyMMhhhh 因此可得 11111112266iiiiiiiiiiiiiiiiM hM hMMMMyyyyhhhh 16iihM 111,1iiiiiiiiihhhhhh 记11111111126iiiiiiiiiiiiiiiiiyyyyhhhhMMMhhhhhh -112iiiiiMMM则有 -116 , iiiy xx x 1,2,.,1 in13iiihhM111iiiiiiyyyyhh116ii

13、hM1111116iiiiiiiiiiyyyyxxxxxx ()三弯矩方程组16iihh在上式中两边同乘第第4章章 数据近似数据近似4.2 分段插值分段插值4.2.3 三次样条插值三次样条插值-11-1126 , 1,2,.,1 iiiiiiiiMMMy xx xin联立等式 方法一 自然边界条件00nMM即 0n方法二 给定端点的一阶导数y 和y ,010101-1162,62,nnnnnnMMy x xyhMMyy xxh有 -1n共有个方程,1inM 个未知数,需再补充两个条件才能确定唯一解0()()0ns xs x即 22-111-1-( ) 226iiiiiiiiiiiiixxx x

14、yyMMs xMMhhhh 由于第第4章章 数据近似数据近似4.2 分段插值分段插值4.2.3 三次样条插值三次样条插值方法三 若两端点的导数值未知0( ),(0,1,2,3) ( ),(-3, -2, -1, )iiniicxx yicxx yinnnn设是通过的唯一三次曲线是通过的唯一三次曲线0( )( )nc xcx取三次样条在两端点处的三阶导数分别与和相同000()() ()()nnnsxcxsxcx即 00123321( )6 , , ( )6 ,nnnnncxy x x x xcxy xxxx容易证明 0101111()() ()()nnnnsxMMsxMMhh又 01101231

15、-3-2-1 2212,-2212,nnnnnnnMMh y xx xxMMh y xxxx 因此边界条件为 33-1-122111-1-( )66 ,66iiiiiiiiiiiiiiiiiiixxx xs xMMhhhxxhxxyMyMxxxhh第第4章章 数据近似数据近似4.2 分段插值分段插值4.2.3 三次样条插值三次样条插值001111 nnnnMdMdMdMd011n-1n-1n因此可以得到统一方程组形式222211111, 6 , 1,2,., -1iiiiiiiiiiiihhdy xx xinhhhh其中 000,0,0,0nndd对应于各种边界 (1) 0001011661,

16、1, ,nnnnnndy x xydyy xxhh(2) 00101233212,2, 12,12,nnnnnnndh y xx xxdh y xxxx (3) 第第4章章 数据近似数据近似4.2 分段插值分段插值4.2.3 三次样条插值三次样条插值生成三次样条函数的计算过程(1)(2 -1)nflop生成三弯矩方程组系数矩阵,计算量约为(2)处理边界条件,即处理第一个方程和最后一个方程(3)处理右端向量,2*( -1)n计算二阶差商,计算量约为(4)(5 )n flop求解方程组,追赶法运算量约为(9 )n flop总的计算量约为例1. 对于给定的节点及函数值2431)(54213210kk

17、xfxk的近似值并求插值函数的三次样条求满足自然边界条件)3(),(0)()(0fxSxSxSn 解:3213123113221kkkkhhh11kkkkhhhk 1第第4章章 数据近似数据近似291g272g60g63g213/223/13/123/2123210mmmm3210gggg819,45,47,8173210mmmm解方程组得：将上述结果代入(10)式)(3111kkkkkkkkkhyyhyyg00001023fhhyyg nnnnnnfhhyyg 23111第第4章章 数据近似数据近似211478381)(230 xxxxxS421478381)(231xxxxxS543341

18、0384583)(232xxxxxS21147838123xxxx42147838123xxxx543341038458323xxxx)(xS417)3()3( Sf第第4章章 数据近似数据近似第第4章章 数据近似数据近似3.2 分段插值分段插值3.2.3 三次样条插值三次样条插值三次样条插值的误差分析012221( ) , , , ( ) max( )( ),max- (3.5)2niia x biy xa ba baxxxbs xMy xxsxMy xx 设是上二次连续可微的函数 在上以为节点的三次插值样条函数满足 中 式定理证明: _-1,( )( ) ( )( ) ( )iixxxH

19、tE xtE tx设定义函数 _1( )()( )0iiH xH xH x显然有,11( ),( ),iiiiH txxH txx因此,在上至少有两个零点在上至少有一个零点( )( )- ( )E xy xs x记1,( )()()iixxxxx第第4章章 数据近似数据近似4.2 分段插值分段插值4.2.3 三次样条插值三次样条插值1,( )0iixxH设为 ,即使_( )( ) ( )( ) ( )H tE xtE tx由于 _2 ( )E x_ 02 ( )( )( ) ( )tE xysx 将代入有_1( )( )( ) ( )2E xysx _ ( )x_( )E x 21( )( )

20、8ihys_( )( ) ( )y ts tx_ ( )( )( )( ) ( )H tE xtE tx2211144iiixxh21( )( )8ihys( )( )- ( )E xy xs x记1,( )()()iixxxxx第第4章章 数据近似数据近似4.2 分段插值分段插值4.2.3 三次样条插值三次样条插值-1-1- ( )iiiiiiixxx xs xMMhh由于 ( )is00000000-11-1126 , iiiiiiiiMMMy xxx又 , a b 对02iM000000-116, + ()iiiiiiy xxxM0000-116, + iiiiy xxxM0000-11

21、6 ,iiiiMy xxx0013( ) iiyxx2( )3( )3s tyM从而_21( )( )( )8iE xhys因此 2212ih M221 2M得证-11max, ,iiiiMMxx ( )maxiiisM都有0000000-11-116 , + iiiiiiiy xxxMM2221(3)8ihMM0=iM第第4章章 数据近似数据近似4.2 分段插值分段插值4.2.3 三次样条插值三次样条插值小结:33-1-122111-1-( )66 ,66iiiiiiiiiiiiiiiiiiixxx xs xMMhhhxxhxxyMyMxxxhh( ),( ),iiiis xy s xMM(

22、1)若则有三次样条的表达式( ), ( ),iiiis xy s xmm(2)若则有三次样条的 表达式2211122111-1( )1212 () () ,iiiiiiiiiiiiiiiiiiiiixxxxxxxxs xyyhhhhxxxxxxmxxmxxxhh第第3 3节节 最小二乘近似最小二乘近似第第4章章 数据近似数据近似4.3 最小二乘近似最小二乘近似 第第4章章 数据近似数据近似4.3 最小二乘近似最小二乘近似,(1,2,.,)iix yim 给定数据点2222i111 ( ( )( )min (3-60)mmniikkiiikEp xygxy 为方便,只需考虑(3-60)最小二乘近

23、似问题的解应使成立( )(1,2,., )()kgx knmn和一组函数假定构造函数12,.,n 求系数1/2221 ( ( )miiiEp xy满足达到最小1122( )( )( )( )nnp xg xgxgx( )iip xy满足 ,(3-60)(1,2,., )kkn反之 使成立的就是最小二乘近似问题的解第第4章章 数据近似数据近似4.3 最小二乘近似最小二乘近似222i11 ( ),mnkkikikEgxy 在)中,它是的二次函数 因此其取极小值的必要条件为220,1,2,.,kEkn111( )( )( ),1,2,.,nmmjikijikijiigx gxy gxkn 即 11(

24、 )( ) ,1,2,.,( ) 1,2,.,mkjkijiimkikiiagx gxk jnby gxkn令 1112111212222212 (3-62)nnnnnnnnaaabaaabaaab则有方程组12,.,n 解方程组得到参数第第4章章 数据近似数据近似4.3 最小二乘近似最小二乘近似1121111122222212()()()()()() ,()()()nnmmnmnnm ng xgxgxyg xgxgxyGyg xgxgxy记2222-minEGa y则有 (3-63)TTG GG y写成矩阵形式 (3-62)及其矩阵形式(3-63)称为最小二乘问题的法方程,.可以证明 最小二

25、乘问题的法方程总有解存在1,()TTTGnG GG GG y若矩阵 的秩数是 则是非奇阵 因而方程有唯一解 第第4章章 数据近似数据近似4.3 最小二乘近似最小二乘近似TTG GaG y求解法问题的解的方法的特点232/2/6, ()TG GmnnO mn1.生成矩阵约需的浮点运算量, 解方程组需要浮点运算量总运算量为G2.矩阵 的条件数一般较大,因此会使得到的解存在较大的误差 因此,应避免用法方程来求最小二乘问题的解,比较可靠的方法是正交化方法,2()( )Tcond G Gcond G可以证明 因此会使得到的解存在较大的误差TG G3.矩阵正定第第4章章 数据近似数据近似4.3 最小二乘近

26、似最小二乘近似( )(0,1,2,., ),jig xxjn若取则最小二乘拟合函数为21231( )nnp xxxx得到法方程11112211111121111mmmniiiiiimmmmniiiiiiiiimmmmnnnnniiiiiiiiimxxyxxxx yxxxx y可以使用平方根法求解法方程第第4章章 数据近似数据近似4.3 最小二乘近似最小二乘近似121112,.,1,0,.,0TnTmvv vvQQveveme引理3.6 对任何 维非零向量存在正交矩阵使此处是 维单位向量证明:2,1umu设 是 维向量 且,-2TQIuu令TQ Q由于 -2-2TTTIuuIuu-44TTTIu

27、uuu uu22-44TTIuuuuuI Q为正交矩阵 -2TQvIuuv由于-2Tvuu v1Qve要使1-2Tveu v u必须且只需 1-uve即 与平行1( -) uve可取 为一个数21u由条件知121ve, =112,veuQve因此,取则得到的 就是满足引理条件的正交阵 证毕12Tvuu ve即。第第4章章 数据近似数据近似4.3 最小二乘近似最小二乘近似(),(-3.7)Gnm n mnmQRQGORnOm nn 设 是秩为 的的矩阵 那么 存在 阶正交阵使 式中为 阶非奇上三定理角阵为的零矩阵-2TQIuu由确定的正交阵称为镜像变换或Householder变换阵1:ve几何意

28、义 将向量 反射到 所在的直线上而不改变其长度证明:12nGGggg将 按列分块成12(1,2,., )TjjjmjggggGjjn其中是 的第 列1111 1mQQ ge则存在 阶正交阵使111QGGQG以左乘 得 (1)(1)1 12negg(1)1 2,3,.,jjgQ gjn其中 第第4章章 数据近似数据近似4.3 最小二乘近似最小二乘近似(1)(1)jijgg记 的分量为1(1)(1)1121(1)(1)22211(1)(1)2 ,00nnmmnGggggGQGgg则可写成1(1)(1)(1)22232(1)(1)(1)_323331(1)(1)(1)23(-1) ( -1) nnm

29、mmnGmnggggggGggg若记的右下角的的子矩阵为-1m_2则存在阶的正交阵Q(2)(2)2232(2)(2)_333212(2)(2)300nnmmnggggGQ Ggg使第第4章章 数据近似数据近似4.3 最小二乘近似最小二乘近似_221TOQOQ令 -1Om,其中 为维的零向量2Qm,显然为 阶正交矩阵,且21Q QG_221GQ G(1)(1)(1)112131(2)(2)2232(2)(2)333(2)(2)300000nnnmmnggggggggg12,nnnmQ QQ重复以上步骤,经过 步后 就可以找到 个 阶的正交阵,.,使11nnnGQ QQG(1)(1)(1)1121

30、31(2)(2)2232(3)33000000 00 0 0nnnngggggg第第4章章 数据近似数据近似4.3 最小二乘近似最小二乘近似Gn由 的秩数为12,.,nQ QQ,均为正交阵知0,1,2,.,iin对均成立,则有11,nnQQ QQ若记并将右端矩阵分块RQGO(1)(1)(1)112131(2)(2)2232(3)33,(1,2,., )000000innnnRingggggRg其中是以为对角线元的n阶上三角阵 0,iR由于因此是非奇上三角阵 证毕第第4章章 数据近似数据近似4.3 最小二乘近似最小二乘近似QR分解 RQGO TRGQOnmn即:任何秩为 的矩阵可以分解为正交阵和

31、上三角阵的乘积上述分解式,可称为矩阵的或QR分解正交分解QR利用分解求解法方程组步骤TG G TR R()TTTG yR OQy12()TThR Oh1 TTR RaR h因此有1 Rah11 aR h,TTRG GaG yQQGO若对于存在正交阵使 TRQOTTROQ第第4章章 数据近似数据近似4.3 最小二乘近似最小二乘近似QR分解计算步骤1212,.,nQ QQRh h1.逐步计算矩阵并计算出 和1 Rah12 hRQGQyhO2.求解方程 ia得到所有的第第4章章 数据近似数据近似4.3 最小二乘近似最小二乘近似QR分解计算公式2TQIuu1wve其中12,Timwiw若记 的第 个分量为即令则1,1, i=2,3,.,miiviv1-2Tveu v u由于 21u122Tu vve有 2w222TwwIw1111222()TveveIveve2Tw v因此 2(2() )TTu v uv=2(2)Tu v=22w第第4章章 数据近似数据近似4.3 最小二乘近似最小二乘近似22211122 22m