NA007b方程求根概要.ppt

* 原理：将非线性方程线性化 —— 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 (x) = 0 等价 f (x)=0 的根 ? (x) 的不动点 现在令 为待定函数，但 ，则 用条件 确定 ，由 故可取 ,于是 被确定为 由此得出下面的特殊的简单迭代法 ----称为Newton迭代法 用简单迭代法求方程 的根，十分重要的问题是构造迭代函数。为了使收敛速度的阶高一些，应尽可能使 在 处有直到更高阶导数等于0。 x*是根 z §4 Newton - Raphson Method 由构造过程知Newton迭代法至少有二阶的收敛速度。 （局部收敛性）设 f ?C2[a, b]，若 x* 为 f (x) 在[a, b]上的根，且 f ’(x*) ? 0，则存在 x* 的邻域 使得任取初值 ，Newton’s Method产生的序列{ xk } 收敛到x*，且满足 §4 Newton - Raphson Method 解非线性方程 的牛顿法，是一种将非线性方程线性化方法。它是解代数方程和超越方程的有效方法之一。牛顿方法在单根附近具有较高的收敛速度， 而且牛顿方法不仅可以用来求实根， 还可用来求 代数方程的复根，同时还可推广用来解非线性方程组。 定理 §4 Newton - Raphson Method 证明：Newton’s Method 事实上是一种特殊的不动点迭代 其中 ，则 收敛 由 Taylor 展开： 只要 f ’(x*) ? 0，则令 可得结论。 在单根 /*simple root */ 附近收敛快 ? 取迭代值 ，迭代结果列于表中。 例 用牛顿法解方程 所给方程实际上是方程 的等价形式。若用迭代格式 进行计算，迭代到同一精度要迭代17次，可见 牛顿法收敛速度是很快的。 §4 Newton - Raphson Method 0.56714 .056716 0.57102 0.5 3 2 1 0 例 利用Newton迭代法计算 的近似值。 解 可视为 的正根, 而 则Newton迭代公式为： 取初值 ,则得到 =1.500000000 =1.416666667 =1.414213562 =1.414215686 与精确根取十位有效数字完全相同。 §4 Newton - Raphson Method §4 Newton - Raphson Method 注：Newton’s Method 收敛性依赖于x0 的选取。 x* x0 ? x0 ? x0 HW: p.221 #9, #10，#11 由Newton迭代法的收敛性定理知（局部收敛性），Newton迭代法对初值 的要求是很苛刻的，在实际应用中，往往很难给出较好的初值 ，牛顿下山法，就是在事先没有给出较好的初值情况下，求 根的一种修正的牛顿法。 针对这几点改进如下： 缺点： 1）初值 不能偏离 太大，否则可能不收敛， 2）对重根收敛较慢，3）需要计算导数值。 §4 Newton - Raphson Method 优点：Newton法收敛很快（对单根），算法简单。 Newton法的改进 Newton下山法 /* Descent Method */ ——Newton’s Method 局部微调： §4 Newton - Raphson Method 原理：若由 xk 得到的 xk+1 不能使 | f | 减小，则在 xk 和 xk+1 之间找一个更好的点 ，使得 。 xk xk+1 选择因子 使（即选取 ） 称为下山因子（一个可选择的参数） 注：? = 1 时就是Newton