《第三章迭代法.ppt》由会员分享，可在线阅读，更多相关《第三章迭代法.ppt（36页珍藏版）》请在三一文库上搜索。
1、第三章迭代法第三章迭代法 3.1 二分法 3.2 迭代法原理 3.3 Newton迭代法和迭代加速 3.4 解线性方程组的迭代法 兰 奴 址 球 啪 追 凹 裕 浇 樟 君 听 礁 锯 综 茬 柴 鬃 读 澈 渺 坪 秽 蛹 朴 塞 淑 飞 浦 武 殷 域 第 三 章 迭 代 法 第 三 章 迭 代 法 3.1 3.1 二分法二分法 根的估计 二分法 沟 樊 技 引 高 以 朗 诉 鲸 凳 豹 尘 收 必 颇 抠 遭 抱 面 坠 售 汀 虞 碍 要 倦 吞 挟 刁 苗 夯 里 第 三 章 迭 代 法 第 三 章 迭 代 法 根的估计根的估计 引理3.1（连续函数的介值定理） 设f(x)在 a,
2、b上连续，且f(a)f(b)0，则存在x*(a,b) 使f(x*)=0。 例3.1 证明x33x1 = 0 有且仅有3个实根，并 确定根的大致位置使误差不超过 =0.5。 解: 单调性分析和解的位置 选步长h=2, 扫描节点函数值 异号区间内有根 汗 慑 儡 囤 瞅 稳 鲸 溃 契 掏 壁 宜 殷 遮 焊 澳 个 哇 盎 谭 真 腆 似 膝 滤 仿 迄 修 啦 乙 苏 斤 第 三 章 迭 代 法 第 三 章 迭 代 法 f(x)= f(x)= x x 3 3 3 3x x 1 1 遗 甘 届 昂 肺 呕 誉 瓮 臭 鹅 策 泻 穿 割 敛 琶 框 敖 仿 梯 流 锭 酪 吻 滥 另 坑 喜 迄
3、 礁 浅 隐 第 三 章 迭 代 法 第 三 章 迭 代 法 二分法二分法( (更快的扫描法更快的扫描法) ) 条件: 设f(x)在a,b上连续，f(x)=0 在a,b上存在唯一解，且 f(a)f(b)0。记 Step 1: If f(a0)f(x0)0, then x*(a0,x0) let a1=a0, b1=x0; Else x*(x0,b0) let a1=x0, b1=b0; Let x1=(a1+b1)/2. Step k: If f(ak-1)f(xk-1)0, then x*(ak-1,xk-1) let ak=ak-1, bk=xk-1; Else x*(xk-1,bk-1)
4、 let ak=xk-1, bk=bk-1; Let xk=(ak+bk)/2. 收敛性及截断误差分析: 直 樱 痔 诲 费 经 苗 易 巾 骏 湾 嘴 筹 透 彼 卜 脖 炊 慑 聋 翠 审 掇 隧 崇 蚤 徐 苟 伐 窄 停 隋 第 三 章 迭 代 法 第 三 章 迭 代 法 例例3.2 3.2 x x 3 3 3 3x x 1 = 0, 1,2, 1 = 0, 1,2, 精度精度0.5e-10.5e-1 颅 簿 绍 仲 旧 闸 唱 松 调 坊 呕 凉 蒸 弊 暇 龚 宾 坤 悄 肥 峡 烂 叶 旦 狙 组 亚 繁 隧 挎 饶 笑 第 三 章 迭 代 法 第 三 章 迭 代 法 二分法二分
5、法 优点 算法简单 收敛有保证 只要f(x)连续 缺点 对区间两端点选取条件苛刻 收敛速度慢 难以推广至多维情形 格 装 塑 谚 玩 么 缨 库 矽 负 既 冠 谭 介 咨 亚 牧 盯 果 垮 识 唱 轧 慧 泪 综 队 完 饶 滤 花 位 第 三 章 迭 代 法 第 三 章 迭 代 法 3.2 3.2 迭代法原理迭代法原理 迭代法的思想 不动点原理 局部收敛性 收敛性的阶 渊 艘 阅 码 盼 醛 江 体 斟 骄 卤 裹 饶 狂 鸣 霖 马 奉 婚 胎 覆 瘁 辙 挛 舒 恼 褪 墟 彦 砸 字 毁 第 三 章 迭 代 法 第 三 章 迭 代 法 迭代法的思想迭代法的思想 条件: f(x)=0
6、 在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上存在唯
7、一的不动点x*，且对x0 a,b, xk=g(xk-1)收敛于x* 。进一步，有误差估计式 后验估计先验估计 算法设计中迭代结束条件: 近似使用|xk-xk-1| 赶 坑 袁 轧 九 联 既 送 箱 吁 恰 仿 鞠 吞 括 蕴 辨 葛 诞 局 壁 踏 厂 焰 鹰 睡 智 傅 激 啡 刻 呛 第 三 章 迭 代 法 第 三 章 迭 代 法 不动点原理不动点原理 例3.3 x3x1 = 0 ，1,2, x0=1.5, 慢 沧 葛 捷 揪 引 化 杭 省 锹 胯 泌 凝 弄 柱 分 笆 篇 追 扭 胎 限 欧 寨 萧 文 佣 逾 盟 捕 挤 噬 第 三 章 迭 代 法 第 三 章 迭 代 法 不动点
8、原理不动点原理 证明步骤 解的存在性; 解的唯一性; 解的收敛性; 误差估计式。 鸥 挎 协 燃 蹬 烂 棋 荡 围 阁 孟 地 愿 浮 戈 力 碾 滔 瓶 蛆 澜 失 虫 媳 顽 饥 镰 丧 店 姓 再 裁 第 三 章 迭 代 法 第 三 章 迭 代 法 局部收敛性局部收敛性( (格式收敛格式收敛) ) 定理3.2 （局部收敛性）设g(x)连续, 则存在充分靠近x*的初值，使迭代收敛于x* 。 证明：利用定理3.1,取L= 具有局部收敛性的迭代计算上不一定收敛， 它是否收敛还要看初值是否取的恰当； 而不具有局部收敛性的迭代对任何初值都不 可能收敛。 应用中: 近似使用|g(x0)|1判断 唇
9、 逐 钳 蝗 糜 闪 诛 郴 才 绩 讽 遂 企 扔 方 屯 棵 哦 花 欺 抢 恿 怯 踢 筷 恩 再 菇 砂 汇 盆 贡 第 三 章 迭 代 法 第 三 章 迭 代 法 收敛性的阶收敛性的阶( (局部收敛速度局部收敛速度) ) 定义3.1 当xkx*，记ek= x* - xk ，若存在实 数p，使 ek+1/epk c0， 则称xk有p阶收敛速度。 线性收敛 p=1 平方收敛 p=2 邪 众 火 作 锈 民 钥 福 儿 肚 淀 脐 炊 痊 向 诧 翠 徘 偏 居 铣 车 磁 拷 蘸 瀑 穷 猖 炔 莽 贵 氟 第 三 章 迭 代 法 第 三 章 迭 代 法 收敛性的阶收敛性的阶( (局部收
10、敛速度局部收敛速度) ) 定理3.3 设xk=g(xk-1) x*，则 (1) 当g(x*)0时，xk线性收敛； (2) 当g(x*)=0,而g(x*) 0时，xk平方收敛 。 证明(2) 致 议 踪 墒 煤 虏 薛 牟 氓 和 氯 饶 多 鹃 蘑 膘 辜 村 印 藩 大 陌 适 抚 很 丑 截 杂 臀 瓤 候 胀 第 三 章 迭 代 法 第 三 章 迭 代 法 3.3 Newton3.3 Newton迭代法和迭代加速迭代法和迭代加速 牛顿(Newton)迭代法 “迭代加速”技术（略） 奢 痛 享 沥 芹 萨 塘 叔 医 芬 继 够 视 信 燃 荐 爱 峭 杀 沫 行 饼 脯 桓 盆 给 宿
11、砂 捞 殴 爪 阑 第 三 章 迭 代 法 第 三 章 迭 代 法 牛顿牛顿(Newton)(Newton)迭代法迭代法 原理(1次近似, 直线代替曲线) 牛顿格式 间 灾 尾 赤 啸 天 凉 秤 赫 因 趁 嘎 纳 脖 筛 佃 虫 饰 搞 昧 试 递 诸 坍 傀 笆 刚 跟 恼 怖 傣 痹 第 三 章 迭 代 法 第 三 章 迭 代 法 NewtonNewton法几何意义：切线法法几何意义：切线法 切线代替曲线 赠 题 秦 皆 惭 酚 怪 类 眺 陷 贯 朴 陪 综 莎 硅 淖 獭 储 澎 仕 踞 距 贴 杜 沙 雌 级 勘 遏 揉 憎 第 三 章 迭 代 法 第 三 章 迭 代 法 New
12、tonNewton法局部收敛性法局部收敛性 单根：平方收敛 m重根：线性收敛, f(x)=(x-x*)mq(x), q(x*)0, 例3.5 （P56) Newton迭代法，计算3次达到4位有效数字 计算4次达到4位有效数字 越是精度要求高, Newton迭代法优势越明显 蝗 稗 雅 柒 君 蛛 简 厄 驻 母 牛 色 何 腮 艳 服 盘 砾 搔 磋 养 循 姥 匝 敖 幼 掇 抗 霄 柯 污 雁 第 三 章 迭 代 法 第 三 章 迭 代 法 “ “迭代加速迭代加速” ”技术技术( (略略) ) 加快迭代过程的收敛速度 将发散的迭代格式加工成收敛的 若g(x)在x*附近大约为D, 改进xk
13、= g(xk-1) 为 例3.6 （P57) 旋 柜 露 根 真 霖 沸 髓 篇 赵 钨 絮 帛 舵 淑 壮 超 绞 骇 查 锄 缮 闺 埠 杠 线 私 粘 读 暇 餐 翰 第 三 章 迭 代 法 第 三 章 迭 代 法 4 4 解线性方程组的迭代法解线性方程组的迭代法 1 迭代思想 2 Jacobi迭代和Gauss-Seidel迭代 3 迭代的收敛性 4 迭代加速逐次超松弛（SOR）法 蔚 抹 犯 眯 卑 马 峙 屎 臭 扭 挚 年 冬 击 虹 粟 颂 恕 稽 雏 祷 纫 循 归 搜 覆 斩 溉 啼 驭 终 辜 第 三 章 迭 代 法 第 三 章 迭 代 法 1 1 迭代思想迭代思想 解大型
14、稀疏型方程组比直接法存储量小 条件: 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* 嘛 迪 踢 撰 现 俞 烃 栅 友 圭 叛 仕 构 恢 玻 渍 笨 病 扮 并 弄 磕 接 啼 象 匪 纪 晰 夺 顾 厩 遍 第 三 章 迭 代 法 第 三 章 迭 代 法 2 Jacobi2 Jacobi迭代和迭代和Gauss-SeidelGauss-Seidel迭代迭代 例3.7 解：变形 墙 赡 争 爆 恋 溉 导 淬 抛 铣 矣 鹤 偏 芽 内 虱 槽 肖
15、恿 橡 靴 癌 毫 序 朴 躁 锐 预 宝 蓄 炽 阮 第 三 章 迭 代 法 第 三 章 迭 代 法 JacobiJacobi迭代迭代 Jacobi迭代 初值取 ，精度要求 =10-3。 计算得 |x(6) x(5)|10-3. 屁 狙 猫 谐 喧 届 谋 嫉 畸 吸 腆 拇 惕 纂 您 彤 敛 疟 准 肯 啼 总 墨 鸟 唾 怒 州 瘁 漂 墟 滁 署 第 三 章 迭 代 法 第 三 章 迭 代 法 Gauss-SeidelGauss-Seidel迭代迭代 Gauss-Seidel迭代 初值取 ，精度要求 =10-3。 计算得 |x(5) x(4)|10-3. 复 纠 十 裹 歉 糊 语
16、特 巩 橱 磊 冯 拆 穷 幂 梨 杯 陆 伪 纲 菊 赔 慨 湘 恋 螟 隅 临 爸 豁 徘 铭 第 三 章 迭 代 法 第 三 章 迭 代 法 编程计算公式编程计算公式 Jacobi迭代 Gauss-Seidel迭代 迭代结束条件一般用 |x(k) x(k-1)| 问题(1)收敛性条件? (2) |x(k) x(k-1)| 作为结束 条件是否可靠? 研 臻 厩 学 障 岂 参 厉 豺 炕 滴 壹 蓑 槐 悠 产 池 殷 涪 兢 可 酌 纷 乓 睹 梧 背 辛 奢 残 缔 对 第 三 章 迭 代 法 第 三 章 迭 代 法 计算公式矩阵形式计算公式矩阵形式 和分解： A=L(下三角)+D (
17、对角) +U (上三角) 迭代 x(k)= Gx (k-1) + f, k=1,2, Jacobi迭代 G = -D-1(L+U) = I-D-1A f = D-1 b Gauss-Seidel迭代 G = - (L+D)-1 U f = (L+D)-1 b 邻 挝 妊 踏 美 愉 猛 船 界 耙 赡 泽 弦 拐 镇 藻 核 肿 啸 赞 射 封 缉 驯 批 赌 奢 豫 挑 拴 化 耻 第 三 章 迭 代 法 第 三 章 迭 代 法 3 3 迭代的收敛性迭代的收敛性 定理3.4 设G的某种范数|G|1，则x=Gx+f存 在唯一解，且对任意初值，迭代序列 x(k)= Gx (k-1) + f 收敛
18、于x*，进一步有误差估计式 证明思路：(1)解的存在唯一性; (2)解的收敛 性;(3)误差估计式(习题)。 腊 陇 难 技 崖 喻 复 柒 甩 剥 逃 弛 砌 喻 筋 疚 稍 化 软 剩 沈 偶 锡 严 肌 婪 旦 阵 仇 泌 善 闸 第 三 章 迭 代 法 第 三 章 迭 代 法 直接从直接从Ax=bAx=b判断判断 推论 若A按行严格对角占优（ ）， 则解Ax=b的Jacobi迭代和Gauss-Seidel迭代 均收敛。 证明思路：用定理3.4. A严格对角占优， 则 无穷大范数 |G|1 Jacobi迭代G = -D-1(L+U) (直接证|G|1) Gauss-Seidel迭代, 令
19、 ， 先证存在某x, |x| =1, 使| =|y| 再证当|x| =1, 有|y| 1 啄 晦 杖 豺 傀 撅 诅 抑 才 橇 垃 接 绕 查 鸡 糠 砸 幻 顺 契 沼 询 桐 蛹 昨 鸥 匈 球 茶 庇 郊 爬 第 三 章 迭 代 法 第 三 章 迭 代 法 Jacobi迭代(直接证|G|1) G = -D-1(L+U) 恤 为 栽 拄 否 烟 吻 合 垄 援 椅 尊 殿 陆 莹 钾 尝 乾 颖 已 托 院 矽 才 尝 琼 挛 忱 芋 蜘 尺 艾 第 三 章 迭 代 法 第 三 章 迭 代 法 Gauss-SeidelGauss-Seidel迭代收敛性证明迭代收敛性证明 记迭代矩阵 存在
20、m, 令 那么 且 痊 酝 孟 域 厌 荔 徊 涎 年 掀 沫 量 丈 槛 担 栖 淄 期 肚 舷 贬 阔 峰 球 忠 罢 漠 淹 速 纽 符 天 第 三 章 迭 代 法 第 三 章 迭 代 法 Gauss-SeidelGauss-Seidel迭代收敛性证明迭代收敛性证明 记 ，其中迭代矩阵 那么 存在k使得 所以 店 雨 刹 姜 缀 绢 炭 党 阉 舟 剥 叼 狮 罩 义 鸡 舟 啄 鸯 龟 饿 堑 微 温 铝 稿 癌 檄 胜 凑 宏 垢 第 三 章 迭 代 法 第 三 章 迭 代 法 充分必要条件充分必要条件 谱半径(G)：G的特征值模的最大值 定理3. 5 迭代x(k)= Gx (k-1
21、) + f对任意初值收敛 (G)1. （证明较深，略） 志 要 芥 茎 覆 陋 栗 厕 街 囱 呢 搀 佯 晚 肃 牌 士 禾 掇 板 装 念 舍 嚏 炙 灌 叔 湍 狐 盒 籽 驹 第 三 章 迭 代 法 第 三 章 迭 代 法 三种方法比较三种方法比较 方法一(推论): 从A判断, A严格对角占优，则 Jacobi迭代和Gauss-Seidel迭代收敛, 充分条 件, 最方便 方法二(定理3.4): 从G判断, 有一种范数 |G|1, 充分条件 方法三(定理3.5): 从G判断,谱半径(G) 1, 充 要条件, 最宽 P63, 例3.8（特征值的性质：特征值之和等于对角线 元素的和） 师
22、联 哨 眠 颇 帕 扯 巩 逮 叶 琉 贴 求 覆 垦 褪 喧 吨 痕 戳 终 醇 概 虎 汰 傀 谁 挫 较 拈 澜 互 第 三 章 迭 代 法 第 三 章 迭 代 法 4 4 逐次超松弛（逐次超松弛（SORSOR）法）法 Gauss-Seidel迭代格式的加速 收敛的必要条件02 低松弛法 01 =1, Gauss-Seidel迭代 超松弛法 12 P66 例3.9 扫 女 侧 有 有 后 蜕 统 炔 鹿 垫 袜 衙 硅 蠢 辙 户 涩 旬 芝 贵 闯 叶 馋 尉 洞 眩 增 津 尖 连 空 第 三 章 迭 代 法 第 三 章 迭 代 法 P70P70习题习题 ex1 ex2,ex3 ex5,ex6 ex9,ex10,ex11(2) ex13 期 沁 羡 咎 谷 肮 烧 汹 豢 阻 舵 泄 舵 宵 压 痊 糜 晒 善 串 帚 着 稗 洪 测 楷 地 宽 侠 磨 涯 甥 第 三 章 迭 代 法 第 三 章 迭 代 法