二分法的具体计算过程.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)ln2≤lnε则 注意到 , ,有 如精度要求提高,则上式的关键项ln(1/ε), 由于210=1024,如要求误差缩小0.1000,则要求多计算10次。 二、计算流程  根据精度要求可以事先计算出需执行步骤数n。 初态:。 对于n=1,2,...n做 计算 如果,输出 如果,则 否则 输出 其几何意义如图: 例: 求方程x3-2x-5=0的近似解,精确到0.001。 解: f(x)= x3-2x-5, ε=0.001,因为f(2)=-10,f(3)=160,故 方程在区间[2,3]上有根。又 ,取n=9,将计算结果列表如下:  所以x*≈x9=2.0947265,而精确值为 2.0945515...,误差为0  三、二分法的特点 二分法的优点是计算简便,对函数f(x)的要求不高,只要求连续即可,且误差估计容易。二分法的缺点是收敛速度很慢,每计算一步,误差减小一半。§2.迭代法 一.简单迭代法 设方程在区间上有唯一的实根,将方程变形为与其同解方程: 要求函数在区间上满足: 则可以在区间上任取一点作为迭代法的初始值,建立迭代关系(递推关系式): , 从而得到一个数列,如果当时,这个数列收敛到,即,则, 则满足方程,由于方程和是同解方程,所以满足方程。在实际计算中,取足够大,则有,我们把作为原方程的近似解。 计算流程: 选取初值 对 做 如果,跳出循环 否则,置,继续循环 输出 例1:用迭代法求方程的根,精确到0.001。 解:设,,,在区间内有根。 将方程变形为,这儿, ,在内,所以迭代是收敛的。 取,则 ， ,迭代结束。 。 几何意义: 取作y轴平行线,交于,作x轴下平行线交于,即;再作y轴平行线交于,再作y轴的平行线交于 ,即;再作y轴的平行线交于,…,一直下去。越来越接近于,就是与的交点的x坐标,即。 二.收敛定理: 定理1:在迭代方程中设满足: (1)当时,;(即在内有界。) (2)存在正数,使得对任意,有,则 (1)方程在内有唯一解,且(2)对任意初值,迭代格式得到的数列,收敛到方程的解,且满足误差估计。 证明: (1)存在性: 因,, 由连续函数的性质,存在, 使。 唯一性:设,均是方程的根则 , 又,,只有,。 (2)迭代的收敛性: 因, 反复用此式 ,即， 迭代收敛。 误差估计: ，而 同理 从而得: 要使,只要,两边取对数 ,即 说明: (1)要求,不能放松为; (2)一个方程变形为有许多形式可以变换,有的可能不收敛,有的可能收敛,且的越小,收敛的越快。 例如:解方程。 如构造,,, 在有限区间为(2,3),; 如取,则 是发散数列。 如取,则 如构造, ,是收敛的。 取, 精度已达小数点第四位。精度已达小数点第五位,收敛速度很快,因很小,故收敛很快。 如将变形为: 在有根区间内,因而也是不收敛的。 取, 是不收敛的。 三、加速收敛（Aitken方法） 设是的某个预测值,适用一次迭代得到校正值,用微分中值定理,如果变化不大,记其近似值为则: ,解得: 利用上式总认为上式比更接近于。 ,在的基础上再调整一个量,使其更接近,称此为改进值,如每步均如此计算,则得公式校正值:; 改进值:。 其中是的值实际计算比较困难,因而可以通过两次校正来回避掉求的困难,,是第一次校正,是第二次校正,由中值定理: 两式相除约去得:,从而解得: 得到改进公式如下: 第一次校正值: 第二次校正值: 改进值: 此方法称为艾特肯法(Aitken)。 这样每一次迭代可