方程求根的迭代法课件

1、230252( )1 ,( )71 ,( ) sinxf xxf xxxxf xx e 超越方程问题：问题：设设 是实系数多项式或是任意实函数，求是实系数多项式或是任意实函数，求 的的 根根 ，其中，其中 .( )f x( ) 0f x *,xa b定义定义 按照按照一定规则（某个固定的计算公式一定规则（某个固定的计算公式 ），）， 把解的近似值逐步精确化，直到满足实际问题的精把解的近似值逐步精确化，直到满足实际问题的精度要求度要求.1()nnxx 迭代法迭代法其基本思想如下：其基本思想如下： 将方程将方程 转化为等价方程转化为等价方程 ( )0f x ( )xx迭代函数迭代函数0 x 取初值

2、取初值 ，用显示公式，用显示公式 计算得数列计算得数列 1()nnxxnx1nnxx若若 ，则计算停止，否则继续迭代，则计算停止，否则继续迭代. .*x012345610.50. 6666660.60.6250.6153850.619048kkx789101112130.6176470.6181820.6179780.6180560.6180260.6180370.61803301111kkxxx210 xx 5513120.4 1010 xx*0.61803x 记笔记记笔记311kkxxkkx01234561.51.375211.330681.325851.324931.324751.324

3、73( )0f x *x11()kkxx311kkxx0121.5 2.37512.398kkx12()kkxx1.迭代函数如何构造？2.初值的选取3.误差估计（迭代结束的条件）例例 用迭代法求方程用迭代法求方程 ， 在在x=1.5附近的一个根附近的一个根3410 ,10 xx取1 开方法开方法11()2kkkaxxx记笔记记笔记1( )()2axxx20( )xaxx k1.414214 1.4142141.4142161.4666671.51Xk4 53210记笔记记笔记21()2kkkxaxax21()2kkkxaxax211()kkkkxaxaxaxa200()kkkxaxaxaxa0

4、0 xaqxa令令 ，则由上式得，则由上式得对任意对任意 ，总有，总有 ，所以，所以 定理定理1 开方公式对于任意初值开方公式对于任意初值 均收敛均收敛思考题思考题1若若 ，开方公式结果如何？，开方公式结果如何？ 2证明对于任意证明对于任意 ，开方公式所得序列，开方公式所得序列单调减有下界单调减有下界00 xaqxa2211kkkqxaq00 x 00 x1q kkxa 00 x 00 xk01234 5Xk121.751.7321431.732051 1.732051 2 法法Newton1()()kkkkf xxxfxNewton 迭代公式()()()fxxxfx迭代函数1是否收敛于方程的

5、根或什么条件下收敛？2. 迭代函数有什么特性？ 牛顿迭代法的几何解释牛顿迭代法的几何解释 y y=f(x) Pk Pk+1 Pk+2 x* xk+2 xk+1 xk x ( )( )( )()kkkkt xf xf xx xNewton法又称为Newton切线法或切线法yx0 x0f(x)0X*yx0 x0f(x)0yx0f(x)0 x0 从几何的角度探讨从几何的角度探讨牛顿迭代法的收敛性牛顿迭代法的收敛性x1y0 x0X*0 x0X*x2 不满足迭代条件时，可能导致迭代值远离不满足迭代条件时，可能导致迭代值远离根的情况而找不到根或死循环的情况根的情况而找不到根或死循环的情况 从几何角度探讨牛

6、顿迭代法的收敛性从几何角度探讨牛顿迭代法的收敛性 ?0)(0 xf 1000)()(xxfxfx ?01 xx 开 始 输 入 x0,N 1 k k+ 1 k x1 x0 输 出 x1 输 出 迭 代 失 败 标 志 结 束 n k N ? n n y 输 出 奇 异 标 志 y y 牛顿迭代法的计算流程牛顿迭代法的计算流程例例 用用求求 x=e-x的根的根,=10-5解：因解：因 f (x)= x ex 1 , f (x)=ex ( x+1)建立迭代公式建立迭代公式11(1)1nnnxxnnnnnxnnx exexxxexx取取x0=0.5,逐次计算得逐次计算得 x1=0.571021, x

7、2=0.567156, x3=0.567143,x4=0.56714334*00.56714xxx求倒数 ，就是求解方程则相应的则相应的 迭代公式迭代公式1a1( )0fxax21( )f xx2( )( )2( )f xxxxaxfx212kkkxxaxNewtonNewton思考题：思考题：1. 讨论其收敛性及收讨论其收敛性及收敛条件敛条件2.讨论牛顿迭代法的收敛讨论牛顿迭代法的收敛条件条件，其其 法的迭代函数为法的迭代函数为3 压缩映象原理压缩映象原理 ), 2 , 1 , 0()(1kxxkk 如果由迭代格式如果由迭代格式 产生的序列产生的序列 收收敛敛, ,即即 nx)(1kkxx*

8、limxxnn则称迭代法收敛则称迭代法收敛 1kkxxkxx* 结束条件 y=x y y=)(x y=x 1)(0*x 0)(1*x P0 P2 P* Q1 Q2 x1 x0 x2 x* x y x0 x x1 x2 x3 x* y=)(x)(xP* P1 (a)(b) y=x y y=x y=)(x 1)(* x 1)(* x （c） （d） P* x1 x0 x y x0 x x1 x2 x3 x* y=)(x)(xx* x2 P* 定理定理2 设函数设函数 在在a,b上具有连续的一阶导上具有连续的一阶导 数数, 且满足且满足 （1）封闭性条件封闭性条件 对所有的对所有的xa,b 有有 a

9、,b （2）压缩性条件压缩性条件 存在存在 0 L 1 ,使所有的使所有的xa,b有有 则则 方程方程 在在a,b上的根上的根 存在且唯一存在且唯一，对任意的，对任意的 a ,b ，迭代过程迭代过程均收敛于均收敛于 . .且成立且成立)(x( ) x( )xL)(xx*x0 x)(1kkxx*x*11kkkLxxxxL01*1xxLLxxkk 压缩映象原理迭代结束的条件（事后误差估计法）满足精度要求的最大迭代次数（事先误差估计法）01 .02 .03 .推论: 若方程 在区间 内有根 且则迭代 均发散( )xx, a b*x,( )1xa bx 10(),kkxxxa b例例1 1 对方程对方

10、程 , ,构造迭代函数如下构造迭代函数如下 ， . .试讨论在试讨论在1,21,2上迭代上迭代 的敛散性的敛散性. .解解0245 xx 则则此时迭代公式满足迭代收敛条件，所以迭代此时迭代公式满足迭代收敛条件，所以迭代 在此区间上收敛在此区间上收敛. .所以所以 此迭代此迭代 发散发散. .2 , 1145)(,42)(45xxxxx5( )42,xx445511( )0.211,25 (42)5 (42)xxx 5516( )102x52()4xx5( )42xx1( )kkxx1( )kkxx1( )kkxx01,2x例例2 已知 讨论迭代 在区间 的敛散性.例例4 求 的近似值， .1,

11、 233(1)( )1,( )1xxxx 1()nnxx20123400 .50 .40 .4 1 60 .4 1 3 7 9 3 1 0 3kkx*2 1 0.4142157x 2 1 0.4142157 1.4142 例例3 用下列迭代法求 的正根 的近似值，试判断其敛散性. （1） ；（2） .220 x *1, 2x 12nnxx112()2nnnxxx4105670.4142857140.4142011830.4142157kkx 迭代法的算法框图迭代法的算法框图实验 ：1.探讨初值对迭代收敛的影响.2.同一方程构造不同的迭代，探讨敛散性；比较收敛迭代的收敛快慢情况. 10)(xx

12、开 始 输 入 x0,N 1 kk+ 1 k x1 x0 输 出 近 似 根 x1 |x1- x0|? 输 出 迭 代 失 败 标 志 结 束 n k N ? y n y 三、三、 局部收敛性局部收敛性定理定理3 3 设设 在在 的根的根 的邻域中有连续的的邻域中有连续的一阶导数一阶导数, ,且且 则迭代过程则迭代过程 具有具有局部局部收敛性收敛性. . )(x)(xx*x1)(* x)(1kkxx 未知，如何求未知，如何求 ？*x*( )x（1）定理）定理3对初值的要求比较高，对初值的要求比较高，一般用对分法找出较满意的初值，定一般用对分法找出较满意的初值，定理理2对初值的要求较宽松对初值的

13、要求较宽松（2）一个迭代若是整体收敛的，则）一个迭代若是整体收敛的，则一定局部收敛；反之则不成立一定局部收敛；反之则不成立例例5 已知方程 在 附近有一实根，讨论迭代 的敛散性.并计算结果，取 . 0 xex00.5x 010.5 ,( )nxnnxxxe510解：令 ，则 ( )xf xex(0.4) 0.27 0, (0.6)0.05 0ff0.5*0.4,0.6x 0.40.4,0.6 ,( )0.68 1xxxee *()1x010.5,( )nxnnxxxe*x1 2 9P010.5,( )nxnnxxxe取 计算结果见书 .附近的实根 ，且则取 收敛于 .例例6 设设 ，要使迭代过

14、程，要使迭代过程 局部收敛到局部收敛到 , ,求求 的取值范围的取值范围. .解：解： 由在根由在根 邻域具有局部收敛性时，收敛邻域具有局部收敛性时，收敛 条件条件 ) 5()(2xxx)(1kkxx5*x2( )(5),xxxxx21)(5*x1521)(*ax15211a0522a所以所以 051a例例7 7 已知方程已知方程 在在 内有根内有根 , ,且在且在上满足上满足 , ,利用利用 构造一个迭代函数构造一个迭代函数, ,使使 局部收敛于局部收敛于 . .解解: :由由 可得可得, , )(xxba,*xba,13)( x)(x)(xg), 2 , 1 , 0()(1kxgxkk*x

15、)(xxxxxx3)(31( ( )3 )2xxx 1213)(21) 3)(21)(xxxgbax,故故 , ,迭代公式迭代公式1)(* xg)3)(21)(1kkkkxxxgx局部收敛于局部收敛于分析 ，则由习题9,对应的迭代发散.2( )4x,xa b ()g x*x定义定义2 2 设迭代过程设迭代过程 收敛于收敛于 的的根根 , ,记迭代误差记迭代误差若存在常数若存在常数m m（m1m1）和和c c（ ），），使使 1()kkxx)(xx*xkkxxe*1limkmkkece则称序列则称序列 是是 m 阶收敛的阶收敛的, , 特别地特别地, ,m =1=1时称时称为线性收敛为线性收敛,

16、 ,m=2=2时称为平方收敛时称为平方收敛.1 .1 m 2 2时时称为超线性收敛称为超线性收敛. . kx四、迭代过程的收敛速度四、迭代过程的收敛速度 0c 例8 讨论迭代公式 ， 的收敛阶.11,0,12nnnxxx 112() ,1,22nnnnxxxx 定理定理4 设迭代过程设迭代过程 ， 若若 在所求根在所求根 的邻域连续且的邻域连续且 则迭代过程则迭代过程在在 邻域是邻域是m阶收敛的阶收敛的. .)(1kkxx( )( )mx*x*(1)*( )*( )( )( )0,( )0mmxxxx*x(2)m 证明： ()*1()() ,!mmkkkkkxxxxxxm在与之间* 2(1)*

17、( )*11( )( )()( )()()()()2!( )1)!()(!kkkkmkmmkkmxxxxxmxxxxxxxxxm*( )0,x 则此迭代过程则此迭代过程是是m阶收敛的阶收敛的. .)(1kkxx*x 迭代过程迭代过程 局部收局部收敛于敛于 ，又，又*()()*1*()()0()!mmkkkmkxxxxxmm 例例9 已知迭代公式已知迭代公式 收敛于收敛于 证明该迭代公式平方收敛证明该迭代公式平方收敛.证证: 迭代公式相应的迭代函数为迭代公式相应的迭代函数为21132kkkxxx3*3x2132)(xxx436)(232)(xxxx ，将将 代入，代入，根据定理根据定理4可知，此

18、迭代平方收敛可知，此迭代平方收敛.3*3x032336)(0)(33* xx， 牛顿迭代法的收敛性分析牛顿迭代法的收敛性分析定理定理5 设设 是方程是方程 的单根的单根, 且且f(x)在在 的某的某邻域内有连续的二阶导数邻域内有连续的二阶导数, 则牛顿法是局部收敛的则牛顿法是局部收敛的, 且至少为二阶收敛且至少为二阶收敛, 有有 *x0)(xf*x*1122*()limlim2()kkkkkkxxfxefxexx 证证: 牛顿迭代公式对应的迭代函数为牛顿迭代公式对应的迭代函数为 若若 是方程是方程 的单根的单根,则有则有 , 从而从而 )()()(xfxfxx*x0)(xf0)(*xf0)(*

19、 xf0)()()()(2* xfxfxfx由定理由定理3知知,牛顿迭代法在牛顿迭代法在 附近收敛附近收敛.又由定理又由定理4知知, 迭代公式至少是二阶收敛的迭代公式至少是二阶收敛的. *x22( )( )()( )( )( )( )( )( )( )1( )( )f xxxfxfx fxf x fxf x fxfxfx *2*()()()()f xfxxfx利用泰勒公式利用泰勒公式*2()0()()()()() ,2kkkkkkff xf xfxxxxx*2()()()()2()kkkkkkf xfxxxxfxfx*2( )( )()( )2 ( )kkkkkkf xfxxxxf xf x*

20、21()()2()kkkkfxxxxfx)(2)(lim*2*1*xfxfxxxxkkk 所以所以 法逻辑结构简单，在单根附近时，收敛速度很快；但（1）若初值选取不当， 迭代法可能失败或者收敛很慢；（2）若导数比较复杂，则每步的计算量较大；（3）若 为方程 的重根，结果如何？NewtonNewton*x( )0f x 4 法的改进与变形法的改进与变形331211 031kkkkkxxxxxxx Newton01.5x 012341.51.347831.325201.324721.32472kkx01230.617.911.946807.98552kkx00.6x 4 法的改进与变形法的改进与变

21、形)()(1kkxfxf 下山法下山法1()()kkkkf xxxfx其中其中(01)(01)为下山因子为下山因子 Newton11()(),()()kkkkkkf xxxf xf xf x- 下山法下山法 Newton1()()kkkkf xxxfx11(1)kkkxxx1, 1,214 为避免计算函数的导数为避免计算函数的导数 ，使用差商，使用差商 00()()kkfxfxxx)(kxf 100( )()( )( )kkkkkf xxxxxf xf x),2, 1(k)(kxf 称为称为弦截法弦截法迭代公式迭代公式.（单点弦截法单点弦截法）替代牛顿公式中的导数替代牛顿公式中的导数 ，便得到

22、迭代公式，便得到迭代公式 kx0 x*x1kxyx( )yf x0在单根附近线性收敛在单根附近线性收敛*00*0*0()()1()()()1()()fxxxxf xfxf xf xxx 使用差商使用差商替代牛顿公式中的导数替代牛顿公式中的导数 ,便得到迭代公式便得到迭代公式 称为称为快速弦截法快速弦截法迭代公式迭代公式.（双点弦截法双点弦截法）11()()kkkkfxfxxx)()()()(111kkkkkkkxxxfxfxfxx),2, 1(k)(kxf 在单根附近收敛，收敛阶为在单根附近收敛，收敛阶为1.618例例10 用用快速快速弦截法求方程弦截法求方程 在在 初初始值邻近的一个根始值邻近的一个根. 要求要求解：取解：取 , , 令令 利用快速弦截法迭代公式利用快速弦截法迭代公式 xex5 . 00 x0001. 01kkxx5 . 00 x6.01xxexxf)()()()()(1111kkxxkkxkkkxxeexxexxxkkk*40.56714xxk2340.567540.567150.56714kx 快速快速弦截法算法实现弦截法算法实现 ?0)(0 xf ?0)(1xf ?0)()(01xfxf 2010111)()