第二节 迭代法及其收敛性1

数值计算方法对于一般的非线性方程,没有通常所说的求根公式求其精确解,需要设计近似求解方法,即迭代法。它是一种逐次逼近的方法,用某个固定公式反复校正根的近似值,使之逐步精确化，最后得到满足精度要求的结果。10.2迭代法及其收敛性

10.2.1不动点迭代法的基本概念和迭代格式的构造将方程（1.1）改写成等价的形式（2.1）若要求满足，则；反之亦然，称为函数的一个不动点.求的零点就等价于求的不动点，选择一个初始近似值，将它代入(2.1)右端，即可求得如此反复迭代计算（2.2）称为迭代函数.如果对任何，由（2.2）得到的迭代序列有极限则称迭代方程(2.2)收敛，且为的不动点，故称（2.2）为不动点迭代法.

上述迭代法是一种逐次逼近法，其基本思想是将隐式方程（2.1）归结为一组显式的计算公式（2.2），就是说，迭代过程实质上是一个逐步显示化的过程.方程的求根问题在平面上就是要确定曲线与直线的交点对于的某个近似值，在曲线上可确定一点，它以为横坐标，而纵坐标则等于过引平行轴的直线，设此直线交直线于点，然后过再作平行于轴的直线，它与曲线的交点记作，则点的横坐标为，纵坐标则等于图1-2

例1求方程（2.3）在附近的根

解设将方程（2.3）改写成下列形式按图1-2中箭头所示的路径继续做下去，在曲线上得到点列，其横坐标分别为依公式求得的迭代值据此建立迭代公式如果点列趋向于点，则相应的迭代值收敛得到所求的根各步迭代的结果见表.如果仅取6位数字，那么结果与完全相同，这时可以认为实际上已满足方程(2.3)，即为所求的根.但若采用方程（2.3）的另一种等价形式建立迭代公式仍取迭代初值，则有结果会越来越大，不可能趋于某个极限.这种不收敛的迭代过程称作是发散的.一个发散的迭代过程，纵使进行了千百次迭代，其结果也是毫无价值的.xyy=xxyy=xxyy=xxyy=xx*x*x*x*y=(x)y=(x)y=(x)y=(x)x0p0x1p1x0p0x1p1x0p0x1p1x0p0x1p1x210.2.2不动点的存在性与迭代法的收敛性首先考察在上不动点的存在唯一性.定理1设满足以下两个条件：1°映内性对任意有2°压缩性存在正常数,使对都有（2.4）

证明先证不动点存在性.若或，显然在上存在不动点.因，以下设及，定义函数显然，且满足，由连续函数性质可知存在使，即即为的不动点.再证唯一性.设都是的不动点，则由(2.4)得引出矛盾.故的不动点只能是唯一的.证毕.定理.2设满足定理1中的两个条件，则对任意，由（2.2）得到的迭代序列收敛到的不动点，并有误差估计

（2.5）

证明设是在上的唯一不动点，由条件1°，可知，再由（2.4）得因，故当时序列收敛到.再证明估计式（2.5），由李普希兹条件有（2.6）反复递推得于是对任意正整数有在上式令，注意到即得式（2.5）证毕.迭代过程是个极限过程.在用迭代法实际计算时，必须按精度要求控制迭代次数.误差估计式（2.5）原则上可用于确定迭代次数，但它由于含有信息而不便于实际应用.根据式（2.6），对任意正整数有在上式中令知由此可见，只要相邻两次计算结果的偏差足够小即可保证近似值具有足够精度.对上述定理中的压缩性，在使用时如果且对任意有（2.7）则由中值定理可知对有表明定理中的压缩性条件可用（2.7）代替.例7.2.3中，当时，,在区间中，，故（2.7）成立.又因，故定理1中条件1°也成立.所以迭代法是收敛的.而当时，在区间中不满足定理条件.10.3局部收敛性与收敛阶上面给出了迭代序列在区间上的收敛性，通常称为全局收敛性.定理的条件有时不易检验，实际应用时通常只在不动点的邻近考察其收敛性，即局部收敛性.

定义7.2.1设有不动点，如果存在的某个邻域，对任意，迭代（2.2）产生的序列，且收敛到，则称迭代法（2.2）局部收敛.定理7.2.3设为的不动点，在的某个邻域连续，且，则迭代法（2.2）局部收敛.

证明由连续函数的性质，存在的某个邻域，使对于任意成立此外，对于任意，总有，这是因为于是依据定理7.2.2可以断定迭代过程对于任意初值均收敛.

证毕.

解这里，可改写为各种不同的等价形式，其不动点为由此构造不同的迭代法：

例7.2.2用不同方法求方程的根讨论迭代序列的收敛速度.取，对上述4种迭代法，计算三步所得的结果如下表.注意，从计算结果看到迭代法（1）及（2）均不收敛，且它们均不满足定理3中的局部收敛条件，迭代法（3）和（4）均满足局部收敛条件，且迭代法（4）比（3）收敛快，因在迭代法（4）中.

定义7.2.2设迭代过程收敛于方程的根，如果迭代误差当时成立下列渐近关系式则称该迭代过程是阶收敛的,C为渐进误差常数.特别地,时称线性收敛，时称超线性收敛，时称平方收敛.

证明先证充分性由于，据定理7.2.3立即可以断定迭代过程具有局部收敛性.再将在根处做泰勒展开，利用条件（2.8），则有注意到，由上式得因此对迭代误差，当时有（2.9）这表明迭代过程确实为阶收敛.证毕.上述定理说明，迭代过程的收敛速度依赖于迭代函数的选取.如果当时，则该迭代过程只可能是线性收敛.在例7.2.2中，迭代法（3）的，故它只是线性收敛，而迭代法（4）的