ch07a非线性方程求解.pptVIP

第七章 非线性方程求解 非线性方程的根 第二节 二分法 算法 误差分析 第三节 不动点迭代 第三节 不动点迭代 举例 收敛性分析 全局收敛与局部收敛 收敛阶 p 阶收敛 * * * 第一节 基本问题 求 f (x) = 0 的根 代数方程： f (x) = a0 + a1x + . . . + anxn 超越方程： f (x) 含超越函数，如 sin(x), ex, lnx 等 实根与复根 根的重数 f (x) = ( x – x*)m · g(x) 且 g(x*) ? 0, 则 x* 为 f (x) 的 m 重根 有根区间：[a, b] 上存在 f (x) = 0 的一个实根 在有根的前提下求出方程的近似根。 研究 内容： 若 f ? C[a, b]，且 f (a) · f (b) 0，则 f 在 (a, b) 上必有一根。 基本原理： 具体方法： 通过二等分不断缩小有根区间的长度，直到满足精度为止。 a b x1 x2 x* 何时终止? 或 不能保证 x 的精度 算法 7.1 (二分法) 给定有根区间 [a, b] ( f(a) · f(b) 0) 和 精度要求 ? 1. 令 x = (a+b)/2 2. 如果 b – a ? 或 f (x) ? , 停机，输出 x 3. 如果 f (a) f (x) 0 , 则令 b = x，否则令 a = x, 返回第1步 用二分法求根，通常先给出 f (x) 草图以确定根的大概位置。 记 a1 = a, b1 = b, 第 k 步的有根区间为 [ak, bk] 对于给定的精度 ? ,可估计二分法所需的步数 k ： 取 简单易用 无法求复根及偶重根 对 f (x) 要求不高，只要连续即可 收敛速度慢 取x6= 1.3242 ，误差为| x* -x6|0.005 。 例1，求方程f(x)= x 3–x -1=0在区间[1，1.5]的一个实根，要求准确到小数点后的第2位。 解：因为 f(1)0，f(1.5)0。 故f(x)在(1，1.5)内有根。 考虑二分次数，由误差估计公式： 有2k50 ,k50/ln2≈5.645 (26=64) k至少取6 用二分法解之，(a,b）=（1,1.5)计算结果如表： k ak bk xk f(xk)符号 0 1.0 1.5 1.2500 － 1 1.2500 － 1.3750 ＋ 2 － 1.3750 1.3125 － 3 1.3125 － 1.3438 ＋ 4 － 1.3438 1.3281 ＋ 5 － 1.3281 1.3203 － 6 1.3203 － 1.3242 － 定理 设 ?(x)?C[a, b] 且可导，若 (2) ? 0 ? L 1，使得 | ?’(x) | ? L 对 ? x?[a, b] 成立 则函数 f (x) = x - ?(x) 在 [a, b] 中有唯一的零点 x*。 (压缩映像定理，不动点定理) x* 称为 ?(x) 的不动点 ?(x*) = x* (1) a ? ?(x) ? b 对一切 x?[a, b] 都成立 简证： f(a) = a - ? (a)? 0 , f(b) = b - ? (b) ? 0 f(x) 在[a, b] 上有零点。 唯一性：反证法，假设存在 x*, y*?[a, b] 使得 x* = ?(x*) y* = ?(y*) 矛盾！ ? (x) 的不动点 f (x) = 0 x = ? (x) 等价变换 基本思想 从一个给定的初值 x0 出发，计算 x1 = ? (x0), x2 = ? (x1), … 若 收敛，即存在 x* 使得 ，则由 ? 的连续性和 可得 x* = ? (x*)，即 x* 是 ? 的不动点，也就是 f (x) 的零点。 具体做法： 不动点迭代 f (x) 的零点 几何含义： 求曲线 y = ?(x) 与直线 y = x 的交点 xk+1 = ?(xk) x y y = x x y y = x x y y = x x y y = x x* x* x* x* y= ?(x) y= ?(x) y=