??(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