《引言分法与迭代法》由会员分享，可在线阅读，更多相关《引言分法与迭代法（24页珍藏版）》请在金锄头文库上搜索。
1、第二章 方程求根 本章主要内容：1、二分法2、简单迭代法（重点）3、牛顿迭代法（重点） 4、割线法本章难点：分析迭代法的收敛性历史背景代数方程的求根问题是一个古老的数学问题。理论上， 次代数方程在复数域内一定有 个根(考虑重数)。早在16世纪就找到了三次、四次方程的求根公式，但直到19世纪才证明大于等于5次的一般代数方程式不能用代数公式求解，而对于超越方程就复杂的多，如果有解，其解可能是一个或几个，也可能是无穷多个。一般也不存在根的解析表达式。因此需要研究数值方法求得满足一定精度要求的根的近似解。 本章解决一元函数方程的求根问题。否则称其为超越方程，如当 为多项式函数时，称此方程为代数方程，如
2、若函数 可表示成( 2.1 )则称 是方程 ( 2.1 ) 的 重根。根的存在性连续函数介值定理则这样的 在 内唯一。 a bx*若函数 在 上连续，且则至少有一个数 ，使得 ，若 还单调，定理：方程 f (x) = 0 的有根区间的确定有根区间：方程在这样的区间内有且只有一个实根。1. 描图法将方程 f (x) = 0 化为 g (x) = h (x) 的形式，画出 g (x) 和h (x) 的简图，从两条曲线的交点的横坐标的位置例2.1 求方程 3x 1 cos x = 0 的有根区间。解：用描图法，将方程变形为令 g (x) = 3x - 1, h (x) = cos x, 做出两个函数
3、的简图确定有根区间。注：g (x) 和 h (x) 的图形比较容易作出。由图可知，方程仅有一个实根，有根区间为2. 通过研究函数性态判断有根区间例2.2 求函数 的有根区间。解： 令 , 并对其求导数得单调减少的。所以函数 在 上是又根据连续函数介值定理，方程 在 内有且仅有一个实根。所以 是方程 的有根区间。第一节 二分法若 f (x) 在 a, b 上连续，且 f (a) f (b) 0，以此类推上至少有一实根。则 f (x) 在 (a, b)原理：基本思想：逐步将区间分半，通过判别区间端点函数值的符号，进一步搜索有根区间，将有根区间缩小到充分小，从而求出满足精度的根的近似。二分法的实施步
4、骤：（1）找出方程 的有根区间 。若每次二分时所取区间中点都不是根，则上述过程将无限进（3）判断：若 则 是方程的根, (a) 若 , 则根属于 ，置： 行下去。计算结束；否则：(b) 若 , 则根属于 ，置： 注：上述过程中 常取做机器零，当小于此数时认为是零！（2）计算 f (x) 在区间中点 的值 ；如 。误差分析：什么时候停止计算？按上述过程反复进行, 可得一系列有根区间套当 n 时, 区间长度趋近于零，因此区间必将最终收缩为由于每一区间都是前一区间的一半，因此区间 的长度一点 , 显然 就是所求的根。若取区间 的中点作为 的近似值，则 ，从而有下述误差估计式只要根据误差估计式，对于预
5、先给定的精度 ，即可由此确定 最大对分次数便有：因此， 就是满足精度要求的近似解。二分法算法实现问题：给定区间a, b ，求 f (x)=0 在该区间上的根 x.输入: a 和 b; 容许误差 TOL; 最大对分次数 Nmax. 输出: 近似根 x.Step 1 令 k = 1;Step 2 计算 x = (a+b)/2 和 y = f (x)Step 3 若 k Nmax，做 Steps 4-6Step 4 若 | y | TOL , 停止; 输出 x.Step 5 若 y * f (a) 0 , 置 b = x;否则，置 a = x;Step 6 置 k = k+1; 计算 x = f (
6、a+b)/2); 转 Step 3；Step 7 输出方程的近似解 x; 停止.算法过程: 解：例2.3 用二分法求方程 在区间 上的根，误差限为 0.0005，问至少需对分多少次？由题意知，最大对分次数所以至少需对分 次。对分 9 次后取有根区间的中点即为满足精度要求的根。 算法简单直观，收敛性有保证; 对 f (x) 要求不高(只要连续即可) . 无法求复根及重根； 收敛速度慢。 注：注：用二分法求根，最好先给出 f (x) 草图以确定根的大概 位置。或用搜索程序，将a, b分为若干小区间，对每一个 满足 f (ak)f (bk) 0 的区间调用二分法程序，可找出区间 a, b内的多个根，
7、且不必要求 f (a)f (b) 0 。优点缺点第二节 迭代法f (x) = 0等价变换基 本 思 想从一个初值 x0 出发，计算一、简单迭代法f (x) 的根若数列 收敛，即存在 ， 使得称为迭代函数称为 的不动点 若函数 还是连续的，则 即即方程 f (x) = 0 的一个根。这样就找到了函数 的一个不动点，xyy = xxyy = xxyy = xxyy = xx*x*x*x*y= (x)y= (x)y= (x)y= (x)x0p0x1p1x0p0x1p1x0p0x1p1x0p0x1p1几何意义例2.4 已知方程 在 上有一个根.解：下面选取5种迭代格式：1、即2、即3、即4、即5、即取
8、计算结果如下：法1法4法3法2法5如何判定迭代法的 收敛性呢？如何构造迭代函数 才能使迭代法收敛？有如下充分条件：定理 2.1（压缩映射原理）若迭代函数 满足下列两个条件：(2) 0 L 1 使得对 x a, b 有：(1) 当 x a, b 时，则迭代过程 对于任意初值 均收敛于方程 的根 ，且有如下误差估计式：证明： 先证当k 时， xk 收敛到 x* ，这是因为再证定理中的误差估计式，利用三角不等式所以注：该定理结论表明只要相邻两次迭代值的距离足够小，即可保证近似值 具有足够的精度，所以可用 来判断是否满足迭代精度！问题：给定初始近似值 x0 ，求 的解. 输入: 初始近似值 x0; 容
9、许误差 TOL; 最大迭代次数 Nmax. 输出: 近似解 x 或失败信息.简单迭代法的算法实现：Step 1 置 i = 1;Step 2 当 i Nmax时，作 Step 3-5：Step 3 置 ;否则，置 i = i + 1;Step 4 若 | x x0 | TOL，则输出 x，停止；Step 6 输出迭代失败信息，停止计算。Step 5 置 x0 = x ，转 Step 2;二、局部收敛性定义：（局部收敛性 ） 若存在 的一个闭邻域 ，对任意于 ，则称该迭代法局部收敛。初值 ，由迭代过程 产生的序列 均收敛定理 2.2关于局部收敛，有如下判定定理：设 为 的解， 在 的某邻域连续，且则迭代过程 局部收敛。 三、迭代法的收敛阶及常数 ，使注注: :（1 1） 的大小反映了迭代法收敛的快慢，是收敛速度的一种度量;定义：设序列 收敛到 ， ，若存在实数则称序列 是 阶收敛的，常数 称为渐近误差常数。特别地，当 且 时，称为线性收敛；当 时为超线性收敛；当 时为平方或二次收敛.定理2.2 设迭代法的迭代函数 的高阶导数证明： 由Taylor公式：取极限得在不动点 的邻域里连续，则当时，迭代过程 是 阶收敛的。
