非线性方程不动点算法及研究本科生毕业论文.doc

本科生毕业论文论 文 题 目： 非线性方程求解的 不动点算法及研究 （20 14届） 本科生毕业论文非线性方程求解的不动点算法及研究 毕业设计（论文）原创性声明和使用授权说明原创性声明本人郑重承诺：所呈交的毕业设计（论文），是我个人在指导教师的指导下进行的研究工作及取得的成果。尽我所知，除文中特别加以标注和致谢的地方外，不包含其他人或组织已经发表或公布过的研究成果，也不包含我为获得 及其它教育机构的学位或学历而使用过的材料。对本研究提供过帮助和做出过贡献的个人或集体，均已在文中作了明确的说明并表示了谢意。作 者 签 名： 日 期： 指导教师签名： 日期： 使用授权说明本人完全了解 大学关于收集、保存、使用毕业设计（论文）的规定，即：按照学校要求提交毕业设计（论文）的印刷本和电子版本；学校有权保存毕业设计（论文）的印刷本和电子版，并提供目录检索与阅览服务；学校可以采用影印、缩印、数字化或其它复制手段保存论文；在不以赢利为目的前提下，学校可以公布论文的部分或全部内容。作者签名： 日 期： 学位论文原创性声明本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。作者签名： 日期： 年 月 日学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权 大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。涉密论文按学校规定处理。作者签名：日期： 年 月 日导师签名： 日期： 年 月 日注 意 事 项1.设计（论文）的内容包括：1）封面（按教务处制定的标准封面格式制作）2）原创性声明3）中文摘要（300字左右）、关键词4）外文摘要、关键词 5）目次页（附件不统一编入）6）论文主体部分：引言（或绪论）、正文、结论7）参考文献8）致谢9）附录（对论文支持必要时）2.论文字数要求：理工类设计（论文）正文字数不少于1万字（不包括图纸、程序清单等），文科类论文正文字数不少于1.2万字。3.附件包括：任务书、开题报告、外文译文、译文原文（复印件）。4.文字、图表要求：1）文字通顺，语言流畅，书写字迹工整，打印字体及大小符合要求，无错别字，不准请他人代写2）工程设计类题目的图纸，要求部分用尺规绘制，部分用计算机绘制，所有图纸应符合国家技术标准规范。图表整洁，布局合理，文字注释必须使用工程字书写，不准用徒手画3）毕业论文须用a4单面打印，论文50页以上的双面打印4）图表应绘制于无格子的页面上5）软件工程类课题应有程序清单，并提供电子文档5.装订顺序1）设计（论文）2）附件：按照任务书、开题报告、外文译文、译文原文（复印件）次序装订3）其它摘 要 非线性方程在工程实践、经济学信息安全和动力学等方面的大量实际问题中有着极为广泛的应用，而不动点迭代算法作为数学研究的一个新方向，是求解非线性方程问题的一个最基本而又重要的方法. 本文主要介绍了非线性方程求解的不动点算法及其研究，首先，综述了非线性方程求解的不动点算法的研究背景、并阐述了本文的主要工作以及介绍了误差、有限差等基本知识；然后，详细介绍了不动点迭代算法的基本思想、在什么条件下方程存在不动点的收敛定理、不动点的收敛阶定理和atiken加速公式；最后，考虑到方程可能会不满足不动点迭代收敛定理的两个条件的情况提出了反函数法、牛顿迭代法、steffensen迭代法和松弛法这四中处理方法.关键词：非线性方程，不动点原理，迭代法ivabstracta large number of practical problems of nonlinear equations in engineering practice,economics of information security and other the dynamics has a very wide range of applications.as a new direction in the study of mathematics,fixed point iterative algorithm is a basic and important methods to solving nonlinear equations problem.this paper describes the solving nonlinear equations fixed point algorithm and research. first, the research background of solving nonlinear equations fixed point algorithm and the main word are introduced, the basic knowledge of errors,finite difference are introduced ; second, the fixed point iterative basic idea, algorithm convergence and convergence rate and the aitken formula are detailed; last, inverse function method, the newton iterative method,steffensen iterative method and the relaxation method are proposed when the equation dose not satisfy the fixed point iteration convergence conditions.keywords: nonlinear equation, fixed point theorem, iterative method 目 录摘 要iabstracti第1章 绪 论11.1 研究背景11.2 预备知识21.2.1 误差21.2.2 有限差3第章 非线性方程求解的不动点迭代算法52.1不动点迭代算法的基本思想62.2 不动点迭代算法的收敛性72.3 不动点迭代算法的收敛速度112.4 加速不动点迭代算法及其收敛性12第3章 非收敛不动点迭代格式的几类处理方法与比较143.1 非收敛不动点迭代格式的几类处理方法153.1.1 反函数法153.1.2 牛顿迭代法153.1.3 steffensen迭代法153.1.4 松弛法163.2 数值实例17结 论21参考文献23附 录24致 谢3537 第1章 绪 论1.1 研究背景 非线性数值解的问题是现代数学的主要研究课题之一，这不仅是由于科学技术发展的需要，而且也是由于计算技术的高速发展提供了解决这类问题的可能，利用计算机解决非线性问题时，最终总是将其化成为有限维非线性问题，或称为非线性代数问题对于求解非线性方程，无论从理论上还是从计算机上，都比解线性问题要复杂的多，一般的非线性方程是很难求出精确解的，往往只能求出近似解、数值解，而长期以来，人们为了得到满足条件的近似值，许多计算工作者致力于研究求解非线性方程的有效方法，尤其是计算机出现后函数方程求根的数值解法得到了蓬勃发展，十七世纪，微积分出现时，newton和halley发明了各自的新的数学工具去解非线性方程，十八世纪，随着微积分的快速蓬勃发展，euler和lagrange分别找到了一个无穷级数来表示方程解，并以各自的名字来命名，十九世纪，人们开始注重问题分析的严密性，柯西建立了优级数技巧，该技巧不断的被以后的事实证明对于研究方程近似解序列的收敛性是很有成效的，在分析严密性发展的时代，ostrowski对newton迭代法的收敛性问题规定了一个合理的假设和一个令人满意的解法，在软件分析完善的年代，kantorovich把newton迭代法和ostrowski的结果推广到banach空间，从而使许多用硬分析去做非常棘手的有关问题被轻轻松松地推论中得到了令人满意的解决，等等，总之，这些方法不断地被后人完善，但在目前，实际问题中可能还需要求方程的负根，求非线性方程（组）的迭代法，求微分方程迭代法等等，迭代方法还需要更深入的研究，同时意味着迭代法的发展空间将会更广阔本文将着重介绍求解非线性方程的不动点算法，其中文献3是由王则柯先生于1988年总结的单纯不动点算法，他简述了不动点在非线性方程数值解、微分方程初值问题、边值问题、分支问题等许多应用问题方面的十多年的发展，以及对单值连续映射的不动点或零点问题进行了讨论，在文献4中，许炎先生简单的阐述了国内外有关不动点理论的发展状况，并主要讨论了l-lipschitz映射的不动点迭代逼近定理，34这两篇文献都总结出了不动点问题的研究和解决在实际问题中起到了至关重要的作用，这一系列的文献还有5678，而秦小龙先生在文献9中介绍了迭代法的发展情况以及相关定理，为本篇论文提供了大量的基础信息，王公俊先生在文献10中分别介绍了常用的求解非线性方程的方法以及收敛性，在文献11中，张卷美主要研究了一类不动点迭代法的求解，在迭代格式不满足迭代条件的情况下，运用的几种处理方法，并且用语言编程上机进行了计算，对迭代收敛结果进行了分析和比较，为本文提供了大量的信息，另外，本文还借鉴了2本不同出版社的数值分析教材的大量内容本文主要介绍了非线性方程求解的不动点算法及其应用，第一章为绪论部分，主要介绍了为什么要研究本文的一些原因、目的，以及价值，也准备了一些预备知识作为对正文的补充；第二章介绍迭代法与不动点的相关思想原理、定理以及迭代法的收敛条件，是本文的一个主要章节和工作重心，并且举出了几个实例来辅助证明了运用不动点迭代法求解非线性方程的方便以及准确性；第三章作为对第二章节的一个完善，非常具有实用性，主要讨论了非收敛不动点迭代格式的几类处理方法，并通过数值实例给予了证明.1.2 预备知识1.2.1 误差 误差的来源有多个方面，主要有模型误差、观测误差、截断误差、舍入误差等 例1.1 可微函数用泰勒(taylor)多项式 近似代替，则数值方法的截断误差是 在0与之间也就是说，截断误差就是近似值与精确值之间的误差 例1.2 用3.14159近似代替，表示舍入误差. 同样，可以定义舍入误差是指由于计算机字长有限在表示时产生的误差 定义1.11设为准确值，为的一个近似值，称为近似值的绝对误差，简称误差然而，在实际中，人们是无法准确计算出误差的精确值的，一般是根据需要估计出误差的绝对值不超过某正数，也就是误差绝对值的一个上界，叫做近似值的误差限，它总是正数 对于一般情形，即 (1.1)这个不等式有时也表示为 (1.2)误差的大小有时还不能完全表示近似值的好坏，例如，有两个量，则 虽然是的5倍，但是比小得多，这就说明了近似的程度比近似的程度要好得多，因此，除了需要考虑误差的大小之外，还应该考虑准确值本身的大小我们把近似值的误差与准确值的比值 (1.3)称为近似值的相对误差，记作在实际计算中，由于真值总是不知道的，通常取 (1.4)作为的相对误差，条件是较小，此时 (1.5)是的平方项级，故可忽略不计相对误差也可正可负，它的绝对值上界叫做相对误差限，记作，即 (1.6) 根据定义，上例中 与分别为与的相对误差限，很显然近似的程度比近似的程度好得多 在实际运算中，为了避免误差危害，数值计算中通常不采取数值不稳定算法，在设计算法是应该尽量避免误差危害，防止有效数字损失，通常要避免两个相近数字相减和用绝对值很小的数做除数，还要注意运算次序和减少运算次数1.2.2 有限差 定义1.22 分别称 (1.7) (1.8) (1.9) 为函数在点的一阶向前差分，一阶向后差分和一阶中心差分，或者分别简称为一阶前差，一阶后差，一阶中心差，统称为(一阶)有限差，其中表自变量的有限增量，称为步长，和分别成为(一阶)前差算子、(一阶)后差算子和(一阶)中差算子，统称为(一阶)有限差算，仿此，可以定义高阶有限差，例如，二阶前差记作，定义为 (1.10) 于是，有 (1.11) 阶前差记作，定义为 (1.12) 同样，二阶后差和阶后差分别定义为 (1.13)和 (1.14) 二阶中心差 和阶中心差分别定义为 (1.15)和 (1.16)我们规定 , , .有限差有下列一下性质： （1）常数的有限差恒为零 （2）有限差算子为线性算子，即对任意的实数,恒有 (1.17) (1.18) (1.19) （3）用函数值表示高阶有限差： (1.20) (1.21) (1.22) 其中 （4）用有限差表示函数值 (1.23) 第章 非线性方程求解的不动点迭代算法2.1不动点迭代算法的基本思想 首先讨论解非线性方程 (2.1)的问题. 方程(2.1)的解又称为函数的不动点. 为求的不动点，选取一个初始值，令 (2.2) 已产生序列. 这一类迭代法称为不动点迭代. 又被称为迭代函数， 很显然，若迭代序列收敛，即有 (2.3)且连续，则是的一个不动点 例2.12 方程在区间中有唯一跟. 我们可以用不同的方法将它化为方程：（1） （2） （3） （4） （5）等等. 取初始值，分别用式(2.2)的迭代格式计算，结果如下表 表2.1 例2.1迭代公式计算结果 1-2.3750.5590169941.0690449681.1960784312-72.561.3829872001.14163787818230505931.12837105413119556821.13076111919332270691.1303294161262386754199705436612265420691037948141.130395365101.2003529761.130395447111.0654751741.130395432121.1811927851.130395435131.0844308331.130395435291.127222584301.133074649311.128116321321.1323221241091.1303954291101.1303964401191.1303954341201.130395436从表2.1中可以看到，选取迭代函数为，分别12次和4次，得到方程的近似根1.130395435若选取作为迭代函数，则为奇数时迭代子序列单调增加，为偶数时迭代子序列单调减小，迭代120次得到近似根1.130395436 若选取作为迭代函数，则迭代序列不收敛， 若选取为迭代函数，则出现了负数开方，因而无法继续进行迭代2.2 不动点迭代算法的收敛性 通过例2.1，可以总结出，对于同一个非线性方程的求解问题，在转化为迭代方程时应该要使其解的迭代次数达到最小，且得到的解应该最精确. 在选择迭代函数 的基本原则是，首先必须保证不动点迭代序列 在的定义中，以使迭代过程不至于中断；其次要求迭代序列收敛且尽可能收敛得快. 定理2.12 假设为定义在有限区间上的一个函数，它满足以下条件 （1）对任意有 (2.4) （2）的导数在上有界，且存在正数使得对一切有 (2.5)那么对于任意初始值由不动点迭代(2.2)产生的序列都收敛于在的唯一不动点，并且有误差估计式 (2.6) 其中. 证明 首先证明的不动点存在且唯一. 令 (2.7) 据条件(1) 又据条件(2)，在上存在，因此在上连续，从而在上也连续，因此方程在上至少有一个跟现假设方程在上有两个根，则由lagrange中值定理知，在与之间存在使得 再由(2.5) 这就得到矛盾式： 因此，即在中的根是唯一的 其次证明由不动点迭代格式(2.2)产生的序列是收敛于的根据定理条件(1)，因此不动点迭代过程不会中断由(2.5)式有 (2.8) 应用lagrange中值定理，并根据(2.5)式有 (2.9)因为，所以 即 (2.10)最后，推导估计式(2.6)应用收敛性的证明过程，有 (2.11)于是 (2.12)在上式中令，得 (2.13) (2.6)式得证 例2.22 讨论例2.1中不动点迭代 (2.14) 的收敛性. 为使解的近似值的误差不超过，试确定迭代次数解 迭代法(2.14)的迭代函数为 的定义域为取初始值，由不动点迭代(2.21)得，因此取区间由于 因此在上单调减小 而 于是，当时，但 在上单调减小，因此 因此，定理2.1的条件(2)不成立从表2.1看到，取作为初始值， 作为当时，从而又由于 因此定理2.1的条件成立故迭代过程收敛中任意取初值，为使解的近似值的误差不超过，根据误差估计式(2.6) 只要 因此，应取为 取于是迭代138+30=168次必可使近似解的误差不超过 实际上，从表2.1中可以看到，只要迭代110次便可达到所要求解的精度(2.6)式右端是最大可能的误差界 就本例来说，估计的迭代次数偏大了.2.3 不动点迭代算法的收敛速度定理2.22 在定理2.1的假设条件下，再设函数在区间 上 次连续可微，且在方程(2.1)的跟处 (2.15)则不动点迭代为阶收敛. 证明 据定理2.1知，方程（2.1）在上有唯一根且对任意初始值，不动点迭代序列收敛于由于 (2.16)据taylor公式和定理条件有 其中. 易知，对于充分大的，若 ，则 ，从而 (2.17） 故证得不动点迭代为阶收敛 关于不动点的迭代，还有下面的局部收敛定理. 定理2.32 设是方程(2.1)的一个根，在的某领域内次连续可微，且 则当初始值充分接近时（存在正数，对一切），不动点迭代序列都收敛于，且收敛阶数为. 证明 由于假设在的某领域内连续且，因此必存在 使得对一切 有 又据lagrange中值定理，有 在与之间，从而 即 (2.18)因此当时，据定理2.2和定理2.3知，对于任意初始值，不动点迭代收敛，且收敛阶数为2.4 加速不动点迭代算法及其收敛性 一个收敛的迭代过程将产生一个收敛序列，如这样，只要迭代足够多次，即充分大时，如，则可取但若迭代过程收敛缓慢，则会使计算量变得很大，因此需要加速收敛过程 假设一个序列：，线性收敛于(收敛缓慢)，即有 (2.19)于是当足够大时，有 即 亦即 (2.20) 解得 定义 ， (2.21)(2.21)称为aitken加速公式（方法） aitken加速方法得到的序列：较原来的序列更快地收敛于. 有下面的定理 定理2.42 设序列是线性收敛于的，并且对于所有足够大的整数有，则由aitken加速方法(2.21)产生的序列有 (2.22) 证明 由假设序列线性收敛于，即有 ，. 记 (2.23)则有 ， 据(2.21)式， (2.24)因此有 在绪论中有讲到一阶前差： 二阶前差： 于是，aitken加速公式(2.21)可改写成 (2.25)由于这个缘故，aitken加速方法又称为aitken加速方法 例2.32 设，则. 由于 因此序列收敛于1 由序列应用aitken加速方法计算得的开头几项列表如下（表2.2）确实比更快的收敛于1 表 2.2 atiken加速法计算结果的开头几项列n10.540302305 20.877582561 0.96177506030.944956946 0.98212935340.9689124210.98978551250.9800665770.99341565060.986143231 第3章 非收敛不动点迭代格式的几类处理方法与比较 在第2章中主要介绍了求解非线性方程的不动点迭代法，其要求是迭代函数要满足收敛定理假定条件，而在现实生活中，明确满足这些条件的迭代函数是很少见的，本章对于迭代函数不满足收敛条件的情况，提出了几类处理方法.3.1 非收敛不动点迭代格式的几类处理方法 一个方程的迭代格式不是唯一的，且迭代也不都是收敛的，其收敛性取决于迭代函数和初值，关于不动点迭代函数的收敛性，上一章已经进行了讨论， 但假若时，就不满足定理2.1的条件(2)了，于是下面分别介绍了反函数法、牛顿迭代法、steffensen迭代法和松弛法这四中处理方法.3.1.1 反函数法因为，有，则当时，所以方程可写成等价形式，从而构造迭代格式 , (3.1)很明显，满足收敛条件. 对于简单情况, 其反函数容易得到.3.1.2 牛顿迭代法 对于迭代格式的情形，采用newton迭代格式有 (3.2) 3.1.3 steffensen迭代法 根据aitken加速算法，对迭代格式,，进行如下修改： (3.3)其中.3.1.4 松弛法 将化成等价形式 , 称为松弛因子, 从而构造迭代格式 (3.4)其迭代函数为 . 记，得到如下结论: （1）当时，取 时，迭代收敛； （2）当时，取 时，迭代收敛； （3）当时，取 时，迭代格式比迭代格式收敛快推导如下： （1）当 时，由得到，其迭代函数为 因为 所以有，从而迭代收敛. （2）当时, 由得到. 因为 所以有, 从而迭代收敛. （3）当时, 取，由得到, 由得到. 所以有, 从而迭代格式 比迭代格式收敛快.3.2 数值实例 通过以上四种方法都可以解决非收敛不动点迭代格式的问题，现对上述四种给出几个不满足不动点迭代收敛定理的实例，并对结果进行分析和比较. 例3.1 求方程在区间内的根，要求精度为 解 对于方程，将它化为，所以，则当时，不满足定理2.1的条件(2),因此不能由(2.2)的迭代格式计算.下面分别用反函数方法、牛顿（newton）迭代法、steffensen迭代法、松弛法对迭代函数进行修改，得到相应新的迭代函数，并用c语言编程上机计算. (1)反函数法：迭代格式为 即 取初值，运用程序见附录1 (2)牛顿（newton）迭代法：迭代格式为 即 取初值，运用计算程序见附录二； (3) steffensen迭代法：迭代格式为 即 取初值，运用如下程序可以得到结果： (4)松弛法：迭代格式为 即 当时，且，所以的取值范围为，现取，运用c语言编程可得到起结果以上这四种方法的计算结果见表(3.1)，本例中以上四种方法都是收敛的，因此这四种方法均可以解决不满足收敛条件的不动点迭代收敛问题，同时本例中变换后的newton迭代法收敛的最快. 表3.1 例3.1的四种方法的计算结果迭代次数反函数法newton法steffensen迭代法松弛法11.650961.695652.076001.6687521.669221.672082.000131.6720131.671661.671701.921191.6716741.671701.671701.841671.6717051.671701.767381.6717061.6786471.6719781.6717091.67170 例 3.2 求方程在区间内的根，要求精度为. 解 对于方程，将它化为，所以，则当时，因此不满足不动点迭代收敛条件，为求此次方程的解，下面同样分别用本章介绍的四种方法求解此方程. (1)反函数法：迭代格式为 将方程变为迭代格式为 取初值，运行附录5的相应程序即可得计算结果. (2)牛顿（newton）迭代法:迭代格式为 代人例题中的数据 取初值，运行附录6的程序即可的计算结果. (3)steffensen迭代法：迭代格式为 代入例题中的数据有 取初值，运行附录7即可算得计算结果. (4)松弛法：迭代格式为 代入例题中的数据有 当时，所以取值在，现取，初值，运行附录8的程序即可得到计算结果.以上这四种方法的计算结果见表(3.2)，本例中以上四种方法都是收敛的，因此这四种方法均可以解决不满足收敛条件的不动点迭代收敛问题，同时本例中变换后的newton迭代法收敛的最快 表3.2 例3.2的四种迭代结果迭代次数反函数法newton法steffensen迭代法松弛法11.414211.407611.448211.4203121.398801.395331.411521.4031531.395971.395341.397091.3979041.395451.395341.395361.3961951.395361.395341.3956261.395341.395341.3954371.395341.3953781.3953591.39534101.39534 例3.3 求方程在区间内的根，要求精度为.解 将方程化为等价形式，那么此时.当时，因此不满足不动点迭代收敛条件.按下面这四种方法处理可以得到近似解.(1)反函数法：首先由反函数处理方法可得到迭代格式 取初值，运用程序见附录9.(2)牛顿（newton）迭代法：由牛顿迭代法得到迭代格式 取初值，运用程序见附录10.(3)steffensen迭代法：由steffensen迭代法得到迭代格式 取初值，运用程序见附录11. (4)松弛法：由松弛法得到迭代格式为 当时，所以取之间的值，现取，初值，运用程序见附录12. 以上这四种方法的计算结果见表(3.2)，本例中以上四种方法都是收敛的，因此这四种方法均可以解决不满足收敛条件定理的不动点迭代收敛问题，同时本例中变换后的newton迭代法收敛的最快 表3.3 例3.3的四种迭代结果迭代次数反函数法newton法steffensen迭代法松弛法1 0.223140.314440.256300.3405120.328170.300150.298230.3101430.289620.300080.300070.3026740.303940.300080.300080.3007550.298640.300080.3002560.300610.3001270.299880.3000980.300150.3000890.300050.30008100.30009110.30007120.30008130.30008 结 论 非线性代数问