下载文档原格式
非线性方程组的求解摘要：非线性方程组求解是数学教学中，数值分析课程的一个重要组成部分，作为一门学科，其研究对象是非线性方程组。
求解非线性方程组主要有两种方法：一种是传统的数学方法，如牛顿法、梯度法、共轭方向法、混沌法、BFGS 法、单纯形法等。
传统数值方法的优点是计算精度高，缺点是对初始迭代值具有敏感性，同时传统数值方法还会遇到计算函数的导数和矩阵求逆的问题，对于某些导数不存在或是导数难求的方程，传统数值方法具有一定局限性。
另一种方法是进化算法，如遗传算法、粒子群算法、人工鱼群算法、差分进化算法等。
进化算法的优点是对函数本身没有要求，不需求导，计算速度快，但是精度不高。
关键字：非线性方程组、牛顿法、BFGS 法、记忆梯度法、Memetic 算法1： 三种牛顿法：Newton 法、简化Newton 法、修改的Newton 法【1-3】求解非线性方程组的Newton 法是一个最基本而且十分重要的方法, 目前使用的很多有效的迭代法都是以Newton 法为基础, 或由它派生而来。
n 个变量n 个方程的非线性方程组, 其一般形式如下:⎪⎪⎩⎪⎪⎨⎧===0),...,(...0),...,(0),...,(21212211n n n n x x x f x x x f x x x f （1）式(1)中,),...,(21n i x x x f ( i=1, ⋯, n) 是定义在n 维Euclid 空间Rn 中开域 D 上 的实值函数。
若用向量记号，令：⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=n x x x ...X 21,⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎣⎡====)(...)()(0),...,(...0),..,(0)...,()(2121212,211X f X f X f x x x f x x x f x x x f X F nn n n n则方程组（1）也可表示为：0)(=X F（2） 其中：X ∈R n ,F ∶R n →R 0, F(X) ∈R n , R n 为赋值空间。
非线性方程组的解法
非线性方程组的解法包括：
（1）近似法。
近似法是根据所给非线性方程组，使用一定的数值方法，建立非线性方程组结果的拟合曲线，以此求解非线性方程组的常用方法，目前有贝塔、拉格朗日近似法和微分近似法等。
（2）多元分割法。
多元分割法根据非线性方程组的参数和变量空间，
将整个运算范围分割成多余小区间，利用各区间中只含有一个未知变
量的简单方程组，将非线性方程组转换成多个一元方程组，再用一次法、弦截法和二分法等算法求解，最终得出整个非线性方程组的解。
（3）迭代映射法。
迭代映射法是通过给定一个初始值，然后利用迭代，反复运算，最终达到收敛点的一种方法，主要包括牛顿法、收敛法、
弦截法、松弛法和隐函数法等。
（4）最小二乘法。
最小二乘法是将非线性方程组表示为残差函数，然
后求解残差函数最小值，获得未知变量的最优解，常用于数值分析中。
（5）特征法。
特征法是采用将非线性方程组表示为线性方程组特征值
和它们关于某一特征量的关系式，利用梯度下降法，最小化残差函数，求解非线性方程组的方法。
以上是非线性方程组的解法的简单综述，它们在一定程度上增加了解决非线性方程组的效率，但并非所有情况都能使用以上求解方法。
正确使用相应的求解方法就可以有效的求解非线性方程组，以便更好的解决实际问题。
第四章 非线性方程组的解法4.1 非线性方程组的一般形式从上面两章中，我们研究了离散化结构中任一单元在t t t ∆+→的时间增量步内，由材料非线性引起的单元切线刚度阵是线性的，（如第三章得出的增量平衡方程p q k t ∆=∆ (7) （假定t 时刻的状态已知）），由此集合而成结构的增量平衡方程也是线性的P q K T ∆=∆，这就为求解整个的非线性过程准备了条件。
即只要确定每一步的切线刚度，通过求解一系列的线性方程组，累加起来就得到了解的全过程。
结构总的平衡方程是非线性的：P q q K =)( (1)i.e P K q 1-=。
令q q K R )(=0)()1(=-=→q R P F (1)’分段线性化是求解非线性问题中一个普遍有效的技术，但作为具体的解法还有许多种，主要的有：1、增量法―纯增量法2、迭代法―直接迭代法（刚线刚度法）、Newton-Raphson 迭代法（切线刚度法）3、.混合法―增量/迭代型方法4.2 载荷增量法（纯增量法）1、基本思想将一个非线性的全过程分成若干段，每一段用一个线性问题去近似。
如将一段取得足够小，总可以逼近真实的非线性过程。
方法：若将外载荷分成N 个增量步，而每个增量载荷为0P P i i λ∆=∆， i λ∆为载荷系数（或称载荷因子）， 则总载荷 0P P λ=；其中：∑=∆=Ni i 1λλ0P 为基准载荷.上面的结构平衡方程为0)()(=-=q R P q F (1)´i.e 0)()(0=-=q R P q F λ (2)λ1Δλ1P 0Δλ2P 0 λP 0λ2 λ3q 1 q 2q 3上式两边对λ微分得00F R P λλ∂∂=-=∂∂ (3)i.e 0)(0=-λd dqq K P T (4)如比例加载（力的大小和方向不变），有0P d dP λ=，代入(4)得1110()()..()T TT d q K qd P K q d P ie qK q P λ---==∆=∆ (5)将(5)式写成增量形式便有以下求解格式1101[()]i T i ii i i i iq K q P P P q q q λ---⎧∆=∆∆=∆⎨=+∆⎩ (6)2、求解步骤1）将载荷分成若干个增量步 01P P Ni i ∑=∆=λ ，准备位移量累加器[Q]并置零.2）施加第1个载荷增量 011P P λ∆=∆，计算qRq k t ∂∂=)(0线性 求解 1101)]([P q K q T ∆=∆-11q q ∆= 并送入位移量累加器[Q]3）施加第2个增量步 022P P λ∆=∆用1q ，求)(1q K T 即在1q 处的切线刚度矩阵 求解 2112)]([P q K q T ∆=∆-212q q q ∆+= 在位移量累加器[Q]中完成累加.4）重复3）直至(N )个载荷施加完毕, 在位移量累加器[Q]中得到总位移 ∑=∆=Ni i q q 13. 几何意义及讨论优缺点：优点：了解加载过程，当→∆P 足够小，总能收敛到真实解缺点：实际不可能无限小，因此累积误差，且无法估计，造成极大偏离而失真P 2 ΔλP 1 λP 0P 3 Δλ4.3 迭代法 1 直接迭代法1) 基本思想：将载荷一次加上，并假设一个初始解代入方程组求出第一次近似解；将其再代入方程组求解，得出第二次近似解，反复迭代逐次修正解，直至满足方程组（类似于对过渡单元加权平均ep D 中m 的迭代）。
非线性方程组的求解摘要：非线性方程组求解是数学教学中，数值分析课程的一个重要组成部分，作为一门学科，其研究对象是非线性方程组。
求解非线性方程组主要有两种方法：一种是传统的数学方法，如牛顿法、梯度法、共轭方向法、混沌法、BFGS 法、单纯形法等。
传统数值方法的优点是计算精度高，缺点是对初始迭代值具有敏感性，同时传统数值方法还会遇到计算函数的导数和矩阵求逆的问题，对于某些导数不存在或是导数难求的方程，传统数值方法具有一定局限性。
另一种方法是进化算法，如遗传算法、粒子群算法、人工鱼群算法、差分进化算法等。
进化算法的优点是对函数本身没有要求，不需求导，计算速度快，但是精度不高。
关键字：非线性方程组、牛顿法、BFGS 法、记忆梯度法、Memetic 算法1： 三种牛顿法：Newton 法、简化Newton 法、修改的Newton 法【1-3】 求解非线性方程组的Newton 法是一个最基本而且十分重要的方法, 目前使用的很多有效的迭代法都是以Newton 法为基础, 或由它派生而来。
n 个变量n 个方程的非线性方程组, 其一般形式如下:⎪⎪⎩⎪⎪⎨⎧===0),...,(...0),...,(0),...,(21212211n n n n x x x f x x x f x x x f （1）式(1)中,),...,(21n i x x x f ( i=1, ⋯, n) 是定义在n 维Euclid 空间Rn 中开域 D 上 的实值函数。
若用向量记号，令：⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=n x x x ...X 21,⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎣⎡====)(...)()(0),...,(...0),..,(0)...,()(2121212,211X f X f X f x x x f x x x f x x x f X F nn n n n则方程组（1）也可表示为：0)(=X F（2） 其中：X ∈R n ,F ∶R n →R 0, F(X) ∈R n , R n 为赋值空间。
非线性方程组的求解摘要：非线性方程组求解是数学教学中，数值分析课程的一个重要组成部分，作为一门学科，其研究对象是非线性方程组。
求解非线性方程组主要有两种方法：一种是传统的数学方法，如牛顿法、梯度法、共轭方向法、混沌法、BFGS 法、单纯形法等。
传统数值方法的优点是计算精度高，缺点是对初始迭代值具有敏感性，同时传统数值方法还会遇到计算函数的导数和矩阵求逆的问题，对于某些导数不存在或是导数难求的方程，传统数值方法具有一定局限性。
另一种方法是进化算法，如遗传算法、粒子群算法、人工鱼群算法、差分进化算法等。
进化算法的优点是对函数本身没有要求，不需求导，计算速度快，但是精度不高。
关键字：非线性方程组、牛顿法、BFGS 法、记忆梯度法、Memetic 算法1： 三种牛顿法：Newton 法、简化Newton 法、修改的Newton 法【1-3】 求解非线性方程组的Newton 法是一个最基本而且十分重要的方法, 目前使用的很多有效的迭代法都是以Newton 法为基础, 或由它派生而来。
n 个变量n 个方程的非线性方程组, 其一般形式如下:⎪⎪⎩⎪⎪⎨⎧===0),...,(...0),...,(0),...,(21212211n n n n x x x f x x x f x x x f （1）式(1)中,),...,(21n i x x x f ( i=1, ⋯, n) 是定义在n 维Euclid 空间Rn 中开域 D 上 的实值函数。
若用向量记号，令：⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=n x x x ...X 21,⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎣⎡====)(...)()(0),...,(...0),..,(0)...,()(2121212,211X f X f X f x x x f x x x f x x x f X F nn n n n则方程组（1）也可表示为：0)(=X F（2） 其中：X ∈R n ,F ∶R n →R 0, F(X) ∈R n , R n 为赋值空间。
一般地， 若在包含的某邻域D 内, 按某种近似意义,用线性函数:k k k b X A +=)X (l （3）近似地代替向量值函数F(X),此处A k 是n 阶矩阵，则可将线性方程组:k k k b X A +=)X (l （4）的解作为非线性方程组( 2) 的近似解。
1.1 Newton 法[1]Newton 法的迭代公式为：,...2,1,0k )-F(X )X )((X F'X X X k k k k k 1k =⎩⎨⎧=∆∆+=+ (5）其中k 1k k X -X X +=∆.1.2 简化Newton 法[1]尽管Newton 法具有较高的收敛速度，但在每一步迭代中，要计算n 个函数值f ，以及n 2个导数值f ′形成Jacobi 矩阵)('k X f ，而且要求)('k X f 的逆阵或者解一个n 阶线性方程组，计算量很大。
为了减少计算量，在上述Newton 法中对一切k=0,1,2,...,取)('k X f 为.)('X f ，于是迭代公式修改为：[]...2,1,0),X ()X ('X X k 1k k 1k =-=-+k f f (6) 式( 5) 即为简化的Newton 法。
该方法能使计算量大为减少，但却大大降低了收敛速度。
简化的Newton 法的算法与Newton 法的算法区别就在于只由给定的初始近似值计算一次)('X f ，以后在每一次迭代过程中不再计算)('k X f ，保持初始计算值。
1.3 修正的Newton 法[2]吸取Newton 法收敛快与简化的Newton 法工作量省的优点，文献【2】把m 步简化的Newton 步合并成一次Newton 步。
则可以得到下列迭代程序:⎪⎭⎪⎬⎫=-==+--m ,k 1k 1j ,k 1k j ,k j k ,k k ,0X X )X (f )X ('f X X X X (7)式中: j=1, 2, ⋯, m, k=0, 1, 2, ⋯, 该式称为修正的Newton 法。
通过分析Newton 法、简化的Newton 法和修正Newton 法的原理, 并通过对算例的分析比较，我们可知: Newton 法(5)式具有较高的收敛速度，但计算量大，在每一步迭代中，要计算n 个函数值f ，以及n2个导数值f'形成Jacobi 矩阵)('k X f ，而且要求)('k X f 的逆阵或者解一个n 阶线性方程组；简化的Newton 法( 6) 式，它用迭代初值X 0来计算)('k X f ，并在每个迭代步中保持不变，它能使每步迭代过程的计算量大为减少，但大大降低了收敛速度。
修正Newton 法(7)与Newton 法(5)相比，在每步迭代过程中增加计算n 个函数值，并不增加求逆次数，然而收敛速度提高了。
2： BFGS 法【4-6】非线性方程组一般形式为:方程组（1）将其转化为一个全局优化问题。
构造能量函数：）（）（n ni i x x x X X f X ,...,),(2112==Φ∑=求非线性方程组解的问题就转化为求解能量函数极小值的问题。
即给定一个充分小的实常数ε，搜索）（**2*1*,...,X n x x x =使得εφ<）（*X 则X *即是非线性方程组（1）对应的近似解。
2.1 BFGS 查分算法【4】文献【4】将传统的BFGS 算法和查分算法有机融合，用来求解非线性方程组，效果显著，可以较为广泛地应用于非线性方程组的求解。
BFGS 方法是由Broyden 、Fletcher 、Goldfarb 和Shanno 等人在1970年提出的。
它是一个拟牛顿方法，具有二次终止性、整体收敛性和超线性收敛性，且算法所产生的搜索方向是共轭的。
BFGS 方法是一个有效的局部算法，用来求解极小值的。
例如方程组⎪⎪⎩⎪⎪⎨⎧===nn n n n A x x x f A x x x f A x x x f ),...,(...),...,(),...,(2122121211 （8） 可将它够着适应度函数∑=-=n i i i A x f X F 1|)(|)( (9)那么求非线性方程组（8）的根问题就转化成了求适应度函数）（X F 最小值的优化问题。
这就是它最基本的思想。
DE 算法(差分进化算法)（文献【5】）具有良好的全局搜索能力，并具有对初始值、参数选择不敏感、鲁棒性强、原理简单、容易操作等优点，是一种较好的全局优化方法。
但在优化后期DE 算法的收敛速度明显变慢，而且搜索结果仅获得满意解域而不是精确解。
为了克服这些缺点，该文在DE 算法的进化后期阶段引入BFGS 方法，利用BFGS 方法的整体收敛性和超收敛性来加快收敛速度。
BFGS 方法属于局部算法，其优化结果的优劣在很大程度上取决于初始值的选取，为此可以利用具有全局搜索能力的DE 算法提供给BFGS 方法良好的初始值。
2.2 改进的BFGS 变尺度法【4】对于高维的大型问题（维数大于100），变尺度法由于收敛快、效果好，被认为是最好的优化方法之一。
其中BFGS 法的数值稳定性较好，是最成功的一种变尺度法。
BFGS 法中有2个非常关键的环节：求函数的偏导数和一维探索。
这2个环节的算法精度对最后结果的精度影响很大。
2.2.1 改进的遗传算法【7】遗传算法的优越性主要表现在：算法具有固有的并行性，通过对种群的遗传处理可处理大量的模式，并且容易并行实现。
(a) 选择复制操作采用保优操作与比例复制相结合, 即最优秀的个体被无条件保留下来,其余的以正比于个体适配值的概率来选择相应的个体。
(b) 交叉操作采用保优操作与算数交叉结合,即最优秀的个体被无条件保留下来，其余的以交叉概率进行算数交叉。
算数交叉的方式为:122211)1(,)1(X X X X X X αααα-+=-+= (10) 式中21,1,0X X ）；（∈α为父代个体；X 1,X 2为后代个体。
（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]考虑非线性方程组n R x x F ∈=,0)( ， （11）其中n n R R F →:是非线性映射。
定义T n x F x F x F x F ))(),...(),(()(21=，其雅可比矩阵J(X)。
记忆梯度法(文献【8-9】)是求解无约束优化问题非常有效的方法，该方法在每步迭代时不需计算和存储矩阵，结构简单，因而适于求解大型优化问题。
算法的基本思想是: 首先将非线性方程组问题(12)转化为一个无约束极小化问题n R x x f ∈),(min , (12) 其中2)(21)(x F x f =。
这里.采用二范数，然后利用记忆梯度法求解问题(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 算法是建立在模拟文化进化基础上的优化算法，它实质上是一种基于种群的全局搜索和基于个体的局部启发式搜索的结合体。
