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