mgx[理学]数值分析简明教程0-1 19.pdf

14.1 二分法二分法二分法二分法§4.2 迭代法迭代法迭代法迭代法§4.3牛顿法牛顿法牛顿法牛顿法§4.4弦截法弦截法弦截法弦截法§第四章方程求根2•我们很熟悉一次我们很熟悉一次我们很熟悉一次我们很熟悉一次、、、、二次代数方程以及某些特殊的高二次代数方程以及某些特殊的高二次代数方程以及某些特殊的高二次代数方程以及某些特殊的高 次方程或超越方程的解法次方程或超越方程的解法次方程或超越方程的解法次方程或超越方程的解法这些方法都是代数解法这些方法都是代数解法这些方法都是代数解法这些方法都是代数解法，，，， 也是精确法也是精确法也是精确法也是精确法但在实际中但在实际中但在实际中但在实际中，，，，有许多方程问题无法求出有许多方程问题无法求出有许多方程问题无法求出有许多方程问题无法求出 公式解公式解公式解公式解例如超越方程例如超越方程例如超越方程例如超越方程 ••• 看起来很简单看起来很简单看起来很简单看起来很简单，，，，却不容易求得精确解却不容易求得精确解却不容易求得精确解却不容易求得精确解至于解三次至于解三次至于解三次至于解三次、、、、 四次代数方程四次代数方程四次代数方程四次代数方程，，，，尽管存在着求解公式尽管存在着求解公式尽管存在着求解公式尽管存在着求解公式，，，，却不实用却不实用却不实用却不实用，，，，而而而而 对一般的五次或五次以上的代数方程对一般的五次或五次以上的代数方程对一般的五次或五次以上的代数方程对一般的五次或五次以上的代数方程，，，，根本没有求根根本没有求根根本没有求根根本没有求根 公式公式公式公式。

另一方面另一方面另一方面另一方面，，，，在实际应用中在实际应用中在实际应用中在实际应用中，，，，只要能获得具有预只要能获得具有预只要能获得具有预只要能获得具有预 先给定的误差限内的近似值就可以了先给定的误差限内的近似值就可以了先给定的误差限内的近似值就可以了先给定的误差限内的近似值就可以了因此因此因此因此，，，，需要引需要引需要引需要引 进能够达到一定精度要求的求方程近似值的方法进能够达到一定精度要求的求方程近似值的方法进能够达到一定精度要求的求方程近似值的方法进能够达到一定精度要求的求方程近似值的方法0=+ xtgx0sin8889. 4tg25. 0=−+xx3• 它包括以下三方面内容它包括以下三方面内容它包括以下三方面内容它包括以下三方面内容：：：：•1．．．．根的存在性根的存在性根的存在性根的存在性方程有没有根方程有没有根方程有没有根方程有没有根？？？？如果有根如果有根如果有根如果有根，，，，•有几个根有几个根有几个根有几个根？？？？•2．．．．这些根大致在哪里这些根大致在哪里这些根大致在哪里这些根大致在哪里？？？？如何把根隔离开来如何把根隔离开来如何把根隔离开来如何把根隔离开来？？？？•3．．．．根的精确化根的精确化根的精确化根的精确化•具体求根通常分为两步走具体求根通常分为两步走具体求根通常分为两步走具体求根通常分为两步走，，，，第一步判断根是否存第一步判断根是否存第一步判断根是否存第一步判断根是否存在在在在，，，，若存在若存在若存在若存在，，，，确定根的某个初始近似值确定根的某个初始近似值确定根的某个初始近似值确定根的某个初始近似值；；；；第二步第二步第二步第二步，，，，将将将将 初始近似值逐步加工成满足精度要求的结果初始近似值逐步加工成满足精度要求的结果初始近似值逐步加工成满足精度要求的结果初始近似值逐步加工成满足精度要求的结果。

•求初始近似值求初始近似值求初始近似值求初始近似值，，，，即确定根的大致区间即确定根的大致区间即确定根的大致区间即确定根的大致区间（（（（a, b），），），），使使使使 （（（（a, b））））内恰有方程的一个实根内恰有方程的一个实根内恰有方程的一个实根内恰有方程的一个实根这个步骤这个步骤这个步骤这个步骤，，，，叫做根的叫做根的叫做根的叫做根的隔离隔离隔离隔离，，，，这样的区间这样的区间这样的区间这样的区间，，，，叫做隔离区间叫做隔离区间叫做隔离区间叫做隔离区间4• 隔离根的方法隔离根的方法隔离根的方法隔离根的方法，，，，主要依据以下根的存在定理主要依据以下根的存在定理主要依据以下根的存在定理主要依据以下根的存在定理：：：：• 定理定理定理定理1：：：：设函数设函数设函数设函数f (x)在区间在区间在区间在区间[a, b]上连续上连续上连续上连续，，，，如果如果如果如果f (a) ⋅ ⋅ ⋅ ⋅ f (b) 0，，，，知知知知f (x)至少有一个正的实根至少有一个正的实根至少有一个正的实根至少有一个正的实根•设从设从设从设从x = 0出发出发出发出发，，，，取取取取h = 0.5为步长向右进行根的扫描为步长向右进行根的扫描为步长向右进行根的扫描为步长向右进行根的扫描，，，，下表记录各个结点上函数值的符号下表记录各个结点上函数值的符号下表记录各个结点上函数值的符号下表记录各个结点上函数值的符号，，，，我们发现我们发现我们发现我们发现，，，，在区间在区间在区间在区间 （（（（1, 1.5））））内必有实根内必有实根内必有实根内必有实根，，，，因此可取因此可取因此可取因此可取x0 = 1或或或或x0= 1.5作为根的作为根的作为根的作为根的初始近似值初始近似值初始近似值初始近似值。

01)(3=−−=xxxf+---1.510.50的符号)(xfx6•在具体运用上述方法时在具体运用上述方法时在具体运用上述方法时在具体运用上述方法时，，，，步长的选择是个关键步长的选择是个关键步长的选择是个关键步长的选择是个关键若步长若步长若步长若步长h足够小足够小足够小足够小，，，，就可以求得任意精度的根的近似就可以求得任意精度的根的近似就可以求得任意精度的根的近似就可以求得任意精度的根的近似值值值值；；；；但但但但h过小过小过小过小，，，，在区间长度大时在区间长度大时在区间长度大时在区间长度大时，，，，会使计算量增大会使计算量增大会使计算量增大会使计算量增大，，，，h过大过大过大过大，，，，又可能出现漏根的现象又可能出现漏根的现象又可能出现漏根的现象又可能出现漏根的现象因此因此因此因此，，，，这种根的这种根的这种根的这种根的隔离法隔离法隔离法隔离法，，，，只适用于求根的初始近似只适用于求根的初始近似只适用于求根的初始近似只适用于求根的初始近似• 根的逐步精确化的方法根的逐步精确化的方法根的逐步精确化的方法根的逐步精确化的方法，，，，包括二分法包括二分法包括二分法包括二分法、、、、迭代法迭代法迭代法迭代法、、、、牛顿法和弦截法牛顿法和弦截法牛顿法和弦截法牛顿法和弦截法。

我们将在以下几节介绍上述方我们将在以下几节介绍上述方我们将在以下几节介绍上述方我们将在以下几节介绍上述方 法法法法，，，，并着重学习迭代法的思想并着重学习迭代法的思想并着重学习迭代法的思想并着重学习迭代法的思想74.1 二分法二分法二分法二分法§首先首先首先首先，，，，假定方程假定方程假定方程假定方程f (x) = 0在区间在区间在区间在区间[a, b]内有唯一内有唯一内有唯一内有唯一的实根的实根的实根的实根x*二分法的基本思想二分法的基本思想二分法的基本思想二分法的基本思想，，，，就是将方程根所在的区就是将方程根所在的区就是将方程根所在的区就是将方程根所在的区间平分为两个小区间间平分为两个小区间间平分为两个小区间间平分为两个小区间，，，，再判断根属于哪个小区间再判断根属于哪个小区间再判断根属于哪个小区间再判断根属于哪个小区间；；；；把有根的小区间再平分为二把有根的小区间再平分为二把有根的小区间再平分为二把有根的小区间再平分为二，，，，再判断根所在的更再判断根所在的更再判断根所在的更再判断根所在的更小的区间小的区间小的区间小的区间；；；；重复这一过程重复这一过程重复这一过程重复这一过程，，，，最后求出所要的近似最后求出所要的近似最后求出所要的近似最后求出所要的近似值值值值。

8• 执行步骤执行步骤执行步骤执行步骤•1．．．．计算计算计算计算f (x)在有解区间在有解区间在有解区间在有解区间[a, b]端点处的值端点处的值端点处的值端点处的值，，，，•f (a)，，，，f (b)•2．．．．计算计算计算计算f (x)在区间中点处的值在区间中点处的值在区间中点处的值在区间中点处的值f (x1)3．．．．判断若判断若判断若判断若f (x1) = 0，，，，则即是根则即是根则即是根则即是根，，，，否则检验否则检验否则检验否则检验：：：：•（（（（1））））若若若若f (x1)与与与与f (a)异号异号异号异号，，，，则知根位于区间则知根位于区间则知根位于区间则知根位于区间•[a, x1]，，，，以以以以x1代替代替代替代替b；；；；•（（（（2））））若若若若f (x1)与与与与f (a)同号同号同号同号，，，，则知根位于区间则知根位于区间则知根位于区间则知根位于区间•[x1, b]，，，，x1代替代替代替代替a9• 反复执行步骤反复执行步骤反复执行步骤反复执行步骤2、、、、3，，，，便可得到一系列有根区间便可得到一系列有根区间便可得到一系列有根区间便可得到一系列有根区间：：：：•[a, b], [a1, b1], …, [ak, bk], …• 其中每个区间都是前一个区间的一半其中每个区间都是前一个区间的一半其中每个区间都是前一个区间的一半其中每个区间都是前一个区间的一半，，，，因此区间长度为因此区间长度为因此区间长度为因此区间长度为••显然显然显然显然，，，，二分过程如果能够无限地继续下去二分过程如果能够无限地继续下去二分过程如果能够无限地继续下去二分过程如果能够无限地继续下去，，，，这些区这些区这些区这些区间最终必收敛于一点间最终必收敛于一点间最终必收敛于一点间最终必收敛于一点x*，，，，该点就是所求的根该点就是所求的根该点就是所求的根该点就是所求的根。

)(21ababkkk−=−10• 由于由于由于由于 •• 只要有根区间只要有根区间只要有根区间只要有根区间[ak+1, bk+1]的长度小于预先给定的误差的长度小于预先给定的误差的长度小于预先给定的误差的长度小于预先给定的误差ε ε ε ε，，，，• 那么就可以取那么就可以取那么就可以取那么就可以取 •• 作为所求根作为所求根作为所求根作为所求根x*的第的第的第的第k+1次近似值次近似值次近似值次近似值其误差估计为其误差估计为其误差估计为其误差估计为：：：：• 综上所述综上所述综上所述综上所述，，，，设设设设f (x)在在在在[a, b]上存在一阶导数且不变号上存在一阶导数且不变号上存在一阶导数且不变号上存在一阶导数且不变号，，，，• 如果如果如果如果f (a)⋅ ⋅ ⋅ ⋅f (b)＜＜＜＜0，，，，则由则由则由则由（（（（1））））所知所知所知所知，，，，当当当当k→∞→∞→∞→∞时时时时，，，，• | || | x*- xk|→|→|→|→0，，，，即即即即xk→→→→x*11*)(21++−=−≤−kkkkkababxx)(21 1kkkbax+=+)(2111*abxxkk−≤−++（1）11• 二分法求二分法求二分法求二分法求f (x) = 0在在在在[a, b]上的实根的框图上的实根的框图上的实根的框图上的实根的框图。

输入 a, b, ε定义f (x)f (a)⋅ f (b)>0k = 0f (a)⋅ f (b)=0f (a) =0打印b, k打印a, k结束是是是否否否m=(a+b)/2|a-b|0打印m, ka=mb=m结束k=k+1是是否否12• 例例例例2：：：： 求方程求方程求方程求方程•• 在区间在区间在区间在区间[1, 1.5]内的实根内的实根内的实根内的实根要求准确到小数点后第要求准确到小数点后第要求准确到小数点后第要求准确到小数点后。