其中0<o1<O2<1.Gauss-Newton算法产生的迭代点列{xk}收 敛到(7.1)的一个稳定点.即 lim J(k)TF(xk)=0. 证明由J(x)在C(axo)上Lipschitz连续可知J(x)连续.由于水 平集C(xo)有界，故存在B>0使得对任意x∈C(xo),‖J(x)川≤B成 立.记0k为Gauss-Newton方向dW与负梯度方向-gk的夹角.利用 一致性条件(7.2)，我们有 grdgN F JdGN cos 0= llgkllldenl 川ENJF ‖JdeN2 、a2lv2 a2 ldeN JdgNl T之2IgNp=>0. 由于g(x)在C(xo)上Lipschitz连续，则由(7.3)的第二式得 (o2-1)gkdk≤[g(ck+a%d)-9Td4≤aLd2. Back Close
6/33 JJ II J I Back Close Ÿ• 0 < σ1 < σ2 < 1. Gauss-Newton é{)Sì: {xk} ¬ Ò (7.1) òá½:. = lim k→∞ J(xk) TF(xk) = 0. y² d J(x) 3 L(x0) ˛ Lipschitz ÎYå J(x) ÎY. duY ²8 L(x0) k., 3 β > 0 ¶È?ø x ∈ L(x0), kJ(x)k ≤ β § ·. P θk è Gauss-Newton êï d GN k ÜKF›êï −gk Y. |^ òó5^á (7.2), ·Çk cos θk = − g T k d GN k kgkkkd GN k k = − F T k Jkd GN k kd GN k kkJ T k Fkk = kJkd GN k k 2 kd GN k kkJ T k Jkd GN k k ≥ α 2kd GN k k 2 β 2kd GN k k 2 = α 2 β 2 > 0. du g(x) 3 L(x0) ˛ Lipschitz ÎY, Kd (7.3) 1™ (σ2 − 1)g T k dk ≤ [g(xk + αkdk) − gk] T dk ≤ αkLkdkk 2
故 a% 02-1 gfdk L ldx2 将其代入(7.3)的第一式得 f-k1≥-1afd4≥mL 1-02(gdk)2 gl cos0 =01L 两边对k求级数，利用{f}单调不增有下界，得到 ●X 2aac 由此可得 lim g lim J()F(k)=0. k>o k→0∞ 证毕 Back Close
7/33 JJ II J I Back Close αk ≥ σ2 − 1 L g T k dk kdkk 2 . ÚŸì\ (7.3) 1ò™ fk − fk+1 ≥ −σ1αkg T k dk ≥ σ1 1 − σ2 L (g T k dk) 2 kdkk 2 = σ1 1 − σ2 L kgkk 2 cos2 θk. ¸>È k ¶?Í, |^ {fk} ¸NÿOke., X ∞ k=1 kgkk 2 cos2 θk < ∞. ddå lim k→∞ gk = lim k→∞ J(xk) TF(xk) = 0. y.
定理7.2设单位步长的Gauss-Newton算法产生的迭代点列{ck} 收敛到(71)的局部极小点x*,而且J(x*)TJ(x)正定.则当J(z)TJ(x), S(x),[J(x)1J(c)]-1在x*的邻域内Lipschitz连续时，对充分大的k, 有 ck+1-x*‖≤l[J(e*)TJ(x*】厂llS(x*）川xk-x*‖+O(2ck-x*2). 证明由于J(x)TJ(x),S(x),[J(x)TJ(x)】-1在x*的邻域内Lipschitz 连续，故存在6>0及正数α，B,y使得对任意x,y∈N(x*,0)有， IS(z)-S()l≤ax-y IJ(x)TJ(x)-J(y)TJ(y)川≤lx-y, (7.4) l[J(x)J(x-1-[J(y)J(y]-‖≤ylx-y. 由于f(x)二阶连续可微，G(x)=J(x)J(x)+S(x)在N(x*,δ)上 Lipschitz连续，故对充分大的k和模充分小的h∈R”,有xk+h∈ Back Close
8/33 JJ II J I Back Close ½n 7.2 ¸†⁄ Gauss-Newton é{)Sì: {xk} ¬Ò (7.1) ¤‹4: x ∗ , Ö J(x ∗ ) T J(x ∗ ) ½. K J(x) T J(x), S(x), [J(x) T J(x)]−1 3 x ∗ çS Lipschitz ÎYû, Èø©å k , k kxk+1 − x ∗ k ≤ k[J(x ∗ ) T J(x ∗ )]−1 kkS(x ∗ )kkxk − x ∗ k + O(kxk − x ∗ k 2 ). y² du J(x) T J(x), S(x), [J(x) T J(x)]−1 3 x ∗ çS Lipschitz ÎY, 3 δ > 0 9Í α, β, γ ¶È?ø x, y ∈ N(x ∗ , δ) k, kS(x) − S(y)k ≤ αkx − yk kJ(x) T J(x) − J(y) T J(y)k ≤ βkx − yk, k[J(x) T J(x)]−1 − [J(y) T J(y)]−1k ≤ γkx − yk. (7.4) du f(x) ÎYåá, G(x) = J(x) T J(x) + S(x) 3 N(x ∗ , δ) ˛ Lipschitz ÎY, Èø©å k ⁄ ø© h ∈ Rn , k xk + h ∈
N(x*,6),且 g(k+h)=g(k)+G(Zk)h+O(lh2). (7.5) 由于xk→x*,对充分大的k,有xk,Tk+1∈N(x*,δ).令ek=xk一x*, hk=xk+1-xk,则 g(x*)=g(xk-ek)=0. 利用(7.5)， g(k)-G(Zk)ex:+O(llekl2)=0. 即 F-(J+S)ek+O(llekl2)=0. 注意到JF=-(JJ)(xk+1-x)=-JJhk.两边同乘(JJ)-1, -hk-ek-()Skek+(J-O(llekl2)=0. Back Close
9/33 JJ II J I Back Close N(x ∗ , δ), Ö g(xk + h) = g(xk) + G(xk)h + O(khk 2 ). (7.5) du xk → x ∗ , Èø©å k , k xk, xk+1 ∈ N(x ∗ , δ). - ek = xk − x ∗ , hk = xk+1 − xk, K g(x ∗ ) = g(xk − ek) = 0. |^ (7.5), g(xk) − G(xk)ek + O(kekk 2 ) = 0. = J T k Fk − (J T k Jk + Sk)ek + O(kekk 2 ) = 0. 5ø J T k Fk = −(J T k Jk)(xk+1 − xk) = −J T k Jkhk. ¸>”¶ (J T k Jk) −1 , −hk − ek − (J T k Jk) −1Skek + (J T k Jk) −1O(kekk 2 ) = 0
所以 k+1-x*=hk+ek=-(J)Skek+(JJ)O(llek2) 两边取2范数， l+1-x*‖≤Il(JRJ)-1 Sek‖+I(JgJ)1‖·O(Ilex2). 由于[J(x)TJ(x)-1在x*处连续，故在k充分大时， I(JJk)-‖≤2[J(x*)J(x*)]- (7.6) 从而 lx+1-x‖≤I(JJ)-1 Sk-x*‖+O(xk-x*2). (7.7） Back Close
10/33 JJ II J I Back Close §± xk+1 − x ∗ = hk + ek = −(J T k Jk) −1Skek + (J T k Jk) −1O(kekk 2 ). ¸> 2 âÍ, kxk+1 − x ∗ k ≤ k(J T k Jk) −1Skkkekk + k(J T k Jk) −1 k · O(kekk 2 ). du [J(x) T J(x)]−1 3 x ∗ ?ÎY, 3 k ø©åû, k(J T k Jk) −1 k ≤ 2k[J(x ∗ ) T J(x ∗ )]−1 k. (7.6) l kxk+1 − x ∗ k ≤ k(J T k Jk) −1Skkkxk − x ∗ k + O(kxk − x ∗ k 2 ). (7.7)