最小二乘法
? 一、线性最小二乘法
? 二、非线性最小二乘法
? 1.改进的 Gauss-Newton法
? 2.Levenberger-Marquart方法
一、线性最小二乘法
)()()(m in)(.1 xfxfxSP T?
满足）的最优解问题（ *xP.2
bAx)x(f ??这里
mnnm Rb,Rx,RA ??? ?
bAAxA TT ?
2bAx ??
bbAxbAxAx)x(S"" TTTT ???? 2证明：
022)( ???? bAAxAxS TT
δx"" * ???? x
22 b)x(AbAx * ???? ?
)bAx(AAbAx *TT* ????? ?? 222
22 ?AbAx * ???
0 时取到最小值.可见，当δ ?
)(2 *22* bAAxAAbAx TTT ????? ??
])*([])*([ ?? AbAxAbAx T ?????
例 ?
?
?
?
?
??
??
??
程组试用最小二乘法求此方给定方程组,
34
12
322
21
21
21
xx
xx
xx
的近似解。
解：,)44()12()322()( 221221221 ????????? xxxxxxxF令
。则原问题化为 )(m i n xFRx ?
，记
?
?
?
?
?
?
?
?
?
?
??
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??
3
1
3
,,
41
21
22
2
1 b
x
x
xA
。则 )()()( bAxbAxxF T ???
,
246
66
41
21
22
422
112
??
?
??
?
?
?
?
?
?
?
?
?
?
?
?
??
?
?
??
?
?
?? AA T
。?
?
?
??
?
?
?
?
?
?
?
?
?
?
?
?
??
?
??
?
?
?
16
10
3
1
3
422
112
bA T
。
?
?
?
?
?
?
?
?
?
?
?
?
?? ?
18
1
18
1
18
1
9
2
)( 1AA T
bAAAx TT 1)(* ???
。
?
?
?
?
?
?
?
?
?
?
??
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
3
1
3
4
16
10
18
1
18
1
18
1
9
2
二,非线性最小二乘法
1.一般形式, 2)()()()(m i n xfxfxfxS T ??;),.,,,,(
))(),.,,,(),(()(
21
21
T
n
T
m
xxxx
xfxfxfxf
?
?其中：
线性最小二似非线性函数，再模仿思想：用线性函数来近
乘法求解。
,))(()()( kkk xxxAxfxf ???所以
。),.,,,2,1(),()()()( mixxxfxfxf kTkikii ?????
则由泰勒公式可知，次的迭代点设已知第 kxk
。其中
nm
j
k
i
xx
n
mm
n
k
x
xf
x
f
.,,
x
f
x
f
.,,
x
f
xA
k
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
? )
)(
()(
1
1
1
1
???
分析求解.2
22 )()()()( kk
kkkk xfdAxxAxfxS ?????
。其中,kk xxd ??
法可得问题，由线性最小二乘对于 )(m i n x?
可逆时则有当 kTk AA
则有记,)( kk xAA ?
,])([])([ kkkTkkk xfdAxfdA ???
)(m i n,])([])([)( xxfdAxfdAx kkkTkkk ?? 则可用记 ???
题的极小点。问题的极小点近似原问
)( kTkkkTk xfAdAA ?? )1(
)()( 1 kTkkTkk xfAAAd ??? )2(
? ?
收敛阶至少是二阶的。当
是收敛的由迭代得到的则：
，充分接近）满足一定条件且（性质：若
,0*)()2(;)1(
*0
?xf
x
xxxf
k
3.改进的 Gauss-Newton法：
)()( 11 kTkkTkkkkk xfAAAxdxx ?? ????
，则有迭代公式令 kkk dxxx ???? 1
,)()(2)()(2)( 1?? ???? mi Tii xfxAxfxfxS因为
矩阵。的在点是则 H e s s exxH kk )(?,2 kTkk AAH ?记
）式可改写为（ 1
)( kkk xSdH ??? )4(
)3(
)(1 kkk xSHd ??? ?即 )5(
所以 )(11 kkkk xSHxx ??? ?? )6(
公式，式称为 N e w t onG au s s ?)6(
方向。）式称为（ N ewt o nG a us s ?5
。令 )()()(2 )( kTkkkTkk xfAxfxAxSg ????
则由其正定性可知：存在若,)( 1?kTk AA
为下降方向kd? 0)(2)( 1 ???? ? kkTkTkkTk gAAgdxS
。奇异，则解不出否则，若 kkTk dAA 。此时令 kk gd ??
算法（共五步）改进的 N ewt o nG a us s ?
。已知：
nmj
iT
m
x
fxAxfxfxf
??
?
?
?
???
?
?
??? )(;))(),..,,(()(
1
。精度给定初始点 0,:1 0 ??xS t e p 。令 0:?k;)(:2 )( k
j
k
ik
ij Ax
xfaS t e p ?
?
??计算：
。?
?
???? m
i kj
k
ik
i
k
j gx
xfxfg
1
)( )()(
??
?
????
??? ?
nAr a n kxfAg
nAr a n kxfAAAdS t e p
kT
kk
kT
kk
T
kk
)()(
)()()(:3 1
如果
如果令
。其中令 )(m i n:,:4 1 kktkkkkk tdxftdtxxS t e p ?????
。转
否则算法结束则若
2,1,
,;,,||)(||:5 1*
S t e pkk
xxxfAS t e p kkTk
??
?? ??
三,Levenberger-Marquart方法
时，迭代无法继续！）接近于（条件数
为奇异或法的迭代中，当
1
)()(.1
1 BB
xAxABN e w t o nG a u s s T
?
??
?
迭代继续！
的对角元的措施使方法采用适当增加 )()(.2 xAxAML T?
方程组：方法求解如下满足当前的迭代点 MLxSx kk ???,0)(.3
( ** ))()()(:))()(( kTkkkTk xfxAzxCzIxAxA ???? ?
过大！能够成立又不至于使为正定，且
中不断调整使是一个正数，它在迭代其中
?
?
)()(
)(:
1 kk
k
xSxS
xC
??
。得到下一迭代点然后令 11 ?? ?? kkk xzxx
!
)(
3
0.4
敛速度的增加，否则将影响收尽可能限制
方向。因而充分大时便接近负梯度偏移，当
方向逐步向负梯度表明方向的增大，下面的性质
方向；随着就是，得到的若取
?
?
??
XS
z
N ew t o nG a u s sz
??
??
）的解，那么有：是方程组（，设 **0.5 z??
))()()()(1 22 zyzxAxfyxAxf kkkk ????? （：性质
).()(2 kk xSzxS ??适当大，总成立：：只要性质 ?
充分接近。与方向充分大时，方向：当性质 )(3 kxSz ???
。并返回：则令若 1),()(:2 S t e pxSzxSS t e p ??? ???
放大。遇到困难时将
缩小，迭代：一次成功迭代后将采用进退方法调整
?
??.6
调整算法：?.7
。的初值，控制终止常数，初始点给定
和步长缩小因子子初始：给定步长放大因
??
??
xxf ),(
,101 ???
。得求解 zxfxAzIxAxAS t e p TT )()())()((:1 ??? ?
。否则返回
则迭代终止，）（若令
1
)(;,::3
S t e p
xfxAzxxS t e p T ???? ????
? 一、线性最小二乘法
? 二、非线性最小二乘法
? 1.改进的 Gauss-Newton法
? 2.Levenberger-Marquart方法
一、线性最小二乘法
)()()(m in)(.1 xfxfxSP T?
满足）的最优解问题（ *xP.2
bAx)x(f ??这里
mnnm Rb,Rx,RA ??? ?
bAAxA TT ?
2bAx ??
bbAxbAxAx)x(S"" TTTT ???? 2证明：
022)( ???? bAAxAxS TT
δx"" * ???? x
22 b)x(AbAx * ???? ?
)bAx(AAbAx *TT* ????? ?? 222
22 ?AbAx * ???
0 时取到最小值.可见，当δ ?
)(2 *22* bAAxAAbAx TTT ????? ??
])*([])*([ ?? AbAxAbAx T ?????
例 ?
?
?
?
?
??
??
??
程组试用最小二乘法求此方给定方程组,
34
12
322
21
21
21
xx
xx
xx
的近似解。
解：,)44()12()322()( 221221221 ????????? xxxxxxxF令
。则原问题化为 )(m i n xFRx ?
，记
?
?
?
?
?
?
?
?
?
?
??
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??
3
1
3
,,
41
21
22
2
1 b
x
x
xA
。则 )()()( bAxbAxxF T ???
,
246
66
41
21
22
422
112
??
?
??
?
?
?
?
?
?
?
?
?
?
?
?
??
?
?
??
?
?
?? AA T
。?
?
?
??
?
?
?
?
?
?
?
?
?
?
?
?
??
?
??
?
?
?
16
10
3
1
3
422
112
bA T
。
?
?
?
?
?
?
?
?
?
?
?
?
?? ?
18
1
18
1
18
1
9
2
)( 1AA T
bAAAx TT 1)(* ???
。
?
?
?
?
?
?
?
?
?
?
??
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
3
1
3
4
16
10
18
1
18
1
18
1
9
2
二,非线性最小二乘法
1.一般形式, 2)()()()(m i n xfxfxfxS T ??;),.,,,,(
))(),.,,,(),(()(
21
21
T
n
T
m
xxxx
xfxfxfxf
?
?其中：
线性最小二似非线性函数，再模仿思想：用线性函数来近
乘法求解。
,))(()()( kkk xxxAxfxf ???所以
。),.,,,2,1(),()()()( mixxxfxfxf kTkikii ?????
则由泰勒公式可知，次的迭代点设已知第 kxk
。其中
nm
j
k
i
xx
n
mm
n
k
x
xf
x
f
.,,
x
f
x
f
.,,
x
f
xA
k
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
? )
)(
()(
1
1
1
1
???
分析求解.2
22 )()()()( kk
kkkk xfdAxxAxfxS ?????
。其中,kk xxd ??
法可得问题，由线性最小二乘对于 )(m i n x?
可逆时则有当 kTk AA
则有记,)( kk xAA ?
,])([])([ kkkTkkk xfdAxfdA ???
)(m i n,])([])([)( xxfdAxfdAx kkkTkkk ?? 则可用记 ???
题的极小点。问题的极小点近似原问
)( kTkkkTk xfAdAA ?? )1(
)()( 1 kTkkTkk xfAAAd ??? )2(
? ?
收敛阶至少是二阶的。当
是收敛的由迭代得到的则：
，充分接近）满足一定条件且（性质：若
,0*)()2(;)1(
*0
?xf
x
xxxf
k
3.改进的 Gauss-Newton法：
)()( 11 kTkkTkkkkk xfAAAxdxx ?? ????
，则有迭代公式令 kkk dxxx ???? 1
,)()(2)()(2)( 1?? ???? mi Tii xfxAxfxfxS因为
矩阵。的在点是则 H e s s exxH kk )(?,2 kTkk AAH ?记
）式可改写为（ 1
)( kkk xSdH ??? )4(
)3(
)(1 kkk xSHd ??? ?即 )5(
所以 )(11 kkkk xSHxx ??? ?? )6(
公式，式称为 N e w t onG au s s ?)6(
方向。）式称为（ N ewt o nG a us s ?5
。令 )()()(2 )( kTkkkTkk xfAxfxAxSg ????
则由其正定性可知：存在若,)( 1?kTk AA
为下降方向kd? 0)(2)( 1 ???? ? kkTkTkkTk gAAgdxS
。奇异，则解不出否则，若 kkTk dAA 。此时令 kk gd ??
算法（共五步）改进的 N ewt o nG a us s ?
。已知：
nmj
iT
m
x
fxAxfxfxf
??
?
?
?
???
?
?
??? )(;))(),..,,(()(
1
。精度给定初始点 0,:1 0 ??xS t e p 。令 0:?k;)(:2 )( k
j
k
ik
ij Ax
xfaS t e p ?
?
??计算：
。?
?
???? m
i kj
k
ik
i
k
j gx
xfxfg
1
)( )()(
??
?
????
??? ?
nAr a n kxfAg
nAr a n kxfAAAdS t e p
kT
kk
kT
kk
T
kk
)()(
)()()(:3 1
如果
如果令
。其中令 )(m i n:,:4 1 kktkkkkk tdxftdtxxS t e p ?????
。转
否则算法结束则若
2,1,
,;,,||)(||:5 1*
S t e pkk
xxxfAS t e p kkTk
??
?? ??
三,Levenberger-Marquart方法
时，迭代无法继续！）接近于（条件数
为奇异或法的迭代中，当
1
)()(.1
1 BB
xAxABN e w t o nG a u s s T
?
??
?
迭代继续！
的对角元的措施使方法采用适当增加 )()(.2 xAxAML T?
方程组：方法求解如下满足当前的迭代点 MLxSx kk ???,0)(.3
( ** ))()()(:))()(( kTkkkTk xfxAzxCzIxAxA ???? ?
过大！能够成立又不至于使为正定，且
中不断调整使是一个正数，它在迭代其中
?
?
)()(
)(:
1 kk
k
xSxS
xC
??
。得到下一迭代点然后令 11 ?? ?? kkk xzxx
!
)(
3
0.4
敛速度的增加，否则将影响收尽可能限制
方向。因而充分大时便接近负梯度偏移，当
方向逐步向负梯度表明方向的增大，下面的性质
方向；随着就是，得到的若取
?
?
??
XS
z
N ew t o nG a u s sz
??
??
）的解，那么有：是方程组（，设 **0.5 z??
))()()()(1 22 zyzxAxfyxAxf kkkk ????? （：性质
).()(2 kk xSzxS ??适当大，总成立：：只要性质 ?
充分接近。与方向充分大时，方向：当性质 )(3 kxSz ???
。并返回：则令若 1),()(:2 S t e pxSzxSS t e p ??? ???
放大。遇到困难时将
缩小，迭代：一次成功迭代后将采用进退方法调整
?
??.6
调整算法：?.7
。的初值，控制终止常数，初始点给定
和步长缩小因子子初始：给定步长放大因
??
??
xxf ),(
,101 ???
。得求解 zxfxAzIxAxAS t e p TT )()())()((:1 ??? ?
。否则返回
则迭代终止，）（若令
1
)(;,::3
S t e p
xfxAzxxS t e p T ???? ????
