文档详情

计算方法NA05b.ppt

发布:2017-05-19约2.73千字共14页下载文档
文本预览下载声明
* §4 牛顿法 /* Newton - Raphson Method */ 原理:将非线性方程线性化 —— Taylor 展开 /* Taylor’s expansion */ 取 x0 ? x*,将 f (x)在 x0 做一阶Taylor展开: ,? 在 x0 和 x 之间。 将 (x* ? x0)2 看成高阶小量,则有: 线性 /* linear */ x y x* x0 只要 f ?C1,每一步迭代都有f ’( xk ) ? 0, 而且 ,则 x*就是 f 的根。 §4 Newton - Raphson Method 定理 (收敛的充分条件)设 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*,且满足 §4 Newton - Raphson Method 证明:Newton’s Method 事实上是一种特殊的不动点迭代 其中 ,则 收敛 由 Taylor 展开: 只要 f ’(x*) ? 0,则令 可得结论。 在单根 /*simple root */ 附近收敛快 ? §4 Newton - Raphson Method 注:Newton’s Method 收敛性依赖于x0 的选取。 x* x0 ? x0 ? x0 Excuses for not doing homework I have the proof, but there isnt room to write it in this margin. §4 Newton - Raphson Method 改进与推广 /* improvement and generalization */ ? 重根 /* multiple root */ 加速收敛法: Q1: 若    ,Newton’s Method 是否仍收敛? 设 x* 是 f 的 n 重根,则: 且 。 因为 Newton’s Method 事实上是一种特殊的不动点迭代, 其中 ,则 A1: 有局部收敛性,但重数 n 越高,收敛越慢。 Q2: 如何加速重根的收敛? A2: 将求 f 的重根转化为求另一函数的单根。 ? 令     ,则 f 的重根 = ? 的单根。 §4 Newton - Raphson Method ? 正割法 /* Secant Method */ : Newton’s Method 一步要计算 f 和 f ’,相当于2个函数值,比较费时。现用 f 的值近似 f ’,可少算一个函数值。 x0 x1 切线 /* tangent line */ 割线 /* secant line */ 切线斜率 ? 割线斜率 需要2个初值 x0 和 x1。 收敛比Newton’s Method 慢,且对初值要求同样高。 §4 Newton - Raphson Method ? 下山法 /* Descent Method */ ——Newton’s Method 局部微调: 原理:若由 xk 得到的 xk+1 不能使 | f | 减小,则在 xk 和 xk+1 之间找一个更好的点 ,使得 。 xk xk+1 注:? = 1 时就是Newton’s Method 公式。 当 ? = 1 代入效果不好时,将 ? 减半计算。 §4 Newton - Raphson Method ? 求复根 /* Finding Complex Roots */ —— Newton 公式中的自变量可以是复数 记 z = x + i y, z0
显示全部
相似文档