3.3 迭代法 3.3.1 不动点迭代 一般地，为了求一元非线性方程 (3.3.1) 的根，可以先将其转换为如下的等价形式 (3.3.2) 式中连续函数 称为迭代函数，并使 两个方程具有相同的解，然后构造迭代公式 （3.3.3 ） 1 计算方法》李桂成 编著 电子工业出版社 对于给定的初值 ，由（3.3.3）可产生 一个迭代序列 如果有 由于 连续，则 则 是（3.3.2）的解，由等价性知 也 是(3.3.1)的解称 为 的不动点，迭代公 式(3.3.3) 称为收敛的，并称其为不动点迭代 法.由于在(3.3.3)式中， 仅由 决定，因此 （3.3.3）式称为单步迭代法 2 计算方法》李桂成 编著 电子工业出版社 称为方程根的第 次近似值 如果迭代 序列 的极限不存在，则称迭代公式（3.3.3 ）是发散的。
因此，在使用迭代法求方程根的近似值时 ，首先要考虑的问题是：如何选取迭代函数 ，使 迭 代 公 式 收敛 3 计算方法》李桂成 编著 电子工业出版社 3.3.2 迭代法的收敛性 为了研究迭代法的收敛性，我们首先介 绍迭代法的几何意义，从几何上讲，求方程 的 根，即求直线 与曲线 的 交点 的横坐标 如图（3.3.1） 4 计算方法》李桂成 编著 电子工业出版社 5 计算方法》李桂成 编著 电子工业出版社 对于 的某个初始近似值 ，在曲线 上可 以确定以 为横坐标的一点 ， 的纵坐标为 ，过点 作 轴的平行线交直线 于 ，过 作 轴的平行线交曲线 于 ，则 的横坐标为 ，如此继续下去，在曲线 上就得点列 其横坐标 ， 由迭代公式 求得， 如果点列 越来越逼近交点 ，则迭代法收 敛,否则迭代法发散从图（3.3.1）可以看出，(a)(b) 两种情形是收敛的，其共同特点是曲线 走势很 缓,即 ，而(c)(d)两种情形发散，其共同特征是 曲线 走势很陡，即 ，下面给出迭代(3.3.3)式 的收敛性基本定理。
6 计算方法》李桂成 编著 电子工业出版社 定理3.3.1 （收敛性基本定理）设迭代函数 满足如下条件： （1） 在 内连续，在 内可导 （2）映内性：对任意的 ，有 （3）压缩性：存在一个常数 使得在 内 7 计算方法》李桂成 编著 电子工业出版社 则： （1）函数 在[a,b]内存在唯一的不动点 （2）对于任意的初始值 由（3.3.3）式 产 生的近似值序列 ，并且 （3）有误差不等式 （3.3.4 ） （3.3.5 ） 8 计算方法》李桂成 编著 电子工业出版社 9 计算方法》李桂成 编著 电子工业出版社 输入 对于 执行 y n 输出 并终止 计算 输出迭代失败信息，终止计算 下面给出迭代法的算法，算法中下面给出迭代法的算法，算法中 为初值，为初值， 为精度，为精度， 为最大迭代次数，为最大迭代次数， 为迭代函数为迭代函数 。
10 计算方法》李桂成 编著 电子工业出版社 在方程求根的迭代法中，迭代函数 的确定, 至关重要，它直接影响着迭代法的收敛性但在实 际应用中，同一个方程可以等价导出不同的迭代函 数，而且要严格地利用定理3.3.1的条件判断迭代公 式在整个区间 内收敛（全局收敛）也非常困难, 因此常常判断迭代公式的局部收敛性 定义3.3.1设 是迭代函数 的不动点,若存 在 的某个领域 ， 使得对任意初值 ，由 迭 代 公式（3.3.3）生成的序列 且有 ，则称迭代公(3.3.3) 是局部收敛的 11 计算方法》李桂成 编著 电子工业出版社 定理3.3.2(局部收敛性定理)设 是迭代函数 不 动 点，若 在 的某个邻域上连续，并有 称 迭代公式（3.3.3）局部收敛 证明：由于 在 的某邻域上连续,且 则 必 存在 的一个 邻 域 和 常 数 由 微 分 中 值 定 理 知，对 任 何 ， 都 有 （ 其 中 ， ）这说明 于是由 定 理 3.3.1 和定义3.3.1知,迭代公式 (3.3.3)局部收敛。
12 计算方法》李桂成 编著 电子工业出版社 当迭代公式收敛时，收敛速度的快慢用收敛阶来衡量 定义3.3.2（收敛阶）设序列收敛到 并记误差 若存在常数和 ，使得： （3.3.6） 则称序列是 阶收敛的，当 称为线 性收敛，当 时， 时，称为超线性收敛， ，称为二次收敛或平方收敛 13 计算方法》李桂成 编著 电子工业出版社 则迭代公式（3.3.3）局部收敛，并且是 阶收敛的 定理3.3.3 （整数阶超线性收敛定理）设 迭代函数的不动点，若有正整数 ，使得 在 的邻域连续 ，并且满足 是 14 计算方法》李桂成 编著 电子工业出版社 。