非线性方程组的求解

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

2、法、BFG法、记忆,$度法、Memetic算法1：三种牛顿法：Newton法、简化Newton法、修改的Newton法"3求解非线性方程组的Newton法是一个最基本而且十分重要的方法，目前使用的很多有效的迭代法都是以Newton法为基础，或由它派生而来。n个变量n个方程的非线性方程组，其一般形式如下：?i(,X2,.Xn)=0,f2(Xi,X2,.Xn)=0(1).fn(X,X2,.Xn户0式(1)中，屋兑区,.4)(i=1,?,n)是定义在n维Euclid空间Rr开域D上的实值函数。若用向量记号，令:xjX2X=,F(X)=1.IHn1-fl(Xi,X2,.Xn)=0-fi(X)

3、f2(Xi,X2,.Xn)=0=f2(X)"._fn(Xi,X2,.Xn)=01_fn(X)则方程组(1)也可表示为:F(X)=0其中：X三Rn,F:Fn-R0,F(X)CRn,Rn为赋值空间。一般地，若在包含的某邻域D内，按某种近似意义，用线性函数：ik(X)=AXbk近似地代替向量值函数F(X),此处A是n阶矩阵，则可将线性方程组：ik(X)=ax+bk(4)的解作为非线性方程组(2)的近似解。1.1Newton法Newtorfe的迭代公式为：Xk书=Xk+AXkk=0,1,2,.(5)、F'(Xk)gXk)=-F(Xk)其中Xk=Xk1-Xk.简化Newton法川尽管N

4、ewton法具有较高的收敛速度，但在每一步迭代中，要计算n个函数值f,以及n2个导数值f'形成Jacobi矩阵f'(Xk),而且要求f'(Xk)的逆阵或者解一个n阶线性方程组，计算量很大。为了减少计算量，在上述Newton法中对一切k=0,1,2,.,取f'(Xk)为f'(X.),于是迭代公式修改为：(6)Xk1=Xkf'(Xk)尸f(Xk),k=0,1,2.式(5)即为简化的Newton法。该方法能使计算量大为减少，但却大大降低了收敛速度。简化的Newton法的算法与Newton法的算法区别就在于只由给定的初始近似值计算一次f'(X),

5、以后在每一次迭代过程中不再计算f'(XJ，保持初始计算值。修正的Newton法吸取Newton法收敛快与简化的Newton法工作量省的优点，文献【2】把m步简化的Newton步合并成一次Newton步。则可以得到下列迭代程序:Xk,。=Xk'Xk,j=Xk,jf'(Xk)f(Xk,j)>(7)Xk书=Xk,m式中：j=1,2,?,m,k=0,1,2,?,该式称为修正的Newton法。通过分析Newton法、简化的Newton法和修正Newton法的原理，并通过对算例的分析比较，我们可知：Newton法(5)式具有较高的收敛速度，但计算量大，在每一步迭代中，要计算n

6、个函数值f,以及n2个导数值f形成Jacobi矩阵f'(Xk)，而且要求f'(Xk)的逆阵或者解一个n阶线性方程组；简化的Newton法(6)式，它用迭代初值X。来计算f'(Xk),并在每个迭代步中保持不变，它能使每步迭代过程的计算量大为减少，但大大降低了收敛速度。修正Newton(7)与Newtorfe(5)相比，在每步迭代过程中增加计算n个函数值，并不增加求逆次数，然而收敛速度提高了2:BFGS法【4-6】非线性方程组一般形式为：方程组(1)将其转化为一个全局优化问题。构造n能量函数：(X)=£f；(X),X=(X1,X2,.X，求非线性方程组解的问题就转

7、化为i=1求解能量函数极小值的问题。即给定一个充分小的实常数6,搜索x*=(x；,x2,.k)使得小(X*)<名则X*即是非线性方程组(D对应的近似解。BFGS查分算法文献【4】将传统的BFGST法和查分算法有机融合，用来求解非线性方程组,效果显著，可以较为广泛地应用于非线性方程组的求解。BFGST法是由Broyden、Fletcher、Goldfarb和Shanno等人在1970年提出的。它是一个拟牛顿方法，具有二次终止性、整体收敛性和超线性收敛性，且算法所产生的搜索方向是共腕的。BFGS?法是一个有效的局部算法，用来求解极小值的。例如方程组'fl(Xi,X2,.Xn)=A(8

8、)f2(X1,X2>.xn)=A2fn(Xi,X2,.Xn)=O可将它够着适应度函数nF(X)=fi(x)-A|(9)i1那么求非线性方程组(8)的根问题就转化成了求适应度函数F(X)最小值的优化问题。这就是它最基本的思想。DEET法(差分进化算法)(文献【5】)具有良好的全局搜索能力，并具有对初始值、参数选择不敏感、鲁棒性强、原理简单、容易操作等优点，是一种较好的全局优化方法。但在优化后期D方法的收敛速度明显变慢，而且搜索结果仅获得满意解域而不是精确解。为了克服这些缺点，该文在D方法的进化后期阶段引入BFGS?法，利用BFGS方法的整体收敛性和超收敛性来加快收敛速度。BFGS?法属于局

9、部算法，其优化结果的优劣在很大程度上取决于初始值的选取，为此可以利用具有全局搜索能力的D方法提供给BFGST法良好的初始值。改进的BFGS变尺度法对于高维的大型问题(维数大于100),变尺度法由于收敛快、效果好，被认为是最好的优化方法之一。其中BFGS法的数值稳定性较好，是最成功的一种变尺度法。BFGSfc中有2个非常关键的环节：求函数的偏导数和一维探索。这2个环节的算法精度对最后结果的精度影响很大。改进的遗传算法遗传算法的优越性主要表现在：算法具有固有的并行性，通过对种群的遗传处理可处理大量的模式，并且容易并行实现。(a)选择复制操作采用保优操作与比例复制相结合，即最优秀的个体被无条件保留下

10、来，其余的以正比于个体适配值的概率来选择相应的个体。(b)交叉操作采用保优操作与算数交叉结合，即最优秀的个体被无条件保留下来，其余的以交叉概率进行算数交叉。算数交叉的方式为：X1=：X1(1-：)X2,X2=：X2(1-：)X1(10)式中aw(0,1)；X1,X2为父代个体；X,X2为后代个体。(c)变异操作采用保优操作与扰动变异结合，即最优秀的个体被无条件保留下来，其余的以变异概率进行扰动变异。扰动变异的方式为X'=X十慎o式中U为满足正态分布的随机扰动；列为尺度参数；X为父代个体；X'为后代个体。混合优化改进的BFGS方法是一种非常有效而且收敛速度很快的局部搜索算法，而改

11、进的遗传算法实现并行搜索，有非常强的全局搜索的能力。文献【7】将2种方法混合起来，实现了并行与串行，全局与局部的融合，极大地提高了优化性能、优化效率和鲁棒性.o尤其对于高维复杂函数效果非常好。混合法的步骤为(1)给定算法参数，初始化种群。(2)评价当前种群中各个体。(3)判断算法收敛准则是否满足。若满足则输出搜索结果，否则转(4)。(4)执行改进的遗传算法的选择复制操作。(5)执行改进的遗传算法的交叉操作。(6)执行改进的遗传算法的变异操作。(7)以当前种群中各个个体作为改进的BFGSf法的初始解，分别用改进的BFGSf法进行搜索得到新的个体，将这些新的个体组成新的种群，转(2)。3:记忆梯度

12、法8-10考虑非线性方程组F(x)=0,xwRn,(11)其中F:RntRn是非线性映射。定义F(x)=(F1(x),F2(x),.F(Xn)T,其雅可比矩阵J(X)。记忆梯度法(文献【8-9】)是求解无约束优化问题非常有效的方法，该方法在每步迭代时不需计算和存储矩阵，结构简单，因而适于求解大型优化问题。算法的基本思想是：首先将非线性方程组问题(12)转化为一个无约束极小化问题minf(x),xRn,(12)i1.2其中f(x)=3F(x)Io这里|.|采用二范数，然后利用记忆梯度法求解问题(13)。因为f(x)>0。所以如果x*是无约束优化问题(12)的最优解，那么x*必是非线性方程组

13、(11)的近似最优解。设f(X)的梯度为g(x),则g(x)=f(x)=J(x)F(x).求解无约束优化问题的记忆梯度法应用于求解非线性方程组，给出了一类新的求解非线性方程组的记忆梯度算法，并分析了算法的全局收敛性。该算法无需求雅克比矩阵的逆矩阵,所以具有更广泛的应用性。止匕外，算法在迭代过程中也无需每一步都计算F(X)的雅克比矩阵，大大减少了算法的计算量，节省了运算时间。与牛顿法相比，记忆梯度法更适于求解大规模非线性方程组。4：基于Memetic算法的非线性方程组求解算法111-121Memetic算法是建立在模拟文化进化基础上的优化算法，它实质上是一种基于种群的全局搜索和基于个体的局部启发

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

15、果具有重要的影响。仍然以方程组(1)为例，现在定义：f(x)=£fi2(X)(13),i1则求解方程组(1)等价于求解这样一个极值优化问题：若在方程组(1)的解空间内找到一组X=XX2，.Xn,使得式(13)达到最小值则此时的X=X1,X2,.Xn就是方程组(1)的解。总结文献【11】的算法大致思路：先初始化种群，看其是否满足停止准则，(1)适应度评价与选择是的话显示结果，算法结束。否则的话，进行以下步骤:(2)染色体多点交叉。(3)拟牛顿局部搜索(4)染色体随机变异。(5)拟牛顿局部搜索。返回看是否满足停止准则，满足显示结果，不满足继续循环。Memetic算法充分发挥了Memeti

16、c®法大范围搜索全局解的特点以及拟牛顿算子局部细致搜索的特点，对非单调多峰函数组成的非线性方程组，求到解的概率显著高于拟牛顿法和GA实验表明基于Memetic算法求解非线性方程组具有较高的收敛可靠性和较高的精度。综上，非线性方程组求解是实际工程领域的一个重要问题，在数值天气预报、石油地质勘探、计算生物化学、控制领域和轨道设计等方面均有较强的应用背景。从实际应用角度出发，有必要探索高效可靠的算法去求解，可以解决我们生活中的很多问题。参考文献1谢世坤,段芳，李强征，罗志扬，郑慧.非线性方程组求解的三种Newtorfe比较J.井冈山学院学报(自然科学),2006,27(8):8-11.2余

17、芝云，陈争，马昌凤.求解对称非线性方程组基于信赖域的修正牛顿法J.福建师范大学学报(自然科学版),2010,26(1):22-27.3LiDH,ChengWY.Recentprogressintheglobalconvergenceofquasi-NewtonmethodsfornonlinearequationsJ.HokkaidoMathJ,2007,36(2):729-743.4刘利斌，欧阳艾嘉，许卫明，李肯立.求解非线性方程组的BFG嵯分进化算法J.2011,47(33):55-58.5周丽，姜长生.非线性方程组求解的一种新方法J.小型微型计算机系统,2008,9:1709-1713.6张飞飞，马群，黄家庆，佟晓君.求解非线性方程组的二分法J.科技创新导报，2009,08(0):146-149.7李涛，刘华伟，陈耀元.非线性方程组求解的新方法J.武汉理工大学学报(交通科学与工程版),2009,33(3):569-572.8李敏，苏酉1,时贞.求解非线性方程组的记忆梯度算法J.工程数学学报，2009,26(3):563-566.9ShiZJ.Anewsuper-memorygradientmethodforunconstrainedoptimizationJ.A