不动点迭代法的全局收敛性.pptx

《不动点迭代法的全局收敛性.pptx》由会员分享，可在线阅读，更多相关《不动点迭代法的全局收敛性.pptx（69页珍藏版）》请在沃文网上搜索。

1、第二章 非线性方程求根 2.1概述 2.2二分法（对分法）2.3 2.4 2.51不动点迭代的基本理论 Newton法 Newton法的变形 2.1 简介一、问题2求解非线性方程 如多项式方程：f(x)=0！p(x)a xn axn1 a x a 0nnn11 0困难：方程的解难以用公式表达。需要一定精度的近似解！二、概念方程 f x 0 的解 x*称为方程 f x 0 的根或称为 f x 的零点。若其中m为正整数，gx满足 gx 0，则显然f x x x*m gxf x*0这时称 x*为 f x 的m重零点，或称 x*为 f x 0的m重根。定理：若 f x 有m阶连续导数，则 x*是 f

2、x的m重零点的充要条件为：f(x*)f(x*)f(m1)(x*)0,f(m)(x*)03概念（续）证证明明 ：必要性设 x*是 f x 的m重零点，则f(x)(x x*)m g(x)且 gx*0c (x x )g(x)kiki0*m(k i)f(x)(i)(k)ck m(m 1)(m ii0当 0 k m 1 时k*mi(mi)1)(x x)kig(x)*(mi)*mi*(k)*ii0当 k m 时m x)g(x)0c m(m 1)(m i 1)(xf(x)kg(x )2013/9/304c m(m 1)(m i 1)(x x )f(x )i0*mi(mi)*i*(k)*m m!g(x*)0概

3、念（续）充分性：设 x*使得 f x*0，f(x*)0,f(1)(x*)0,f()(x*)0由Taylor公式得f(x)f(x*)f(x*)(x x*)(x x*)mf m(x*(x x*)(x x*)m1 f(m1)(x*)m!(m 1)!(x x*)则有 1。令g(x)1 f(m)(x*0 m!g(x*)f(x)(x x*)m g(x)且f(m)(x*)0m!1其中根据定义 x*为f(x)的m重零点。证毕2013/9/305三、根的隔离方程可能有多个实根，我们只能逐个求出来。定义：设在区间a,b上方程有一个根，则称该区间 为方程的一个有根区间。若在区间a,b上方程只有 一个根，则称把方程的

4、根隔离出来了。Remark：若能把有根区间不断缩小，则可以得出 根的近似值。基于函数f(x)的连续性质，常用的根的隔离的方法 有：函数作图法与试算法。要找出方程的所有的根，要进行“根的搜索”。2013/9/306 2.2 二分法（对分法）一、算法设 f(x)在a,b上连续，f(a)f(b)0且在a,b内f(x)=0 仅有一个实根 x*。二分法的基本思想是：逐步将 有根区间分半，通过判别函数值的符号，进一步 搜索有根区间，将有根区间缩小到充分小，从而 求出满足给定精度的根 x*的近似值。具体算法：记a,b为a1,b1。将区间a1,b1分半，计算中点x 1(a b)*2111f(x1)以及函数值。

5、x x12013/9/307若 f(x1)0则。二分法（对分法）（续）a a1,b2 x12否则，若有，则，令x a,x 11*f(x1)f(a1)0或 f(x1)f(b1)0，则，令,b 11x*x2121a x,b bb a 1(b a)1(b a)再计算a,b 中点x的函数值 f(x)。a2 b22221122新的有根区间a2,b2 的长度2222若则2。否则则，x*xf(x)02f(x2)f(a2)0 x*a,x 22令 a3 x2,b3 b2。令 a3 a2,b3 x2，或 f(x2)f(b2)0 则22，,b x*x新的有根区间 a3,b3 的长度 b3 a3 (b2 a2)2 (

6、b a)21122013/9/308二分法（对分法）（续）如此对分下去则得到一系列的有根区间a1,b1 a2,b2 ak,bk a)1 (b a)2k 1且 b a 1(b2k 1k 1kk 1(b a)1 (b a),k 1,2,2k2x x*kkk由 xk及ak bk2当对分过程无限继续下去，则有根区间必收敛到一点，即2013/9/309lim xk x*k 二分法（对分法）（续）二、误差估计定理：给定方程 f(x)=0，设 f(x)在区间a,b上 连续，且f(a)f(b)0，则由二分法产生的序列xk收敛于方程的根x*，且具有误差估计(k 1,2,)2013/9/3010 1 (b a)2

7、kx x*k二分法（对分法）（续）三、收敛准则1.事先误差估计：(b a)x x*2k1k利用误差估计定理，令得k ln(b a)ln ln 2从而得到对分次数k，取xk作为根得近似值x*。2.事后误差估计：给定，每步检查 xk xk 1(b a)2k，或1f(xk)Remark：二分法的优点是方法及相应的程序均简单，且对f(x)性质要求不高，只要连续即可。但二分法不 能用于求复数根和偶数重根。若成立，则取 x xk，否则继续对分。*2013/9/3011 2.3 不动点迭代的基本理论一、不一、不动动点迭代点迭代令方程 f(x)0,将其变成一个等价的方程 x (x),构造 xk 1 (xk),

8、k 0,1,xk 称为迭代序列，(x)称为迭代函数,(xk)称为迭代格式或迭代过程（迭代式），xk 1 lim(xk)(lim xk)且当(x)连续时，有 lim xk1k k k (x*)或 f(x*)0即序列xk 的极限 x*为 f(x)0的根。2013/9/3012。即 x*不不动动点迭代（点迭代（续续）由于 f(x)0 的根 x*满足 x*(x*)，反之亦然。也称 x*为(x)的不动点。即映射关系 将x*映射 到 x*本身。求 f(x)的零点就等价转化为求 的不动点。也称 xk 1 (xk),k 0,1,为不动点迭代法（也称简 单迭代法或逐次逼近法）。Remark：可以通过不同的途径将

9、f(x)=0化为 x (x)的形式。问题：如何选取合适的迭代函数？(x)迭代函数(x)应满足什么条件，序列xk收敛？怎样加速序列xk的收敛？2013/9/3013二、不二、不动动点迭代法的全局收点迭代法的全局收敛敛性性定理（全局收敛定理）已知 x (x)，(x)满足1.存在常数0L1,使对任意 x(a,b)有(x)L，且(x)Ca,b C(a,b)2.对任意 则则x a,b,有a (x)b1.x (x)在a,b上有唯一的不动点 x*xx0 (a,b),xk 1 (xk),k 0,1,2产生的序列x k2.对任意必收敛到的不动点。(x*)2013/9/3014*,x x*x x*x x L L

10、x xkk3.xk 有误差估计x x,lim1 L1 Lx*k 110k 1k xkkk不不动动点迭代法的一般理点迭代法的一般理论论（续续）证证明：明：1.由于(x)在a,b 上连续，作辅助函数(x)(x)x,则(x)Ca,b且，(a)(a)a 0,(b)(b)b 0故由连续函数的介值定理，至少存在x*a,b使(x*)0,即(x*)x*即存在的不动点 x*又由 L 1(x)(x)1 L 1 0知 (x)单调。故存在唯一的x*，使得 (x*)0，即(x)在a,b上有唯一的不动点。2013/9/3015不不动动点迭代法的一般理点迭代法的一般理论论（续续）2.因 L x x*k 1(x)(x*)()

11、x x*k 1k 1x x*k介于x与x*之间，故有k 1其中 L x x*Lk x x*,k 1,2x x*0k 1k因L 1,lim xk x*0,即即 lim xk x*,x0 a,b。k k 2013/9/3016不不动动点迭代法的一般理点迭代法的一般理论论（续续）3.由(xk)(xk1)()(xk xk1)xk 1 xk L xk xk 1,(xk 1,xk)(a,b),k 1,2,x x*L x x*xk 1 x*k 1xk 1 xkx )x x(x x )(xkk由结论2有k 1k x x*(1 L)x x*x x x x*故k 1k 1kkk即x x*1 xx L x xkk

12、1k 11 L1 Lkk2x x*x L x x L xk102013/9/3017k 2k 11 L1 Lk不不动动点迭代法的一般理点迭代法的一般理论论（续续）由)(x x*)(x*)(x x*(xk 1k 1k 1kx x*知 (k 1)x x*k对上式两端取极限，并注意到k 1*lim k 1 xk 故(x*)limxk xx*k x证毕2013/9/3018k 1不不动动点迭代法的一般理点迭代法的一般理论论（续续）Remark1：若(x)为定义在区间a,b上的函数，且x a,b，均有(x)a,b，则称(x)为区间a,b自 身上的一个映射。若(x)为区间a,b自身上的一个映射，且0 L

13、1,x1,x2 a,b(x1)(x2)L x1 x2则称(x)为区间a,b上的一个压缩映射，L为Lipschitz常 数。关于压缩映射有如下结论：（1）若(x)为区间a,b上的压缩映射，则称(x)必为区 间a,b上的连续函数。（2）若(x)为区间a,b自身上的映射，(x)Ca,b且(x)L 1，则(x)必是区间a,b上的一个压缩映射。2013/9/3019不不动动点迭代法的一般理点迭代法的一般理论论（续续）Remark2：不动点定理还可以叙述为：若(x)为定义 在区间a,b上的压缩映射，则(x)在区间a,b上存在 唯一的不动点。Remark3：不动点定理的两个误差估计式实际上给出 了迭代收敛的

14、两个准则：事后误差估计与事先误差估 计（利用估计式预先求出迭代次数k）。Remark4：由不动点定理知，若L1，则xk必然收敛 较慢；若L1，则收敛速度快。Remark5：不动点定理给出的是区间a,b上的收敛性，称之为全局收敛性。（判定困难）2013/9/3020不不动动点迭代法的一般理点迭代法的一般理论论（续续）Remark6：设函数(x)在区间a,b内有不动点x*，且当xa,b时，(x)1，则对任意初值x0 a,b，且x0 x*，迭代格式 xk 1 (xk)，k=0,1,2,发散证明 由x0 a,b，且x0 x*，知如果x1 a,b，则有(x)(x*)()(x x*)x x*00000 x

15、 x*1 x x*0 x x*(x)(x*)()(x x*)x x*211110如此继续下去，或者xka,b，或者 xk x因而迭代序列不可能收敛于x*，即迭代格式发散2013/9/3021 x0 x 0*三、局部收三、局部收敛敛性及收性及收敛阶敛阶1.局部收局部收敛敛性性（1）定定义义：若存在 的不动点 x*的闭邻域N(x*)x*,x*(0)使对任意(x),k 0,1,2,产生的迭x N(x*),迭代x0k 1k代序列xk 均收敛于 x*，则称求 x*的迭代法在 附近局部收敛。xk 1 (xk),k 0,1,2,（2）局部收局部收敛敛性的判性的判别别*x定理2.设 x*为的不动点，(x)在

16、x*的(x)某个邻域连续，且(x)L 1，则迭代式收敛。2013/9/3022局部收局部收敛敛性及收性及收敛阶敛阶（续续）因(x)连续，故存在 N(x*)x*(0),x*证证明：明：使得(x)L 1，x N(x*)，即对一切 x N(x*)故(x)x*(x)(x*)L x x*有 x*(x)x*。将前述定理1中的a,b取为x*,x*则对任意*)迭代法收敛。x N(x0Remark1：可以证明，若在根 x*证毕 的邻域中(x)1，则可以以邻域内任何一点 x0 为初始值，用迭代过程产生 的序列就一定不会收敛于 x*。事实上，x*)x x*x x*k 1 02013/9/3023kk 1k 1x x

17、*)(x*)()(x (xRemark2：当 x0 不取在 x*的邻域为内时可能不收敛。局部收局部收敛敛性及收性及收敛阶敛阶（续续）2.收收敛阶敛阶收敛速度是接近收敛的过程中迭代误差的下降速度。（1）p阶收敛的定义设 x（x）收敛于 x (x)的根x*，令迭代误差e x x*，如果存在实数 p 1 及非零正常数C使得k 1kkklim k 1 Ceepk（称为渐近误差常数）k2013/9/3024则称该迭代过程以及该迭代式是p阶收敛的。若0C1称为超线性收敛；p2称为平方收敛（二次收敛）。p 越大，收敛速 度越快；反之，p越小，收敛速度就越慢。局部收局部收敛敛性及收性及收敛阶敛阶（续续）（2）

18、收敛速度的判别设迭代法 xk 1满足全局收敛或局部收敛的（xk条件，则。lim x x*kk 再设在a,b或x*的邻域中，(x)0。若取 x x*，必有x x*,(k 1,2,)k0从而有kkek 1 xk 1 x)e(x)(x)(*其中介于xk与x*之间。当时，由(x)的连续性得，lim ek 1k (x*)0k ek故这种情况下迭代是线性收敛的。这启发我们，要得到超收敛的方法，迭代式必须满足(x*)0 。2013/9/3025局部收局部收敛敛性及收性及收敛阶敛阶（续续）定理：迭代式 xk 1 (xk),(k 0,1,)的迭代函数的高阶导数(（p)p1）在不动点 x*的邻域里连续，则迭代式为

19、p阶收敛的充要条件是(x*)x*,(x*)(x*)(p1)(x*)0,(p)(x*)0lim ek 1 1(p)(x*)0(p 1要求(x*)1可证收敛)2013/9/3026p!k e pk且有证证明：明：充分性.对p1，由于（x*）0 即满足x在邻域具有局部收敛性的条件，故迭代式收敛。(x)k 1k*x局部收局部收敛敛性及收性及收敛阶敛阶（续续）由(x)(x*)(x*)(xkk x*)x*)pk x*)p1 1(p)()(x p!k 1(p1)(x*)(x(p 1)!介于x 与x*之间，故k*pk(p)kk 1(x x )()p!x(x)x*x x*即lim ek 1 1(p)(x*)0(

20、p)(x*)p!1k (x x*)plim k 1 k故x(x)为p阶收敛p!k e pkk 1k(x)(x)()(x x*)*当p1时，即kk(x*)1lim xk 1 xx x*k 2013/9/3027k局部收局部收敛敛性及收性及收敛阶敛阶（续续）必要性：设迭代式为p 阶收敛，由收敛定义有 lim x x*kk 也即lim(x)x*。由(x)在x*邻域的连续性知 x*(x*)。kk 下面证明：(x*)(x*)(p1)(x*)0,(p)(x*)0用反证法，假定设有正整数 p 使0(x*)(x*)(p0 1)(x*)0(p0)(x*)0p0 p(x x*)p0即(p0)()p0!则(x)x*

21、kk(x)0p0!1 lim(p0)*ek 10 k epk显然 2013/9/3028,当p0 p 1时，由lim e 0得limp pk ek pp pek 1 1 ek 1000 1 kkkkpkeee局部收局部收敛敛性及收性及收敛阶敛阶（续续）即e p不存在。这与xk 为p 阶收敛矛盾。lim ek 1k p p 1 由lim e 0得 lim 1 0k e p p00kk 当k即 lim ek 1 lim，这也与为p阶lim 0 1 k e p p0k e p0k 1k e pex kkek 12013/9/3029收敛矛盾。kkk C 0)(limk p0ek证毕局部收局部收敛敛性

22、及收性及收敛阶敛阶（续续）（3）收敛速度的实例设有两个迭代序列和，且为线性收敛，x x kkx kx k为平方收敛，且有 c(c 0,c e 1)c(0 c 1),ek 1ek 102limlimk k ekek则 ck 1 ee c e c2 e0k 1k 1k2k 1(2k 1 1)e04ek 12 2ek 1 c c ek cc若 1,c c 0.75，欲使误差小于108，则对于e e00线性收敛的 xk，由(0.75)可得k 1 64.03 ，2013/9/3030因此大约需要65次迭代。k 18 10lg 0.75 8局部收局部收敛敛性及收性及收敛阶敛阶（续续）x k而对于平方收敛的

23、，由(0.75)(2k 1 1)108 可得 2k 1 8 1 65.03,k 1 6.02lg 0.752013/9/3031，因此大约需要7次迭代。结论：平方收敛的序列收敛速度要比线性收敛的序 列大的多。Remark:不动点迭代的方法是以求解非线性方程的 实根来讨论的，但类似的结果完全可以推广到求方 程的复数根的情形。四、不动点迭代的加速设方程为，的某个预测值为校正两次x (x)x*x ,0 x1 (x0),x2 (x1)。x x*()(x x*)*由于 在10 与之间与之间。在2110 x2 x (xx)(x x )*211x在 x*邻域中，消去导数信息，即*x即x x*x x*1 0

24、x 2 2x x*x x (x x )x*110202*x2 xx1 x*2 x (x1 x0)21 02x*x x xx0 2x1 x2x2 2x1 x00因此可以得下述Steffensen迭代方法：2013/9/3032不动点迭代的加速（续）给出 x0，校正 xk 1 (xk)，再校正 xk 2 (xk 1)(x x)2(x)x)2kk 1k 2kk 1xk 1 xk x2x x改进k=0,1,2,.(xk)2(xk)xk x k k k 1kx或若记 yk(yk),k=0,1,2,.,上式也可以写成。(xk),zk上式称为Steffensen迭代格式。(y x )2 yk (xk)，zk

25、 (yk)k 12013/9/3033k 0,1,2,z 2 y x k k kkkkx x 不动点迭代的加速（续）对于Steffensen迭代，有以下定理：定理：设函数(x)有不动点 x*，且在 x*的邻域内 具有二阶连续导数，若(x*)A 且A 1,A 0,则 Steffensen迭代式为二阶收敛，而且其极限为 x*。证 明设 Aitken 或 Steffensen 迭 代 式 为 xk 1 xk k=0,1,2,则(x)(x)(x)x(x)x x x x x x(x)2(x)x222013/9/3034不动点迭代的加速（续）(1)验证:(x)与 (x)有相同的不动点(x*)则若 x*(x

26、*)x*2 x*(x*)(x*)2(x*)x*0 x*(x*),(x*)1.(x)x2即 x*(x*)。注意xx*(x)(x)(x)xlimx (x)limx x*lim 2(x)x(x)1 x x*(x)(x)(x)(x)12(x*)x*)(x*)1)(x*)x*)(x*)1)(x*)x*)(x*)*(x*)(x*)(x*)1)02013/9/3035(x*)(x*)1)(x*)1)(x*)1 2 2不动点迭代的加速（续）即 lim(x)x*.注意(x)的连续性，知(x*)x*,从而x x*说明 x (x)与 x (x)具有相同的不动点。(2)验证Steffensen迭代为二阶收敛 由(x)

27、有二阶连续导数，且 x*为(x)的不动点，有(x)(x*)(x*)(x x*)1()(x x*)22 x*A(x x*)O(x x*)2 1.1.(x)x (x)x*(x x*)A(x x*)O(x x*)2 (x x*)(A 1)(x x*)O(x x*)2 2013/9/3036不动点迭代的加速（续）2.(x)(x)(A 1)(x)(x*)O(x)(x*)2 (A 1)A(x x*)O(x x*)2)O A(x x*)O(x x*)2)2(A 1)A(x x*)O(x x*)2 2013/9/3037不动点迭代的加速（续）(x)x 2*故 xk 1 x (xk)x(xk)(xk)(xk)x

28、k x x*k k k(A 1)A(x x*)(A 1)(x x*)O(x x*)2 kkk(A 1)2(x x*)2 O(x x*)3)kk x x*k(A 1)2(x x*)2 O(x x*)3)(A 1)2(x x*)O(x x*)2 x x*k k kkk*3 O(x x*)2)O(x x )k(A 1)2(x x*)O(x x*)2)kkk C 0limxk 1 x*2013/9/3038 x*)2k 0 (xk即Steffensen迭代二阶收敛。证毕不动点迭代的加速（续）Remark1：当在x*的邻域中0 (x)1，则 0 (x*)1.xk 1 (xk)线性收敛。当在x*的邻域中(

29、x)1 时，则(x*)1.xk 1 (xk)不收敛。但Steffensen迭代不仅能加速收敛，而且也能将发散的 迭代改进为收敛的迭代。(x x)2k 2k 1kk 1 k k 1k x x 2x xRemark2：严格讲，x称为Aitken加速迭代格式，此时可以证明xk 比xk 收敛 快。只有当xk 由不动点迭代 xk 1 (xk)，xk 2 (xk 1)产生，得到的公式才称为Steffensen公式。Remark3：Steffensen加速技术一般不对高阶收敛的迭 代法进行加速，因为此时效果不明显。2013/9/3039 2.4 Newton 法一牛顿迭代格式及其几何意义设xk 是 f(x)

30、0 的一个近似根。f(x)f(x)f(x)(x x)f(xk)(x x)2 2!kkkk取前两项近似代替f(x)得近似 f(x)0的线性方程f(xk)f (xk)(x xk)0f(xk)设 f(x)0,令解为 xk 1得xk 1 xk f(x),(k 0,1,2,)上式k称为 f(x)0 的Newton迭代法，对应的方程x x f(x)f(x)2013/9/3040显然是 f(x)0的同解方程。标准牛顿法（续）由知是处y f(x)的f(x)k 1kkx x k 1x(xk,f(xk)切线与 轴交点的横坐标，f(x)k f(x)y f(x)kkxx xk故Newton法的几何意义是逐次用切线代替

31、曲线，求切线与横坐标轴的交点。Newton法亦称为切线法。Newton法示意图见下页。2013/9/3041标准牛顿法（续）yy=f(x)x*xn x0 xn+1xn+2Newton法示意图2013/9/3042二、局部收敛性与收敛的阶定理：定理：设 x*为 f(x)0 的根，在开区间(x*,x*)内，f(x)连续，f (x)0,则Newton迭代式对 x至少为二阶收敛.x*,x*0由(x)x f(x)及(x)1 1 f(x)2 f(x)f(x)f(x)f(x)2证证明明：再根据 f(x)在(x*,x*)内连续.f(x)0,知(x),(x)f(x*)f(x*)在(x*,x*)内连续，且(x*)

32、x*,(x*)0 f(x*)2故由迭代局部收敛的充分条件知，Newton迭代法局部证毕Remark：只有当初值选的充分靠近 x*时，才能保证序 列收敛。收敛，且至少为2阶收敛。2013/9/3043三、非局部收敛性定理：定理：设有 f(x)0且 f(x)C 2 a,b，（二阶导数存在）且满足，（1）f(a)f(b)0（2）f (x)0,f(x)0.x a,b（f(x),f(x)不变号）取x0 a,b,使 f(x0)f(x0)0.则（1）f(x)0 在 a,b内有唯一的根 x*f (x )2 f(x*)2013/9/3044lim*x*)2xk 1 xk (x（2）由Newton迭代式产生的序列

33、收敛于,且xx kk非局部收敛性（续）证明：（1）由 f(x)在 a,b上连续，且 f(a)f(b)0 知 f(x)0在a,b内至少有一根，由 f(x)0（即f(x)不变号），知f(x)0在 a,b内有唯一的根，且 f (x)0,保证了该根为单根。（2）条件（1）和 f (x)0 有四种情况。仅就 f(a)0,f(b)0,f(x)0 的情况证明。由中值定理，存在 (a,b)使得 f ()f(b)f(a)0b a2013/9/3045由于f(x)在 a,b上不变号，因而 f(x)在a,b上总大于零，即对x a,b.f (x)0 ，由 f(x)0，知 f(x)在 a,b上单调增。又由 f(x0)f

34、(x0)0 可知。f(x0)0非局部收敛性（续）又由 f(x0)0 知 x0 x,*而0得f(x0)f(x0)xx1 x0 x1 x0 x x0*而另一方面，将 f(x)在 x0 作Taylor展开，f(x)f(x )f(x )(x x )1f()(x x )2f(x*)f(x )f (x )(x*x )1f()(x*x )2 0000002!其中 0 在x 与x0之间，解 变形200000)(x*x )2f(x )f(x )(x*x )1 f(即x*x f(x0)1 f(0)(x*x )2 0000000022 f (x )2013/9/3046f(x )00非局部收敛性（续）故x*x x*

35、x 0 0f(x)f(x)100于是10 x*x x一般地，设,类似可得*x xkf(xk)f(xk)0 xkkkk 1 x x f(x)f(xk)f(xk)*k 1 x x x x f(x )f(x )kkkkx x且k)(x*x)2 02 f(x)(1 fkk xk(k 0.1.2)xk 1*即有 x由此知为单调下降序列，且有下界，故必有极限*xxx k2013/9/3047非局部收敛性（续）两端同时取极限f(x)f(xk)k 1kkx x 对从而得 f(x)0，再由 f(x)0 在a,b 内有唯一根，则必有 x x*从而知 lim x x*kk 且由2 f(x)1 f(k)(x x*)2

36、(x*x)2*xk 1 xk 1*kkkx x x*)22f(x*)1 f (x )k (xlim*xk 1 xk得这表明了Newton迭代的二阶收敛性。证毕2013/9/3048非局部收敛性（续）更一般的非局部收敛定理（全局收敛定理）如下：定理：设 f(x)在a,b 上连续，且（1）f(a)f(b)0（2）f (x)0 f(x)0，f(b)2013/9/3049（3）f(a)b af (a)f (b)b a.则对 x0 a,b，Newton迭代序列xk 收敛于方程f(x)0在a,b内的唯一实根 x*。Remark：该定理的实质是指，当取x0=a或x0=b时，能保证x1仍然在区间a,b中。2.

37、5 Newton迭代法的变形一、重根情形的牛顿迭代法Remark：标准牛顿迭代法仅适用于单根的情形。设 x*为f(x)0 的重根(m 2),f(x)在 x*的某邻域内有m 阶连续导数，这时f(x*)f(x*)f(m1)(x*)0f(m)(x*)0将 f(x)在 x*处展开，有：1)(x x*)m(m1)*(m)*(m1)m!f(x x )f(x )(m 1)!f(x)f(x )*(2)(x x*)m1(m)*m2(m1)*(m 1)!(x x )f(x )(m 2)!f(x)f (x )f2013/9/3050重根情形的牛顿迭代法（续）(x x*)3 3 (x x*)m2(m 2)!f(m)(

38、)f(m1)(x*)f(x)f(x*)(m 3)!其中 1，2，3 介于x 与 x*之间.由Newton迭代函数(x)x f(x)f(x)得(x )lim(x)lim)(m)(1)(x x*)mm!(m)*xxx xx ff(x x )(m 1)!*m12(x x*)f(m)()limx 1 x*2013/9/30512mf(m)()xx*重根情形的牛顿迭代法（续）(f(x)2(x*)lim(x)lim f (x)f(x)xx*xx*m f(m)()223(m 1)f(m)()f(m)()1 limxx*m1 1由于0 (x*)1，故对于m重根（m 2），Newton迭 代法仍收敛，但只有线性

39、收敛速度。若取f(x)，从以上分析可知，(x*)0，(x)x m f(x)由此得到平方收敛的方法：mf(xk)xk 1 xkk 0,1,2,f(x)k该方法称为改进的Newton法。但实际上该式使用比较 困难，因为事先很难知道根 x*的重数m。2013/9/3052重根情形的牛顿迭代法（续）一种修改法是令则若 x 是f(x)的 m重零点，f(x),(x)f(x)*则 x*是(x)的单重零点，取迭代函数 f(x)f (x)f(x)(x)x (x)x f(x)(x)(f(x)2即(x)x f(x)f(x)(f(x)2 f(x)f (x)f(xk)f(xk)xk 1 xk则是二阶收敛的。缺点 f(x

40、)f(x)f (x)2kkk是需要计算 f(xk)，计算量稍大。2013/9/3053重根情形的牛顿迭代法（续）另一种修改方法式估计m的近似值。如果发现用 Newton迭代格式计算的收敛速度很慢时，可以结 合加速方法来确定根的重数。对Newton迭代有x x*lim k 1 1x x*1k kmx*xm k xk 1 xk故有22x*k 2kk 1(xk 1 xk)xk 2 2xk 1 xkxk 2 2xk 1 xkkxx x x 又由知k k 1kkk 2k 1(xk 1 xk)kx xxx 2x xm x 1 2x 2xk 1 xkk 2xk 1 xk2013/9/3054二、Newton

41、下山法由Newton迭代法的收敛定理知，Newton迭代法对 初值x0的要求是很苛刻的。在实际应用中往往难 以给出较好的初值x0。下面我们给出一种降低对 初值要求的修正的Newton法。方程f(x)0 的解 x*是f(x)的最小值点，即0 f(x*)min f(x)x若我们视 f(x)为f(x)在 x 处的高度，则 x*是山谷的最低点。若序列 x k 满足f(xk 1)f(xk),则称 xk 是 f(x)的一2013/9/3055个下山序列。求下山序列的算法称为下山法。Newton下山法（续）Newton下山法即是要求迭代后，得到一个以0为下界的严格单调减序列)，这样当 可得 f(xk 1)0

42、,k 时，f(x k xk 1*x因为*)2 xk 1 x*f (k)(2 f(x)xkkx)(x x*)f(x)f(x*)f(k1k1k1有f(x)f(2 f(x)*f()f()(x x)k 1*k 1k 1k 1k2(x x)kk2f(k 1)f (k )f(x k )f(2 f(xk2013/9/3056kNewton下山法（续）k 若 x*为 f(x)的单根，则当时，f (x k 1)1 f (x)0*即f(x)O(f 2(x)2f (x)2f2 (x)kk 1k于是当 k 充分大时，f(xk 1)f(xk)。结论：收敛的牛顿序列除去有限个点后一定为 下山序列。但下山序列的一个极限点不

43、一定是 方程的根。2013/9/3057Newton下山法（续）引理：若，且 f(x)0,则存在 0,f(x)C 2 a,b使得当 0 t 时，)f(x)，f(x)f(x t f(x)x a,b证明：将在处展开,得f(x)t f(x)fxxf(x)O(t)f(x)f(x)f(x)t f(x)2f x tf(x)f x t ()f(x)t ()f(x)f xf x所以 limt 0 0 t f(x)f(x)2013/9/3058f(x)f(x)Newton下山法（续）故1 0,t(0,),f x t f(x)f(x)t f(x)f(x)f(x)f(x)1f(x)t f(x)f(x)2f(x t

44、f(x)(1 t)f(x)1 t f(x)2f(x)（0 t 1）即由)(1 t)f(x)f(x tf(x)(1t)f(x)f(x)f(x tf(x)f(x)f(x)t得(1)f(x)f(x)2013/9/30592f(x)f(x t证毕Newton下山法（续）Remark：该引理表明，f(x)是f(x)在x点的下山方f(x)0，使 x向。可以选择适当的tkf(x)f(xk )k 1kk xk t满足f(xk 1)f(xk),k 0,1,.在Newton迭代法中引进下山因子tk 0,1将迭代格式修改为xf(x)f(xk)k 1k则有 f(xk 1)f(xk),为保证xk 是f(x)的一个收敛的

45、下山 xk tkk 0,1,.序列，则 t k 不能太小；为保证牛顿法的高阶收敛性，我们希望k充分大时，tk 1，即成为标准牛顿迭代法。1 1下山因子的一种常用取法是取自集合。2013/9/3060kt1,.2 4Newton下山法（续）这种将下山法和牛顿迭代法结合起来使用的方法 称为牛顿下山法。其计算步骤如下：Step1.选取初始 x0。Step2.取下山因子 t 1。Step3.计算及k 1。f(x)f(xk)xk 1 xk tkf(x)Step4.判断？f(xk 1)f(xk)f(xk 1)f(xk)成立，则有两种情况：（1）若当时，终止迭代，取；x xk2013/9/3061x*xxk

46、 1k 1Newton下山法（续）x 时，k增加1，即把 xk 1 称为新的 x，当 xk 1 xkkf(xk)，也有两种情况：f(xk 1)（2）若转Step2继续迭代。当 t t ，且时，将 t缩小一半，转Step3继续迭代；f(xk 1)f当t t，且时，终止迭代，取 x xk 1；f(xk 1)f*否则，取 xk 1 xk（为一适当增量），转Step2继 续迭代。Remark：上述步骤中，x，f 分别表示根的允许误差2013/9/3062和残量精度要求，t 为下山因子下界。Newton下山法（续）Remark1：由数值试验可知，用Newton下山法求 解方程的根，需要一定的经验。当函数

47、形状复杂 时，Newton下山法可能收敛很慢。只有当xk充分 接近x*时，才具有二阶收敛速度。Remark2：对形状复杂的函数使用Newton法和 Newton下山法时，程序中应该加上f(xk)是否为零 的判断，以排除 f(xk)0不能进行迭代的可能。Remark3：Newton法是一种特定的不动点迭代 法，因此它可以用于求方程f(x)=0的复根。2013/9/3063三、弦割法为了得到超线性收敛且避免导数计算的迭代格式，常 用函数增量与自变量增量之比来近似替代Newton迭 代格式中的导数项。f(x)f(xk)f(xk 1)x xk取kk 1用上述增量比代替Newton迭代格式中的一阶导数，

48、则有f(xk)2013/9/3064),k 0,1,.(x xf(x)f(x)k 1k 1k 1x x kkk弦割法的迭代格式（续）此迭代过程为弦割法，又称为拟牛顿法。弦割法求 xk1的过程，相当于过A、B两点作直线：y f(xk)f(xk)f(xk 1)用来描述用弦AB代替 f(x)，用弦AB与x轴交点C的横坐标 xk 1 作为f(x)0 的新的近似根。再用弦AC与X轴交点的 横坐标 xk 1 作为 f(x)0的新的近似根。弦割法求 xk 1 要用到 xk,xk 1,开始必须先给出 x0,x1。2013/9/3065xxkxkxk 1f(x)0局部收敛性定理定理：设 f(x)0,f(x*)0

49、,f(x)在 x*的某邻域内连续，则存在 x*的一个邻域 N(x*)x*,x*，（0当*)时，弦割法产生的序列收敛于 x*，且收敛阶为 1.618。x0,x1 N(xx k2013/9/3066对于弦割法的修正弦割法与Steffensen迭代法有密切的关系。设 f(x)0 的等价方程为x(x),yk (xk),zk (yk)(xk),对g(x)x(x)0,在(xk,g(xk),(yk,g(yk)使用弦割法，求出的值记为 xk 1 ，则xk 1(x y)x g(xk)g(yk)x kkkg(xk)k(y x)(y(y)(x (x)xk (xk)kkkkkkkz k 2 y k x(y k x k

50、 )k x2(xk)2(xk)xk(xk)xk)k x 2这就是Steffensen迭代法。2013/9/3067修正的弦割法（续）牛顿法和弦割法的另一种修改方式为：对于给定的f(x)0,令(x)x f(x)，则 f(x)0与 x (x)等价。对如此特定的(x)应用Steffensen迭代，有xk 1 (xk)2(x)x f(x f(x)f(x)f(x)该迭代式也称为Steffensen迭代，它也可看作是对 Newton法和弦割法的一种修改。这一迭代公式既不要 计算Newton法中的导数 f(xk)，也不需弦割法中的两 个初值，它是一种单点迭代法。2013/9/3068修正的弦割法（续）当 f