第三章迭代法.ppt
《第三章迭代法.ppt》由会员分享,可在线阅读,更多相关《第三章迭代法.ppt(36页珍藏版)》请在三一文库上搜索。
1、第三章迭代法,3.1 二分法 3.2 迭代法原理 3.3 Newton迭代法和迭代加速 3.4 解线性方程组的迭代法,3.1 二分法,根的估计 二分法,根的估计,引理3.1(连续函数的介值定理) 设f(x)在a,b上连续,且f(a)f(b)0,则存在x*(a,b)使f(x*)=0。 例3.1 证明x33x1 = 0 有且仅有3个实根,并确定根的大致位置使误差不超过 =0.5。 解: 单调性分析和解的位置 选步长h=2, 扫描节点函数值 异号区间内有根,f(x)= x33x1,二分法(更快的扫描法),条件: 设f(x)在a,b上连续,f(x)=0在a,b上存在唯一解,且f(a)f(b)0。记,S
2、tep 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) let ak=xk-1, bk=bk-1; Let xk=(ak+bk)/2.,收敛性及截断误差分析:,例3.2 x33x1 = 0, 1,2, 精度0.5e-1,二分法,优点 算法简单 收敛有保证 只要f(x
3、)连续 缺点 对区间两端点选取条件苛刻 收敛速度慢 难以推广至多维情形,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
4、, xk=g(xk-1)收敛于x* 。进一步,有误差估计式,算法设计中迭代结束条件: 近似使用|xk-xk-1|,不动点原理,例3.3 x3x1 = 0 ,1,2, x0=1.5,不动点原理,证明步骤 解的存在性; 解的唯一性; 解的收敛性; 误差估计式。,局部收敛性(格式收敛),定理3.2 (局部收敛性)设g(x)连续, 则存在充分靠近x*的初值,使迭代收敛于x*。 证明:利用定理3.1,取L= 具有局部收敛性的迭代计算上不一定收敛,它是否收敛还要看初值是否取的恰当; 而不具有局部收敛性的迭代对任何初值都不可能收敛。,应用中: 近似使用|g(x0)|1判断,收敛性的阶(局部收敛速度),定义3
5、.1 当xkx*,记ek= x* - xk ,若存在实数p,使 ek+1/epk c0, 则称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平方收敛。,证明(2),3.3 Newton迭代法和迭代加速,牛顿(Newton)迭代法 “迭代加速”技术(略),牛顿(Newton)迭代法,原理(1次近似, 直线代替曲线) 牛顿格式,Newton法几何意义:切线法,切线代替曲线,Newton法局部收敛性,单根:平方收敛 m重根:
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第三 迭代法
链接地址:https://www.31doc.com/p-2568935.html