第五章 最小二乘问题的解法1.最小二乘问题 1)回归方程问题[]Ti i l i yt t)()()(1,,...,,m i ,...,2,1=是m 个实验点。

现要根据这些点确定y 与l 个物理量l t t t ,...,,21之间的关系式。

设这种关系式为),...,,,...,(11n l x x t t F y =，其中n x x ,...,1是方程中需要待定的n 个参数(系数)。

因此问题是如何通过)(n m m >个实验点，确定方程中的系数。

由于实验点的个数大于待定系数的个数，因此方程中系数的确定是一个超静定问题，无法按一般的方法进行求解。

此时将实验点到曲面距离最短的那个曲面作为所求曲面，从而求取该曲面方程。

即求解[]∑=-mi i i y x t F 12)()(),(min ，这就是最小二乘问题。

2)非线性方程组问题求解非线性方程组⎪⎪⎩⎪⎪⎨⎧===0),...,(. 0),...,(0),...,(11211n n n n x x f x x f x x f 可转化为求解如下形式的最小二乘问题。

∑=mi n i x x f 112),...,(min显而易见，最小二乘法的一般形式可写为)()(minx f x f T最小二乘法问题实际上是具有n 个变量的无约束极小化问题，前面解无约束优化问题的方法均可应用。

但是最小二乘问题具有一定的特殊性，即目标函数的表达式是由多个表达式的平方和组成，理应有更、更有效的方法。

这正是最小二乘解法要解决的问题。

2.线性最小二乘问题的解法最小二乘法的一般形式可写为)()(min x f x f T特别地，当b Ax x f -=)(，即)(x f 为线性函数时，则最小二乘问题可表示为：2min bAx -1) 线性最小二乘问题解的条件定理1:*x 是线性最小二乘问题极小点的充要条件是*x 满足b A Ax A TT =。

证明：(1)必要性 令2)(bAx x s -=，于是有：bb Ax b b A x Ax A x b Ax b A x b Ax b Ax x s TTTTTTTTTT+--=--=--=))(()()()(由于b A x T T 是一个数，而一个数的转置是它的本身，因此有：Axb A x b b A x b A x TTT T T TTTTT===)()(故上式可化为：bb Ax b Ax A x x s TTTT+-=2)(b A Ax A x s TT22)(-=∇若*x 是)(x s 的极小点，则必有0)(=∇x s ，则必有：b A Ax A TT =(2)充分性 若*x 满足bA Ax A TT =*，即0)(*=-b Ax A T考虑任一点n R z x v ∈+=*，计算)(2)()()()()()())(())(()(*22*******2*2b Ax A z AzbAx Az Az b Ax A z Az b Ax b Ax b Ax Az b Ax Az b Ax bz x A bAv T T TTTTTT -++-=+-+-+--=+-+-=-+=- 由于上式第二项大于等于零，第三项为零，故*x 是极小点。

我们称b A AxA TT =为最小二乘问题的法方程组。

由上述定理可知，求解最小二乘问题等价于求解它的法方程组。

2)法方程组的解法 由于02≥=AvAv A v T T ，所以A A T 至少是半正定的，因此法方程组有解的条件是A A T 正定。

定理2:设A 是n m ⨯矩阵)(n m >，则A A T 正定的充要条件是A 的秩为n 。

推论1:当A 的秩为n 时，则b A A A x T T 1)(-=是最小二乘的唯一解。

推论2:设A 是n m ⨯矩阵)(n m ≤，则T AA 正定的充要条件是A 的秩为m 。

推论3: 设A 是n m ⨯矩阵)(n m >，则T AA 正定的充要条件是A A T 为非奇异。

上述解法方程组的解法需要A A T 正定，实际问题并不能保证A A T 正定，因此上述方法仅具有理论意义。

3)用QR 分解求线性最小二乘解 若Q 是m m ⨯正交矩阵T Q Q =-1，则22)()()()()(b Ax b Ax b Ax b Ax Q Q b Ax b ax Q TT T -=--=--=-上式说明以2)(b Ax Q -为目标函数的最小二乘解与目标函数为2bAx -的最小二乘解具有相同的解。

因此求解2minbAx -可转化为求解2mincRx -，其中QA R =，Qb c =。

由线性代数可知，适当地选择正交矩阵Q ，总可使QA R =呈现为如下形式的矩阵：⎥⎦⎤⎢⎣⎡=O U R ，其中U是n r ⨯的秩为r 的上梯形矩阵；O 是n r m ⨯-)(的零矩阵。

定理: 线性最小二乘问题2min bAx -与线性方程组pUx=具有相同解。

其中p 是由Qb c =的前r 个分量组成的r 维向量。

证明：由于2minbAx -的解与2mincRx -的解相同。

现只需证明2mincRx -与pUx =具有相同的解。

2min cRx -的法方程组为cR RxR TT =，即cR RxR TT =的解就是2mincRx -的解。

将⎥⎦⎤⎢⎣⎡=O U R 代入上式有：⎥⎦⎤⎢⎣⎡⎥⎦⎤⎢⎣⎡=⎥⎦⎤⎢⎣⎡⎥⎦⎤⎢⎣⎡q p O U x O U O U TT，上式展开后得：pUUx U TT =而在pUx=的两侧同时左乘T U 即得pUUxU TT =。

若n U r =)(。

最小二乘问题的解为p U x 1-=。

否则最小二乘问题的解不是唯一的，在这种情况下，通常取具有最小范数的解作为最小二乘问题的解。

这个解称为最小二乘问题的极小最小二乘解。

这个解为pUUU x TT 1)(-=，且解是唯一的。

pUUU x TT1)(-=显然是pUx=的一个解。

设y 是pUx=的另一个解。

则0)(=-y x U)(2)(2222y x x yx xy x x yT---+=--=0)(])[()(1=-=--y x U UUp y x x TTTT因为0>-y x ，所以22xy>。

因此极小最小二乘解是唯一的。

3.Gauss-Newton 法Gauss-Newton 法适用于非线性最小二乘问题)()()(x f x f x s T=。

Gauss-Newton法是一种迭代算法。

假定选定初始点0x 后经过迭代已求得k x 。

现考虑1+k x 的求法。

首先把)(x f 线性化，用线性最小二乘问题的解去逼近非线性最小二乘问题的解。

把)(x f 的第i 个分量)(x f i 在点k x 处用Taylor 展开式展开。

)()()()(k Tk i k i i x x x f x f x f -∇+≈，mi , (1)则))(()()(k k k x x x A x f x f -+=，其中：⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎣⎡∂∂∂∂∂∂∂∂=⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡∇∇=n k m k m n k k T k m Tk k x x f x x f x x f xx f x f x f x A )()()()()()()(11111记)(k k x f f =，)(k k x A A =，则2)()(k k k x x A f x s -+≈如设线性最小二乘问题kk f p A +min 的解为k p ，那么kk k p x x +=+1就是极小点的新的近似解。

由前述可知，kTk k T k kf A A A p 1)(--=，则kTk k T k k k f A A A x x11)(-+-=。

当)(x f 满足一定的条件，并且0x 充分靠近极小点时，算法是收敛的。

假如在某次迭代中k T kA A变成奇异的，那么上述方法失效，另外，当0x 离极小点较远时，算法可能发散。

例：设有非线性方程组⎩⎨⎧=-+==-+=022)(012)(21222211x x x f x x x f(1)列出求解这个方程组的非线性最小二乘问题的数学模型。

(2)写出Gauss-Newton 法迭代公式的具体形式。

数学模型为：))22()12min((22122221-++-+x x x x迭代公式为：kTk k Tk k k f A A A x x11)(-+-=[]Tx x x x x f 2212)(212221-+-+=⎥⎦⎤⎢⎣⎡=1242)(21x x x A例：已知某物理量y 与另两个物理量1t 和2t 的依赖关系为22111311t x t x t x x y ++=，其中1x ，2x 和3x 是待定参数。

为确定这三个参数测得21,t t 和y 的5组数据：186.0126.0076.0219.0126.0000.0000.2000.2000.1000.1100.0000.2000.1000.2000.121yt t(1)用最小二乘法建立关于确定1x ，2x 和3x 的数学模型。

(2) 写出Gauss-Newton 法迭代公式的具体形式。

数学模型为：)()(minx f x f T⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡-+-++-++-++-++=⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡=21312213122131221312213154321)186.011.0()126.0212()076.021()219.0212()126.01()()()()()()(x x x x x x x x x x x x x x x x x x x x f x f x f x f x f x f迭代公式为：kTk k T k k k f A A A x x11)(-+-=⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎣⎡∂∂∂∂∂∂∂∂=⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡∇∇=n k m k m n k k T k m Tk k x x f x x f x x f xx f x f x f x A )()()()()()()(111114.修正Gauss-Newton 法先确定一个搜索方向，从k x 出发作直线搜索来求下一个迭代点1+k x 。

当k T kA A非奇异时，将Gauss-Newton 法解出来的k p 作为搜索方向，否则将负梯度方向作为搜索方向。

下面证明Gauss-Newton 法解出来的k p 是目标函数的一个下降方向。

∑===mi i Tx f x f x f x s 12)()()()(∑==∇=∇mi Ti i x f x A x f x f x s 1)()(2)()(2)(kTk k T k k f A A A p 1)(--=0)()(2)(1<-=∇-k Tk k Tk Tk Tk k Tk f A A A f A p x s因此Gauss-Newton 法解出来的k p 是目标函数的一个下降方向。