第二讲计算方法方程求根

1、第二章第二章 方方 程程 求求 根根主要内容主要内容1。二分法。二分法2。迭代法。迭代法3。牛顿法。牛顿法4。割线法。割线法 2.1 引 言 一一. 问题问题 ( )0f x 求解非线性方程 代数方程代数方程超越方程超越方程-1-1100 0nnnnna xaxa xaa（） sin0 xex例如对于超越方程，一般而言必须用数值方法求它的解。对于超越方程，一般而言必须用数值方法求它的解。求根问题包括：根的存在性、根的范围和根的精确化。求根问题包括：根的存在性、根的范围和根的精确化。( )0( )( )( )f xf xf xf x方程的根又称为函数的零点。若是多项式，方程称为代数方程；若是超越

2、函数，方程称为超越方程；(1)( )*( *)0,( *)0,*( )0( *)( *)( *)0( *)0*( )0kkxf xfxxf xf xfxfxfxxf xk若满足但则称为方程的单根。一般地，若，但，则称为方程的 重根。单根与重根单根与重根关于代数方程，有代数学基本定理：关于代数方程，有代数学基本定理：n次代数方程有次代数方程有n个根（实根与复根）。现在理论上已证明，对于次数个根（实根与复根）。现在理论上已证明，对于次数n=5的多项式方程的多项式方程,它的根一般不能用解析表达式表示。它的根一般不能用解析表达式表示。常用的求根方法分为区间法和迭代法两大类。常用的求根方法分为区间法和迭

3、代法两大类。求根方法中最直观最简单的区间方法是二分法。求根方法中最直观最简单的区间方法是二分法。二二. 方法方法 2.2 二 分 法 一一. 二分法的原理与步骤二分法的原理与步骤 ( ) , ( )( )0 ( )0 , f xa bf af bf xa b设在上连续，且满足，则根据介值定理，在必有根。假设仅有一个根，则可采用如下二分法（对分法）。 ( )0, ( )0f af b不妨设11111111 , 0 * ; 0 22 . , .22ababxfxxxfabababbbaa） 取若输出根否则：若，则令，反之，令1111 ,* ,2baa bxa b于是得区间，区间长度为且。11222

4、) , 1*, , ,.nna bxa ba b对区间重复 ）的计算，要么得到要么 产生nnn+13) xx*2ab取=作为根的近似值。.2nnnbaba此时区间长度为11*22nnnnbabaxx此时的误差有如下的估计式：14) 2nban当给定误差限 时，可根据不等式确定 。二二. 二分法的优缺点二分法的优缺点 二分法对函数要求不高，计算过程简单，程序容易二分法对函数要求不高，计算过程简单，程序容易实现，可在大范围内求根。但该方法收敛较慢实现，可在大范围内求根。但该方法收敛较慢,且不能求且不能求重根和复根。重根和复根。32 x101.01 510 x 用 二 分 法 求 方 程在(, .

5、)内 的 根 ， 要 求 误 差 不 超 过。解：解：332( )1, (1.0)10, (1.5)1.51.5 101.0, 1.5( )310, f xxxffxfxx 取，且当时，方程有唯一根。1110.51022ln0.52ln1014.6. 5.ln2nnbann 根据不等式，得到 ，解得 取nanbnXn+1f(xn+1)的符号01.01.51.25-11.251.51.375+21.251.3751.3125-31.3125 1.3751.3438+41.3125 1.3438 1.3281+51.3125 1.3281 1.3203-.2nnba也可以事后估计误差.采用公式 2

6、.3 迭 代 法 一一. 迭代法的基本思想迭代法的基本思想1()kkxx( )0f x ( )xx（1）（2） 构造递推公式 011, NNNnxNxxxx选取一个 ，若有某个 ，满足则是方程的根，否则得到序列。（3）（4）* *x (0 limnnnxxf xxx 若 ( )连续，且收敛，即，则是方程）的根.*1 = limlim ()(lim)()kkkkkkxxxxx原因：迭代函数迭代函数迭代格式迭代格式迭代序列迭代序列迭代收敛迭代收敛二二. 迭代法的几何意义迭代法的几何意义 ) yxy(x的交点横坐标。( )xx的根012*xxxxO)(xyxy 0231*xxxxxO)(xyxy 上

7、述两图均为迭代收敛的情况上述两图均为迭代收敛的情况*( *)*( )xxxx若有成立，则称为的一个不动点。*012xxxxO)(xyxy 2013*xxxxxO)(xyxy 上述两图为迭代发散的情况上述两图为迭代发散的情况2( )1603.531 128 9f xxxx 用迭代法求方程的根（可以解得方程的一个根是 ）.从上面的图中可以看出，并不是每一个迭代都能够得到方从上面的图中可以看出，并不是每一个迭代都能够得到方程的根。程的根。 收敛充分性定理(一、1) 221616116; (2) ; (3) 121xxxxxxxxx（）分别取如下三种不同的迭代函数分别取如下三种不同的迭代函数0 x3,

8、 取相同的初值迭代计算后结果如下表：k0123456789(1)37-33-1073-1 151 313(2)343.23.8103.3263.6993.4053.6323.4543.592(3)33.5713.531迭代法要考虑的问题：收敛性，收敛速度，误差估计迭代法要考虑的问题：收敛性，收敛速度，误差估计定理1.三三. 迭代法的收敛性迭代法的收敛性( ) , ,xa b设迭代函数在上有一阶连续导数 且满足;)(,)1(bxabax时当(2),01, , ,LLxa b 存在数满足且有Lx|)(|*,)(.1xbaxxo内有唯一解在方程则*)(,.210 xxxbaxkko均收敛于迭代法对于

9、任意初值11*.3kkkoxxLLxx011*.4xxLLxxkko(全局收敛性)证:由条件(1)o1( )( ),g xxx 设( )( )g aaa0( )( )g bbb0( ) , g xa b则在上连续可导由介值定理由介值定理,( )0 , f xa b方程在上至少有一个根。1|)(|Lx由由( )1( )gxx0( ) , ,( )0 , ( ) , *g xa bg xa bxxa bx则在上单调递增 所以在上仅有一个根，即方程在内有唯一解。知知),(.21kkoxx对于迭代法12110|*| |()( *)| |( )(*)| |(*)|(*)| |(*)| 0 ().kkkk

10、kkxxxxxxLxxLxxLxxk 由微分中值定理由微分中值定理o113 *()()()( *) *kkkkkkkxxxxxxL xxL xx1 *1kkkLxxxxL所以，o112124 ()() kkkkkkxxxxL xx由于211210*11 1kkkkkkLLxxxxxxLLLxxL所以证毕.问题：迭代过程何时停止？问题：迭代过程何时停止？11kkxxLL11 kkLxxL即|*|kxx预先给定的误差限 ，即要求时在事后估计法中，如果迭代次数超过预先指定的次数在事后估计法中，如果迭代次数超过预先指定的次数N，仍达不到精度要求，则认为方法发散。仍达不到精度要求，则认为方法发散。 事后

11、估计法事后估计法事前估计法事前估计法 101kLxxL10(1) ln/ lnLkLxx即因此迭代格式 收敛。用迭代法求方程的近似解用迭代法求方程的近似解,精确到小数点后精确到小数点后6位位0210 xex解:迭代函数采用如下构造形式迭代函数采用如下构造形式102)(1xexx|)(|1x10 xe,0 xe由于1021时为时为超线性收敛的超线性收敛的， p=2时为时为平方收敛平方收敛或二次收敛。显然，或二次收敛。显然，p越大，迭代收敛的越大，迭代收敛的速度越快。速度越快。定理定理3 对于迭代过程对于迭代过程 如果迭代函数如果迭代函数 1,kkxx 在所求根在所求根 的邻近有连续的二阶导数，且

12、的邻近有连续的二阶导数，且 xx则有则有1,x （1）当）当 时，迭代过程为线性收敛；时，迭代过程为线性收敛；0 x（2）当）当 时，迭代过程为平方收敛；时，迭代过程为平方收敛；0,0 xx而证明 11(1) kkkkexxxxxx 由 1 =0 kkexcke 得。故该迭代过程为线性收敛。故该迭代过程为线性收敛。 (2) 0,kxxx若将在根 处作泰勒展开得 2212! 2!kkkkkxxxxxxxxxxx 12 =0 2!2!kkxecke 所以，。即迭代过程为平方收敛。即迭代过程为平方收敛。三、迭代法的加速三、迭代法的加速11 ()*( *)()( )( *)kkkkkxxxxxxxx

13、令，则 1( )( )*( *)kkxxLxxL xx若在求根范围内变化不大，近似取，则 11*11kkLxxxLL移项整理得，111k 11()111kkkkkLLxxxxxxLLL若取迭代格式： 则有理由认为 是一个比 更好的近似值。1kx1kx迭代加速公式111k 1() ()1kkkkkxxLxxxxL上面的公式也可以看作由下面方法得到上面的公式也可以看作由下面方法得到 ,1.xxLxL xxLx将两边同时减去得01 ,LL于是，当和时 可得 1.1xxLxL取相应的迭代公式为取相应的迭代公式为11,1kkkxxLxL上式还可以写为上式还可以写为11kkkkLxxxxL分别用迭代法和加

14、速收敛的方法求方程分别用迭代法和加速收敛的方法求方程xxe解:0.5( ),(0.5)0,(0.6)0,0.5,0.6. 0.5,0.6|( ) |0.6071.xxf xxeffxxee设为有根区间当时， 在在x=0.5附近的近似解附近的近似解,精确到小数点后精确到小数点后3位位0111111x0.5 -0.60.6()1.6kkxkxkkkkkkxexeLxxxxx取迭代初值，则当分别取迭代格式 迭代加速格式() 计算结果如下页表格所示计算结果如下页表格所示 迭代 迭代加速 kxk k xk00.50000.50010.60710.56720.54520.56730.580340.5604

15、50.571560.565670.568780.567890.5679埃特金埃特金(Aitken)加速收敛方法加速收敛方法,()()kkkkkxyxzy考虑对于某个作迭代 ， *( *)()( *)*( *)()( *)kkkkkkxyxxL xxxzxyL xy则 ， *,*kkkkxyxxxzxy于是有 22*22kkkkkkkkkkkkzyz xyxzzyxzyx解得 212kkkkkkkzyxzzyx 称为埃特金迭代格式。可证明是二阶收敛方法斯蒂芬森斯蒂芬森(Steffensen )迭代格式迭代格式222*22 =2kkkkkkkkkkkkkkkkkkzyz xyxzzyxzyxxyx

16、xyz实际上前面的表达式还可以写成如下形式 于是可得到所谓的于是可得到所谓的斯蒂芬森斯蒂芬森迭代格式迭代格式21y(), z(y ),2kkkkkkkkkkkxxyxxxyz显然，斯蒂芬森迭代法也是二阶收敛的方法。显然，斯蒂芬森迭代法也是二阶收敛的方法。 2.5 牛 顿 法一、牛顿法迭代格式的建立一、牛顿法迭代格式的建立牛顿法实际上是一种线性化方法。牛顿法实际上是一种线性化方法。1()()kkkkf xxxfx *( )0( )0()0)( *) ( *)() ()*kkkkkkxf xxf xfxf xxf xf xfxxx设是方程的根， 是方程的近似根。将在点 展开，有（）() ()*0k

17、kkf xfxxx于是有 （）()*()kkkf xxxfx解得 这就是牛顿法迭代格式这就是牛顿法迭代格式1nx牛顿法在局部至少是平方收敛的方法牛顿法在局部至少是平方收敛的方法，这是因为，这是因为2( )( )( )( ), ( ) ( *)0( )( )f xf x fxxxxxfxfx二、牛顿法的几何意义二、牛顿法的几何意义,()( ) ()() ()nnnnnxf xyf xyf xfxxx过点作曲线的切线，其方程为x此切线与 轴的交点横坐标为() ()nnnf xxxfx), 2 , 1 , 0( )( )(1nxfxfxxnnnn牛顿法也可以通过以下方法得到牛顿法也可以通过以下方法得

18、到 ( )0( ) ( ),( )0( )( ) ( )( )1( ) ( )( )( )f xxxk x f xk xxxk x f xxk x f xk x fx 其中令，则*( )0, |( )|*, ( *)0( *)0 1( *) ( *)( *)( *)0 xf xxxfxxk xf xk xfx设为的根 则在附近越小 收敛速度越快，如果，令，即11 ( *)( )( *)( )k xk xfxfx进而得，1()( ) ( ) ( )()kkkkf xf xxxxxfxfx于是三、牛顿法的收敛性定理三、牛顿法的收敛性定理 2040( )( )0 1, ( )0,kxf xxf x

19、fxfxLfxxxxxx定理 设 是方程的根，若在包含 的某个开区间内，且则存在，当时，由牛顿迭代法产生的迭代序列收敛于 。1()()nnnnf xxxfx2( ) ( ), ( )( )( ) ( )( )f xxxfxf x fxxfx 0005,1 0;2 0,3;4 ,0,f x0,kfxa bfaf bfxfxxa bfxfxxa bx定理 设在上满足下列条件：存在且不改变符号选取使则由牛顿迭代法产生的序列收敛于 ( )= 在上的唯一根 。Newton(0 ,2c cc用迭代法求） 并就进行迭代计算。22,0, ( )xcxcf xxc设则取则由牛顿迭代格式则由牛顿迭代格式211()

20、,22nnnnnnxccxxxxx1122(),2nnncxxx当时，012341,1.500 000 0001.416 666 667,1.414 215 6861.414 213 562xxxxx取得 ，与精确值的前十位已经完全相同与精确值的前十位已经完全相同解解1、优点：牛顿迭代法具有平方收敛的速度，所以在迭代过程中只要迭代几次就会得到很精确的解。这是牛顿迭代法优越的地方。四四. 牛顿迭代法的优缺点牛顿迭代法的优缺点2、缺点：选定的初值要接近方程的解，否则有可能得不到收敛的结果。再者，牛顿迭代法计算量比较大，因每次迭代除计算函数值外还要计算微商值。 2.6 割线法及牛顿法的其它变形)()(1kkkkxfxfxxNewton迭代法需要求每个迭代点处的导数)(kxf 计算量增大得中的近似替代用,)(0kkxxfx)()(01xfxfxxkkk