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

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

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

3、别地，当f(x) Ax b，即f (x)为线性函数时，则最小二乘问题可表示为： min | Ax b 21)线性最小二乘问题解的条件定理1：x*是线性最小二乘问题极小点的充要条件是x*满足ATAx ATb。证明：(1 )必要性令s(x) Ax b2,于是有：s(x) (Ax b)T (Ax b) (xT AT bT)(Ax b) xT AT Ax xT ATb bTAx bTb由于xTATb是一个数，而一个数的转置是它的本身，因此有：xTATb (xTATb)T bT(xTAT)T bTAx故上式可化为：s(x) xT At Ax 2bT Ax bTbs(x) 2At Ax 2ATb若x*是s

4、(x)的极小点，则必有 s(x) 0，则必有：ATAx ATb(2)充分性若 x* 满足 ATAx* ATb，即 AT(Ax* b) 0考虑任一点v x* z Rn，计算|Av b|A(x* z) q2 (Ax* b) Az)T(Ax* b) Az)(Ax b)T(Ax b) (Ax b)T Az zTAT(Ax b) (Az)T(Az)| Ax*| Az2 2zTAT(Ax* b)由于上式第二项大于等于零，第三项为零，故x*是极小点.我们称ATAx ATb为最小二乘问题的法方程组。由上述定理可知，求解最小二乘问题等价于求解它的法方程组。2) 法方程组的解法由于vtAtAv |Av0，所以At

5、A至少是半正定的，因此法方程组有解的条件 是AtA正定。定理2：设A是m n矩阵(m n),则AT A正定的充要条件是A的秩为n.推论1：当A的秩为n时，则x (AtA) 1ATb是最小二乘的唯一解。推论2:设A是m n矩阵(m n)，则AAT正定的充要条件是A的秩为m.推论3：设A是m n矩阵(m n),则AAT正定的充要条件是ATA为非奇异. 上述解法方程组的解法需要 AtA正定,实际问题并不能保证AtA正定，因此 上述方法仅具有理论意义。3) 用QR分解求线性最小二乘解若Q是m m正交矩阵Q 1 QT，则2 2Q(ax b) (Ax b)TQTQ(Ax b) (Ax b)T (Ax b)

6、 Ax b上式说明以|Q(Ax b)|2为目标函数的最小二乘解与目标函数为|Ax b|2的最小二乘解具有相同的解。因此求解min|Ax b可转化为求解mi n|Rx其中R QA， c Qb。由线性代数可知，适当地选择正交矩阵Q,总可使R QA呈现为如下形式的矩阵：R U，其中U是r n的秩为r的上梯形矩阵；O是(m r) n的零矩阵。 定理：线性最小二乘问题min|Ax即与线性方程组Ux p具有相同解. 其中p是由c Qb的前r个分量组成的r维向量。证明：由于minAx b的解与min | Rx q2的解相同.现只需证明mi n|Rx与Ux p具有相同的解。min Rx c ?的法方程组为rt

7、 Rx RTc，即RTRx RTc的解就是min Rx c ?的解。TT将R U代入上式有：UUx UP，上式展开后得：UTUxUTpOOO Oq而在Ux p的两侧同时左乘UT即得UTUx UTp.若r(U ) n。最小二乘问题的解为x U 1p。否则最小二乘问题的解不是唯一 的，在这种情况下，通常取具有最小范数的解作为最小二乘问题的解这个解称为最小二乘问题的极小最小二乘解。这个解为x UT(UUT) 1p，且解是唯一的。x UT(UUT) 1p显然是Ux p的一个解。设y是Ux p的另一个解。则 U(x y) 0y2 x (x y)2 x2 x y2 2xT(x y)xT(x y) pT(U

8、UT) 1TU(x y) 0因为x y 0，所以y2 x2。因此极小最小二乘解是唯一的。3. Gauss Newt on 法Gauss Newt on法适用于非线性最小二乘 问题s(x) f (x)T f (x)。Gauss-Newton法是一种迭代算法假定选定初始点Xo后经过迭代已求得Xk.现考虑Xki的求法。首先把f(X)线性化，用线性最小二乘问题的解去逼近非线性最小二乘问题 的解把f(x)的第i个分量fi(x)在点Xk处用Taylor展开式展开.fi(x) fi(Xk)fi(Xk)T(x Xk),i 1,m则 f(x) f(Xk) A(Xk)(x Xk)，其中:f,Xk)TA(Xk)fi

9、(xQXifi(Xk)Xnfm(Xk)Tfm(Xk)X1fm(Xk)Xn记 fk f (Xk)， AkA(Xk)，则 s(x)I fk Ak(x Xk)如设线性最小二乘问题min AkPfk的解为Pk，那么Xk 1 Xk Pk就是极小点的新的近似解。由前述可知，Pk(A：Ak) Ffk，则 Xk 1Xk(A：Ak) 1A：fk.当f(x)满足一定的条件，并且Xo充分靠近极小点时，算法是收敛的。假如在某次迭代中At Ak变成奇异的，那么上述方法失效，另外，当Xo离极小点较远时，算法可能发散例：设有非线性方程组2 2f1 (x) x-i2x2 1 0f2(x) 2% x2 2 0(1 )列出求解这

10、个方程组的非线性最小二乘问题的数学模型。(2)写出Gauss-Newton法迭代公式的具体形式.数学模型为：min(X： 2x2 1)2 (2为他2)2)f (x)X22T2X21 2X1 X22A(x)2为24x21例：已知某物理量y与另两个物理量t1和t2的依赖关系为yX1X3t11X-I t1x2t2，其中X1，X2和X3是待定参数。为确定这三个参数测得ti上和y的5组数据:t1t2y1.0001.0000.1262.0001.0000.2191.0002.0000.0762.0002.0000.1260.1000.0000.186(1)用最小二乘法建立关于确定X1， X2和X3的数学模

11、型。 写出Gauss-Newton法迭代公式的具体形式。数学模型为:min f(X)T f(X)f1(x)f2 (X) f (X)f3(x)f4 (X)fs(x)(X1X31 X-i X22X1X31 2x1 x2X1X31 x1 2x22X1X31 x1 2x20.1x1 X3(1Xi迭代公式为:xk 1f1(Xk)TA(Xk)fm(Xk)T20.126)0.219)20.076)20.126)20.186)2Xk(Ak Ak)f1(Xk)X1f1( Xk )Xnfm(Xk)Xifm(Xk)Xn4.修正 Gauss Newton 法先确定一个搜索方向，从Xk出发作直线搜索来求下一个迭代点Xk

12、 1.当 AkT Ak 非奇异时，将 GaussNewton 法解出来的 pk 作为搜索方向，否则将 负梯度方向作为搜索方向 .下面证明 GaussNewton 法解出来的 pk 是目标函数的一个下降方向。mT2s(X) f(X)T f (X)fi2(X)i1ms(X) 2 fi(X) fi(X) 2A(X)T f (X)i1pk( AkT Ak ) 1AkTfks(Xk)Tpk2( AkT f k )T ( AkT Ak ) 1AkTfk 0因此Gauss-Newton法解出来的Pk是目标函数的一个下降方向。5。阻尼最小二乘法Gauss Newt on法收敛速度一般是较快的。它遇到的主要问题

13、是 NAk可能为 奇异，以至Pk (AkAk) 1 A-fk无法求出。遇到这种情况，修正 Gauss-Newton法 是用负梯度方向代替Pk,这时Gauss-Newton法变为梯度法，收敛速度减慢。阻尼最小二乘法将从另一个角度来克服上述困难 .1)基本想法Gauss-Newton法是用方程AAp N fk来确定pk的。现在矩阵aTa对角线上的元素都加上同一个数o，则上述方程变为：(AkT AkI)P AkT fk这样做的目的是：即使ATAk奇异，只要将 取得充分大，总能使(ATAkI)正定，从而(NAkI)pNAr肯定有解。这个解依赖于，记为Pk()。当 0 时，pk (0)就是 Gauss Newton 方向。当 已经增大到与aTa的每个分量相比这些分量都趋于消失，则(AkTAkl)pNfk变为IpAfk,这就是说，当很大时，pk()将接近负梯度方向。可以想象，当从零增大到无穷大时，Pk()将从Gauss-Newton方向连续地转向负梯度方向 ATfk。由以上的分析，可构成如下的迭代格式:Xk 1Xk(N AkkI) 1Ak'fk这就是阻尼最小二乘法的迭代公式，称为阻尼因子.最后说明一下阻尼最小二乘法的由来。当 0时,Pk (AkAN