计算方法方程求根省公共课一等奖全国赛课获奖课件.pptx

第二章第二章 方程求根方程求根/*Solutions of Equations*/本章主要内容：本章主要内容：1 1、二分法、二分法2 2、不动点迭代结构及其收敛性判定、不动点迭代结构及其收敛性判定3 3、Newton迭代迭代4 4、割线法、割线法第1页历史背景历史背景 代数方程求根问题是一个古老数学问题。理论上，代数方程求根问题是一个古老数学问题。理论上，次代次代数方程在复数域内一定有数方程在复数域内一定有 个根个根(考虑重数考虑重数)。早在。早在1616世纪就找世纪就找到了三次、四次方程求根公式，但直到到了三次、四次方程求根公式，但直到1919世纪才证实大于等于世纪才证实大于等于5 5次普通代数方程式不能用代数公式求解，而对于超越方程就次普通代数方程式不能用代数公式求解，而对于超越方程就复杂多，假如有解，其解可能是一个或几个，也可能是无穷多复杂多，假如有解，其解可能是一个或几个，也可能是无穷多个。普通也不存在根解析表示式。所以需要研究数值方法求得个。普通也不存在根解析表示式。所以需要研究数值方法求得满足一定精度要求根近似解。满足一定精度要求根近似解。1第2页求方程求方程 几何意义几何意义 假如函数假如函数 在在 上连续，且上连续，且则最少有一个数则最少有一个数 使得使得 ，若同时，若同时 一阶导一阶导数数 在在 内存在且保持定号，即内存在且保持定号，即 (或或 )则这么则这么 在在 内唯一。内唯一。abx*基本定理基本定理:第3页2 2 二分法二分法 /*Bisection Method*/原理：原理：若若 f Ca,b，且，且 f(a)f(b)0，则，则 f 在在(a,b)上最少有一实根。上最少有一实根。基本思想：基本思想：逐步将区间分半，经过判别区间端点函数值符号，深逐步将区间分半，经过判别区间端点函数值符号，深入搜索有根区间，将有根区间缩小到充分小，从而求入搜索有根区间，将有根区间缩小到充分小，从而求 出满足给定精度根出满足给定精度根 近似值。近似值。以这类推以这类推第4页终止法则？终止法则？abx1x2ab何时终止何时终止?或或不能确保不能确保 x 精度精度x*2xx*第5页 二分法算法二分法算法给定区间给定区间a,b，求，求f(x)=0 在该区间上根在该区间上根x.输入输入:a和和b;允许误差允许误差 TOL;最大对分次数最大对分次数 Nmax.输出输出:近似根近似根 x.Step 1 Set k=1;Step 2 Compute x=f(a+b)/2);Step 3 While(k Nmax)do steps 4-6 Step 4 If|b-a|TOL,STOP;Output the solution x.Step 5 If x*f(a)0,Set b=x;Else Set a=x;Step 6 Set k=k+1;Compute x=f(ab)/2);Go To Step 3;Step 7 Output the solution of equation:x;STOP.第6页3、由二分法过程可知：由二分法过程可知：4、对分次数计算公式：对分次数计算公式：1、2、令令误差误差 分析分析第7页解解：例例1 1：用二分法求方程用二分法求方程 在区间在区间 上根，上根，误差限为误差限为 ，问最少需对分多少次？，问最少需对分多少次？注：计算过程见教材注：计算过程见教材19页表页表2-1。第8页简单简单;对对f(x)要求不高要求不高(只要连续即可只要连续即可).无法求复根及无法求复根及偶重根偶重根收敛慢收敛慢 注：注：注：注：用二分法求根，最好先给出用二分法求根，最好先给出 f(x)草图以确定根大约草图以确定根大约位置。或用搜索程序，将位置。或用搜索程序，将a,b分为若干小区间，对每一分为若干小区间，对每一个满足个满足 f(ak)f(bk)0 区间调用二分法程序，可找出区区间调用二分法程序，可找出区间间a,b内多个根，且无须要求内多个根，且无须要求 f(a)f(b)0。优点优点缺点缺点课内练习：课内练习：教材教材34页，第页，第1题。题。第9页3 迭代法迭代法/*Iteration Method*/f(x)=0 x=g(x)（迭代函数）（迭代函数）等价变换等价变换思思绪绪从一个初值从一个初值 x0 出发，计算出发，计算 x1=gx0),x2=g(x1),xk+1=g(xk),若若 收敛，即存在收敛，即存在 x*使使得得 ，且，且 g 连续，则由连续，则由 可可知知 x*=g(x*)，即，即x*是是 g 不动点，也就是不动点，也就是f 根。根。看起来很简单，令人看起来很简单，令人有点不相信，那么问有点不相信，那么问题是什么呢？题是什么呢？怎样判定这种方法怎样判定这种方法是收敛呢？是收敛呢？f(x)根根g(x)不动点不动点一、不动点迭代一、不动点迭代 /*Fixed-Point Iteration*/第10页xyy=xxyy=xxyy=xxyy=xx*x*x*x*y=g(x)y=g(x)y=g(x)y=g(x)x0p0 x1p1 x0p0 x1p1 x0p0 x1p1x0p0 x1p1几何意义几何意义第11页 例例2 试用迭代法求方程试用迭代法求方程 在区间在区间(1，2)内实根。内实根。解：由解：由 建立迭代关系建立迭代关系 k=10,1,2,3.计算结果以下计算结果以下:准确到准确到5位小数：位小数：第12页但假如由但假如由 建立迭代公式建立迭代公式:仍取仍取 ，则有，则有显然结果越来越大，显然结果越来越大，是发散序列是发散序列.第13页例例3：已知方程已知方程 在在 上有一个根（正根）上有一个根（正根）下面选取下面选取5 5种迭代格式：种迭代格式：1 1、即即2 2、即即3 3、即即4 4、即即5 5即即第14页取取计算结果以下：计算结果以下：法法1 1法法4 4法法3 3法法2 2法法5 5第15页考虑方程考虑方程 x=g(x),若若(I)当当 x a,b 时，时，g(x)a,b；(II)0 L 1 使得使得 对对 x a,b 成成立。立。则任取则任取 x0 a,b，由，由 xk+1=g(xk)得到序列得到序列 收敛收敛于于g(x)在在a,b上唯一不动点。而且有误差预计式：上唯一不动点。而且有误差预计式：(k=1,2,)定理定理1：第16页证实：证实：g(x)在在a,b上存在不动点？上存在不动点？令令有根有根 不动点唯一？不动点唯一？反证：若不然，设还有反证：若不然，设还有 ，则则在在和和之间。之间。而而 当当k 时，时，xk 收敛到收敛到 x*？第17页L 越越 收敛越快收敛越快可用可用 来来控制收敛精度控制收敛精度 小小第18页 算法算法:不动点迭代不动点迭代给定初始近似值给定初始近似值 x0，求，求x=g(x)解解.输入输入:初始近似值初始近似值 x0;允许误差允许误差 TOL;最大迭代次数最大迭代次数 Nmax.输出输出:近似解近似解 x 或失败信息或失败信息.Step 1 Set i=1;Step 2 While(i Nmax)do steps 3-6Step 3 Set x=g(x0);/*计算计算 xi*/Step 4 If|x x0|TOL then Output(x);/*成功成功*/STOP;Step 5 Set i+;Step 6 Set x0=x;/*更新更新 x0*/Step 7 Output(The method failed after Nmax iterations);/*不成功不成功*/STOP.当当 x 很大时，此很大时，此处可改为处可改为第19页例例4 证实函数 在区间1，2上满足迭代收敛条件。证实：第20页若取迭代函数 ，不满足压缩映像原理，故不能必定 收敛到方程根。第21页例例5 5：已知方程已知方程 在在1.51.5附近有根，把方程写成三附近有根，把方程写成三种不一样等价形式种不一样等价形式(1)(1)对应迭代格式对应迭代格式 ；(2)(2)对应迭代格式对应迭代格式 ；(3)(3)对应对应迭代格式迭代格式 ;判断迭代格式在判断迭代格式在 收敛性，选收敛性，选一个一个收敛格式收敛格式计算，准确到小数点后计算，准确到小数点后第二位第二位。解：解：（1 1），迭代格式收敛；，迭代格式收敛；（2 2），迭代格式收敛；，迭代格式收敛；（3 3），迭代格式发散。，迭代格式发散。选择选择(2)(2)计算计算 0 1 2 3 40 1 2 3 4 1.5 1.481 1.473 1.469 1.467 1.5 1.481 1.473 1.469 1.467第22页