二分法的具体计算过程.doc

1. 二分法一、二分法的具体计算过程第一步,取区间中点(a+b)/2,计算区间中点的函数值f(a+b)/2), 如果,则在区间上,f(x)在两个端点的函数值异号,于是原方程在区间内有根,记,下一步在区间内继续进行。第二步, 求f(x)在区间a1,b1的中点的函数值,并检验其正负号, 如果, 则原方程在区间内有根,并记; 如果,则在区间上,原方程有根,记。于是,我们得到,其区间宽度为: 象这样,继续进行第三步、第四步、. , 区间宽度每次缩小一半,得到一个区间序列:此时,f(an). f(bn)0,即原方程在区间an,bn内有根,区间宽度为: 当n足够大时,如果此时的区间宽度已达到精度要求,则以区间的中点作为x*的近似值,即;此时,近似值的误差小于该区间宽度的一半,即。如果精度要求,则要求 两边取自然对数,得: ln(b-a)-(n+1)ln2ln则 注意到 , ,有如精度要求提高,则上式的关键项ln(1/), 由于210=1024,如要求误差缩小0.1000,则要求多计算10次。二、计算流程 根据精度要求可以事先计算出需执行步骤数n。 初态:。 对于n=1,2,.n做 计算 如果,输出 如果,则 否则 输出YXabb1=(a+b)/2b2=(a+b1)/2b3=(a+b2)/2a1=(a+b2)/2x*其几何意义如图:例: 求方程x3-2x-5=0的近似解,精确到0.001。解: f(x)= x3-2x-5, =0.001,因为f(2)=-10,故方程在区间2,3上有根。又 ,取n=9,将计算结果列表如下: 所以x*x9=2.0947265,而精确值为 2.0945515.,误差为0.00017506。 三、二分法的特点 二分法的优点是计算简便,对函数f(x)的要求不高,只要求连续即可,且误差估计容易。二分法的缺点是收敛速度很慢,每计算一步,误差减小一半。2.迭代法一.简单迭代法设方程在区间上有唯一的实根,将方程变形为与其同解方程:要求函数在区间上满足:则可以在区间上任取一点作为迭代法的初始值,建立迭代关系(递推关系式): ,从而得到一个数列,如果当时,这个数列收敛到,即,则,则满足方程,由于方程和是同解方程,所以满足方程。在实际计算中,取足够大,则有,我们把作为原方程的近似解。计算流程: 选取初值 对 做 如果,跳出循环 否则,置,继续循环 输出例1:用迭代法求方程的根,精确到0.001。解:设,在区间内有根。将方程变形为,这儿,在内,所以迭代是收敛的。取,则，,迭代结束。几何意义:p2p3p1p0xx3x*x1x0x2y取作y轴平行线,交于,作x轴下平行线交于,即;再作y轴平行线交于,再作y轴的平行线交于,即;再作y轴的平行线交于,一直下去。越来越接近于,就是与的交点的x坐标,即。yxyx二.收敛定理:定理1:在迭代方程中设满足:(1)当时,;(即在内有界。)(2)存在正数,使得对任意,有,则(1)方程在内有唯一解,且(2)对任意初值,迭代格式得到的数列,收敛到方程的解,且满足误差估计。证明:(1)存在性:因,由连续函数的性质,存在,使。唯一性:设,均是方程的根则,又,只有,。(2)迭代的收敛性:因,反复用此式,即，迭代收敛。误差估计:，而同理从而得:要使,只要,两边取对数,即说明:(1)要求,不能放松为;(2)一个方程变形为有许多形式可以变换,有的可能不收敛,有的可能收敛,且的越小,收敛的越快。例如:解方程。如构造,在有限区间为(2,3),;如取,则是发散数列。如取,则如构造,是收敛的。取, 精度已达小数点第四位。精度已达小数点第五位,收敛速度很快,因很小,故收敛很快。如将变形为:在有根区间内,因而也是不收敛的。取,是不收敛的。三、加速收敛（Aitken方法） 设是的某个预测值,适用一次迭代得到校正值,用微分中值定理,如果变化不大,记其近似值为则:,解得:利用上式总认为上式比更接近于。,在的基础上再调整一个量,使其更接近,称此为改进值,如每步均如此计算,则得公式校正值:;改进值:。其中是的值实际计算比较困难,因而可以通过两次校正来回避掉求的困难,是第一次校正,是第二次校正,由中值定理:两式相除约去得:,从而解得:得到改进公式如下:第一次校正值:第二次校正值: 改进值:此方法称为艾特肯法(Aitken)。这样每一次迭代可以省计算一次的值。例2:用快速迭代法来解方程。取初始值,对见书上表格,计算到已达到,取，3、牛顿法一.牛顿法的构造 在求解方程时,设可导,且在附近,则在附近一次泰勒展式如果是的解,则代入上式解得: 将左边作的一次近似,反复运用以上公式,得到迭代公式:得数列,如收敛,则。二.几何意义: 是曲线,其一次泰勒展开式,是过曲线上的切线，而满足,即是该切线与x轴的交点。而是曲线与x轴的交点，因而每次近似均是过的切线与x轴的交点来近似逼近。xy三.牛顿法计算步骤： 选取初值 对于 计算和 判断 如果是转出循环 如果不是继续循环 输出四.数值例子:例1:用牛顿法解方程,精确到0.01。解:,选取初值此时迭代结束。结果基本相同。用两分法求解方程达到0.00065的精度需要10次达到要求。用一般迭代法构造例1、 七次迭代可达到以上精度,而牛顿迭代只需三次。例2、计算的近似值。，即求的根，f (x)=2x 这是求平方根的简单很有效的迭代算法，此式就是从牛顿迭代中推出来的。例：求初值取x0=20精确值为14.142136，收敛速度很快。五、多重根的情况 如果x*是f(x)=0的m重根，将迭代公式修改为：而实际情况m往往是不知道的，而如x*是f(x)的m重根，则x*是f (x)的m-1重根，则x*是的单根了，则对k(x)可以使用牛顿迭代的方法来求解，即。六、收敛性问题 牛顿法是一种迭代法，令，则牛顿迭代就是 而此时，因此如果f(x)在x*的某个邻域内f (x)0,且f (x)存在,则当时，牛顿迭代收敛，且至少有二阶收敛性。 如迭代序列，记对于正实数，和常数c满足，则称该迭代是p阶收敛性，而牛顿迭代是至少2阶收敛，即常数，如果en约是0.01，则下一步误差en+1约是，收敛速度是很快的。 我们首先要使f(x)的分离区间a,b尽可能小，并要求f (x)和f (x)不变号，即要求f(x)保持严格单调，且凹凸性不变。以下四个图说明此问题：x3 x2 x1 XYx* y=f(x) x0f( x0)0 y=f(x)x*x2 x1 x0 YX(1)、在a,b上均有，f (x)0, f (x)0，f (x)0,意味着曲线严格单调增，f (x) 0曲线上凹。(2)、在a,b上均有f (x)0, f (x)0这说明曲线y=f(x)是严格单调增，而向上凸的，XYx0 x1 x2 x* y=f(x)f( x0)0x0(3)、在a,b上均有f (x)0，此时曲线y=f(x)严格单调减，曲线向上凹，x* x0 y=f(x)YXXYx0 x1 x2 x* y=f(x)f( x0)0f( x0)0 y=f(x)YX(4)、在a,b上均有f (x)0, f (x)0，此时曲线y=f(x)严格单调减，曲线向上凸，f( x0)0的x0，可以用作初始值，而实际上只要选取x0，使之得到的x1仍在a,b内的初始值内可以。定理2、设函数f(x)在a,b上满足： (1)、f(a) f(b)0；则牛顿迭代序列收敛到方程f(x)=0在a,b内的唯一的根x*。证明：由条件(1)可知方程f(x)在a,b内至少有一个根，由条件(3)知f (x)在a,b内连续，再由条件(2)知f (x)在a,b内保持同号，因而f(x)在a,b内是严格单调和，因而方程f(x)=0的根在a,b内是唯一的。因而对以上四种情况，我们讨论一种情况，即f (x)0, f (x)0，即f(x)严格单调增，且是向上凹的，因而，此时f(b)0。当xx*时，f(x)0。因为选取f(x0) f (x)0，f(x0)0x0x*下面用归纳法证明每次迭代x* xn xn-1因，由，曲线向上凹，任一点的曲线的切线总在曲线的上方。因而切线在曲线的下方，因而而。g(x)与x轴的交点xn在x*和xn-1之间，x* xn xn-1， 因而数列，是单调下降且有下界的数列，因而，在迭代格式中，令得：，即。x*x0YX 说明： (1)第(4)个条件未必初始值必须选取,即选取(在第一种情况下),由以上四种情况的图中，只要选取x0，使由此得到的x0仍然满足定理的条件的a,b区间内，自然x1会满足的。 (2)用牛顿法解方程，初始值x0的选取很重要，因有时定的条件不容易验证，初始值x0的选取不同，可能收敛，可能不收敛。由于非线性方程往往有许多根，初始值x0的选取不同可能会由敛到不同的根。下图是不收敛的例子：x*x0YXx0x2x4x1x3x5 y=f(x) 注意图中不是同号的。例：求方程的根，要求0.0005。解：f(x)=2x-3x,f(3)=-10,在3,4 内 故选取初始值x0=4，迭代格式为 此时此时4、弦截法一、弦截法的思想：Xx0x*x1 x2Y y=f(x) 设方程f(x)=0在区间x0, x1内有唯一实根，其解就是曲线与x轴的交点，而弦截法是选取曲线上两点，用过两点的直线（弦）与x轴的交点作为x*的一次近似值。 不妨假定f(x0)0, f(x1)0P0P2P1(3)、如，再与相邻作弦与x轴 交点为；如此反复计算。Xx0x*x1 x2 x3Y f(x)0P0P2P1二、弦截法的计算流程： 假定f(x)在 a,b上连续, (异号)，不妨设，置对于n=1,2,. 并计算如或转出循环；如，；否则置继续循环输出三、四种情况的讨论： 第一种情况：在a,b上恒有，即f(x)单调增加，且向上凹，取Xx0x*x1 x2 x3YP0P2P1P3 可以证明,数列xn是单调上有界,以x*为上界,因而迭代公式是: xn+1= xn( xn- x0),即曲线的弦总是以为一端。第二种情况:, f(x)单调减，向上凸，同样置，数列xn是单调递增，以x*为上界,始终是弦的一端。Xx0x*x1 x2 x3YP0P2P1P3第三种情况：置，相应得到的数列均为，数列是单调递减且以x*为下界，始终是弦的一端。x3 x2 x1P3P2P1P0x0x*YX第四种情况：置，相应得到的数列xn具有性质：，数列xn是单调递减，且以x*为下界，始终是弦的一端。P1P0Yx0 x1 x2x1Xx*P3P2总之，在上不变号的情况下： (1)、如（第一、二种情况）置； (2)、如（第三、四种情况）置；计算公式均为：始终是弦的一端。（而不必讨论了）。,取,精度达,精度达,取,精度达,精度达牛顿迭代法:1)迭代公式:2)初始值的选取:内满足。(按书上说法)要使选取使得:。例如:在上恒(向上凹),如,选;如在内向上凸,意味。,选。(而实际上):可任选,由一次迭代计算出的,自然会满足(在满足定理前三条)唯一要求是。3)收敛条件:选取使在在有根。不为零,不变号。4)举例:(自我练习3)用牛顿法求方程在上的近似根。解:,迭代公式为:在内,故选取,达到精度要求。四.弦