实验三求代数方程的近似根课件.ppt

《实验三求代数方程的近似根课件.ppt》由会员分享，可在线阅读，更多相关《实验三求代数方程的近似根课件.ppt（24页珍藏版）》请在三一办公上搜索。

1、1,实验三,求代数方程的近似根,感谢你的观看,2019年8月28,2,解方程（代数方程）是最常见的数学问题之一，也是众多应用领域中不可避免的问题之一,目前还没有一般的解析方法来求解非线性方程，但如果在任意给定的精度下，能够解出方程的近似解，则可以认为求解问题已基本解决，至少可以满足实际需要,本实验主要介绍一些有效的求解方程的数值方法：对分法，不动点迭代法 和 牛顿法。同时要求大家学会如何利用 Matlab 来求方程的近似解,问题背景和实验目的,代数方程近似求解,感谢你的观看,2019年8月28,3,相关概念,若 f(x)是一次多项式，称上面的方程为线性方程；否则称之为非线性方程,线性方程 与

2、非线性方程,本实验主要讨论非线性方程的数值求解,感谢你的观看,2019年8月28,4,内容提要,对分法,求解非线性方程的数值算法,牛顿迭代法,不动点迭代一般格式 松弛加速迭代法 Altken 加速迭代法,不动点迭代法,感谢你的观看,2019年8月28,5,对分法,对分法,将有根区间进行对分，判断出解在某个分段内，然后再对该段对分，依次类推，直到满足给定的精度为止,适用范围,只能计算有根区间内的 单重实根 或 奇数重实根,数学原理：介值定理,设 f(x)在 a,b 上连续，且 f(a)f(b)0，则由介值定理可得，在(a,b)内至少存在一点 使得 f()=0,基本思想,感谢你的观看,2019年8

3、月28,6,具体步骤,算法描述,设 f(x)在区间 a,b 内连续，且 f(a)f(b)0。对于给定的精度要求，若有|f(z)|，则 z 就是我们所需要的 f(x)=0 在区间 a,b 内的 近似根,例：用对分法求 x3-3x+1=0 在 0,1 中的解。,(1)令 x=(a+b)/2,计算 f(x),(2)若|f(x)|，则停止计算，输出近似解 x,(3)若 f(a)f(x)0，则令 b=x;否则令 a=x,(4)返回第一步,fuluA.m,感谢你的观看,2019年8月28,7,收敛性分析,对分法收敛性,设方程的根为 x*(ak,bk)，又，所以,对分法总是收敛的,对分法的收敛速度通常较慢

4、对分法通常用来试探实根的分布区间，或给出根的一个较为粗糙的近似,根据上面的算法，我们可以得到一个每次缩小一半的区间序列 ak,bk，在(ak,bk)中含有方程的根。,感谢你的观看,2019年8月28,8,不动点迭代,不动点迭代法,不动点迭代一般格式,感谢你的观看,2019年8月28,9,不动点迭代法,构造 f(x)=0 的一个等价方程：,(x)的不动点,f(x)=0,x=(x),f(x)的零点,不动点迭代基本思想,感谢你的观看,2019年8月28,10,若 收敛，即，假设(x)连续，则,收敛性分析,迭代法的收敛,即,注：若得到的点列发散，则迭代法失效！,例：用迭代法求 x3-3x+1=0 在

5、0,1 中的解。,fuluB.m,感谢你的观看,2019年8月28,11,迭代法收敛性判断,定理 1：如果定理 1 的条件成立，则有如下估计,定义：如果存在 x*的某个 邻域=(x*-,x*+),使得对 x0 开始的迭代 xk+1=(xk)都收敛,则称该迭代法在 x*附近局部收敛。,定理 1：设 x*=(x*)，(x)在 x*的某个 邻域 内连续，且对 x 都有|(x)|q 1,则对 x0，由迭代 xk+1=(xk)得到的点列收敛。,感谢你的观看,2019年8月28,12,定理 3：已知方程 x=(x)，且(1)对 xa,b，有(x)a,b；(2)对 xa,b，有|(x)|q 1；则对 x0a

6、,b，迭代 xk+1=(xk)得到的点列都收敛，且,迭代法收敛性判断,q 越小，迭代收敛越快,(x*)越小，迭代收敛越快,感谢你的观看,2019年8月28,13,迭代法的加速,迭代法的加速,松弛加速 Altken 加速,感谢你的观看,2019年8月28,14,松弛迭代法,设迭代 xk+1=(xk)，第 k 步和第 k+1 步得到的近似根分别为 xk 和(xk)，令,其中 wk 称为加权系数或权重。得新迭代 xk+1=(xk),感谢你的观看,2019年8月28,15,松弛迭代法,松弛法迭代公式,松弛法具有较好的加速效果 甚至有些不收敛的迭代，加速后也能收敛,缺点：每次迭代需计算导数,例：用松弛迭

7、代法求 x3-3x+1=0 在 0,1 中的解。,其中,k=0,1,2,.,fuluD.m,感谢你的观看,2019年8月28,16,Altken 迭代法,Altken 加速,用 差商 近似 微商,设 x*是方程的根，则由中值定理可得,感谢你的观看,2019年8月28,17,Altken 迭代法,k=0,1,2,.,Altken 算法中不需要计算导数 Altken 算法同样具有较好的加速效果,例：用 Altken 迭代法求 x3-3x+1=0 在 0,1 中的解。,fuluE.m,感谢你的观看,2019年8月28,18,牛顿迭代,牛顿迭代法,感谢你的观看,2019年8月28,19,牛顿迭代法,令

8、：,牛顿法基本思想,用线性方程来近似非线性方程，即采用线性化方法,设非线性方程 f(x)=0,f(x)在 x0 处的 Taylor 展开为,感谢你的观看,2019年8月28,20,牛顿法迭代公式,牛顿迭代公式,k=0,1,2,.,牛顿法的收敛速度,令,牛顿法至少二阶局部收敛,(x)即为牛顿法的迭代函数,例：用牛顿法求 x3-3x+1=0 在 0,1 中的解。,fuluF.m,感谢你的观看,2019年8月28,21,牛顿法迭代公式,牛顿法的优点,牛顿法是目前求解非线性方程(组)的主要方法,至少二阶局部收敛，收敛速度较快，特别是当迭代点充分靠近精确解时。,牛顿法的缺点,对重根收敛速度较慢（线性收敛）对初值的选取很敏感，要求初值相当接近真解,在实际计算中，可以先用其它方法获得真解的一个粗糙近似，然后再用牛顿法求解。,感谢你的观看,2019年8月28,22,Matlab 解方程函数,见讲义：Matlab 多项式运算与代数方程求解,感谢你的观看,2019年8月28,23,上机作业与要求,教材第 87 页：第 4 题,上机作业,要求写实验报告,上机要求,见课程主页 将所编写的程序分别命名为 hw341.m,hw342.m,hw343.m,hw344.m,hw345.m 参考课程主页上的附录程序,感谢你的观看,2019年8月28,24,感谢你的观看,2019年8月28,