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

第二章方程求根

本章主要内容：1、二分法2、简单迭代法（重点）3、牛顿迭代法（重点）4、割线法本章难点：分析迭代法的收敛性第二章方程求根本章主要内容：1、二分法2、简单迭代法（1历史背景

代数方程的求根问题是一个古老的数学问题。理论上，次代数方程在复数域内一定有个根(考虑重数)。早在16世纪就找到了三次、四次方程的求根公式，但直到19世纪才证明大于等于5次的一般代数方程式不能用代数公式求解，而对于超越方程就复杂的多，如果有解，其解可能是一个或几个，也可能是无穷多个。一般也不存在根的解析表达式。因此需要研究数值方法求得满足一定精度要求的根的近似解。

历史背景代数方程的求根问题是一个古老的数学问题。理论2本章解决一元函数方程的求根问题。否则称其为超越方程，如当为多项式函数时，称此方程为代数方程，如若函数可表示成(2.1)则称是方程(2.1)的重根。本章解决一元函数方程的求根问题。否则称其为超越方程，如当3根的存在性连续函数介值定理则这样的在内唯一。abx*若函数在上连续，且则至少有一个数，使得，若还单调，定理：根的存在性连续函数介值定理则这样的在内唯一。4方程f(x)=0的有根区间的确定有根区间：方程在这样的区间内有且只有一个实根。1.描图法将方程f(x)=0化为g(x)

=h(x)的形式，画出g(x)和h(x)的简图，从两条曲线的交点的横坐标的位置例2.1求方程3x–1–cosx=0的有根区间。解：用描图法，将方程变形为令g(x)=3x-1,h(x)=cosx,做出两个函数的简图确定有根区间。注：g(x)和h(x)的图形比较容易作出。方程f(x)=0的有根区间的确定有根区间：方程在这5由图可知，方程仅有一个实根，有根区间为由图可知，方程仅有一个实根，有根区间为62.通过研究函数性态判断有根区间例2.2求函数的有根区间。解：令,并对其求导数得单调减少的。所以函数在上是又根据连续函数介值定理，方程在内有且仅有一个实根。所以是方程的有根区间。2.通过研究函数性态判断有根区间例2.2求函数7第一节二分法若f

(x)在[a,b]上连续，且f(a)·f(b)<0，以此类推上至少有一实根。则f(x)在(a,b)原理：基本思想：逐步将区间分半，通过判别区间端点函数值的符号，进一步搜索有根区间，将有根区间缩小到充分小，从而求出满足精度的根的近似。第一节二分法若f(x)在[a,b]上连续，且8二分法的实施步骤：（1）找出方程的有根区间。若每次二分时所取区间中点都不是根，则上述过程将无限进（3）判断：若则

是方程的根,(a)若

,则根属于，置：行下去。计算结束；否则：(b)若

,则根属于，置：注：上述过程中常取做机器零，当小于此数时认为是零！（2）计算f(x)在区间中点的值；如。二分法的实施步骤：（1）找出方程9误差分析：什么时候停止计算？按上述过程反复进行,可得一系列有根区间套当n→∞

时,区间长度趋近于零，因此区间必将最终收缩为由于每一区间都是前一区间的一半，因此区间的长度一点

,

显然

就是所求的根。若取区间

的中点作为

的近似值，则，从而有下述误差估计式误差分析：什么时候停止计算？按上述过程反复进行,可得一系列10只要根据误差估计式，对于预先给定的精度，即可由此确定最大对分次数便有：因此，就是满足精度要求的近似解。只要根据误差估计式，对于预先给定的精度，即可由此确定11二分法算法实现问题：给定区间[a,b]，求f(x)=0在该区间上的根x.输入:

a和b;容许误差TOL;最大对分次数Nmax.输出:

近似根x.Step1

令k=1;Step2计算x=(a+b)/2和y=f(x)Step3若kNmax，做Steps4-6Step4若

|y|

<TOL

,停止;输出

x.Step5

若y*f(a)<0

,置b=x;否则，置a=x;Step6置k=k+1;计算x=f((a+b)/2);转Step3；Step7

输出方程的近似解

x;停止.算法过程:

二分法算法实现问题：给定区间[a,b]，求f(x)=12解：例2.3用二分法求方程在区间上的根，误差限为0.0005，问至少需对分多少次？由题意知，最大对分次数所以至少需对分次。对分9次后取有根区间的中点即为满足精度要求的根。解：例2.3用二分法求方程在区间13①算法简单直观，收敛性有保证;

②

对f(x)

要求不高(只要连续即可).①无法求复根及重根；②收敛速度慢。注：用二分法求根，最好先给出f(x)

草图以确定根的大概位置。或用搜索程序，将[a,b]分为若干小区间，对每一个满足f(ak)·f(bk)<0的区间调用二分法程序，可找出区间[a,b]内的多个根，且不必要求f(a)·f(b)<0。优点缺点①算法简单直观，收敛性有保证;①无法求复根14第二节

迭代法f(x)=0等价变换基本思想从一个初值x0

出发，计算一、简单迭代法f(x)的根若数列收敛，即存在，使得称为迭代函数称为的不动点

若函数还是连续的，则即即方程f(x)=0的一个根。这样就找到了函数的一个不动点，第二节迭代法f(x)=0等价变换基本思想从一个初值15xyy=xxyy=xxyy=xxyy=xx*x*x*x*y=φ(x)y=φ(x)y=φ(x)y=φ(x)x0p0x1p1x0p0x1p1x0p0x1p1x0p0x1p1几何意义xyy=xxyy=xxyy=xxyy=xx*16例2.4已知方程在上有一个根.解：下面选取5种迭代格式：1、即2、即3、即4、即5、即例2.4已知方程17取计算结果如下：法1法4法3法2法5取计算结果如下：法1法4法3法2法518如何判定迭代法的收敛性呢？如何构造迭代函数才能使迭代法收敛？有如下充分条件：定理2.1（压缩映射原理）若迭代函数满足下列两个条件：(2)0L<1使得对x[a,b]有：(1)当x[a,b]时，则迭代过程对于任意初值均收敛于方程的根，且有如下误差估计式：如何判定迭代法的收敛性呢？如何构造迭代函数才19证明：先证当k

时，

xk收敛到x*，这是因为再证定理中的误差估计式，利用三角不等式所以注：该定理结论表明只要相邻两次迭代值的距离足够小，即可保证近似值具有足够的精度，所以可用来判断是否满足迭代精度！证明：先证当k时，xk收敛到x*，这是因为20问题：给定初始近似值x0，求的解.输入:初始近似值

x0;容许误差TOL;最大迭代次数Nmax.输出:近似解x或失败信息.简单迭代法的算法实现：Step1置i=1;Step2当iNmax时，作Step3-5：Step3置;否则，置i=i+1;Step4若|xx0|<TOL，则输出x，停止；Step6输出迭代失败信息，停止计算。Step5置x0=x，转Step2;问题：给定初始近似值x0，求21二、局部收敛性定义：（局部收敛性）若存在的一个闭邻域，对任意于，则称该迭代法局部收敛。初值，由迭代过程产生的序列均收敛定理2.2关于局部收敛，有如下判定定理：设为的解，在的某邻域连续，且则迭代过程局部收敛。二、局部收敛性定义：（局部收敛性）若存在的一个闭邻域22三、迭代法的收敛阶及常数，使的一种度量;定义：设序列收敛到，，若存在实数则称序列是阶收敛的，常数称为渐近误差常数。特别地，当且