第二章 方程求根
教学内容：
1．二分法 2．基本迭代法 3．牛顿法 4．弦位法
5．埃特金法和斯基芬森法 6．重根的情况
教学重点：
各种算法的思路及迭代公式的构造
教学难点：
各种算法的收敛性、收敛速度及误差估计
计划学时：5-6学时 授课提纲：
方程求根就是求函数f(x)的零点x*，即求解方程 f(x)?0
这里，f(x)?0可以是代数方程，也可以不是，如超越方程。
方程的根既可以是实数，也可以是复数；既可能是单根，也可能是重根；即可能要求求出给定范围内的某个根，也可能要求求出方程全部的根。
本章介绍的方法对两类方程都适用，但大部分都是要求知道根在什么范围内，且在此范围内只有一个单根。若有?使得f(?)?0,f?(?)?0，则称?是方程f(x)?0的单根；若有?使得
f(?)?f?(?)???f(m?1)(?)?0,f(m)(?)?0，
则称?是方程f(x)?0的m重根。
设f(x)在区间[a,b]连续，若f(a)f(b)?0，则f(x)在区间（a,b）内至少有一个实根，若再有f?(x)不变号，则有根区间（a,b）内仅有一个实根。除特别声明，本章介绍的算法都是求单实根。
2.1 二分法
二分法又称区间对分法，是最直观、最简单的一种方法。 2.1.1 二分法原理
若 f (x)在[a, b]内单调连续，且f(a) f(b)<0，则f在(a, b)内必有惟一的实根。
1
2.1.2 二分法思想
区间对分，去同存异 2.1.3 二分法计算步骤
步1：令x0?(a?b)/2，计算f(x0)； 步2：若f(x0)?0，令x*?x0，计算结束； 步3：若f(x0)*f(a)>0，令a?x0；否则令b?x0；
步4：若|b?a|??，令x*?(a?b)/2,计算结束；否则转步1。 2.1.4 二分法误差分析和收敛性
记第k次区间中点为xk，则有
x*?x0?(b?a)/2，x*?x1?(b?a)/22，?,x*?xk?(b?a)/2k?1
故当k??时，xk?x*。
为使x*?xk??，解不等式(b?a)/2k?1??，得
k?[ln(b?a)?ln?]/ln2?1
2.1.5 二分法的优缺点
? 算法简单直观，易编程计算； ? 只需f(x)连续即可；
? 区间收缩速率相同，收敛速度慢；
? 无法求复根和偶重根。 例2-1 p15例1
2.2 迭代法
2.2.1 迭代法原理
f(x)?0 ? x??(x) f(x)的根 ?(x)的不动点
2.2.2 迭代法思路
任取初值x0?[a,b]，令x1??(x0)，x2??(x1)，反复迭代，即得
xk?1??(xk),(k?0,1,2,?)
直到满足精度要求的xk来近似x*。称x??(x)为迭代公式，?(x)为迭代函数，{xk}为迭代序列。
若{xk}收敛时，称迭代公式是收敛的。此时设limxk?x*，当?(x)连续时
k??x*?limxk?1?lim?(xk)??(lim)??(x*)
k??k??k??亦即f(x*)?0。若{xk}不收敛，称迭代公式是发散的。
2
2.2.3 迭代法的计算步骤
步1：选取初值x0及精度?，置k=0; 步2：计算xk?1??(xk)；
步3：若xk?1?xk??，令x*?xk?1，计算结束；令k=k+1,转第2步。 2.2.4 迭代法的几何意义及收敛性条件
迭代法的几何意义是求曲线y?x和y??(x)交点的横坐标x*。
x1 x0 x* p1 x x0 x* p0 x0 y x1 x* y = x x x0 y y=?(x) p0 x* x1 y = x x p0 y p1 y = x y=?(x) y p0 y = x ? ? p1 y=?(x) y=?(x) ? ? p1 x x1 可以看出，若?(x)的变化幅度小于x的变化幅度时，迭代公式收敛，否则，迭代公式不收敛。
迭代序列的收敛性依赖于构造的迭代函数（不唯一）。
例2-2 求方程f(x)?x5?2x?1在（1，2）内的根。分别构造迭代函数
1 ?1(x)?52x?1 ?2(x)?(x5?1)
2定理2-1 迭代收敛基本定理 设迭代函数?(x)在[a,b]内连续，在(a,b)内可导，且满足
（1）映内性：当x?[a,b]时，有?(x)?[a,b]； （2）压缩性：?0?L?1，?x?[a,b]，有??(x)?L；
3
则
① 函数?(x)在[a,b]内存在惟一的不动点x*；
② ?x0?[a,b]，迭代公式xk?1??(xk)产生的序列{xk}?k?1?[a,b]，且
xk?x* limk??③ 有如下误差估计 1xk?1?xk x*?xk?1?LLkx1?x0 x?xk?1?L*(k?1,2,?)
(k?1,2,?)；
x*?xk?1 ④ lim*???(x*)
k??x?xk说明：(i) 常用xk?1?xk来控制是收敛精度，L越小，收敛越快。
(ii) 条件?0?L?1，?x?[a,b]，有??(x)?L太强，但是好验证，可以
改为较弱的条件：
?x1,x2?[a,b],?(x1)??(x2)?Lx1?x2,其中L是与x1,x2无关的常数（Lipschitz常数），且0?L?1。
（ⅲ）定理的条件是迭代公式收敛的充分条件，非充要条件。
p19例3。
定义2-1 如果存在x*的某个邻域N(x*,?)，使迭代过程xk?1??(xk)对任意的初值x0?N(x*,?)均收敛，则称该迭代过程在根x*邻近具有局部收敛性。
定理2-2 局部收敛性定理 设x*是x??(x)的不动点，??(x)在x*的某个邻域N(x*,?)内连续且??(x)?L?1，则迭代公式xk?1??(xk)对任意的初值
x0?N(x*,?)局部收敛。
定理2-3 设x*是x??(x)的不动点，??(x)在x*附近连续，若存在x*的某个邻域N(x*,?)，?x?N(x*,?)，都有??(x)?1，则迭代公式不对任意的初值
x0?N(x*,?)收敛，称为发散。见p19定理3。
定理2-4 对于迭代公式xk?1??(xk)，如果?(p)(x)在x*附近连续，且有
??(x*)????(x*)????(p?1)(x*)?0,?(p)(x*)?0
则该迭代公式在x*附近是p阶收敛的。见p20定理4。
4
证明：由??(x*)?0及定理2-2知，迭代过程xk?1??(xk)在x*的附近具有局部收敛性。再将?(xk)在x*处做泰勒展开，则有
?(p)(?)* ?(xk)??(x)?(xk?x*)p （?介于xk和x*之间）
p!注意到xk?1??(xk)及x??(x)，从而有xk?1?xk?**?(p)(?)p!(xk?x*)p
xk?1?x*?(x*)ek?1*x故 limp?lim，迭代公式在附近是p阶收敛的。 ?k??ek??*pp!kxk?x迭代法的收敛阶是对迭代法收敛速度的一种度量。 例4（见p20）
例 设a,x0?0，证明迭代公式xk?1并计算limk??2xk(xk?3a)是计算a的3阶方法，?23xk?aa?xk?1(a?xk)3。
证明 显然当a,x0?0，xk?0(k?1,2,?)， 令?(x)?x(x2?3a)3x?a2，则??(x)???3(x2?a)2(3x?a)22。
则?x?0，可使??(x)?1，即迭代收敛。设xk?x*，则有 x?*x(x*?3a)3x*?a22，解之得x*?0,a,?a，取x*?a。则
3xk?3axka?23xk?alimk??a?xk?1(a?xk)3=limk??(a?xk)3=lim11= 32k??3x2?ak??4a(a?xk)(3xk?a)k(a?xk)3=lim故迭代是3阶收敛。
例 已知迭代公式xk?1明该迭代公式平方收敛。
x2?3x2?4x?3证法一：迭代函数?(x)?，经计算??(x)?，??(x*)?0， 22x?42(x?2)2xk?3x2?3局部收敛于方程x?的根x*?1，证?2x?42xk?4???(x)?
1，而???(x*)?0，有定理2-4知，迭代公式平方收敛。 3(x?2)5