计算方法方程求根b.ppt

* 6.3 牛顿迭代法和割线法 原理：将非线性方程线性化 —— Taylor 展开 取 x0 ? x*，将 f (x)在 x0 做一阶Taylor展开: ，? 在 x0 和 x 之间。 将 (x* ? x0)2 看成高阶小量，则有： 线性 /* linear */ x y x* x0 只要 f ?C1，每一步迭代都有f ’( xk ) ? 0， 而且 ，则 x*就是 f 的根。 x1 定理 （收敛的充分条件）设 f ?C2[a, b]，若 (1) f (a) f (b) 0；(2) 在整个[a, b]上 f ”不变号且 f ’(x) ? 0； (3) 选取 x0 ? [a, b] 使得 f (x0) f ”(x0) 0； 则Newton’s Method产生的序列{ xk } 收敛到f (x) 在 [a, b] 的唯一根。 有根 根唯一 产生的序列单调有界，保证收敛。 定理 （局部收敛性）设 f ?C2[a, b]，若 x* 为 f (x) 在[a, b]上的根，且 f ’(x*) ? 0，则存在 x* 的邻域 使得任取初值 ，Newton’s Method产生的序列{ xk } 收敛到x*，且满足 在单根 附近收敛快 6.3 牛顿迭代法和割线法 证明：Newton’s Method 事实上是一种特殊的不动点迭代 其中 ，则 收敛 由 Taylor 展开： 只要 f ’(x*) ? 0，则令 可得结论。 ? 6.3 牛顿迭代法和割线法 例 用牛顿法求解方程 x3-x-1=0 在[1, 2]中的根，计算精度要求ε=10-6。(x*=1.324718…) 解：牛顿迭代公式为 ： 3.23216E-7 5.88844E-4 0.025307 |xk+1-xk| 1.32471 1.324718 1.325307 1.3 xk … 3 2 1 0 k 2.16754E-7 4.82224E-4 0.0226256 0.152173 0.5 |xk+1-xk| 1.324718 1.324718 1.325200 1.347826 1.5 1 xk 5 4 3 2 1 0 k 取x0=1 取x0=1.3 6.3 牛顿迭代法和割线法 改进与推广 ? 重根加速收敛法： Q1: 若　　　 ，Newton’s Method 是否仍收敛？ 设 x* 是 f 的 n 重根，则： 因为 Newton’s Method 事实上是一种特殊的迭代法， 其中 ，则 A1: 有局部收敛性，但重数 n 越高，收敛越慢。 Q2: 如何加速重根的收敛？ A2: 将求 f 的重根转化为求另一函数的单根。 ? 令　　　　　 ，则 f 的重根 = u 的单根。 6.3 牛顿迭代法和割线法 注：Newton’s Method 收敛性依赖于x0 的选取。 x* x0 ? x0 ? x0 6.3 牛顿迭代法和割线法 ? 下山法 /* Descent Method */ ——Newton’s Method 局部微调： 原理：若由 xk 得到的 xk+1 不能使 | f | 减小，则在 xk 和 xk+1 之间找一个更好的点 ，使得 。 xk xk+1 注：? = 1 时就是Newton’s Method 公式。 当 ? = 1 代入效果不好时，将 ? 减半计算。 6.3 牛顿迭代法和割线法 ? 割线法 Newton’s Method 一步要计算 f 和 f ’，相当于2个函数值，比较费时。现用 f 的值近似 f ’，可少算一个函数值。 x0 x1 切线 割线 切线斜率　?　割线斜率 需要2个初值 x0 和 x1。 收敛比Newton’s Method 慢，且对初值要求同样高。 6.3 牛顿迭代法和割线法 6.4 劈因子法 /* Splitting Method */ 求多项式的所有根 从 f (x)中分离出一个2 次因子。即： 通过 　　　　　　 可解出一对共轭复根。 思路 从一对初值 ( u, v ) 出发，则有 其中( r, s )取决于u 和 v，可以看作是( u, v )的函数，即 r = r