第二章非线性方程求根

《第二章非线性方程求根》由会员分享，可在线阅读，更多相关《第二章非线性方程求根（66页珍藏版）》请在金锄头文库上搜索。

1、第二章 非线性方程求根1 1 二分法二分法2 2 简单迭代法简单迭代法3 3 牛顿迭代法牛顿迭代法4 4 迭代法的收敛阶与加速收敛方法迭代法的收敛阶与加速收敛方法11. 二分法二分法1.1 问题的提出问题的提出1.2 有关概念有关概念1.3 二分法原理二分法原理1.4 程序框图程序框图1.5 收敛性分析收敛性分析1.6 二分法的优缺点二分法的优缺点1.7 例题求解例题求解1.8 二分法与跨步区间法求方程的全部实根二分法与跨步区间法求方程的全部实根21.1 问题的提出：问题的提出： 函数方程函数方程若若 不不是是x的线性函数的线性函数, 则称则称(1)为为非线性方程非线性方程 , 特特别若别若

2、是是n次次多项式，则称多项式，则称(1)为为n次次多项式方程多项式方程或或代数方程代数方程；若；若 是超越函数，则称是超越函数，则称(1)为为超越方程超越方程。 理论上已证明理论上已证明，对于次数，对于次数n=5的多项式方程，它的多项式方程，它的根可以用公式表示，而次数大于的根可以用公式表示，而次数大于5的多项式方程，的多项式方程，它的根一般不能用解析表达式表示。它的根一般不能用解析表达式表示。3 因此对于因此对于 的函数方程，一般来说，不的函数方程，一般来说，不存在根的解析表达式，而实际应用中，也不一定必存在根的解析表达式，而实际应用中，也不一定必需得到求根的解析表达式，只要得到满足精度要求

3、需得到求根的解析表达式，只要得到满足精度要求的根的近似值就可以了。的根的近似值就可以了。求根方法中最直观最简单的方法是二分法。求根方法中最直观最简单的方法是二分法。4 求根问题包括：根的存在性、根的范围和根的精求根问题包括：根的存在性、根的范围和根的精确化。确化。 根的存在定理根的存在定理 假设函数假设函数 ,且且 , 函数函数图象图象如图如图1所示，所示，则至少存在一点则至少存在一点 使得使得 ,这就是根的存在定理。这就是根的存在定理。 1.2 有关概念有关概念 二分法二分法就是将方程的有根区间对分就是将方程的有根区间对分,然后再选择比然后再选择比原区间缩小一半的有根区间原区间缩小一半的有根

4、区间,如此继续下去如此继续下去,直到得到直到得到满足精度要求的根为止的一种简单的区间方法。满足精度要求的根为止的一种简单的区间方法。 5 yxba图一 函数方程函数方程 的解通常的解通常称为方程的称为方程的根根或函数或函数 的的零点零点，特别地，如果函数，特别地，如果函数 可分解为可分解为 且且 , 则称则称 是是 的的 重零点或重零点或 的的 重根。重根。 当当 时，称时，称 是是 的单的单根根 或单零点。或单零点。67 1.3 二分法原理二分法原理 给定方程给定方程 ,设设 在区间在区间 连续连续,且且 ,则方程则方程 在在 内至少内至少有一根有一根,为便于讨论为便于讨论,不妨设方程不妨设

5、方程 在在 内只有一实根内只有一实根 ，采取使有根区间逐步缩小，采取使有根区间逐步缩小,从从而得到满足精度要求的实根而得到满足精度要求的实根 的近似值的近似值 。 8 取取区间区间 二等分的中点二等分的中点 ， 若若 ,则则 是是 的实根；的实根； 若若 成立成立,则则 必在区间必在区间 内内,取取 ;否则否则 必在区间必在区间 内内,取取 , 这样这样,得到新区间得到新区间 ，其长度为，其长度为 的一半的一半,如如此继续下去此继续下去,进行进行 次等分后次等分后,得到一组不断缩小的区得到一组不断缩小的区间间 。 其中每一个区间都是其中每一个区间都是前一个区间长度的一半前一个区间长度的一半,从

6、而从而 的长度为的长度为9 如此继续下去，则有这些区间将收敛于一点，该如此继续下去，则有这些区间将收敛于一点，该点即为所求的根。点即为所求的根。当做到第当做到第 步时，有步时，有 为给定为给定精度精度 此时此时 即为所求方程的近似解即为所求方程的近似解. 以上方法就是用于求非线性方程实根近似值的二以上方法就是用于求非线性方程实根近似值的二分法。用二分法求方程分法。用二分法求方程 在区间在区间 内近似内近似根的程序框图根的程序框图如图如图2 ， 表示各有根区间的左右两表示各有根区间的左右两端点端点; 为二分次数为二分次数, 为允许误差为允许误差;当当 时时,终止运算终止运算10 图2 1.4 程

7、序框图程序框图11现在来研究用二分法求函数的根时的精确性。假定现在来研究用二分法求函数的根时的精确性。假定 是连续函数，并且它在区间是连续函数，并且它在区间 的的两端点两端点 所取的所取的值有相反的符号，于是在值有相反的符号，于是在 中有一个根中有一个根 ，如果如果用中点用中点 作为对作为对 的估计，则有的估计，则有 。 现在应用二分算法，现在应用二分算法，经过经过n步后步后将算出一个近似根将算出一个近似根其误差至多为其误差至多为其中其中1.5 收敛性分析收敛性分析12 二分法计算过程简单，程序容易实现。二分法计算过程简单，程序容易实现。可在大范围内求根，但该方法收敛较慢，且可在大范围内求根，

8、但该方法收敛较慢，且不能求偶数重根和复根，一般用于求根的初不能求偶数重根和复根，一般用于求根的初始近似值，而后在使用其它的求根方法。始近似值，而后在使用其它的求根方法。 二分法收敛速度不快，其收敛速度仅与二分法收敛速度不快，其收敛速度仅与一个以一个以 1/2为比值的等比级数相同为比值的等比级数相同 。 1.6二分法的优缺点二分法的优缺点131.7例题求解例题求解 例1：用二分法求方程 在区间 内的实根,要求误差限为 。解：令 因为 得 得.14 例2，求方程f(x)= x 3 e-x =0的一个实根。 因为 f(0)0。 故f(x)在(0,1)内有根用二分法解之，(a,b）=（0,1)计算结果

9、如表：ka bk xk f(xk)符号00 1 0.5000 10.5000 0.7500 20.7500 0.8750 3 0.87500.8125 4 0.81250.7812 5 0.7812 0.7656 60.7656 0.7734 7 0.7734 0.7695 8 0.7695 0.7714 90.7714 0.7724 100.7724 0.7729 取x10=0.7729，误差为| x* -x10|=1/211 。 15 如果我们把如果我们把二分法二分法与与跨步区间法跨步区间法结合起来结合起来,就可以求就可以求非线性方程在任一区间上的全部实根。非线性方程在任一区间上的全部实根

10、。 首先首先, 将方程式将方程式f(x)=0化为函数式化为函数式y=f(x).假设方程求假设方程求解区间为解区间为x a,b ,跨步区间为跨步区间为h长长,允许误差为允许误差为 。如图如图3所示所示,由由a点出发向点出发向 b点跨步点跨步,每跨一步每跨一步h,经过判断在该区经过判断在该区间内是否有根。如有根则进行二分法求根计算间内是否有根。如有根则进行二分法求根计算,否则继续否则继续以以h为步长向前跨步找根为步长向前跨步找根,直到走出区间直到走出区间a,b为止为止 。这样。这样 ,我们就可以按顺序将方程的全部我们就可以按顺序将方程的全部实根找出。实根找出。 1.8 二分法与跨步区间法求方程的全

11、部实根二分法与跨步区间法求方程的全部实根16 但应注意在计算中步长但应注意在计算中步长h要适当取小一些要适当取小一些,若若h过长过长则容易丢根则容易丢根(若在区间范围内有两相邻函数值符号相同若在区间范围内有两相邻函数值符号相同而判定无根而判定无根),若间隔若间隔h值太小值太小,则影响计算速度。则影响计算速度。 y x a b o 图3 17二、简单迭代法二、简单迭代法-(2)将非线性方程将非线性方程 继续继续-(3)称称(3)式为求解非线性方程式为求解非线性方程(2)的的简单迭代法简单迭代法-(1)化为一个同解方程化为一个同解方程18则称迭代法则称迭代法(3)收敛收敛,否则称为发散。否则称为发

12、散。-(4)如果将如果将(2)式表示为式表示为与方程与方程(2)同解同解收敛收敛19例例3.解解:(1) 将原方程化为等价方程将原方程化为等价方程发散发散20显然迭代法发散显然迭代法发散(2) 如果将原方程化为等价方程如果将原方程化为等价方程21仍取初值仍取初值x2 = 0.9644x3 = 0.9940x4 = 0.9990x5 = 0.9998x6 = 1.0000x7 = 1.0000依此类推依此类推,得得已经收敛已经收敛,故原方程的解为故原方程的解为同样的方程同样的方程不同的迭代格式不同的迭代格式有不同的结果有不同的结果什么形式的迭代法什么形式的迭代法 能够收敛呢能够收敛呢?迭代函数的

13、构造有关迭代函数的构造有关22定理定理1.23证证:24252627定理定理1指出指出,只要只要因此因此,当当迭代就可以终止迭代就可以终止,只要构造的迭代函数满足只要构造的迭代函数满足此时虽收敛但不此时虽收敛但不 一定是唯一根一定是唯一根28例例4.用迭代法求方程的近似解用迭代法求方程的近似解,精确到小数点后精确到小数点后6位位解解:本题迭代函数有两种构造形式本题迭代函数有两种构造形式因此采用迭代函数因此采用迭代函数29d1 = 0.1000000d2 = -0.0105171d3 = 0.1156e-002d4 = -0.1265e-003d5 = 0.1390e-004d6 = -0.15

14、00e-005d7 = 0.1000e-006由于由于|d7| =0.1000e-0061e-6因此原方程的解为因此原方程的解为x7 = 0.090525x1 = 0.1000000x2 = 0.0894829x3 = 0.0906391x4 = 0.0905126x5 = 0.0905265x6 = 0.0905250x7 = 0.090525130定理定理2若存在区间若存在区间 ，使，使（1）方程）方程 在在 内内有实根有实根 ；（2） 在在 内连续且内连续且 。 则迭代法则迭代法 在在 附近具有附近具有局部收敛性（指存在局部收敛性（指存在 的一个邻域的一个邻域，使当，使当 时，时， 收敛

15、于收敛于 。31证明：证明： 因为因为 在在 内连续且内连续且 ，故在，故在 内存在内存在 的一个邻域的一个邻域 和小于和小于1的正的正数数 ，使，使 在在 上存在且上存在且 这表明，若取这表明，若取 ，则，则 在在 上满足定理上满足定理1中的条件（中的条件（1）；另一方面，当）；另一方面，当 （即（即 ）时）时（其中（其中 介于介于 与与 之间），这说明之间），这说明 在在 上又上又满足定理满足定理1中的条件（中的条件（2）。因此当）。因此当 时，时，迭代序列迭代序列 收敛于收敛于 。32例例5 5：方程 有唯一实根 ，试分析迭代过程 的收敛性。解：解：这里这里 。容易看出在区间。容易看出在

16、区间 内连续且内连续且由定理由定理2 2知，所给迭代法知，所给迭代法 在在 附近具有局附近具有局部收敛性，只要部收敛性，只要 取的好（充分接近取的好（充分接近 ），则迭代），则迭代法收敛。法收敛。33 三、三、NewtonNewton迭代法迭代法将将f(x)在初值处作在初值处作Taylor展开展开取线性部分作为取线性部分作为f(x)的近似，有：的近似，有：若若，则有，则有记为记为类似，我们可以得到类似，我们可以得到xyx*x01、牛顿迭代公式、牛顿迭代公式34这样一直下去，我们可以得到迭代序列这样一直下去，我们可以得到迭代序列Newton迭代的等价方程为：迭代的等价方程为：35例例6.用用Ne

17、wton迭代法求方程的根迭代法求方程的根:解解:由由Newton迭代法迭代法x0 =0.5;x1 =0.3333333333x2 =0.3472222222x3 =0.3472963532x4 =0.3472963553迭代四次迭代四次精度达精度达10-8 362、牛顿迭代的判定条件、牛顿迭代的判定条件定理定理3对于方程对于方程 ，若存在区间，若存在区间 ，使，使（1）在）在 内存在方程的单根内存在方程的单根 ；（2） 在在 连续。连续。则牛顿迭代法在则牛顿迭代法在 附近具有局部收敛性。附近具有局部收敛性。证明：证明：易知牛顿迭代法的迭代函数为：易知牛顿迭代法的迭代函数为：37定理定理4对于方

18、程对于方程 ，若存在区间，若存在区间 ，使，使3839Newton迭代法迭代法需要求每个迭代点处的导数需要求每个迭代点处的导数复杂！复杂！-(12)-(13)这种格式称为这种格式称为简化简化Newton迭代法迭代法精度稍低精度稍低3 弦割法弦割法 40则则Newton迭代法变为迭代法变为-(14)这种格式称为这种格式称为弦截法弦截法收敛阶约为收敛阶约为1.618几何意义几何意义41例例7.用简化用简化Newton法和弦截法解例法和弦截法解例(5)中方程的根，中方程的根，解解:由简化由简化Newton法法并和并和Newton 迭代法比较迭代法比较由弦截法由弦截法42x0=0.5x1= 0.333

19、3333333x2 = 0.3497942387x3 = 0.3468683325x4 = 0.3473702799x5 = 0.3472836048x6 = 0.3472985550x7 = 0.3472959759x8 = 0.3472964208x9 = 0.3472963440x10 = 0.3472963572x11 = 0.3472963553x0=0.5;x1=0.4;x2 = 0.3430962343x3 = 0.3473897274x4 = 0.3472965093x5 = 0.3472963553x6 = 0.3472963553简化简化Newton法法由弦截法由弦截法要达

20、到精度要达到精度10-8 简化简化Newton法迭代法迭代11次次弦截法迭代弦截法迭代5次次Newton迭代法迭代法迭代迭代4次次43无论前面哪种迭代法：无论前面哪种迭代法：Newton迭代法迭代法简化简化Newton法法弦截法弦截法Newton迭代法迭代法x0 = 2x1 = -3.54x2 = 13.95x3 = -279.34x4 = 122017是否收敛均与初值的位置有关是否收敛均与初值的位置有关如如x0 =1x1 = -0.5708x2 = 0.1169x3 = -0.0011x4 = 7.9631e-010x5 = 0收敛收敛发散发散44这种方法称为这种方法称为Newton下山法下

21、山法，45例例8.解解:1.先用先用Newton迭代法迭代法x4 = 9.70724 x5 = 6.54091 x6 = 4.46497 x7 = 3.13384 x8 = 2.32607 x9 = 1.90230x10= 1.75248x11= 1.73240x12= 1.73205x13= 1.73205迭代迭代13次才达次才达到精度到精度要求要求462.用Newton下山法,结果如下k=0 x0 =-0.99 fx0 =0.666567k = 1 x1 =32.505829 f(x) = 11416.4 w =0.5 x1 =15.757915 f(x) = 1288.5 w =0.25

22、 x1 =7.383958 f(x) =126.8 w =0.125 x1 =3.196979 f(x) =7.69 w = 0.0625 x1 =1.103489 f(x)=-0.655k = 2 x2 = 4.115071 f(x) =19.1 w = 0.5 x2 = 2.60928 f(x)=3.31 w =0.25 x2 =1.85638 f(x)=0.27k = 3 x3 =1.74352 f(x)=0.023k = 4 x4 = 1.73216 f(x)=0.00024k = 5 x5 = 1.73205 f(x)=0.00000k = 6 x6 = 1.73205 f(x)=0

23、.00000047定义1. ， -(9)4 迭代法的收敛阶与加速收敛方法迭代法的收敛阶与加速收敛方法48不可能直接确定不可能直接确定49定理定理5. 50例9.为线性收敛证明:所以51例10.至少是平方收敛的52注意例9与例10的迭代法是相同的,两例有何区别?证明:令则所以所以，该迭代法至少是平方收敛的53埃特肯加速方法5455560.6409640.6412850.6411420.6412058910110.6354980.6437190.6400610.64168645670.50.7071070.6125470.65404101230.6411850.641186230.50.63898

24、6010.6125470.6413840.6411860.7071070.6407410.6411860.50.6421880.6411860.641186012357有唯一根有唯一根有多根有多根所有根均为单根所有根均为单根有重根有重根用迭代法求解用迭代法求解然后在每个区间上判断是否有根然后在每个区间上判断是否有根58若成立统计根的个数则所有的有根区间均为单根区间则继续对分区间,并重新判断直到找到所有根的所在区间然后在每个有根区间进行求根59可得一系列的小区间和中点60小区间中点显然每个小区间都有单根搜索法二分法61例8.解:由于可知方程的解在区间0,10内将区间0,10等分成三等份0,3.333.33,6.676.67,100,3.33内至少有一个根625,6.673.33,5将3.33,6.67再分成两个区间5,6.67内至少有一个根3.33,5内至少有一个根0,3.335,6.673.33,5因此找到了三个有单根的区间依此类推结果为对分63故有且对于Newton迭代法趋于零Newton迭代法也只是线性收敛此时Newton迭代法可能不收敛64考察函数而应该用定义求导Tailor展开65所以由定理2，迭代法至少是二阶收敛66