方程求根的迭代法0省公共课一等奖全国赛课获奖课件.pptx

重庆大学数理学院数数 值值 分分 析析第第十讲十讲主讲教师：主讲教师：谭谭 宏宏第1页第四章第四章 非线性方程求根非线性方程求根1 1教学内容：教学内容：二分法、迭代法普通原理、NEWTON迭代法 2 2重点难点：重点难点：重点：重点：牛顿迭代法及局部收敛性难点：难点：迭代法及收敛性定理3 3教学目标：教学目标：掌握迭代法普通原理、对给出方程球根问题，能利用普通迭代法或者牛顿迭代法进行数值求解第2页 在中课时，我们很熟悉一次、二次代数方程以及一些特殊高次方程或超越方程解法。这些方法都是代数解法，也是准确法。但在实际中，有许多方程问题无法求出公式解。比如超越方程 看起来很简单，却不轻易求得精确解。至于解三次、四次代数方程，尽管存在着求解公式，却不实用，而对一般五次或五次以上代数方程，根本没有求根公式。其次，在实际应用中，只要能获得具有预先给定误差限内近似值就可以了。因此，需要引进能够达到一定精度要求求方程近似值方法。第3页求方程根也叫求函数零点。需要处理几个问题：1根存在性。方程有没有根？假如有根，有几个根？根存在性。方程有没有根？假如有根，有几个根？2这些根大致在哪里？怎样把根隔离开来？这些根大致在哪里？怎样把根隔离开来？3根准确化根准确化定理定理1：设函数设函数 f(x)在区间在区间a,b上连续上连续，假如假如f(a)f(b)0，则方程则方程 f(x)=0 在在a,b内最少有一实根内最少有一实根x*。第4页4444、0 0 0 0 二二二二 分分分分 法法法法二分法基本思想是：逐步将有根区间分半，经过判别函数值符号，深入搜索有根区间，将有根区间缩小到充分小，从而求出满足给定精度根近似值。执行步骤执行步骤1计算计算f(x)在有解区间在有解区间a,b端点处值端点处值，f(a)，f(b)。2计算计算f(x)在区间中点处值在区间中点处值f(x1)。第5页3判断若判断若f(x1)=0，则则x1即是根，不然检验即是根，不然检验：（1）若若f(x1)与与f(a)异号异号，则知解位于区间则知解位于区间a,x1，b1=x1,a1=a;（2）若若f(x1)与与f(a)同号同号，则知解位于区间则知解位于区间x1,b，a1=x1,b1=b。重复执行步骤重复执行步骤2、3，便可得到一系列有根区间便可得到一系列有根区间：(a,b),(a1,b1),(ak,bk),第6页4、当当时时5、则、则即为根近似即为根近似简单简单;对对f(x)要求不高要求不高(只要连续即可只要连续即可).无法求复根及偶重根无法求复根及偶重根 收敛慢收敛慢 第7页Yx0abYx0ab第8页误差预计：因为：所以，二分法能够求得任意精度根。对于任意给定精度要求：由得：即：只要二分K次，就可得到指定精度根。第9页例：求方程在 区间1,1.5内 实根。要求准确到小数点后第2位。用二分法，这里a=1,b=1.5，且f(a)0。取区间a,b中点x0=1.25将区间二等分，因为f(x0)0f(a)f(b)=0f(a)=0打印打印b,k打印打印a,k结束结束是是是是是是否否否否否否m=(a+b)/2|a-b|0打印打印m,ka=mb=m结束结束k=K+1是是是是否否否否输入输入 k=0二分法程序流程图第12页4444、1 1 1 1 迭代过程收敛性迭代过程收敛性迭代过程收敛性迭代过程收敛性1、迭代法设计思想 迭代法是一个逐次迫近法，这种方法使用某个固定公式所谓迭代公式重复校正根近似值，使之逐步准确化，直至满足精度要求结果。迭代法求根过程分成两步，第一步先提供根某个猜测值，即所谓迭代初值，然后将迭代初值逐步加工成满足精度要求根。迭代法设计思想是：f(x)=0等价变换等价变换迭代函数第13页把根某个猜测值=()代入迭代函数得普通地：第14页 迭代过程几何表示 O x*x2 x1 x0 xy第15页例：例：求方程求方程一个根一个根解：解：等价变换等价变换迭代格式迭代格式x1=0.4771x2=0.3939x6=0.3758x7=0.3758取初始值x0=1，可逐次算得 第16页迭代法设计思想是：f(x)=0等价变换等价变换迭代函数问题：？1、怎样选取迭代函数2、怎样确保迭代收敛3、怎样加速迭代收敛第17页第18页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第19页3、压缩映像原理定理定理1：假如：假如 (x)满足以下条件满足以下条件（1 1）当）当x a,b时，时，(x)a,b（2 2）当任意）当任意x a,b，存在，存在0 L 1，使，使 则方程则方程x=(x)在在a,b上有唯一根上有唯一根x*,且对任意初值且对任意初值 x0 a,b时，迭代序列时，迭代序列xk+1=(xk)(k=0,1,)收敛于收敛于x*。(6)且有以下误差预计且有以下误差预计(7)(8)第20页证：其中 在x*与xk之间，设x*是方程根，即x*=(x*)，由微分中值定理由条件（2）得因为0 L 1，由知第21页所以即 xk+1=(xk)收敛因为：所以：而：所以：第22页 据（7）式，只要 充分小，就能够确保足够小。所以可用条件 来控制迭代过程结束。第23页例：求方程 在0,0.5内根，准确到10-5。解：将方程变形因为，在0,0.5内 为增函数，所以满足收敛条件，取x0=0.25，算得x1=(0.25)=0.3385416 x2=(x1)=0.3462668x3=(x2)=0.3471725 x4=(x3)=0.3472814x5=(x4)=0.3472945 x6=(x5)=0.3472961x7=(x6)=0.3472963因为取近似根为x*=0.347296第24页第25页4、迭代过程局部收敛性在实际应用迭代法时，通常首先在根 邻近考查。称一个迭代过程在根 邻近收敛，假如存在邻域 ，使迭代过程对于任意初值 均收敛，这种在根邻近所含有收敛性被称为局部收敛局部收敛性性。定理定理2 设 在 根 邻近有连续导数，且 成立 则迭代过程 在 邻近含有局部收 敛性。第26页5、迭代过程收敛速度 设由某方法确定序列设由某方法确定序列xk收敛于方程根收敛于方程根x*，假如存在正实数假如存在正实数p，使得，使得定义：定义：（C C为非零常数）为非零常数）则称序列则称序列xk收敛于收敛于x*收敛速度是收敛速度是p阶，或称该方法阶，或称该方法含有含有p 阶敛速。当阶敛速。当p=1时，称该方法为线性（一次）收敛；时，称该方法为线性（一次）收敛；当当p=2时，称方法为平方（二次）收敛；当时，称方法为平方（二次）收敛；当1 p 2时，时，称方法为超线性收敛。称方法为超线性收敛。第27页对于在根 邻近收敛迭代公式，因为式中 介于 与 之间，故有：所以：所以，若 则该迭代过程为线性收敛。第28页若将在 处泰勒展开有：所以，故即当迭代过程为平方收敛。第29页4444、2 2 2 2 迭代过程加速迭代过程加速迭代过程加速迭代过程加速 设 是根 某个近似值，用迭代公式校正一次得假设 在所考查范围内改变不大，其预计值为L，则有据此可导出以下加速公式：其一步分为两个步骤：迭代:改进:(10)第30页埃特金算法埃特金算法 前面加速方案有个缺点是其中含有导数 相关信息而不便于实际应用。设将迭代值 再迭代一次，可得据此结构出不含导数信息加速公式：迭代:迭代:改进:这一加速方法称为埃特金算法埃特金算法。第31页第32页