非线性方程组的求解

非线性方程组的求解

摘要：非线性方程组求解是数学教学中，数值分析课程的一个重要组成部分，作为一门学科，其研究对象是非线性方程组。求解非线性方程组主要有两种方法：一种是传统的数学方法，如牛顿法、梯度法、共轭方向法、混沌法、BFGS法、单纯形法等。传统数值方法的优点是计算精度高，缺点是对初始迭代值具有敏感性，同时传统数值方法还会遇到计算函数的导数和矩阵求逆的问题，对于某些导数不存在或是导数难求的方程，传统数值方法具有一定局限性。另一种方法是进化算法，如遗传算法、粒子群算法、人工鱼群算法、差分进化算法等。进化算法的优点是对函数本身没有要求，不需求导，计算速度快，但是精度不高。 关键字：非线性方程组、牛顿法、BFGS法、记忆梯度法、Memetic算法

1： 三种牛顿法：Newton 法、简化Newton 法、修改的Newton 法【1-3】 求解非线性方程组的Newton 法是一个最基本而且十分重要的方法, 目前使用的很多有效的迭代法都是以Newton 法为基础, 或由它派生而来。 n 个变量n 个方程的非线性方程组, 其一般形式如下:

f1(x1,x2,...xn)0f(x,x,...x)0212n...

fn(x1,x2,...xn)0 （1）

式(1)中,fi(x1,x2,...xn)( i=1, ⋯, n) 是定义在n 维Euclid空间Rn中开域 D上 的实值函数。若用向量记号，令：

f1(x1,x2,...xn)0f1(X)x1xf(X)f(x,x,..x)022212n X,F(X).........xf(X)f(x,x,...x)0nnn12n

则方程组（1）也可表示为：

F(X)0 （2）

其中：XRn,F∶Rn→R0, F(X) ∈Rn, Rn为赋值空间。一般地， 若在包含的某邻域

D 内, 按某种近似意义,用线性函数:

lk(X)AkXbk （3）

近似地代替向量值函数F(X),此处Ak 是n 阶矩阵，则可将线性方程组:

lk(X)AkXbk （4）

的解作为非线性方程组( 2) 的近似解。

1.1 Newton法[1]

Newton法的迭代公式为：

Xk1XkXkk0,1,2,... (5）F'(Xk)(Xk)-F(Xk)

其中XkXk1-Xk.

1.2 简化Newton 法[1]

尽管Newton 法具有较高的收敛速度，但在每一步迭代中，要计算n 个函数值f，以及n2个导数值f′形成Jacobi矩阵f'(Xk)，而且要求f'(Xk)的逆阵或者解一个n 阶线性方程组，计算量很大。为了减少计算量，在上述Newton 法中对一切k=0,1,2,...,取f'(Xk)为f'(X.)，于是迭代公式修改为：

Xk1Xkf'(Xk)f(Xk),k0,1,2... (6) 1

式( 5) 即为简化的Newton 法。该方法能使计算量大为减少，但却大大降低了收敛速度。简化的Newton 法的算法与Newton 法的算法区别就在于只由给定的初始近似值计算一次f'(X)，以后在每一次迭代过程中不再计算f'(Xk)，保持初始计算值。

1.3 修正的Newton 法

吸取Newton 法收敛快与简化的Newton 法工作量省的优点，文献【2】把m 步简化的Newton 步合并成一次Newton 步。则可以得到下列迭代程序: [2]

Xk,0Xk1Xk,jXk,jf'(Xk)f(Xk,j1) (7)

Xk1Xk,m

式中: j=1, 2, ⋯, m, k=0, 1, 2, ⋯, 该式称为修正的Newton 法。

通过分析Newton 法、简化的Newton 法和修正Newton 法的原理, 并通过对算例的分析比较，我们可知: Newton 法(5)式具有较高的收敛速度，但计算量大，在每一步迭代中，要计算n个函数值f，以及n2个导数值f'形成Jacobi 矩阵

而且要求f'(Xk)的逆阵或者解一个n 阶线性方程组；简化的Newton 法f'(Xk) ，

( 6) 式，它用迭代初值X0来计算f'(Xk)，并在每个迭代步中保持不变，它能使每步迭代过程的计算量大为减少，但大大降低了收敛速度。修正Newton法(7)与Newton法(5)相比，在每步迭代过程中增加计算n个函数值，并不增加求逆次数，然而收敛速度提高了。

2： BFGS法【4-6】

非线性方程组一般形式为:方程组（1）将其转化为一个全局优化问题。构造能量函数：（X）求非线性方程组解的问题就转化为fi2(X),X（x1,x2,...xn）

i1n

求解能量函数极小值的问题。即给定一个充分小的实常数，搜索

***使得（X*）则X*即是非线性方程组（1）对应的近似解。 X*（x1,x2,...xn）

2.1 BFGS查分算法【4】

文献【4】将传统的BFGS算法和查分算法有机融合，用来求解非线性方程组，效果显著，可以较为广泛地应用于非线性方程组的求解。BFGS方法是由Broyden、

Fletcher、Goldfarb和Shanno 等人在1970年提出的。它是一个拟牛顿方法，具有二次终止性、整体收敛性和超线性收敛性，且算法所产生的搜索方向是共轭的。BFGS方法是一个有效的局部算法，用来求解极小值的。

例如方程组

f1(x1,x2,...xn)A1f(x,x,...x)A212n2...

fn(x1,x2,...xn)An （8）

可将它够着适应度函数

F(X)|fi(x)Ai|

i1n (9)

那么求非线性方程组（8）的根问题就转化成了求适应度函数F（X） 最小值的优化问题。这就是它最基本的思想。

DE算法(差分进化算法)（文献【5】）具有良好的全局搜索能力，并具有对初始值、参数选择不敏感、鲁棒性强、原理简单、容易操作等优点，是一种较好的全局优化方法。但在优化后期DE算法的收敛速度明显变慢，而且搜索结果仅获得满意解域而不是精确解。为了克服这些缺点，该文在DE算法的进化后期阶段引入BFGS方法，利用BFGS 方法的整体收敛性和超收敛性来加快收敛速度。BFGS方法属于局部算法，其优化结果的优劣在很大程度上取决于初始值的选取，为此可以利用具有全局搜索能力的DE算法提供给BFGS方法良好的初始值。

2.2 改进的BFGS 变尺度法【4】

对于高维的大型问题（维数大于100），变尺度法由于收敛快、效果好，被认为是最好的优化方法之一。其中BFGS 法的数值稳定性较好，是最成功的一种变尺度法。BFGS法中有2个非常关键的环节：求函数的偏导数和一维探索。这2个环

节的算法精度对最后结果的精度影响很大。

2.2.1 改进的遗传算法【7】

遗传算法的优越性主要表现在：算法具有固有的并行性，通过对种群的遗传处理可处理大量的模式，并且容易并行实现。

(a) 选择复制操作

采用保优操作与比例复制相结合, 即最优秀的个体被无条件保留下来,其余的以正比于个体适配值的概率来选择相应的个体。

(b) 交叉操作

采用保优操作与算数交叉结合,即最优秀的个体被无条件保留下来，其余的以交叉概率进行算数交叉。算数交叉的方式为:

(10) X1X1(1)X2,X2X2(1)X1

式中（0,1）；X1,X2为父代个体；X1,X2为后代个体。

（c）变异操作

采用保优操作与扰动变异结合,即最优秀的个体被无条件保留下来，其余的以变异概率进行扰动变异。扰动变异的方式为X'X。式中为满足正态分布的随机扰动；为尺度参数; X为父代个体; X'为后代个体。

2.3 混合优化【7】

改进的BFGS 方法是一种非常有效而且收敛速度很快的局部搜索算法，而改进的遗传算法实现并行搜索，有非常强的全局搜索的能力。文献【7】将2种方法混合起来，实现了并行与串行，全局与局部的融合，极大地提高了优化性能、优化效率和鲁棒性.。尤其对于高维复杂函数效果非常好。

混合法的步骤为:

(1)给定算法参数，初始化种群。(2)评价当前种群中各个体。（3)判断算法收敛准则是否满足。若满足则输出搜索结果，否则转(4)。(4)执行改进的遗传算法的选择复制操作。（5)执行改进的遗传算法的交叉操作。（6)执行改进的遗传算法的变异操作。(7)以当前种群中各个个体作为改进的BFGS方法的初始解，分别用改进的BFGS方法进行搜索得到新的个体，将这些新的个体组成新的种群，转

（2）。

3： 记忆梯度法[8-10]

考虑非线性方程组

（11） F(x)0,xRn ，

其中F:RnRn是非线性映射。

定义F(x)(F1(x),F2(x),...F(xn))T，其雅可比矩阵J(X)。记忆梯度法(文献【8-9】)是求解无约束优化问题非常有效的方法，该方法在每步迭代时不需计算和存储矩阵，结构简单，因而适于求解大型优化问题。

算法的基本思想是: 首先将非线性方程组问题(12)转化为一个无约束极小化问题

minf(x),xRn, (12) 其中f(x)1F(x)22。 这里采用二范数，然后利用记忆梯度法求解问题(13)。因为f( x) ≥ 0。所以如果x* 是无约束优化问题(12)的最优解，那么x* 必是非线性方程组(11) 的近似最优解。设f(X)的梯度为g(x)，则g(x)=▽f(x)=J(x)F(x).求解无约束优化问题的记忆梯度法应用于求解非线性方程组，给出了一类新的求解非线性方程组的记忆梯度算法，并分析了算法的全局收敛性。该算法无需求雅克比矩阵的逆矩阵，

所以具有更广泛的应用性。此外，算法在迭代过程中也无需每一步都计算F(X) 的雅克比矩阵，大大减少了算法的计算量，节省了运算时间。与牛顿法相比，记忆梯度法更适于求解大规模非线性方程组。

4： 基于Memetic算法的非线性方程组求解算法【11-12】

Memetic 算法是建立在模拟文化进化基础上的优化算法，它实质上是一种基于种群的全局搜索和基于个体的局部启发式搜索的结合体。Memetic 算法流程和GA 有很大的相似。其关键区别是Memetic算法在交叉和变异后多了一个局部搜索优化的过程。针对函数优化问题,传统的遗传算法虽然能够全局寻优，但是它很容易早熟。对于传统的局部搜索算法，它一个初始解开始，在其邻域中搜寻比其更好的解，它可以快速求出较优解，其不足主要是只有当迭代初值在真实解附近时，其较快的局部搜索性能才能得以发挥。Memetic 算法充分吸收了遗传算法和传统局部搜索算法的优点，采用遗传算法的操作流程，但是在每次交叉和变异后进行局部搜索，通过优化种群分布及早剔除不良种群，进而减少迭代次数，在Memetic算法的设计过程中各个参数的选择策略对算法求解结果具有重要的影响。

仍然以方程组（1）为例，现在定义：

f(x)f

i1n2i(X) (13)

则求解方程组( 1) 等价于求解这样一个极值优化问题: 若在方程组( 1) 的解空间内找到一组X[X1,X2,...Xn]，使得式(13)达到最小值则此时的X[X1,X2,...Xn] 就是方程组( 1) 的解。

总结文献【11】的算法大致思路：先初始化种群，看其是否满足停止准则，是的话显示结果，算法结束。否则的话，进行以下步骤：(1)适应度评价与选择。

（2）染色体多点交叉。（3）拟牛顿局部搜索。（4）染色体随机变异。（5）拟牛顿局部搜索。返回看是否满足停止准则，满足显示结果，不满足继续循环。

Memetic算法充分发挥了Memetic算法大范围搜索全局解的特点以及拟牛顿算子局部细致搜索的特点，对非单调多峰函数组成的非线性方程组，求到解的概率显著高于拟牛顿法和GA，实验表明基于Memetic算法求解非线性方程组具有较高的收敛可靠性和较高的精度。

综上，非线性方程组求解是实际工程领域的一个重要问题，在数值天气预报、石油地质勘探、计算生物化学、控制领域和轨道设计等方面均有较强的应用背景。从实际应用角度出发，有必要探索高效可靠的算法去求解，可以解决我们生活中的很多问题。

参考文献

[1]谢世坤,段芳,李强征,罗志扬,郑慧.非线性方程组求解的三种Newton法比较

[J].井冈山学院学报( 自然科学),2006,27(8):8-11.

[2]余芝云,陈争,马昌凤.求解对称非线性方程组基于信赖域的修正牛顿法[J].福建师范大学学报( 自然科学版),2010,26(1):22-27.

[3]Li D H，Cheng W Y． Recent progress in the global convergence of quasi-Newton methods for nonlinear equations［J］． Hokkaido Math J，2007， 36 ( 2) : 729-743．

[4]刘利斌,欧阳艾嘉,许卫明,李肯立.求解非线性方程组的BFGS差分进化算法

[J].2011,47(33):55-58.

[5]周丽,姜长生.非线性方程组求解的一种新方法[J].小型微型计算机系统,2008,9:1709-1713.

[6]张飞飞,马群,黄家庆,佟晓君.求解非线性方程组的二分法[J].科技创新导报，2009,08（c):146-149.

[7]李涛,刘华伟,陈耀元.非线性方程组求解的新方法[J].武汉理工大学学报(交通科学与工程版),2009,33(3):569-572.

[8]李敏,苏醒,时贞.求解非线性方程组的记忆梯度算法[J]. 工程数学学报，2009,26（3）：563-566.

[9]Shi Z J． A new super-memory gradient method for unconstrained optimization［J］． Advances in Mathematics，2006，3( 35) : 265-273．

[10]陈长忆,叶永春.基于粒子群算法的非线性方程组求解[J].计算机应用与软件,2006,23(5):137-139.

[11]屈爱平，李敏.MEMETIC算法在非线性方程组求解中的应用[J].湖南文理学院学 报(自然科学版),2009,21(4):13-15.

[12]Sudholt D.The impact of parametrization in memetic evolutionary algorithms[J] .Theoretical Computer Science, 2009, 26(410) : 2 511-2528.

。