Advances in Applied Mathematics
Vol.05 No.04(2016), Article ID:19126,5 pages
10.12677/AAM.2016.54093

A LS Algorithm for Nonlinear Equations

Linghua Huang

School of Information and Statistics, Guangxi University of Finance and Economics, Nanning Guangxi

Received: Nov. 12th, 2016; accepted: Nov. 26th, 2016; published: Nov. 30th, 2016

Copyright © 2016 by author and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY).

http://creativecommons.org/licenses/by/4.0/

ABSTRACT

This paper presents a LS conjugate gradient algorithm for nonlinear equations and the given algorithm has the following features: 1) the search direction satisfies the sufficient descent property; 2) the direction also has the trust region property; 3) the proposed algorithm possesses the global convergence; 4) numerical results show that the new algorithm is effective.

Keywords:Nonlinear Equations, Conjugate Gradient, Convergence

一个求解非线性方程组问题的LS算法

黄玲花

广西财经学院信息与统计学院,广西 南宁

收稿日期:2016年11月12日;录用日期:2016年11月26日;发布日期:2016年11月30日

摘 要

本文给出一个求解非线性方程组问题的LS算法,该方法具有如下特点:1) 搜索方向自动满足充分下降性;2) 方向具有信赖域的特征;3) 算法拥有全局收敛性;4) 数值结果表明新方法是有效的。

关键词 :方程组,共轭梯度,收敛性

1. 引言

考虑如下问题:

(1.1)

其中是一个连续函数,上述问题是一个非线性方程组,一个求解该问题的一个方法时将它化为如下的最优化问题模型:

(1.2)

其中定义是欧式范数,不难看出(1.1)和(1.2)的解是等价的。从中可见(1.1)就转化为

了一个最小值的优化问题(1.2),本文将针对(1.2)提出其求解方法。下面的数值迭代方法经常被使用,公式为:

(1.3)

其中代表搜索方向,是步长,是当前迭代点或第次迭代点,根据就产生下一个迭代点,依次下去便会产生一个点列,分析此点列收敛到某一聚点或得到

共轭梯度算法是一类非常有效的数值优化方法,它的方向定义如下:

根据的选取不同,便称为相应的共轭梯度法,目前已有很多公式 [1] [2] [3] [4] 等。目前已有很多学者将共轭梯度法应用于非线性方程组问题(见文献 [5] [6] 等),我们给出一个修正的LS共轭梯度算法,该方法具有显著的优点。下一部分,我们给出修正的LS方法和具体算法步骤,第三部分证明算法的全局收敛性,最后给出数值检验结果。

2. 公式和算法

下面给出修正的LS公式,表达式为:

(2.1)

其中是常数。此公式设计的部分思想是基于文章 [6] 。在此公式的基础上,我们给出一个修正的LS共轭梯度算法,步骤如下:

算法1 (修正的LS算法)

步0:给定初始点,常数。令

步1:若,则停止;否则进行步2。

步2:通过式(2.1)计算搜索方向

步3:选出满足下面的线搜索条件的步长

(2.2)

步4:令迭代公式为

步5:若,停止并令;否则令

(2.3)

步:令,转步1。

注:线搜索(2.2)是由文献 [5] 给出,(2.3)的思想来源于文献 [7] 。

3. 下降性、信赖域性质和收敛性分析

首先分析算法1的充分下降性和信赖域的性质,通过下面的引理实现。

引理3.1. 若搜索方向由式(2.1)产生,有

(3.1)

(3.2)

成立,其中是常数。

证明:根据(2.1)式,当时,(3.1)和(3.2)显然成立。当时,由(2.1)得到

(3.1)式成立。下证(3.2)式。根据(3.1)式,可推出

从上式可得(3.1)式的左边,其中取。对于(3.2)的右边,通过(2.1)式获得下式

其中最后一个不等式根据得到,取便得到(3.2)的右边。综上,(3.1)和(3.2)均成立。证毕!

上述引理中的(3.1)是充分下降性,(3.2)是信赖域性质,这两个性质对算法的全局收敛性起着非常重要的作用。从中也可看出,所建议的搜索方向不需要任何附加条件,自动满足这两个性质。为获得算法1的全局收敛性,我们需要下面的假设条件。

假设1:(A) 所研究的问题(1.1)有解;

(B)上满足下面的Lipschitz性质,即

其中是个常数。

在假设1和引理3.1结论的基础上,我们可以建立算法的全局收敛性。因为全局收敛性的证明与文献 [6] 的证明过程基本相同,此处不再详述,只给出定理。

定理3.1. 假如序列由算法1产生,同时假设1成立,则有

成立。

此定理被称为算法1的全局收敛性定理。

4. 数值结果

为了验证算法的有效性,我们将对下面的问题进行检验(表1),这些问题同文献 [5] 一样。

利用Matlab R2009a编写程序,在Windows 7系统,6.00GB内存,64位操作系统,CPU为Intel (R) Xeon (R), E5507 2.27 GHz上运行。参数选取是:。表二中参数含义:NI表示迭代次数,NF表示函数值次数,Dim表示问题的维数,Time表示运行的CPU时间,Fval表示程序终止时的范数值。

Table 1. Equations problem

表1. 方程组问题

从上面表格中的数值结果可以看出,算法1对上述问题的求解非常有效,最终的范数值很接近零,表明对非线性方程组的精确解逼近程度很高,个别问题可以求到精确解(如问题7和问题9);随着问题维数的增加,CPU时间和迭代次数以及函数值次数改变不是很大,说明算法1的有效性;个别问题的CUP时间是零,说明其求解几乎没有占用系统的CPU时间,就得出了结果。

文章引用

黄玲花. 一个求解非线性方程组问题的LS算法
A LS Algorithm for Nonlinear Equations[J]. 应用数学进展, 2016, 05(04): 813-817. http://dx.doi.org/10.12677/AAM.2016.54093

参考文献 (References)

  1. 1. Fletcher, R. and Reeves, C.M. (1964) Function Minimization by Conjugate Gradients. Computer Journal, 7, 149-154. https://doi.org/10.1093/comjnl/7.2.149

  2. 2. Polak, E. and Ribière, G. (1968) Note sur la convergence de méthodes de directions conjuguées. Rev. franaise Informat.recherche Opérationnelle, 16, 35-43.

  3. 3. Wei, Z.X., Yao, S.W. and Liu, L.Y. (2006) The Convergence Properties of Some New Conjugate Gradient Methods. Applied Mathematics & Computation, 183, 1341-1350. https://doi.org/10.1016/j.amc.2006.05.150

  4. 4. Yuan, G.L. (2009) Modified Nonlinear Conjugate Gradient Methods with Sufficient Descent Property for Large-Scale Optimization Problems. Optimization Letters, 3, 11-21. https://doi.org/10.1007/s11590-008-0086-5

  5. 5. Li, Q. and Li, D.H. (2011) A Class of Derivative-Free Methods for Large-Scale Nonlinear Monotone Equations. Ima Journal of Numerical Analysis, 31, 1625-1635. https://doi.org/10.1093/imanum/drq015

  6. 6. Yuan, G. and Zhang, M. (2015) A Three-Terms Polak-Ribière-Polyak Conjugate Gradient Algorithm for Large-Scale Nonlinear Equations. Journal of Computational & Applied Mathematics, 286, 186-195. https://doi.org/10.1016/j.cam.2015.03.014

  7. 7. Solodov, M.V. and Svaiter, B.F. (1998) A Globally Convergent Inexact Newton Method for Systems of Monotone Equations. Reformulation: Nonsmooth, Piecewise Smooth, Semismooth and Smoothing Methods. Springer US, 1411- 1414.

期刊菜单