非线性方程求重根方法研究

2016届毕业生 毕业论文

题 目： 非线性方程求重根方法研究 院系名称： 理学院 专业班级： 学生姓名： 学 号： 指导教师： 教师职称：

2016年05月20日

摘 要

随着科学技术的发展，在现代科学和工程技术中，经常会遇到大量而复杂的数学计算问题。这些问题常常归结为非线性方程求根的问题。求解非线性方程的单根已经具有了比较成熟和丰富的构造技术手段。例如，其中在工程和其他领域的科学计算中的广泛应用迭代算法，它从某个初始点出发，由迭代格式生成一种收敛于方程根的序列。这些方法在面对非线性方程单根的时候可以很好的解决问题，然而这些方法在求解非线性方程的重根时，构造的算法显得相当的复杂甚至是无效的。举一个简单的例子就是平时我们经常研究的经典的牛顿迭代法。它对方程的单根二阶收敛，但是对于于方程的重根只能线性收敛，并且收敛速度变慢。因此非线性方程重根的高阶，尤其是最优解的迭代格式如何构造是一项具有挑战性的工作。直到现在，这方面的研究成果还不是很丰富。目前绝大多数求重根的最优阶迭代算法都是利用方程重根的重数信息来构造迭代格式。对于各种求非线性方程求重根这一问题，国内的许多数学界的前辈对此从不同的方面展开了研究，并在不同方面取得了一定的成果。全文共分为三章

第一章概述了相关的基础理论知识，主要介绍了非线性方程求根的研究背景和及研究现状，着重介绍了迭代法的相关知识，探讨了几种求非线性方程的解的方法，论述了各个解法的优缺点。

第二章主要介绍了迭代法在非线性方程求重根的情形下的应用，给出了几种新的修正迭代格式，从各个思路对非线性方程求重根进行了探讨，并且了解了一些其他求非线性方程重根的方法。 第三章是总结了全文主要的讨论内容。

关键词: 非线性 二分法 迭代 收敛 迭代加速 牛顿法 修正牛顿法 重根 阶乘法

I

Title Nonlinear equation root method and study

Abstract

With the development of science and technology,people often encounter large and complicated mathematics problems in the modern science and engineering. These questions often come down to the problem of nonlinear equation for the root. To solve the nonlinear equation of single has mature technology and rich structure. For example, one in the field of engineering and other scientific computing is widely used in the iterative algorithm，It starting from an initial point, generated by the iterative format a sequence converges to equation root.These methods when he faced the nonlinear equation of single can well solve the problem, however, these methods in solving the nonlinear equations of roots, the structure of the algorithm is quite complex and even invalid.A simple example of this is we often study at ordinary times the classic Newton iteration method.It to the equation of single second order convergence, but for the equation of double root only linear convergence, and slow convergence speed.So the roots of the high-order nonlinear equation, especially iterative format how to construct the optimal solution is a challenging job.Until now, the research achievements are not very rich.At present, most of the multiple roots optimal order iterative algorithm is using heavy equation root of multiplicity information to construct the iterative format.For a variety of heavy to nonlinear equations for the root of this problem, the predecessor of many domestic to this from different aspects, and has obtained certain achievements in different aspects.Full text is divided into three chapters

The first chapter summarizes the related basic theoretical knowledge, mainly introduced the research background of nonlinear equation for the root and and the research status, introduces the iterative method of related knowledge, discusses several ways to the solution of nonlinear equations, the advantages and disadvantages of each method are discussed.

The second chapter mainly introduces the iterative method in nonlinear equations

II

roots under the situation of the application, several new modified iterative format is given, from different way of thinking are discussed in this paper, the roots of nonlinear equations for heavy and learning some other nonlinear equation root method.

The third chapter summarizes the full text is the main discussion.

Keywords:

method

Nonlinear dichotomy iterations convergence an iterative

acceleration Newton's method modified Newton method multiple root factorial

III

目 录

1 非线性方程求根的基本方法 ........................................... 1

1.1 非线性方程求根 ................................................ 1 1.2 迭代法的基本思想 .............................................. 2 1.3 二分法 ........................................................ 2

1.4 不动点迭代法 .................................................. 3 1.5 迭代法的收敛性 ................................................ 4 1.6 迭代法的收敛速度 .............................................. 6 1.7 迭代加速收敛的方法 ............................................ 7

1.7.1 Aitken加速方法 .......................................... 7 1.7.2 Steffensen迭代方法 ...................................... 8 1.8 Newton法 ..................................................... 9

1.8.1 Newton法及其收敛性 ...................................... 9 1.8.2 简化牛顿法及牛顿下山法 ................................. 10 2 非线性方程求重根方法研究 .......................................... 12 2.1 牛顿法在非线性方程求重根时的情形 .............................. 12

13 2.1.1 已知根的重数m ........................................ 14 2.1.2 未知根的重数m ........................................ 2.2 牛顿法在非线性方程求重根的情形下的一些改进方法 ............... 15

2.2.1 无约束优化技术中的牛顿法 ............................... 15

.............. 18 2.2.2 Aitken加速外推下的修正牛顿法求重根重数

20 2.3 一些其他的求非线性方程重根的方法 .......................... 总 结 ............................................................... 22

参 考 文 献 ......................................................... 23

IV

1 非线性方程求根的基本方法

在现实中的许多问题中，如流体力学，弹性力学，电路和电力系统计算，非线性规划等众多领域，常常会遇到求解非线性方程的问题。 设有非线性方程：

f(x)?0 (1.1) 其中函数f(x)可以是超越函数，则其对应方程为超越方程如e5x?sinx。函数f(x)也可以是多项式函数，即

f(x)?anxn?an?1xn?1?????a1x?a 0其中an?0，则称方程（1.1）为n次代数方程。当n?1,2时，求根公式大家都是熟悉的，当n?3,4时。也可以在数学手册上查到根的公式和求法。然而当n?5时，就无法用加减乘除和根式等运算的一般公式来准确写出根的表达式，所以需要数值方法来解决这个问题。

对于代数方程有单根和重根的概念，这可推广到一半方程（1.1）.如果存在常数s使得f(x?)?0,则称s是方程（1.1）的根，又称x?是函数f(x)的零点。若f(x)能分解为

??xm)? f(x)?(x( x)其中?(x?)?0，则称x?是方程（1.1）的m重根和f(x)的m重零点。当m?1时，x?为方程（1.1）的单根和f(x)的单零点。

1.1 非线性方程求根

只有很少类型的非线性方程能解出根的解析表达式，对于大多数非线性方程，通常只能得到一定精度的近似解。一般情况下，多用迭代方法解决此类问题。

首先，要判断根是否存在：判断（1.1）是否有根，如果有，存在几个根？例如对多项式方程，n次方程就有n个根。

其次，确定跟的隔离：把有根区间分成较小的子区间，每个自取件或者有一个根或者没有根，这样可以将有根子区间内的任一点都可以看成该根的一个近似值；

最后，使根精确化：对根的某个初始值设法逐步细化，使之达到一定的精度要

1

求。

1.2 迭代法的基本思想

迭代法是一种逐步逼近的方法，其基本思想是利用迭代格式反复校正根的近似值，使之逐步精确化，直到满足精度要求为止。迭代的基本步骤有两步：首先提供根的估计值，称为迭代初值，然后利用迭代格式将初值逐步转换为满足精度要求的根。

设给定方程f(x)?0，将方程转换为与其等价的形式：

x??(x) （1.2） 这里的方程式隐式的，因此无法直接求出它的解。但是如果直接给出根的某个猜测值x0，将它带入式（1.2）的右端，即可求得x1??(x0)。然后，又可取x1作为猜测值，进一步得到x2??(x1)。如此反复计算。计算公式

,?0,1???,2 xk?1??(xk)k , （1.3）

称为迭代格式。此时得到的一个序列{xk}，称为迭代序列。如果确定的序列{xk}有极限x??limxk，则称迭代公式（1.3）收敛。这时极限值x?显然就是方程（1.2）的

k?0根。

上述迭代法的基本思想就是将隐式方程（1.2）归结为一组显式的计算公式（1.3），就是说，迭代的实质上是一个逐步逼近逐步显式化的过程。利用迭代法求解非线性方程（1.1）需要考虑以下几个问题：

（1）初始的近视根如何选取？

（2）迭代函数如何构造？迭代序列是否收敛？ （3）收敛速度如何？怎样进行误差分析？

1.3 二分法

如果在区间[a,b]上方程（1.1）至少有一个根，那就称[a,b]是方程f(x)?0的一个有根区间，例如，如果知道f(a)f(b)?0,由于f的连续性，可知[a,b]是一个有根区间，可以用一些x点上的函数值f(x)的符号来搜索有根区间。如果在[a,b]上方程有且只有一个根，那就把方程的根隔离出来了，这时候若能把有根区间不断缩小，

2

便可逐步得出根的近似值。

求根方法中最简单最直观的方法是二分法，定义如下

定义1.1 对于[a,b]上连续不断且f(a)f(b)?0的函数y?f(x)，通过不断的把函数 f(x)的零点所在的区间一分为二，是区间的两个端点逐步逼近零点，进而得到零点近似值的方法。

二分法的优点是计算过程简单，收敛性可保证，对函数性质要求低，只要求连续就可以了；它的缺点是计算出来的值收敛速度慢，不能求偶数重根，也不能求复根和虚根。特别是函数值f(ak),f(bk)(k?0,1,2,???)每次均以计算出来，但是没有利用上，只利用了它们的符号，显然是一种浪费。在此基础上人们改进了二分法，充分利用函数f(ak),f(bk)(k?0,1,2,???)的值求根称为试位法，收敛速度速度比二分法快乐许多。

1.4 不动点迭代法

在1.2中我们了解到迭代法的基本思想，我们可以通过不同的途径将方程（1.1）转变为等价方程（1.2）的形式。例如，令?(x)?x?f(x)或者?(x)?x?Af(x)，其中A为常数。函数?(x)与f(x)的定义域可能不相同，但要求它们在所要求的f(x)?0的解x?邻近都有定义。

定义1.2 为了了解方程（1.1）类似线性代数方程组迭代法的构造，把方程（1.1）变换为等价的方程（1.2）。其中?为迭代函数，利用方程（1.2）可以构造迭代公式（1.3），如果limxk?x?，则x?满足方程（1.2）。称x?是迭代函数，x?是函数?的

k?0一个不动点，它也就是方程（1.2）的一个根方法（1.3）被称为不动点迭代法。

用迭代法(1.3）求解f(x)?0，需要讨以下问题： （1）如何选取合适的迭代函数?(x)；

（2）迭代函数?(x)满足什么条件，迭代序列收敛到x?，收敛速度是多少； （3）怎样加速序列{xk}的收敛速度。

3

1.5 迭代法的收敛性

方程f(x)?0的转化形式不同（即迭代函数?(x)不同），随之建立的迭代格式迭代后得到的序列的收敛性也不同。这意味着，并非任意的等价变换后所建立的迭代格式都是收敛的。那么应该如何变换才能使所建立的迭代格式收敛呢？下面我们就来讨论下迭代格式的收敛性。

考虑在区间[a,b]上的迭代函数?(x)的收敛性。 定理1.1 设函数?(x)在区间[a,b]上连续，且满足： 1 映内性： ?x?[a,b]，?(x)?[a,b]；

2 压缩性：存在常数0?L?1，使得?(x1)??(x2)?Lx1?x2，其中L称为压缩系数（Lipschitz 系数）， 则

（1）函数?(x)在区间[a,b]存在唯一的不动点x?；

（2）对任意的初值x0?[a,b]，迭代格式（1.3）所产生的迭代序列一定收敛到x?； （3）误差的估计如下；

L x??x?xkk?x?k1， （1.4）

1?LLkx1?x0. （1.5） x?xk?1?L? 由定理1.1可以看出

xn?1?x?xn?x??L，即

xn?1?x??Lxn?x?.

因此参数L决定迭代速度，并且L的值越接近于0，迭代的收敛速度就越快。由定理1.1 可知，如果L已知，根据给定的精度便可以估计出迭代的次数。在实际操作中，L是难以确定的，运用起来很不方便，但是从（1.4）中可以看出：只要两次相邻的迭代值之差的绝对值充分小，就可以保证迭代值xk充分接近于x?。当L未知时，如果已知精度?，则迭代的终止准则为 xk?1?xk??.

4

在实际操作中，总是采用如下定理来判断迭代格式的收敛性。

定理1.2 将方程f(x)?0f(x)?0改写为x??(x)，如果?(x)在区间[a,b]上连续，且满足：

1 映内性：?x?[a,b]，?(x)?[a,b]；

2 ?x?[a,b]，??(x)存在，且??(x)?L?1，其中L为Lipschitz常数，与x1,x2无关，则迭代xn?1??(xn)收敛，且收敛到f(x)?0的解x?。

迭代法求根的一个显著的优点就是逻辑结构简单，并且只要保证相邻两次迭代值得偏差充分小，就可以保证迭代的收敛性，可以用xk?1?xk控制计算的精度。一般而言，使用迭代法求解的过程如下：

首先，选取初值x0和误差限?，构造方程f(x)?0的等价变换形式x??(x)； 其次，依据构造好的迭代格式x1??(x0)计算?(x0)；

最后，判断x1?x0??，如果成立则停止计算，x1即为方程的根；反之，令x1?x0重复低二第三步。

在上述算法中x0和x1分别代表每次迭代的初值和终值，?为误差限。如果收敛速度过慢则放弃，可以用最大迭代次数N来控制。

在定理1.1和定理1.2中我们讨论了迭代函数?(x)对任意的x0?[a,b]的收敛性，这可以说是在区间[a,b]上的全局收敛性。然而在使用是需要讨论迭代函数在整个区间上的映内性和压缩性，使用不便。另外，我们平时更想要知道的是迭代序列在迭代函数不动点附近的收敛性，即设法找到一个在不动点附近的初始根。这时如果迭代序列收敛则收敛的速度很快；如果迭代序列不收敛，则任何初始根都不会使迭代序列收敛。因此我们更需要讨论在不动点x?附近的收敛性，称之为局部收敛性。 定义1.3 设?在区间I上有不动点x?，若存在x?的一个邻域S?I，对任意的

x0?S，不动点迭代法（1.3）产生的序列{xk}?S，且{xk}收敛到x?，则称迭代法

（1.3）局部收敛。

定理1.3 设x?为?的不动点，??(x)在x?的某个邻域S上存在且连续，满足

5

??(x?)?1，则迭代法（1.）局部收敛。

1.6 迭代法的收敛速度

对于一种迭代法要具有实用价值，不仅要收敛，而且还有有比较快的收敛速度。迭代过程的收敛速度就是指误差在收敛过程中的下降速度。因此，提出了收敛阶的概念。

定义1.4 设序列{xk}收敛到x?，记误差ek?xk?x?。若存在实数p?1及非零常数C，使

ek?1 limp?C， （1.6）

k??ek则称{xk}为p阶收敛，C称为渐近误差常数。

可见，收敛阶确实描述了迭代接近收敛时迭代误差下降的速度，即迭代收敛速度，因此，收敛阶的概念刻画了迭代速度的快慢。一般来说，p越大，收敛速度越快。 当p?1时，也称{xk}线性收敛，p?1时称超线性收敛，p?2时称平方收敛。定义中，若p?1，则只有c?1时迭代才收敛；若p?1，c?0是为了保证收敛阶p的唯一性。则c不要求小于1.

如果{xk}线性收敛，则（1.6）式的常数C满足0?C?1，如果{xk}超线性收敛，则有

e limk?1? 0 （1.7）

k??ek 如果?满足定理1.3的条件，且在x?的邻域S内有??(x)?0，则迭代法产生的{xk}收敛。若取x0?x?，必有xk?x?(k?1,2,???)，而且 ek?1?xk?1?x???(xk)??(x?)???(?k)ek， 因此有

e??). 0 limk?1???x(k??ek{xk}在这种情况下为线性收敛。反之，若??存在且连续，想要得到超线性收敛序列

6

{xk}，就必须要求??(x?)?0。因此在整数解收敛的情形下有如下定理。

定理1.4 设x?为?的不动点，整数p?1，?(p)(x)在x?的邻域上连续，且满足

(p)? ?(k)(x?)?0,k?1,2,???,p?1， ?(x)?0， (1.8)

则有迭代法（1.3）产生的序列{xk}在x?的邻域上是p阶收敛的，且有

ek?1?(p)(x?) limp?.

k??ep!k （1.9）

1.7 迭代加速收敛的方法

虽然收敛阶能够刻画迭代收敛于根x?所需的迭代次数的多少，但并不能说明迭代到收敛时所需的的时间的多少。 对于收敛的迭代过程，只有迭代次数足够，总是可以是结果达到任意的精度。然而依然需要考虑收敛的速度问题，因为缓慢的迭代速度将导致计算量的增大，因此需要探究迭代法的加速问题. 1.7.1 Aitken加速方法

线性收敛的序列收敛较慢，常常考虑加速收敛的方法。设{xk}线性收敛到x?，记作ek?xk?x?，有

ek?1 lim?C， 0?C?1.

k??ek当k充分大时有

xk?1?x??c(xk?x?)， xk?2?x??c(xk?1?x?)， 其中c?C.由

xk?2?x?xk?1?x??

xk?1?x?xk?x?可解出

2xkxk?2?xk?1 x?.

xk?2?2xk?1?xk?在计算了xk，xk?1和xk?2之后，可以用上式右端作为xk?2的一个修正值，利用差分记号?xk?xk?1?xk，?2xk?xk?2?2xk?1?xk，写成

7

2xkxk?2?xk(?xk)2?1 xk?， （1.10） ?xk?2xk?2?2xk?1?xk?xk它是x?的一个新的近似值，从序列{xk}用（1.10）式得到的序列xk的方法，称为Aitken加速方法.

可以证明，只要{xk}满足xk?x?,k?1,2,???，且lim式产生的序列xk是完全确定的，而且有

xk?1?x?? 0 limk??x?x?kek?1??，??1，则有（1.10）

k??ek????即序列xk收敛比Aitken要快。

Aitken加速法避免了微商的计算，但是每次需要进行两次迭代 1.7.2 Steffensen迭代方法

Aitken方法对{xk}进行加速计算，得到序列xk，它不管原来序列{xk}是如何产生的。如果我们把关于函数?的不动点迭代与加速技巧结合起来，有如下的Steffensen迭代法：

???????yk??(xk),? ?zk??(yk), （1.11）

?2(y?x)kk?xk?1?xk??zk?2yk?xk? 如果把（1.11）式写成一种不动点迭代的形式

xk?1??(xk)， （1.12） 则迭代函数?(x)为

[?(x)?x2]?(x)?x??(?(x))?2?(x)?x?x?(?(x))?[?(x)]?(?(x))?2?(x)?x2. （1.13）

与Aitken加速迭代法相类似，Steffensen加速迭代法不但可以加快迭代速度，有时候

8

还可以使某些发散的迭代改变为具有较好收敛性的迭代。

1.8 Newton法

前面简单介绍了非线性方程的研究背景以及几种非线性方程求根的常用方法。下面我们重点来了解一种求解非线性方程的经典迭代法——Newton法。牛顿迭代法是非线性方程求方程根的重要方法之一，牛顿迭代法收敛速度比较快，迭代形式简单，在方程（1.1）的单根附近具有平方收敛，并且牛顿迭代法求方程的重根，复根也可以很好的应用。随着数学研究的进步，几百年来，新的迭代格式层出不穷，但是几乎所有的迭代发的研究都是以牛顿迭代法的技巧和分析方法为基础。在研究牛顿迭代法收敛性的过程中得到很多理论都被人们借鉴引用。无论是理论研究还是实际应用中，牛顿迭代法在迭代发的历史中所起的左右是任何迭代法都无可替代的，因此我们需要对牛顿迭代法熟练掌握。 1.8.1 Newton法及其收敛性

对于非线性方程f(x)?0而言，如果f(x)是线性函数，则它的求根是容易的。牛顿法得基本思想是将非线性方程f(x)?0逐步归结为某种线性方程来求解，因此牛顿法的实质是一种线性化方法，

设方程f(x)?0的函数f(x)连续可微，x?为方程f(x)?0的实根，xk是其某个近似值。将f(x)在xk点作Taylor展开；

f(x)?f(xk)?f?(xk)(x?xk)?f??(xk)(x?xk)2???? 2!取其线性部分作为f(x)的近似，得到

?x)(? f(xxk)?f(k设f?(x0)?0，其解为 x??xk?f(xk). ?f(xk)kx?) 0将这一近似值作为第k+1次迭代，得到如下的迭代格式: xk?1?xk?f(xk) (k?0,1,?2?,?. (1.14) f?(xk)这就是牛顿迭代法。

9

图 1-1

牛顿法有着明显的几何意义。方程f(x)?0的根x?可解释为曲线y?f(x)与x轴的交点的横坐标（图1-1）设x0是根x?的某个近似值。过曲线y?f(x)与横坐标为x0的点（(x0,f(x0))引切线，并将该切线与x轴交点的横坐标x1作为x?的新的近似值，注意到切线方程为

y?f(0x)??f(0x)(?x0 x)这样求得的值x1必满足f(xk)?f?(xk)(x?xk)?0。从而就是牛顿公式（1.14）的计算结果。因为这种几何背景，牛顿法又被称为切线法。

关于牛顿法的收敛性有如下定理

定理1.5 设f(x?)?0，f?(x?)?0，且f在包含x?的一个区间上有二阶连续倒数，则牛顿迭代法（1.14）局部收敛到x?，且至少是二阶收敛，并有

xk?1?x?f??(x?)? lim. （1.15) ?k??(x?x?)2?2f(x)k这一结果表明:牛顿法具有平方速度。 1.8.2 简化牛顿法及牛顿下山法

牛顿法的优点是收敛快，缺点一是每步迭代要计算f(xk)及f?(xk)，计算量较大且有时f?(xk)计算困难，二是初始近似x0只有在根x?附近才能保证收敛，如x0给的不合适可能不收敛。因此在实际应用牛顿迭代法时，常根据这两种情况可以作适当的修正。

（1）简化牛顿迭代法

如果所遇到的问题中f?(xk)很难计算，则可将式（1.14）修改为

10

xk?1?xk?Cf(xk)， C?0, (k?0,1,2,???) (1.16) 迭代函数?(x)?x?Cf(x)。

0?Cf?(x)?2。在根x?附近成立，则迭代法 若 ??(x)?1?C?f(x?)，即取1（1.16）局部收敛。在（1.16）中取C?1，则称式（1.16）为简化牛顿迭代法。 f?(x0)这类方法虽然只有线性收敛，但计算量简单，其几何意义是用平行弦月x轴交点作为

x?的近似。 （2）牛顿下山法

牛顿法收敛性收初值x0的选取影响很大，如果x0偏离所求根x?太远，则牛顿法可能发散。为了防止迭代发散，我们队迭代过程附加一项要求，及具有单调性： f(xk?1)?fx(k. ) （1.17） 我们把符合这项要求的算法称为下山法。

如果在下山法保证函数值稳定下降的前提下，用牛顿法加快收敛速度，将牛顿法与下山法结合起来使用。首先将牛顿法的结果 xk?1?xk?f(xk) f?(xk)与前一步的迭代值xk作适当加权为新的改进值，即 xk?1??xk?1?(1??x)k， 或者说

xk?1?xk??f(xk) (k?0,1,?2?,? （1.18） f?(xk)这里的0???1称为下山因子。只要选择适当的?，就可以使（1.17）成立。称为牛顿下山法。但是，?的选择只能是一个逐步选择和探索的过程。从??1开始，按照一定步长将?的值逐步递减进行尝试。如果整个尝试过程中找不到合适的?，则称“下山失败”，此时只能重新选择初值x0。

11

、

2 非线性方程求重根方法研究

之前我们的讨论的许多方法在面对非线性方程单根的时候可以很好的解决问题，然而这些方法在求解非线性方程的重根时，构造的算法显得相当的复杂甚至是无效的。因此非线性方程重根的高阶，尤其是最优解的迭代格式如何构造是一项具有挑战性的工作。

2.1 牛顿法在非线性方程求重根时的情形

Newton迭代法是非线性方程求根的一个基本方法，牛顿法因收敛速度快而得到广泛应用，然而牛顿迭代法在求重根是是否可以很好的应用呢？下面我

12

们来研究这个问题.

若根x?的重数m?1，及f(x?)?f?(x?)?????f(m?1)(x?)?0，则所有建立在反函数基础上的推导均归无效，这是因为在x?的任何邻域内不存在反函数。虽然如此，可以证明牛顿迭代法在重根邻域是线性收敛的。事实上，对于牛顿迭代公式中的迭代函数，有

?(x)?x?f(x)f?(x)f(x?)?f?(x?)(x?x?)?????1(m)f(?1)(x?x?)mm!?x? 1???(m)?m?1f?(x)?f??(x)(x?x)?????f(?2)(x?x)(m?1)!1f(m)(?1)?x?(x?x?)(m)mf(?2)?1，?2在x与x?之间。

??考虑到?(x)?x，于是有

lim ??(x)?x?xx?x????(x)???x(?)1??1?，0 m?1， (2.1)

m?由于m?1，??(x)??1?1?1，所有由定理1.3及定理1.4得知，牛顿迭代法对mm重根x是一阶收敛的。

我们对牛顿迭代法加以修正，使其对重根应用是仍具有二阶收敛性。 2.1.1 已知根的重数m

当根的重数m已知时，可将式（1.14）修正为

xk?1?xk?mf(xk)， (k?0,1,?2?,?. （2.2） f?(xk)?此公式对m重根x?是二阶收敛的。事实上，因为

?k?1?x??xk?1?x??xk?mf(xk)f?(xk)(x??xk)f?(xk)?mf(xk)G(xk)??f?(xk)f?(xk) （2.3）

?其中，G(x)?(x?x)f?(xk)?mf(xk)，由

13

??(m)????f f(x)??f(x??1)(?x)，? 0得

G(j)(x)?mf(j)(?x)?(?xx)?j(f1)?(x)jj(f()x

(j)?2,m , G(x)?0， j?0,1,???(m?1)(x?)??f(m?1)(x?) G?利用对G(xk)，f?(xk)在x附近进行Taylor展开，有

1G(m?1()?1)?km?1G(m?1()?1)21(m?1)!??k， ?k?1?(m)1m(m?1)f(?)(m)m?12f(?2)?k(m?1)!于是，得

?k?11f(m?1)(x?)??0。 lim(m)?k???2m(m?1)f(x)k从而证明了式（2.2）是m重根x的二阶公式。 2.1.2 未知根的重数m

当根的重数m未知时，式（1.14）可修正为 xk?1?xk?u(xk)， (k?0,1,?2?,?. （2.4） u?(xk)?其中，u(x)?f(x). ?f(x) 显然，该公式是用来求u(x)?0得单根x?的二阶方法。我们只需说明f(x)?0的m重根x?就是u(x)?0的单根。实际上，利用在根x?附近的Taylor展开，并设x?是

f(x)?0的m重根，有

f(x)1f(m)(?1)???,? u(x)?， 在x与?(x?x)x12之间。

f?(x)mf(m)(?2)?所以，x就是u(x)?0的单根。

14

由该方法可以看出，只要令u(x)?f(x)，则方程f(x)?0的任何重根，都可以f?(x)转化为求u(x)?0得单根，可以利用前面以单根为条件的各种方法，其收敛阶与根的重数无关。

x例1.1 用下列方法求方程(sinx?)2?0的正跟：

2（1）牛顿迭代法（1.14）； （2）修正的牛顿迭代法（2.2）； （3）修正的牛顿迭代法（2.4）。 在三个方法中初值均取x0? x1 x2 x3 x4 x5 ?2，结果如下表所表示

方法（1） 方法（2） 方法（3） 1.78540 1.4456 1.87083 1.88335 1.88946 ...... 1.89548 1.89549 2.00000 1.90100 1.95510 1.89549 1.80175 1.88963 1.89547 1.89549

..... x14 x15 显然，方法（2）和方法（3）确实比方法（1）要收敛的快得多。

2.2 牛顿法在非线性方程求重根的情形下的一些改进方法

因为牛顿迭代法的一些局限性，一直以来，许多数学工作者对牛顿迭代法作出了改进提出了许多有效算法。他们通过几何构造或者多步法的技巧，借助于增加函数，导数的个数或者改变迭代初始值等等各个方面，修正了牛顿法的迭代格式，很大程度上提高了牛顿法迭代收敛阶和收敛速度。下面简单介绍一些牛顿法修正方法 2.2.1 无约束优化技术中的牛顿法

15

牛顿迭代法在重根的情形下只有线性的收敛速，知道重根数的信息或者计算二阶导数都可以解决重根收敛慢的问题，然而这在实际计算中并不方便。因此有学者考虑：将非线性方程求根问题转换为求函数极值得问题，并利用无约束技术中的牛顿法求解。单根情形下雨牛顿法求根等价，重根情形下则得到了一直不需要二阶导数且具有二阶收敛速度的算法。

定理2.1 设x?是f(x)的m(m?1)重零点，则x?是函数

?f2(x) K(x)? （2.5）

f(x??f(x))?f(x)的单重零点，其中??0。

?m?证明 假设f(x)?(x?x)g(x)，其中g(x)?0.

令

S(x)?f(x??f(x))?f(x)， 则

S(x)?(x??f(x)?x?)mg(x??f(x))?(x?x?)mg(x)?[(x?x?)m?m?f(x)(x?x?)m?1?m(m?1)22?f(x)(x?x?)m?2????2??mfm(x)]g(x??f(x))?(x?x?)mg(x)m(m?1)2?(x?x?)3m?2g2(x)????2

?m?(x?x?)2m?1g(x)g(x??f(x))?[2??m(x?x?)mgm(x)]g(x??f(x))?(x?x?)m[g(x??f(x))?g(x)]令

m(m?1)2T(x)?[?x(?x?2

??m(x?x?)mg23m?2)g2x(????)m

m?x(g)]x?(?fx(?)x)?x(gx)??[f(x?g(x))()]由于x?是f(x)的m(m?1)重零点，x?应至少是g(x??f(x))?g(x)的m重零点，因此x应是

?m (x?x)[g(x??f(x))?g(x)]

?的2m重零点，从而T(x)可写成

?2m T(x)?(x?x)H(x)

16

的形式，也就是

(?x?2m)?1gx(gx)??(fx?(x)?)x?(m2Hx) S(x)?m?x由此K(x)可化为

()?(x?x?)g2x() K(x)?

m?(x?x?)2m?1g(x)g(x??f(x))?(x?x?)m2H(x)?????而f(x)?0,g(x)?0，因此g(x??f(x))?0，也就是说x是K(x)单重零点。证

明完毕。

根据定理2.1，为求非线性方程f(x)?0的重根，可以构造形如式（2.5）的

K(x)，利用（1.14）的到迭代格式

xk?1?xk?其中：

M(xk) （2.6） N(xk) M(xk)?f(xk)[f(xk??f(xk))] (2.7)

N(xk)?f?(xk)[2f(xk??f(xk))?f(xk)(1??f?(xk??f(xk)))]?f(xk)f?(xk??f(xk)) (2.8) 当x0充分靠近x时，该迭代格式具有局部二阶收敛速度。 求重根的具体算法为：

输入 初始值x；误差限?；最大迭代次数m及参数?。 输出 近似解或失败信息 步骤1 p0?x0

步骤2 对i?1,2,???,m，作步骤3—4. 步骤3 p?p0?M(p0)，其中M,N形如（2.7），（2.8） N(p0)??步骤4 若p?p0??，则输出，停止，否则p?p0. 步骤5 输出（Method failed )；停止

17

2.2.2 Aitken加速外推下的修正牛顿法求重根重数

当x为重根时，牛顿迭代法线性收敛，如果已知m为根x的重数，则修正牛顿法xk?1?xk?mf(xk)平方收敛，但是根的重数往往是事先未知的，因此如何求?f(xk)??出根的重数成为求出非线性方程重根的一种思路。下面我们给出一种在牛顿迭代法的基础上利用Aitken加速外推给出的一直新的估计根的重数的方法。该方法不用求函数的高阶导数，对于产生的序列只需要简单的四则运算就可以估计根的重数，对于根的较大重数情形也能适用。 在修正的牛顿迭代格式（2.2）的基础上给出 Aitken加速格式： 校正：xk?1?g(xk).

?再校正：xk?1?g(xk?1).

2(x?x)k?1k?1?加速：xk?1?xk?1??. （2.9)

xk?1?2xk?1?xkAitken加速外推格式

设每次迭代飞误差是成比例的减少，即

ek?2ek?1? ek?1ek??设x是非线性方程f(x)?0的精确根，ek?x?xk，则

x??xk?2x??xk?1?? ?

x?xk?1x?xk从上式解出

2xk?xk?2?xk?1 x? （2.10）

xk?2xk?1?xk?2?2?为了减少算术运算，保持数值的稳定性，我们引进的过程 2 ?xk?xk?1?xk,?xk??xk?1??xk.

因此（2.10）即为

18

(?xk)2 x?xk?2 （2.11）

?xk??定理2.2 设非线性方程f(x)?0在其m(m?1)重根x的某个邻域有充分连续导

数。若牛顿迭代格式产生的迭代序列{xk}，则重数 m???xk （x表示对x四舍五入取整）. 2?xk?证明 因为x为非线性方程f(x)?0的m重根，由2.1章节可知牛顿迭代法对m???x??(x),x??(x)，我们有 x重根是收敛的。考虑到k?1k???? x?xk?1??(x)??(xk)???(?)(x?xk) ?介于xk与x之间 （2.12）

x??xk?1???(?)，因为当k??时xk?x?，??x?，所以当式（2.12）可以写作?x?xkk充分大时，我们可以认为

x??xk?11?????(?)??x(?)?1 ? （2.13）

x?xkm从式（2.13）解出

x??xk m? （2.14）

xk?1?xk联立式（2.11）和式（2.14）并消去x，得到 m?证明完毕. 根重数的计算过程

步骤1 给出方程重根的初始近似值 步骤2 牛顿迭代:xk?1?xk?f(xk)，直到连续3次迭代序列{xk}具有单调性； f?(xk)???xk. ?2xk步骤3 取步骤2中连续3次区间单调性的迭代值xk,xk?1,xk?2，计算 ?xk?xk?1?xk,?2xk??xk?1??xk

19

步骤4 代入重数公式m???xk ?2xk2.3 一些其他的求非线性方程重根的方法

针对虚位法在非线性方程求重根时收敛速度太慢，有学者提出了两种改进的虚位法—乘方法和阶乘法在求解非线性方程的重根时可以加快收敛，并且可以方便的在计算机上实现。

1 方法描述 设x?为f(x)的m重根，当x趋近于x?时，f(x)将以x?x?趋近于0.因此采用虚位法时，多是某一端点连续驻留，而另一端点逐步趋近x?，致使收敛趋近不能有效的缩小。Lllinois法和Pegasus法是通过吧连续驻留点的函数值乘以一个缩减因子?来缩小收敛区间的。

乘方法是当某一端点驻留n次时，缩减因子?取某一端点是第一次驻留时，乘方法和阶乘法都是取2 算法描述

（1）非线性方程奇数重根的求解 A 乘方法

输入：初值x1,x2误差限?.

步骤1：计算y1?f(x1)，y2?f(x2)，n?2； 步骤2：计算x?y2?x1?y1?x2；

y2?y1m11，阶乘法则是取。这样当2nn!1，与Lllinois法相当。 2步骤3：如果x?x2?e，输出结果，结束； 步骤4：计算y?f(x)； 步骤5：如果y?y2?0，

则x1?x2,x2?x,y1?y2,y2?y,n?2 否则x2?x,y2?y,??步骤6：返回步骤2。 B. 阶乘法

20

1,y1?y1??,n?n?1； n2

阶乘法的算法基本与乘方法相同，只是?的取值为多次时，它对收敛区间的缩小要比乘方法快。 （2） 非线性方程偶数重根的求解

1。当某一端点连续驻留n!具有偶数重根的非线性方程的求解考虑将偶数重根x?一侧的曲线移动至y轴的负向，然后按求奇数重根的方法进行求解。

A 乘方法

输入：初值x1,x2误差限?.

?,y2?,n?2； 步骤1：计算y1?f(x1),y2?f(x2),y1步骤2：计算x?y2x1?y1x2；

y2?y1步骤3；如果x?x2?e，输出结果，结束； 步骤4；计算y?f(x),y?；

??0， 步骤5；如果y??y2??y2?,y2??y?,n?2 则x1?x2,y1?y2,x2?x,y2?y,y1??y?,?? 否则x2?x,y2?y,y21,y1?y1??,n?n?1； n2步骤6：返回步骤2 B 阶乘法

阶乘法中??1，其余算法同乘方法 n!

21

总 结

非线性方程的解法和理论是当今数值分析研究的重要课题之一，本文简单介绍了一下非线性方程求根的方法，比如二分法，迭代法，阶乘法等。其中迭代法是一种解非线性方程中经常用到方法，也是数值分析中的一种很基本的方法。对其我们介绍了非线性方程的研究背景和意义，以及相关的一些概念和定理。

二分法运用于解非线性方程f(x)?0，方法简单，要求低，收敛有保证，但不能求偶重根和复根.阶乘法收敛速度快，计算量较小。而迭代法则是非线性方程求根中的重要方法之一，一直被专家学者们进行研究探索。本文着重介绍了迭代法的一些相关知识如收敛定理，迭代加速方法，并对迭代法中的经典方法之一牛顿迭代法的几何意义，推导方法，以及牛顿法的一些修正方法如下山法进行了解。然后在此基础上了解了几种非线性方程求重根的方法。

虽然关于非线性方程求重根的的问题，可能由于复杂，繁琐的计算原因等，研究起来十分困难，但是因为这些问题具有的广泛的现实意义，所以国内外的学者并未因为困难而放弃这些问题的探究，一直在不断的提出新的方法，给予了我们极大的信心。

22

参 考 文 献

[1] 傅鹂，龚劬，刘琼荪，何中市.数学实验[M].北京：科学出版社,2000.

[2] 李庆杨，王能超，易大义.数值分析[M].武汉:华中科技大学出版社, 2006. [3] 黄友谦，李岳生. 数值逼近[M].北京: 高等教育出版社, 1987. [4] 冯康，等. 数值计算方法[M].北京：国防工业出版社, 1978.

[5] 周国标，宋宝瑞，谢建利 .数值计算[M]. 北京：高等教育出版社, 2008. [6] 曹志浩. 数值线性代数[M].上海：复旦大学出版社, 1996.

[7] 李庆杨，关治，白峰杉.数值计算原理[M].北京：清华大学出版社, 2001. [8] 孙志忠,等 . 数值分析[M].南京：东南大学出版社, 2002.

[9] Kelly,C.T..Iterative Methods for Linear and Nonlinear Equations[J]. SIAM,Philadelphia,1995.

[10] 苏彤.非线性方程重根解法的探讨[J].工业技术经济，1995（6）：155-156. [11] 周小建.求解非线性方程重根的迭代算法[D].南京师范大学，2013. [12] 蔡慧萍.牛顿迭代法在非线性方程求重根中的应用[J].科技信息：学术版2008（27）.

[13] 王霞，赵玲玲，李飞敏.牛顿方法的两个新格式[J].数学的实践与认识，2007,37（1）：72-76

[14] 张海蒂，曹德欣.求解非线性方程重根的区间牛顿法[J].计算机工程与应用，2012,48（31）：40-42

[15] 李小武.非线性方程Newton型迭代解法与几何迭代算法[D].重庆大学，2011.

23

[16] 袁媛，杨建伟.求解非线性方程重根的二阶迭代法[J].南京信息工程大学学报：自然科学版，2010,2（1）：71-73.

[17] 吴建春，杜永军.一直估计非线性方程重根重数的新方法[J].甘肃科学报，2012,24（2）：12-14

24

本文来源：https://www.bwwdw.com/article/96g7.html