求解非线性方程组的方法研究

Ⅰ毕业论文原创性声明本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写的成果或作品。本人完全意识到本声明的法律后果由本人承担。作者签名：年月日毕业论文版权使用授权书本毕业论文作者完全了解学院有关保存、使用毕业论文的规定，同意学院保留并向有关毕业论文管理部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权本学院及以上级别优秀毕业毕业论文评选机构将本毕业论文的全部或部分内容编入有关数据库以资检索，可以采用复印、缩印或扫描等复制手段保存和汇编本毕业论文。声明人签名：导师签名：求解非线性方程组的方法研究Ⅱ摘要如今，随着现代科学技术的飞速发展以及计算机的广泛普及，非线性的问题成为了工程应用领域和数值计算中重要的研究内容。因为在工程实践、经济学、信息安全和动力学等许多领域中被涉及的越来越多，并逐渐占有不可缺少的地位。传统的求解非线性方程组的方法包括牛顿法、拟牛顿法、梯度法等方法。近年来，在优化领域里诞生了许多运用仿生学的优化算法，如粒子群算法、遗传算法、鱼群算法等等。上述所说的方法各有各的优缺点。根据算法的原理，说明牛顿法、拟牛顿法，遗传算法的使用方法，利用Matlab对方程组进行编程，对比三种算法的数值实验结果，讨论三种算法的优劣势。关键词：非线性方程组牛顿法拟牛顿法遗传算法Ⅰ目录摘要......................................................................21绪论......................................................................11.1研究目的及意义........................................................11.2国内外研究现状........................................................11.3本文的主要工作........................................................22求解非线性方程组的方法介绍................................................32.1牛顿法................................................................32.2拟牛顿法.............................................................63遗传算法................................................................103.1遗传算法的来源.......................................................103.2遗传算法的思想.......................................................103.3遗传算法的实现.......................................................103.4小结.................................................................154总结与展望...............................................................164.1总结.................................................................164.2展望.................................................................16参考文献...................................................................17致谢.......................................................................18昌吉学院2016届本科生毕业论文（设计）11绪论1.1研究目的及意义如今，随着现代科学技术的飞速发展以及计算机的广泛普及，非线性的问题成为了一个基本而又重要的问题，因为在工程实践、经济学、信息安全和动力学等等许多领域中被涉及的越来越多，并逐渐占有不可缺少的地位。以致寻找一个好的方法逐渐成为工程应用和数值计算中重要的研究内容[1]。随着对工程数学计算精度的要求越来越高，使研究非线性方程组的求解取得了突破性的进展，从而逐渐成为现代数学研究的一个分支，是解决实际问题的一个重要学科。对于非线性方程组的实际问题，在很多情况下不必求出方程组的真实解，而是只需求得一个近似值，此近似值可以通过数值方法来获得，当然此近似值与真实解之间的误差应该控制在实际问题所能接受的范围之内。从而，研究非线性方程组的数值解法有着重要的理论意义和实际应用价值[2-3]。目前，关于求解非线性方程组的数值方法研究比较广泛，传统的求解方法包括牛顿法、拟牛顿法、梯度法等方法[4]，但这些方法存在着收敛性差、初值不敏感等不足。人工智能算法[5]是近几年研究的一种新方法，它广泛应用于智能控制，信息安全等方面。本论文通过传统方法与遗传算法[6]的比较，阐述遗传算法在解决实际问题中的优势。1.2国内外研究现状目前国内外求解非线性方程组已有多种解法，如牛顿迭代法、大范围收敛法、人工智能法[7]等。其中最常用、最基本的是牛顿迭代法，牛顿迭代法在理论上已经达到了比较成熟的阶段，各种以牛顿迭代法为基础的高级收敛法也得到了不断地完善。牛顿法又叫迭代法，最初是由物理学家艾萨克·牛顿于1736年在MethodofFluxions中公开提出。而事实上该方法已经由JosephRaphson在1690年在AnalysisAequationum中提出。牛顿法是一种在实数域和复数域上求方程近似解的方法[8]。在方程的根附近有平方收敛是此方法一个很大的优点，此方法也可以用来求非线性方程的重根和复根。另外该方法可以用Matlab来进行数值实验。本文也介绍了牛顿法的Matlab编程。拟牛顿法(Quasi-NewtonMethods)于20世纪50年代由美国Argonne国家实验室的物理学家W·C·Davidon所提出来。这被认为是求解非线性优化问题最有效的方法之一。不久R·Fletcher和M.·J·D·Powell证实了这种新的算法远比其他方法快速和可靠，使得非线性优化问题在此后的飞速发展。拟牛顿法要求每一次迭代时都要得到函数的梯度。通过计算梯度的变化，构造一个目标函数的模型使函数具有超线性收敛性。这类方法大大优于最速下降法，尤其对于困难的问题。另外，因为拟牛顿法不需要求得目标函数的二阶导数，所以有时拟牛顿法比牛顿法更为有效。遗传算法是一类借鉴生物界的进化规律（适者生存，优胜劣汰遗传机制）演化而来的随机化搜索方法[9]。它是由美国的J.Holland教授1975年首先提出，其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的求解非线性方程组的方法研究2全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。遗传算法的这些性质，已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域[10]。在现代有关智能计算中它起着至关重要的作用1.3本文的主要工作根据构造一个非线性方程组来解决一下几个问题：(1)写出算法的推导公式，(2)用Matlab进行编程，(3)得出结论。第一章：绪论。本章主要介绍牛顿法，拟牛顿法和遗传算法在国内外研究状况。第二章：详细介绍求解非线性方程组的经典算法牛顿法和拟牛顿法的思想，并给出算法，进行数值实验，总结算法的优缺点。第三章：详细介绍求解非线性方程组的遗传算法思想，并给出算法，总结算法优缺点。第四章：结论与展望。本章主要对全文所介绍的三种方法进行了总结。昌吉学院2016届本科生毕业论文（设计）32求解非线性方程组的方法介绍非线性方程组一般表达式如（2-1）（2-1）其中，是定义在维空间中的实值函数。引进向量，记（2-2）则公式（2-2）可以写成，（2-3）牛顿法解非线性方程组的基本思想与解线性方程组的迭代解法相同，它主要包括两个方面：一个是构造合适的迭代格式，另一个是研究迭代格式的收敛性和收敛速度。为了得到方程组的迭代格式，先将其改写成下面等价的方程组，然后给定一个初始值代入左端算出，再将代入左端算出，…，可得到一个迭代序列,…,2.1牛顿法设是函数的一个近似根，把在进行Taylor展开得：（2-4）取一阶近似，可得：（2-5）设可逆，则可得迭代公式：（2-6）这就是经典的迭代公式下面讨论牛顿法的收敛性求解非线性方程组的方法研究4定理1：设在D上三阶可微，且η是非线性方程组的一个实数根，则此迭代格式具有二阶收敛性。证明：(1)选取迭代公式（2-7）则（2-8）则（2-9）即非线性方程组在D上存在根，则该迭代序列收敛于。且当时，当时，，由上可得此迭代序列是超线性收敛的。又因为所以，其中且有所以对，上式都成立。现在取则可得由上可得该迭代格式至少为2阶收敛。(2)对，有。另取，，当。由上可得该迭代格式的收敛阶。所以，该迭代格式收敛阶为2阶。牛顿算法具体步骤列为①给定初始点，设定收敛判据，②计算和。若则停止计算，否则确认搜索方向。④从出发，沿做维搜索，。⑤设通过上述定理可知，牛顿迭代法收敛速度快，这是它最突出的优点。但是它也有缺陷，原始牛顿法虽然具有二次终止性（即用于二次凸函数时，经有限次迭代必达极小点），但是要求初值的选取必须准确，否则有可能不收敛。优势也会产生迟滞。每步迭代都要计算矩阵，计算量较大。昌吉学院2016届本科生毕业论文（设计）5Matlab实现牛顿法用LATLAB求解下列非线性方程组（2-10）程序如图2-1所示图2-1牛顿法程序求解非线性方程组的方法研究6执行结果如图2-2所示图2-2牛顿法结果2.2拟牛顿法牛顿法虽然计算时收敛速度快，但是在计算的过程中需要得到目标函数的二阶偏导数，对于有些函数不易求得。更为复杂的是目标函数的Hesse矩阵无法得到或准确度不高，从而使牛顿法失效。Argonne提出的拟牛顿法就很好的解决了类问题。这个方法的基本思想是不用二阶偏导数就可以构造出近似Hesse矩阵的逆的正定对称阵，从而在拟牛顿的条件下优化目标函数[11]。构造方法的不同决定了不同的拟牛顿法。下面我们讨论拟牛顿法推导公式。首先分析如何构造矩阵可以近似Hesse矩阵的逆：设第k次迭代之后得到点，将目标函数在处展成Taylor级数，取一阶近似，得（2-11）因此令，则令，同时设Hesse矩阵可逆，则方程（2-11）可表示为（2-12）昌吉学院2016届本科生毕业论文（设计）7因此，只需计算目标函数的一阶导数，就可以依据方程(2-12)估计该处的Hesse矩阵的逆。为了用不包含二阶导数的矩阵，必须满足（2-13）方程(2-13)也称为拟牛顿条件。下面给出两个最常用的构造公式的构造公式DFP公式设初始的矩阵为单位矩阵I，然后通过修正给出，即（2-14）布洛伊登矫正公式如下（2-15）（2-16）DFP公式DFP算法中定义校正矩阵为（2-17）可以验证，这样产生的对于二次凸函数而言可以保证给定，且满足拟牛顿条件。BFGS公式FGS公式和DFP公式的互为对偶公式。这是因为其推导过程与方程(2-14)完全一样，只需要用矩阵取代，同时将和互换，最后可以得到（2-18）这个公式要优于DFP公式，因此目前得到了最为广泛的应用