迭代方程求根与加速.ppt

《迭代方程求根与加速.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

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

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

4、中点即为所求近似根.误差，反复执行步骤2和步骤3，直到区间长度小于允许13§2迭代法及其收敛性1不动点迭代法将方程改写成等价的形式若满足，则；求的零点就等价于求的不动点.选择一个初始近似值，将它代入右端，即可求得为函数的一个不动点.反之亦然，称14如此反复迭代计算称为迭代函数.如果对任何由上述迭代法得到的序列有极限则称迭代方程收敛，故称上述方法为不动点迭代法.15方程的求根问题在平面上就是要确定曲线与直线的交点对于的某个近似值，在曲线上可确定一点，它以为横坐标，而纵坐标则等于就是说，迭代过程实质上是一个逐步显示化的过程.过引平行轴的直线，设此直线交直线于点，然后

5、过再作平行于轴的直线，与曲线的交点上述迭代法是一种逐次逼近法，其基本思想是将隐式方程归结为一组显式的计算公式.16则点的横坐标为，图5-2记作，纵坐标则等于按图5-2中箭头所示的路径继续做下去.在曲线上得到点列其横坐标分别为依公式17例3在附近的根解求得的迭代值如果点列趋向于点，则相应的迭代值收敛到所求的根据此建立迭代公式求方程设将方程改写成下列形式18各步迭代的结果见表5-2.这时可以认为实际上已满足方程，即为所求的根.如果仅取6位数字，那么结果与完全相同.19但若采用方程的另一种等价形式建立迭代公式仍取迭代初值，则有结果会越来越大，不可能趋于某个极限.这种不

6、收敛的迭代过程称作是发散的.一个发散的迭代过程，纵使进行了千百次迭代，其结果也是毫无价值的.202不动点的存在性与迭代法的收敛性首先考察在上不动点的存在唯一性.定理1设满足以下两个条件：1.对任意有2.存在正常数，使对任意都有则在上存在唯一的不动点证明先证不动点的存在性.21因，以下设及，若或，则不动点为或，存在性得证.定义函数显然，由连续函数性质可知存在,且满足使,即即为的不动点.22再证唯一性.设都是的不动点，引出矛盾.故的不动点只能是唯一的.则23定理2设满足定理1中的两个条件，对任意，由迭代法得到的迭代序列收敛到的不动点，并有误差估计证明设是在上的唯一不

7、动点，可知，因，故当时序列收敛到.则由定理1中条件2)得24再证明估计式，由定理1中条件2)有反复递推得于是对任意正整数有25在上式令，注意到即得.迭代过程是个极限过程.在用迭代法实际计算时，必须按精度要求控制迭代次数.根据上式，对任意正整数有在上式中令知原则上可以用上述误差估计式确定迭代次数.26由此可见，只要相邻两次计算结果的偏差足够小即可保证近似值具有足够精度.对定理1和定理2中的条件2，且对任意有则由中值定理知,对有表明定理中的条件2可用代替.如果27例3中，当时，,在区间中，又因，而当时，，在区间中故条件2）成立，.所以迭代法是收敛的.不满足定理条件.

8、故定理1中条件1也成立.