第二节牛与顿迭代法 .ppt

第三节 牛顿迭代法与弦割法 1、牛顿法基本思想 将非线性方程线性化，以线性方程的解逼近非线性方程的解。 将非线性方程线性化， 取 x0 ? x*，将 f (x) 在 x0 处做一阶Taylor展开: ，? 在 x0 和 x 之间 2. 牛顿迭代法的原理 ，可将 (x* ? x0)2 看成高阶小量，则有： 如何实现？？ 取 这个为什么就变成f(x)=0了呢？这是泰勒公式的形式，还是x*本来就是我要找的f(x)=0的根呢？ x y x* x0 只要 f ?C1，每一步迭代都有 而且 ，则 x*就是 f 的根。 是如下线性方程的根！ 这个是个什么约束呢？ 3. 牛顿迭代法的几何解释： 方程 的根 在几何上是曲线 与 x 轴的交 点的横坐标。若 是根 的一个近似，过曲线上横坐标为 的点 作曲线 的切线，则该切线与 x 轴交点的横坐 标即为 。 x y x* x0 例2.5：?写出求 的牛顿迭代格式；?写出求 的牛顿迭代格式,要求公式中既无开方运算，又无除法运算。 解： ?等价于求方程 的正根 ?解法一： 等价于求方程 的根 退化为二分法！！ 解法二： 等价于求方程 的正根 ? 设 x* 为方程 f (x) = 0的根，在包含x*的某个开区间内 连续，且 ，则存在 x* 的邻域 ，使得任取初值 ，由牛顿迭代法产生的序列 以不低于二阶的收敛速度收敛于x*，且 4、牛顿迭代法的局部收敛性定理 其中 ，则 收敛 由泰勒展开： 在单根附近收敛快！ ? 只要 ，则令 可得结论。 证明： 牛顿迭代法事实上是一种特殊的不动点迭代 在 和 之间 牛顿迭代法的改进 ? 重根 Q1: 若　　　 ，牛顿迭代法是否仍收敛？ 设 x* 是 f 的 n 重根，则： 且 。 因为牛顿迭代法事实上是一种特殊的不动点迭代， 其中 ，则 A1: 有局部收敛性，但重数 n 越高，收敛越慢。 Q2: 如何加速重根的收敛？ A2: 根的重数已知，可将 f 的重根转化为另一函数的单根。 ? 令　　　　　，则 f 的重根是 ? 的单根，且 从而可构造出相应的迭代法格式为 对 构造出相应的牛顿迭代格式，迭代函数为 若已知根的重数为 n，可将迭代格式改为， 则 ，所以上述格式是平方收敛的。 ① 收敛速度快，稳定性好； ② 精度高。 ① 在重根附近收敛速度会降阶； ② 每次都要计算函数及其导数值，计算量大。 优点 缺点 注解：牛顿法是局部收敛的，所以要求初值 选在解 的附 近，实际计算时，常先用简单迭代法算几步，估计出一个质 量较好的初值！！ 主要缺陷！！ 收敛比牛顿迭代法慢，且对初值要求同样高。 第五节 弦割法 x0 x1 切线 割线 切线斜率　?　割线斜率 需要2个初值 x0 和 x1。 基本思想：牛顿迭代法每一步要计算 f 和 ，为了避免计算导数值，现用 f 的差商近似代替微商 ，从而得到弦割法。 x2 Th2.10 局部收敛性 设 表示区间 ， x*为方程 f (x) =0的根， 函数f (x)在 中有足够阶连续导数， 且 满足 则对 ，由割线法产生的序列 都收敛于x*，且 (i) (ii) (iii) 其中 收敛速度介于牛顿法和 二分法 之间