数值计算方法课件-CH6逐次逼近法—63非线性方程的迭代解法.ppt

1、华长生制作1第六章第六章 逐次逼近法逐次逼近法6.3 解非线性方程的迭代法解非线性方程的迭代法本节主要内容本节主要内容3-1 解非线性方程的简单迭代法解非线性方程的简单迭代法3-2 Newton迭代法及其变形迭代法及其变形 6.3 6.3 非线性方程的迭代法非线性方程的迭代法 方程是在科学研究中不可缺少的工具，方程求解是科方程是在科学研究中不可缺少的工具，方程求解是科学计算中一个重要的研究对象学计算中一个重要的研究对象.0)(xf设函数方程设函数方程.0)()()(0111次代数方程为，则称若nxfaxaxaxaxPxfnnnnn.0)()(为超越方程等），则称数数、指数函数、对数函为超越函数

2、（即三角函若xfxf统称为非线性方程统称为非线性方程 几百年前就已经找到了代数方程中二次至五次方程的几百年前就已经找到了代数方程中二次至五次方程的求解公式求解公式,但是但是,对于更高次数的代数方程目前仍无有效对于更高次数的代数方程目前仍无有效的解析解法，对于无规律的超越方程的求解也无精确解的解析解法，对于无规律的超越方程的求解也无精确解法法.因此因此,研究非线性方程的数值解法成为必然研究非线性方程的数值解法成为必然.注注.(1)非线性方程一般情况下很难求得其解析解非线性方程一般情况下很难求得其解析解,所以往往采用数值方法求解所以往往采用数值方法求解.(2)非线性方程中非线性方程中,通常假设函数

3、通常假设函数 f(x)是连续的是连续的.求非线性方程求非线性方程的根的根.f(x)=0-(3.1)求非线性方程的根求非线性方程的根,即求曲线即求曲线 y=f(x)与与 x 轴的交点轴的交点单根区间单根区间:方程在区间方程在区间 a,b 只有一根只有一根多根区间多根区间:方程在区间方程在区间 a,b 有多个根有多个根有根区间有根区间xyy=f(x)aAb0B保证有解3-1 3-1 简单迭代法简单迭代法思思路路2.建立迭代格式建立迭代格式:求解非线性方程问题转化为求序列极限问题求解非线性方程问题转化为求序列极限问题1.将将 化为与它同解的方程化为与它同解的方程:0)(xf)(xx-(3.2)即若存

4、在即若存在,使使 ,则有则有 ;反之也成立反之也成立.0)(f)()(1kkxx-(3.3)称称(3.3)为求解非线性方程的为求解非线性方程的(简单简单)迭代法迭代法迭代过程迭代过程迭代格式迭代格式.若当若当 时时 ,则迭代法则迭代法(3.3)收敛收敛,就是方程就是方程(3.1)的解的解,否则迭代法发散否则迭代法发散.kkx3.从初值从初值 出发出发,得到序列得到序列0 xkx),2,1,0(k迭代函数 根的存在与唯一性根的存在与唯一性:方程有没有根？若有根方程有没有根？若有根,是否唯一是否唯一?研究研究内容内容 迭代格式的收敛性迭代格式的收敛性:如何构造收敛的迭代格式如何构造收敛的迭代格式？

5、定理3.1:解的存在与唯一性定理 收敛速度的确定；收敛速度的确定；收敛阶的概念及判定定义3.1,定理3.2例例1 用迭代法求用迭代法求 的根的根.012)(3xxxf)(213xxx(1)化为等价方程化为等价方程:取取 ,代入上式得代入上式得:00 x)(2131kkkxxx得迭代格式得迭代格式:,994.0,964.0,79.0321xxx显然显然,当当 时时,即迭代法收敛即迭代法收敛.另外另外 即即 是方程是方程 f(x)=0 的根的根.k1kx0)1(f1x解解:(2)由由 还可得等价方程还可得等价方程:0123 xx)(123xxx)(1231kkkxxx得迭代格式得迭代格式:取取 ,

6、代入上式得代入上式得:00 x,55,3,1321xxx显然显然,当当 时时,即迭代法发散即迭代法发散.kkx迭代法的收迭代法的收敛与发散敛与发散,依赖于迭代依赖于迭代函数的构造函数的构造!迭代函数要满足什么迭代函数要满足什么条件条件,迭代法才收敛？迭代法才收敛？定理3.1(P225)且满足上连续在设迭代函数,)(bax;)(,)1(bxabax时当均有对任意存在正数,10)2(baxLLx|)(|，且收敛于，迭代法意初始值，并且对任内存在唯一根在则方程),2,1,0()(,)(10kxxbaxbaxxkk11.(3.4)1okkkLxxxL102.(3.5)1kokLxxxL判断迭代是否可终

7、止的依据判断迭代是否可终止的依据若迭代函数满足定理若迭代函数满足定理 3.1 的条件的条件,则迭代法收敛则迭代法收敛.那么那么迭代过程何时结束？迭代过程何时结束？l 由由(3.4)(3.4)知知,只要相邻两次计算值的差只要相邻两次计算值的差 达到事先给达到事先给定的精度要求定的精度要求 ,迭代过程可终止迭代过程可终止,即即1kkxx)(1kkxxkxl 由由(3.5)(3.5)知知,若已知若已知 L L 的范围的范围,则由给定的精度可大致估计则由给定的精度可大致估计 迭代所需次数迭代所需次数 k(3.4)11kkkLxxxL(3.5)101kkLxxxL判断迭代可终止的条件判断迭代可终止的条件

8、估计迭代次数估计迭代次数1kkxx迭代法的结束条件迭代法的结束条件如何确定迭代次数？如何确定迭代次数？迭代法次数的确定迭代法次数的确定局部收敛问题局部收敛问题 定理定理3.1的条件一般难于验证的条件一般难于验证,且在大区间且在大区间 a,b 上上,这些这些条件未必满足条件未必满足,因此使用迭代法时，往往只在根因此使用迭代法时，往往只在根附近进行附近进行.即只要假定即只要假定 在在的附近的小邻域内连续的附近的小邻域内连续,且满足且满足则存在则存在的某个邻域的某个邻域 ,在在S上上 满足定理满足定理3.1的条件的条件,称这种收敛为称这种收敛为局部收敛局部收敛.1)(x)(xx:S)(x一般一般,在

9、给定精度下在给定精度下,要求方程在某点附近的根要求方程在某点附近的根.例例2 求求 在在 附近的一个根附近的一个根,要求精度要求精度 .xex0.5x 310解解(2)利用定理利用定理3.1验证所建立迭代格式的收敛性验证所建立迭代格式的收敛性(1)首先化等价方程首先化等价方程,建立迭代格式建立迭代格式)(1kxkxexk 当当 时时,0.5,0.69x()()0.6065xxxeex 所建迭代格式所建迭代格式 满足定理满足定理3.1的条件的条件,对于初始值对于初始值 收敛收敛.kxkex15.00 x0.5,0.69x 确定迭代区间确定迭代区间,取取 一般选择根附近的一个小区间 当当 时，时，

10、是单调递减函数是单调递减函数.()xxe6065.0)5.0(0.69)0.5016()0.5,0.69x0.5,0.69x0.5,0.69x 当当 时，时，0 0.5 0.606 531 0.106531 迭代结果迭代结果:1kxkexkxkkxx1k 1 0.606 531 0.545 239 0.061 292 2 0.545 239 0.579 703 0.034 464 3 0.579 703 0.560 065 0.019 638 4 0.560 065 0.571 172 0.011 107 5 0.571 172 0.564 863 0.006 309 6 0.564 863

11、0.568 439 0.003 576 7 0.568 439 0.566 409 0.002 030 8 0.566 409 0.567 560 0.001 151 9 0.567 560 0.566 907 0.000 6530.566 907 是方程在是方程在 x=0.5 附近的计算根附近的计算根.从定理从定理3.1可见可见,一方面一方面,当当 L 或或 的值越小的值越小,迭代收敛的速度越快迭代收敛的速度越快;另一方面另一方面,当当 L 1 称为超线性收敛称为超线性收敛;p=2 称为平方收敛称为平方收敛.p越大越大,迭代法收敛速度越快迭代法收敛速度越快定义定义3.1 设迭代格式设迭代格式

12、 xk+1=(xk),当当k时时,xk+1,记误差记误差 。若存在实数。若存在实数 p 1 和和 c 0 满足满足则称迭代法为则称迭代法为 p 阶收敛阶收敛.ceepkkk1lim-(3.7)如何定量判断如何定量判断收敛速度收敛速度?11,kkkkexex收敛阶的判定收敛阶的判定定理定理3.2 如果如果 x=(x)中中,迭代函数迭代函数 (x)在根在根附近附近满足：满足：（1 1）(x)存在存在 p 阶导数且连续；阶导数且连续；（2 2）()=()=(p-1)()=0,(p)()0 则迭代法则迭代法 xk+1=(xk)为为 p 阶阶收敛收敛.例例3 设设 ,证明由证明由建立的迭代法至少是平方收

13、敛的建立的迭代法至少是平方收敛的.0)(f)()()(xxfxfxx0)(f-(3.8)Newton 迭代法迭代法证明证明 只需证明只需证明 ,见教材见教材 p228.0)(3-2 Newton3-2 Newton迭代法及其变形迭代法及其变形 用迭代法解非线性方程时，如何构造迭代函数是非用迭代法解非线性方程时，如何构造迭代函数是非常重要的常重要的.主要介绍：主要介绍：1）Newton迭代法迭代法2）弦截法）弦截法1、Newton迭代法（又称作切线法）迭代法（又称作切线法）Newton法是求解方程法是求解方程 f(x)=0的一种重要的迭代法。的一种重要的迭代法。这种方法的基本思想是设法将非线性方

14、程这种方法的基本思想是设法将非线性方程 f(x)=0逐步转逐步转化为某种线性方程求解。化为某种线性方程求解。如果将非线性方程如果将非线性方程0)(xf)()(xfxkxx)0)(xk)(x)()()()(1)(xfxkxfxkx,0)(的根为设xf则收敛速度越快附近越小在,|)(|x化为等价方程化为等价方程0)()()()(1)(fkfk所以可以令所以可以令 ，这样就能保证，这样就能保证(1)(1)式对应的迭代法式对应的迭代法至少是平方收敛的。至少是平方收敛的。即：即：那么如何确定那么如何确定k(x)的形式使上式成立并使其所对应的迭的形式使上式成立并使其所对应的迭代法收敛呢？代法收敛呢？（1）

15、0)()0()0)ff x若即不是的重根，有)(1)(fk于是取于是取)(1)(xfxk)()()(1xfxfxxx）变为：则式（(2)迭代法上式为至少是平方收敛，并称则迭代法，且的根为）设方程（定理Newton),2,1,0()()(,0)(0)(P2283.31kxfxfxxfxfkkkk-(3.10)注意：注意：1)Newton迭代法的迭代法的优点优点:收敛速度快（至少是平收敛速度快（至少是平方收敛的）。方收敛的）。2)Newton迭代法的迭代法的缺点缺点：需要计算导：需要计算导数数 ，如果函数，如果函数f(x)比较复杂，使用比较复杂，使用Newton公式是不公式是不方便的。为了避开导数

16、的计算，可以用导数的近似值方便的。为了避开导数的计算，可以用导数的近似值来替代来替代 ，得到所谓的，得到所谓的弦截法弦截法。()fx()fx2、弦截法、弦截法中含有函数的导数中含有函数的导数,不方便求不方便求.11)()()(kkkkkxxxfxfxf)()(1kkkkxfxfxx -(3.10)代入代入(3.10)得得Newton迭代法迭代法:可用导数的近似式代替，即可用导数的近似式代替，即-(3.11)()()()(111kkkkkkkxxxfxfxfxx)()()()(111kkkkkkkxxxfxfxfxx弦截法弦截法的收敛阶为p1.618BAxk-1xkxk+2xk+1xk+1xk+

17、2y=f(x)f(xk)f(xk-1)Newton迭代法与弦截法的几何意义迭代法与弦截法的几何意义xy弦截法不需要求导弦截法不需要求导,但但需要两个初始值需要两个初始值;Newton 法虽需求导法虽需求导,但只需一个初始值但只需一个初始值.二者比较二者比较:Newton 法法又称切线法又称切线法例例4（P230）用用Newton法和弦截法分别计算方程法和弦截法分别计算方程在在 x=1.5 附近的根附近的根.时停止计算时停止计算013 xx解解131)()(231kkkkkkkkxxxxxfxfxx取初值取初值 x0=1.5,代入上式代入上式,得计算解序列：得计算解序列：x11.347 83,x

18、21.325 20,x31.324 72,x41.324 72，(1)用用Newton法：法：注意：注意：1）Newton法在根法在根 附近收敛，初值应选在附近收敛，初值应选在 附近；附近；初值选的不合适会导致初值选的不合适会导致Newton迭代法发散迭代法发散;2）Newton法的收敛速度与初值、收敛阶数有关。法的收敛速度与初值、收敛阶数有关。4100.152175 10 xx 4210.022635 10 xx 4320.000525 10 xx4435 10 xx 因此因此 1.324 7241510kkxx取初值取初值 x0=1.5,x1=1.4 代入上式代入上式,得计算解序列：得计算

19、解序列：x21.335 22,x31.325 41,x41.324 72,x51.324 72，(3)若用若用Newton法法,取初值取初值 x0=0,得得x1=1,x2=-0.5,x30.33,x4-1.44 发散震荡！11)()()()(21123111kkkkkkkkkkkkkkxxxxxxxxxxfxfxfxx两个初值!(2)用弦截法用弦截法:4210.064705 10 xx 4320.009815 10 xx 4430.000695 10 xx4545 10 xx 因此因此 1.324 72初始值的选取影响初始值的选取影响Newton法的收敛性！法的收敛性！-2-1.5-1-0.500.511.52-8-6-4-202461)(3xxxf00.511.5-2-1.5-1-0.500.511.51.32472x1=1.34783x0=1.5x2=1.325 20收敛-2-1.5-1-0.500.511.52-8-6-4-202461)(3xxxf-1.5-1-0.500.5-8-6-4-2024x30.33x1=-1x2=-0.5x4-1.44x0=0发散