优秀论文~~非线性方程的求解

非线性方程组的求解摘要：非线性方程组求解是数学教学中，数值分析课程的一个重要组成部分，作为一门学科，其研究对象是非线性方程组。

求解非线性方程组主要有两种方法：一种是传统的数学方法，如牛顿法、梯度法、共轭方向法、混沌法、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 为赋值空间。

泰勒公式的应用论文泰勒公式是一个非常重要的数学工具，在物理、工程和其他科学领域都有广泛的应用。

本文将介绍一篇关于泰勒公式应用的论文，通过该论文的介绍，读者可以了解泰勒公式的具体应用以及其在该领域的重要性。

题目：《利用泰勒公式对非线性方程进行求解的数值方法研究》摘要：本文研究了一种利用泰勒公式对非线性方程进行求解的数值方法。

通过将非线性方程展开成泰勒级数的形式，可以近似地求解非线性方程，并得到更加精确的解。

本文通过对该数值方法进行理论推导和实验证明，证明了该方法的有效性和准确性。

引言：非线性方程是很多科学问题中常见的数学模型，然而求解非线性方程通常比线性方程复杂得多。

泰勒公式是一种在求解非线性方程时常用的近似方法。

通过将非线性方程进行泰勒级数展开，可以将非线性方程转化为线性方程或更简单的形式，从而得到近似的解。

方法：本文首先对泰勒公式进行了简要的介绍和推导。

然后，根据泰勒公式的展开形式，将非线性方程的各阶导数代入泰勒级数中，得到更简单的形式。

接下来，研究了如何选取适当的展开点和截断误差来提高近似解的精确性。

最后，利用MATLAB编写了求解非线性方程的数值算法，并通过多个实例进行了验证。

结果与讨论：通过对多个不同类型的非线性方程进行求解，得到了较好的结果。

与传统的数值方法相比，利用泰勒公式进行求解的方法具有更高的精确性和更快的收敛速度。

此外，通过调整展开点和增加泰勒级数的项数，还可以进一步提高解的精确度。

结论：本文研究了一种利用泰勒公式求解非线性方程的数值方法，并通过理论推导和实验证明了该方法的有效性和准确性。

该方法可以准确地求解非线性方程，并且具有更高的精确性和更快的收敛速度。

因此，该方法在实际应用中具有很大的潜力，可以应用于物理、工程和其他科学领域中。

展望：虽然本文对利用泰勒公式求解非线性方程的数值方法进行了研究和验证，但仍然有一些问题需要进一步探讨。

例如，如何选择展开点和确定截断误差的更准确方法，以及将该方法应用于更复杂的非线性方程等。

⾮线性⽅程求解基于MATLAB的⾮线性⽅程的五种解法探讨摘要：本⽂利⽤matlab软件对⾮线性⽅程解法中的⼆分法、简单迭代法、⽜顿法、割线法以及Steffensen法的数值分析⽅法的算法原理及实现⽅法进⾏了探讨。

对f x x x=+-()2ln2的零点问题，分别运⽤以上五种不同的⽅法进⾏数值实验，⽐较⼏种解法的优缺点并进⾏初步分析评价。

关键词：⼆分法、简单迭代法、⽜顿法、割线法、Steffensen法1、引⾔在很多实际问题中，经常需要求⾮线性⽅程f(x) =0的根。

⽅程f(x) =0的根叫做函数f(x)的零点。

由连续函数的特性知：若f(x)在闭区间[a,b ]上连续,且()()0f a f b<.则f(x) =0在开区间(a,b)内⾄少有⼀个实根。

这时称[a,b]为⽅程f(x) =0的根的存在区间。

本⽂主要对⾮线性⽅程的数值解法进⾏分析，并介绍了⾮线性⽅程数值解法的五种⽅法。

并设=+-.f x x x()2ln2f x在[1,2]上的图形，如图1：. 显然，函数在[1,2]之间有⼀个零点。

⾸先画出()2、计算机配置操作系统Windows 7 旗舰版内存2GB处理器AMD 4核 A6-3400M APU 1.4GHz图.13、⼆分法⼆分法的基本思想是将⽅程根的区间平分为两个⼩区间,把有根的⼩区间再平分为两个更⼩的区间,进⼀步考察根在哪个更⼩的区间内。

如此继续下去,直到求出满⾜精度要求的近似值。

设函数()f x 在区间[a,b ]上连续,且f(a)·f(b) <0，则[a,b ]是⽅程f(x) =0的根的存在区间，设其内有⼀实根，记为x*。

取区间[a,b ]的中点()2k a b x +=并计算1()f x ,则必有下列三种情况之⼀成⽴： (1) 1()f x =0，x1就是⽅程的根x*;(2)()f a .1()f x <0,⽅程的根x*位于区间[a, 1x ]之中,此时令111,a a b x ==; (3)1()f x .()f b <0,⽅程的根x*位于区间[1x ,b ]之中,此时令11a x =,1b b =。

非线性方程组研究毕业论文第一章绪论1.1 了解非线性方程组的一般形式如下:f l X i ,X 2,X 3,...,X n =0, ,f n （X i ,X 2,X 3，…，X n ）=0,可以看出f i i = 1,2,3,..., n 是在空间R 的实值函数。

再用向量转换下可以得到：把F 可以看做在R n 区域内展开的非线性映像，表示为F 尸 D R n、 R n1.2下面来介绍简单的边值问题：X = f t,s 0 乞t 辽1 , x 0 二 a, x 1 = ：。

（ 1.2）此时定义f 在D —t,x |0岂21,-：： ：：x ：：：：［上二阶可微连续, 现在求解（1.2）上X 的数值。

(1.1)F X = 0。

我们用差分方法离散化得到：u 1 4 •…h= -------- , t j = J h, j=0,1,2,3 ,、、n+1 ,n +1在得到：'' 1X (t j )=活区斗—2X j +X j J j+1,2，八、n, h在转化矩阵又可以得到：2-10-1 2 ...A =0 ... -1-…-1 2_在从映像转换成：2x =h X j,...X n ,方程（1.2）转化为：Ax+ 「x =0本文将介绍求解非线性方程组的牛顿法，迭代法，牛顿法，这是本人对非线性方程数值求解的认识，我会使用这些方法并为为开展进一步研究。

第二章、求解非线性方程组的牛顿法2.1牛顿法的引入与介绍在学习中关于方程f x =0的求解这种题型接触的太多了， f x 作为线性方程 函数，解法多样也很容易求解值。

我们来比较一下牛顿法，牛顿法简单的来说其实也 是一种线性化方法，他的理念就是把非线性方程 f x 转化成某种类型的线性方程求解x 的值。

非线性方程不过是线性方程的扩展， 非线性方程组就是在此基础上加以延 伸。

F 面我们来介绍了解一下牛顿法的理论:我们看下例题:f l X i ,X 2,X 3,…，X n i=0.也可以用向量把它转化为F x [=0 可以看出n^2时，fj(i=1,...,n )至少有一个变量是在x(i=1,...,n )的非线性函数， 我们这时(2.1)就可以看作非线性方程组，非线性方程组的求解实际上就是n=1求根的应用。

非线性方程求解方法的研究与比较分析非线性方程是数学中一类重要的方程，它们的求解对很多实际问题具有重要的意义。

然而，非线性方程由于其非线性特性，使得其求解更加困难和复杂。

本文旨在研究和比较非线性方程的求解方法，通过对不同求解方法的分析和比较，来评估它们的优缺点和适用范围。

首先，我们介绍一些常用的非线性方程求解方法。

目前常用的求解方法主要包括迭代法、牛顿法、二分法等。

迭代法是一种比较简单的求解非线性方程的方法。

其基本思想是通过不断迭代逼近方程的解。

具体的迭代公式可以选择不同的形式，如固定点迭代法、牛顿迭代法等。

迭代法的优点是简单易懂，但是其收敛速度较慢，而且在某些情况下可能无法收敛到解。

牛顿法是一种较为常用的非线性方程求解方法。

它利用函数的一阶导数和二阶导数信息，通过不断的迭代逼近方程的解。

牛顿法的优点是收敛速度快，但是在某些情况下可能会出现迭代发散的情况。

二分法是一种比较简单但是有效的非线性方程求解方法。

其基本思想是通过不断地缩小解的搜索范围，直到找到满足方程的解。

二分法的优点是简单易懂，而且收敛性和精度较好，但是其收敛速度相对较慢。

在对以上几种方法进行比较分析之前，我们需要明确一些评价指标。

首先是收敛性，即方法是否能够收敛到解。

其次是收敛速度，即方法迭代到解所需的时间。

还有精度，即方法得到的解与真实解之间的误差。

最后是稳定性，即方法对初始值的选择是否敏感。

通过对以上几种方法的比较分析，我们可以得出以下结论：首先，迭代法是一种简单但是不稳定的求解方法。

其收敛性和精度较差，而且对初始值的选择较为敏感。

因此，在实际应用中，迭代法通常只适用于简单的非线性方程求解。

其次，牛顿法是一种较为常用的求解方法。

它具有收敛速度快、精度高的优点，但是在某些情况下可能会出现迭代发散的情况。

此外，牛顿法对函数的一阶导数和二阶导数的计算要求较高，所以在某些情况下可能不适用。

最后，二分法是一种简单而有效的求解方法。

它具有收敛性好、精度高的优点，但是其收敛速度相对较慢。

非线性方程的求解毕业论文题目(中文): 非线性方程的求解(英文): The Solution of Nonlinear Equations目录绪论 ..................................................................... ........................................................... 1 1 非线性方程的简介 ..................................................................... .. (1)1.1非线性方程的背景 ..................................................................... . (1)1.2非线性方程的概念 ..................................................................... ...................... 2 2非线性方程求解的数值方法 ..................................................................... (3)2.1 二分法 ..................................................................... .. (3)2.1.1 二分法的思想 ..................................................................... . (3)2.1.2 二分法的推理 ..................................................................... . (3)2.1.3 二分法的应用 ..................................................................... . (4)2.2 牛顿迭代法 ..................................................................... (4)2.2.1 迭代法 ..................................................................... (4)2.2.2 牛顿迭代法 ..................................................................... . (6)2.3 改进牛顿迭代法 ..................................................................... .. (10)2.3.1 改进牛顿迭代法的背景 ......................................................................102.3.2 改进的法 ..................................................................... ........... 11 Newton3 牛顿迭代法和改进牛顿迭代法的应用 ....................................................................123.1 牛顿迭代法的应用...................................................................... . (12)3.2 改进牛顿迭代法的应用 ..................................................................... ............ 19 4 结束语 ..................................................................... ................................................. 22 参考文献 ..................................................................... ................................................. 23 致谢 ..................................................................... (24)I非线性方程的求解摘要非线性方程在实际问题中经常出现，很多熟悉的线性模型都是在一定的条件下由非线性问题简化得到的;非线性方程在科学与工程计算中的地位越来越重要,因此研究和探讨非线性方程求解的方法是非常有必要的。

长沙学院CHANGSHA UNIVERSITY 本科生毕业论文摘要非线性方程在工程实践、经济学信息安全和动力学等方面的大量实际问题中有着极为广泛的应用，而不动点迭代算法作为数学研究的一个新方向，是求解非线性方程问题的一个最基本而又重要的方法.本文主要介绍了非线性方程求解的不动点算法及其研究，首先，综述了非线性方程求解的不动点算法的研究背景、并阐述了本文的主要工作以及介绍了误差、有限差等基本知识；然后，详细介绍了不动点迭代算法的基本思想、在什么条件下方程存在不动点的收敛定理、不动点的收敛阶定理和Atiken加速公式；最后，考虑到方程可能会不满足不动点迭代收敛定理的两个条件的情况提出了反函数法、牛顿迭代法、Steffensen 迭代法和松弛法这四中处理方法.关键词：非线性方程，不动点原理，迭代法ABSTRACTA 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目录摘要 (I)ABSTRACT (I)第1章绪论 (1)1.1 研究背景 (1)1.2 预备知识 (2)1.2.1 误差 (2)1.2.2 有限差 (3)第２章非线性方程求解的不动点迭代算法 (5)2.1不动点迭代算法的基本思想 (6)2.2 不动点迭代算法的收敛性 (7)2.3 不动点迭代算法的收敛速度 (11)2.4 加速不动点迭代算法及其收敛性 (12)第3章非收敛不动点迭代格式的几类处理方法与比较 (14)3.1 非收敛不动点迭代格式的几类处理方法 (15)3.1.1 反函数法 (15)3.1.2 牛顿迭代法 (15)3.1.3 Steffensen迭代法 (15)3.1.4 松弛法 (16)3.2 数值实例 (17)结论 (21)参考文献 (23)附录 (24)致谢 (35)第1章绪论1.1 研究背景非线性数值解的问题是现代数学的主要研究课题之一，这不仅是由于科学技术发展的需要，而且也是由于计算技术的高速发展提供了解决这类问题的可能，利用计算机解决非线性问题时，最终总是将其化成为有限维非线性问题，或称为非线性代数问题．对于求解非线性方程，无论从理论上还是从计算机上，都比解线性问题要复杂的多，一般的非线性方程是很难求出精确解的，往往只能求出近似解、数值解，而长期以来，人们为了得到满足条件的近似值，许多计算工作者致力于研究求解非线性方程的有效方法，尤其是计算机出现后函数方程求根的数值解法得到了蓬勃发展，十七世纪，微积分出现时，Newton和Halley发明了各自的新的数学工具去解非线性方程，十八世纪，随着微积分的快速蓬勃发展，Euler和Lagrange分别找到了一个无穷级数来表示方程解，并以各自的名字来命名，十九世纪，人们开始注重问题分析的严密性，柯西建立了优级数技巧，该技巧不断的被以后的事实证明对于研究方程近似解序列的收敛性是很有成效的，在分析严密性发展的时代，Ostrowski对Newton迭代法的收敛性问题规定了一个合理的假设和一个令人满意的解法，在软件分析完善的年代，Kantorovich把Newton迭代法和Ostrowski的结果推广到Banach空间，从而使许多用硬分析去做非常棘手的有关问题被轻轻松松地推论中得到了令人满意的解决，等等，总之，这些方法不断地被后人完善，但在目前，实际问题中可能还需要求方程的负根，求非线性方程（组）的迭代法，求微分方程迭代法等等，迭代方法还需要更深入的研究，同时意味着迭代法的发展空间将会更广阔．本文将着重介绍求解非线性方程的不动点算法，其中文献[3]是由王则柯先生于1988年总结的单纯不动点算法，他简述了不动点在非线性方程数值解、微分方程初值问题、边值问题、分支问题等许多应用问题方面的十多年的发展，以及对单值连续映射的不动点或零点问题进行了讨论，在文献[4]中，许炎先生简单的阐述了国内外有关不动点理论的发展状况，并主要讨论了L-Lipschitz映射的不动点迭代逼近定理，[3][4]这两篇文献都总结出了不动点问题的研究和解决在实际问题中起到了至关重要的作用，这一系列的文献还有[5][6][7][8]，而秦小龙先生在文献[9]中介绍了迭代法的发展情况以及相关定理，为本篇论文提供了大量的基础信息，王公俊先生在文献[10]中分别介绍了常用的求解非线性方程的方法以及收敛性，在文献[11]中，张卷美主要研究了一类不动点迭代法的求解，在迭代格式不满足迭代条件的情况下，运用的几种处理方法，并且用Ｃ语言编程上机进行了计算，对迭代收敛结果进行了分析和比较，为本文提供了大量的信息，另外，本文还借鉴了2本不同出版社的《数值分析》教材的大量内容．本文主要介绍了非线性方程求解的不动点算法及其应用，第一章为绪论部分，主要介绍了为什么要研究本文的一些原因、目的，以及价值，也准备了一些预备知识作为对正文的补充；第二章介绍迭代法与不动点的相关思想原理、定理以及迭代法的收敛条件，是本文的一个主要章节和工作重心，并且举出了几个实例来辅助证明了运用不动点迭代法求解非线性方程的方便以及准确性；第三章作为对第二章节的一个完善，非常具有实用性，主要讨论了非收敛不动点迭代格式的几类处理方法，并通过数值实例给予了证明.1.2 预备知识1.2.1 误差误差的来源有多个方面，主要有模型误差、观测误差、截断误差、舍入误差等．例1.1 可微函数)(x f 用泰勒(Taylor)多项式 ,!)0(...!2)0(!1)0()0()()(2n n n x n f x f x f f x p +''+'+= 近似代替，则数值方法的截断误差是 ,)!1()()()()(1)1(+++=-=n n n n x n f x p x f x R ξ ξ在0与x 之间．也就是说，截断误差就是近似值与精确值之间的误差．例1.2 用3.14159近似代替π，表示舍入误差..0000026.014159.3⋅⋅⋅=-=πR同样，可以定义舍入误差是指由于计算机字长有限在表示时产生的误差．定义1.1[1] 设x 为准确值，*x 为x 的一个近似值，称x x e -=**为近似值的绝对误差，简称误差．然而，在实际中，人们是无法准确计算出误差*e 的精确值的，一般是根据需要估计出误差的绝对值不超过某正数*ε，也就是误差绝对值的一个上界，*ε叫做近似值的误差限，它总是正数．对于一般情形，**||ε≤-x x ，即,****εε+≤≤-x x x (1.1)这个不等式有时也表示为.**ε±=x x (1.2)误差的大小有时还不能完全表示近似值的好坏，例如，有两个量110±=x ，51000±=y ，则.5,1000;1,10****====y x y x εε虽然*y ε是*x ε的5倍，但是%5.0**=y y ε比%10**=xx ε小得多，这就说明了*y 近似y 的程度比*x 近似x 的程度要好得多，因此，除了需要考虑误差的大小之外，还应该考虑准确值本身的大小．我们把近似值的误差*e 与准确值x 的比值 ,**xx x x e -= (1.3) 称为近似值*x 的相对误差，记作*r e ．在实际计算中，由于真值x 总是不知道的，通常取 ,*****xx x x e e r -== (1.4) 作为*x 的相对误差，条件是***xe e r =较小，此时 ,)(1)()()()(**2*****2*******x e x e e x x e x x x x e x e x e -=-=-=- (1.5) 是*r e 的平方项级，故可忽略不计．相对误差也可正可负，它的绝对值上界叫做相对误差限，记作*r ε，即 .||***x r εε= (1.6) 根据定义，上例中 %10||**=x x ε与%5.0||**=y y ε分别为x 与y 的相对误差限，很显然*y 近似y 的程度比*x 近似x 的程度好得多．在实际运算中，为了避免误差危害，数值计算中通常不采取数值不稳定算法，在设计算法是应该尽量避免误差危害，防止有效数字损失，通常要避免两个相近数字相减和用绝对值很小的数做除数，还要注意运算次序和减少运算次数．1.2.2 有限差定义1.2[2] 分别称),()()(x f h x f x f -+=∆ (1.7) ),()()(h x f x f x f --=∇ (1.8) ⎪⎭⎫ ⎝⎛--⎪⎭⎫ ⎝⎛+=22)(h x f h x f x f δ (1.9)为函数)(x f 在点x 的一阶向前差分，一阶向后差分和一阶中心差分，或者分别简称为一阶前差，一阶后差，一阶中心差，统称为(一阶)有限差，其中)0(>h 表自变量的有限增量，称为步长，∇∆,和δ分别成为(一阶)前差算子、(一阶)后差算子和(一阶)中差算子，统称为(一阶)有限差算，仿此，可以定义高阶有限差，例如，二阶前差记作)(2x f ∆，定义为[]).()()()(2x f h x f x f x f ∆-+∆=∆∆=∆ (1.10) 于是，有).()(2)2()(2x f h x f h x f x f ++-+=∆ (1.11) n 阶前差记作)(x f n ∆，定义为[]).()()()(111x f h x f x f x f n n n n ---∆-+∆=∆∆=∆ (1.12) 同样，二阶后差)(2x f ∇和n 阶后差)(x f n ∇分别定义为[])()()()(2h x f x f x f x f -∇-∇=∇∇=∇ (1.13)和[]).()()()(111h x f x f x f x f n n n n -∇-∇=∇∇=∇--- (1.14) 二阶中心差 )(2x f δ 和n 阶中心差)(x f n δ分别定义为[],22)()(2⎪⎭⎫⎝⎛--⎪⎭⎫ ⎝⎛+==h x f h x f x f x f δδδδδ (1.15)和[].22)()(111⎪⎭⎫⎝⎛--⎪⎭⎫⎝⎛+==---h x f h x f x f x f n n n n δδδδδ (1.16)我们规定0()()f x f x ∆=, 0()()f x f x ∇=, 0()()f x f x δ=.有限差有下列一下性质：（1）常数的有限差恒为零．（2）有限差算子为线性算子，即对任意的实数α,β恒有()),()()()(x g x f x g x f ∆+∆=+∆βαβα (1.17) ()),()()()(x g x f x g x f ∇+∇=+∇βαβα (1.18)()).()()()(x g x f x g x f βδαδβαδ+=+ (1.19)（3）用函数值表示高阶有限差：()),)((1)(0h i n x f C x f ni in i n -+-=∆∑= (1.20)()),(1)(0ih x f C x f n i in i n --=∇∑= (1.21)()),)2((1)(0h i hx f C x f n i i n i n -+-=∑=δ (1.22)其中 .!)1()1(i i n n n C i n +-⋅⋅⋅-= （4）用有限差表示函数值 .)()(0∑=∆=+n i i i nx f C nh x f (1.23)第２章 非线性方程求解的不动点迭代算法2.1不动点迭代算法的基本思想首先讨论解非线性方程)(x g x = (2.1) 的问题. 方程(2.1)的解又称为函数g 的不动点. 为求g 的不动点，选取一个初始值0x ，令⋅⋅⋅==-,2,1),(1k x g x k k (2.2) 已产生序列}{k x . 这一类迭代法称为不动点迭代. )(x g 又被称为迭代函数， 很显然，若迭代序列}{k x 收敛，即有,lim p x k k =∞→ (2.3) 且)(x g 连续，则p 是g 的一个不动点．例2.1[2] 方程042)(23=-+=x x x f 在区间[]2,1中有唯一跟. 我们可以用不同的方法将它化为方程：（1）;42)(231+--==x x x x g x（2）;22)(212⎥⎦⎤⎢⎣⎡⎪⎭⎫ ⎝⎛-==x x x g x （3）;22)(2133⎪⎪⎭⎫ ⎝⎛-==x x g x （4）;212)(214⎪⎭⎫ ⎝⎛+==x x g x （5）,4342)(2235xx x x x x g x +-+-== 等等.取初始值5.10=x ，分别用式(2.2)的迭代格式计算，结果如下表．表2.1 例2.1迭代公式计算结果从表2.1中可以看到，选取迭代函数为)(4x g ，)(5x g ，分别12次和4次，得到方程的近似根1.130395435．若选取)(3x g 作为迭代函数，则k 为奇数时迭代子序列单调增加，k 为偶数时迭代子序列单调减小，迭代120次得到近似根1.130395436． 若选取)(1x g 作为迭代函数，则迭代序列不收敛， 若选取)(2x g 为迭代函数，则出现了负数开方，因而无法继续进行迭代．2.2 不动点迭代算法的收敛性通过例2.1，可以总结出，对于同一个非线性方程的求解问题，在转化为迭代方程时应该要使其解的迭代次数达到最小，且得到的解应该最精确. 在选择迭代函数)(x g 的基本原则是，首先必须保证不动点迭代序列⋅⋅⋅⋅⋅⋅,,,21k x x x 在)(x g 的定义中，以使迭代过程不至于中断；其次要求迭代序列}{k x 收敛且尽可能收敛得快.定理2.1[2] 假设)(x g 为定义在有限区间[]b a ,上的一个函数，它满足以下条件 （1）对任意[]b a x ,∈有[];,)(b a x g ∈ (2.4) （2）)(x g 的导数)(x g '在[]b a ,上有界，且存在正数1<L 使得对一切[]b a x ,∈有 ,1|)(|<≤'L x g (2.5) 那么对于任意初始值[]b a x ,0∈由不动点迭代(2.2)产生的序列都收敛于g 在[]b a ,的唯一不动点p ，并且有误差估计式|,|1||01x x LL e kk --≤,1≥k (2.6) 其中p x e k k -=.证明 首先证明g 的不动点存在且唯一. 令 ).()(x g x x h -= (2.7)据条件(1),0)()(≤-=a g a a h .0)()(≥-=b g b b h又据条件(2)，在)(x g '上存在，因此)(x g 在[]b a ,上连续，从而)(x h 在[]b a ,上也连续，因此方程0)(=x h 在[]b a ,上至少有一个跟．现假设方程0)(=x h 在[]b a ,上有两个根q p q p ≠,,，则由Lagrange 中值定理知，在p 与q 之间存在ξ使得|,||)(||))((||)()(|||q p g q p g q g p g q p -'=-'=-=-ξξ 再由(2.5).|||||||)(|q p q p L q p g -<-≤-'ξ这就得到矛盾式：.||||q p q p -<- 因此q p =，即0)(=x h 在[]b a ,中的根是唯一的．其次证明由不动点迭代格式(2.2)产生的序列}{k x 是收敛于p 的．根据定理条件(1)[]b a x k ,∈，⋅⋅⋅=,2,1,0k ，因此不动点迭代过程不会中断．由(2.5)式有).()(1p g x g p x k k -=-- (2.8) 应用Lagrange 中值定理，并根据(2.5)式有|||||)(||)()(|||111p x L p x g p g x g p x k k k k -≤-'=-=----ξ.||0p x L k -≤⋅⋅⋅≤ (2.9) 因为10<<L ，所以,0||lim ||lim 0=-≤-∞→∞→p x L p x k k k k即.lim p x k k =∞→ (2.10)最后，推导估计式(2.6)．应用收敛性的证明过程，有|||)()(|||111-++-+++++-≤-=-j k j k j k j k j k j k x x L x g x g x x|,|01x x L j k -≤⋅⋅⋅≤+ (2.11) 于是()∑∑-=+++-=++++-≤-=-11101||m j j k j k m j j k j k k m k x x x xx x||1)1(||010110x x LL L x x Lm k m j jk ---=-≤∑-=+.||101x x LL k--≤ (2.12)在上式中令∞→m ，得.1||||01x x L L p x e kk k --≤-= (2.13) (2.6)式得证．例2.2[2] 讨论例2.1中不动点迭代⋅⋅⋅=⎪⎪⎭⎫ ⎝⎛-==--,2,1,22)(213113k xx g x k k k (2.14) 的收敛性. 为使解的近似值的误差不超过810-，试确定迭代次数．解 迭代法(2.14)的迭代函数为.22)(2133⎪⎪⎭⎫⎝⎛-=x x g )(3x g 的定义域为]4,(3-∞．取初始值5.10=x ，由不动点迭代(2.21)得559016994.01=x ，因此取区间[][]5.1,5.0,=b a ．由于,02243)(22133<⎪⎪⎭⎫ ⎝⎛--='-x xx g [],5.1,5.0∈x 因此)(3x g 在[]5.1,5.0上单调减小． 而[],559.0)5.1()(min 335.1,5.0≈=∈g x g x[],399.1)5.0()(max 335.1,5.0≈=∈g x g x于是，当[]5.1,5.0∈x 时，[]5.1,5.0)(3∈x g ，但,04432243)(232333<⎪⎭⎫⎝⎛+-⎪⎪⎭⎫ ⎝⎛--=''-x x x xx g [],5.1,5.0∈x )(3x g '在[]5.1,5.0上单调减小，因此 [][]{}3330.5,1.50.5,1.5max |()|max |(0.5)|,|(1.5)|x x g x g g ∈∈'''=.019.3)5.1(3≈'=g 因此，定理2.1的条件(2)不成立．从表2.1看到，取133074649.130=x 作为初始值0x ，128116321.131=x 作为1x ．当[]3031,x x x ∈时，[]303132,31,x x x x ∈从而[]30313,)(x x x g ∈．又由于[]313033,|()|max |()|x x x g x g x ∈''≤{}331330max |()|,|()|g x g x ''= ,1853541077.0)(303<=≈'=L x g因此定理2.1的条件成立．故迭代过程收敛[]3031,x x 中任意取初值，为使解p 的近似值k x 的误差不超过810-，根据误差估计式(2.6)|,|1||01x x L L p x kk --≤- 只要.10||1801-<--x x L L k因此，k 应取为810||lg10lg1lg x x L k L ---->853541077.0lg 146458923.0128116321.1133074649.1lg 8⎪⎭⎫⎝⎛---≈.69977.137≈取138=k ．于是迭代138+30=168次必可使近似解的误差不超过810-． 实际上，从表2.1中可以看到，只要迭代110次便可达到所要求解的精度．(2.6)式右端是最大可能的误差界． 就本例来说，估计的迭代次数偏大了.2.3 不动点迭代算法的收敛速度定理2.2[2] 在定理2.1的假设条件下，再设函数)(x g 在区间[]b a , 上)2(≥m 次连续可微，且在方程(2.1)的跟p 处,0)()(=p g j ,1,,1-⋅⋅⋅=m j ,0)()(≠p g m (2.15) 则不动点迭代为m 阶收敛.证明 据定理2.1知，方程（2.1）在[]b a ,上有唯一根p ．且对任意初始值[]b a x ,0∈，不动点迭代序列{}k x 收敛于p 由于),()()()(11p g e p g p g x g p x e k k k k -+=-=-=++ (2.16) 据Taylor 公式和定理条件有()mkk k m m k m k k k e e p g m e p g m e p g e p g e )(!1)()!1(1)(!21)()(1121θ++-+⋅⋅⋅+''+'=--+ ,)(!1)(mk k k m e e p g m θ+=其中10<<k θ. 易知，对于充分大的k ，若 01≠-k e ，则 ),1,(0⋅⋅⋅+=≠k k i e k ，从而()).(!1lim 1p g m e e m m k k k =+∞→ (2.17）故证得不动点迭代为m 阶收敛．关于不动点的迭代，还有下面的局部收敛定理.定理2.3[2] 设p 是方程(2.1)的一个根，)(x g 在p 的某领域内m 次连续可微，且 ,0)()(=p g j ,1,,1-⋅⋅⋅=m j ,0)()(≠p g m ),2(≥m则当初始值0x 充分接近p 时（存在正数r ，对一切[]r p r p x +-∈,0），不动点迭代序列{}k x 都收敛于p ，且收敛阶数为m .证明 由于假设()x g '在p 的某领域内连续且()0='p g ，因此必存在0>r 使得对一切[]r p r p x +-∈, 有.1|)(|<≤'L x g 又据Lagrange 中值定理，有),)(()()(p x g p g x g -'=-ξ ξ在x 与p 之间，从而,|||||)(||)()(|r p x p x g p g x g ≤-<-'=-ξ 即.|)()(|r p g x g <- (2.18) 因此当[]r p r p x +-∈,时，[]r p r p x g +-∈,)(．据定理2.2和定理2.3知，对于任意初始值[]r p r p x +-∈,0，不动点迭代收敛，且收敛阶数为m ．2.4 加速不动点迭代算法及其收敛性一个收敛的迭代过程将产生一个收敛序列⋅⋅⋅⋅⋅⋅,,,,21n x x x ，如p x n n =∞→lim ．这样，只要迭代足够多次，即n 充分大时，如m n =，则可取m x p ≈．但若迭代过程收敛缓慢，则会使计算量变得很大，因此需要加速收敛过程．假设一个序列{}n x ：⋅⋅⋅⋅⋅⋅,,,,21n x x x ，线性收敛于p (收敛缓慢)，即有λ=--+∞→p x px n n n 1lim ().0≠λ (2.19) 于是当n 足够大时，有,121px px p x p x n n n n --≈---++ 即),)(()()221p x p x p x n n n --≈-++亦即.)(22222121p p x x x x p p x x n n n n n n ++-≈+-++++ (2.20) 解得nn n n n n x x x x x x p +--=++++12212222221121222n n n n n n n n n n n nx x x x x x x x x x x x ++++++-+--=-+.2)(1221nn n n n n x x x x x x +---=+++ 定义⋅⋅⋅=+---=++++,2,1,0,2)(~12211n x x x x x x x nn n n n n n ， (2.21)(2.21)称为Aitken 加速公式（方法）．Aitken 加速方法得到的序列{}n x ~：⋅⋅⋅⋅⋅⋅,~,,~,~21n x x x 较原来的序列{}n x 更快地收敛于p . 有下面的定理．定理 2.4[2] 设序列}{n x 是线性收敛于p 的，并且对于所有足够大的整数n 有0))((1≠--+n n x p x ，则由Aitken 加速方法(2.21)产生的序列{}n x ~有.0~lim 1=--+∞→p x px n n n (2.22) 证明 由假设序列}{n x 线性收敛于p ，即有,lim 1λ=--+∞→p x px nn n ，0≠λ.记,1λ---=+px px q n n n (2.23) 则有 0lim =∞→n n q ，0lim 1=+∞→n n q ． 据(2.21)式，()⎥⎦⎤⎢⎣⎡-+----=--++++p x x x x x x p x p x p x nn n n n n n n n 1221121~2121()1()(2)n n n n n n x x x p x x x +++-=---+21221212111[()]()1()[2()]111..21n n n n n n n n n n n n n n n x p x p x p x p x p x p x p x p x p x p x p x p x p x p x p ++++++++----=-----+-⎡⎤-=--⎢⎥-⎡⎤---⎣⎦-+⎢⎥---⎣⎦ .1)(2))((1)1(112++-++⋅-+-=+λλλλn n n n q q q q (2.24)因此有.012)1(1~lim 221=+---=--+∞→λλλp x p x nn n在绪论中有讲到一阶前差：,1n n n x x x -=∆+ ⋅⋅⋅=,2,1,0n 二阶前差：,2)(122n n n n x x x x x +-=∆∆=∆++ .,2,1,0⋅⋅⋅=n 于是，Aitken 加速公式(2.21)可改写成,)(~221n n n n x x x x ∆∆-=+ .,2,1,0⋅⋅⋅=n (2.25)由于这个缘故，Aitken 加速方法又称为Aitken 2∆加速方法．例2.3[2] 设nx n 1cos =，则1lim =∞→n n x . 由于,111cos 111cos lim 11lim 1=--+=--∞→+∞→nn x x n n n n 因此序列{}nx 收敛于1． 由序列{}nx 应用Aitken 加速方法计算得{}nx ~的开头几项列表如下（表2.2）．{}n x ~确实比{}n x 更快的收敛于1．第3章 非收敛不动点迭代格式的几类处理方法与比较在第2章中主要介绍了求解非线性方程的不动点迭代法，其要求是迭代函数要满足收敛定理假定条件，而在现实生活中，明确满足这些条件的迭代函数是很少见的，本章对于迭代函数不满足收敛条件的情况，提出了几类处理方法.3.1 非收敛不动点迭代格式的几类处理方法一个方程的迭代格式不是唯一的，且迭代也不都是收敛的，其收敛性取决于迭代函数)(x g 和初值0x ，关于不动点迭代函数的收敛性，上一章已经进行了讨论， 但假若[]b a x ,∈时，1)(>≥'L x g ，就不满足定理2.1的条件(2)了，于是下面分别介绍了反函数法、牛顿迭代法、Steffensen 迭代法和松弛法这四中处理方法.3.1.1 反函数法因为)(x g x =，有[])(1)(1x g x g '='-，则当[]b a x ,∈时，[]11)(1<≤'-Lx g ，所以方程)(x g x =可写成等价形式)(1x g x -=，从而构造迭代格式)(11k k x g x -+=, ),1,0(⋅⋅⋅=k (3.1) 很明显，)(11k k x g x -+=满足收敛条件.对于)(x g 简单情况, 其反函数)(1x g -容易得到.3.1.2 牛顿迭代法对于迭代格式)(x g x =的情形，采用Newton 迭代格式有 ,)(1)()()(1)(1k k k k k k k k k x g x g x x g x g x g x x x '-'-='---=+ ),1,0(⋅⋅⋅=k (3.2)3.1.3 Steffensen 迭代法根据Aitken 加速算法，对迭代格式)(1k k x g x =+,),1,0(⋅⋅⋅=k ，进行如下修改：),(k k x g y = ),(k k y g z =[]kk k k k k k k k k k k k x x g x g g x g x g g x g g x y z y z z x +---=+---=+)(2))(()())(())((2)(221 (3.3)其中⋅⋅⋅=,1,0k .3.1.4 松弛法将)(x g x =化成等价形式)()1(x wg x w x +-= , 称w 为松弛因子, 从而构造迭代格式),()1(1k k k x wg x w x +-=+ (3.4)其迭代函数为)()1()(x wg x w x g +-= . 记)(min minx g g bx a '='≤≤，)(max max x g g bx a '='≤≤，得到如下结论:（1）当1)(>≥'L x g 时，w 取01)(2max <<-'-w x g 时，)()1(1k k k x wg x w x +-=+迭代收敛；（2）当1)(-<-≤'L x g 时，w 取)(120minx g w '-<< 时，)()1(1k k k x wg x w x +-=+迭代收敛；（3）当1)(<≤'L x g 时，w 取)(1)(11minminx g x g w '-'+<< 时，迭代格式)()1(1k k k x wg x w x +-=+比迭代格式)(1k k x g x =+收敛快． 推导如下：（1）当1)(>≥'L x g 时，由01)(2max<<-'-w x g 得到2)(max->-'w x g w ，其迭代函数为)()1()(x wg x w x f +-=． 因为()()()()()()()max1111111f x w wg x w wg x f x w wg x w g x '''=-+≥-+>-'''=-+=+-<所以有1)(<'x g ，从而)()1(1k k k x wg x w x +-=+迭代收敛.（2）当1)(-<-≤'L x g 时, 由)(120min x g w '-<<得到2)(min->'+-x g w w . 因为()()()()()()()min111,1111f x w wg x w wg x f x w wg x w g x '''=-+≥-+>-'''=-+=+-<所以有1)(<'x f , 从而)()1(1k k k x wg x w x +-=+迭代收敛.（3）当1)(<≤'L x g 时, w 取)(1)(11min minx g x g w '-'+<<，由1>w 得到[]0)(1)1(<'--x g w ,()()()()()1(1)1f x w wg x w g x g x g x '''''=-+=--+<⎡⎤⎣⎦ 由)(1)(1minminx g x g w '-'+<得到0)()(1min min>'+-'+x g w w x g .()()min()11f x w wg x w wg x '''=-+≥-+()()()()minmin 1w wg x g x g x g x ''''≥-++->-所以有)()(x g x f '<', 从而迭代格式)()1(1k k k x wg x w x +-=+ 比迭代格式)(1k k x g x =+收敛快.3.2 数值实例通过以上四种方法都可以解决非收敛不动点迭代格式的问题，现对上述四种给出几个不满足不动点迭代收敛定理的实例，并对结果进行分析和比较. 例3.1 求方程033=--x x 在区间[]2,1内的根，要求精度为510-．解 对于方程033=--x x ，将它化为33-=x x ，所以3)(3-=x x g ，则当[]2,1∈x 时，13)(2>='x x g ，不满足定理2.1的条件(2),因此不能由(2.2)的迭代格式计算.下面分别用反函数方法、牛顿（Newton ）迭代法、Steffensen 迭代法、松弛法对迭代函数进行修改，得到相应新的迭代函数，并用C 语言编程上机计算. (1)反函数法：迭代格式为),(11k k x g x -+= 即.)3(311+=+k k x x 取初值5.10=x ，运用程序见附录1．(2)牛顿（Newton ）迭代法：迭代格式为,)(1)()()(1)(1k k k k k k k k x g x g x x g x g x g x x x '-'-='---=+即.133231)3(23231-+=----=+k k k k k k k x x x x x x x 取初值5.10=x ，运用计算程序见附录二； (3) Steffensen 迭代法：迭代格式为),(k k x g y = ),(k k y g z = [][].)(2))(()())(())((2221kk k k k k kk k k k k k x x g x g g x g x g g x g g x y z y z z x +---=+---=+即,33-=k k x y,3)3(33--=k k x z[].)3(23)3()3(3)3(3)3(3332333331kk k k kk k x x x x xx x +-----------=+ 取初值5.10=x ，运用如下程序可以得到结果： (4)松弛法：迭代格式为),()1(1k k k x wg x w x +-=+ 即),3()1(31-+-=+k k k x w x w x当[]2,1∈x 时，13)(2>='x x g ，且3)(min='x g ，12)(max ='x g ，所以w 的取值范围为01122>>--w ，现取5.10=x ，15.0-=w ，运用C 语言编程可得到起结果． 以上这四种方法的计算结果见表(3.1)，本例中以上四种方法都是收敛的，因此这四种方法均可以解决不满足收敛条件的不动点迭代收敛问题，同时本例中变换后的Newton 迭代法收敛的最快.例 3.2 求方程0124=--x x 在区间[]2,1内的根，要求精度为510-.解 对于方程0124=--x x ，将它化为21214-=x x ，所以2121)(4-=x x g ，则当[]2,1∈x 时，14)(3>='x x g ，因此不满足不动点迭代收敛条件，为求此次方程的解，下面同样分别用本章介绍的四种方法求解此方程. (1)反函数法：迭代格式为),(11k k x g x -+= 将方程变为迭代格式为().12411+=+k k x x取初值5.10=x ，运行附录5的相应程序即可得计算结果. (2)牛顿（Newton ）迭代法:迭代格式为,)(1)()()(1)(1k k k k k k k k x g x g x x g x g x g x x x '-'-='---=+代人例题中的数据.12212321212134341-+=-⎪⎭⎫ ⎝⎛---=+k k k k k k k x x x x x x x 取初值5.10=x ，运行附录6的程序即可的计算结果. (3)Steffensen 迭代法：迭代格式为),(k k x g y =),(k k y g z = [][].)(2))(()())(())((2221kk k k k k kk k k k k k x x g x g g x g x g g x g g x y z y z z x +---=+---=+代入例题中的数据有,21214-=k k x y ,2121212144-⎪⎭⎫ ⎝⎛-=k k x z.2121221212121212121212121212121214442444441k k k k k k k x x x x x x x +⎪⎭⎫⎝⎛---⎪⎭⎫ ⎝⎛-⎥⎥⎦⎤⎢⎢⎣⎡⎪⎭⎫ ⎝⎛---⎪⎭⎫ ⎝⎛---⎪⎭⎫ ⎝⎛-=+ 取初值5.10=x ，运行附录7即可算得计算结果. (4)松弛法：迭代格式为),()1(1k k k x wg x w x +-=+ 代入例题中的数据有.2121)1(41⎪⎭⎫ ⎝⎛-+-=+x w x w x k k当[]2,1∈x 时，14)(3>='x x g ，13224)(3max>=⨯='x g ，所以w 取值在01322<<--w ，现取05.0-=w ，初值5.10=x ，运行附录8的程序即可得到计算结果.以上这四种方法的计算结果见表(3.2)，本例中以上四种方法都是收敛的，因此这四种方法均可以解决不满足收敛条件的不动点迭代收敛问题，同时本例中变换后的Newton 迭代法收敛的最快．例3.3 求方程032=-+x e x 在区间[]1,0内的根，要求精度为510-.解 将方程化为等价形式x e x 23-=，那么此时x e x g 23)(-=.当[]1,0∈x 时，12)(>-='x e x g ，因此不满足不动点迭代收敛条件.按下面这四种方法处理可以得到近似解.(1)反函数法：首先由反函数处理方法可得到迭代格式,223ln 1⎪⎭⎫⎝⎛-=+k k x x取初值5.00=x ，运用程序见附录9.(2)牛顿（Newton ）迭代法：由牛顿迭代法得到迭代格式,21321kk x x k k k e e x x x +-+-=+ 取初值5.00=x ，运用程序见附录10.(3)Steffensen 迭代法：由Steffensen 迭代法得到迭代格式,23k x k e y -= ,2322⎪⎭⎫ ⎝⎛--=k x e k e z()()[](),)23(223232323223231kx e e e k x e e e e x kkx kx kx +------=---+ 取初值5.00=x ，运用程序见附录11. (4)松弛法：由松弛法得到迭代格式为(),23)1(1x k k e w x w x -+-=+当[]1,0∈x 时，122)(-<-≤-='x e x g ，e x g 2)(min-='，所以w 取ew 2120+<<之间的值，现取2.0=w ，初值5.00=x ，运用程序见附录12.以上这四种方法的计算结果见表(3.2)，本例中以上四种方法都是收敛的，因此这四种方法均可以解决不满足收敛条件定理的不动点迭代收敛问题，同时本例中变换后的Newton 迭代法收敛的最快．结 论非线性代数问题的解法是现代计算数学的一个重要研究课题，而不动点迭代算法是求解非线性方程近似根的一个重要方法.本文通过搜集大量资料了解了非线性方程求解的不动点迭代算法的的研究背景，以及研究价值，然后通过介绍不动点迭代法的基本思想，对不动点迭代法的收敛性、收敛速度以及加速不动点迭代算法的收敛性进行了研究，并结合实例经行了比较分析，对于不满足收敛条件的情况，本文通过翻阅大量资料和文献，归纳总结出了四种处理方法，分别为反函数法、牛顿（Newton)迭代法、Steffensen 迭代法、松弛法，使得不满足收敛不动点迭代格式的非线性方程的求解得到了解决，同样也给出了相关实例进行了比较和验证.具体来说，对于一般的非线性方程，只要满足第2章定理2.1中的条件(1)和条件(2)，那么对于任意的初始值[]b a x ,0∈，则由不动点迭代⋅⋅⋅==-,2,1),(1k x g x k k 产生的迭代序列都收敛于g 在[]b a ,的唯一不动点p ，那么要考虑的是光是收敛还不能很好的解决一个迭代效率问题，于是本文还致力研究了不动点迭代法的收敛速度，以及加速不动点迭代法.而对于一般不满足第2章定理2.1中的条件（1）或者条件（2）的情况，那么有不动点迭代算法产生的迭代序列不是收敛的，就不能求出函数的近似解，那么本文通过阅读大量的资料以及文献，总结出了四种比较好用的处理方法，并且通过3个实例，可以发现这几种方法不仅能得到收敛的迭代序列，而且收敛的速度也比较快，通过分析比较这四种方法，牛顿迭代法的迭代效果最好.这也是本文的亮点所在.由于诸多条件限制，本文也有很多不足之处，比如说没有足够多的实例来充分的证明第2章的定理2.2与定理2.3，并且对于第3章给出的3个实例中的精度要求较低，有待于继续研究，若有条件，可以更深层次的研究非线性方程组的不动点算法及其应用.参考文献[1] 李庆扬，王能超，易大义.数值分析[M].北京：清华大学出版社，2008,32(2)：3-8[2] 林成森.数值分析[M].北京：科学出版社，2007,18(1):133-135,255-265[3] 王则柯．单纯不动点算法[J]．广州：中山大学数学系，1988,12(12)：113-127[4] 许炎．Banach空间中的不动点迭代逼近[J]．苏州：苏州科技学院数理学院，2010，13(2)：1-44[5] 李素红．非线性算子的不动点迭代逼近[J]．天津工业大学学报，2006，16(1)：51-58[6] 孙俊萍，徐裕生．非线性算子的不动点定理[J]．长春大学学报，2000，10(5)：30-31[7] 宋娜娜．几类非线性算子的不动点定理[J]．长春工程学院学报（自然科学版），2003,4(3)：1-4[8] 段华贵．几类非线性算子的不动点定理及应用[J]．哈尔滨师范大学自然科学学报，2004，20(4)：31-33[9] 秦小龙．非线性算子方程的迭代算法[J]．科学技术与工程研究简报，2010，10(13)：3169-3170[10] 王公俊．非线性方程的迭代法研究[J]．河北大学学报（自然科学版），2000，20(3)：228-231[11] 张卷美．一类不动点迭代法的求解[J]．燕山大学学报，1998，22(2)：140-142[12] 高尚.不动点迭代法的一点注记[J]．大学数学．2003,19(4):30-37[13] 代璐璐．非线性方程组的迭代解法[J]．合肥工业大学学报，2012，5(4):1-57[14] Halikias, Galanis, Karcanias, Milonidis.Nearest common root of polynomials,approximate greatest common divisor and the structured singular value[J].IMA Journal of Mathematical Control & Information,2013，30(4)：423-442附录附录1（反函数处理法）：%main()为主函数%用途：用反函数法求解非线性方程在非收敛不动点迭代格式情况下的解%格式：solut (double x,int k),solut为被调用函数，x为返回输出的值，即为迭代函数产生的迭代序列，k为在一定精度下的迭代次数#include <stdio.h>#include <math.h>double solut (double x,int k){double f;int i;for(i=0;i<k;i++){f=pow(x+3,1.0/3.0);x=f;}return(x);}main( ){double x0=1.5;int i,k;printf("\n input k(k>0):");scanf("%d",&k);for(i=1;i<=k;i++){printf("\n x=%6.5lf\n",solut(x0,i));}}附录2（牛顿(Newton)迭代法）：%main()为主函数%用途：用牛顿(Newton)迭代法求解非线性方程在非收敛不动点迭代格式情况下的解%格式：solut (double x,int k),solut为被调用函数，x为返回输出的值，即为迭代函数产生的迭代序列k为在一定精度下的迭代次数#include <stdio.h>#include <math.h>double solut(double x,int k){double f;int i;for(i=0;i<k;i++){f=x-(pow(x,3)-x-3)/(3*pow(x,2)-1);x=f;}return(x);}main( ){double x0=1.5;int i,k;printf("\n input k(k>0):");scanf("%d",&k);for(i=1;i<=k;i++){printf("\n x=%6.5lf\n",solut(x0,i));}}附录3（Steffensen迭代法）：%main()为主函数%用途：用Steffensen迭代法求解非线性方程在非收敛不动点迭代格式情况下的解%格式：solut (double x,int k),solut为被调用函数，x为返回输出的值，即为迭代函数产生的迭代序列，k为在一定精度下的迭代次数#include <stdio.h>#include <math.h>double solut(double x ,int k){double f,f1,f2;Int i;for(i=0;i<k;i++){f1=pow(x,3)-3;f2=pow(f1,3)-3;f=f2-(pow(f2-f1,2)/(f2-2*f1+x);x=f;}return(x);}main( ){double x0=1.5;int i,k;printf(“\n input k(k>0):”);scanf(“%d”,&k);for(i=1;i<=k;i++){printf(“\n x=%6.5lf\n”,solut(x0,i);}｝附录4（松弛法）：%main()为主函数%用途：用松弛法求解非线性方程在非收敛不动点迭代格式情况下的解%格式：solut (double x,int k),solut为被调用函数，x为返回输出的值，即为迭代函数产生的迭代序列，k为在一定精度下的迭代次数#include <stdio.h>。

本科毕业设计(论文)题目名称：离散型牛顿法在解非线性方程中的应用学院：数学学院专业年级：信息与计算科学2009级学生姓名：班级学号：200911020110指导教师：姜晓威二O一三年四月十七日摘要牛顿型方法是解非线性方程组的一类重要方法,在非线性方程组迭代解法的理论研究中占有十分重要的地位,牛顿型方法是逐步线性化方法的典型代表,牛顿法的收敛性理论及其研究方法,特别是K ahtopobnu的著名论文,对迭代的研究产生了深远的影响.在通常情况下，非线性算子方程的解不能精确解出，而是用数值方法求其近似解.牛顿法是一种普遍适用的迭代法.它的计算格式简洁，程序简单，而且收敛速度快，适用范围广.多年来，众多学者对经典牛顿法提出多种改进方案，如：萨马斯基提出的修正牛顿法，阻尼牛顿法，拟牛顿法等各种变形.经典牛顿法尽管具有很多优点,但在处理某些不可微问题或导数难计算问题时会遇到一些困难,而离散型牛顿法可以在一定程度上弥补这方面的不足.本文讨论了牛顿法及离散型牛顿法的半局部收敛性及大范围收敛性，并给出数值算例对此两种方法的执行情况.关键词：非线性方程；牛顿法；离散型牛顿法；收敛性AbstractThe Newton method is an important method for the solution of nonlinear equations，Occupies a very important position in the theory group iterative method for solving nonlinear equations.The Newton method is a typical representative of successive l inearization method, Newton method, convergence theory and research method, especially the famous paper Kahtopobnu, exerted a profound influence on the study of iteration.Generally speaking, we can not solve the nonlinear equations exactly. We always Give the approximate solution by using the numerical methods for nonlinear equations. Newton’s method is one of the most powerful and well-known iterative methods known to converge operator equation. In recent decades, scholars obtained many progresses of the classic Newton ’s method for solving nonlinear equations, Frozen- Newton method given by Samaski, damped Newton method, Quasi- Newton method and other forms.In this paper, we will give the convergence and convergence rate of the modified discrete Newton’s method, again. And numerical examples are given to verify the validity of the method. Moreover, using the modified discrete Newton’s method, we propose the modified continuous Newton’s method. We prove that it is convergence.Keywords: nonlinear equations; Newton’s method;Discret e Newton’s method; convergence目录中文摘要 (Ⅰ)英文摘要 (Ⅱ)目录 (Ⅲ)1.引言 (1)2.主要内容 (1)2.1牛顿法和牛顿型方法介绍 (1)2.2牛顿方法的收敛性 (3)2.2.1牛顿法的半局部收敛性 (3)2.2.2大范围收敛问题 (4)2.3.离散型牛顿法 (6)2.3.1半局部收敛性 (6)2.3.2大范围收敛性 (7)2.4数值算例 (8)3.总结 (10)致谢 (11)参考文献 (12)1.引 言牛顿法是牛顿在17世纪提出的一种在实数域或复数域上近似求解方程的方法.多数方程不存在求根公式,因此求精确根非常困难,甚至不可能,从而寻找方程的近似根就显得特别重要.牛顿法是求方程的重要方法之一,其最大优点是在方程0)(=x f 的单根附近具有平方收敛速度,而且该方法还可以用来求方程的重根,复根,此时线性收敛,但是可通过一些手段变成超线性收敛.该方法已广泛用于计算机编程中. 本课题主要来源于非线性算子方程数值解法.随着非线性科学的飞速发展，许多科研工作者逐渐的对非线性问题的求解产生了浓厚的兴趣.线性系统的解很容易由计算机求出，但是对于非线性问题，无论从理论上还是从计算方法上都比解线性问题要复杂的多.一般情况下，非线性问题是很难求出解析解(或精确解)，往往只能求出数值解(或近似解).经典牛顿法尽管具有很多优点,但在处理某些不可微问题或导数难计算问题时会遇到一些困难,而离散型牛顿法可以在一定程度上弥补这方面的不足.2.主要内容2.1 牛顿法和牛顿型方法介绍考虑解方程式 ()0F x =，(2.1)其中映像F :nnR RΩ⊂→ 于凸区域Ω中二次G-可微,且()F x ''于Ω连续.设*x ∈Ω为方程组(2,1)的解.选定*x 的初始近似值(0)x ∈Ω,利用Taylor 级数,我们有1(0)(0)(0)(0)(0)(0)2()()()()(())()(1)F x F xF xx xF xt x xx xt d t'''=+-++---⎰.由于(0)x 充分接近*x ,因此我们可以用线性方程组(0)(0)(0)()()()0F xF xx x'+-= (2.2)近似的代替方程组(2.1).设(2.2)的解为(1)x :(1)(0)(0)1[()]()xxFx F x-'=-. 一般说来,(1)x 应较(0)x 更近似于*x ,因而,类似的可以再(1)x 近旁用线性方程组(1)(1)(1)()()()F xFx x x'+-= 近似代替(2.1),其解(2)x 为*x 的新的近似值: (2)(1)(1)1[()]()xxFx F x-'=-. 一般地.我们有...2,1,0),()]([)(1)()()1(='-=-+k xF xF xxk k k k (2.3)这就是解方程组的牛顿程序.从上述讨论看出,解方程组的牛顿法,无论其形式或者构造方法均与方程式情形相同.对于方程组,同样可以构造简化牛顿程序,其迭代公式为...2,1,0),()]([)(1)()()1(='-=-+k xF xF xxk k k k (2.4)显然,对于方程组,这种简单化更有意义,因为他每一步减少了2n 个微商值的计算. 迭代公式(2.3)及(2.4)一般说来只是一种形式记法,因为,在空间维数n 很大,求微商的逆是困难的.实际计算时,它们分别采用下述形式:(1)()()'()()()()()0,0,1,2,k k k k k k xx x F x x F x k +⎧=+∆⎪⎨∆+==⎪⎩ , (2.5)(1)()()'(0)()()()()0,0,1,2,k k k k kxx x F x x F xk +⎧=+∆⎪⎨∆+==⎪⎩ . (2.6)即利用牛顿法或简化牛顿法计算时,每步需要解一个n 阶线性方程组,其中简化牛顿程序每步所解得方程组具有同一系数矩阵.按上述构造牛顿法的方法,我们实际上是用形如()()()()()()0k k k A xx xF x-+= (2.7)的线性方程组近似代替方程组(2.1),其解(1)()()1()[()](),0,1,2,...k k k kxxA xF xk +-=-= (2.8)即作为(2.1)的解的近似值,为保证()k x 近似于*x ,应要求A(x)近似于*()F x '.基于不 同的考虑,适当选取)(x A ,即得到牛顿法的各种变体.这类方法统称为牛顿型方法.考虑到很多问题(例如,由微积分方程离散化导出的方程组)()F x ''的计算较复杂,因此常常将()F x '的元素用相应的差商代替,即)(x A 去乘下列矩阵:(,)J x h 211111121111(()()),...,(()()).................................................................................11(()()),...,(()())nn nn n n n n n n f x h e f x f x h e f x h h f x h e f x f x h e f x h h ⎛⎫+-+- ⎪ ⎪= ⎪⎪ ⎪+-+- ⎪⎝⎭ (2.9)1(,...,),Tin h h h e=为第i 个单位向量,此时相应的迭代程序(2.8)称为离散型牛顿程序,其计算公式为(1)()()(k )()()()(,)()0,0,1,2...k k k k k k xx x J x h xF x k +⎧=+∆⎪⎨∆+==⎪⎩ (2.10) 其中()k h 为事先选定的向量序列.容易看出,为实现(2.10)每步需计算1+n 个函数向量(即(1)n n +个函数值),并且解一个n 阶线性方程组,每步计算量与牛顿法相同,但无需计算()F x '.2.2牛顿方法的收敛性2.2.1牛顿法的半局部收敛性局部收敛性定理都是在假定原方程的解*x 存在,并且初值0x 必须在真解的某个邻域中得到的.但是一般情况下，我们不知道方程是否有解,自然地，希望能从迭代过程的收敛性去确定方程解的存在性.并且对选取的初值0x ，给出保证迭代收敛性的条件，进一步还希望估计出*xx k-的误差.这样不事先假定解存在的收敛性叫做半局部收敛性.讨论牛顿法的半局部收敛性,最著名的定理是康托洛维奇定理. 定理2.1 设,X Y 均为实Banach 空间,算子0:(,)F B x X Yγ⊂→是F-可微分的,且满足: (i)0[()]F x ' 是Y到X 的有界性算子100||[()]()||F x F x α-'≤10||[()]||F x β-'≤,(ii)0||[()()]||||||,,(,)F x F y L x y x y B x γ''-≤-∈,(iii) 21L αβ<, 2αγ<.则牛顿迭代程序: 11[()](),0,1,...n n n nx x Fx F x n -+'=-= 收敛于方程()F x θ=的唯一解*0(,2),x B x α∈且有估计式:*2111||||2nn n x x q---≤,其中2qL αβ=.2.2.2大范围收敛问题Mbicobcknx 曾经指出,在Cauchy 型条件下,即使对单调函数,牛顿法也仅有局部收敛性质,并且举出方程式情形4ρ>不收敛的例子,然而,选择初始近似(0)x ,使之满足牛顿法的收敛条件是很困难的,因此,改造牛顿型方法,使之具有大范围收敛性,无论在理论上或是实际应用上都有意义的.大范围收敛的牛顿程序是按下降思想导出的,现以方程式为例介绍牛顿下降法的构造思想.考虑解方程式()0F x =(2.11)的牛顿程序(1)()()1(()()k k k kxxFx F s +-''=-,利用Taylor 公式有(1)(1)()()(1)|()||()()()()|k k k kk kF xF xF xFx x x +++'=---(k )()1()21|(x)||()()|2k k F F x F x-'''=,式中()()(1)()(),01k k k k x xx xθθ+=+-<<. 由此看出,若()()12()1|()||()||()|12k kk F xF x F x -'''<, (2.12)则有(1)()|()||()|k k F x F x +<.条件(2.2)实际上是Mbicobcknx 定理2.1中的条件2ρ<.换言之,当()F x 满足Cauchy 型条件时, 2ρ<保证了()|()|k F x 随着k 的增大而减少.上述事实启发我们适当改造牛顿程序,以减弱2ρ<的限制并保持()|()|k F x 关于k 下降的性质.基于这种考虑,构造程序(1)()()1(()()k k k kk xxFx F x ω+-'=- , (2.13)仍利用Taylor 公式导出(1)2()()12()()1|()|(|()||()||()|1)|()|2k k k kkk k F xF x F x F x F x ωω+-'''≤-+, 01k ω<≤,当()()12()1|()||()||()|12kk k k f xf xf x ω-'''<(2.14) 时,将有(1)|()||()|k kf x f x +<.只要取k ω充分小,尽管(2.2)不成立,仍可使(2.4)成立.这就解除了2ρ<的限制.鉴于上述讨论,在方程组情形考虑下述牛顿下降程序(1)()()1(()()k k k kk xxFx F x ω+-'=- 0,1,...,01k k ω=<≤ (2.15)我们有 定理2.2 设:nnFR RΩ⊂→满足下列条件:(1)(0)||()||;F x η< (2)于区域(0){||||}()x x xF x γβη'Ω=-≤⊂Ω有逆存在,且1||()||,F x x β-''≤∀∈Ω, (2.16)||()()||||||,,F x F y x y x y ρ''-≤-∀∈Ω (2.17) 则当22/1γρα≥>时,方程组()F x =于0Ω有解*x 存在,且对任何01k ω<≤,210,02,k a x αωρβη<≤≤-=.由(2.5)定义之()k x 收敛于*x ,且至少是线性收敛的.注1 当满足定理2.1的条件时,有0k 使02||()||2kx F x βα≤-,此时视0k x 为该定理中(0)x ,仍满足定理条件,因而可取1k ω≡,即此时牛顿法收敛,因而得到二阶收敛性.注2 注意到二次三项式21()12ϕωωρω=+- 在12ρ>时由1ωρ=处取最小值:11()12ρϕρρ=-,因而,为使(2.5)具有较快的敛速,可取2(k)1/||()||kx F xωβ=,换言之,程序(2.5)可以取成下列形式(1)()()1(2()()(),m i n {1,1/||()},0,1,2,... .k k k k k k k x x F x F x xF x k ωωβ+-'⎧=-⎪=⎨⎪=⎩(2.18) 对由(2.11)定义的()k x ,估计式(3.8)变成为()()22(1)2()2()212||()||,||()||;2||()||12||()||,||()||.2k k k k k F x F x X X F x X F x F x X ββββ+⎧-≥⎪⎪≤⎨⎪≤⎪⎩当当 (2.19) 注3 如果集合{||()||()||}Dx F x F x =<为有限区域,且于D 满足(2.6)(2.7)则对任何(0)(0),||()||||()||x D F x F x ∈<,故定理(2.1)的结论成立.事实上,此时由(2.5)定义的()k x 均落于D 中,否则,若有某m,使()m x D∈,而(1)m x D+∈,则有()()1()()()m m m m xx Fx F x θω-'=- ,01θ<<,使||()||||()||F xF x = ,对此x 仍有222()()1||()||(||()||1)||()||2m mm m F xX F x F x θωβθω<-+(0)||()||F x < , 这就导致了矛盾.前述定理已给出了牛顿法的大范围收敛条件.程序(2.5)早就有人研究过.2.3离散型牛顿法2.3.1半局部收敛性对于非线性算子方程 ()F x θ=其中,:FX Y→,这里Y X ,都是Banach 空间,则有以下定理:定理2.3设,X Y 均为实际Banach 空间,算子0:(,)F B x r X Y⊂→是F-可微分的,且满足:(i) 10[()]F x -'是Y 到X 的有界线性算子,100||[()]()||F x F x a-'≤ ,10||[()]||F x β-'< (ii)||()()||||||,F x F y L x y ''-≤- 0,(,)x y B x r ∈(iii)41,2,lim 0n n L a r αβτ→∞<<=则离散型牛顿法11[()]()(),0,1,...n n n n n n x x F x F x x x n τ-+'=---=收敛于式(3.1)的唯一解*0(,)x B x r ∈,且有估计式:*02||||2() (,)32n n r x x a x B x -≤∈.即对牛顿法进行简单修正后得到的离散型牛顿法 11[()]()(),0,1...n n n n n n x x F x F x x x n τ-+'=---=只要对n τ附加条件:lim 0nn τ→∞=,再加上牛顿法收敛的条件,就能收敛到非线性算子方程()F x =的解*x ,且收敛率为*2||||2()3nn x x a -≤ .2.3.2大范围收敛性由于离散牛顿法在实际应用中的重要性以及它对初始近似的苛刻限制(定理3.2及3.3),研究离散牛顿程序的大范围收敛条件更有实际意义. 相应于离散牛顿程序烤炉大范围收敛程序(1)()1()()()()11(,)(),||||||()||.k k kk kk k k k xx J xhF xhF x ωω+-⎧=-⎪⎨≤⎪⎩我们有定理2.4 设:nnFR RΩ⊂→ 满足下列条件:(1)0||()||F x η≤,(2)于(0){||||}x x xγβηΩ=-≤⊂Ω内()F x '有逆存在,且满足(2.6)及(2.7),则当35/γρα≥时,方程组()F x =于0Ω有解*x 存在,且对任何401,07k k ωαωρ<≤<≤≤,由(2.13)定义的序列(){}k x 收敛于*x ,并且至少是线性收敛的,其中,max(,1)X ρββηββ==.对于定理2.2也可以列出与定理2.1类似的注记.例如,特别可以取0Ω为集合11{||()||||()||}D x F x F x =≤,而(0)x 满足条件(0)11||()||||()||F x F x ≤其次,为提高收敛速度可以将(2.13)取成下列形式(1)()1()()()()1()()11(,)(),m in{1,25/84||()||},||||||()||.k k k k k k k k k k k x x J x h F x X F x h F x ωωββω+-⎧=-⎪=⎨⎪≤⎩此时由(2.13)定义的()k x 有下述估计式:()()11(1)1()2()11254||()||,||()||;1687||()||424||()||,||()||257.k k k k k F x X F x X F x X F x X F x ββββββββ+⎧-≤⎪⎪≤⎨⎪>⎪⎩当当最后,容易想到,仿定理2.2可以建立离散型牛顿程序的大范围收敛性定理.2.4数值算例本小节对二个经典的非线性方程组分别运用牛顿法和离散型牛顿法求解,并将所求结果进行对比,直观的说明修正的离散型牛顿法的有效性.1. 求方程组212121()0c os(/2)x x F x x x π⎧⎫-+==⎨⎬-⎩⎭的真解为*(0,1)x =,其中迭代停止准则为101||||10n n x x -+-≤.若取初值0(1,0)x =,用牛顿法收敛到(1,2)-,不收敛到所需要的真解*x .若使用离散型牛顿法来求解非线性方程组,取(0.5,0.5)x=-,则有小面的计算结果:表2.1取(0.5,0.5)x=-时的修正的离散型牛顿法迭代计算结果2. 方程组121212211(sin())22()01(1)()24x x x x x f x ex e e ex πππ⎧⎫--⎪⎪⎪⎪==⎨⎬⎪⎪--+-⎪⎪⎩⎭的真解为*(0.3,2.8)x =,其中迭代停止准则为101||||10n n x x -+-≤.若取初值0(0.1,0.1)x =,使用牛顿法进行迭代,求解结果收敛到点(-0.26059929002248,0.62253089661391), 也就是不收敛到所需要的真解*x . 而用离散型牛顿法求解,若取(0.5,3.3)x=,则有以下计算结果:表2.2取(0.5,3.3)x=时离散型牛顿法迭代计算结果对于以上两个非线性方程组,当初值取在真解附近时,使用牛顿法求解,所得结果都不收敛到真解,而使用离散型牛顿法求解,所得结果都收敛到真解,收敛准则都确定为101||||10n n x x -+-≤.数值算例的结果说明了离散型牛顿法是可行有效的.3.总 结牛顿型方法是解非线性方程组的一类重要方法,在非线性方程组迭代解法的理论研究中占有十分重要的地位,牛顿程序的构造方法是逐步线性化方法的典型代表,牛顿法的收敛性理论及其研究方法,特别是Kahtopobnu[1984,1957]的著名论文,对迭代的研究产生了深远的影响. 因此, 寻找快速可行的迭代的方法具有重要意义本文针对这种离散型牛顿法，列出完善的收敛性证明以及收敛速率，并应用数值算例验证算法的可行性.致谢本文的研究和撰写工作都是在导师姜晓威老师的悉心指导下完成的. 从论文的选题、开题、撰写直至最后的答辩, 都得到了姜老师的关心、大力帮助和耐心指导. 姜老师在学术上敏锐的洞察力、开阔活跃的学术思维、不懈进取的精神、严谨的治学风范、崇高的敬业精神、渊博的学识给我留下深刻的印象, 将使我终身受益. 最令我感动的是姜老师在我撰写论文期间给予了孜孜不倦的指导, 他严谨的科研作风给我留下了深刻的教诲和影响. 谨此之际, 向关心和培养我的导师姜晓威老师表示衷心的感谢和诚挚的敬意!同时, 感谢论文的各位评审专家能在百忙之中抽出时间对我的学士论文进行评审, 并提出宝贵的建议, 在此表示衷心的感谢! 最后, 向所有曾经关心和帮助过我的老师、同学、朋友表示诚挚的感谢!参考文献[1]关治, 陆金甫.数值分析基础（第二版）[M], 高等教育出版社,1998.52-67[2]谢如彪, 姜培庆.非线性数值分析[M], 上海交通大学出版社, 1984. 1-6[3] 袁东锦, 计算方法（第二版）[M], 南京师范大学出版社,2007. 183-209.[4] 李庆扬, 王能超，易大义.数值分析[M], 清华大学出版社,1995.863-1003[5] 姜波, 徐家旺. 非线性方程组的数值解法比较[J],沈阳航空工业学院报,2002(29):195-203.[6]邓建中, 葛仁杰,程正兴.计算方法[M], 西安交通大学出版社,2003(30): 1255-1258.[7]吴淦洲.求解非线性方程组的改进牛顿法[J], 茂民学院学报,2004, 8(2): 88-96.[8]田巧玉,古钟壁,周新志.基于混合遗传算法求解非线性方程组[J], 计算机技术与发展, 1999, 292: 99-125.[9]罗亚中,袁端才,唐国金.求解非线性方程组的混合遗传算法[J]. 计算力学学报,1979, 244(5): 1093-1096.[10] Gill P E, Murray W, Saunders M A, Tomlia J A, Wright M H. On projected Newton barrier methods for linear programming and an equivalence to Karmarkar’s projective method[J]. Mathematical Programming, 1986, 36: 183-209.。