第一节引言二分法与迭代法课件.ppt

《第一节引言二分法与迭代法课件.ppt》由会员分享，可在线阅读，更多相关《第一节引言二分法与迭代法课件.ppt（24页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第一节引言二分法与迭第一节引言二分法与迭代法代法第1页，此课件共24页哦历史背景史背景代数方程的求根代数方程的求根问题是一个古老的数学是一个古老的数学问题。理。理论上，上，次代数方程在复数域内一定有次代数方程在复数域内一定有个根个根(考考虑重重数数)。早在。早在1616世世纪就找到了三次、四次方程的求根公式，就找到了三次、四次方程的求根公式，但直到但直到1919世世纪才才证明大于等于明大于等于5 5次的一般代数方程式不次的一般代数方程式不能用代数公式求解，而能用代数公式求解，而对于超越方程就复于超越方程就复杂的多，如的多，如果有解，其解可能是一个或几个，也可能是无果有解，其解可能是一个或几个，

2、也可能是无穷多个。多个。一般也不存在根的解析表达式。因此需要研究数一般也不存在根的解析表达式。因此需要研究数值方方法求得法求得满足一定精度要求的根的近似解。足一定精度要求的根的近似解。第2页，此课件共24页哦本章解决一元函数方程本章解决一元函数方程本章解决一元函数方程本章解决一元函数方程的求根的求根的求根的求根问题问题。否否否否则则称其称其称其称其为为超越方程超越方程超越方程超越方程，如，如，如，如当当 为多多项式函数式函数时，称此方程，称此方程为代数方程代数方程，如，如若函数 可表示成(2.1)则称 是方程(2.1)的 重根。第3页，此课件共24页哦根的存在性根的存在性连续函数介函数介值定理

3、定理则这样的在内唯一。abx*若函数 在 上连续，且则至少有一个数 ，使得 ，若 还单调，定理：定理：第4页，此课件共24页哦方程方程 f(x)=0 的有根区的有根区间的确定的确定有根区间：方程在这样的区间内有且只有一个实根。1.描描图法法将方程 f(x)=0 化为 g(x)=h(x)的形式，画出 g(x)和h(x)的简图，从两条曲线的交点的横坐标的位置例例2.1求方程 3x 1 cos x=0 的有根区间。解：解：用描图法，将方程变形为令 g(x)=3x-1,h(x)=cos x,做出两个函数的简图确定有根区间。注：注：g(x)和 h(x)的图形比较容易作出。第5页，此课件共24页哦由图可知

4、，方程仅有一个实根，有根区间为第6页，此课件共24页哦2.2.通通通通过过研究函数性研究函数性研究函数性研究函数性态态判断有根区判断有根区判断有根区判断有根区间间例例2.2 求函数 的有根区间。解：令 ,并对其求导数得单调减少的。所以函数 在 上是又根据连续函数介值定理，方程 在 内有且仅有一个实根。所以 是方程 的有根区间。第7页，此课件共24页哦第一第一节二分法二分法若 f(x)在 a,b 上连续，且 f(a)f(b)0，以以此此类推推上至少有一实根。则 f(x)在(a,b)原理：原理：基本思想：基本思想：逐步将区间分半，通过判别区间端点函数值的符号，进一步搜索有根区间，将有根区间缩小到充

5、分小，从而求出满足精度的根的近似。第8页，此课件共24页哦二分法的二分法的实施步施步骤：（1）找出方程 的有根区间 。若每次二分时所取区间中点都不是根，则上述过程将无限进（3）判断：若则 是方程的根,(a)若 ,则根属于 ，置：行下去。计算结束；否则：(b)若 ,则根属于 ，置：注：注：上述过程中 常取做机器零，当小于此数时认为是零！（2）计算 f(x)在区间中点 的值 ；如 。第9页，此课件共24页哦误差分析：什么差分析：什么时候停止候停止计算？算？按上述过程反复进行,可得一系列有根区间套当 n 时,区间长度趋近于零，因此区间必将最终收缩为由于每一区间都是前一区间的一半，因此区间 的长度一点

6、 ,显然 就是所求的根。若取区间 的中点作为 的近似值，则，从而有下述误差估计式第10页，此课件共24页哦只要根据误差估计式，对于预先给定的精度 ，即可由此确定最大对分次数便有：因此，就是满足精度要求的近似解。第11页，此课件共24页哦二分法算法二分法算法实现问题：给定区间a,b，求 f(x)=0 在该区间上的根 x.输入:a 和 b;容许误差 TOL;最大对分次数 Nmax.输出:近似根 x.Step 1 令 k=1;Step 2 计算 x=(a+b)/2 和 y=f(x)Step 3 若 k Nmax，做 Steps 4-6Step 4 若|y|TOL,停止;输出 x.Step 5 若 y

7、*f(a)0,置 b=x;否则，置 a=x;Step 6 置 k=k+1;计算 x=f(a+b)/2);转 Step 3；Step 7 输出方程的近似解 x;停止.算法过程:第12页，此课件共24页哦解解：例例2.3 用二分法求方程在区间上的根，误差限为 0.0005，问至少需对分多少次？由题意知，最大对分次数所以至少需对分 次。对分 9 次后取有根区间的中点即为满足精度要求的根。第13页，此课件共24页哦 算法简单直观，收敛性有保证;对 f(x)要求不高(只要连续即可).无法求复根及重根；收敛速度慢。注：注：注：注：用二分法求根，最好先用二分法求根，最好先给出出 f(x)草草图以确定根的大概

8、以确定根的大概位置。或用搜索程序，将位置。或用搜索程序，将a,b分分为若干小区若干小区间，对每一个每一个满足足 f(ak)f(bk)0 的区的区间调用二分法程序，可找出区用二分法程序，可找出区间a,b内的多个根，且不必要求内的多个根，且不必要求 f(a)f(b)0。优点点缺点缺点第14页，此课件共24页哦第二第二节 迭代法迭代法f(x)=0等价等价变换基基本本思思想想从一个初值x0 出发，计算一、一、简单迭代法迭代法f(x)的根若数列 收敛，即存在 ，使得称为迭代函数称为 的不动点 若函数 还是连续的，则即即方程 f(x)=0 的一个根。这样就找到了函数 的一个不动点，第15页，此课件共24页

9、哦xyy=xxyy=xxyy=xxyy=xx*x*x*x*y=(x)y=(x)y=(x)y=(x)x0p0 x1p1 x0p0 x1p1 x0p0 x1p1x0p0 x1p1几何意几何意义第16页，此课件共24页哦例例2.4 已知方程已知方程 在在 上有一个根上有一个根.解：下面选取5种迭代格式：1、即即2、即即3、即即4、即即5、即即第17页，此课件共24页哦取取计算算结果如下：果如下：法法1 1法法4 4法法3 3法法2 2法法5 5第18页，此课件共24页哦如何判定迭代法的收如何判定迭代法的收敛性呢？性呢？如何构造迭代函数 才能使迭代法收敛？有如下充分条件：定理定理 2.1（压缩映射原理

10、）映射原理）若迭代函数 满足下列两个条件：(2)0 L 1 使得对 x a,b 有：(1)当 x a,b 时，则迭代过程 对于任意初值 均收敛于方程 的根 ，且有如下误差估计式：第19页，此课件共24页哦证明：明：先证当k 时，xk 收敛到 x*，这是因为 再证定理中的误差估计式，利用三角不等式所以注：注：该定理结论表明只要相邻两次迭代值的距离足够小，即可保证近似值 具有足够的精度，所以可用来判断是否满足迭代精度！第20页，此课件共24页哦问题：给定初始近似值 x0，求 的解.输入:初始近似值 x0;容许误差 TOL;最大迭代次数 Nmax.输出:近似解 x 或失败信息.简单迭代法的算法迭代法

11、的算法实现：Step 1 置 i=1;Step 2 当 i Nmax时，作 Step 3-5：Step 3 置 ;否则，置 i=i+1;Step 4 若|x x0|TOL，则输出 x，停止；Step 6 输出迭代失败信息，停止计算。Step 5 置 x0=x，转 Step 2;第21页，此课件共24页哦二、局部收二、局部收敛性性定定义：（局部收：（局部收敛性性）若存在的一个闭邻域，对任意于 ，则称该迭代法局部收敛。初值 ，由迭代过程 产生的序列 均收敛定理定理 2.2关于局部收敛，有如下判定定理：设 为 的解，在 的某邻域连续，且则迭代过程局部收敛。第22页，此课件共24页哦三、迭代法的收三、迭代法的收敛阶及常数，使注注:（1 1）的大小反映了迭代法收敛的快慢，是收敛速度的一种度量;定义：设序列 收敛到 ，若存在实数则称序列 是 阶收敛的，常数 称为渐近误差常数。特别地，当 且 时，称为线性收敛；当 时为超线性收敛；当 时为平方或二次收敛.第23页，此课件共24页哦定理2.2设迭代法的迭代函数的高阶导数证明：由Taylor公式：取极限得在不动点 的邻域里连续，则当时，迭代过程 是 阶收敛的。第24页，此课件共24页哦