第四章 方程求根的迭代法优秀PPT.ppt

第四章 方程求根的迭代法第一页，本课件共有45页012345610.50.6666660.60.6250.6153850.619048789101112130.6176470.6181820.6179780.6180560.6180260.6180370.618033第二页，本课件共有45页记笔记记笔记由由由由 得表一：得表一：得表一：得表一：由表一知迭代由表一知迭代由表一知迭代由表一知迭代 收敛于收敛于收敛于收敛于 的根的根的根的根 .而由而由而由而由 得表二：得表二：得表二：得表二：由表二知迭代由表二知迭代由表二知迭代由表二知迭代 是发散的是发散的是发散的是发散的01234561.51.375211.330681.325851.324931.324751.324730121.5 2.37512.3981.迭代函数如何构造？2.初值的选取3.误差估计（迭代结束的条件）例例 用迭代法求方程用迭代法求方程 ，在在x=1.5附近的一个根附近的一个根第三页，本课件共有45页 准确方程准确方程 校正量校正量 ，校正值，校正值 近似方程近似方程 校正方程校正方程 开方公式 忽忽略略高高阶阶小小量量 ,令令第四页，本课件共有45页1 开方法开方法记笔记记笔记k1.414214 1.4142141.4142161.4666671.51Xk4 53210一、公式的建立一、公式的建立二、直观解释二、直观解释第五页，本课件共有45页记笔记记笔记三、收敛性三、收敛性第六页，本课件共有45页令令 ，则由上式得，则由上式得对任意对任意 ，总有，总有 ，所以，所以 定理定理1 开方公式对于任意初值开方公式对于任意初值 均收敛均收敛 思考题思考题1若若 ，开方公式结果如何？，开方公式结果如何？2证明对于任意证明对于任意 ，开方公式所得序列，开方公式所得序列单调减有下界单调减有下界k01234 5Xk1 1.51.4666671.4142161.414214 1.414214第七页，本课件共有45页 准确方程准确方程 校正量校正量 ，校正值，校正值 近似方程近似方程 校正方程校正方程 Newton公式 令令迭代函数 2 法法一、公式的导出一、公式的导出第八页，本课件共有45页二、几何解释二、几何解释Newton法又称为Newton切线法或切线法第九页，本课件共有45页yx0 x0f(x)0X*yx0 x0f(x)0yx0f(x)0 x0 从几何的角度探讨从几何的角度探讨牛顿迭代法的收敛性牛顿迭代法的收敛性第十页，本课件共有45页x1y0 x0X*0 x0X*x2 不满足迭代条件时，可能导致迭代值远离不满足迭代条件时，可能导致迭代值远离根的情况而找不到根或死循环的情况根的情况而找不到根或死循环的情况 从几何角度探讨牛顿迭代法的收敛性从几何角度探讨牛顿迭代法的收敛性第十一页，本课件共有45页 三三 牛牛顿顿迭迭代代法法的的计计算算流流程程第十二页，本课件共有45页例例 用用牛顿迭代法牛顿迭代法求求 x=e-x的根的根,=10-5解：因解：因 f(x)=x ex 1,f(x)=ex(x+1)建立迭代公式建立迭代公式取取x0=0.5,逐次计算得逐次计算得 x1=0.571021,x2=0.567156,x3=0.567143,x4=0.567143第十三页，本课件共有45页求倒数 ，就是求解方程则相应的则相应的 迭代公式迭代公式思考题：讨论牛顿迭代法的收敛条件思考题：讨论牛顿迭代法的收敛条件，其其 法的迭代函数为法的迭代函数为第十四页，本课件共有45页3 压缩映象原理压缩映象原理 如果由迭代格式如果由迭代格式 产生的序列产生的序列 收敛收敛,即即 则称迭代法收敛则称迭代法收敛 结束条件第十五页，本课件共有45页(a)(b)第十六页，本课件共有45页第十七页，本课件共有45页定理定理2 设函数设函数 在在a,b上具有连续的一阶导上具有连续的一阶导 数数,且满足且满足（1）封闭性条件封闭性条件 对所有的对所有的xa,b 有有 a,b（2）压压缩缩性性条条件件 存存在在 0 L 1,使使所所有有的的xa,b有有 则则 方程方程 在在a,b上的根上的根 存在且唯一存在且唯一，对任意的，对任意的 a,b，迭代过程迭代过程均收敛于均收敛于 .且成立且成立 压缩映象原理压缩映象原理迭代结束的条件迭代结束的条件（事后误差估计法）满足精度要求的最大满足精度要求的最大迭代次数迭代次数（事先误差估计法）推论推论:若方程若方程 在区间在区间 内有根内有根 且且则迭代则迭代 均发散均发散第十八页，本课件共有45页例例1 1 对方程对方程 ,构造迭代函数如下构造迭代函数如下 ，.试讨论在试讨论在1,21,2上上迭代迭代 的敛散性的敛散性.解解 则则此时迭代公式满足迭代收敛条件，所以迭代此时迭代公式满足迭代收敛条件，所以迭代 在此区间上收敛在此区间上收敛.所以所以 此迭代此迭代 发散发散.第十九页，本课件共有45页例例2 已知 讨论迭代 在区间 的敛散性.例例4 求 的近似值，.例例3 用下列迭代法求 的正根 的近似值，试判断其敛散性.（1）；（2）.k1.414214 1.4142141.4142161.4666671.51Xk4 53210第二十页，本课件共有45页 迭迭代代法法的的算算法法框框图图实验：1.探讨初值对迭代收敛的影响.2.同一方程构造不同的迭代，探讨敛散性；比较收敛迭代的收敛快慢情况.第二十一页，本课件共有45页三、三、局部收敛性局部收敛性定理定理3 3 设设 在在 的根的根 的邻域中有连续的一阶的邻域中有连续的一阶导数导数,且且 则迭代过程则迭代过程 具有具有局部局部收敛性收敛性.未知，如何求未知，如何求？（1）定理）定理3对初值的要求比较高，一对初值的要求比较高，一般用对分法找出较满意的初值，定理般用对分法找出较满意的初值，定理2对初值的要求较宽松对初值的要求较宽松（2）一个迭代若是整体收敛的，则）一个迭代若是整体收敛的，则一定局部收敛；反之则不成立一定局部收敛；反之则不成立第二十二页，本课件共有45页例例5 已知方程 在 附近有一实根，讨论迭代 的敛散性.并计算结果，取 .解：令 ，则 取 计算结果见书 .附近的实根 ，且则取 收敛于 .第二十三页，本课件共有45页例例6 设设 ，要使迭代过程，要使迭代过程 局部收敛到局部收敛到 ,求求 的取值范围的取值范围.解：解：由在根由在根 邻域具有局部收敛性时，收敛邻域具有局部收敛性时，收敛 条件条件 所以所以 第二十四页，本课件共有45页例例7 7 已知方程已知方程 在在 内有根内有根 ,且在且在上满足上满足 ,利用利用 构造一个迭代函数构造一个迭代函数,使使 局部收敛于局部收敛于 .解解:由由 可得可得,故故 ,迭代公式迭代公式局部收敛于局部收敛于分析 ，则由习题9,对应的迭代发散.第二十五页，本课件共有45页定义定义2 2 设迭代过程设迭代过程 收敛于收敛于 的根的根 ,记迭代误差记迭代误差若存在常数若存在常数m m（m1m1）和和c c（），），使使 则称序列则称序列 是是 m 阶收敛的阶收敛的,特别地特别地,m=1=1时称为时称为线性收敛线性收敛,m=2=2时称为平方收敛时称为平方收敛.1 .1 m 2 2时称为时称为超线性收敛超线性收敛.四、迭代过程的收敛速度四、迭代过程的收敛速度 第二十六页，本课件共有45页例8 讨论迭代公式 ，的收敛阶.定理定理4 设迭代过程设迭代过程 ，若若 在所求根在所求根 的邻域连续且的邻域连续且 则迭代过程则迭代过程在在 邻域是邻域是m阶收敛的阶收敛的.第二十七页，本课件共有45页证明：则此迭代过程则此迭代过程是是m阶收敛的阶收敛的.迭代过程迭代过程 局部收局部收敛于敛于 ，又，又第二十八页，本课件共有45页例例9 已知迭代公式已知迭代公式 收敛于收敛于 证明该迭代公式平方收敛证明该迭代公式平方收敛.证证:迭代公式相应的迭代函数为迭代公式相应的迭代函数为将将 代入，代入，根据定理根据定理4可知，此迭代平方收敛可知，此迭代平方收敛.第二十九页，本课件共有45页 牛顿迭代法的收敛性分析牛顿迭代法的收敛性分析定理定理5 设设 是方程是方程 的单根的单根,且且f(x)在在 的某的某邻域内有连续的二阶导数邻域内有连续的二阶导数,则牛顿法是局部收敛的则牛顿法是局部收敛的,且至少为二阶收敛且至少为二阶收敛,有有 证证:牛顿迭代公式对应的迭代函数为牛顿迭代公式对应的迭代函数为 若若 是方程是方程 的单根的单根,则有则有 ,从而从而 由定理由定理3知知,牛顿迭代法在牛顿迭代法在 附近收敛附近收敛.又由定理又由定理4知知,迭迭代公式至少是二阶收敛的代公式至少是二阶收敛的.第三十页，本课件共有45页第三十一页，本课件共有45页利用泰勒公式利用泰勒公式所以所以 法逻辑结构简单，在单根附近时，收敛速度很快；但（1）若初值选取不当，迭代法可能失败或者收敛很慢；（2）若导数比较复杂，则每步的计算量较大；（3）若 为方程 的重根，结果如何？第三十二页，本课件共有45页4 法的改进与变形法的改进与变形012341.51.347831.325201.324721.3247201230.617.911.946807.98552第三十三页，本课件共有45页4 法的改进与变形法的改进与变形 下山法下山法其中其中(01)(01)为下山因子为下山因子 -下山法下山法 第三十四页，本课件共有45页 为避免计算函数的导数为避免计算函数的导数 ，使用差商，使用差商 称为称为弦截法弦截法迭代公式迭代公式.（单点弦截法单点弦截法）替代牛顿公式中的导数替代牛顿公式中的导数 ，便得到迭代公式，便得到迭代公式 第三十五页，本课件共有45页在单根附近线性收敛在单根附近线性收敛第三十六页，本课件共有45页 使用差商使用差商替代牛顿公式中的导数替代牛顿公式中的导数 ,便得到迭代公式便得到迭代公式 称为称为快速弦截法快速弦截法迭代公式迭代公式.（双点弦截法双点弦截法）在单根附近收敛，收敛阶为在单根附近收敛，收敛阶为1.618第三十七页，本课件共有45页例例10 用用快速快速弦截法求方程弦截法求方程 在在 初始初始值邻近的一个根值邻近的一个根.要求要求解：取解：取 ,令令 利用快速弦截法迭代公式利用快速弦截法迭代公式 k2340.567540.567150.56714第三十八页，本课件共有45页 快快速速弦弦截截法法算算法法实实现现 第三十九页，本课件共有45页迭代：迭代：改进：改进：5 加速算法加速算法或合并写成：或合并写成：第四十页，本课件共有45页例例11 用加权法加速技术求方程用加权法加速技术求方程 在在0.5附近的一个根附近的一个根.解：解：因为在因为在 附近附近 取取L=-0.6，建立如下迭代公式建立如下迭代公式仍取仍取 ,逐次计算得逐次计算得(精度为精度为 ）12340.566582 0.567132 0.567143 0.567143第四十一页，本课件共有45页Aitken加速公式加速公式第四十二页，本课件共有45页例例12 用埃特金方法求方程用埃特金方法求方程 在初值在初值 附近的一个根附近的一个根,精度要求精度要求 ，取迭代公式取迭代公式解解 埃特金方法迭代格式为埃特金方法迭代格式为只迭代二次就得到满足精度要求的解只迭代二次就得到满足精度要求的解.第四十三页，本课件共有45页作业作业习题四习题四 3（1）、）、5、10、12第四十四页，本课件共有45页课堂练习 1、6、7、8（1）、）、（2）、）、11、13、14、20、21第四十五页，本课件共有45页