《最优化方法》课程教学资源（题解）第七次 最小二乘法

最小二乘法 一、线性最小二乘法 非线性最小二乘法 1.改进的 Gauss- Newton法 2. Levenber ger- Marquart方法

最小二乘法 • 一、线性最小二乘法 • 二、非线性最小二乘法 • 1.改进的Gauss-Newton法 • 2.Levenberger-Marquart方法

线性最小二乘法 1. (P) min S()=f(x)f(x) Ax-b 这里∫(x)=Ax-b A∈R"M,x∈R",b∈Rm 2.问题(P)的最优解x满足 A Ax=a b

一、线性最小二乘法 1. (P) min S(x) f (x) f (x) T = 2.问题（P）的最优解 x * 满 足 这 里 f ( x ) = Ax − b m n n m A R , x  R , b  R  A Ax A b T T = 2 = Ax − b

证明"→"S(x)=x TATAx-2baxtbb VS(x=2A Ax-2A b=0 "<"Vx=x"+6 4x-b2=|(x2+6)- =(4x*-b)+A8[(4x*-b)+A6 b+|4。+20A(Ax-b Ax-b+|4|2+26(4Ax-4b) Ax +|A6 可见,当δ=0时取到最小值

" " S( x ) x A Ax b Ax b b T T T T 证明： = − 2 + S(x) = 2A Ax − 2A b = 0 T T ""  x = x * +δ 2 2 Ax b A( x ) b * − = +  − Ax b A A ( Ax b ) * T T * = − +  + 2 − 2 2 2 2 Ax b A * = − + 可见，当δ= 0时取到最小值. 2 ( ) 2 * 2 * Ax b A A Ax A b T T T = − +  +  − [(Ax * b) A ] [(Ax * b) A ] T = − + − +

2x,+2x,=3 例给定方程组x1-2x2=1,试用最小二乘法求此方程组 x,+4x,=3 的近似解。 解:令F(x)=(2x1+2x2-3)2+(x1-2x2-1)2+(x1+4x2-4)2, 则原问题化为minF(x)。 x∈ 22 3 记A=1-2,x b=1 则F(x)=(4x-b)(4x-b)

例      + = − = + = 给定方程组 ,试用最小二乘法求此方程 组 4 3 2 1 2 2 3 1 2 1 2 1 2 x x x x x x 的近似解。 解： ( ) ( 2 2 3) ( 2 1) ( 4 4) , 2 1 2 2 1 2 2 令 F x = x1 + x2 − + x − x − + x + x − 则原问题化为 min xR F(x) 。 记 ，           =       =           = − 3 1 3 , , 1 4 1 2 2 2 2 1 b x x A x 则 F(x) = (Ax − b) T (Ax − b)

22 21 66 2-2 624 211 10 Ab 16 (4A) 918 1818 2 10 ∴x=(4A)Ab 1818 3

, 6 24 6 6 1 4 1 2 2 2 2 2 4 2 1 1       =           −       −  A A = T 。      =                 − = 16 10 3 1 3 2 2 4 2 1 1 A b T 。           − −  = − 18 1 18 1 18 1 9 2 ( ) 1 A A T x A A A b T 1 T * ( ) −  = 。           =                − − = 3 1 3 4 16 10 18 1 18 1 18 1 9 2

二、非线性最小二乘法 1一般形式:minS(x)=∫(x)f(x)=|f(x)2 其中:f(x)=(f1(x),f2(x),,fn(x) X=r,x 思想:用线性函数来近似非线性函数,再模仿线性最小二 乘法求解

二、非线性最小二乘法 1.一般形式： 2 min S(x) f (x) f (x) f (x) T = = ( , ,..., ) ; ( ) ( ( ), ( ),..., ( )) 1 2 1 2 T n T m x x x x f x f x f x f x = 其中： = 思想：用线性函数来近似非线性函数，再模仿线性最小二 乘法求解

2.分析求解 设已知第次的迭代点x,则由泰勒公式可知 f(x)≈f(x^)+vf(x^)(x-x),(i=1,2,,m) 所以∫(x)≈f(x)+A(x4)(x-x), af af 其中A(x)=:: nxI af a =x

( ) ( ) ( )( ), k k k 所以 f x  f x + A x x − x f i (x)  f i (x k )+ f i (x k ) T (x − x k ),(i = 1,2,...,m)。 设已知第k次的迭代点x k ，则由泰勒公式可知 其 中 m n 。 j k i x x n m m n k x f x x f ... x f x f ... x f A x k  =   =                       = ) ( ) ( ) ( 1 1 1 1    2.分析求解

记A=A(x2),则有 S(x)xf(x)+A(x-x)=Akd+(rk) [A d +f(xl la d +f(xl, 其中:d=x-x 记φ(x)=[Ad+f(x)[Ad4+f(x2)],则可用ming(x) 问题的极小点近似原问题的极小点。 对于minp(x)问题,由线性最小二乘法可得 AkA d=-Akf() 当AA可逆时则有 d=-(AA)Af(x2)(2)

2 2 ( ) ( ) ( ) ( ) k k k k k k S x  f x + A x − x = A d + f x 其中：d k = x − x k 。 对于min(x)问题，由线性最小二乘法可得 当 k可逆时则有 T Ak A 记 Ak = A(x k ),则有 [ ( )] [ ( )], k k k k k T = Ak d + f x A d + f x (x) [ A d f (x )] [ A d f (x )], min (x) k k k k k T 记 = k + + 则可用  问题的极小点近似原问题的极小点。 ( ) T k k k k T Ak A d = −A f x (1) ( ) ( ) 1 T k k k T k k d A A A f x − = − (2)

令x4=x=x4+4,则有迭代公式 x=x4+d=x4-(4A)41f(x2)(3) 性质:若∫(x)满足一定条件且x充分接近x*, 则:(1)由迭代得到的{x“}是收敛的; (2)当∫(x)=0,收敛阶至少是二阶的。 3.改进的 Gauss-Newton法: 因为ⅴS(x)=2∑f(xv(x)=2A4(x)f(x), 记H=2AA,则H是q(x)在点x的Hese矩阵。 (1)式可改写为 VS(x)(4)

  当 收敛阶至少是二阶的。 则 ： 由迭代得到的 是收敛的 性质：若 （ ）满足一定条件且 充分接近 ， (2) ( *) 0, (1) ; * 0 f x = x f x x x k 3.改进的Gauss-Newton法： ( ) ( ) 1 1 T k k k T k k k k k x x d x A A A f x + − = + = − 令x k+1 = x = x k + d k，则有迭代公式 ( ) 2 ( ) ( ) 2 ( ) ( ), 1  =  =  = m i T 因为 S x f i x f i x A x f x 2 k , 则Hk 是 (x)在点x k的Hesse矩阵。 T 记 Hk = Ak A （1）式可改写为 ( ) k k Hk d = −S x (4) (3)

即d4=-HVS(x) 所以x+=x4-HVs(x)(6 (6)式称为GSs- Newton公式, (5)式称为 Gauss- Newton方向。 Vs(x o k A(x)f(x)=Af(x)。 2 若(4A)存在,则由其正定性可知: ⅴs(x)yd=-2g(44)g4<0→d为下降方向 否则,若44奇异,则解不出d。此时令d=-gk

( ) 1 k k k d = −H S x 即 − (5) 所以 ( ) 1 1 k k k k x = x − H S x + − (6) (6)式称为Gauss − Newton公式， （5）式称为Gauss − Newton方向。 令 ( ) ( ) ( )。 2 ( ) T k k T k k k k A x f x A f x S x g = =  = 若(Ak T Ak ) −1存在,则由其正定性可知： S(x k ) T d k = −2gk T (Ak T Ak ) −1 gk  0  d k为下降方向 否则，若Ak T Ak奇异，则解不出d k 。此时令d k = −gk