玻尔百科在整个计算科学与工程领域，从模拟流体动力学到计算分子的电子结构，许多复杂问题都可归结为寻找一个“不动点”（fixed point）——即一个解 ，它在函数 的作用下保持不变。这种搜索通常通过简单迭代进行，这是一个强大但往往缓慢的过程，可能难以高效收敛。虽然存在一些基本技术可以稳定这些迭代，但它们通常以牺牲速度为代价，因此需要更智能的加速方法。本文介绍安德森加速（Anderson Acceleration），这是一种杰出的技术，它通过从自身历史中学习，从而实现向解的巨大跃进。我们首先将在“原理与机制”一节中探讨该方法背后的核心思想，揭示其与最优算法之间深刻的数学联系。随后，“应用与跨学科联系”一节将展示该方法在从量子化学到机器学习等不同领域的卓越通用性及其影响。
想象一下，你正试图在公园里找到一个安静的地点，那里的喷泉声和远处道路传来的声音强度相等。你可以从某个地方开始，听一听，然后朝着似乎能让声音更平衡的方向走。你走一步，再听一次，然后重复这个过程。这个简单直观的过程是科学与工程领域大量计算方法的核心。我们称之为定点迭代。
在数学上，我们试图求解形如 的方程。在这里， 可能不是一个单一的数字，而是一个巨大的向量，例如代表涡轮叶片上数千个点的温度、整个流场的压力或分子的电子密度。函数 是一个映射，它接受系统的某个状态 ，并计算出一个新状态 。我们在寻找那个特殊的状态，即不动点 ，它在该映射下保持不变：。这就是我们在公园里的那个安静点，是平衡温度，是稳态流，是基态能量。
这种“简单迭代”功能强大且基础，但可能慢得令人痛苦。有时，每一步只能让你稍微接近解。另一些时候，迭代可能会越过目标，像一个永远无法稳定下来的紧张摆锤一样来回振荡。为了解决这个问题，一个常见的技巧是欠松弛（under-relaxation）。我们不采用 建议的完整步长，而是采取一个更谨慎、更短的步长：
这里， 是一个介于 和 之间的数。这可以稳定一个剧烈发散的迭代，但通常会迫使一个本已收敛的迭代以蜗牛般的速度爬行。 这有点像在糖蜜中行走；你不太可能摔倒，但你也无法很快到达目的地。当然，我们可以更聪明一些。
当你调校一个老式收音机的旋钮时，如果转得过了一点，电台声音变得模糊，然后你又转回来，再次越过目标，你不会只是重复同样笨拙的调整。你会逐渐找到感觉。你会注意到自己错误的模式。你会不自觉地从自己行为的历史中学习，从而做出更好、更果断的调整。
这就是安德森加速（Anderson Acceleration）的精髓，既巧妙又简单。
安德森加速并不丢弃所有过去的尝试，仅使用最后一个点 来寻找下一个点，而是保留一个简短的记忆。它会回顾例如最近 个点的历史，然后提问：“根据我之前的位置和得到的结果，对于解，我能做出的最智能的猜测是什么？”它试图找到这些过去结果的最佳组合，以形成一个全新的、显著改进的猜测，从而实现向解的跃进，而不是缓慢前行。
为此，我们需要一种方法来衡量我们在任意点的“错误”程度。最自然的度量是残差（residual），定义为我们映射的输入和输出之差：。在真正的不动点 处，残差为零。因此，我们的目标是找到残差为零的点。
Anderson 的洞见在于，新的猜测 不是由单个点生成的，而是由函数 最近的输出的加权平均值构成。这被称为仿射组合（affine combination）：
系数 是标量，其和必须为一（）。这个约束至关重要；它确保了如果奇迹般地我们所有过去的点都已经是解，那么我们的新猜测也将是解。但是我们如何找到最佳的权重 呢？我们选择它们来最小化我们已知残差的相应组合的大小：
找到能最小化组合残差向量长度的 ：
这是一种信念的美妙飞跃。我们假设，那个能最好地抵消我们过去尝试中错误的权重组合，也将产生一个更接近真实解的新点。这个最小化问题是一个标准的最小二乘问题，其计算成本很低。 从本质上讲，安德森加速将一个在数百万维空间中寻找残差零点的艰巨任务，投影到了一个由我们最近历史所张成的子空间中的微小、可管理的问题上。
这种方法听起来可能像是一种巧妙但或许有些随意的启发式方法。但事实远非如此。当我们在线性问题这种构成计算科学基石的简单问题上测试安德森加速时，其真正的美妙和威力才得以显现：即求解线性方程组。一个线性定点问题形如 。
当应用于此类问题时，一件非凡的事情发生了：安德森加速在代数上与广义最小残差（GMRES）方法完全相同，后者是数值线性代数领域的巨擘之一。 这是一个深刻的联系。GMRES 被认为是一种“最优”算法，因为它能在专门构建的搜索方向子空间内找到最佳的近似解。安德森加速凭借其简单直观的残差最小化方案，原来是这个算法“皇族”的一员。这是物理学和数学中一个反复出现的主题：一个简单、优雅的思想，当从正确的角度审视时，会发现它是一个更宏大、更强大结构的一部分。
这个隐藏的身份解释了它令人难以置信的有效性。例如，当应用于一维线性问题时，安德森加速可以在一个加速步内找到精确解，瞬间收敛，而简单迭代可能需要数千步才能接近解。 在更高维的线性问题上，它能从其历史中构建出最优近似，其行为就像一个根据问题谱系完美调校的误差缩减多项式滤波器。
对于现实世界中出现的复杂非线性问题，这种联系意味着安德森加速扮演着拟牛顿法（quasi-Newton method）的角色。它构建了系统雅可比矩阵逆矩阵的近似——该矩阵衡量输出如何响应输入的变化——而无需计算那个计算成本极高的矩阵。它从自身迭代的历史中“即时”学习系统的局部响应。这赋予了它标志性的超线性收敛特性，当接近答案时，解的正确位数在每一步都可能翻倍。
这种概念的统一性跨越了多个学科。同一个算法，由 Anderson 在 1965 年发现，又由 Peter Pulay 于 1980 年在量子化学领域独立提出，在那里它被称为 DIIS（迭代子空间直接求逆法），是收敛自洽场计算的主力方法。这是一个绝佳的例子，说明同一个强大的思想如何在不同的背景下涌现，以解决同样的基础问题。
当然，现实世界是复杂的。要充分发挥安德森加速的威力，需要一些实践技巧来驾驭现实世界计算中的陷阱。
首先是成本问题。加速步骤并非没有代价。它需要在每次迭代中存储 个历史向量，并求解一个小的 最小二乘问题。这值得吗？绝对值得。在像模拟核反应堆堆芯这样的大规模仿真中，物理模型一步（一次“输运扫描”）的成本可能非常巨大，并随未知数数量 的增加而增加。然而，安德森加速的开销大致按 的规模增长。如果 很小（例如 5 到 10），而 达到数百万，那么 AA 的开销与单次输运扫描的成本相比，只是沧海一粟。如果这点额外成本能将总扫描次数减半，那么净节省的时间将是巨大的。
更微妙的挑战在于鲁棒性。如果我们学习的历史具有误导性怎么办？这主要有两种情况。首先，在非常“刚性”的问题中，例如模拟轻型结构与稠密流体的相互作用，连续步骤之间的残差可能变得几乎平行。将这种近乎冗余的信息提供给安德森加速，就像要求侦探根据同一条线索的十个副本来破案。底层的最小二乘问题会变得病态，算法可能会产生极其不稳定的外推步骤。
其次，如果函数 带有噪声——例如，当它涉及用于辐射传热的蒙特卡洛模拟时——较长的历史记录可能会诱使算法“过拟合”噪声。它可能会找到一个巧妙的过去迭代组合，抵消掉历史记录中的随机统计波动，从而产生一个与真实底层信号无关的、不符合物理规律的大步长。 [@problem_-id:3965814]
这时工程技术就派上用场了。一个鲁棒的安德森加速实现不仅仅是原始算法，它是一台经过精心调校并带有必要保障措施的机器。
它从不盲目相信建议的步长。它会检查该步长是否确实改善了某个具有物理意义的量，例如总能量平衡。如果某一步使情况恶化，该步长将被拒绝，并尝试一个更谨慎的、带阻尼的步长。
它使用智能的停止准则。它不只是在残差很小时停止。它还会检查加速是否仍在起作用。如果“安德森增益”——相比简单迭代的改进——变得微不足道，或者迭代开始停滞，算法可能会决定清除其历史并重新启动，从而以全新的视角审视问题。
总而言之，安德森加速是深奥数学原理与实用计算智慧相互作用的完美体现。它始于从过去学习的简单直观思想，揭示了与数值分析中一些最强大最优方法的深刻联系，最终成为一个鲁棒、适应性强的工具，在整个科学计算领域都不可或缺。
衡量一个优美的科学思想的真正标准不是其复杂性，而是其简单性及其影响的广度。正如我们所见，安德森加速建立在一个极其简单的前提之上：在迭代的旅程中，不要只看最后一步，而是回顾你走过的路，以便做出更明智的向前跃进。事实证明，这个简单的想法不仅仅是一个小小的数值技巧。它是一个深刻的原理，在众多科学和工程学科中回响。无论我们在哪里遇到迭代和自洽这一基本过程，它都会出现，有时会伪装起来，并以不同的名称示人。让我们踏上穿越这些不同领域的旅程，看看这个原理在实践中的应用，不仅要理解它确实有效，还要对其为何如此强大获得直观的认识。
许多复杂问题，当你仔细审视它们时，会发现其核心是线性的。甚至许多非线性问题也是通过一系列线性近似来求解的。一个经典问题是求解线性方程组 。像 Gauss-Seidel 迭代这样的方法通过将其转化为 形式的定点问题来求解。你可能会认为，将安德森加速应用于如此简单的线性迭代只会带来适度的加速。但实际上发生了远为神奇的事情。
在科学探索中那些美妙的偶然发现时刻之一，我们发现，当安德森加速应用于线性问题时，它在数学上等价于数值线性代数中最著名、最强大的算法之一：广义最小残差法（GMRES）。这不是巧合，而是一个启示。两种方法都以各自的方式发现了同一个基本真理：解决系统的最佳方法是在一个特殊的、不断扩展的方向“子空间”——克雷洛夫子空间（Krylov subspace）——内寻找解，从而在每一步最小化误差。简单迭代在一个方向上走一步，而 AA/GMRES 则通过它所探索过的所有先前方向的最优组合来构建一个“超级步”。它拥有记忆，并利用这份记忆以惊人的效率在高维解空间中导航。
这种联系不仅仅是理论上的奇闻。它具有深远的实际意义。例如，在核反应堆模拟中，计算中子分布需要迭代求解一个线性输运方程。将安德森加速应用于这个“源迭代”过程，本质上是释放 GMRES 的力量，以更快地找到稳定的中子通量，这是反应堆安全和设计的关键任务。此外，这一洞见使我们能够使用安德森加速来改进其他先进方法。广泛使用的重启 GMRES() 方法在遇到问题中的某些“慢”模式时可能会停滞。通过在每个重启周期后应用几步安德森加速作为“平滑器”，我们有效地为算法提供了一个更大的多项式移动工具包，以消除这些麻烦的模式，从而恢复其快速收敛性。
当然，世界很少是线性的。从蛋白质的折叠到机翼上的气流，大多数现象都由非线性方程控制。这些问题通常导致形式为 的定点问题，其中映射 现在是一个复杂的非线性函数。在这里，简单的“Picard”迭代，，可能会慢得令人痛苦，甚至完全无法收敛，就像试图在一条曲折湿滑的斜坡上一次只迈一小步。
安德森加速在这个领域大放异彩。要看到它的真正威力，让我们考虑最简单的非平凡情况：一个一维线性问题，它可以被看作是复杂相互作用的线性化模型，比如飞机机翼上流固耦合界面的作用力。在这种理想化的设置中，仅用一步过去记忆的安德森加速就实现了惊人的效果：它在单次迭代中找到了精确解！这就是其威力背后的秘密。它不仅仅是混合旧解，而是在进行智能外推。在一维情况下，这相当于通过观察残差函数的割线与零交叉的位置来找到不动点。这是 Steffensen's 方法的核心，一种实现二次收敛的著名技术。
在更高维、完全非线性的问题中，我们无法获得这种完美的单步收敛。然而，同样的原理仍在起作用。安德森加速利用迭代历史来构建系统的局部线性近似——一种“穷人的牛顿法”——而无需计算真实且通常非常昂贵的雅可比矩阵。其结果是，它通常将一个缓慢线性收敛的迭代转变为一个更快但仍为线性收敛的迭代。它显著降低了线性收敛常数，将爬行变为快走。
现代物理学和化学中的大量问题都是“自洽”问题。其过程是一个经典的定点迭代之舞：你猜测系统的某个属性（如电子分布），用它来计算它们产生的力或场，然后用这些场来找到一个新的电子分布。你重复这个循环————直到输入与输出相匹配。
这是量子化学中用于确定分子轨道的自洽场（SCF）方法的基石。几十年来，人们一直使用简单的混合方案来引导这些迭代收敛，但对于许多分子来说，这是一个令人沮丧且不稳定的过程。安德森加速的引入——在该领域被称为迭代子空间直接求逆法（DIIS）——改变了游戏规则，将不可能的计算变成了常规计算。
同样的故事也发生在计算材料科学中，那里使用密度泛函理论（DFT）从第一性原理预测材料的性质。DFT的核心是求解 Kohn-Sham 方程，这是另一个庞大的自洽循环。一个引人入胜的问题 对此过程进行建模，并揭示了材料物理性质与数值方法收敛性之间的深刻联系。在模拟的“金属性”相中，长程相互作用会产生难以抑制的、困难的低频误差模式。而在“绝缘性”相中，相互作用更为局域化，收敛更容易。安德森加速的成功取决于它能否构建一个历史记录，有效捕捉并消除这些麻烦的长程模式，使其成为研究金属性系统不可或缺的工具。
这次进入量子世界的旅程也教会了我们谦逊。在求解多体物理学中复杂的 Dyson 方程时，我们发现安德森加速核心的最小二乘问题本身也可能变得病态。这意味着过去步骤的“记忆”变得近乎冗余，试图求解最佳组合就像试图将铅笔立在笔尖上一样。这并不意味着该方法有缺陷，而是必须谨慎使用，利用正则化技术来应对这些数值挑战并保持稳定。
从微观到宏观，工程师们经常面临“多物理场”问题，即不同的物理现象耦合在一起。例如气流与振动的飞机机翼之间的相互作用（流固耦合），或地下岩石变形与流体流动的耦合（孔隙弹性力学）。
一种强大的策略是“分区”方法：求解流体方程，将结果传递给结构；求解结构方程，将结果传回，然后迭代直到界面处的解一致。这又是一个定点问题！
例如，在计算地质力学中，人们可能会将一个一次性处理所有问题的复杂“整体”求解器与一个更简单的分区方案进行比较。分区方案更容易实现，但可能收敛缓慢，尤其是在大时间步长等挑战性场景中。在这里，安德森加速就像一个强大的助推火箭。通过加速简单分区方案的收敛，它可以使其性能超越整体牛顿法，提供一种既鲁棒又高效的解决方案。这代表了一种常见且极具价值的应用场景：使简单、灵活的方法能够与更复杂、更刚性的方法相竞争。
安德森加速的影响力甚至超出了物理科学的范畴。考虑一下机器学习和统计建模的世界。现代数据科学的一个基石是 LASSO 问题，用于在高维环境中寻找稀疏解。
解决 LASSO 问题最流行的算法之一是循环坐标下降法。这个算法初看起来不像是一个定点迭代。但是，如果我们将更新每个坐标的一个完整周期视为一个“步骤”，那么整个过程就变成了从一个参数向量到下一个参数向量的映射：。只要有定点映射，安德森加速就可以派上用场。
通过将 AA 应用于坐标下降法生成的迭代序列，我们通常可以更快地达到最优解。这个应用也凸显了优化中的一个重要实践细节：需要“安全保障措施”。因为安德森加速是一种外推技术，它偶尔会过冲，落入一个目标函数值更差的区域。一个简单的检查——如果新点不比旧点好，就不要进行跳跃——足以使算法变得鲁棒，同时在大多数时候仍能享受加速带来的好处。
从物理学的基本粒子到数据的抽象景观，迭代自洽的原理是一条贯穿始终的线索。安德森加速为解决这些问题提供了一个简单、优雅且效果惊人的工具。它提醒我们，有时，向前迈进的最明智方式是仔细回顾你走过的路。