数值分析：4非线性方程求解

1、第四章第四章 非线性方程数值求解非线性方程数值求解 4.1 一元方程求根1）问题的提出问题的提出 满足函数方程满足函数方程 f(x)=0 (1)f(x)=0 (1)的的x x称为方程称为方程(1)(1)的的根根，或称为函数，或称为函数f(x)f(x)的的零点零点。如果。如果函数函数 (x)(x)可分解为可分解为 (x)=(x(x)=(x s)s)m mg(x)g(x)且且g(g(s s ) ) 0,0,则称则称s s是是 (x)(x)的的m m重零点或重零点或 (x)=0(x)=0的的m m重根。重根。当当m=1m=1时，称时，称s s是是 (x)(x)的单根的单根 或单零点。或单零点。若若f

2、(x)f(x)不不是是x x的线性函数的线性函数, , 则称则称(1)(1)为为非线性方程非线性方程, , 特特别地别地, , 若若f(x)f(x)是是n n次多项式，则称次多项式，则称(1)(1)为为n n次多项式方程次多项式方程或或代数方程代数方程。 理论上已证明，对于次数理论上已证明，对于次数n=4n=4的多项式方程的多项式方程, ,它的根它的根可以用公式表示可以用公式表示, ,而次数大于而次数大于5 5的多项式方程的多项式方程, ,它的根它的根一般不能用解析表达式表示一般不能用解析表达式表示. .因此对于因此对于f(x)=0f(x)=0的函数的函数方程方程, ,一般来说一般来说, ,不

3、存在根的解析表达式不存在根的解析表达式, ,而实际应用而实际应用中中, ,也不一定必须得到求根的解析表达式也不一定必须得到求根的解析表达式, ,只要得到只要得到满足精度要求的根的近似值就可以了。常用的求根满足精度要求的根的近似值就可以了。常用的求根方法分为区间法和迭代法两大类。方法分为区间法和迭代法两大类。求根问题包括：根的存在性、根的范围和根的精确求根问题包括：根的存在性、根的范围和根的精确化。化。求根方法中最直观最简单的方法是二分法求根方法中最直观最简单的方法是二分法。2)2)预备知识预备知识定理定理1 1.(.(根的存在定理根的存在定理) ) 假设函数假设函数y=f(x)y=f(x) C

4、 C a,ba,b , ,且且f(a)f(a)f(b)0, f(b)0, 则则至少存在一点至少存在一点x x (a,b)(a,b)使得使得f(x )=0.f(x )=0.( (并称区间并称区间(a,b)(a,b)为有根区间为有根区间) )定理定理2 2. . 假设函数假设函数y=f(x)y=f(x)在在 a,ba,b 上单调连续上单调连续, ,且且f(a)f(a)f(b)0, f(b)0, 则恰好只存在一点则恰好只存在一点x x (a,b)(a,b)使得使得f(x )=0f(x )=0定理定理3 3. . 假设函数假设函数y=f(x)y=f(x)在在x=sx=s的某一邻域内充分可微，的某一邻域

5、内充分可微，则则s s是方程是方程f(x )=0f(x )=0的的m m重根的充分必要条件是重根的充分必要条件是 0)(, 0)()()()()1(sfsfsfsfmm(1)(1)问题问题 给定方程给定方程f(x)=0,f(x)=0,设设f(x)f(x)在区间在区间a,ba,b连续连续, ,且且f(a)f(b)0,f(a)f(b)0,则方程则方程f(x)f(x)在在(a,b)(a,b)内至少有一根内至少有一根 , ,为为便于讨论便于讨论, ,不妨设方程不妨设方程f(x)=0f(x)=0在在(a,b)(a,b)内只有一个内只有一个( (重根重根视为一个视为一个) )实根，实根，求满足精度要求的近

6、似值实根求满足精度要求的近似值实根 。 (2)(2)概念及基本思想概念及基本思想 概概念：念： 二分法也称对分区间法、对分法等，二分法也称对分区间法、对分法等， 是最简单的求根方法，属于区间法求根类型。是最简单的求根方法，属于区间法求根类型。 基本思想：基本思想：利用连续函数的零点定理，将含根区利用连续函数的零点定理，将含根区 间逐次减半缩小，就可以构造出收敛点列间逐次减半缩小，就可以构造出收敛点列 来来 逼近根逼近根 。 *xxkx*x(3)(3)构构 造造 原原 理理 反复运用反复运用 定理定理1.(1.(根的存在定理根的存在定理, ,连续函数的连续函数的零点定理零点定理) ) 这个定理指

7、出了根的存在区间可由两端点处这个定理指出了根的存在区间可由两端点处的函数值是否反号确定，那么注意到，将含根区的函数值是否反号确定，那么注意到，将含根区间分为两个长度相等的子区间后，在这两个子区间分为两个长度相等的子区间后，在这两个子区间上也可利用零点原理确定根在那个子区间上，间上也可利用零点原理确定根在那个子区间上，如此继续下去就达到将含根区间逐步缩小的目的，如此继续下去就达到将含根区间逐步缩小的目的，此时，在这一些相互包含的子区间中构造收敛的此时，在这一些相互包含的子区间中构造收敛的数列数列 ，它将收敛于根，它将收敛于根 ，见下图，见下图kx*xabx1x2x3xf(x)(4)(4)方法步骤

8、方法步骤 0011111101011110111101110 (),().2():()0,() ()0,;, 0000110011001. 记1. 记含含根根区区间间 a , b =a, b, a , b =a, b,取取 中 中点点 并并计计算算2. 判2. 判别别的的值值若若则则 为为根根；若若取取 =即=即否否则则取取 =即=即得得到到a , b , 取a , b , 取代代a , b 继a , b 继续续运运算算. .abxf xf xf xxf xf aaa bxa baxax bba bx bk-1k-1kkk-1k-1kkkkk-1k-1k-1,2()0,() (a)0,abka

9、ba babxxf xxf xfxx kkkkkkkkkkkk3. 继3. 继续续运运算算， 由 由区区间间,构,构造造区区间间 , , 并并得得到到 ：若若则则为为所所求求的的根根; ;若若则则取取a , b =, ;a , b =, ;否否则则, 可, 可取取a , b = ,.a , b = ,.11*(a) () ()01(b) ()2(c) .,.;,()0,(,),lim,limkkkkkkkkkkkkkkf af bbabaa babxf xxa baxb 0011kk0011kk01k01k01k01k这这样样就就得得到到一一系系列列闭闭区区间间：a , b ，a , b ，a

10、 , b ，a , b ，. . . a , b , . . . , k=0, 1, 2, . . . . ,. . . a , b , . . . , k=0, 1, 2, . . . . ,并并满满足足：aaabbb即aaabbb即满满足足并并且且*,limkkkxxx控制循环（控制循环（K K）的方法：）的方法： 121n-1n-1n-1n-12nnN|,b-a|=222xxbaabx nnnn用用两两个个适适当当的的小小数数 、和和一一个个次次数数 来来控控制制，(1) 当(1) 当f ( )就f ( )N 时kN 时就就结结束束循循环环，表表示示未未达达到到求求解解精精度度而而终终止

11、止。由 得因此只要对分 次，则 有 注：因为 为 的一个端点，所以将区间 对分后，取 的中点 作为 的近似值，满足 nnab)(log22abnabn1)(log2abn,nnbax xx*211nnnbax,nnba)(log12abn,11nnbanx,ba*xnxx*简单并保证收敛简单并保证收敛; 对对f (x) 要求不高要求不高(只要连续即可只要连续即可) .无法求复根无法求复根 收敛慢收敛慢 (仅与一个以仅与一个以 1/21/2为比值的等比级数相同为比值的等比级数相同) )二分法的优缺点 确定根所在的范围a,b对有的函数是一件困难的事。所幸的是，在实际应用中，根据其物理或工程的背景，

12、在绝大部分场合是不困难的。对给定的函数也有一些确定范围的方法。 P75 复习题习题 3.7 P84 习题习题 3.14P113 习题习题 4.2 See you next timeSee you next time！第四章第四章 非线性方程数值求解非线性方程数值求解 4.2 不动点迭代法及其收敛定理 迭代法是求解非线性方程近似根的一种方法，这迭代法是求解非线性方程近似根的一种方法，这种方法的关键是确定迭代函数种方法的关键是确定迭代函数 (x)(x)，简单迭代法，简单迭代法 用直接的方法从原方程中隐含地求出用直接的方法从原方程中隐含地求出x x，从而确定，从而确定迭代函数迭代函数 (x)(x)，

13、这种迭代法收敛速度较慢，迭代，这种迭代法收敛速度较慢，迭代次数多，因此常用于理论中次数多，因此常用于理论中,Newton,Newton迭代法采用另迭代法采用另一种迭代格式一种迭代格式, , 具有较快的收敛速度，由具有较快的收敛速度，由牛顿迭牛顿迭代法可以得到很多其他迭代格式代法可以得到很多其他迭代格式。迭代法求非线性方程的根简单迭代法简单迭代法( (基本迭代法基本迭代法) ):( )0 ( )(f xxxf建立改写， 连续）01 ,.)2 , 1 , 0( )(xnxxnn取取定定初初值值 *121 ,.,., nnx xxxx则产生数列若收敛，设极限为，则迭代法的建立与收敛性迭代法的建立与收

14、敛性*1limlim () ()nnnnxxxx*1( )0,nxf xnx即 是之根，故当 充分大时可作为近似值（1）需要讨论的问题首先期望每个首先期望每个xk都在都在 (x)的定义域上的定义域上,保持有界保持有界而且收敛到精确解而且收敛到精确解;如何选取适合的迭代函数如何选取适合的迭代函数 (x);迭代函数迭代函数 (x)迭满足什么条件迭满足什么条件,迭代序列收敛到迭代序列收敛到精确解精确解,收敛速度如何收敛速度如何;怎样加速序列怎样加速序列xk的收敛速度的收敛速度.且满足上连续在设迭代函数,)(bax;)(,)1(bxabax时当有且满足存在一正数,10,)2(baxLL1 .( ) ,

15、 *oxa bx则 函数在上存在唯一的不动点012 . , ,()*okkxa bxxx对于任意初值迭代法均收敛于13 .*1okkkLxxxxL104 .*1kokLxxxxL(压缩性):条件条件(2)可用更强更便于应用的条件代替可用更强更便于应用的条件代替:（映内性）(2)(3)1212()()xxL xx),(1| )(|baxLx则则设设),x(x)x(g 00 )b(b)b(g,)a(a)a(g*x , , g()0,:( ),| |()( ) |,(1L) | 0,| 0,( )a,b .a bxyyyxyxyL xyxyxyxxx故至少有一个根使若另有根 则所以从而即在内有唯一解

16、9：设方程 在区间 内有根 ， 则有 由故据此反复递推有故当 时迭代值 ,即证.)(xxba,*x)(1kkxx| )()(|*1xxLxxxxkkk)(*xx*1xxLxxkk*0*xxLxxkk02k*xxk10 00*111*111110*1134 :()()(1)11L()()1L1L1LkkkkkkkkkkkkkkkkkkkkkkkkxxxxxxxxxxxxL xxLxxxxxxxxxxL xxL xxxxxxxx于是可得 同时注意到故可得继续利用前面的递推公式,可得最后一个估计式.指出指出:只要构造的迭代函数满足只要构造的迭代函数满足1| )(|Lx就收敛迭代法)(1kkxx11k

17、kxxLL由由(2)式式, 只要只要因此因此,当当 LLxxkk11迭代就可以终止迭代就可以终止,可以作为方程的近似解kx对于预先给定的误差限|*|xxk即要求注注：L L越小，收敛越快。越小，收敛越快。n改进条件：*k01L1110L1-L2(),:kkxxxx当时, 即时由相邻两次迭代值的误差控制通常算法中采用,.当时 迭代结束11111,kkkkkkkxxxCxxxCxn改进条件：01111L121L0, 使使*1*| (0)|lim|npnnxccxxx 则称序列则称序列是是 p阶阶收敛收敛, 相应的迭代法称为相应的迭代法称为p阶方法阶方法. 特别地特别地, p = 1, 称线性收敛称

18、线性收敛; 1p1),则利用m构造新的迭代公式: 此时, , 至少2阶收敛. 不实用: m往往不确定.方法二方法二. 取 ,再对函数F(x)用Newton迭代:此时,X*为F(x)的单根,所以至少是2阶收敛. 但要用到二阶导数.1()()kkkkf xxxmfx( )*( )( ),()0f xfxxxmx( )( )( )f xF xfx12()()()()()()()kkkkkkkkkkF xf xfxxxxF xfxf xfx)()(1kkkkxfxfxxNewtonNewton迭代法迭代法需要求每个迭代点处的导数需要求每个迭代点处的导数 f (xk)复杂！复杂！得中的近似替代用,)(0

19、kkxxfx)()(01xfxfxxkkk这种格式称为这种格式称为简化简化NewtonNewton迭代法迭代法精度稍低精度稍低则则NewtonNewton迭代法变为迭代法变为)()()()(111kkkkkkkxxxfxfxfxx这种格式称为这种格式称为弦截法弦截法( (割线法割线法) )（书（书P111 P111 例题例题4.74.7）收敛阶约为收敛阶约为1.6181.618)(kxf 如果用数值导数代替11)()()(kkkkkxxxfxfxf用简化用简化Newton法和弦截法解下面方程的根，并和法和弦截法解下面方程的根，并和Newton 迭代法比较迭代法比较0133xx13)(3xxxf

20、设33)(2xxf由简化由简化Newton法法)()(01xfxfxxkkk3313203xxxxkkk由弦截法由弦截法)()()()(111kkkkkkkxxxfxfxfxx由由Newton迭代法迭代法)()(1kkkkxfxfxx331323kkkkxxxxx0= 0.5x1= 0.3333333333x2 = 0.3497942387x3 = 0.3468683325x4 = 0.3473702799x5 = 0.3472836048x6 = 0.3472985550 x7 = 0.3472959759x8 = 0.3472964208x9 = 0.3472963440 x10 = 0.

21、3472963572x11 = 0.3472963553x0=0.5;x1=0.4;x2 = 0.3430962343x3 = 0.3473897274x4 = 0.3472965093x5 = 0.3472963553x6 = 0.3472963553简化简化Newton法法由弦截法由弦截法要达到精度要达到精度10-8 简化简化Newton法迭代法迭代11次次弦截法迭代弦截法迭代5次次Newton迭代法迭代迭代法迭代4次次x0 =0.5;x1 =0.3333333333x2 =0.3472222222x3 =0.3472963532x4 =0.3472963553由由Newton迭代法迭代法

22、无论哪种迭代法：无论哪种迭代法：NewtonNewton迭代法迭代法简化简化NewtonNewton法法弦截法弦截法00 *x,)xarctan()x(f精精确确解解用用NewtonNewton迭代法求解迭代法求解: :)1(arctan21kkkkxxxxx0 = 2x1 = -3.54x2 = 13.95x3 = -279.34x4 = 122017是否收敛均与初值的位置有关是否收敛均与初值的位置有关. .20 x若若取取初初值值x0 =1x1 = -0.5708x2 = 0.1169x3 = -0.0011x4 = 7.963110-10 x5 = 0收敛收敛发散发散10 x若若取取初初值值牛顿下山法牛顿下山法 一般地说，牛顿法的收敛性依赖于初值 的选取，如果 偏离 较远，则牛顿法可能发散。 为了防止发散，通常对迭代过程再附加一项要求，即保证函数值单调下降： 满足这项要求的算法称为下山法下山法。 牛顿下山法牛顿下山法采用以下迭代公式：其中 称为下山因子。 1kkf xf x011kkkkf xxxfx0 x0 x*x牛顿下山法只有线性收敛牛顿下山法只有线性收敛.第四章第四章 非线性方程数值求解非线性方程数值求解略略- 4.4 Aitken加速方案/Steffensen迭代法简单迭代公式的加速简单迭代公式的加速 设 是根