计算方法迭代法.ppt

第三章迭代法 3 1二分法 3 2迭代法原理 3 3Newton迭代法和迭代加速 3 4解线性方程组的迭代法 3 1二分法 根的估计二分法 根的估计 引理3 1 连续函数的介值定理 设f x 在 a b 上连续 且f a f b 0 则存在x a b 使f x 0 例3 1证明x3 3x 1 0有且仅有3个实根 并确定根的大致位置使误差不超过 0 5 解 单调性分析和解的位置选步长h 2 扫描节点函数值异号区间内有根 f x x3 3x 1 二分法 条件 设f x 在 a b 上连续 f x 0在 a b 上存在唯一解 且f a f b 0 记 Step1 Iff a0 f x0 0 thenx a0 x0 leta1 a0 b1 x0 Elsex x0 b0 leta1 x0 b1 b0 Letx1 a1 b1 2 Stepk Iff ak 1 f xk 1 0 thenx ak 1 xk 1 letak ak 1 bk xk 1 Elsex xk 1 bk 1 letak xk 1 bk bk 1 Letxk ak bk 2 收敛性及截断误差分析 例3 2x3 3x 1 0 1 2 精度0 5e 1 二分法 优点算法简单收敛有保证只要f x 连续缺点对区间两端点选取条件苛刻收敛速度慢 3 2迭代法原理 迭代法的思想不动点原理局部收敛性收敛性的阶 迭代法的思想 条件 f x 0在x0附近有且仅有一个根设计同解变形x g x 迭代式xk g xk 1 k 1 2 如果收敛xk x 则x 是f x 0的根 不动点原理 迭代过程收敛 定理3 1 不动点原理 设映射g x 在 a b 上有连续的一阶导数且满足1o封闭性 x a b g x a b 2o压缩性 L 0 1 使对 x a b g x L 则在 a b 上存在唯一的不动点x 且对 x0 a b xk g xk 1 收敛于x 进一步 有误差估计式 算法设计中迭代结束条件 近似使用 xk xk 1 不动点原理 证明步骤解的存在性 解的唯一性 解的收敛性 误差估计式 例3 3 局部收敛性 格式收敛 定理3 2 局部收敛性 设g x 连续 则存在充分靠近x 的初值 使迭代收敛于x 证明 利用定理3 1 取L 具有局部收敛性的迭代计算上不一定收敛 它是否收敛还要看初值是否取的恰当 而不具有局部收敛性的迭代对任何初值都不可能收敛 应用中 近似使用 g x0 1判断 收敛性的阶 局部收敛速度 定义3 1当xk x 记ek x xk 若存在实数p 使ek 1 epk c 0 则称 xk 有p阶收敛速度 线性收敛p 1平方收敛p 2 定理3 3设xk g xk 1 x 则 1 当g x 0时 xk 线性收敛 2 当g x 0 而g x 0时 xk 平方收敛 3 3Newton迭代法和迭代加速 牛顿 Newton 迭代法 迭代 加速 技术 牛顿 Newton 迭代法 原理 1次近似 直线代替曲线 牛顿格式 Newton法几何意义 切线法 切线代替曲线 Newton法局部收敛性 单根 平方收敛m重根 线性收敛例3 5 P56 Newton迭代法 计算3次达到4位有效数字计算4次达到4位有效数字越是精度要求高 Newton迭代法优势越明显 迭代 加速 技术 加快迭代过程的收敛速度将发散的迭代格式加工成收敛的若g x 在x 附近大约为D 改进xk g xk 1 为例3 6 P57 4解线性方程组的迭代法 1迭代思想2Jacobi迭代和Gauss Seidel迭代3迭代的收敛性4迭代加速 逐次超松弛 SOR 法 1迭代思想 解大型稀疏型方程组比直接法存储量小条件 Ax b解存在唯一设计同解变形x Gx f迭代式x k Gx k 1 f k 1 2 取初值x 0 如果收敛x k x 则x 是Ax b的解x k x 2Jacobi迭代和Gauss Seidel迭代 例3 7解 变形 Jacobi迭代 Jacobi迭代初值取 精度要求 10 3 计算得 x 6 x 5 10 3 Gauss Seidel迭代 Gauss Seidel迭代初值取 精度要求 10 3 计算得 x 5 x 4 10 3 编程计算公式 Jacobi迭代Gauss Seidel迭代迭代结束条件一般用 x k x k 1 问题 1 收敛性条件 2 x k x k 1 作为结束条件是否可靠 计算公式矩阵形式 和分解 A L 下三角 D 对角 U 上三角 迭代x k Gx k 1 f k 1 2 Jacobi迭代G D 1 L U I D 1Af D 1bGauss Seidel迭代G L D 1Uf L D 1b 3迭代的收敛性 定理3 4设G的某种范数 G 1 则x Gx f存在唯一解 且对任意初值 迭代序列x k Gx k 1 f收敛于x 进一步有误差估计式证明思路 1 解的存在唯一性 2 解的收敛性 3 误差估计式 习题 直接从Ax b判断 推论若A按行严格对角占优 则解Ax b的Jacobi迭代和Gauss Seidel迭代均收敛 证明思路 用定理3 4 A严格对角占优 则无穷大范数 G 1Jacobi迭代 直接证 G 1 Gauss Seidel迭代 令y Gx 则y D 1 Ly Ux 先证存在某x x 1 使 G y 再证当 x 1 有 y 1 Gauss Seidel迭代收敛性证明 记迭代矩阵存在m 令那么且 Gauss Seidel迭代收敛性证明 记 其中迭代矩阵那么存在k使得所以 充分必要条件 谱半径 G G的特征值模的最大值定理3 5迭代x k Gx k 1 f对任意初值收敛 G 1 证明较深 略 三种方法比较 方法一 推论 从A判断 A严格对角占优 则Jacobi迭代和Gauss Seidel迭代收敛 充分条件 最方便方法二 定理3 4 从G判断 有一种范数 G 1 充分条件方法三 定理3 5 从G判断 谱半径 G 1 充要条件 最宽P63 例3 8 特征值的性质 特征值之和等于对角线元素的和 4逐次超松弛 SOR 法 Gauss Seidel迭代格式的