计算方法—数据分析与智能计算初探（第2版）教学课件 第2章 方程求根的数值解法.ppt

* 若取 x0 = 2.0，分别用上述三种迭代方法计算，结果见下表（准确根 x* = 1.73205080757…） 1.732050821 2.0 x8 8 1.732050907 1.5 x7 7 1.732051553 2.0 x6 6 1.732056369 1.5 x5 5 1.732050808 1.732092320 2.0 x4 4 1.732050810 1.732360840 1.5 x3 3 1.732142857 1.734375000 2.0 x2 2 1.75 1.75 1.5 x1 1 2.0 2.0 2.0 x0 0 xn n * 迭代过程的收敛速度 如果存在某个实数 p 和非零常数 C，使得： 定义：设序列 {xn} 是收敛于 f (x) = 0 的准确根 x* 的迭代序列，记各步的迭代误差为 en = xn - x*, 则称序列 {xn} 是 p 阶收敛的。 渐近误差常数 p = 1, 0 C 1时，序列 {xn} 是线性收敛 p = 1, C = 0 时，序列 {xn} 是超 p 阶收敛 p 1时，序列 {xn} 是超线性收敛 p = 2时，序列 {xn} 是平方收敛 p 越大，收敛越快 * 迭代过程的收敛速度（续） 定理：对于迭代过程 xn+1 = ? (x)，如果迭代函数 ? (x)在准确根 x* 的邻近有连续的二阶导数，且： 则有： 当 而 时，迭代过程为平方收敛 当 时，迭代过程为线性收敛 当 而 时，迭代过程为 p 阶收敛 * 如果迭代函数 j (x) 收敛，在 x* 的某个邻域 ? 内有j ?(x) 1，当有根区间较小或 j ?(x) 在 ? 内变化较平缓时，可近似将 j ?(x) 取某个定值 a。 迭代过程的加速 设迭代方程 x = j (x) 的准确根为 x*，由微分中值定理可知： xn+1 的大致误差，可以在 xn+1 的基础上叠加上这个误差，从而得到比 xn+1 本身更精确的近似值 * 经过加速处理后，迭代过程为： 迭代终止条件仍为： 迭代： 加速： a 的确定需要求解迭代函数的导函数 j ?(x) 不便之处 * 埃特金（Atiken）加速 所以： 展开得： 即： * * 埃特金（Atiken）加速（续） 加速公式中不再含有与 j ?(x) 相关的系数 a 需要两次迭代再能得到下一步的近似值 某些发散的迭代公式经埃特金法加速处理后，能够获得较好的收敛性 两次迭代 迭代： 迭代： 加速： * 牛顿法 假设已知 f (x) = 0 的某个初始近似根为 x0，且在 x0 的一个适当小的邻域内 f (x) 可微，将 f (x) 在点 x0 附近用泰勒公式展开： 如果仅取上述泰勒展开式的前两项，忽略 (x - x0)2及其后的各项，则可以得到 f (x) 在 x0 附近的近似线性展开式： * 假设 f ?(x0) ? 0，则上式的解为： 如果将上面公式求得的 x 作为原方程的一个新的近似根 x1，将 f (x) 在 x1 附近作近似线性展开，可求得另一个新的近似根 x2 。如此重复上述过程，可得到一般的迭代公式： 这种迭代方法称为牛顿法 牛顿迭代公式 * 显然，牛顿法对应的方程为： 牛顿法的迭代函数为： 如果 x* 是方程 f (x) = 0 的一个单根，即： 其中： 由于： 而 则 ，因此 的邻近迭代过程具有局部收敛性 * 牛顿法的几何意义 x y 0 牛顿法又叫切线法 * 牛顿法的计算步骤 选择合适的初始近似根 x0，计算 f (x0) 和 f ?(x0) 将 x0 代入迭代公式： 求得一个新的近似根 x1，并计算 f (x1) 和 f ?(x1) 求得达到精度要求的近似根 超过预定的迭代次数 N 后仍未达到精度要求 迭代过程中存在 f ?(xk) = 0，此时应终止迭代 检查 | x1 - x0 | ? e 且 f ?(x1) ? 0，如成立，则迭代终止，方程的近似根 x1；如不成立，则将 x1 代入迭代方程，重复前述步骤 * 牛顿法的收敛速度 设 x*是 f (x) = 0 的一个准确单根， f (x) 在 x* 附近具有连续的二阶导数，且 f ?(x*) ? 0，则牛顿法具有二阶收敛速度，即牛顿法是平方收敛 牛顿法的迭代函数为： * 牛顿法举例 每步迭代只做一次除法和一次加法再做一次移位即可，计算量少