线性系统的直接法

直接法通过有限次算术运算求解线性系统 Ax = b，通常通过对矩阵进行因式分解，然后通过代入法求解三角系统。

Definition

直接法是一种算法，它在预定的有限次运算中计算线性系统的精确解（精确到舍入误差），与产生一系列近似解的迭代法相对。

Scope

本主题涵盖高斯消元法、其作为LU分解的表达、主元选择在控制误差增长中的作用、三角系统的前向和后向代入法，以及使直接求解器适用于稠密和带状矩阵的运算计数。

Core questions

• 高斯消元法如何将系统简化为三角形式，为什么这等同于LU分解？
• 为什么主元选择是必要的，部分主元选择和完全主元选择如何控制舍入误差的增长？
• 直接求解的计算成本是多少，以及如何利用结构（对称性、带状性、稀疏性）来降低成本？
• 在什么条件下，带部分主元选择的高斯消元法在实践中是后向稳定的？

Key theories

带部分主元选择的LU分解

带行交换的高斯消元法将矩阵分解为 PA = LU，其中 L 是单位下三角矩阵，U 是上三角矩阵；部分主元选择限制了乘数，并使该方法对于实践中遇到的几乎所有矩阵都可靠。

增长因子和后向稳定性

高斯消元法的后向误差由消元过程中元素的增长因子决定；尽管在人为构造的案例中可能出现指数增长，但部分主元选择使增长足够小，以至于该方法对于几乎所有实际问题都是后向稳定的。

Mechanisms

高斯消元法逐列进行：每一步选择一个主元（部分主元选择当前列中幅度最大的候选），将主元行的倍数从下面的行中减去以引入零，并将乘数存储起来形成 L。得到的上三角 U 通过回代求解，右侧通过前代处理。对于一个 n 乘 n 的稠密矩阵，因式分解大约需要三分之二 n 立方次运算，而每次三角求解大约需要 n 平方次运算。

Clinical relevance

当必须以完全精度求解中等大小的稠密或带状系统时，直接求解器是默认的主力工具——在有限元组装、电路仿真、控制以及作为大型数值方案内部求解器中——并且单个因式分解可以重复使用以廉价地求解许多右侧。

History

消元法可追溯到高斯及更早时期，但其在有限精度算术中的行为在 20 世纪 60 年代由 Wilkinson 的后向误差分析阐明，该分析表明部分主元选择可以抑制误差增长，并解释了早期计算机上长期观察到的该方法的经验可靠性。

Key figures

• Carl Friedrich Gauss
• James H. Wilkinson
• Nicholas J. Higham

Seminal works

• trefethen1997
• golub2013
• higham2002

Frequently asked questions

什么时候应该优先选择直接法而不是迭代法？

当矩阵是稠密或中等大小的，当许多右侧共享一个矩阵（因此单个因式分解被重复使用），或者当需要保证有限、全精度的解时，优先选择直接法。非常大的稀疏系统通常更倾向于迭代法。

主元选择总是能保证小误差吗？

部分主元选择在实践中几乎对所有矩阵都保证后向稳定性，但它不能克服病态性：如果矩阵本身接近奇异，即使是后向稳定的求解也可能返回具有大前向误差的解。