一种基于病态问题的修正牛顿法

一种基于病态问题的修正牛顿法

王小朋,刘翔峰

(武汉理工大学 理学院，湖北 武汉 430070)

摘要：针对初值在真解附近，由牛顿法得到的最终迭代结果远离真值的这一类病态问题,在对已有修正牛顿法进行研究的基础上，通过引入一个控制参数提出了一种新的修正牛顿法。进一步在完备的赋范线性空间中给出该修正牛顿法的收敛性证明与误差估计。最后，数值实验结果表明了这种新的修正牛顿法的有效性以及在收敛速度上的优越性。

关键词：完备的赋范线性空间；牛顿法；病态问题；Frechet可微

基金项目：国家自然科学基金项目(11201357)

作者简介：王小朋(1989-),男,山西汾阳人,硕士生，主要研究方向为最优化理论与应用.

收稿日期：2014-04-11

文章编号：1672-6871(2015)01-0086-06

中图分类号：O241.6

文献标志码：A

0引言

众所周知，无论是求解优化问题还是方程组问题，牛顿法都是一种最为常见的有效算法。但是牛顿法在每一次迭代的过程中不仅需要n2个偏导数，而且还要Hesse矩阵的逆。为了克服牛顿法计算量大的缺陷，许多学者对牛顿法进行了一系列的改进，例如简化的牛顿法、萨马斯基技巧、阻尼牛顿法、牛顿下山法、离散的牛顿法、割线法、修正牛顿法[1-6]等。纵观牛顿法的这些改进，其优势在于：第一，减少了原来牛顿法的计算量；第二，防止牛顿法在某一步迭代过程中出现偏导数不存在或Hesse矩阵奇异；第三，能够解决初值在真解附近，但是牛顿法所得的最终迭代结果却远离真值的这一类病态问题。对于这一类病态问题，就目前的研究现状而言，其研究成果相对较少。文献[1]虽然给出了一种求解这一类病态问题的修正牛顿法，但是仔细研究其算法证明和数值实验，发现该算法在收敛性证明过程中较为复杂，当取τk=2-k时算法收敛速度不是很快。本文将在原有修正牛顿法[1]的基础上，通过限制牛顿方向与引入控制参数相结合的方式来探讨这一病态问题的求解方法，从而给出一种新的修正牛顿法。

1迭代形式与算法

首先给出求解方程组g(x)=0的修正牛顿法迭代形式

(1)

对于上述提到的这一类病态问题可知：传统的牛顿法是失效的，但是添加修正项之后的牛顿法[1-2]却是收敛的。就牛顿法的迭代格式而言，可知式(1)中的

分别表示传统牛顿法的方向与修正牛顿法的方向。由优化理论知识可知：对于上述两种算法之所以出现两种相反结果的原因，可能是传统牛顿法的方向问题导致了算法出现病态，而添加修正项之后的牛顿法，正是由于对方向进行了适当的修正从而得到了相反的收敛结果。下文将在上述分析的基础上通过修正牛顿方向与引入参数相结合的方式，提出一种新的修正牛顿法来克服文献[1-2]中牛顿法的缺陷。

算法

步骤2利用迭代式

来求出x1。

2算法的收敛性分析

本节将在完备的赋范线性空间中给出算法1的收敛性证明。在此证明之前，首先给出完备的赋范线性空间中一些常用的定理。

引理1压缩映射原理[7]：设D为完备的赋范线性空间B中的非空闭子集，g:D→D是压缩的，即对任意的x,y∈D都有

则存在唯一的x*∈D，使得gx*=x*，即T在D内存在唯一的不动点x*。

引理2Lagrange中值定理[8]：设X,Y分别为两个完备的赋范线性空间，A⊂X，B⊂A，如果算子g:A→Y在B上是Frechet可微的，则存在λ∈(0,1)，使得

引理3设X,Y分别为两个完备的实赋范线性空间，G为B(X,Y)中所有有界逆算子全体组成的一个集合，如果A∈G，且对于B(X,Y)中的元素B满足

则有[5]B∈G，并有

引理4设X,Y分别为两个完备的赋范线性空间，A为X中的连通开集，B⊂Y，且g为从A到B中的可微算子，则当x∈A时，对于任意使得x+△x∈A的△x都有[9]

定理1设X,Y分别为两个实的完备赋范线性空间，算子g:B(x0,r)⊂X→Y是Frechet可微的，并假设：

则方程g(x)=0在B(x0,r)中存在唯一解x*，且该修正牛顿法的迭代形式

(2)

收敛于x*，误差估计为：

证明首先证明当x∈B(x0,r)时，g′(x)-1存在且有界。

由假设条件(Ⅱ)可知：当x∈B(x0,r)时，

由引理3知：当x∈B(x0,r)时，g′(x)-1存在有界且满足

及

其次，用第二数学归纳法来证，式(2)产生的序列{xn}都在B(x0,r)中而且还是收敛的。

(Ⅰ)显然x0在B(x0,r)中，下证x1也在B(x0,r)中。

由g′(xk)=g′(xk-1)+g′(xk)-g′(xk-1)可知：

g′(xk)=g′(xk-1)[I+g′(xk-1)-1(g′(xk)-g′(xk-1))]，

即

g′(xk)-1=g′(xk-1)-1[I-(g′(xk)-g′(xk-1))g′(xk)-1]。

对上述等式两边同取范数并利用假设条件(Ⅱ)可得：

ak≤ak-1(1-Lαk-1ak-1)-1=ak-1(1-ηk-1)-1。

当k=1时，

由假设条件(Ⅱ)可得:

且

故当k=1时，结论显然成立。

假设当k=2,3,…,n-1时，结论都成立，下证当k=n时，结论也成立。

‖g′(xn)-1(g(xn)-g(xn-1)-g′(xn-1)(xn-xn-1))+

故

(3)

综上所述，迭代式(2)产生的序列{xn}都在B(x0,r)中，且收敛。

再次，证明序列{xn}的极限x*是方程g(x)=0在B(x0,r)中的唯一解。

由g(x)的连续性以及迭代式(2)可知：g(x*)=0，故x*为方程g(x)=0在B(x0,r)中的解。下证解的唯一性。

最后，证明误差估计不等式。

在不等式(3)两端同时令p→∞，则有：

3数值试验

本节采用文献[1-2,8，10]中的3个数值算例来说明所提算法是可行有效的，并将所求结果与文献[1-2,8，10]中算法的数值结果进行对比，说明本文所提出的算法的收敛速度比文献[1-2]中提出的算法的收敛速度快。在进行数值试验过程中为方便计算，在算法的步骤3中取ε=10-10。

算例1

表1　算例1的数值结果

取与文献[1-2]中相同的初始值x0=(1,0)′，相同的迭代终止准则为10-10，其中，x0为迭代的初始点。

算例2

文献[1-2,8]中给出了该算例的真解为x*=(0.3,2.8)′。用本文所给算法来计算算例2，相应的数值结果如表2所示。

表2　算例2的数值结果

取与文献[1-2]中相同的初始值x0=(0.1,0.1)′，相同的迭代终止准则10-10。

文献[1-2,8]的数值结果：取初始值x0=(0.1,0.1)′，当ξ=(0.4，2.9)T时,迭代次数为32，方程g2(x)=0的解为xk+1=(0.299 4，2.836 9)T；当ξ=(0.5，3.3)T时,迭代次数为32，方程g2(x)=0的解为xk+1=(0.500 0，3.141 6)T，显然不是原问题的解。

算例3

文献[1-2,8,10]中给出了该算例的真解为x*=(0.7,0.7)′。用本文所给算法来计算算例3，相应的数值结果如表3所示。

表3　算例3的数值结果

取与文献[1-2]中相同的初始值x0=(0.1,0.1)′，相同的迭代终止准则为10-10。

文献[1-2,8,10]的数值结果：取初始值x0=(0.1,0.1)′，当ξ=(0.9，0.9)T时,迭代次数为33，方程g3(x)=0的解为xk+1=(0.700 0，0.700 0)T；当ξ=(1.2，1.2)T时,迭代次数为34，方程g3(x)=0的解为xk+1=(0.700 0，0.700 0)T；当ξ=(2.3，2.3)T时,迭代次数为36，方程g3(x)=0的解为xk+1=(0.700 0，0.700 0)T。

4结论

本文研究了初值在真解附近，但牛顿法最终迭代结果远离真值的一类病态问题，提出了一种新的修正牛顿法，在完备的赋范线性空间中证明了算法的有效性。数值试验结果表明：该算法是可行而且有效的。

参考文献：

[1]晁玉翠,韩波.求解非线性方程组的修正牛顿法研究[D].哈尔滨:哈尔滨工业大学,2007.

[2]马元婧,韩波.非线性方程组的一种修正牛顿法及其连续型[D].哈尔滨:哈尔滨工业大学,2009.

[4]Francisco F,Andreas F,Markus H.An LP-Newton Method:Nonsmooth Equations,KKT Systems,and Nonisolated Solutions[J].Mathematical Programming,2013:DOI:10.1007/s10107-013-0676-6.

[5]Zhou F Q.An Analysis on Local Convergence of Inexact Newton-Gauss Method for Solving Singular Systems of Equations[J].The Scientific World Journal,2014:752673.

[6]Du S Q.Generalized Newton Method for a Kind of Complementarity Problem[J].Abstract and Applied Analysis,2014,2014:745981.

[7]时宝,王兴平,盖明久,等.泛函分析引论及其应用[M].北京:国防工业出版社,2009.

[8]Han B,Zhang D L,Liu J Q.A New Class of Methods for Solving Nonlinear Equations[J].J Comput Appl Math,1994,51:107-111.

[9]蹇人宜.应用数学中的泛函分析[M].北京:科学出版社,2013.

[10]Tewarson R P.Use of Smoothing and Damping Techniques in the Solution of Nonlinear Nonlinear Equations[J].SIAM Rev,1977,1:35-45.