打开文本图片集
【摘要】对于非线性问题，大多数转化为非线性方程（组）来求解，具体的解决方法有牛顿法、割线法、延拓法、搜索法、梯度法、信赖域法、共轭方向法、变尺度法等.本文主要介绍求解非线性方程组的牛顿型算法、信赖域算法、遗传算法三种方法.
【关键词】非线性方程组；牛顿型算法；信赖域算法；遗传算法
一、引言
非线性科学在工业、农业、科学研究领域占有重要地位，绝大多数问题最终都能转化为非线性方程（组）的求解问题，传统的解决方法有：牛顿法、割线法、延拓法、搜索法、梯度法、信赖域法、共轭方向法、变尺度法等.本文着重介绍信赖域算法、牛顿型算法、遗传算法三种方法.
非线性方程组为
fj（x1，x2，…，xn）=0（j=1，2，…，m）.（1）
其中X=（x1，x2，…，xn）∈DRn，D={（x1，x2，…，xn）"ai≤xi≤bi，i=1，2，…，n}.
解非线性方程组一般分为两类方法：一类属于线性化方法，即把非线性方程组转化为一种近似的非线性方程组，构造出迭代格式，然后逐次接近准确解，达到满足精度要求就终止计算；一类属于求函数极值方法，即由非线性函数构造出一个目标函数，把方程组的求解问题转化为求目标函数的极值点问题.构造目标函数：
F（x1，x2，…，xn）=∑mi=1|fi（x1，x2，…，xn）|.
这样，在区域内求解非线性方程组问题（1）就转化为了函数优化问题：
minF（x1，x2，…，xn）s.t（x1，x2，…，xn）∈D.（2）
显然，满足F（x*1，x*2，…，x*n）=0的非线性方程组的解X*（x*1，x*2，…，x*n）就是函数优化问题（2）的最优解.
二、牛顿型算法
求解非线性方程组的线性化方法为：
xk+1=xk-[A（xk）]-1F（xk）（k≥1）.（3）
若取A（xk）=
SymbolQC@ F（xk），则得到求解非线性方程组的牛顿型迭代算法.
1牛顿法
牛顿法算法程序构造过程实际上是对非线性方程组（1）左端的非线性函数逐步线性化的过程.假定F：D∈Rn→Rn在开凸集内二次G-可导，且F″（x）在D内连续.设x*∈D是（1）式的解，x0∈D是x*的初始近似值.牛顿法虽然有收敛速度快和自校正等优点，但应用到实际计算中仍存在不少问题：迭代初始值x0要求与解x*很接近；每次迭代计算Jacobi矩阵F′（xk）和求解一个线性方程F′（xk）Δx=-F（xk），工作量较大；当F′（xk）奇异或是病态时，计算将无法进行下去.为了解决这些问题，牛顿法有了如下几种变形.
2修正牛顿法
修正牛顿法主要是针对牛顿法计算量较大进行简化和改进，将牛顿法收敛快和简化牛顿法工作量省的优点结合起来，得到如下迭代程序：
x0k=xkxik=xi-1kxk+1=xmk-[F′（xk）]-1F（xi-1k）（i=1，…m；k=1，2，3，…）.（4）
从xk计算到xk+1中间做m次简化，只需计算一次Jacobi矩阵F′（xk）和求一次逆矩阵[F′（xk）]-1，这种修正牛顿法具有m+1阶收敛速度.
3参数牛顿法
参数牛顿法是为了保证每一步迭代中的F′（xk）非奇异或非病态，而引入所谓的阻尼因子λk使F′（xk）+λkI（这里I为n阶单位矩阵）非病态，此时得到迭代程序为：
xk+1=xk-[F′（xk）+λkI]-1F（xk）（k=0，1，2，…）.（5）
当λk选得足够大，可以使矩阵F′（xk）+λkI对角占优，从而消除F′（xk）的奇异性，并具有局部收敛性.
4下降牛顿法
为了克服牛顿法的局部收敛，初始点x0选取要很靠近解x*，引入迭代参数，采用下降法思想具有大范围收敛的牛顿下降法，其迭代程序为：
xk+1=xk-ωk[F′（xk）]-1F（xk）（k=0，1，…）.（6）
其中0<ωk≤1是迭代参数，可以证明迭代式具有大范围收敛性，但实际应用中选择ωk仍比较困难.
牛顿法及其改进形式是最基础、应用广泛的求解非线性方程组方法，但由于牛顿法需要每步计算函数的导数，若导数不能直接表示出来，则很难求解，且在实际应用中往往受到很多条件的限制，它的收敛性和性能特征在很大程度上依赖于初始点的选择；另外，牛顿型算法在处理某些形式比较复杂的非线性方程组时效果不好.因此，牛顿法的各种变型都是针对牛顿法的某一缺陷而考虑的，实际应用时只能根据要解决主要问题采取相应的策略.
三、信赖域方法
信赖域方法首先定义一个在当前点与目标函数近似的二次模型，利用目标函数在一定的区域内与二次模型的充分近似，取二次模型的最优值作为信赖域方法的下一个迭代点.其出发点是利用目标函数的二次模型的近似程度来调节信赖域的大小：若新的迭代点不能使目标函数值有充分的下降，说明二次模型与目标函数的近似程度不够好，需要缩小信赖域半径；否则就扩大信赖域半径.
对非线性方程组F（x）=0的求解可转化为如下无约束优化问题：
minf（x）x∈RN=12‖F（x）‖2.（7）
相应的二次信赖域优化模型：
mk（d）=12‖Fk+Jkd‖2=fk+dTJTkFk+12dTgTkJkd.
其中，Jk=
SymbolQC@ F（xk）为F（x）在xk点Jacobi矩阵.
对于（7），在xk点的下降方向dk有下述信赖域子问题产生.
minmk（d）s.t.‖d‖≤Δk（其中Δk>0为信赖域半径）.（8）
四、遗传算法
求解非线性方程组对于传统算法的选择、构造与所要解决问题的特性有很大关系.遗传算法不采用确定性规则，而采用概率的变迁规则来指导它的搜索方向，是一种灵活的自适应算法，无需过多考虑问题的具体形式.由于非线性方程组改造成的函数多数是多峰值函数，遗传算法在其求解应用中具有较大优势，尤其在一些非线性方程组没有精确解的时候，遗传算法显得更为有效，近几年利用遗传算法求解非线性方程组的数值问题也有相关的研究成果.
刘灿文等“基于求解非线性方程组的并行遗传算法的设计”提出了将非线性方程组的数值求解问题（1）转化为线性约束最优化问题：
min{gf（x）}，x∈D.
其中gf（x）=1n∑ni=1|fi（x）|为非线性方程组（1）的误差度量函数.将遗传算法改进为自适应并行遗传算法求解该最优化问题，从另一角度为求解非线性方程组提供了一条比较有效的途径.
曾毅“改进的遗传算法在非线性方程组求解中的应用”提出利用改进的遗传算法求非线性方程组的解，数值模拟结果表明改进后的遗传算法不仅可以求得高精度的解，而且大大提高了遗传算法的局部寻优能力.曾毅“浮点遗传算法在非线性方程组求解中的应用”提出利用浮点遗传算法适应值的分布和实数编码的特点，通过缩小、移动搜索空间的方法，将整体和局部寻优能力有机结合，数值模拟结果表明该算法求精确解的有效性.吴国辉等“一种新的求解非线性方程组的混合遗传算法”提出利用浮点遗传算法全局群体搜索能力及起始搜索速度快的特点，快速得到接近精确解的较优解，之后将其作为拟牛顿法迭代的初始值，利用其局部寻优能力非常强的特点快速迭代至精确解，该算法融合了遗传算法和拟牛顿法的优点，具有较好的收敛速度和相当精度的收敛解.杜娟等“一种新的非线性方程组的混合量子遗传算法”综合考虑了量子遗传算法和拟牛顿法的各自优点，结合两者提出一种求解非线性方程组的有效算法，充分发挥量子遗传算法的群体搜索和全局收敛性，同时采用拟牛顿法作为一个强局部搜索算子，把量子遗传算法的寻优结果作为拟牛顿算法的初值，有效地解决了拟牛顿法对初始值的敏感问题，提高了算法的局部搜索能力，仿真实验表明此算法具有较高的求解精度与成功率.
总之，遗传算法在求解非线性方程组具有一定的优势，但仍存在一些问题有待于进一步研究，如增强局部搜索能力、快速达到最优解、改造遗传算法防止早熟、恰当选择参数等问题.如何改进遗传算法或结合传统的算法，更好地应用于解决各类复杂的非线性系统，这将是需要继续探索的课题.
推荐访问： 方程组 求解 三种 算法