非线性方程组的求解

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

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

3、1,X2,.Xn) =0Xn_fn(X1,X2,.Xn) =0_fn(X)则方程组(1)也可表示为:F(X)=0(2)其中：XwRF ： UTR0, F(X) Rn, Rn为赋值空间。一般地，若在包含的某邻域D内，按某种近似意义，用线性函数:lk(X) =AX bk(3)近似地代替向量值函数F(X)，此处A是n阶矩阵，则可将线性方程组：ik(x)= ax bk(4)的解作为非线性方程组(2)的近似解。1.1 Newton 法1NewtonS的迭代公式为:KAXk+AXk k=0,1,2,.尸(Xk)(AXk)=-F(Xk)(5其中"小=Xk1-Xk.1.2 简化 Newton 法1尽

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

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

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

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

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

9、法，利用BFGS方法的整体收敛性和超收敛性来加快收敛速度。BFGS?法届丁局部算法，其优化结果的优劣在很大程度上取决丁初始值的选取，为此可以利用具有全局搜索能力的D审法提供给BFGST法良好的初始值。2.2 改进的BFGS变尺度法对丁高维的大型问题（维数大丁 100）,变尺度法由丁收敛快、效果好，被认 为是最好的优化方法之一。其中BFGS法的数值稳定性较好，是最成功的一种变 尺度法。BFG法中有2个非常关键的环节：求函数的偏导数和一维探索。 这2个环 节的算法精度对最后结果的精度影响很大。2.2.1改进的遗传算法遗传算法的优越性主要表现在：算法具有固有的并行性，通过对种群的遗传 处理可处理大量

10、的模式，并且容易并行实现。(a) 选择复制操作采用保优操作与比例复制相结合，即最优秀的个体被无条件保留下来，其余的以正比丁个体适配值的概率来选择相应的个体。(b) 交义操作采用保优操作与算数交义结合，即最优秀的个体被无条件保留下来，其余的以 交义概率进行算数交义。算数交义的方式为：X1 = ： X1 (1 -：)X2,X2 = ：X2 (1 - ：)X1(10)式中aw(0,1) ； X1,X2为父代个体；X1,X2为后代个体。(c)变异操作采用保优操作与扰动变异结合，即最优秀的个体被无条件保留下来，其余的以 变异概率进行扰动变异。扰动变异的方式为X'=X+H。式中W为满足正态分布 的

11、随机扰动;n为尺度参数；X为父代个体;X'为后代个体。2.3 混合优化171改进的BFGS方法是一种非常有效而且收敛速度很快的局部搜索算法，而改 进的遗传算法实现并行搜索，有非常强的全局搜索的能力。文献【7】将2种方法 混合起来，实现了并行与申行，全局与局部的融合，极大地提高了优化性能、优 化效率和鲁棒性.o尤其对丁高维复杂函数效果非常好。混合法的步骤为(1)给定算法参数，初始化种群(2)评价当前种群中各个体。(3)判断算法收敛准则是否满足。若满足则输出搜索结果，否则转(4)。(4)执行改进的遗传算 法的选择复制操作。(5)执行改进的遗传算法的交义操作。(6)执行改进的遗传算 法的变异

12、操作。(7)以当前种群中各个个体作为改进的BFGS*法的初始解，分别 用改进的BFGSf法进行搜索得到新的个体，将这些新的个体组成新的种群，转(2) 。3:记忆梯度法8-10考虑非线性方程组F(x)=0,xRn ,(11)其中F : Rn T Rn是非线性映射。定义F(x) =(F1(x),F2(x),.F(Xn)T ,其雅可比矩阵J(X)。记忆梯度法(文献【8-9】)是求解无约束优化问题非常有效的方法，该方法在每步迭代时不需计算和存储矩 阵，结构简单，因而适丁求解大型优化问题。算法的基本思想是：首先将非线性方程组问题(12)转化为一个无约束极小 化问题min f (x), x Rn,(12)

13、,11.2其中 f(x) =e F(x) |。这里|. |采用二范数，然后利用记忆梯度法求解问题 (13)。因为九x) > 0。所 以如果x*是无约束优化问题(12)的最优解，那么x*必是非线性方程组(11)的近似最优解。设f(X)的梯度为g(x),则g(x)= Vf(x)=J(x)F(x).求解无约束优化问题的记忆梯度法应用丁求解非线性方程组，给出了一类新的求解非线性方程组的记 忆梯度算法，并分析了算法的全局收敛性。该算法无需求雅克比矩阵的逆矩阵, 所以具有更广泛的应用性。此外，算法在迭代过程中也无需每一步都计算 F(X)的 雅克比矩阵，大大减少了算法的计算量，节省了运算时间。与牛顿法

14、相比，记忆 梯度法更适丁求解大规模非线性方程组。4：基于Memetic算法的非线性方程组求解算法111-121Memetic算法是建立在模拟文化进化基础上的优化算法，它实质上是一种基 丁种群的全局搜索和基丁个体的局部启发式搜索的结合体。Memetic算法流程和GA有很大的相似。其关键区别是Memetic算法在交义和变异后多了一个局部搜索 优化的过程。针对函数优化问题，传统的遗传算法虽然能够全局寻优，但是它很 容易早熟。对丁传统的局部搜索算法，它一个初始解开始，在其邻域中搜寻比其 更好的解，它可以快速求出较优解，其不足主要是只有当迭代初值在真实解附近 时，其较快的局部搜索性能才能得以发挥。Mem

15、etic算法充分吸收了遗传算法和 传统局部搜索算法的优点，采用遗传算法的操作流程，但是在每次交义和变异后 进行局部搜索，通过优化种群分布及早剔除不良种群，进而减少迭代次数，在 Memetic算法的设计过程中各个参数的选择策略对算法求解结果具有重要的影 响。仍然以方程组(1)为例，现在定义：f(x)=修 f(X)(13).i m则求解方程组(1)等价丁求解这样一个极值优化问题：若在方程组(1)的解空 间内找到一组X =X, X2，.Xn,使得式(13)达到最小值则此时的 X =X1,X2,.Xn就是方程组(1)的解。总结文献【11】的算法大致思路：先初始化种群，看其是否满足停止准则，(1)适应度

16、评价与选择是的话显小结果，算法结束。否则的话，进行以下步骤:(2)染色体多点交义。(3)拟牛顿局部搜索(4)染色体随机变异。(5)拟牛顿局部搜索。返回看是否满足停止准则，满足显示结果，不满足继续循环。Memetic算法充分发挥了 MemeticM法大范围搜索全局解的特点以及拟牛顿 算子局部细致搜索的特点，对非单调多峰函数组成的非线性方程组，求到解的概 率显著高于拟牛顿法和GA实验表明基于Memetic算法求解非线性方程组具有较 高的收敛可靠性和较高的精度。综上，非线性方程组求解是实际工程领域的一个重要问题，在数值天气预报、石油地质勘探、计算生物化学、控制领域和轨道设计等方面均有较强的应用背景。

17、 从实际应用角度出发，有必要探索高效可靠的算法去求解，可以解决我们生活中 的很多问题。参考文献1 谢世坤，段芳，李强征，罗志扬，郑慧.非线性方程组求解的三种Newtorfe比较 J.井冈山学院学报(自然科学),2006,27(8):8-11.2 余芝云，陈争，马昌凤.求解对称非线性方程组基于信赖域的修正牛顿法J.福建师范大学学报(自然科学版)，2010,26(1):22-27.3 Li D H, Cherg W Y. Recert progress ir the global convergence ofquasi-Newtor methods for rorlirear equations

18、J. Hokkaido Math J, 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 李敏，苏醒，时贞.求解非线性方程组的记忆梯度算法J.工程数学学报，2009,26 (3) : 563-566.9 Shi Z J . A new super-memory gradient method for unconstrainedoptimization J. Advances in Math