证法二：由于limxk?x*?1，则ek?xk?1。于是
k??ek?122xk?3(xk?1)2ek ?xk?1?1??1??2xk?42xk?42xk?4ek?111??0。 从而 lim2?limk??k??2x?42ekk2.2.4 迭代法的特点
? 算法逻辑结构简单；
? 在计算时,中间结果若有扰动,仍不会影响计算结果； ? 不同的迭代公式在收敛性、收敛速度上有差别。?
2.3 牛顿（Newton）法
2.3.1牛顿法原理
牛顿法是把非线性方程f(x)?0线性化的一种近似方法。
把f(x)在x0点附近展开成泰勒（Taylor）级数
11f(x)?f(x0)?f?(x0)(x?x0)?f??(x0)(x?x0)2???f(n)(x0)(x?x0)n??取
2!n!其线性部分，当f?(x0)?0时，得到第1次迭代结果，
x1?x0?f(x0)/f?(x0)
若f?(x1)?0，在x1点作线性近似，得到第2次迭代结果
x2?x1?f(x1)/f?(x1)
这样，得到牛顿法的一个迭代序列 xk?1?xk?f(xk)/f?(xk) 2.3.2牛顿法的几何意义
f(x)过点(xk,f(xk))的切线方程为y?f(xn)?f?(xn)(x?xn)，
该切线与x轴的交点是xk?f(xk)/f?(xk)，把它记作xk?1作为下一次迭代点。故牛顿法也叫做切线法。
6
2.3.3牛顿法的计算步骤
步1：选取初值x0及精度;
步2：计算f(x0),f?(x0)，令x1?x0?f(x0)/f?(x0)；
x?x0??，步3：若x1?x0??或1令x*?x1，计算结束；否则，令x0?x1,x1转第2步。
例5 p23，参[1] p20例2-8，2-9，2-10 2.3.4牛顿法的收敛性及收敛速度
定理2-5 牛顿迭代法平方局部收敛定理 设x*是方程f(x)?0的单根，且
f(x)在x*的某邻域有二阶连续导数，则牛顿法在x*附近局部收敛，且至少是
二阶收敛，有
limk??ek?1ek2?limk??x*?xk?1x?xk*2?f??(x*)2f?(x)* （参[6]p61）
问题与思考：
1．牛顿法的收敛性与初值x0的选取是否有关系？ 有 2．当有重根即f(x*)=0时，牛顿法仍收敛吗？ 是 3．当x*是方程f(x)?0的m重根时，是否仍平方收敛？
线性收敛，且limk??xk?1?x*xk?x*?m?1 m4．收敛速度与得光滑性有关系吗？ 有 例6 p23
定理2-6 收敛充分条件 若f(x)在区间[a,b]上满足： （1）f(a)?f(b)?0； 有根 （2）f?(x)?0； 唯一根 （3）f??(x)不变号； {xk}单调有界 （4）选取初值x0?[a,b]，使f(x0)f??(x0)?0， 自身映射 则牛顿法产生的迭代序列单调收敛于方程f(x)?0在该区间上的惟一解。
例 用牛顿迭代法推导求a(a?0)的迭代公式，并求收敛的阶。
7
解 方法一：设f(x)?x2?a，则有xk?1?此时，??(x)?1a(xk?)。 2xk1aa1(1?2)，???(x)?3，??(a)?0，???(a)??0， 2x4x4a故该迭代公式为二阶收敛迭代公式。
2xka1方法二：设f(x)?1?2，则有xk?1?xk(3?)。
x2a3x33x23此时，??(x)??，???(x)??，??(a)?0，???(a)???0，由于
a22aa6af??(x)??4，故取x0?(0,a)时，迭代公式二阶收敛。
x3a方法三：设f(x)?(x2?a)2，则有xk?1?xk?，此时
44xk3a1?2，由于?(a)?a，而0???(a)??1， 44x2故该迭代公式仅为线性收敛迭代公式。
??(x)?2.3.5牛顿法的特点及牛顿下山法
牛顿法有以下特点：
? 收敛速度快，达到平方收敛；
? 计算量较大，对函数f(x)解析性质要求较高。
? 具有局部收敛性，即当初值x0与x*太远时，收敛速度很慢，甚至不收敛，仅在x*附近可达到平方收敛；
将牛顿迭代公式修改为以下形式
f(xk) xk?1?xk??
f?(xk)111其中参数??(0,1)称为下山因子。用试算的方法选取?(1,,2,3,?)，使得
222f(xk?1)?f(xk)
称满足上述要求的算法为牛顿下山法。
2.4 弦位法
2.4.1 弦位法的思想
弦位法又称弦截法或割线法。是用差商代替牛顿公式中的微商f?(xk)；或者说是用f(x)在点(xk?1,f(xk?1))和(xk,f(xk))处的割线的零点作为新的迭代点
8
xk?1?xk?2.4.2 弦位法的几何意义 略
2.4.3 弦位法的计算步骤 略
2.4.4 弦位法的收敛性及收敛速度
f(xk)(xk?xk?1)
f(xk)?f(xk?1)定理2-7 设x*是方程f(x)?0的单根，且f(x)在x*的某邻域有二阶连续导数，则?x0,x1?N(x*,?)，弦位法在x*附近局部收敛，且按阶1.618收敛到x*。 2.4.4 弦位法的特点
? 收敛速度夹较快，但比牛顿法慢； ? 超线性收敛，收敛阶为1.618；
? 无需计算导数，每步只需计算一次函数值；
? 属于多点迭代，而牛顿法和一般迭代法属于单点迭代。
2.5 迭代法的改善与加速
2.5.1 一般的加速算法
加速算法思想是先求xk?1??(xk)，然后选取合适的数m和n，令 xk?1?mxk?1?nxk 作为下一次迭代点。
为选取合适的线性组合系数m,n。由于?(x)连续，且x*??(x*)，从而 x*?xk?1??(x*)??(xk)???(?)(x*?xk) 用a近似代替上式中的??(?)，立即有 x*?xk?1?a(x*?xk) 整理得
1axk?1?xk 1?a1?a从而得到加速迭代公式
1axk?1??(xk)?xk
1?a1?a x*?2.5.2 埃特金（Aithen）加速算法
埃特金算法的思想是将一般迭代法和弦位法相结合来实现加速迭代算法的收敛速度的。
9
为构造埃特金法加速迭代公式，设xk是x??(x)的一个近似解，首先令
?k?1??(xk) xk?1??(xk)，x?(x然后在曲线y??(x)上，过点P(x,x)和Pkk?1k?1?k?1)做连线，该直线的两点,x式方程为
?k?1?xk?1y?xk?1x ?xk?1?xkx?xk最后考虑到方程x??(x)的解是曲线y??(x)和直线y?x的交点P*的横坐标，
?与直线y?x的交点P代替P*,即用点P的横坐标作为x??(x)的可用弦PPk?1k?1一个近似解，其值可通过将上式中的y用x代替并解出x得到
?k?1?xk2?1xkx x??k?1xk?2xk?1?x用上式进一步可以构造出两种具有加速收敛的迭代公式
?k?1?2xk2?1?k?1?xk)2xkx(x?k?1? xk?1??x?k?1?k?1xk?2xk?1?xxk?2xk?1?x称上式为埃特金算法的迭代公式；
xk?1?k?1?2xk2?1xkx(xk?1?xk)2 ??xk???xk?2xk?1?xk?1xk?2xk?1?xk?1称上式为Steffensen（斯姬芬森）外推迭代公式。实质上，若令
?(x)?x???(x)?x?2?(?(x))?2?(x)?x，则xk?1??(xk)k?0,1,2,?称为Steffensen迭代公式。
2.5.3 埃特金算法的几何意义 略 p25图2-7 2.5.4 埃特金算法的计算步骤
3 略 例8p25，原本发散的迭代公式xk?1?xk?1 用埃特金算法是收敛的。
2.5.4 加速算法的收敛性
设x*是x??(x)的精确解，由迭代法收敛性定理知：若??(x*)在x*的某个邻域上连续，若0???(x*)?1，则迭代算法xk?1??(xk)局部收敛；若??(x*)?1，则迭代算法可能收敛，也可能不收敛；若??(x*)?1，则迭代算法肯定不收敛。但经过改进后的Aitken算法超线性收敛，Steffensen（斯基芬森）外推算法若
????(x)在x*处连续，且??(x*)?1，则算法至少有二次收敛性。
定理2-8 Steffensen迭代法收敛定理 设函数?(x)按上式定义的迭代函数：
10