1 基本概念
迭代算法是通过重复应用同一计算步骤，使近似解逐步逼近目标解的一类方法。它通常先给出初始值，再依照固定规则不断更新，直到结果达到预定精度或满足停止条件为止。与直接求解法相比，迭代算法更适合处理规模较大、结构较复杂或难以一次性解析求解的问题。
1.1 迭代与递推的区别
迭代强调的是“反复改进同一个近似值”的过程，常见于数值计算中。例如，从一个初始估计出发，多次修正，逐渐接近方程解。递推则更侧重于“由前一项或若干前项生成下一项”的序列构造过程，常用于定义数列、函数或离散模型。两者在形式上可能相似，但迭代通常以求解为目标，递推则更偏向关系定义与序列生成。
1.2 初始值与更新规则
初始值是迭代过程的起点，往往会影响收敛速度，甚至决定算法能否成功收敛。更新规则则规定每一步如何由当前近似值生成下一步近似值，通常可表示为某种映射或计算公式。一个设计良好的更新规则需要兼顾精度、稳定性与计算代价。
1.3 终止条件与误差控制
迭代算法并不会无限进行，通常需要设置终止条件。常见标准包括达到最大迭代次数、残差足够小、相邻两次结果差异低于阈值等。误差控制则用于衡量当前近似解与真实解之间的偏离程度，并据此判断是否继续迭代。
1.4 收敛与发散
若迭代生成的序列逐渐趋向某个固定值，称为收敛；若序列不断偏离目标、振荡增大或无界增长，则称为发散。收敛性是评价迭代算法有效性的核心指标之一。一个方法可能在理论上可收敛，但在实际计算中由于初值、舍入误差或参数选择不当而表现不佳。
2 数学基础
迭代算法的分析通常依赖不动点理论、误差分析和收敛阶等工具。它们提供了判断算法是否可靠、收敛多快以及误差如何传播的理论框架。
2.1 不动点理论
不动点理论研究映射在何种条件下存在不动点，以及如何通过迭代逼近该不动点。在数值计算中，许多问题都可改写为不动点形式，从而转化为迭代求解。
2.1.1 不动点方程
若某个值经过映射后仍保持不变，即满足 \(x=g(x)\)，则称 \(x\) 为不动点，对应的方程称为不动点方程。很多非线性方程、优化条件和离散模型都可变形为这一形式，便于构造迭代格式。
2.1.2 Banach不动点定理
Banach不动点定理说明，在完备度量空间中，如果映射是压缩映射，那么它存在唯一不动点，且从任意初值出发的迭代都会收敛到该点。该定理为迭代法的收敛性提供了重要保证，也是构造稳定算法的基础之一。
2.2 误差分析
误差分析用于研究近似解与精确解之间的偏差来源及其演化规律。迭代算法中的误差一般会在每步更新中传播，有时会被放大，有时会逐步减小。
2.2.1 绝对误差与相对误差
绝对误差是近似值与真实值之差的绝对值，反映偏离的实际大小。相对误差则是将绝对误差与真实值或其尺度进行比较，更适合衡量不同量级问题中的精度。前者直观，后者便于跨尺度评估。
2.2.2 截断误差与舍入误差
截断误差来自将无限过程、连续模型或高阶项截去后所产生的偏差，例如将理论公式离散化时引入的误差。舍入误差则来源于计算机有限精度表示与运算过程中的取整。迭代次数增加时，这两类误差都可能影响最终结果。
2.3 收敛阶
收敛阶用来描述迭代误差减小的速度，是比较不同方法效率的重要指标。一般而言，收敛阶越高，接近解的速度越快，但单步计算通常也更复杂。
2.3.1 线性收敛
若误差在相邻迭代中大致按固定比例缩小，则称为线性收敛。此类方法稳定、易实现，但在高精度要求下可能需要较多迭代步数。
2.3.2 超线性收敛
超线性收敛快于线性收敛，但通常又不如二次收敛那样陡峭。它常见于某些改进型迭代方法，在保持适度计算成本的同时提升了收敛效率。
2.3.3 二次收敛
二次收敛意味着误差的下降速度非常快，通常接近于误差平方级别缩小。牛顿类方法在条件合适时可表现出这一特性，因此常被视为高效迭代法的代表。
3 典型迭代方法
迭代方法种类繁多，按用途可分为线性方程组、非线性方程、特征值问题和优化问题等多个类别。不同方法在收敛性、计算量和适用范围上各有特点。
3.1 线性方程组迭代法
线性方程组迭代法主要用于求解大规模稀疏系统。与直接消元法相比，它们更节省存储空间，且适合并行计算。
3.1.1 Jacobi迭代
Jacobi迭代在更新每个分量时使用上一轮全部分量的值，因此形式清晰、实现简便。它的优点是易于并行，但收敛速度通常较慢，对矩阵结构有一定要求。
3.1.2 Gauss-Seidel迭代
Gauss-Seidel迭代在更新时会尽量使用当前轮已计算出的新值，因此通常比Jacobi迭代收敛更快。它在许多实际问题中较为常用，但并行化难度相对更高。
3.1.3 SOR方法
SOR方法是在Gauss-Seidel迭代基础上引入松弛因子，通过适当调整更新幅度来加速收敛。若参数选取合理，往往能明显提高效率，但参数不当也可能导致稳定性下降。
3.2 非线性方程迭代法
非线性方程的求解常依赖局部线性化或映射构造。相比线性情形，这类问题对初值更敏感，算法设计也更依赖问题结构。
3.2.1 牛顿迭代法
牛顿迭代法通过对非线性函数在当前点进行线性近似，构造新的改进值。它在接近解时通常收敛极快，但对初值和导数信息依赖较强，若条件不佳则可能失效。
3.2.2 割线法
割线法用相邻两点构造斜率近似导数，从而避免显式计算导数。该方法实现较为方便，适合导数难以获得的情形，但其收敛速度一般低于牛顿法。
3.2.3 不动点迭代法
不动点迭代法将原方程改写为 \(x=g(x)\)，然后不断重复应用映射 \(g\)。其优点是形式简洁，缺点是对映射构造要求较高，且收敛性高度依赖于函数性质。
3.3 特征值问题迭代法
特征值迭代法用于近似求矩阵的主特征值、特征向量或部分谱信息，尤其适合大型矩阵情形。
3.3.1 幂法
幂法通过反复乘以矩阵并进行适当归一化，逐步提取主特征向量对应的信息。它实现简单，适用于主特征值与其他特征值分离较明显的情况。
3.3.2 反幂法
反幂法通过对矩阵进行逆向作用来寻找靠近指定值的特征信息，常与位移技巧结合使用。该方法可提高对目标特征值附近分量的敏感性，常用于精细谱分析。
3.3.3 QR迭代的基本思想
QR迭代通过矩阵分解与相似变换不断改进矩阵形式，使其逐渐接近上三角结构，从而读出特征值信息。它是特征值计算中的重要方法之一，在数值稳定性方面表现较好。
3.4 优化中的迭代法
优化问题通常目标明确，但变量维数可能较高，且目标函数未必可直接求极值，因此需要借助迭代搜索最优解。
3.4.1 梯度下降法
梯度下降法沿目标函数下降最快的方向逐步更新参数，是最基础的优化迭代方法之一。其优点是直观、通用，缺点是可能收敛较慢，并对步长选择较敏感。
3.4.2 共轭梯度法
共轭梯度法适用于特定类型的二次优化或线性方程问题，能够在较少步数内获得较好结果。它比普通梯度下降更高效，尤其适合大规模稀疏系统。
3.4.3 牛顿法与拟牛顿法
牛顿法利用二阶信息构造更新方向，通常收敛较快，但每步计算代价较高。拟牛顿法则通过近似海森矩阵来降低开销，在效率与精度之间取得折中。
4 收敛性分析
收敛性分析旨在判断迭代是否会逼近解，以及逼近过程是否稳定、快速。该部分通常结合理论条件与数值经验共同评估。
4.1 收敛判据
收敛判据是衡量迭代过程是否继续的依据，也是算法设计中的关键环节。
4.1.1 充分条件与必要条件
充分条件保证算法在一定条件下必然收敛，但并不意味着这些条件是必须的。必要条件则是收敛所不可缺少的要求。实际应用中，常以充分条件作为安全依据，再结合经验调参。
4.1.2 谱半径判据
对于线性迭代格式，迭代矩阵的谱半径常被用来判断收敛性。若谱半径小于1，则迭代通常可收敛；若大于等于1，则往往难以保证收敛。该判据在理论分析中十分常见。
4.2 单调性与稳定性
单调性反映迭代序列在数值上的变化趋势，稳定性则关注误差受扰动影响的程度。两者都与算法在实际计算中的可靠性密切相关。
4.2.1 数值稳定性
数值稳定性指算法在有限精度环境下对误差传播的控制能力。一个稳定的方法即使存在舍入误差，也不至于使结果迅速失真。
4.2.2 条件数影响
条件数刻画问题对输入扰动的敏感程度。条件数越大，问题越“病态”，迭代过程越可能受到误差放大影响，因此需要更谨慎的参数和更严格的停止准则。
4.3 加速技术
加速技术的目标是在不显著增加复杂度的情况下提高收敛速度，减少迭代步数。
4.3.1 松弛技术
松弛技术通过对新旧值进行加权组合，调节每步更新的幅度。适当松弛可避免震荡并提升速度，但过度松弛可能导致发散。
4.3.2 外推法
外推法利用已有迭代结果推测更接近极限的位置，从而缩短收敛路径。它常用于序列加速和误差消除。
4.3.3 Aitken加速
Aitken加速通过对收敛序列做变换，减少线性收敛中的误差分量。该方法使用方便，在很多单变量迭代中具有良好效果。
5 算法实现
迭代算法的实际应用不仅取决于理论形式，还与程序设计、计算资源和停止规则密切相关。
5.1 迭代格式设计
迭代格式设计关注如何将数学更新规则转化为可执行的计算步骤。合理的格式应清晰、稳定，并便于扩展。
5.1.1 向量化实现
向量化实现通过数组或矩阵运算统一处理多个分量，减少显式循环，提高计算效率。它在现代数值软件和高性能计算中十分常见。
5.1.2 矩阵分裂思想
矩阵分裂思想将原问题拆分为若干更易处理的部分，再据此构造迭代公式。许多经典线性迭代法都建立在这一思想之上。
5.2 停机准则
停机准则决定何时结束迭代，是平衡精度与效率的重要手段。
5.2.1 残差准则
残差准则通过衡量当前结果代回原方程后的偏差大小来判断是否收敛。若残差已足够小，通常认为近似解可接受。
5.2.2 相邻两次近似差准则
该准则比较连续两次迭代结果的差异，如果变化已低于阈值，则停止计算。它实现简单，但有时不足以完全反映真实误差。
5.3 复杂度与效率
复杂度分析有助于评估某种迭代法在大规模问题中的可行性。效率不仅取决于单步成本，也取决于总迭代次数。
5.3.1 时间复杂度
时间复杂度描述完成一次或多次迭代所需的计算量。对于大规模问题，单步复杂度和收敛步数都必须综合考虑。
5.3.2 空间复杂度
空间复杂度反映算法运行时所需的存储量。迭代法通常不必保存大量中间结果，因此在内存受限场景中具有优势。
5.3.3 并行化处理
许多迭代算法可以利用并行计算加速，尤其适合向量或矩阵操作密集的任务。并行化能显著提升大规模计算效率，但也需要处理数据依赖与同步开销。
6 应用领域
迭代算法几乎贯穿现代科学计算与工程建模的多个环节，是求解复杂问题的重要工具。
6.1 科学计算
科学计算中常见的大型模型往往无法直接解析求解，因此需要借助迭代法进行数值近似。
6.1.1 偏微分方程数值解
偏微分方程离散化后通常会转化为大规模代数方程组，迭代法可用于逐步求解。它在热传导、流体模拟和波动问题中应用广泛。
6.1.2 大规模线性系统求解
在高维科学计算中，线性系统往往规模巨大且稀疏。迭代法可以显著减少存储压力，并在适当预处理后获得良好性能。
6.2 工程问题
工程计算常要求兼顾精度、速度与稳定性，迭代法因此成为常用工具。
6.2.1 结构分析
结构分析中，力学模型离散化后常形成大型计算系统。迭代算法可用于求解位移、应力及相关响应量。
6.2.2 控制系统设计
控制系统设计中，参数整定、状态估计和稳定性分析都可能借助迭代过程完成。通过反复修正模型参数，可使系统性能逐步接近期望指标。
6.3 数据科学
在数据科学中，许多估计和学习任务本质上都是优化问题，因而天然适合迭代式求解。
6.3.1 参数估计
参数估计通常通过迭代优化目标函数或似然函数来完成。随着迭代推进，模型参数逐步逼近更合理的取值。
6.3.2 机器学习中的优化迭代
机器学习模型训练常依赖迭代更新参数，例如通过梯度类方法最小化损失函数。不同算法在收敛速度、稳定性和计算成本上各有侧重。
7 相关概念与扩展
迭代算法与若干相近概念存在联系，也衍生出多种扩展形式，适用于更复杂的计算场景。
7.1 递归算法与迭代算法
递归算法通过函数自我调用完成求解，常见于分治、树结构处理等问题。迭代算法则依赖循环与状态更新，通常更便于控制内存开销。二者都可实现重复计算，但表达方式不同。
7.2 近似算法
近似算法不一定追求精确解，而是以较低代价获得足够好的结果。某些近似算法内部也会采用迭代机制，通过不断改善当前解提高结果质量。
7.3 随机迭代算法
随机迭代算法在更新过程中引入随机性，常用于高维优化、采样和大数据计算。它们有时能突破确定性方法的局限，但分析收敛性与稳定性往往更复杂。
7.4 多重网格与分层迭代方法
多重网格与分层迭代方法通过在不同尺度上协同处理误差，加快整体收敛。它们特别适合偏微分方程和大型稀疏系统，能够有效消除长波与短波误差分量。