最优化——第五次最小二乘法

最小二乘法•一、线性最小二乘法•二、非线性最小二乘法•1.改进的Gauss-Newton法•2.Levenberger-Marquart方法一、线性最小二乘法)()()(min)(.1xfxfxSPT满足）的最优解问题（*xP.2bAx)x(f这里mnnmRb,Rx,RAbAAxATT2bAxbbAxbAxAx)x(STTTT2证明：022)(bAAxAxSTTδx*x22b)x(AbAx*)bAx(AAbAx*TT*22222AbAx*0时取到最小值.可见，当δ)(2*22*bAAxAAbAxTTT])*([])*([AbAxAbAxT例程组试用最小二乘法求此方给定方程组,3412322212121xxxxxx的近似解。解：,)34()12()322()(221221221xxxxxxxF令。则原问题化为)(minxFRx，记313,,41212221bxxxA。则)()()(bAxbAxxFT,24666412122422112AAT。1610313422112bAT。18118118192)(1AATbAAAxTT1)(*。3134161018118118192二、非线性最小二乘法1.一般形式：2)()()()(minxfxfxfxST;),...,,())(),...,(),(()(2121TnTmxxxxxfxfxfxf其中：线性最小二似非线性函数，再模仿思想：用线性函数来近乘法求解。,))(()()(kkkxxxAxfxf所以。),...,2,1(),()()()(mixxxfxfxfkTkikii则由泰勒公式可知，次的迭代点设已知第kxk。其中nmjkixxnmmnkxxfxf...xfxf...xfxAk))(()(1111分析求解.222)()()()(kkkkkkxfdAxxAxfxS。其中：kkxxd法可得问题，由线性最小二乘对于)(minx可逆时则有当kTkAA则有记,)(kkxAA,])([])([kkkTkkkxfdAxfdA)(min,])([])([)(xxfdAxfdAxkkkTkkk则可用记极小点。的极小点近似原问题的)(kTkkkTkxfAdAA)1()()(1kTkkTkkxfAAAd)2(收敛阶是二阶的。在一定条件下　　是收敛的由迭代得到的则：，充分接近）满足一定条件且（性质：若,)2(;}{)1(*0kxxxxf3.改进的Gauss-Newton法：)()(11kTkkTkkkkkxfAAAxdxx，则有迭代公式令kkkdxxx1,)()(2)()(2)(1miTiixfxAxfxfxS因为矩阵。的在点是则HessexxHkk)(,2kTkkAAH记）式可改写为（1)(kkkxSdH)4()3()(1kkkxSHd即)5(所以)(11kkkkxSHxx)6(公式，式称为NewtonGauss)6(方向。）式称为（NewtonGauss5。令)()()(2)(kTkkkTkkxfAxfxAxSg则由其正定性可知：存在若,)(1kTkAA为下降方向kd0)(2)(1kkTkTkkTkgAAgdxS。奇异，则解不出否则，若kkTkdAA。此时令kkgd算法（共五步）改进的NewtonGauss。精度给定初始点0,:10xStep。令0:k;)(:2)(kjkikijAxxfaStep计算：。mikjkikikjgxxfxfg1)()()(nArankxfAgnArankxfAAAdStepkTkkkTkkTkk)()()()()(:31如果如果令nmjiTmxfxAxfxfxf)(;))(,),(()(1已知：。其中令)(min:,:41kktkkkkktdxftdtxxStep。转否则算法结束则若2,1:,;,,||)(||:51*StepkkxxxfAStepkkTk三、Levenberger-Marquart方法时，迭代无法继续！）接近于（条件数为奇异或法的迭代中，当1)()(.11BBxAxABNewtonGaussT迭代继续！的对角元的措施使方法采用适当增加)()(.2xAxAMLT方程组：方法求解如下满足当前的迭代点MLxSxkk,0)(.3(**))()()(:))()((kTkkkTkxfxAzxCzIxAxA过大！能够成立又不至于使为正定，且中不断调整使是一个正数，它在迭代其中)()()(:1kkkxSxSxC。得到下一迭代点然后令11kkkxzxx!)(30.4敛速度的增加，否则将影响收尽可能限制方向。因而充分大时便接近负梯度偏移，当方向逐步向负梯度表明方向的增大，下面的性质方向；随着就是，得到的若取XSzNewtonGaussz）的解，那么有：是方程组（，设**0.5z))()()()(122zyzxAxfyxAxfkkkk（：性质).()(2kkxSzxS适当大，总成立：：只要性质充分接近。与方向充分大时，方向：当性质)(3kxSz。并返回：则令若1),()(:2StepxSzxSStep放大。遇到困难时将缩小，迭代：一次成功迭代后将采用进退方法调整.6调整算法：.7。的初值，控制终止常数，初始点给定和步长缩小因子子初始：给定步长放大因xxf),(,101。得求解zxfxAzIxAxAStepTT)()())()((:1。否则返回则迭代终止，）（若令1)(;,::3StepxfxAzxxStepT