第三章 3 曲线拟合

1、第第3 3章章 数据近似数据近似第第3章章 数据近似数据近似3.3 最小二乘近似最小二乘近似 第第3章章 数据近似数据近似3.3 最小二乘近似最小二乘近似,(1,2,.,)iix yim 给定数据点2222i111 ( ( )( )min (3-60)mmniikkiiikEp xygxy 为方便,只需考虑(3-60)最小二乘近似问题的解应使成立( )(1,2,., )()kgx knmn和一组函数假定构造函数12,.,n 求系数1/2221 ( ( )miiiEp xy满足达到最小1122( )( )( )( )nnp xg xgxgx( )iip xy满足 ,(3-60)(1,2,., )

2、kkn反之 使成立的就是最小二乘近似问题的解第第3章章 数据近似数据近似3.3 最小二乘近似最小二乘近似222i11 ( ),mnkkikikEgxy 在)中,它是的二次函数 因此其取极小值的必要条件为220,1,2,.,kEkn111( )( )( ),1,2,.,nmmjikijikijiigx gxy gxkn 即 11( )( ) ,1,2,.,( ) 1,2,.,mkjkijiimkikiiagx gxk jnby gxkn令 1112111212222212 (3-62)nnnnnnnnaaabaaabaaab则有方程组12,.,n 解方程组得到参数第第3章章 数据近似数据近似3.

3、3 最小二乘近似最小二乘近似1121111122222212()()()()()() ,()()()nnmmnmnnm ng xgxgxyg xgxgxyGyg xgxgxy记2222-minEGa y则有 (3-63)TTG GG y写成矩阵形式 (3-62)及其矩阵形式(3-63)称为最小二乘问题的法方程,.可以证明 最小二乘问题的法方程总有解存在1,()TTTGnG GG GG y若矩阵 的秩数是则是非奇阵 因而方程有唯一解 第第3章章 数据近似数据近似3.3 最小二乘近似最小二乘近似TTG GaG y求解法问题的解的方法的特点232/2/6, ()TG GmnnO mn1.生成矩阵约需

4、的浮点运算量, 解方程组需要浮点运算量总运算量为G2.矩阵 的条件数一般较大,因此会使得到的解存在较大的误差 因此,应避免用法方程来求最小二乘问题的解,比较可靠的方法是正交化方法,2()( )Tcond G Gcond G可以证明 因此会使得到的解存在较大的误差TG G3.矩阵正定第第3章章 数据近似数据近似3.3 最小二乘近似最小二乘近似( )(0,1,2,., ),jig xxjn若取则最小二乘拟合函数为21231( )nnp xxxx得到法方程11112211111121111mmmniiiiiimmmmniiiiiiiiimmmmnnnnniiiiiiiiimxxyxxxx yxxxx

5、 y可以使用平方根法求解法方程第第3章章 数据近似数据近似3.3 最小二乘近似最小二乘近似121112,.,1,0,.,0TnTmvv vvQQveveme引理3.6 对任何 维非零向量存在正交矩阵使此处是 维单位向量证明:2,1umu设 是 维向量 且,-2TQIuu令TQ Q由于 -2-2TTTIuuIuu-44TTTIuuuu uu22-44TTIuuuuuI Q为正交矩阵 -2TQvIuuv由于-2Tvuu v1Qve要使1-2Tveu v u必须且只需 1-uve即 与平行1( -) uve可取 为一个数21u由条件知121ve, =112,veuQve因此,取则得到的 就是满足引理

6、条件的正交阵 证毕12Tvuu ve即第第3章章 数据近似数据近似3.3 最小二乘近似最小二乘近似(),(-3.7)Gnm n mnmQRQGORnOm nn 设 是秩为 的的矩阵 那么 存在 阶正交阵使 式中为 阶非奇上三定理角阵为的零矩阵-2TQIuu由确定的正交阵称为镜像变换或Householder变换阵1:ve几何意义 将向量 反射到 所在的直线上而不改变其长度证明:12nGGggg将 按列分块成12(1,2,., )TjjjmjggggGjjn其中是 的第 列1111 1mQQ ge则存在 阶正交阵使111QGGQG以左乘 得 (1)(1)1 12negg(1)1 2,3,.,jjg

7、Q gjn其中 第第3章章 数据近似数据近似3.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) nnmmmnGmnggggggGggg若记的右下角的的子矩阵为-1m_2则存在阶的正交阵Q(2)(2)2232(2)(2)_333212(2)(2)300nnmmnggggGQ Ggg使第第3章章 数据近似数据近似3.3 最小二乘近似最小二乘近似_221TOQOQ令 -1Om,其

8、中 为维的零向量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)112131(2)(2)2232(3)33000000 00 0 0nnnngggggg第第3章章 数据近似数据近似3.3 最小二乘近似最小二乘近似Gn由 的秩数为12,.,nQ QQ,均为正交阵知0,1,2,.,iin对均成立,则有11,nnQQ QQ若记并将右端矩阵分块RQGO

9、(1)(1)(1)112131(2)(2)2232(3)33,(1,2,., )000000innnnRingggggRg其中是以为对角线元的n阶上三角阵 0,iR由于因此是非奇上三角阵 证毕第第3章章 数据近似数据近似3.3 最小二乘近似最小二乘近似QR分解 RQGO TRGQOnm n即:任何秩为 的矩阵可以分解为正交阵和上三角阵的乘积上述分解式,可称为矩阵的或QR分解正交分解QR利用分解求解法方程组步骤TG G TR R()TTTG yR OQy12()TThR Oh1 TTR RaR h因此有1 Rah11 aR h,TTRG GaG yQQGO若对于存在正交阵使 TRQOTTROQ第

10、第3章章 数据近似数据近似3.3 最小二乘近似最小二乘近似QR分解计算步骤1212,.,nQ QQRh h1.逐步计算矩阵并计算出 和1 Rah12 hRQGQyhO2.求解方程 ia得到所有的第第3章章 数据近似数据近似3.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第第3章章 数据近似数据近似3.3 最

11、小二乘近似最小二乘近似22211122 22miivvvvv用分量形式得到222v 2v 12sgn( )vv 为保证精度,取 12-1,.,kkQ QQ一般地,在作第 步变换前 已得到正交阵12-1,.,kG GG,并且计算出了10,1,2,.,1()iiiGQGikGG满足关系 记(1)(1)(1)(1)1121311(2)(2)(2)22322(1)(1)111,1,(1)(1)knknkkkkkkknkkmkmngggggggGgggg第第3章章 数据近似数据近似3.3 最小二乘近似最小二乘近似,kKQ G计算的过程按下述过程进行12(1)(1)2 sgn()() (3-71)mkkk

12、kkiki kgg ( )( )( )1( ) kkkkkkmw若记22( )( -1)(1)221 ()mkkkkkkiki kwgg 则(1)2( -1)2()2kmkkikkkki kgg2( -1)22kkkkkkg( -1)2()kkkkkg( )2kkk 1kkve( -1)( -1)1,( -1)0-0kkkkkkkkmkggg 第第3章章 数据近似数据近似3.3 最小二乘近似最小二乘近似 (3-72) (k)kkk记=1_1 Q1kkkkIOIkPQ则 在中是阶单位阵( )( )_2( )2-2kk TkkwwQIw1( )( )kk TkIww1(1) (1)kkQGmknk于是左乘右下角的的子矩阵( -1)( -1)_1( -1)( -1)kkkkknkkkmkmnggGgg_1kG_k可由Q 乘的各列完成,_111kkkknGGggg将分块成_(1)(1),.,1,.,Tkkkjmjkgggjk kn式中 第第3章章 数据近似数据近似3.3 最小二乘近似最小二乘近似_ _1( )( )_( )() (3-73)kk TkkjjkjkjQ gIwwggt w于是 _1( )1( )(1) (3-74)mkkkjkkkiijji ktwgg这里 (3-71)(3-74)kkQG因此,由到式可以计算出和第第3章