《方程求根的迭代法》PPT课件.ppt

第四章第四章 方程求根的迭代法方程求根的迭代法高次方程超越方程问题：问题：设设 是实系数多项式或是任意实函数，求是实系数多项式或是任意实函数，求 的的 根根 ，其中，其中 .定义定义 按照按照一定规则（某个固定的计算公式一定规则（某个固定的计算公式 ），）， 把解的近似值逐步精确化，直到满足实际问题的精把解的近似值逐步精确化，直到满足实际问题的精度要求度要求.―――――――― 迭代法迭代法其基本思想如下：其基本思想如下：①① 将方程将方程 转化为等价方程转化为等价方程 迭代函数迭代函数②② 取初值取初值 ，用显示公式，用显示公式 计算得数列计算得数列 ③③若若 ，则计算停止，否则继续迭代，则计算停止，否则继续迭代. .012345610.50. 6666660.60.6250.6153850.619048789101112130.6176470.6181820.6179780.6180560.6180260.6180370.618033记笔记记笔记由由由由 得表一：得表一：得表一：得表一：由表一知迭代由表一知迭代由表一知迭代由表一知迭代 收敛于收敛于收敛于收敛于 的根的根的根的根 . .而由而由而由而由 得表二：得表二：得表二：得表二：由表二知迭代由表二知迭代由表二知迭代由表二知迭代 是发散的．是发散的．是发散的．是发散的．01234561.51.375211.330681.325851.324931.324751.32473012…1.5 2.37512.398…1.迭代函数如何构造？2.初值的选取3.误差估计（迭代结束的条件）例例 用迭代法求方程用迭代法求方程 ，， 在在x=1.5附近的一个根附近的一个根§1 开方法开方法记笔记记笔记k1.414214 1.4142141.4142161.4666671.51Xk4 53210记笔记记笔记令令 ，则由上式得，则由上式得对任意对任意 ，总有，总有 ，所以，所以 ．．定理定理1 开方公式对于任意初值开方公式对于任意初值 均收敛．均收敛． 思考题思考题1．若．若 ，开方公式结果如何？，开方公式结果如何？ 2．证明对于任意．证明对于任意 ，开方公式所得序列，开方公式所得序列单调减有下界．单调减有下界．k01234 5Xk121.751.7321431.732051 1.732051 §2 法法－－－－ 迭代公式迭代函数1．是否收敛于方程的根或什么条件下收敛？2. 迭代函数有什么特性？ 牛顿迭代法的几何解释牛顿迭代法的几何解释Newton法又称为Newton切线法或切线法yx0x0f´´(x)>0X*yx0x0f´´(x)<0yx0f´´(x)<0x0yx0f´´(x)>0x0 从几何的角度探讨从几何的角度探讨牛顿迭代法的收敛性牛顿迭代法的收敛性x1y0x0X*0x0X*x2 不满足迭代条件时，可能导致迭代值远离不满足迭代条件时，可能导致迭代值远离根的情况而找不到根或死循环的情况根的情况而找不到根或死循环的情况 从几何角度探讨牛顿迭代法的收敛性从几何角度探讨牛顿迭代法的收敛性 牛牛顿顿迭迭代代法法的的计计算算流流程程例例 用用牛顿迭代法牛顿迭代法求求 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求倒数 ，就是求解方程则相应的则相应的 迭代公式迭代公式思考题：思考题：1. 讨论其收敛性及收讨论其收敛性及收敛条件敛条件2.讨论牛顿迭代法的收敛讨论牛顿迭代法的收敛条件．条件．，其其 法的迭代函数为法的迭代函数为§3 压缩映象原理压缩映象原理 如果由迭代格式如果由迭代格式 产生的序列产生的序列 收敛收敛, ,即即 则称迭代法收敛．则称迭代法收敛． －－－－－－ 结束条件(a)(b)定理定理2 设函数设函数 在在[a,b]上具有连续的一阶导上具有连续的一阶导 数数, 且满足且满足 （（1））封闭性条件封闭性条件 对所有的对所有的x∈∈[a,b] 有有 ∈∈[a,b] （（2））压压缩缩性性条条件件 存存在在 0 < L< 1 ,使使所所有有的的x∈∈[a,b]有有 则则 方程方程 在在[a,b]上的根上的根 存在且唯一存在且唯一，对任意的，对任意的 ∈ ∈[a ,b] ，，迭代过程迭代过程均收敛于均收敛于 . .且成立且成立①① ②② 压缩映象原理迭代结束的条件（事后误差估计法）满足精度要求的最大迭代次数（事先误差估计法）推论: 若方程 在区间 内有根 且则迭代 均发散例例1 1 对方程对方程 , ,构造迭代函数如下构造迭代函数如下①① ，， ②② . .试讨论在试讨论在[1,2][1,2]上迭代上迭代 的敛散性的敛散性. .解解 ①① 则则此时迭代公式满足迭代收敛条件，所以迭代此时迭代公式满足迭代收敛条件，所以迭代 在此区间上收敛在此区间上收敛. .②②所以所以 此迭代此迭代 发散发散. .例例2 已知 讨论迭代 在区间 的敛散性.例例4 求 的近似值， . 例例3 用下列迭代法求 的正根 的近似值，试判断其敛散性. （1） ；（2） . 迭迭代代法法的的算算法法框框图图实验 ：1.探讨初值对迭代收敛的影响.2.同一方程构造不同的迭代，探讨敛散性；比较收敛迭代的收敛快慢情况.三、三、 局部收敛性局部收敛性定理定理3 3 设设 在在 的根的根 的邻域中有连续的的邻域中有连续的一阶导数一阶导数, ,且且 则迭代过程则迭代过程 具有具有局部局部收敛性收敛性. . 未知，如何求未知，如何求 ？？（（1）定理）定理3对初值的要求比较高，对初值的要求比较高，一般用对分法找出较满意的初值，定一般用对分法找出较满意的初值，定理理2对初值的要求较宽松．对初值的要求较宽松．（（2）一个迭代若是整体收敛的，则）一个迭代若是整体收敛的，则一定局部收敛；反之则不成立．一定局部收敛；反之则不成立．例例5 已知方程 在 附近有一实根，讨论迭代 的敛散性.并计算结果，取 . 解：令 ，则 取 计算结果见书 .附近的实根 ，且则取 收敛于 .例例6 设设 ，要使迭代过程，要使迭代过程 局部收敛到局部收敛到 , ,求求 的取值范围的取值范围. .解：解： 由在根由在根 邻域具有局部收敛性时，收敛邻域具有局部收敛性时，收敛 条件条件 所以所以 例例7 7 已知方程已知方程 在在 内有根内有根 , ,且在且在上满足上满足 , ,利用利用 构造一个迭代函数构造一个迭代函数, ,使使 局部收敛于局部收敛于 . .解解: :由由 可得可得, , 故故 , ,迭代公式迭代公式局部收敛于局部收敛于分析 ，则由习题9,对应的迭代发散.定义定义2 2 设迭代过程设迭代过程 收敛于收敛于 的根的根 , ,记迭代误差记迭代误差若存在常数若存在常数m m（（m≥1m≥1））和和c c（（ ），），使使 则称序列则称序列 是是 m 阶收敛的阶收敛的, , 特别地特别地, ,m =1=1时称时称为线性收敛为线性收敛, ,m=2=2时称为平方收敛时称为平方收敛.1 < .1 < m < 2 < 2时时称为超线性收敛称为超线性收敛. . 四、迭代过程的收敛速度四、迭代过程的收敛速度 例8 讨论迭代公式 ① ，② 的收敛阶.定理定理4 设迭代过程设迭代过程 ，， 若若 在所求根在所求根 的邻域连续且的邻域连续且 则迭代过程则迭代过程在在 邻域是邻域是m阶收敛的阶收敛的. .证明： 则此迭代过程则此迭代过程是是m阶收敛的阶收敛的. . 迭代过程迭代过程 局部收局部收敛于敛于 ，又，又例例9 已知迭代公式已知迭代公式 收敛于收敛于 证明该迭代公式平方收敛证明该迭代公式平方收敛.证证: 迭代公式相应的迭代函数为迭代公式相应的迭代函数为将将 代入，代入，根据定理根据定理4可知，此迭代平方收敛可知，此迭代平方收敛. 牛顿迭代法的收敛性分析牛顿迭代法的收敛性分析定理定理5 设设 是方程是方程 的单根的单根, 且且f(x)在在 的某的某邻域内有连续的二阶导数邻域内有连续的二阶导数, 则牛顿法是局部收敛的则牛顿法是局部收敛的, 且至少为二阶收敛且至少为二阶收敛, 有有 证证: 牛顿迭代公式对应的迭代函数为牛顿迭代公式对应的迭代函数为 若若 是方程是方程 的单根的单根,则有则有 , 从而从而 由定理由定理3知知,牛顿迭代法在牛顿迭代法在 附近收敛附近收敛.又由定理又由定理4知知, 迭代公式至少是二阶收敛的迭代公式至少是二阶收敛的. 利用泰勒公式利用泰勒公式所以所以 法逻辑结构简单，在单根附近时，收敛速度很快；但（1）若初值选取不当， 迭代法可能失败或者收敛很慢；（2）若导数比较复杂，则每步的计算量较大；（3）若 为方程 的重根，结果如何？§4 法的改进与变形法的改进与变形012341.51.347831.325201.324721.3247201230.617.911.946807.98552§4 法的改进与变形法的改进与变形－－－－－－－－－－－－－－－－－－ 下山法下山法其中其中λ(0<λ<1)λ(0<λ<1)为下山因子为下山因子 ------------ 下山法下山法  为避免计算函数的导数为避免计算函数的导数 ，使用差商，使用差商 称为称为弦截法弦截法迭代公式迭代公式.（（单点弦截法单点弦截法））替代牛顿公式中的导数替代牛顿公式中的导数 ，便得到迭代公式，便得到迭代公式 在单根附近线性收敛在单根附近线性收敛 使用差商使用差商替替代代牛牛顿顿公公式式中中的的导导数数 ,便便得得到到迭迭代代公公式式 称为称为快速弦截法快速弦截法迭代公式迭代公式.（（双点弦截法双点弦截法））在单根附近收敛，收敛阶为在单根附近收敛，收敛阶为例例10 用用快速快速弦截法求方程弦截法求方程 在在 初初始值邻近的一个根始值邻近的一个根. 要求要求解：取解：取 , , 令令 利用快速弦截法迭代公式利用快速弦截法迭代公式 k2340.567540.567150.56714 快快速速弦弦截截法法算算法法实实现现 迭代：迭代： 改进：改进：§5 加速算法加速算法或合并写成：或合并写成：例例11 用加权法加速技术求方程用加权法加速技术求方程 在附近的一个根在附近的一个根.解：解： 因为在因为在 附近附近 取取，，建立如下迭代公式建立如下迭代公式仍取仍取 , ,逐次计算得逐次计算得( (精度为精度为 ））12340.566582 0.567132 0.567143 0.567143Aitken加速公式加速公式例例12 用埃特金方法求方程用埃特金方法求方程 在初值在初值 附近的一个根附近的一个根, 精度要求精度要求 ，， 取迭代公式取迭代公式解解 埃特金方法迭代格式为埃特金方法迭代格式为只迭代二次就得到满足精度要求的解只迭代二次就得到满足精度要求的解. 作作业习题四习题四 5、、10、、12课堂练习 1、、 6、、7、、 8（（1）、）、（（2）、）、11、、13、、14、、20、、21。