计算方法方程求根b 2013年最新西安交通大学《数值分析》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 C2a, b，若 (1) f (a) f (b) 0； 则Newtons Method产生的序列 xk 收敛到f (x) 在 a, b 的 唯一根。 有根 根唯一 产生的序列单调有 界，保证收敛。 定理 （局部收敛性）设 f C2a, b，若 x* 为 f (x) 在a, b 上的根，且 f (x*) 0，则存在 x* 的邻域 使得任取初 值 ，Newtons Method产生的序列 xk 收敛到x* ，且满足 在单根 附近 收敛快 6.3 牛顿迭代法和割线法 证明：Newtons Method 事实上是一种特殊的不动点迭代 其中 ，则 收敛 由 Taylor 展开： 只要 f (x*) 0，则令 可得结论。 6.3 牛顿迭代法和割线法 例 用牛顿法求解方程 x3-x-1=0 在1, 2中的根，计算精度要求 =10-6。(x*=1.324718) 解：牛顿迭代公式为 ： k0123 xk1.31.3253071.3247181.32471 |xk+1-xk| 0.0253075.88844E-43.23216E-7 k012345 xk11.51.3478261.3252001.3247181.324718 |xk+1-xk|0.50.1521730.02262564.82224E-42.16754E-7 取x0=1 取x0=1.3 6.3 牛顿迭代法和割线法 改进与推广 重根加速收敛法： Q1: 若 ，Newtons Method 是否仍收敛？ 设 x* 是 f 的 n 重根，则： 因为 Newtons Method 事实上是一种特殊的迭代法， 其中 ，则 A1: 有局部收敛性，但重数 n 越高，收敛越慢。 Q2: 如何加速重根的收敛？ A2: 将求 f 的重根转化为求另一函数的单根。 令 ，则 f 的重根 = u 的单根。 6.3 牛顿迭代法和割线法 注：注：Newtons Method 收敛性依赖于x0 的选取。 x* x0 x0 x0 6.3 牛顿迭代法和割线法 下山法 /* Descent Method */ Newtons Method 局部微调： 原理：若由 xk 得到的 xk+1 不能使 | f | 减小，则在 xk 和 xk+1 之间找一个更好的点 ，使得 。 xkxk+1 注：注： = 1 时就是Newtons Method 公式。 当 = 1 代入效果不好时，将 减半计算。 6.3 牛顿迭代法和割线法 割线法 Newtons Method 一步要计算 f 和 f ，相当于2个函数值 ，比较费时。现用 f 的值近似 f ，可少算一个函数值。 x0x1 切线 割线 切线斜率 割线斜率 需要2个初值 x0 和 x1。 收敛比Newtons Method 慢 ，且对初值要求同样高。 6.3 牛顿迭代法和割线法 6.4 劈因子法 /* Splitting Method */ 求多项式的所有根 从 f (x)中分离出一个2 次因子。即： 通过 可解出一对共轭复根。 思 路 从一对初值 ( u, v ) 出发，则有 其中( r, s )取决于u 和 v，可以看作是( u, v )的函数，即 r = r ( u, v )，s = s ( u, v ) 。 目标：r = r ( u*, v* ) = 0，s = s ( u*, v* ) = 0。 6.4 Splitting Method 将r 和 s 在初值点( u, v )做一阶Taylor展开，并代入( u*, v*) ： 每步迭代须计算 从中解出 ，以 更新 u 和 v 再迭代，直到 r 和 s 充分接近0。 6.4 Splitting Method 计算 r 和 s ： 可记为 bn1 若令 ，则 6.4 Splitting Method 计算： n2 阶多项式n4 阶多项式 与前一步同理，可导出 和 的公式 。 f(x)与v无关， P(x),r,s是v的 函数 6.4 Splitting Method 计算 r/v 和 s/ v ： 6.4 S