§4.1 引 言绪论中讲到方程求根得二分法，但二分法收敛速度慢，有必要掌握新的方法。

§4.1.1迭代法的思想迭代法是一种逐次逼近法，使用某个固定公式（迭代公式）反复校正，逐步精确，直到满足精度。

迭代法求根分两步： 1） 猜测初值 2）迭代如求解初值问题00')(),,(y x y y x f y ==用梯形公式111[(,)(,)2n n n n n n h y y f x y f x y +++≈++ （1）看作关于1+n y 的函数方程，按欧拉公式提供猜测值),()0(1n n n n y x hf y y +=+，代入（1）得)],(),([2)0(11)1(1+++++=n n n n n n y x f y x f h y y若)1(1+n y 仍不满足要求，则将它代入（1）式，继续得到校正值)2(1+n y ，写成迭代公式)],(),([2)(11)1(1k n n n n n k n y x f y x f h y y ++++++= （2）一般地，为了求一元非线性方程0)(=x f 的根，可以先将其转换为如下的等价形式()x x ϕ= （3）式（3）中连续函数()x ϕ称为迭代函数，其右端含未知数，不能直接求解。

先用根的某个猜测值0x 代入（3），构造迭代公式：()k k x x ϕ=+1。

如果迭代值k x 有极限，则称迭代收敛，极限值k k x x ∞→=lim *就是方程（3）的根。

几何意义P127图4-1为使迭代法有效，必须保证它的收敛行，()x ϕ满足什么条件，才能保证收敛？以最简单的线性迭代()d kx x +=ϕ，可以看出收敛的充分必要条件()1'<=k x ϕ。

几何意义P127图4-2,3,4,5。

§4.1.3 压缩映像原理设*x 是方程()x x ϕ=的根，则由微分中值定理))(()()(*'*1*k k k x xx x x x-=-=-+εϕϕϕ，如果存在10<≤L ，使得],[b a x ∈有()k k x x L x x L x -≤-⇒≤+*1*'ϕ，则迭代误差0e L e kk ≤，由于10<≤L ，故0→k e ，即迭代收敛。

需注意，上述过程中需保证一切迭代值k x 全落在],[b a ，为此要求对任意],[b a x ∈，总有],[)(b a x ∈ϕ。

综上，压缩映像原理：定理 1 设()x ϕ在],[b a 上具有连续的一阶导数，满足条件： （1）对任意],[b a x ∈，总有],[)(b a x ∈ϕ。

映内性（2）存在10<≤L ，使得对于任意],[b a x ∈成立()L x ≤'ϕ。

压缩性则迭代过程()k k x x ϕ=+1对于任意初值],[0b a x ∈均收敛于方程()x x ϕ=的根*x ，且有下列误差估计式：)8(1)7(1101*1*x x LLx x x x L x x kk k k k --≤---≤-+证明：由k k x x L x x -≤-+*1*有k k k k k k x x L x x x x x x x x ---≥---≥-++**1**1从而有k k k x xL x x --≥-+*1)1(，（7）式得证()111')()(--+-≤-=-⇒≤k k k k k k x x L x x x x L x ϕϕϕ011x x L x x k k k -≤-+，结合（7）式得01*1x x LLx x kk --≤-由（7）式知只要1,+k k x x 的偏差足够小，就能保证迭代值1+k x 足够准确，可用kk x x -+1来控制迭代过程是否结束。

流程图见P128图4－6。

例1 P130 P142题3，5，6，7注意迭代函数的选择，同一方程，可以采用不同的迭代函数，但迭代函数可能不收敛，或收敛缓慢，迭代函数的选择非常重要。

§4.1.3 迭代过程的局部收敛性在方程求根的迭代法中，迭代函数()x x ϕ=的确定，至关重要，它直接影响着迭代法的收敛性。

但在实际应用中，同一个方程可以等价导出不同的迭代函数，而且要严格地利用定理1的条件判断迭代公式在整个区间],[b a 内收敛（全局收敛）也非常困难，因此常常判断迭代公式的局部收敛性。

通常在根*x 的邻近考察。

如果存在邻域δ≤-∆*:xx ，使得迭代过程对于任意初值∆∈0x 均收敛，这种收敛性称为局部收敛性。

定理 2 设()x ϕ在()x x ϕ=的根*x 邻近有一阶导数，且成立()1*'<xϕ，则迭代过程()k k x x ϕ=+1在*x 邻近具有局部收敛性。

证：存在充分小邻域δ≤-∆*:x x ，使()1'<≤L x ϕ，L 为某个定数，根据微分中值定理：))(()()(*'*x x x x -=-εϕϕϕ，注意到()**xx ϕ=，又当∆∈x 时∆∈ε，故有δϕ≤-≤-≤-x x x x L xx ***)(，即),()(*δϕx x ∆∈由定理1知()k k x x ϕ=+1对于任意∆∈0x 均收敛。

例2 P131§4.1.4 收敛速度迭代误差*x x e k k -=，当∞→k 时C ee pkk →+1，称迭代过程为P 阶收敛的，P ＝1称线性收敛，P ＝2称为平方收敛。

对于在根*x 邻近收敛的迭代公式()k k x x ϕ=+1，由于))((*'1*k k x x x x -=-+εϕ，式中ε介于k x 和*x 之间，故有∞→→+k x e e kk ),(*'1ϕ，若0)(*'≠x ϕ，则为线性收敛。

若0)(*'=x ϕ，将()k x ϕ在*x 处进行泰勒展开有：()2*''*)(2)()(x x x x k k -+=εϕϕϕ，又()k k x x ϕ=+1，()**xx ϕ=，由上式知∞→→+k x e e kk ,2)(*''21ϕ，表明当0)(*'=x ϕ，0)(*''≠x ϕ时平方收敛。

故有下述论断：定理 3 设()x ϕ在()x x ϕ=在根*x 的邻近有连续的二阶导数，且()1'<x ϕ，则0)(*'≠x ϕ时线性收敛；当0)(*'=x ϕ，0)(*''≠x ϕ时平方收敛。

例 P146题3§4.2 迭代过程的加速§4.2.1 迭代公式的加工迭代过程收敛缓慢，计算量将很大，需要进行加速。

设k x 是根*x 的某个近似值，用迭代公式校正一次得()k k x x ϕ=+1，假设)('x ϕ在所考察得范围内变化不大，其估计值为L ，则有：k k k k x L Lx L x x x L x x ---≈⇒-≈-++111)(1**1*有迭代公式k k k x LL x Lx ---=++11111，是比1+k x 更好的近似根。

这样加工后的计算过程为：迭代()k k x x ϕ=+1 改进k k k x LLx L x ---=++11111合并的])([111k k k Lx x Lx --=+ϕ 例3 P133 §4.2.1 埃特金算法上述加速方法含有导数()x 'ϕ，不便于计算。

设将迭代值()k k x x ϕ=+1再迭代一次，又得()11~++=k k x x ϕ，由于)(~1*1*++-≈-k k x x L x x又)(*1*k k x x L x x -≈-+，消去L 得kk k k k k k k k k x x x x x x x x x x x x x x x +---≈⇒--≈--++++++++112111*1**1*1*2~)~(~~ 计算过程如下： 迭代()k k x x ϕ=+1 迭代()11~++=k k x x ϕ 改进kk k k k k k x x x x x x x +---=++++++11211112~)~(~§4.3 牛顿法§4.3.1 公式的导出对于方程0)(=x f ，设已知它的近似根k x ，函数)(x f 在k x 处可用一阶泰勒展开来近似))(()()('k k k x x x f x f x p -+=，取0)(=x p 的根作为0)(=x f 的新的近似根，记作1+k x ，则：)()('1k k k k x f x f x x -=+，这就是牛顿公式，相应的迭代函数是)()()('x f x f x x -=ϕ牛顿法是一种逐步线性化方法，将非线性方程0)(=x f 的求根问题归结为计算一系列0))(()('=-+k k k x x x f x f 的根。

牛顿法几何意义是：(牛顿法亦称切线法，直线经过))(,(k k x f x 、)0,(1+k x ) ，流程图P136 图4－9例5： P137牛顿法收敛很快。

其迭代公式2''''')]([)()()()()()(x f x f x f x x f x f x x =⇒-=ϕϕ假定*x 是0)(=x f 的单根，即0)(*=x f ，0)(*'≠x f ，则由上式知0)(*'=x ϕ。

故牛顿法至少平方收敛定理4 牛顿法在0)(=x f 的单根*x 附近为平方收敛。

(局部收敛)证：1）由2'''')]([)()()(x f x f x f x =ϕ知10)(*'<=x ϕ，故其局部收敛。

2）2*'*'*)(2)())(()()(k k k k x x f x x x f x f x f -+-+=ε1'''1)()()()()(++-=-⇒-=k k k k k k k k k x x f x x f x f x f x f x x代入得2*'1*'*)(2)())(()(0k k k x x f x x x f x f -+-==+ε由上式得)(2)(lim*'*''21x f x f e e kk k →+∞→，故单根时平方收敛。

但当*x 是0)(=x f 的重根时，牛顿法线性收敛。

因)()()(*x g x x x f m-=，其中)(x g 有二阶导数，且0)(*'≠x g)()()()()()()()()()()()()()('**'*1**'x g x x x mg x g x x x x g x x x g x x m x g x x x x f x f x x m m m-+--=-+---=-=-ϕ2'*2''2*'*'])()()(1[)()()()()(2)()11()(x mg x g x x x g m x g x x x mg x g x x mx -+-+-+-=ϕ故)11()(*'mx -=ϕ，当m>1时0)(*'≠x ϕ，且有1)(*'<x ϕ，故线性收敛。