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

毕业论文原创性声明本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写的成果或作品。本人完全意识到本声明的法律后果由本人承担。作者签名： 年 月 日毕业论文版权使用授权书本毕业论文作者完全了解学院有关保存、使用毕业论文的规定，同意学院保留并向有关毕业论文管理部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权本学院及以上级别优秀毕业毕业论文评选机构将本毕业论文的全部或部分内容编入有关数据库以资检索，可以采用复印、缩印或扫描等复制手段保存和汇编本毕业论文。声明人签名： 导师签名： 求解非线性方程组的方法研究摘 要如今，随着现代科学技术的飞速发展以及计算机的广泛普及，非线性的问题成为了工程应用领域和数值计算中重要的研究内容。因为在工程实践、经济学、信息安全和动力学等许多领域中被涉及的越来越多，并逐渐占有不可缺少的地位。传统的求解非线性方程组的方法包括牛顿法、拟牛顿法、梯度法等方法。近年来，在优化领域里诞生了许多运用仿生学的优化算法，如粒子群算法、遗传算法、鱼群算法等等。上述所说的方法各有各的优缺点。根据算法的原理，说明牛顿法、拟牛顿法，遗传算法的使用方法，利用Matlab对方程组进行编程，对比三种算法的数值实验结果，讨论三种算法的优劣势。关键词：非线性方程组 牛顿法 拟牛顿法 遗传算法目 录摘 要 .11 绪论 .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年在Method of Fluxions中公开提出。而事实上该方法已经由Joseph Raphson在1690年在Analysis Aequationum中提出。牛顿法是一种在实数域和复数域上求方程近似解的方法 8。在方程的根附近有平方收敛是此方法一个很大的优点，此方法也可以用来求非线性方程的重根和复根。另外该方法可以用Matlab来进行数值实验。本文也介绍了牛顿法的Matlab 编程。拟牛顿法(Quasi-Newton Methods)于20世纪50年代由美国Argonne国家实验室的物理学家WC Davidon所提出来。这被认为是求解非线性优化问题最有效的方法之一。不久RFletcher和M. JDPowell证实了这种新的算法远比其他方法快速和可靠，使得非线性优化问题在此后的飞速发展。拟牛顿法要求每一次迭代时都要得到函数的梯度。通过计算梯度的变化，构造一个目标函数的模型使函数具有超线性收敛性。这类方法大大优于最速下降法，尤其对于困难的问题。另外，因为拟牛顿法不需要求得目标函数的二阶导数，所以有时拟牛顿法比牛顿法更为有效。求解非线性方程组的方法研究2遗传算法是一类借鉴生物界的进化规律（适者生存，优胜劣汰遗传机制）演化而来的随机化搜索方法 9。它是由美国的J.Holland教授1975 年首先提出，其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。遗传算法的这些性质，已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域 10。在现代有关智能计算中它起着至关重要的作用1.3本文的主要工作根据构造一个非线性方程组来解决一下几个问题：(1)写出算法的推导公式，(2)用Matlab进行编程，(3)得出结论。第一章：绪论。本章主要介绍牛顿法，拟牛顿法和遗传算法在国内外研究状况。第二章：详细介绍求解非线性方程组的经典算法牛顿法和拟牛顿法的思想，并给出算法，进行数值实验，总结算法的优缺点。第三章：详细介绍求解非线性方程组的遗传算法思想，并给出算法，总结算法优缺点。第四章：结论与展望。本章主要对全文所介绍的三种方法进行了总结。昌吉学院2016届本科生毕业论文（设计）32求解非线性方程组的方法介绍非线性方程组一般表达式如（2-1）（2-1）1(1,2,3,)=0,2(1,2,3,)=0,3(1,2,3,)=0,(1,2,3,)=0,其中， 是定义在 维空间 中的实值函数。引进向量，记(=1,2,3,) （2-2）()=1()2()3()()， =123 ， 0=0000则公式（2-2）可以写成， （2-3）()=0牛顿法解非线性方程组的基本思想与解线性方程组的迭代解法相同，它主要包括两个方面：一个是构造合适的迭代格式，另一个是研究迭代格式的收敛性和收敛速度。为了得到方程组的迭代格式，先将其改写成下面等价的方程组， ()=然后给定一个初始值 代入左端算出 ，再将 代入左端算出 ，0 (0)=1 1 (1)=2可得到一个迭代序列, ,()=+1 =0,1,2,2.1牛顿法设 是函数 的一个近似根，把 在 进行Taylor展开得： ()=0 () ()=()+()()+12!“()()2+（2-4）+ 1(1)!(1)()()1+1!()()()取一阶近似，可得：（2-5）() ()+()()设 可逆，则可得迭代公式：“()求解非线性方程组的方法研究4（2-6）+1=()()这就是经典的迭代公式下面讨论牛顿法的收敛性定理1：设 在D上三阶可微，且是非线性方程组的一个实数根，则此迭代()： ，格式具有二阶收敛性。证明：(1)选取迭代公式（2-7）()=()1()则（2-8）()=()1()则 （2-9）()=01即非线性方程组 在D上存在根 ，则该迭代序列 收敛于 。且当 时，当()=0 时， ， 0lim+1 =0由上可得此迭代序列 是超线性收敛的。又因为()()() () 122所以 ，其中()()=()1() =()1且有 ()1 2 2(322)=32所以对 ，上式都成立。现在取 =， ()=+1， ()=