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

第二章方程求根本章主要内容：1、二分法2、简单迭代法（重点）3、牛顿迭代法（重点）4、割线法本章难点：分析迭代法的收敛性历史背景代数方程的求根问题是一个古老的数学问题。理论上，次代数方程在复数域内一定有个根(考虑重数)。早在16世纪就找到了三次、四次方程的求根公式，但直到19世纪才证明大于等于5次的一般代数方程式不能用代数公式求解，而对于超越方程就复杂的多，如果有解，其解可能是一个或几个，也可能是无穷多个。一般也不存在根的解析表达式。因此需要研究数值方法求得满足一定精度要求的根的近似解。nn本章解决一元函数方程()0fx的求根问题。否则称其为超越方程，如11100nnnnaxaxaxa31cos0xx当为多项式函数时，称此方程为代数方程，如()fx若函数可表示成()fx00()()()()0mfxxxgxgx，(2.1)则称是方程(2.1)的重根。m0x根的存在性连续函数介值定理则这样的在内唯一。[,]ababx*()yfxoxy()fx[,]ab()()0fafb若函数在上连续，且()0f()fx则至少有一个数，使得，若还单调，定理：方程f(x)=0的有根区间的确定有根区间：方程在这样的区间内有且只有一个实根。1.描图法将方程f(x)=0化为g(x)=h(x)的形式，画出g(x)和h(x)的简图，从两条曲线的交点的横坐标的位置例2.1求方程3x–1–cosx=0的有根区间。解：用描图法，将方程变形为31cosxx令g(x)=3x-1,h(x)=cosx,做出两个函数的简图确定有根区间。注：g(x)和h(x)的图形比较容易作出。131()31gxx21()coshxx由图可知，方程仅有一个实根，有根区间为1[,].32xyo2.通过研究函数性态判断有根区间例2.2求函数的有根区间。sincos40xxx解：令,并对其求导数得()sincos4fxxxx()cossin4fxxx0单调减少的。所以函数在上是()fx(,)又11()0,()0,22ff根据连续函数介值定理，方程在内有且仅有一个实根。()0fx11[,]22所以是方程的有根区间。()0fx11[,]22第一节二分法若f(x)在[a,b]上连续，且f(a)·f(b)0，o()yfxabxyx1b2a3a1a2b3b11[,]ab22[,]ab33[,]ab以此类推上至少有一实根。则f(x)在(a,b)原理：基本思想：逐步将区间分半，通过判别区间端点函数值的符号，进一步搜索有根区间，将有根区间缩小到充分小，从而求出满足精度的根的近似。32abx1122abx12abx二分法的实施步骤：（1）找出方程的有根区间。()0fx[,]ab若每次二分时所取区间中点都不是根，则上述过程将无限进（3）判断：若则是方程的根,0(),fx0x(a)若,则根属于，置：0()()0fafx0[,]ax0011[,][,]axab0011[,][,]xbab行下去。计算结束；否则：0()()0fxfb0[,]xb(b)若,则根属于，置：注：上述过程中常取做机器零，当小于此数时认为是零！（2）计算f(x)在区间中点的值；0()fx02abx如。1210误差分析：什么时候停止计算？按上述过程反复进行,可得一系列有根区间套当n→∞时,区间长度趋近于零，因此区间必将最终收缩为1122[,][,][,][,]nnabababab1()0,1,2,...,,...2nnnbabann由于每一区间都是前一区间的一半，因此区间的长度[,]nnab一点,显然就是所求的根。*x*x若取区间的中点[,]nnab1()2nnnxab作为的近似值，*x*111()()22nnnnxxbaba则，从而有下述误差估计式*11,[,]nnnxxab22lnlnlnban112nnxxba只要根据误差估计式，对于预先给定的精度，即可由此确定最大对分次数便有：nxx因此，就是满足精度要求的近似解。nx二分法算法实现问题：给定区间[a,b]，求f(x)=0在该区间上的根x.输入:a和b;容许误差TOL;最大对分次数Nmax.输出:近似根x.Step1令k=1;Step2计算x=(a+b)/2和y=f(x)Step3若kNmax，做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;停止.算法过程:解：31115102,.,ab，22ln()lnlnban3151102ln(.)lnln8.97例2.3用二分法求方程在区间上的根，310xx115[,.]误差限为0.0005，问至少需对分多少次？由题意知，最大对分次数9n所以至少需对分次。对分9次后取有根区间的中点即为满足精度要求的根。①算法简单直观，收敛性有保证;②对f(x)要求不高(只要连续即可).①无法求复根及重根；②收敛速度慢。注：用二分法求根，最好先给出f(x)草图以确定根的大概位置。或用搜索程序，将[a,b]分为若干小区间，对每一个满足f(ak)·f(bk)0的区间调用二分法程序，可找出区间[a,b]内的多个根，且不必要求f(a)·f(b)0。优点缺点第二节迭代法f(x)=0等价变换基本思想从一个初值x0出发，计算lim*nnxx1limlim()nnnnxx()xx一、简单迭代法xf(x)的根10(),xx21(),...,xx1(),...nnxx0nnx若数列收敛，*x即存在，使得()xx称为迭代函数()x*x称为的不动点()x若函数还是连续的，则()x即**()xx即方程f(x)=0的一个根。这样就找到了函数的一个不动点，()xxyy=xxyy=xxyy=xxyy=xx*x*x*x*y=φ(x)y=φ(x)y=φ(x)y=φ(x)x0p0x1p1x0p0x1p1x0p0x1p1x0p0x1p1几何意义例2.4已知方程在上有一个根.324100xx12[,]解：下面选取5种迭代格式：1、32410xxxx即32410()xxxx2、1321102xx1321102xx即3、12104xxx即12104xxx4、12104xx即12104xx5、32241038xxxxxx即()()()fxxxfx取015.x计算结果如下：12384087567324697201027510....xxxx法11234451113484013673813649613652613751713652251365230013.......xxxxxxx法412123081650299691865086..(.)xxx法3123445112912869514025413454613751713751713751713651378211365230013........xxxxxxxx法2123413733313652613652300141365230013....xxxx法5如何判定迭代法的收敛性呢？如何构造迭代函数才能使迭代法收敛？()x有如下充分条件：定理2.1（压缩映射原理）若迭代函数满足下列两个条件：()x(2)0L1使得对x[a,b]有：()1;xL(1)当x[a,b]时，()[,];xab则迭代过程对于任意初值均收敛于1()kkxx0[,]xab方程的根，且有如下误差估计式：()xx*x*11()||||1kkkAxxxxL*10()||||1kkLBxxxxL证明：先证当k时，xk收敛到x*，这是因为*||kxx*1|()()|kxx**10||......||0kkLxxLxx再证定理中的误差估计式，利用三角不等式**11||||||kkkkxxxxxx**||||kkxxLxx所以*11||||1kkkxxxxL注：该定理结论表明只要相邻两次迭代值的距离1||kkxx足够小，即可保证近似值具有足够的精度，所以可用kx1||kkxx来判断是否满足迭代精度！*11|()|||kkξxx()xx问题：给定初始近似值x0，求的解.输入:初始近似值x0;容许误差TOL;最大迭代次数Nmax.输出:近似解x或失败信息.简单迭代法的算法实现：Step1置i=1;Step2当iNmax时，作Step3-5：0()xxStep3置;否则，置i=i+1;Step4若|xx0|TOL，则输出x，停止；Step6输出迭代失败信息，停止计算。Step5置x0=x，转Step2;二、局部收敛性定义：（局部收敛性）[,]Nxx若存在的一个闭邻域，对任意x(0)x于，则称该迭代法局部收敛。{}kx1()kkxx初值，由迭代过程产生的序列均收敛0xN()1xL定理2.2关于局部收敛，有如下判定定理：x()xx()xx设为的解，在的某邻域连续，且则迭代过程局部收敛。1()kkxx三、迭代法的收敛阶1limkpkkece及常数，使1p0c的一种度量;定义：kxxkkexx设序列收敛到，，若存在实数kxpc则称序列是阶收敛的，常数称为渐近误差常数。1p01c特别地，当且时，称为线性收敛；1p当时为超线性收敛；2p当时为平方或二次收敛.注:的大小反映了迭代法收敛的快慢，是收敛速度p定理2.2设迭代法的迭代函数的高阶导数()x1()()()pxp01210()()(),(),,,,,()lpxxxlpx证明：由Taylor公式：11111()()()()()()()()()()()!!kkppppkkxxxxxxxxxxppkxx介于、之间11()()()!ppkkxxxxp110()lim()!pkpkkexep取极限得x在不动点的邻域里连续，则当p1()kkxx时，迭代过程是阶收敛的。