非线性方程求根方法分解PPT课件

1、1历史背景 代数方程的求根问题是一个古老的数学问题。理论上，n次代数方程在复数域内一定有 n个根(考虑重数)。早在16世纪就找到了三次、四次方程的求根公式，但直到19世纪才证明大于等于5 5次的一般代数方程式不能用代数公式求解，而对于超越方程就复杂的多，如果有解，其解可能是一个或几个，也可能是无穷多个。一般也不存在根的解析表达式。因此需要研究数值方法求得满足一定精度要求的根的近似解。第1页/共48页2根的概念 给定方程 f (x)=0，如果有a使得f(a)=0，则称a为 f(x) =0的根 或f(x)的零点. 设有正整数m使得f(x)=(x-a)mg(x)且g(a) 0 ， 则当m=2时，称a

2、为f(x)=0的m重根； 当m=1时，称为f(x)=0的单根. 本章只讨论实根的求法.第2页/共48页3 重点介绍求解非线性方程的几种常见和有效的数值方法, 简单介绍一些最基本的解法.无论在理论上,还是在实际应用中,这些数值解法都是对经典的解析方法的突破性开拓和补充,许多问题的求解,在解析方法无能为力时,数值方法则可以借助于计算机出色完成.第3页/共48页4 零点定理： 设 ，且 ，则方程 在区间 上至少有一个根。如果 在 上恒正或恒负，则此根唯一。2( ) , 4f xC a bbac-( ) ( )0f a f b 0是给定的步长，取 ，若 则扫描成功；否则令 ，继续上述方法，直到成功。如

3、果 则扫描失败。再将h 缩小，重复以上步骤。01,xa xah=+01()()0f xf x第5页/共48页6例题 例 设方程 解：取h=0.1,扫描得： 又 即 在 有唯一根。 3( )1, , 1,2f xxxa b=-=(1.3)0.610(1.4)0.3440ff= -1.3,1.4. 方程的有根区间为2( )310,1.3,1.4fxxx=- ( )0fx=4 . 1 , 3 . 1 第6页/共48页7 设有非线性方程 f (x) =0其中， f (x)为 a ,b 上连续函数且设 f (a) f (b)0不妨设方程于 a ,b 内仅有一个实根。求方程实根 x* 的二分法过程，就是将

4、含根区间 a ,b 逐步分半，检查函数符号的变化，以便确定含根的充分小区间。二分法第7页/共48页8示意图ba1b2x*ab1a2第8页/共48页9二二分法的步骤分法的步骤 用二分法(将区间对平分)求解。 令 若 ，则 为有根区间，否则 为有根区间 记新的有根区间为 ， 则 且 1111112,()aa bb cab=+11( ) ( )0f a f c,11ca,11bc,22ba,2211baba122112()baba-=-第9页/共48页10二分法 对 重复上述做法得 且 ,22ba.,.,2211nnbababa11()2nnnbaba-=-第10页/共48页11 设 所求的根为 ，

5、 则 即 取 为 的近似解，则 1()2nnnxab=+x*,1,2.nnxa bn*=1,2.nnaxbn*=n 11lim()lim()02nnnnbaba-=-=limlimnnnnabx=*x*2nnbaxx-第11页/共48页12 323n( )410011,2,10 .2f xxxxx*-=+-=-=3n111111()0.0004882811022xxba*-=例 讨论以下计算的算法的收敛阶。第23页/共48页24 1(1)( )()2axxxj=+()12aaaaaj骣琪=+=琪桫21( )(1)2axxj=-()0aj=解：解：3( )axxj=1()0aaj=从而知(1)是

6、平方收敛的。第24页/共48页25证：考虑迭代格式01020,1,2,.kkxxxk+=+=，122222.22 .2kkxxx=+=+个则2lim22 .22kk+=个例利用适当的迭代格式证明第25页/共48页26 1( )2( )2 2xxxxff=+=+记，则0,2( ) (0), (2) 2,20,2xxfff挝=当时，0*20,22kkxxxx=+=因而由迭代格式产生的序列收敛于方程在内的唯一根，1|( )|(0)12 2xff=1重根，则此时Newton法仅有线性收敛速度. ( )( )( )f xxxfxj=-2( )( )( )( )f x fxxfxj=( )0fx=x*x*

7、( )0f x =x*( )*xf0( )*1011xmf= -第30页/共48页31Newton法收敛的充分条件2000*11( ),(1)( ) ( )0;( ),(2)( )( )0,( )(3)()()0,( )0,( )0limnnnnf xCa bf a f bf xa bfx fxxa bf xfxf xfxxa bxxa bfxf xa bxxf xxffee+$-定理 设满足【在内有根】，【的根唯一,凹向不变】（ ），【 ( )=】（ ）则 在上有且仅有一个实根；迭代公式（） 收敛于 的根。且*122*lim.2nnnnxxfxfxxx+=轾臌（）（）第31页/共48页32N

8、ewton迭代法收敛性证明： 根的存在性 根的唯一性(1)( ) , ,( )0( , )fxC a bfxa b=由条件及知在内至少有一个根。*( )0,( )Ca,b,( )( ) , ( )0( , ),fxfxfxf xa bf xa bx刮=由及知保号，故是上严格单调函数，因此在内有唯一根 记此根为。第32页/共48页0*00001000200000*00000( )0()0,( )0( )0( )0( )()0( )0()01( )()()()()()2()1(2f afxxa bf af bfxf xxxfxfxf xfxxxxfxf xf xxxfxxxffxfxxxxfxfx

9、xx揶-=+-+-=-就其四种可能情况之一证明如下：，严格单增；（）（）（）（）（）2*2001010*1*2*201010*11()1)()2()()11()()22limlimkkkkkkkkkkkkkkkkkkkkknnkkfxxxxfxfxxxxxfxffxfxxxxxxxxxfxfxfxfxfxxxxxxxfxfxxxx+=-=-=-=-例 用牛顿法求并说明算法的收敛阶。第36页/共48页37牛顿阶导数法( )( )( )( )( ) ( )( )()()()()222222222122222222 22323333nnnnfx fxxxfxfx fxxaxxxxxax xaxaxx

10、axaxxaxxaff+=-轾-臌-=-+-=-=+=+（ ） 牛顿 阶导数法由前例可知其为阶收敛。第37页/共48页382.5 割线法几何示意图(a) 单点割线法 (b) 变端点弦截法 第38页/共48页392.5 割线法Newton迭代法有一个较强的要求是 存在且 ,因此用弦的斜率近似的替代 。得弦的方程及则过)(,(P)(,(P111000 xfxxfx( )0fx( )fx*01( ) , ,f xa bxxa xb=设在上有唯一零点，取101110()()()()f xf xyf xxxxx-=+-( )fx第39页/共48页40割线法解得弦与 轴的交点是坐标 1021110()()

11、()xxxxf xf xf x-=-解得1012110()()()()0fxfxfxxxxx-+-=-.,320 xxx计算再由010()(1,2,.)()()nnnnnxxxxf xnf xf x+-=-=-x2x.端点弦截法称之为单点割线法、定第40页/共48页41割线法111()(1,2,.)()()nnnnnnnxxxxf xnf xf x-+-=-=-以此类推计算若由,321xxx0101()()()()(1,2,.)() (1,2,.)nnnnnnnf xf xf xf xnxxxxfxn-=-=即分别以与代替。.,又称快速弦截法端点弦截法称之为双点割线法、变第41页/共48页42

12、例 用双点割线法求方程在区间 内的实根。解：取 代入公式 计算结果,如下表所示：3( )10f xxx=- =2 , 1 011,2xx=111()(1,2,.)()()nnnnnnnxxxxf xnf xf x-+-=-=-第42页/共48页kxkf(xk)01-112521.166666667-0.5787036931.253112023-0.2853630241.337206444 0.05388057951.323850096-0.003698116861.324707936-4.273521*10E-571.3247179653.79*10E-8第43页/共48页44割线法收敛的速度

13、010*(1)()1,2,.()();nnnnnnxxxxf xnf xf xxx+-=-=-由确定的序列线性收敛到111*(2)()1,2,.()()5 11.618,2nnnnnnnnxxxxf xnf xf xxpx-+-=-=-+=由确定的序列以的敛速收敛到即为超线性收敛的。*2*0, , ,( ) , ,( )0a bxxf xCa bxf xddd$D-+定理设有为 的根，则第44页/共48页45将Newton迭代中的导数，用差商代替，有格式111()()()kkkkkkkxxxxf xf xf x-+-=-是2步格式。收敛速度比Newton迭代慢x0 x1割线 切线第45页/共48页4611.618nneMe+=x0 x1切线切线 割线 2*(),()fxKfx 11limkqqkkeKe 1151 6182().q 第46页/共48页47001110111020110112111010101010*2(,(),(,()()()()()0,()()()()()()()()()()()()ABA xf xB