迭代方程求根与加速.ppt

1、1,第5章 非线性方程求根,2,1 方程求根与二分法,1 引言,（1.1）,本章主要讨论单变量非线性方程,的求根问题，这里,一类特殊的问题是多项式方程,（1.2）,的求根问题，其中系数 为实数.,3,方程 的根 ，又称为函数 的零点，,它使 .,若 可分解为,其中 为正整数，且,当 时，称 为单根.,若 称 为 重根，或 为 的 重零点.,若 是 的 重零点，且 充分光滑，,则,4,例1,解,根据有根区间定义，对 的根进行搜索计算，,先给出根 的一个范围.,若 且,可知 在 内至少有一个实根，,这时称 为,根据连续函数性质,结果如下：,方程 的有根区间.,通常可通过逐次搜索法求得方程 的有根区

2、间.,5,由此可知方程的有根区间为,6,如果同号，说明所求的根 在 的右侧,考察有根区间 ，取中点 将它分为 两半，,2 二分法,假设中点 不是 的零点，然后进行根的搜索.,检查 与 是否同号，,否则 必在 的左侧，,这时令,见图7-1.,这时令,图5-1,7,用中点 将区间 再分为两半，,图7-1,对压缩了的有根区间 又可施行同样的手续，,即,不管出现哪一种情况，新的有根区间 的长度仅 为 的一半.,8,如此反复二分下去，即可得出一系列有根区间,其中每个区间都是前一个区间的一半，,因此 的长度,当 时趋于零.,就是说，如果二分过程无限地继续下去，这些区间最终必收缩于一点 ，该点显然就是所求的

3、根.,9,作为根的近似，,该序列必以根 为极限.,由于,只要二分足够多次（即 充分大），便有,这里 为预定的精度.,每次二分后，设取有根区间 的中点,则在二分过程中可以获得一个近似根的序列,10,例2,在区间 内的一个实根，要求准确到小数点后第2位.,解,这里 ，,取 的中点 ，将区间二等分，,由于,即 与 同号，,故所求的根 必在 右侧.,如此反复二分下去, 按误差估计式,求方程,而,这时应令 ，从而得到新的有根区间,欲使,11,只需 ，,计算结果如表5-1.,即只要二分6次，便能达到预定的精度.,12,二分法是计算机上的一种常用算法，计算步骤如下：,步骤1 准备,计算 在有根区间 端点处的

4、 值,步骤2 二分,计算 在区间中点 处的值,步骤3 判断,若 ，则 即是根， 计算过程结束，,若 ，则以 代替 ，否则以,否则检验.,代替 .,13,此时中点 即为所求近似根.,14,2 迭代法及其收敛性,1 不动点迭代法,将方程改写成等价的形式,若 满足 ，则 ；,求 的零点就等价于求 的不动点.,选择一个初始近似值 ，将它代入右端，即可求得,15,如此反复迭代计算,称为迭代函数.,如果对任何 由上述迭代法得到的序列 有极限,则称迭代方程收敛，,故称上述方法为不动点迭代法.,16,方程 的求根问题在 平面上就是要确定曲 线 与直线 的交点,对于 的某个近似值 ，在曲线 上可确定 一点 ，它

5、以 为横坐标，而纵坐标则等于,就是说，迭代过程实质上是一个逐步显示化的过程.,过 引平行 轴的直线，设此直线交直线 于点 ，,然后过 再作平行于 轴的直线，,与曲线 的交点,上述迭代法是一种逐次逼近法，其基本思想是将隐式 方程 归结为一组显式的计算公式 .,17,则点 的横坐标为 ，,图5-2,记作 ，,纵坐标则等于,18,例3,在 附近的根,解,求得的迭代值,如果点列 趋向于点 ，则相应的迭代值 收敛 到所求的根,据此建立迭代公式,求方程,设将方程改写成下列形式,19,各步迭代的结果见表5-2.,这时可以认为 实际上已满足方程，即为所求的根.,如果仅取6位数字，那么结果 与 完全相同.,20

6、,但若采用方程的另一种等价形式,建立迭代公式,仍取迭代初值 ，则有,结果会越来越大，不可能趋于某个极限.,这种不收敛的迭代过程称作是发散的.,一个发散的迭代过程，纵使进行了千百次迭代，其结果也是毫无价值的.,21,2 不动点的存在性与迭代法的收敛性,首先考察 在 上不动点的存在唯一性.,定理1,设 满足以下两个条件：,1. 对任意 有,2. 存在正常数 ，使对任意 都有,则 在 上存在唯一的不动点,证明,先证不动点的存在性.,22,因 ，,以下设 及 ，,若 或 ，则不动点为 或 ，,存在性得证.,定义函数,显然 ，,由连续函数性质可知存在 ,且满足,使 ,即,即为 的不动点.,23,再证唯一

7、性.,设 都是 的不动点，,引出矛盾.,故 的不动点只能是唯一的.,则,24,定理2,设 满足定理1中的两个条件，,对任意 ，,由迭代法得到的迭代序列 收敛到,的不动点 ，并有误差估计,证明,设 是 在 上的唯一不动点，,可知 ，,因 ，故当 时序列 收敛到 .,则,由定理1中条件2)得,25,再证明估计式，,由定理1中条件2)有,反复递推得,于是对任意正整数 有,26,在上式令 ，注意到 即得.,迭代过程是个极限过程.,在用迭代法实际计算时，必须按精度要求控制迭代次数.,根据上式， 对任意正整数 有,在上式中令 知,原则上可以用上述误差估计式确定迭代次数.,27,对定理1和定理2中的条件2，

8、,且对任意 有,则由中值定理知, 对 有,表明定理中的条件2可用 代替.,如果,28,例3中，当 时， ,在区间 中，,又因 ，,而当 时， ，,在区间 中,故条件2）成立，.,所以迭代法是收敛的.,不满足定理条件.,故定理1中条件1也成立.,29,3 局部收敛性与收敛阶,上面给出了迭代序列 在区间 上的收敛性，,定理的条件有时不易检验，实际应用时通常只在不动点 的邻近考察其收敛性，即局部收敛性.,定义1,设 有不动点 ，,对任意 ，,通常称为全局收敛性.,如果存在 的某个邻域,且收敛到 ，,不动点迭代法产生的序列,则称迭代法局部收敛.,30,证明,存在 的某个邻域,使对于任意 成立,定理3,

9、设 为 的不动点，,则不动点迭代法局部收敛.,由连续函数的性质，,此外，,对于任意 ，,总有 ，,于是,依据定理2可以断定迭代过程 对于任意 初值 均收敛.,这是因为,31,讨论迭代序列的收敛速度.,例4,用不同方法求方程 的根,解,这里,其不动点为,可改写为各种不同的等价形式,由此构造不同的迭代法：,32,取 ，,对上述4种迭代法，计算三步所得的结果如下表.,33,从计算结果看到迭代法（1）及（2）均不收敛，且它们均不满足定理3中的局部收敛条件.,注意 .,迭代法（3）和（4）均满足局部收敛条件，且迭代法（4）比（3）收敛快，因在迭代法（4）中 .,34,定义2,则称该迭代过程是 阶收敛的.

10、,特别地, 时称线性收敛;,时称超线性收敛;,时称平方收敛.,35,定理4,对于迭代过程 ，如果 在所 求根 的邻近连续，并且,则该迭代过程在点 邻近是 阶收敛的.,证明,由于 ，据定理3立即可以断定迭代,过程 具有局部收敛性.,再将 在根 处做泰勒展开，利用定理的条件，,则有,36,注意到 ，,因此对迭代误差，,当 时有,这表明迭代过程 确实为 阶收敛.,由上式得,上述定理说明，迭代过程的收敛速度依赖于迭代函数 的选取.,如果当 时 ，则该迭代过程只可能线性收敛.,37,在例4中，迭代法（3）的 ，故它只是线性 收敛.,而迭代法（4）的 ，,由定理4知,该迭代过程为2阶收敛.,而,38,3

11、迭代收敛的加速方法,1 埃特金加速收敛方法,设 是根 的某个近似值，,由微分中值定理，有,其中 介于 与 之间.,假定 改变不大，近似地取某个近似值 ，,用迭代公式校正一次得,则有,39,由于,将它与上式联立，消去未知的 ，,由此推知,在计算了 及 之后，可用上式右端作为 的新近 似，记作 .,若将校正值 再校正一次，又得,有,40,一般情形是由 计算 ，,称为埃特金（Aitken）加速方法.,可以证明,它表明序列 的收敛速度比 的收敛速度快.,记,41,2 斯蒂芬森迭代法,埃特金方法不管原序列 是怎样产生的，对 进 行加速计算，得到序列 .,如果把埃特金加速技巧与不动点迭代结合，则可得到 如

12、下的迭代法：,称为斯蒂芬森(Steffensen)迭代法.,42,它可理解为，要求 的根 ，,已知 的近似值 及 ，其误差分别为,过 及 两点做线性插值函数.,它与 轴交点就是 ，,即方程,的解,令,43,实际上斯蒂芬森(Steffensen)迭代法是将不动点迭代法 计算两步合并成一步得到的，可将它写成另一种不动点迭代,其中,44,则 是 的不动点.,定理 5,反之，若 为 的不动点，设 连续， ，,则 为 的不动点.,若 x* 为迭代函数 的不动点，,定理 6,45,例5,是发散的，现用斯蒂芬森迭代法计算， 取 .,例3中已指出, 下列迭代,46,至于原来已收敛的迭代法，由定理6可知它可达到2阶以上收敛.,计算表明它是收敛的，这说明即使迭代