数值分析2-方程求根二分法代法数值分析2-方程求根二分法迭代法数值分析2-方程求根二分法迭代法数值分析2-方程求根二分法迭代法.ppt

2.2 二分法(Bisection) 2.3迭代法(Iteration) 2.3.3 迭代法收敛速度 解： 一般地，收敛阶还可通过下面定理判断： * * 思路：找到一区间，满足 在 上连续单调，且 。（有唯一解） 通过迭代法，将有根区间缩小，使在足够小的区间内有唯一解。（满足误差精度） 记： ，取中点 ， 分成两区间： 若 ，则找到方程的根； 否则有： ，或 若 ，记 ， 若 ，记 ， ………… 通过k 次迭代，得到一区间 ，有 取 中点 作为近似解， ∴可通过误差公式反算出迭代次数k。 考虑误差： 例：求 在[0，1]内的根，要求达到3为有效数字。 已知： ， ； ，所以当 时，有唯一根， 此时： 可满足精度。 通过上机计算可知， 二分法的特点： 1：计算简单，方法可靠，但收敛速度一般，且无法求重根和复根； 2：可通过该方法找到足够小的有根区间，为别的求根方法提供好的初值。 作业：证明方程 在[0, 1]中有且只有1个根。 的根，需求多少次迭代？ 使用二分法求误差不大于 （不必求出根） 常用的数值求根方法，包括方程组求解，主要考虑是否收敛，收敛的快慢问题。 思路： 给一初值 ，通过迭代产生 ， …… 几何意义如右图： 考虑的问题： 1.φ(x)的形式多样性，不同的φ(x)，迭代结果不同，可能收敛，可能发散。 若 有极限值，则收敛，极限值可作为方程的根。 2. 的收敛快慢。 例： , ∈[2, 4]， = 4。 φ(x)形式有： ① ② ③ （收敛） （发散） （发散） 由几何作图可知：迭代是否收敛与迭代函数有关，具体有下列定理： 定理2.1 迭代函数φ(x)具有一阶连续的导数，且满足 （1）当 ∈[a, b]时, φ(x) ∈[a, b], （2）存在正常数L＜1，使得当 x∈[a, b]时有|φ’(x)|≤L， 则迭代方程收敛，且有以下性质： （1）方程在[a,b]内有唯一根 。 证明：记 ∵φ(x) ∈[a, b], ∴ , ∴在[a,b]内至少有一个根（端点处也可以） 又∵ ， ∴单调。 （2）对任意 ∈[a,b] 通过φ(x)迭代，结果收敛，有 证明：∵ , ∴ 由拉格朗日中值定理知： ， ∈[a, b] ∴ , ∈[ ] ∈[a, b] ∵ ≤ L1， ∴ ∴ ，即 （3） 证明：(反推法) 不等式即为： ， 由性质（2）知： ， ∴若 即可。 这显然是成立的，因为 该结果可用于判断迭代次数是否达到误差范围. ∴由 前后两次迭代结果判断称为误差事后公式。 （4） 证明：由性质（3）得 又∵ ∴ 由于尚未计算，即能估计出迭代次数，该式称为误差事先公式。 (5) ∵ ，∴ 又∵ ， ∴ (6) 若 时， ，则对任意初值 ， 迭代公式发散. 逐渐远离 . Ck越来越大, 例：判断迭代函数收敛性. （同时满足定理2个条件） ① 当 时, , 迭代收敛. (该题可作习题，精确4位有效数字, ) ② 当 时， , 迭代发散. 例：利用迭代法求 的根,区间为[0,1]. 当 时， ，条件1满足. 但 ，不能满足条件2. 方法: 缩小区间使得同时满足两个条件, 可使用二分法或等距法. 等距法更快,从 开始以 为步长，确定区间使 . ,所以 内有根. . 但此时 闭区间在端点处不满足. 这是由 引起. 继续缩小区间为 . 此时: . 可通过迭代方法求出. 注意:若有根区间较大,不能满足两个条件. 可通过缩小有根区间的方法，或采用下面的局部收敛判别定理. 2.3.2迭代法的局部收敛性. (给定较大区间,原定理的两个条件较难同时满足. 如果区间足够小,可保证同时满足两个条件.) 定义:对方程 ，若在