数值线性代数 · aiwiki.page

数值线性代数是线性代数的一个分支，研究如何使用有限精度算术求解涉及向量和矩阵的问题。其主要任务包括求解线性方程组、拟合最小二乘模型、计算特征值与特征向量，以及构造矩阵分解。与纯符号方法不同，数值线性代数研究舍入误差、对输入数据的敏感性、矩阵结构和计算资源如何影响算法的可靠性与效率。矩阵分解是这些计算的核心框架。(netlib.org)

条件性与数值稳定性

计算机通常通过浮点运算表示和处理数值数据，因此中间结果一般会产生舍入误差。理解这些误差需要区分两个概念：条件性描述数学问题对输入扰动的敏感程度，而稳定性描述算法如何传播计算误差。即使算法设计良好，也无法消除问题本身固有的敏感性。(netlib.org)

对于可逆矩阵 $A$ ，在相容的诱导范数下，其条件数为

\kappa(A)=\|A\|\,\|A^{-1}\|.

条件数较大，意味着某些微小的相对扰动可能导致解发生大得多的相对变化。前向误差衡量计算结果与精确结果之间的差异；后向误差衡量需要对输入施加多大扰动，才能使计算结果成为精确结果。后向稳定的方法得到的是某个邻近问题的精确解，但如果原问题是病态的，其前向误差仍可能很大。(netlib.org)

对于线性方程组 $Ax=b$ ，近似解 $\hat{x}$ 的残差为 $r=b-A\hat{x}$ 。仅凭残差较小，并不能断定 $\hat{x}$ 接近真实解；还必须考虑问题的条件性。因此，求解器的诊断通常会结合基于残差的误差估计与条件数估计。(netlib.org)

直接法与矩阵分解

直接法通过有限次运算将问题化简，而不是主要通过不断改进近似解直至满足停止准则来求解。矩阵分解将矩阵表示为若干因子的乘积，利用这些因子的结构简化后续计算。(cs.cornell.edu)

高斯消元法可以得到LU分解，通常写为

PA=LU,

其中 $P$ 表示行置换， $L$ 为下三角矩阵， $U$ 为上三角矩阵。随后通过前代和回代求解方程组。部分选主元法从当前列中可选的元素里选择绝对值最大的元素作为主元，有助于避免过小的主元和过大的元素增长，但并不能无条件地保证避开所有不利情形。(netlib.org)

对于实对称正定矩阵，乔列斯基分解无需选主元即可得到 $A=LL^T$ 。另一种基本分解是QR分解，即 $A=QR$ ，其中 $Q$ 的列向量构成标准正交组， $R$ 为上三角矩阵。乘以正交矩阵不会改变欧几里得范数，这一性质对于构造稳定的变换十分重要。(netlib.org)

常规稠密矩阵LU分解的计算复杂性随矩阵阶数呈三次增长。一旦得到这些因子，就可以重复使用它们，求解具有其他右端项的方程组。这种先分解再求解的过程避免了仅为求解 $Ax=b$ 而显式构造逆矩阵。(johnfoster.pge.utexas.edu)

最小二乘与奇异值

线性最小二乘问题求解的是

\min_x\|Ax-b\|_2.

它是普通最小二乘法和线性回归的核心。对于列满秩的超定方程组，使目标函数达到最小值的解是唯一的。QR分解在保持相关范数不变的同时，将问题转化为三角方程组的求解。(netlib.org)

在上述假设下，正规方程 $A^TAx=A^Tb$ 在数学上与原问题等价，但有

\kappa_2(A^TA)=\kappa_2(A)^2.

因此，与基于QR分解的方法相比，构造并求解正规方程可能会加剧数值计算中的困难。(courses.seas.harvard.edu)

奇异值分解将矩阵写为 $A=U\Sigma V^*$ ，其中 $\Sigma$ 的对角元素是非负的奇异值， $^{*}$ 表示共轭转置。它可用于求取最小范数解以及处理秩亏问题。在计算中，判断有效的矩阵的秩需要设定阈值，因为极小的奇异值既可能反映真实的结构，也可能是扰动造成的。吉洪诺夫正则化通过加入惩罚项来修改拟合问题，以改变所求解为代价降低对扰动的敏感性。(netlib.org)

特征值计算

计算特征值与特征向量是另一项主要任务。对于一般的稠密矩阵，QR算法通过一系列变换得到舒尔形，再从中提取特征值。实舒尔形为拟上三角形式，允许用二阶矩阵块表示成对的共轭复特征值。(netlib.org)

实际的QR算法实现使用正交变换或酉变换，并且可以做到后向稳定。不过，特征值的敏感性取决于矩阵本身：仅有后向稳定性，并不能保证每个特征值或特征向量的误差都很小。(netlib.org)

稀疏方程组与迭代法

对于大型稀疏矩阵，算法会利用非零元素占比很小这一特点。迭代求解器通常主要依赖矩阵与向量的乘积，避免进行完整的稠密矩阵分解。克雷洛夫子空间法通过反复将矩阵作用于初始残差，生成相应的子空间，并在这些子空间中构造近似解。(netlib.org)

共轭梯度法适用于对称正定方程组。GMRES通过在当前克雷洛夫子空间内最小化残差，求解一般的非对称方程组。不采用重启时，其存储需求和正交化工作量会不断增长；重启可以限制这些开销，但可能影响收敛。预条件化利用旨在改善收敛性的辅助算子变换方程组，其效果需要与构造和应用该算子的成本相权衡。(netlib.org)

软件与实现

BLAS提供标准化的向量、矩阵与向量以及矩阵与矩阵运算；LAPACK则以这些计算内核为基础，构建更高层次的求解器和矩阵分解程序。分块算法围绕矩阵与矩阵运算来组织计算，以提高数据复用率并支持并行计算。因此，性能不仅取决于算术运算次数，也取决于内存访问方式和底层计算内核的效率。(netlib.org)