书签 分享 收藏 举报 版权申诉 / 30
上传文档赚钱

类型数值分析10方程求根的迭代法课件.ppt

  • 上传人(卖家):晟晟文业
  • 文档编号:4370612
  • 上传时间:2022-12-03
  • 格式:PPT
  • 页数:30
  • 大小:384.37KB
  • 【下载声明】
    1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
    2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
    3. 本页资料《数值分析10方程求根的迭代法课件.ppt》由用户(晟晟文业)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
    4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
    5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
    配套讲稿:

    如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。

    特殊限制:

    部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。

    关 键  词:
    数值 分析 10 方程 求根 迭代法 课件
    资源描述:

    1、第四章 方程求根的迭代法高 云方程求根需要考虑的问题求求 f(x)=0 的根的根q 代数方程:代数方程:f(x)=a0+a1x+.+anxn超越方程:超越方程:f(x)含超越函数,如含超越函数,如 sin(x),ex,lnx 等等q 实根与复根实根与复根q 根的重数根的重数 f(x)=(x x*)m g(x)且且 g(x*)0,则则 x*为为 f(x)的的 m 重根重根q 有根区间:有根区间:a,b 上存在上存在 f(x)=0 的一个实根的一个实根在在有根的前提下求出方程的的前提下求出方程的近似根。研究研究 内容:内容:迭代法的基本思想0)(xf基基本本思思路路)(xx 同解同解迭代迭代公式公

    2、式)(1kkxx 给定初值给定初值0 xnnxxxx110 序序列列*limxxnn 存在存在*)(xx 0)(*xf等价于等价于迭代迭代函数函数?转换是转换是否唯一否唯一的不动点的不动点为为)(*xx 几何几何意义意义 )(xyxy 转换例子(1)x=1(x)=x3-6x2+10 x-2;(2);32926()()xxxx(3);32326923129()xxxxxxxx(4);234692()xxxx 例:已知方程已知方程 x3-6x2+9x-2=0 在在 3,4 内有一根,考虑迭代内有一根,考虑迭代?哪种转换方法好哪种转换方法好几何含义xyy=xxyy=xx*x*y=g(x)y=g(x)

    3、x0p0 x1p1 x0p0 x1p1 几何含义xyy=xxyy=xx*x*y=(x)y=(x)x0p0 x1p1x0p0 x1p1压缩映像定理定理定理设设 (x)Ca,b 且可导,若且可导,若(2)0 L 1,使得,使得|(x)|L 对对 x a,b 成立成立(1)a (x)b 对一切对一切 x a,b 都成立都成立则有则有(a)对任意对任意 x0 a,b,由,由 xk+1=(xk)产生的迭代序列产生的迭代序列 均收敛到均收敛到 (x)在在 a,b 中的唯一不动点中的唯一不动点 x*。0kkx(b)有如下的误差估计有如下的误差估计11|*|1kkkxxxxL10|*|1kkLxxxxL可用可

    4、用|x k+1-xk|来控制收敛精度来控制收敛精度L 越小收敛越快越小收敛越快压缩映像定理证明(a)由压缩映像定理可知,不动点由压缩映像定理可知,不动点 x*存在且唯一。存在且唯一。111()(*)|()|*|*|*|kkkkxxxxxxxLx 2120|*|*|*|*|kkkkxxL xxLxxLxxlim|*|0kkxx压缩映像定理证明(b)1|*|*|kkxxL xx111|(*)(*)|*kkkkkkxxxxxxxxxx(1)*kL xx11*1kkkxxxxL1111|()()|()|kkkkkkkkxxxxxxL xx 又又11101*111kkkkkkLLxxxxxxxxLLL全

    5、局收敛与局部收敛p 定理的条件保证了不动点迭代的定理的条件保证了不动点迭代的全局收敛性全局收敛性。即迭代的收敛性与初始点的选取无关。即迭代的收敛性与初始点的选取无关。p 这种在这种在 x*的邻域内具有的收敛性称为的邻域内具有的收敛性称为局部收敛性局部收敛性。定理中的条件定理中的条件|(x)|L 1 可以适当放宽可以适当放宽(2)(x)在在 x*的某个邻域内连续,且的某个邻域内连续,且|(x*)|1由由 (x)的连续性及的连续性及|(x*)|1 即可推出:即可推出:存在存在 x*的的某个某个 邻域邻域 N(x*)=x*-,x*+,使得对使得对 x N(x*)都有都有|(x)|L 1,则由则由 x

    6、0 N(x*)开始开始的迭代都收敛。的迭代都收敛。迭代过程的收敛速度1|lim0|krkkeCe定义定义则称该迭代为则称该迭代为 r 阶收敛。(1)当当 r=1 时称为时称为线性收敛,此时,此时 C 1 时称为时称为超线性收敛。p 二分法线性收敛二分法线性收敛p 不动点迭代中,若不动点迭代中,若 (x*)0,则则11*()(*)()kkkkexxxxe取极限得取极限得1|lim|(*)|0|krkkexe(C为常数为常数)线性收敛线性收敛P阶收敛设迭代设迭代 xk+1=(xk),若,若 (p)(x)在在 x*的某邻域内连续,的某邻域内连续,则该迭代法具有则该迭代法具有 p 阶收敛的充要条件是阶

    7、收敛的充要条件是定理定理(1)()(*)*,(*)(*)(*)0,(*)0ppxxxxxx()11lim(*)!pkrkkexep并且有并且有()1()()(*)(*)(*).(*)!ppkkkkkxxxxxxxxp证明:充分性充分性.根据泰勒展开有根据泰勒展开有()1()*(*)!ppkkkxxxxp()11lim(*)!pkrkkexep必要性的证明必要性必要性.设迭代设迭代 xk+1=(xk)是是 p 阶收敛。阶收敛。迭代两边取极限迭代两边取极限,由,由 (x)的连续性可知的连续性可知 x*=(x*)。设设 p0 是满足是满足00(1)()(*)(*)(*)0,(*)0 ppxxxx的最

    8、小正整数。的最小正整数。由充分性的证明过程可知迭代由充分性的证明过程可知迭代 p0 阶收敛。阶收敛。00111kkppppkkkeeeee又又若若 p0 p,与迭代与迭代 p 阶收敛矛盾阶收敛矛盾p0=p迭代过程的加速p 设有不动点迭代:设有不动点迭代:1()kkxx 1*()(*)()(*)kkkxxxxxx 11()*()kkxxx 设:设:()()kx 11()*()kkkkxxxxx 11()()()kkkkkxxxxx 缺点缺点:每次迭代需计算每次迭代需计算()kx 埃特金算法1*()(*)kkkxxxx 设:设:1()()kk 12*kkkkxxxxxxxx Aitken 加速加速

    9、211*()(*)kkkxxxx 21212*kkkkkkxxxxxxx 21 2(),()kkkkkkkkkkkyxzyyxxxzyx 当当 x 收敛到收敛到 x*时,修正项分子趋于零。时,修正项分子趋于零。一点注记0)(xf)(xfxx )()(xfxx )(11)(11)(111kkkkkkkkxfLxlxxfxLlxxLx 1)(11 LMxfMxxkkkNewton迭代迭代p 基本思想:基本思想:将非线性方程将非线性方程线性化设设 xk 是是 f(x)=0 的近似根,的近似根,将将 f(x)在在 xk 一阶一阶 Taylor 展开展开:2()()()()()()2!kkkkff xf

    10、 xf xxxxx,在在 xk 和和 x 之间。之间。0(*)f x()()(*)kkkf xf xxx()*()kkkf xxxf x1()()kkkkf xxxf xxyx*xkxk+1条件:条件:f(x)0Newton迭代迭代p Newton 法可以看作下面的不动点迭代:法可以看作下面的不动点迭代:1()kkxx其中其中()()()f xxxf x2()()()()f x fxxfx(x*)=0Newton 法至少法至少 二阶 局部收敛定理定理 设设 f(x)在其零点在其零点 x*的某个邻域内的某个邻域内二阶连续可导二阶连续可导且且 f(x)0,则存在,则存在 x*的的某个某个 邻域邻域

    11、 N(x*)=x*-,x*+,使得对使得对 x0 N(x*),Newton 法产生的序列以法产生的序列以不低于不低于二阶二阶的收敛速度收敛到的收敛速度收敛到 x*。Newton迭代迭代p Newton 法也可以看作一类特殊的加速迭代法也可以看作一类特殊的加速迭代11()()()kkkkkxxxxx 取取 (x)=x-f(x)1111()()()kkkkkkxf xfxxxfx ()()()kkkkf xx fxfx ()()kkkf xxfx收敛性定理收敛性定理定理定理设设 f C2a,b,且,且 f 满足满足(1)f(a)f(b)0;则则 Newton 法产生的序列收敛到法产生的序列收敛到

    12、f 在在 a,b 的唯一零点的唯一零点 x*。全局收敛性定理全局收敛性定理定理定理设设 f C2a,b,且,且 f 满足满足(1)f(a)f(b)0)。a解:转化为求转化为求 x2-a=0 的正根的正根Newton 迭代:迭代:12()2(12kkkkkkkkkf xxaxaxxxf xxx212kkkxaxaax22222kkkkkxaxaxaxx1212kkkxaxxa12 a二阶收敛二阶收敛mynewton.m重根情形重根情形p 设设 x*是是 f(x)的的 m(m 2)重根,重根,Newton法是否收敛?法是否收敛?10 0()()(*)(*)(*),(*)mmf xfxfxfx Ta

    13、ylor 展式展式11()()()(*)!mmf xfxxm 1211()()()(*)()!mmfxfxxm 2312()()()(*)()!mmfxfxxm Newton 迭代:迭代:()()()f xxxf x2*()()(*)lim()lim()xxxxf x fxxxfx11m 线性收敛。线性收敛。且重数且重数 m 越高,收敛越慢。越高,收敛越慢。提高收敛阶提高收敛阶p 提高收敛速度提高收敛速度但但 m 通常无法预先知道通常无法预先知道!法一:取法一:取()()()f xxxmf x(*)0 x二阶收敛二阶收敛法二:将求法二:将求 f(x)的重根转化为求的重根转化为求 另一个函数另一

    14、个函数 的单根。的单根。构造针对构造针对 (x)的具有二阶收敛的的具有二阶收敛的 Newton 迭代:迭代:2()()()()()()()()xf x fxxxxxfxf x fx令令 ,则,则 x*是是 (x)的单重根。的单重根。()()()f xxf x降低初始点的要求降低初始点的要求例:例:求求 sin(x)-x/6=0 的正根。的正根。mynewton.mp Newton 下山法:下山法:1 ()()kkkkf xxxfx k k 为数列为数列 中满足中满足 的最大数。的最大数。012ll 1()()kkf xf x p 算法 7.2(Newton下山法下山法)给定初始点给定初始点 x

    15、0,精度要求,精度要求 1.如果如果|f(xk)|,停机,输出停机,输出 xk2.计算计算 ,=1()()kkkdf xfx 3.如果如果|f(xk+dk)|f(xk)|,令,令 xk+1=xk+dk,返回第,返回第1步;步;否则否则 折半,重新计算第折半,重新计算第3步步Newton 法的收敛依赖于初始点的选取。法的收敛依赖于初始点的选取。割线法割线法p Newton法的缺点:法的缺点:每步迭代都要计算导数值每步迭代都要计算导数值 只需计算函数值,避免计算导数;只需计算函数值,避免计算导数;切线斜率切线斜率 割线斜率割线斜率11()()()kkkkkf xf xfxxx 111()()()(

    16、)kkkkkkkf xxxxxf xf x xk-1xkxk+1xk+1切线切线割线割线 需要两个初始点;需要两个初始点;收敛比收敛比Newton法稍慢,但对初始点要求同样高。法稍慢,但对初始点要求同样高。割线法公式割线法公式111()()()()kkkkkkkf xxxxxf xf x p 两点割线法100()()()()kkkkkf xxxxf xfxx p 单点割线法误差估计误差估计引理引理 设设 f(x)在其零点在其零点 x*的的某个邻域某个邻域 N(x*)=x*-,x*+内存在连续的二阶导数,且内存在连续的二阶导数,且 f(x)0,又设,又设 xk-1,xk N(x*)x*,且互不相等,则由两点割线法的误差,且互不相等,则由两点割线法的误差 ek=xk-x*满足满足112()()kkkkkfee ef 其中其中 11,min,*,max,*kkkkkkxx xxx x 局部收敛性定理局部收敛性定理定理定理 设设 x*是是 f(x)的单重零点,的单重零点,f”(x)在在 x*的的某个邻域内连某个邻域内连续,则存在续,则存在 x*的的一个邻域一个邻域 N(x*)=x*-,x*+,使得当,使得当x0,x1 N(x*)时,由两点割线法产生的序列收敛到时,由两点割线法产生的序列收敛到 x*,且收,且收敛阶为敛阶为 5 1 2 1618.本章结束谢谢!

    展开阅读全文
    提示  163文库所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
    关于本文
    本文标题:数值分析10方程求根的迭代法课件.ppt
    链接地址:https://www.163wenku.com/p-4370612.html

    Copyright@ 2017-2037 Www.163WenKu.Com  网站版权所有  |  资源地图   
    IPC备案号:蜀ICP备2021032737号  | 川公网安备 51099002000191号


    侵权投诉QQ:3464097650  资料上传QQ:3464097650
       


    【声明】本站为“文档C2C交易模式”,即用户上传的文档直接卖给(下载)用户,本站只是网络空间服务平台,本站所有原创文档下载所得归上传人所有,如您发现上传作品侵犯了您的版权,请立刻联系我们并提供证据,我们将在3个工作日内予以改正。

    163文库