迭代方程求根与加速.ppt

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