1 基本概念
固定点迭代是一类以“求不动点”为核心的数值方法。其基本思路是把原问题转化为寻找满足 \(x=g(x)\) 的点，再从初始值出发，按迭代公式不断更新，逐步逼近目标解。由于形式简洁，这类方法在方程求解、优化与线性代数计算中都十分常见。
1.1 固定点与不动点
若某个点 \(x^\*\) 满足 \(g(x^\*)=x^\*\)，则称 \(x^\*\) 为映射 \(g\) 的固定点，也常称为不动点。此时，点经过映射后位置不变，因此得名“不动点”。
在数值计算中，许多问题都可以通过引入合适的映射转化为不动点问题。若能找到固定点，就相当于得到了原方程或原系统的解。
1.2 迭代思想
固定点迭代的核心是重复应用同一个映射，生成序列 \[ x_{k+1}=g(x_k), \quad k=0,1,2,\dots \] 其中 \(x_0\) 是初始值。若迭代收敛，则序列极限通常就是固定点。
这种方法的优势在于实现方式直接，只需能计算 \(g(x)\) 即可。然而，能否收敛以及收敛速度如何，取决于迭代函数的性质和初值位置。
1.3 迭代格式的构造
把一个问题改写成固定点形式，并不只有唯一方式。不同的改写方式会得到不同的迭代公式，而这些公式在收敛性和效率上可能差异明显。
1.3.1 方程重写为 x = g(x)
对于方程 \(f(x)=0\)，常可通过代数变形写成 \[ x=g(x) \] 例如，将 \(f(x)=0\) 改写为 \(x=x-f(x)\) 只是最直接的形式之一；实际应用中往往需要更合适的拆分方式，以提高收敛概率。
1.3.2 等价变换的原则
构造迭代格式时，通常要求新方程与原方程等价，即两者解集一致或至少在关注范围内一致。若变换不恰当，可能引入伪解、遗漏真解，或使迭代朝错误方向演化。
常见原则包括：保持解的等价性、尽量让迭代函数在目标点附近具有良好收缩性质，以及避免在计算上引入不必要的复杂性。
1.3.3 迭代函数的选择
迭代函数 \(g(x)\) 的选取直接影响收敛行为。理想情况下，\(g\) 应在解附近满足较强的收缩特征，使迭代点迅速靠近固定点。
在实际问题中，常需要在“表达简单”和“收敛稳定”之间折中。有些形式虽然代数上简洁，却可能收敛缓慢甚至发散；另一些形式则计算稍复杂，但更适合数值实现。
2 理论基础
固定点迭代理论主要研究迭代序列是否存在极限、是否唯一、在什么条件下收敛，以及收敛速度如何评估。这些结论通常建立在映射的连续性、压缩性及导数界等条件之上。
2.1 不动点定理
不动点定理为固定点迭代提供了理论保障。它说明在一定条件下，不动点不仅存在，而且可以通过迭代逐步逼近。
2.1.1 压缩映射原理
若映射在某个区域内满足压缩性质，即任意两点经过映射后距离缩小，那么该映射更容易产生收敛的迭代序列。压缩映射原理是固定点理论中的基础工具。
2.1.2 Banach不动点定理
Banach不动点定理指出：在完备度量空间中，若一个映射是压缩映射，则它有唯一的不动点，且从任意初值出发的迭代都收敛到该不动点。该结论在数值分析中极为重要，因为它同时给出了存在性、唯一性与构造性求解方法。
2.2 收敛性条件
固定点迭代能否收敛，通常与迭代函数在固定点附近的局部行为密切相关。导数大小、映射区域范围以及初值位置，都会影响最终结果。
2.2.1 局部收敛
| 局部收敛指迭代在固定点附近从足够接近的初值出发时能够收敛。这类结论常由导数条件保证，例如在一维情形下，若 \( | g'(x^\*) | <1\)，则固定点附近通常具有吸引性。 |
|---|
2.2.2 全局收敛
全局收敛要求从较大范围内的初值出发也能收敛到目标点。相比局部收敛，这一条件更强，也更难满足。通常需要映射在整个迭代区域内都具有压缩性，或配合特殊的保护策略。
2.2.3 初值依赖性
初始值的选择往往决定迭代是否进入收敛区域。即便迭代函数本身具有固定点，若起点落在不利区域，仍可能出现发散、震荡或收敛到其他固定点。因此，初值是实际计算中必须认真处理的因素。
2.3 收敛阶
收敛阶用来描述迭代误差减少的速度。它是衡量算法效率的重要指标，通常与误差递推式的渐近形式有关。
2.3.1 线性收敛
若误差大致按固定比例缩小，即 \[ e_{k+1}\approx C e_k \] 则称为线性收敛。固定点迭代最常见的情形就是线性收敛，特点是稳定但速度一般。
2.3.2 超线性收敛
若误差减少速度快于线性，但又未必达到经典二次收敛标准，则称为超线性收敛。此类方法通常在算法改进中出现，兼顾稳定性与效率。
2.3.3 二次收敛的情形
二次收敛意味着误差满足近似关系 \[ e_{k+1}\approx C e_k^2 \] 这类方法在接近解时收敛极快，但往往对初值和函数光滑性有更高要求。与普通固定点迭代相比，它通常属于更高阶的改进形式。
3 误差与稳定性
数值迭代不仅要关注是否收敛，还要关注误差如何传播，以及算法对扰动的反应是否稳定。误差分析有助于判断计算结果的可信程度。
3.1 绝对误差与相对误差
绝对误差通常指近似值与真值之间的差的绝对值；相对误差则是把这一差值与真值规模进行归一化后的结果。前者更直观，后者更适合比较不同量级的数据。
在固定点迭代中，这两类误差都可能用于衡量迭代终止时的精度。
3.2 迭代误差传播
每一步迭代都会把前一步的误差带入下一步，并可能被放大或缩小。若迭代函数具有收缩性，误差通常会逐步衰减；反之，误差可能持续积累，导致结果偏离真实解。
误差传播是分析迭代稳定性的基础，也是设计终止准则的重要参考。
3.3 稳定性分析
稳定性关注的是：输入或中间计算发生轻微变化时，迭代结果会不会发生明显波动。一个稳定的迭代过程，通常能容忍有限的舍入误差和数据扰动。
3.3.1 数值稳定与条件稳定
数值稳定强调算法本身不会放大计算误差；条件稳定则更侧重问题本身对扰动的敏感程度。即使算法设计合理，如果原问题条件差，最终结果仍可能不够可靠。
3.3.2 对初值扰动的敏感性
固定点迭代常对初值较敏感，尤其在多个固定点并存时更为明显。微小的初值变化，可能导致收敛到不同解，甚至使轨道进入发散区域。
3.3.3 振荡与发散现象
当映射在固定点附近不满足良好收缩条件时，迭代序列可能出现来回摆动，或者数值迅速增大而脱离可控范围。振荡通常意味着局部导数接近或超过特定临界值，而发散则表示迭代未能进入稳定吸引区。
4 经典算法与变体
围绕固定点迭代，发展出了多种增强形式。这些方法的目的通常是提高收敛速度、扩大收敛域，或减少震荡与数值不稳定。
4.1 最基本的固定点迭代
最基本的形式就是直接使用 \[ x_{k+1}=g(x_k) \] 它实现简单，结构清晰，是许多复杂迭代方法的基础。其性能主要由 \(g\) 的收缩程度决定。
4.2 松弛迭代
松弛迭代通过引入权重，对新旧迭代值进行混合，以调节更新幅度。它常用于改善收敛行为。
4.2.1 欠松弛
欠松弛指更新时更偏向保留旧值，即新迭代点只向目标方向前进一小步。这种做法可减弱振荡，适合某些容易过冲的情形。
4.2.2 超松弛
超松弛则是在更新中加大步幅，使迭代更积极地朝目标移动。若参数选取得当，可加快收敛；但若过大，也可能导致不稳定。
4.3 加速固定点迭代
加速方法试图利用已有迭代序列中的信息，构造更接近极限的新序列，从而减少迭代次数。
4.3.1 Aitken加速
Aitken加速常用于改进线性收敛序列，通过消除主要误差项来提高收敛速度。它在一维序列处理中尤其常见。
4.3.2 Anderson加速
Anderson加速通过组合若干步历史迭代信息，生成更优的更新方向。它在大规模非线性问题中应用广泛，常被视为较有效的通用加速手段。
4.4 阻尼迭代
阻尼迭代通过控制每次更新的强度，使迭代过程更加平滑，常用于避免更新过猛造成的发散。
4.4.1 阻尼因子
阻尼因子决定新旧信息的混合比例。较小的因子通常更稳健，但可能降低速度；较大的因子则相反。
4.4.2 自适应步长
自适应步长会根据当前迭代效果动态调整更新幅度，以兼顾收敛稳定性和效率。这种机制常见于更复杂的数值算法设计中。
5 数值求解中的应用
固定点迭代不仅是一种独立方法，也是一种通用框架。许多看似不同的数值算法，实际上都可以解释为不动点迭代。
5.1 非线性方程求根
对非线性方程而言，固定点迭代是最直观的求根工具之一。只要能构造出合适的 \(g(x)\)，便可逐步逼近方程解。
5.1.1 单变量方程
在单变量情形下，方程 \(f(x)=0\) 可通过重写得到 \(x=g(x)\)。若选取得当，迭代能在较少步骤内逼近根；若形式不佳，则可能出现收敛慢或不收敛的问题。
5.1.2 多变量方程组
对于方程组，固定点思想可推广为向量迭代 \[ \mathbf{x}_{k+1}=\mathbf{g}(\mathbf{x}_k) \] 此时，需要同时处理多个分量之间的耦合关系。向量情形的分析往往更复杂，但基本思想保持一致。
5.2 最优化问题
很多优化方法可以被解释为寻找某种映射的不动点。这样一来，固定点理论便可用于分析算法的收敛性与稳定性。
5.2.1 梯度下降的迭代视角
梯度下降可写成 \[ x_{k+1}=x_k-\alpha \nabla f(x_k) \] 从形式上看，这也是一种固定点迭代。若最终达到稳定点，则满足更新前后不变，因而与不动点概念密切相关。
5.2.2 近端映射形式
近端方法常把复杂优化问题转化为一个隐式更新过程，其更新算子本身就是一种固定点映射。该形式特别适合处理带有非光滑项的问题。
5.3 线性代数中的迭代法
在求解大型线性方程组时，直接法可能代价较高，固定点迭代思想因此成为重要替代方案。
5.3.1 Jacobi迭代
Jacobi迭代将线性方程组拆分为对角部分与其余部分，并用上一轮的全部分量同时更新下一轮结果。其结构简单，便于并行实现。
5.3.2 Gauss-Seidel迭代
Gauss-Seidel迭代在更新时会立即使用当前轮已计算出的新值，因此通常比 Jacobi 迭代收敛更快。它体现了顺序更新带来的效率优势。
5.3.3 SOR方法
SOR方法是在 Gauss-Seidel 基础上加入松弛参数的改进形式。通过适当调节参数，可显著影响收敛速度，但参数不当也可能适得其反。
6 计算实现
固定点迭代在程序实现中通常较为直接，但要获得可靠结果，仍需合理设计流程、终止条件与参数策略。
6.1 算法流程
一般流程包括：选定迭代函数、给定初始值、循环计算新迭代点、检测停止条件并输出结果。若在迭代中出现异常增长或无法满足终止条件，则需要中止并重新调整参数。
6.2 停止准则
停止准则用于判断迭代是否已经达到预定精度。实际中通常会联合多种条件，以避免过早停止或无休止计算。
6.2.1 迭代步长阈值
当相邻两次迭代值的差足够小时，往往认为结果已基本稳定。这是最常见的停止判据之一。
6.2.2 残差阈值
残差反映当前近似解代回原问题后的偏差。若残差足够小，说明当前解在原方程意义下已较为接近真实解。
6.2.3 最大迭代次数
为防止算法陷入长时间循环，通常设置最大迭代次数。即使尚未达到精度要求，也可以在超限时终止并返回当前结果。
6.3 参数选取
参数设置对固定点迭代的实际效果影响显著。合理的参数能提升效率，不合适的参数则可能导致失败。
6.3.1 初始值选择
初值应尽量接近目标解所在区域，尤其在局部收敛方法中更为关键。若问题对初值敏感，通常需要借助先验信息或粗略估计来确定起点。
6.3.2 松弛参数设置
松弛参数决定更新幅度，是影响速度与稳定性的关键量。实际选取常依赖经验、试算或问题结构分析。
6.3.3 容差设定
容差表示允许的误差范围。设置过严会增加计算成本，设置过松又可能牺牲结果精度，因此需要根据任务需求折中。
7 局限与注意事项
尽管固定点迭代应用广泛，但它并非对所有问题都适用。理解其局限性，有助于避免误用。
7.1 不收敛的原因
不收敛通常源于迭代函数不具备收缩性、初值不合适、映射形式选取不当，或问题本身存在强非线性和病态特征。即使理论上存在解，迭代也未必能稳定找到它。
7.2 多解与吸引域
当系统存在多个固定点时，不同初值可能落入不同的吸引域，从而收敛到不同解。这使得迭代结果具有明显的路径依赖性。
7.3 周期点与循环
有些映射不会收敛到固定点，而是进入周期循环，例如在两个或多个点之间来回跳转。这说明迭代结构可能存在振荡型动力学行为，而不只是简单的逼近过程。
7.4 伪收敛现象
伪收敛是指迭代值表面上变化很小，但实际并未真正满足原问题。其原因可能是数值舍入、停止准则过松，或迭代在错误区域内暂时趋于平缓。因此，通常需要结合残差等指标综合判断。
8 相关概念
固定点迭代与多个基础数值方法和理论概念联系紧密，常作为理解更高级算法的入口。
8.1 牛顿法
牛顿法是一种经典求根方法，也可改写为固定点迭代形式。与普通固定点法相比，它通常具有更快的局部收敛速度，但对初值和导数计算要求更高。
8.2 不动点方程
不动点方程就是形如 \(x=g(x)\) 的方程，是固定点迭代研究的直接对象。许多数值问题一旦转化为这种形式，就可以借助迭代进行求解。
8.3 迭代法
迭代法是一类通过重复更新逐步逼近解的通用计算策略。固定点迭代属于其中最基本、最具代表性的形式之一。
8.4 数值分析
数值分析研究如何用有限步骤和有限精度近似求解数学问题。固定点迭代在其中占据重要位置，因为它兼具理论性、通用性与实际可实现性。