第五章--最小二乘问题的解法

1、第五章 最小二乘问题的解法1. 最小二乘问题1) 回归方程问题【巴,L，yT,i =1,2,m是m个实验点。现要根据这些点确定y与l个物理量匕出,匕之间的关系式。设这种关系式为y = F (ti ,t| , Xi ,Xn )，其中Xi,., Xn是方程中需要待定的门个参 数係数)。因此问题是如何通过m(m .n)个实验点，确定方程中的系数。由于实验点的个数大于待定系数的个数，因此方程中系数的确定是一个超 静定问题，无法按一般的方法进行求解。此时将实验点到曲面距离最短的那个曲面作为所求曲面，从而求取该曲面 方程。m即求解minF (t,x) y(i) 2，这就是最小二乘问题。i2) 非线性方程组

2、问题1(X1 ,., Xn ) = 0求解非线性方程组f2(X1,., Xn) M可转化为求解如下形式的最小二乘问题。Ifn (Xi ,., Xn) =0m - 2min 二 f i (Xi,., Xn)i 土显而易见，最小二乘法的一般形式可写为min f (x)t f (x)最小二乘法问题实际上是具有n个变量的无约束极小化问题，前面解无约束 优化问题的方法均可应用。但是最小二乘问题具有一定的特殊性，即目标函数的表达式是由多个表达ii式的平方和组成，理应有更、更有效的方法。这正是最小二乘解法要解决的问 题。2. 线性最小二乘问题的解法最小二乘法的一般形式可写为min f(x)Tf(x)特别地，

3、当f(x)二Ax _b，即f (x)为线性函数时，则最小二乘问题可表示为: min |Ax -b1)线性最小二乘问题解的条件定理1：x*是线性最小二乘问题极小点的充要条件是x*满足AT Ax二ATb。证明：(1)必要性令s(x) =|ax b，于是有:s(x) =(Ax -b),Ax -b) =(xA -J)(Ax - bAx - b -Ax bb由于xTATb是一个数，而一个数的转置是它的本身，因此有：xT A T b = (xT AT b)T =bT(xTAT)T = bT Ax故上式可化为：s(x) = XT AT Ax -2bT Ax bT b' s(x) =2 AT Ax -

4、2 ATb若x*是s(x)的极小点，则必有、s(x)=O，则必有:ATAx二ATb(2)充分性若 x 满足 AT Ax = AT b，即 AT ( Ax -b)=0考虑任一点7 i z Rn，计算Av _bA(x* z) _b =( Ax * _b) Az)T (Ax * _b) Az)*T*TT T*T= (Ax -b) (Ax -b) (Ax -b) Az z A (Ax -b) - (Az) (Az)2=Ax * -b Az 2zT AT (Ax * - b)由于上式第二项大于等于零，第三项为零，故x*是极小点。我们称ATAx =ATb为最小二乘问题的法方程组。由上述定理可知，求解最小二

5、乘问题等价于求解它的法方程组。2) 法方程组的解法由于vfv =|Av_0，所以ATA至少是半正定的，因此法方程组有解的条件 是ata正定。定理2：设A是m n矩阵(m . n)，则AT A正定的充要条件是A的秩为n。推论1：当A的秩为n时，则x=(ATA)ATb是最小二乘的唯一解。推论2：设A是m n矩阵(m乞n)，则AAT正定的充要条件是A的秩为m。推论3：设A是m n矩阵(m . n)，则aA正定的充要条件是AT A为非奇异。上述解法方程组的解法需要ata正定，实际问题并不能保证ata正定，因此 上述方法仅具有理论意义。3) 用QR分解求线性最小二乘解若Q是m m正交矩阵QQt，则Q (

6、ax -b)=(Ax -b)TQTQ(Ax -b) =(Ax -b)T (Ax -b) = Ax - b上式说明以|Q(Ax -b)为目标函数的最小二乘解与目标函数为| Ax -b的最小二乘解具有相同的解。因此求解min |Ax -b可转化为求解 min | Rx -c|，其中 R =QA ， c = Qb。由线性代数可知，适当地选择正交矩阵Q ,总可使R -QA呈现为如下形式的矩阵:R=U I,其中u是灯的秩为r的上梯形矩阵；0是(mr)"的零矩阵。定理：线性最小二乘问题min |Ax _b 2与线性方程组Ux = p具有相同解。其中p是由c =Qb的前r个分量组成的r维向量。证明

7、：由于 min | Ax b的解与 min | Rx -c| 2的解相同。现只需证明 min H Rx 一 c与 Ux = p具有相同的解。min | Rx -c |2的法方程组为RTRx=RTc，即RTRx=RTc的解就是 min | Rx - c2的解。将R =代入上式有：P U叮?'，上式展开后得：UTUX =UTp1。dd 6 5而在Ux =p的两侧同时左乘UT即得U TUx =U T p。若r(U ) =n。最小二乘问题的解为x =Up。否则最小二乘问题的解不是唯一 的，在这种情况下，通常取具有最小范数的解作为最小二乘问题的解。这个解 称为最小二乘问题的极小最小二乘解。这个解

8、为x = UT(UU T)p，且解是唯一的。x =U T (UU T )p显然是Ux = p的一个解。设y是Ux = p的另一个解。贝卩 U (x _y) =0y=|x-(x-y)| =|x| +|xy| -2/ (y)TTT _1 Tx(X -y) =p (UU ) U (x -y) =0因为 |x-y|。，所以 |y|、x。因此极小最小二乘解是唯一的。3. Gauss-Newton 法Gauss-Newton法适用于非线性最小二乘问题 s(x) =f (x)T f (x)。Gauss-Newton法是一种迭代算法假定选定初始点Xo后经过迭代已求得Xk。现考虑的求法。首先把f(x)线性化，用

9、线性最小二乘问题的解去逼近非线性最小二乘问题的解。把f(x)的第i个分量fi(x)在点Xk处用Taylor展开式展开fi(x) ：、fi(Xk) fj(Xk)T(x Xk)， i =1,., m则 f(x) = f(Xk)A&kXxXk)，其中:A(Xk)Vf'Xk 厂_TWm (Xk )：fl(Xk)cf m (Xk)Ifl(XQ；：f m (Xk )-Xn5#记 fk = f (xj， Ak =A(Xk)，贝S s(x) ：、fk Ajx Xk) $如设线性最小二乘问题min|AkP - fk的解为Pk，那么Xk d = Xk Pk就是极小点的新的近似解由前述可知,Pk =

10、-3入宀飞，则Xk 1二Xk -(A：Ak)A： fk。当f(x)满足一定的条件，并且X0充分靠近极小点时，算法是收敛的。假如在某次迭代中A：Ak变成奇异的，那么上述方法失效，另外，当X。离极小点较远时，算法可能发散。 2 2例：设有非线性方程组“1空2十0I f2 (x) = 2洛 + x2 2 = 0(1)列出求解这个方程组的非线性最小二乘问题的数学模型。f (X)=(2)写出Gauss-Newton法迭代公式的具体形式。数学模型为：min( x12 2x2 -1)2 ' (2x1 x2 - 2)2)迭代公式为：Xk 1 二Xk -(A""%： fk丄22x2

11、-12x1 x2 -2 fA(x)2Xi4 x21例：已知某物理量y与另两个物理量ti和t2的依赖关系为1 Xiti - X?t2，其中X1 ,x2和x3是待疋参数。1.0002.0001.000t21.0001.0002.000y0.1260.2190.076为确定这二个参数测得2.000 0.1002.000 0.0000.126 0.186t1，t2和y的5组数据:(1)用最小二乘法建立关于确定X1 , X2和X3的数学模型。写出Gauss-Newton法迭代公式的具体形式。数学模型为：min f(x)T f (x)(" 0.126 )21 + x2M(x)|f2 (x)f(x

12、)= f3(X)| f4(X)5(X)一2x1 x3( 1 2x1 x2-0.219)2X1X3( 1 x1 2x22-0.076)2x1 X31 x1 2x22-0.126)0.1 x1 x3(0.186)-1 +人%(Xk)T|Wm(XQT-f m ( X k )X11 ( Xk )讦1(Xk);x-Xn迭代公式为：T_LTxk:：1二 xk -(Ak Ak )A k f k4. 修正 Gauss-Newton法先确定一个搜索方向，从Xk出发作直线搜索来求下一个迭代点Xk.1当aT Ak非奇异时，将Gauss-Newton法解出来的Pk作为搜索方向，否则将负梯度方向作为搜索方向下面证明Ga

13、uss-Newton法解出来的pk是目标函数的一个下降方向。mT_2s(x) = f (x) f(X)二' fi (x)i丄m'、s(x) =2 fi (x) fi(x) =2A(x)T f (x)i -1T_1 TPk =-(AkAk) Ak fk''S(xk) Pk = -2 (Ak f k ) ( Ak A k ) Ak f k 0因此Gauss-Newton法解出来的Pk是目标函数的一个下降方向。5. 阻尼最小二乘法Gauss-Newton法收敛速度一般是较快的。它遇到的主要问题是AT Ak可能为奇 异，以至Pk -(A：Ak)fk无法求出。遇到这种情况

14、，修正 Gauss-Newton法是 用负梯度方向代替Pk，这时Gauss-Newton法变为梯度法，收敛速度减慢。阻尼最小二乘法将从另一个角度来克服上述困难。1)基本想法Gauss-Newton法是用方程人入卩二-a： fk来确定Pk的。现在矩阵A： Ak对角线上的元素都加上同一个数 J - 0，则上述方程变为：(A：Akl) p = -A； fk这样做的目的是：即使A：Ak奇异，只要将取得充分大，总能使(A：Akl) 正定，从而(A；AkI)P A：Ak肯定有解。这个解依赖于，记为pf)。当=0 时，Pk(0)就是 Gauss-Newton方向。当已经增大到与A：Ak的每个分量相比这些分量都趋于消失，则 (A；Akl)p二-A； fk变为人九，这就是说，当，很大时，PkL)将接近负梯 度方向。可以想象，当J从零增大到无穷大时，PkQ）将从Gauss-Newton方向连续地 转向负梯度方向A：fk。由以上的分析，可构成如下的迭代格式：T1 TXk 1 =Xk -（Ak AkAk fk这就是阻尼最小二乘法的迭代公式，称为阻尼因子。最后说明一下阻尼最小二乘法的由来。当.二-0时,Pk 入宀：fk。当 J 充分大时，i|p ：、- A： f k，