第7章1-3节迭代方程求根与加速.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第,5,章 非线性方程求根,1,1,方程求根与二分法,1,引言,（1.1）,本章主要讨论单变量非线性方程,的求根问题，这里,一类特殊的问题是多项式方程,（1.2）,的求根问题，其中系数 为实数,.,2,方程 的根,，,又称为函数 的零点，,它使,.,若 可分解为,其中 为正整数，且,当 时，称 为单根,.,若 称 为 重根，或 为 的 重零点,.,若 是 的 重零点，且 充分光滑，,则,3,例,1,解,根据有根区间定义，对 的根进行搜索计算，,先给出根 的一个范围,.,若 且,可知 在 内至少有一个实根，,这时称 为,根据连续函数性质,求方程 的有根,区间,.,结果如下：,方程 的有根区间,.,通常可通过逐次搜索法求得方程 的有根区间,.,4,由此可知方程的有根区间为,5,如果同号，说明所求的根 在,的右侧,考察有根区间,，,取中点 将它分为,两半，,2,二分法,假设中点 不是 的零点，然后进行根的搜索,.,检查 与 是否同号，,否则 必在 的左侧，,这时令,见图,7-1.,这时令,图,5-1,6,用中点 将区间 再分为两半，,图7-1,对压缩了的有根区间 又可施行同样的手续，,即,不管出现哪一种情况，新的有根区间 的长度仅,为 的一半,.,7,如此反复二分下去，即可得出一系列有根区间,其中每个区间都是前一个区间的一半，,因此 的长度,当 时趋于零,.,就是说，如果二分过程无限地继续下去，这些区间最终必收缩于一点 ，该点显然就是所求的根,.,通过根的搜索判定所求的根在 的哪一侧，,一个新的有根区间 ，其长度是 的一半,.,从而又确定,8,作为根的近似，,该序列必以根 为极限,.,由于,只要二分足够多次（即 充分大），便有,这里 为预定的精度,.,每次二分后，设取有根区间 的中点,则在二分过程中可以获得一个近似根的序列,9,例,2,在区间 内的一个实根，要求准确到小数点后第,2,位,.,解,这里 ，,取 的中点,，,将区间二等分，,由于,即 与 同号，,故所求的根 必在 右侧,.,如此反复二分下去,按误差估计式,求方程,而,这时应令 ，从而得到新的有根区间,欲使,10,只需 ，,计算结果如表,5-1.,即只要二分,6,次，便能达到预定的精度,.,11,二分法是计算机上的一种常用算法，计算步骤如下：,步骤,1,准备,计算 在有根区间 端点处的,值,步骤,2,二分,计算 在区间中点 处的值,步骤,3,判断,若 ，则 即是根，,计算过程结束，,若,，,则以 代替,，,否则以,否则检验,.,代替,.,12,此时中点 即为所求近似根,.,误差 ，,反复执行步骤,2,和步骤,3,，直到区间 长度小于允许,13,2,迭代法及其收敛性,1,不动点迭代法,将方程改写成等价的形式,若 满足,，,则 ；,求 的零点就等价于求 的不动点,.,选择一个初始近似值 ，将它代入右端，即可求得,为函数 的一个不动点,.,反之亦然，称,14,如此反复迭代计算,称为迭代函数,.,如果对任何 由上述迭代法得到的序列 有极限,则称迭代方程收敛，,故称上述方法为,不动点迭代法,.,15,方程 的求根问题在 平面上就是要确定曲,线 与直线 的交点,对于 的某个近似值,，,在曲线 上可确定,一点,，,它以 为横坐标，而纵坐标则等于,就是说，迭代过程实质上是一个逐步显示化的过程,.,过 引平行 轴的直线，设此直线交直线 于点 ，,然后过 再作平行于 轴的直线，,与曲线 的交点,上述迭代法是一种逐次逼近法，其基本思想是将隐式,方程 归结为一组显式的计算公式,.,16,则点 的横坐标为 ，,图,5-2,记作 ，,纵坐标则等于,按图,5-2,中箭头所示的路径继续做下去,.,在曲线,上得到点列,其横坐标分别为依公式,17,例,3,在 附近的根,解,求得的迭代值,如果点列 趋向于点,，,则相应的迭代值 收敛,到所求的根,据此建立迭代公式,求方程,设将方程改写成下列形式,18,各步迭代的结果见表,5-2.,这时可以认为 实际上已满足方程，即为所求的根,.,如果仅取,6,位数字，那么结果 与 完全相同,.,19,但若采用方程的另一种等价形式,建立迭代公式,仍取迭代初值 ，则有,结果会越来越大，不可能趋于某个极限,.,这种不收敛的迭代过程称作是,发散,的,.,一个发散的迭代过程，纵使进行了千百次迭代，其结果也是毫无价值的,.,20,2,不动点的存在性与迭代法的收敛性,首先考察 在 上不动点的存在唯一性,.,定理,1,设 满足以下两个条件：,1.,对任意 有,2.,存在正常数,，,使对任意 都有,则 在 上存在唯一的不动点,证明,先证不动点的存在性,.,21,因 ，,以下设 及 ，,若 或,，,则不动点为 或 ，,存在性得证,.,定义函数,显然 ，,由连续函数性质可知存在,且满足,使,即,即为 的不动点,.,22,再证,唯,一性,.,设 都是 的不动点，,引出矛盾,.,故 的不动点只能是,唯,一的,.,则,23,定理,2,设 满足定理,1,中的两个条件，,对任意 ，,由,迭代法,得到的迭代序列 收敛到,的不动点 ，并有误差估计,证明,设 是 在 上的唯一不动点，,可知 ，,因,，,故当 时序列 收敛到,.,则,由定理,1,中条件,2),得,24,再证明估计式，,由定理,1,中条件,2),有,反复递推得,于是对任意正整数 有,25,在上式令,，,注意到 即得,.,迭代过程是个极限过程,.,在用迭代法实际计算时，必须按精度要求控制迭代次数,.,根据上式，对任意正整数 有,在上式中令 知,原则上可以用上述误差估计式确定迭代次数,.,26,由此可见，只要相邻两次计算结果的偏差,足够小即可保证近似值 具有足够精度,.,对定理,1,和定理,2,中的条件,2,，,且对任意 有,则由中值定理知,对 有,表明定理中的条件,2,可用 代替,.,如果,27,例,3,中，当 时，,在区间 中，,又因 ，,而当 时，,在区间 中,故条件,2,）成立，,.,所以迭代法是收敛的,.,不满足定理条件,.,故定理,1,中条件,1,也成立,.,28,3,局部收敛性与收敛阶,上面给出了迭代序列 在区间 上的收敛性，,定理的条件有时不易检验，实际应用时通常只在不动点 的邻近考察其收敛性，即局部收敛性,.,定义,1,设 有不动点 ，,对任意 ，,通常称为全局收敛性,.,如果存在 的某个邻域,且收敛到 ，,不动点迭代法产生的序列,则称迭代法,局部收敛,.,29,证明,存在 的某个邻域,使对于任意 成立,定理,3,设 为 的不动点，,在 的某个,且 ，,邻域连续，,则,不动点,迭代法局部收敛,.,由连续函数的性质，,此外，,对于任意 ，,总有 ，,于是,依据定理,2,可以断定迭代过程 对于任意,初值 均收敛,.,这是因为,30,讨论迭代序列的收敛速度,.,例,4,用不同方法求方程 的根,解,这里,其不动点为,可改写为各种不同的等价形式,由此构造不同的迭代法：,31,取 ，,对上述,4,种迭代法，计算三步所得的结果如下表,.,32,从计算结果看到迭代法（,1,）及（,2,）均不收敛，且它们均不满足定理,3,中的局部收敛条件,.,注意,.,迭代法（,3,）和（,4,）均满足局部收敛条件，且迭代法（,4,）比（,3,）收敛快，因在迭代法（,4,）中,.,33,定义,2,则称该迭代过程是,阶收敛,的,.,特别地,时称,线性收敛,;,设迭代过程 收敛于方程,的根 ，,如果迭代误差 当 时成立下列,渐近关系式,时称,超线性收敛,;,时称,平方收敛,.,34,定理,4,对于迭代过程 ，如果 在所,求根 的邻近连续，并且,则该迭代过程在点 邻近是 阶收敛的,.,证明,由于 ，据定理,3,立即可以断定迭代,过程 具有局部收敛性,.,再将 在根 处做泰勒展开，利用定理的条件，,则有,35,注意到 ，,因此对迭代误差，,当 时有,这表明迭代过程 确实为 阶收敛,.,由上式得,上述定理说明，迭代过程的收敛速度依赖于迭代函数,的选取,.,如果当 时 ，则该迭代过程只可能线性收敛,.,36,在例,4,中，迭代法（,3,）的,，,故它只是线性,收敛,.,而迭代法（,4,）的 ，,由定理,4,知,该迭代过程为,2,阶收敛,.,而,37,3,迭代收敛的加速方法,1,埃特金加速收敛方法,设 是根 的某个近似值，,由微分中值定理，有,其中 介于 与 之间,.,假定 改变不大，近似地取某个近似值 ，,用迭代公式校正一次得,则有,38,由于,将它与上式联立，消去未知的 ，,由此推知,在计算了 及 之后，可用上式右端作为 的新近,似，记作,.,若将校正值 再校正一次，又得,有,39,一般情形是由 计算 ，,称为埃特金（,Aitken,）,加速方法,.,可以证明,它表明序列 的收敛速度比 的收敛速度快,.,记,40,2,斯蒂芬森迭代法,埃特金方法不管原序列 是怎样产生的，对 进,行加速计算，得到序列,.,如果把埃特金加速技巧与不动点迭代结合，则可得到,如下的迭代法：,称为斯蒂芬森,(,Steffensen,),迭代法,.,41,它可理解为，要求 的根 ，,已知 的近似值 及 ，其误差分别为,过 及 两点做线性插值函数,.,它与 轴交点就是 ，,即方程,的解,令,42,实际上斯蒂芬森,(,Steffensen,),迭代法是将不动点迭代法,计算两步合并成一步得到的，可将它写成另一种不动点迭代,其中,43,则 是 的不动点,.,定理 5,反之，若 为 的不动点，设 连续，,则 为 的不动点,.,若,x,*,为迭代函数 的不动点，,定理,6,44,例,5,是发散的，现用,斯蒂芬森迭代法,计算，,取,.,例,3,中已指出,下列迭代,45,至于原来已收敛的迭代法，由定理,6,可知它可达到,2,阶以上收敛,.,计算表明它是收敛的，这说明即使迭代法不收,敛，用斯蒂芬森迭代法仍可能收敛,.,46,例,6,求方程 在 中的解,.,解,由方程得等价形式 ，,由此构造迭代法,且当 时，,取对数得,由于,根据定理,2,此迭代法是收敛的,.,47,若取 迭代,16,次得,，,有六位有效数,字,.,若用,斯蒂芬森迭代法,进行加速，计算结果如下：,这里计算,2,步（相当于迭代,4,步）结果与 相同，,说明用,斯蒂芬森迭代法,迭代法的收敛速度比原迭代法快得多,.,48,