2022年第五章--最小二乘问题的解法 .pdf

《2022年第五章--最小二乘问题的解法 .pdf》由会员分享，可在线阅读，更多相关《2022年第五章--最小二乘问题的解法 .pdf（8页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1 第五章最小二乘问题的解法1.最小二乘问题1)回归方程问题Tiiliytt)()()(1,.,mi,.,2, 1是m个实验点。现要根据这些点确定y与l个物理量lttt,.,21之间的关系式。设这种关系式为),.,.,(11nlxxttFy，其中nxx ,.,1是方程中需要待定的n个参数(系数)。因此问题是如何通过)(nmm个实验点，确定方程中的系数。由于实验点的个数大于待定系数的个数，因此方程中系数的确定是一个超静定问题，无法按一般的方法进行求解。此时将实验点到曲面距离最短的那个曲面作为所求曲面，从而求取该曲面方程。即求解miiiyxtF12)()(),(min，这就是最小二乘问题。2)非线

2、性方程组问题求解非线性方程组0),.,(.0),.,(0),.,(11211nnnnxxfxxfxxf可转化为求解如下形式的最小二乘问题。minixxf112),.,(min显而易见，最小二乘法的一般形式可写为)()(minxfxfT最小二乘法问题实际上是具有n个变量的无约束极小化问题， 前面解无约束优化问题的方法均可应用。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 8 页2 但是最小二乘问题具有一定的特殊性，即目标函数的表达式是由多个表达式的平方和组成，理应有更、更有效的方法。这正是最小二乘解法要解决的问题。2.线性最小二乘问题的

3、解法最小二乘法的一般形式可写为)()(minxfxfT特别地，当bAxxf)(，即)(xf为线性函数时，则最小二乘问题可表示为：2minbAx1) 线性最小二乘问题解的条件定理 1:*x是线性最小二乘问题极小点的充要条件是*x满足bAAxATT。证明：(1)必要性令2)(bAxxs，于是有：bbAxbbAxAxAxbAxbAxbAxbAxxsTTTTTTTTTT)()()()(由于bAxTT是一个数，而一个数的转置是它的本身，因此有：AxbAxbbAxbAxTTTTTTTTTT)()(故上式可化为：bbAxbAxAxxsTTTT2)(bAAxAxsTT22)(若*x是)(xs的极小点，则必有0

4、)(xs，则必有：bAAxATT(2)充分性若*x满足bAAxATT*，即0)(*bAxAT考虑任一点nRzxv*，计算精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 8 页3 )(2)()()()()()()()()(*22*2*2bAxAzAzbAxAzAzbAxAzAzbAxbAxbAxAzbAxAzbAxbzxAbAvTTTTTTTT由于上式第二项大于等于零，第三项为零，故*x是极小点。我们称bAAxATT为最小二乘问题的法方程组。由上述定理可知，求解最小二乘问题等价于求解它的法方程组。2)法方程组的解法由于02AvAvAvTT

5、， 所以AAT至少是半正定的， 因此法方程组有解的条件是AAT正定。定理 2:设A是nm矩阵)(nm，则AAT正定的充要条件是A的秩为n。推论 1:当A的秩为n时，则bAAAxTT1)(是最小二乘的唯一解。推论 2:设A是nm矩阵)(nm，则TAA正定的充要条件是A的秩为m。推论 3: 设A是nm矩阵)(nm，则TAA正定的充要条件是AAT为非奇异。上述解法方程组的解法需要AAT正定，实际问题并不能保证AAT正定，因此上述方法仅具有理论意义。3)用QR分解求线性最小二乘解若Q是mm正交矩阵TQQ1，则22)()()()()(bAxbAxbAxbAxQQbAxbaxQTTT上式说明以2)(bAx

6、Q为目标函数的最小二乘解与目标函数为2bAx的最小二乘解具有相同的解。因此求解2minbAx可转化为求解2mincRx，其中QAR，Qbc。由线性代数可知，适当地选择正交矩阵Q，总可使QAR呈现为如下形式的精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页，共 8 页4 矩阵：OUR，其中U是nr的秩为r的上梯形矩阵；O是nrm)(的零矩阵。定理: 线性最小二乘问题2minbAx与线性方程组pUx具有相同解。其中p是由Qbc的前r个分量组成的r维向量。证明：由于2minbAx的解与2mincRx的解相同。现只需证明2mincRx与pUx具有相同

7、的解。2mincRx的法方程组为cRRxRTT，即cRRxRTT的解就是2mincRx的解。将OUR代入上式有：qpOUxOUOUTT，上式展开后得：pUUxUTT而在pUx的两侧同时左乘TU即得pUUxUTT。若nUr)(。最小二乘问题的解为pUx1。否则最小二乘问题的解不是唯一的，在这种情况下，通常取具有最小范数的解作为最小二乘问题的解。这个解称为最小二乘问题的极小最小二乘解。这个解为pUUUxTT1)(，且解是唯一的。pUUUxTT1)(显然是pUx的一个解。设y是pUx的另一个解。则0)(yxU)(2)(2222yxxyxxyxxyT0)()()(1yxUUUpyxxTTTT因为0yx

8、，所以22xy。因此极小最小二乘解是唯一的。3.Gauss-Newton法Gauss-Newton法适用于非线性最小二乘问题)()()(xfxfxsT。Gauss-Newton精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4 页，共 8 页5 法是一种迭代算法。假定选定初始点0 x后经过迭代已求得kx。现考虑1kx的求法。首先把)(xf线性化，用线性最小二乘问题的解去逼近非线性最小二乘问题的解。把)(xf的第i个分量)(xfi在点kx处用 Taylor 展开式展开。)()()()(kTkikiixxxfxfxf，mi,.,1则)()()(kkkx

9、xxAxfxf，其中：nkmkmnkkTkmTkkxxfxxfxxfxxfxfxfxA)()()()()()()(11111记)(kkxff，)(kkxAA，则2)()(kkkxxAfxs如设线性最小二乘问题kkfpAmin的解为kp，那么kkkpxx1就是极小点的新的近似解。由前述可知，kTkkTkkfAAAp1)(，则kTkkTkkkfAAAxx11)(。当)(xf满足一定的条件，并且0 x充分靠近极小点时，算法是收敛的。假如在某次迭代中kTkAA变成奇异的，那么上述方法失效，另外，当0 x离极小点较远时，算法可能发散。例：设有非线性方程组022)(012)(21222211xxxfxxx

10、f(1)列出求解这个方程组的非线性最小二乘问题的数学模型。(2)写出 Gauss-Newton法迭代公式的具体形式。数学模型为：)22() 12min(22122221xxxx精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 8 页6 迭代公式为：kTkkTkkkfAAAxx11)(Txxxxxf2212)(2122211242)(21xxxA例：已知某物理量y与另两个物理量1t和2t的依赖关系为22111311txtxtxxy，其中1x，2x和3x是待定参数。为确定这三个参数测得21,tt和y的 5 组数据：186.0126.0076.

11、0219.0126.0000.0000.2000.2000.1000.1100.0000.2000.1000.2000.121ytt(1)用最小二乘法建立关于确定1x，2x和3x的数学模型。(2) 写出 Gauss-Newton法迭代公式的具体形式。数学模型为：)()(minxfxfT21312213122131221312213154321)186.011 .0()126.0212()076.021()219.0212()126. 01()()()()()()(xxxxxxxxxxxxxxxxxxxxfxfxfxfxfxf迭代公式为：kTkkTkkkfAAAxx11)(nkmkmnkkTkm

12、TkkxxfxxfxxfxxfxfxfxA)()()()()()()(111114.修正 Gauss-Newton法精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 6 页，共 8 页7 先确定一个搜索方向，从kx出发作直线搜索来求下一个迭代点1kx。当kTkAA非奇异时，将 Gauss-Newton法解出来的kp作为搜索方向，否则将负梯度方向作为搜索方向。下面证明 Gauss-Newton法解出来的kp是目标函数的一个下降方向。miiTxfxfxfxs12)()()()(miTiixfxAxfxfxs1)()(2)()(2)(kTkkTkkfAAA

13、p1)(0)()(2)(1kTkkTkTkTkkTkfAAAfApxs因此 Gauss-Newton法解出来的kp是目标函数的一个下降方向。5.阻尼最小二乘法Gauss-Newton法收敛速度一般是较快的。 它遇到的主要问题是kTkAA可能为奇异，以至kTkkTkkfAAAp1)(无法求出。遇到这种情况，修正Gauss-Newton法是用负梯度方向代替kp，这时 Gauss-Newton法变为梯度法，收敛速度减慢。阻尼最小二乘法将从另一个角度来克服上述困难。1)基本想法Gauss-Newton法是用方程kTkkTkfApAA来确定kp的。现在矩阵kTkAA对角线上的元素都加上同一个数0，则上述

14、方程变为：kTkkTkfApIAA)(这样做的目的是：即使kTkAA奇异，只要将取得充分大，总能使)(IAAkTk正定，从而kTkkTkAApIAA)(肯定有解。这个解依赖于，记为)(kp。当0时，)0(kp就是 Gauss-Newton方向。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 7 页，共 8 页8 当已 经 增大 到 与kTkAA的 每 个 分 量 相 比 这 些 分 量 都 趋 于 消 失 ， 则kTkkTkfApIAA)(变为kTkfAIp，这就是说，当很大时，)(kp将接近负梯度方向。可以想象，当从零增大到无穷大时，)(kp将从

15、 Gauss-Newton方向连续地转向负梯度方向kTkfA。由以上的分析，可构成如下的迭代格式：kTkkkTkkkfAIAAxx11)(这就是阻尼最小二乘法的迭代公式，称为阻尼因子。最后说明一下阻尼最小二乘法的由来。当0时，kTkkTkkfAAAp1)(。当充分大时，kTkfAIp，即kTkfAp1，特别当时，0)(kp。因此起着使步长)(kp缩短或阻尼作用，这就是阻尼最小二乘法的由来。作业: 1.用最速下降法求解22122214minxxxx，初始点取为Tx 1 , 1 0。2.用 Newton法求解3123222118294minxxxxx，初始点任取。3.用单纯形替换法求解22214minxx，初始点取为Tx 2, 20，初始单纯形取为正三角形，边长为1.0。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 8 页，共 8 页