1. 引言
本文研究下面的非线性方程组问题:
(1.1)
是连续可微函数,不难看出问题(1.1)的求解等价于求解如下形式的最小值优化问题模型:
(1.2)
其中
表示欧式范数。则非线性方程组问题(1.1)就转化为了一个最小值的优化问题(1.2),我们将对(1.2)提出其求解的新算法。求解一个最优化问题,常采用数值迭代方法,一般的迭代公式定义为
(1.3)
是搜索方向,
表示步长,
代表第
次迭代点(或称为当前点),有了
和
,产生第
个迭代点
(或称为下一个迭代点);依次类推,根据(1.3)产生一个迭代序列
,设计算法主要是分析迭代序列
是否收敛到某一聚点
或得到
?
本文将针对(1.2)设计一个新的三项共轭梯度法,众所周知共轭梯度算法是一类非常有效的求解目标函数最小值的优化方法 [1] [2] [3] [4] [5] ,特别是对大规模优化问题,其搜索方向定义形式是:
![](//html.hanspub.org/file/4-1700083x26_hanspub.png)
表示共轭梯度参数,它是共轭梯度法设计的关键。鉴于此方法设计简单、程序容易实现,很多学者便成功将此类方法应用于(1.1)的求解(见文献 [6] [7] [8] 等),受此启发,我们将做进一步的研究,设计一个三项共轭梯度算法,新方法具有不错的性质和特点。第二部分,给出设计好的三项共轭梯度方法和及其具体的算法步骤,第三部分分析算法的下降性、信赖域特点和全局收敛性,第四部分进行非线性方程组问题的检验。
2. 公式和算法
建议的三项共轭梯度公式如下:
(2.1)
,
是常数。上述公式的思想是受文章 [7] [8] 启发设计的。下面给出该三项共轭梯度算法详细步骤:
算法1:(三项共轭梯度算法)
步骤0:初始条件的赋值,初始迭代点
,常数
,置
。
步骤1:条件
满足,停止算法;否则转步骤2。
步骤2:解(2.1)获得搜索方向
。
步骤3:通过下面线搜索技术
(2.2)
获得步长
。
步骤4:置
。
步骤5:如果条件
满足,算法停止并取
;否则置
(2.3)
步骤6:置
,转到步骤1。
注:线搜索技术(2.2)是文献 [7] 最先给出,(2.3)是投影技术,由文献 [9] 给出。
3. 信赖域特点、充分下降性以及全局收敛性
我们首先通过下面的引理证明算法1的信赖域的特点和充分下降性。
引理3.1:(2.1)产生的搜索方向
满足
(3.1)
和
(3.2)
是常数。
证明:根据(2.1)的定义形式,
时,不难获得(3.1)和(3.2)。下面讨论
时的情况,同样利用(2.1)有
![](//html.hanspub.org/file/4-1700083x49_hanspub.png)
从而获得(3.1)。根据(3.1)的结果,易得
![](//html.hanspub.org/file/4-1700083x50_hanspub.png)
取
,则(3.2)式的左边成立。关于(3.2)的右边不等式,需要再次利用(2.1)来获得,具体如下
![](//html.hanspub.org/file/4-1700083x52_hanspub.png)
最后一个不等式利用了
获得,任取
,(3.2)的右边不等式便能获得。综上所述,关系式(3.1)和(3.2)都是成立的。证毕!
关系式(3.1)被称为充分下降性,而关系式(3.2)被称为信赖域的特征。从证明过程可以看出,我们建议的三项共轭梯度的搜索方向在没有其他假设条件的情况下,自身就能拥有这两个优点,关系式(3.1)和(3.2)对算法的收敛性起着至关重要的作用。为进一步获得三项共轭梯度算法的全局收敛性,需要一些假设条件。
假设A:(i) 假设问题(1.1)的解存在;
(ii)
满足Lipschitz条件,也就是
,
是Lipschitz常数。
根据假设A和获得的引理3.1,便可以证明算法1的全局收敛性结论。此结论的证明与参考文献 [7] 的证明过程相似,我们就不再详述。
定理3.1:若迭代序列
是由算法1产生的且假设A的条件满足,则关系式
![](//html.hanspub.org/file/4-1700083x59_hanspub.png)
成立。
此定理被称为算法1的全局收敛性定理。
4. 数值实验
为验证建议的三项共轭梯度算法是有效的,本节将对下面的问题(见表1)利用计算机编写程序计算。
我们将利用Matlab R2009a编写程序代码,程序是在Windows 7系统、CPU为Intel (R) Xeon (R),E5507 2.27 GHz、64位操作系统、6.00GB内存上运行。算法中的参数选取分别是:
,
,
,
。表2中第一行参数含义分别是:NI代表迭代次数,Nq代表函数值次数,Dim代表所检验问题的维数,Cpu-Time代表程序在计算机上运行的CPU时间,Val代表程序终止时的范数值。
从表格中测验结果能够看出:(1) 给定的三项共轭梯度算法能成功求解这10个非线性方程组问题,范数值接近于零说明利用新算法几乎得到了其精确解,其中第十个问题就获得了精确解;(2) 随着检验问题规模的增大,NI和Nq的变化不大,有的个别问题反而减少,但Cpu-Time均会适当增加,这也证明了算法的合理性;(3) 有些问题的Cpu-Time = 0,这证明算法在运行时,几乎没有占用系统的CPU时间。