迭代法 迭代原理 迭代方法是依靠收敛的迭代序列来求方程根的近似值。 简单迭代法的基本思想 将方程化为等价方程，然后在隔根区间内取一点，按下式计算  （） 计算结果生成数列  如果这个数列有极限，显然就是方程的根。于是可以从此数列中求得满足精度要求的近似根。 相关定义 迭代法： 上述求方程的根的方法. 迭代格式： . 迭代函数：  . 迭代初始值：  . 迭代序列：  . 若序列收敛，则称迭代格式收敛；否则，称迭代格式是发散的。 简单迭代法的步骤 将，其中不唯一，但总能找到。 设，且，即是隔根区间， 在内取一点，按下式计算：  (*1) 可得一个序列，若序列是收敛的，即：  对（*1）式两边取极限得：    即： 为方程的根，也就是的根。 例1．用迭代法求方程在内的实根。取。 （精确解为）。 解：对方程进行如下三种变形： ①、， 建立迭代格式：  可得：，显然这是一个发散的迭代格式。 ②、， 建立迭代格式：  可得： ，迭代格式是收敛的。 ③、， 建立迭代格式：  可得：，迭代格式是收敛的。 从上例可看出，对的迭代函数不唯一，建立的迭代格式有的发散有的收敛，有的收敛的快，有的收敛的慢。 这正是下面所要讨论的两个问题：收敛性问题和收敛速度问题。 二、收敛条件与误差估计 收敛条件 定理1 设在有限区间上存在，且满足如下条件： （1）当， 即 . (*2) （2）存在正常数，使得对， (*3) 则：①在上的解存在且唯一； ②对任选的初始近似，由迭代过程产生的序列收敛到。 证明：①存在唯一性 由（*3）知，上连续， 令  则上连续。 由（*2）知：  则方程= 0在上至少有一个根 。 设在上有两个根 ，即： 则有  其中， 只有当时，不等式才成立。 故：。 ②收敛性 任取，由微分中值定理，有     ，  ，即。 推论 若条件（*3）改为存在正常数，对，不等式  恒成立,则定理1中的结论成立。 我们称满足定理1条件的为从的压缩映射，称定理中的常数为Lipschitz常数。 定理2 设是的一个根，在的某个邻域内存在，且存在正常数，使 ，  （*4） 则任取，迭代格式均收敛于，并且有下列估计式成立。  （*5） 反之，若，则迭代格式发散。 证明：首先证明条件式（*4）成立时迭代格式的收敛性。 显然，在的邻域内定理1的条件（2）成立，在根据微分中值定理和条件式（*4），任取，有  故，即定理1的条件（1）也成立。由定理1，当时，迭代格式收敛于。 下面证明证明条件式（*4）成立时误差估计式（*5）成立。 当时，因为  故 。 类似的， 上两式联立即得误差估计式（*5）。  下证时，迭代格式发散。 由于 所以迭代过程发散。 全局收敛性：对于任意给定，迭代格式均收敛，则称此格式具有全局收敛性。 局部收敛性：若存在根的邻域 使对，迭 代法均收敛，则称此迭代法局部收敛. 如定理2所提到的迭代法收敛性属于局部收敛，因为只有当 选得充分接近时，迭代序列才保证收敛。 收敛速度：由（*5）可见，值愈小，迭代法收敛得愈快。 若，则收敛快；接近于1，则收敛很慢。 例2.求在[0，1]内的一个实根. 解：   ，此时定理1中的条件（*2）成立， 又 ，即定理1中条件（*3）也成立，  对于[0，1]中任意初值，迭代序列  收敛，计算结果如下表，取. n 0 1 2 3 4   0.4 0.3929119 0.39198641 0.39186519 0.39184930   n 5 6 7 8 9   0.39184722 0.39184695 0.39184691 0.39184691 0.39184691  注. 方程也可化为等价方程 . 但此时定理1条件不成立，迭代序列不能保证收敛。 例3： 回顾例1，用迭代法求方程 在内的实根。取。 解：对方程进行如下三种变形： ①、， 建立迭代格式：  得到：。 分析：，当 时，由Th 2可知是发散的，这正和结果吻合。 ②、， 建立迭代格式：  得到：，迭代格式是收敛的。 分析： 即当 时，由Th 1可知是收敛的，这正和结果吻合。 ③， 建立迭代格式：  得到：，迭代格式是收敛的。 分析： ， 即当 时，由定理1可知是收敛的，这正和结果吻合。 又，由（*4）式知道，愈小，收敛性愈好，愈靠近1，收敛性愈差。这正好能解释②和③都收敛，但③收敛的效果比②好。 三、迭代法的流程图 由（*5）式知，如果，则近似解有如下误差估计  所以在正常收敛的情况下，即不十分接近1时，可用控制迭代结束。这种前后两次迭代结果估计误差的办法称为事后误差估计。 考虑流程图时，控制迭代结束的条件可取为： 其中， 四、迭代过程的收敛速度（收敛阶） 收敛速度的阶：判断迭代方法收敛快慢的重要标准。 定义 设迭代序列收敛于，若存在实数 和非零常数，使  成立，则称序列 阶收敛的，相应的迭代方法称为阶收敛方法。特别，当，称为线性收敛；称为平方收敛；称为超线性收敛。 注意：越大，收敛越快。 定理3 设是的根，于的邻域内次连续可导，那么， 若，则迭代过程在的邻近为线性收敛； 若 ，则迭代过程在的邻近为阶收敛。 证明 因为在的邻域内连续，且，所以存在的邻域，使时，（这个邻域是可以取到的。根据函数连续的定义，我们知道，对，当时，有成立。所以，当充分小时，我们总可以取到这样的邻域，使得成立。），故迭代格式局部收敛。由于，又考虑到  其中介于与之间。故而有  （） 所以迭代过程为线性收敛。 当条件成立时，在附近Taylor展开，得 ， 其中位于与之间。 因此  故此迭代法阶收敛。定理得证。 例3. 证明迭代格式是求的三阶方法。假设充分靠近，求：。 证明： 说明：为方程的根。 为计算方便，将方程化为：  （*） 对（*）式求一阶导数： ， 则有：。 对（*）式求二阶导数： ， 则有： 对（*）式求三阶导数： ， 则有：， 由定理3知为三阶收敛方法。 有 五、加速收敛的埃特金法 设是方程根的一个近似值，由开 始相继迭代两次，将其结果记作 ，，则有  当时，，因此  所以  这样构造的公式不再含有导数的信息，但需要用两次迭代值进行加工。我们有如下迭代格式：  称之为埃特金（Aitken）外推加速法。 例4 求方程在附近的根。 解 取，迭代格式，得  若用埃特金法，则  仍取，得  由此可见，埃特金法加速收敛的效果是相当显著的。 作业 习题二 7，8