第二篇 方程求根.ppt

数 值 分 析 ——第二章 方程求根 第2章 方程求根 解数值问题 直接法 逐次逼近法——规则：A1?A2 ?… ?An ?…精确解 其中Ai可以是数、向量、矩阵或其他 两种形式：迭代法——利用递推公式 搜索法——利用法则（如二分法） 直接法——小型问题及特殊问题 逐次逼近法——大型问题及非线性问题。 2.1 非线性方程的迭代法 设非线性方程 f(x) = 0 (2.1) 若有?，使f(?)=0，则称?为方程(2.1)的根，或称?为函数f(x)的零点。 注：(1) 代数方程——5次以上不能用解析公式求根 超越方程——求解更难 (2) 若f(x) = 0在区间[a，b]上仅有一根，则称[a，b]为方程(2.1)的单根区间； 若f(x) = 0在区间[a，b]上有多个根，则称[a，b]为方程(2.1)的多根区间，统称为有根区间。 2.1 非线性方程的迭代法 2.1.1 根的搜索 1. 逐步搜索法 为明确起见，不妨假定f(a) 0，f(b) 0。 我们从有根区间[a，b]的左端x0 = a出发，某个预定的步长h (譬如取h = (b – a)/N，N为正整数)一步一步地向右跨，每跨一步进行一次根的“搜索”，即检查节点xk = a + kh上的函数值f(xk)的符号，一旦发现节点xk与端点a的函数值异号，即f(xk) 0，则可以确定一个缩小了的有根区间[xk-1，xk]，其宽度等于预定的步长h. 2.1 非线性方程的迭代法 2.1.1 根的搜索 1. 逐步搜索法 【例2-1】考察方程f(x) = x3 – x – 1 = 0. 注意到f(0)0，f(2)0，知f(x)在区间(0，2)内至少有一个实根. 设从x = 0出发，取h = 0.5为步长向右进行根的搜索，列表记录各个节点上函数值的符号(表6-1)，我们发现区间[1.0，1.5]内必有一根. 2.1 非线性方程的迭代法 2.1.1 根的搜索 1. 逐步搜索法 在具体运用上述方法时，步长h的选择是个关键.很明显，只要步长h取得足够小，利用这种方法可以得到具有任意精度的近似根.不过当h缩小时，所要搜索的步数相应增多，从而使计算量增大。 因此，如果精度要求比较高，单用这种逐步搜索方法是不合算的。 下述二分法可以看作是逐步搜索方法的一种改进。 2.1 非线性方程的迭代法 2.1.1 根的搜索 2. 二分法 考察有根区间[a，b]，取中点x0 = (a + b)/2将它分为两半, 然后进行根的搜索, 即检查f(x0)与f(a)是否同号。 如果确系同号，说明所求的根?在x0的右侧，这时令a1=x0，b1=b; 否则?必在x0的左侧，这时令a1=a，b1=x0.不管出现哪一种情况，新的有根区间[a1，b1]的长度仅为[a，b]的一半. 2.1 非线性方程的迭代法 2.1.1 根的搜索 2. 二分法 对压缩了的有根区间[a1，b1]又可施行同样的手续，即用中点x1 = (a1 + b1)/2将区间[a1，b1]再分为两半，然后通过根的搜索判定所求的根在x1的哪一侧，从而又确定一个新的有根区间[a2，b2]，其长度是[a1，b1]的一半。 2.1 非线性方程的迭代法 2.1.1 根的搜索 2. 二分法 如此反复二分下去，即可得出一系列有根区间 [a，b][a1，b1][a2，b2]…[ak，bk]… 其中每个区间都是前一个区间的一半，因此[ak，bk]的长度bk – ak = (b – a)/2k+1当时趋于零，就是说，如果二分过程无限地继续下去，这些区间最终必收缩于一点? ，该点显然就是所求的根. 2.1 非线性方程的迭代法 2.1.1 根的搜索 2. 二分法 每次二分后，设取区间[ak，bk]的中点xk = (bk + ak)/2作为根的近似值，则在二分过程中可以获得一个近似根的序列x0，x1，x2，…，xk…该序列必以根?为极根。 由于 |? – xk|≤(bk – ak)/2 = (b – a)/2 k+1 只要二分足够多次(即k充分大)，便有|? – xk| ?，这里?为预定的精度. 2.1 非线性方程的迭代法 2.1.1 根的搜索 2. 二分法 【例2-2】求方程f(x) = x3 – x – 1 = 0在区间[1.0，1.5]内的一个实根，要求准确到小数点后的第2位. 解：这里a=1.0，b=1.5，而f(a)0，f(b