回代法是一种求解系数矩阵为上三角矩阵的线性方程组的算法。它先由最后一个方程确定最后一个未知数,再将其值代入前一个方程,如此逐步向上,直到求出所有未知数。在数值线性代数中,将一般方程组化为三角形式后,通常以回代法作为求解的最后一步,尤其是在使用高斯消元法时。
数学表述
考虑方程组
其中, 是一个 上三角矩阵,即当 时,。将方程组展开可得
如果所有对角元素 均不为零,则由最后一个方程可得
随后按下标递减的顺序计算其余未知数:
在每一步中,位于 右侧的所有未知数都已确定。正是这种依赖结构使回代过程得以进行。
对角元素均非零这一条件等价于矩阵非奇异,因为三角矩阵的行列式为
示例
对于方程组
由最后一个方程可得
代入第二个方程,得到
最后,
因此,解为
与消元不同,这一计算过程不会在系数矩阵中产生零元素,而是利用矩阵中已有的零元素。
算法与计算成本
一种直接实现如下:
对 i = n, n-1, ..., 1:
s = b[i]
对 j = i+1, ..., n:
s = s - U[i,j] * x[j]
x[i] = s / U[i,i]
对于稠密三角矩阵,该算法执行
次乘法、同样次数的减法,以及 次除法。若将每次乘法、减法和除法均计为一次算术运算,则总运算次数为 。因此,用大O记号表示,其运行时间为 ,而常规稠密消元或矩阵分解的运行时间为 。
计算出的解可以直接覆盖右端向量,因此,除矩阵及该向量所占的存储空间外,只需常数大小的辅助存储空间。如果 是单位上三角矩阵,即所有对角元素均为一,则可以省去除法。
对于稀疏矩阵,实现时可以跳过已知为零的元素。此时,算术运算成本取决于所存储非零元素的数量及其分布。对于上带宽为 的上三角矩阵,求解需要 次运算。
在矩阵分解中的作用
回代法通常是更完整求解方法中的一个步骤。
高斯消元法与 LU分解
高斯消元法将一般方程组变换为等价的上三角方程组,随后通过回代求出未知数;回代与消元阶段本身是不同的步骤。
在包含行置换的LU分解中,一种常见约定是
其中, 是置换矩阵, 是下三角矩阵, 是上三角矩阵。求解 时,依次进行以下步骤:
- 施加置换,得到 。
- 通过前代法求解 。
- 通过回代法求解 。
一旦算出这些分解因子,就可以将其重复用于不同的右端向量,而不必重新进行分解。
QR分解与最小二乘法
对于列向量线性无关的实矩阵 ,其简化QR分解的形式为
其中, 的各列构成标准正交组, 为非奇异的上三角方阵。最小二乘法问题
可化为
再通过回代法求解。对于复矩阵,则以共轭转置代替转置。
Cholesky分解
对于实对称正定矩阵,其Cholesky分解可写为
求解方程组时,先对 使用前代法,再对 使用回代法。
这些方法通过求解三角方程组,而不是显式构造逆矩阵来求解,从而避免了仅需方程组的解时计算逆矩阵所带来的额外工作。
数值精度
在浮点运算中,乘法、减法和除法都会引入舍入误差。不过,通常的回代法具有标准的逐分量后向误差界。在通常的算术模型下,假设未发生上溢或会造成问题的下溢,计算得到的解 满足
其中,绝对值和不等式均按分量理解,且
这里, 为单位舍入误差,并假设 。这意味着计算结果是某个邻近三角方程组的精确解。
这种形式的数值稳定性并不保证解本身的误差很小。前向精度还取决于 的条件数:病态方程组可能会显著放大微小扰动。
即使最终的数学解可以在所用数值格式中表示,过大的中间值仍可能导致上溢。专门的三角方程组求解程序可以引入缩放来降低这一风险。此外,回代法的稳定性本身并不能说明此前进行的矩阵分解也是稳定的。
奇异方程组与矩形方程组
标准递推公式要求对角元素非零。如果 ,就无法用该元素作除数。此时,该方程转而给出相容性条件
若右端非零,则该方程与已赋予的变量值不相容;若右端为零,则在这一步中 尚不能确定。更前面的方程可能还会施加进一步的约束。
因此,仅凭某个对角元素为零,无法区分方程组是无解还是有无穷多解。处理奇异方程组时,需要利用矩阵的秩等信息,识别主元变量、自由变量及相容性条件。
回代法也适用于矩形行阶梯形方程组中的主元方程。先为自由变量赋予参数,再按主元顺序的逆序确定主元变量。
变体与实现
当右端有多个向量时,问题变为
可以逐列单独求解,但分块实现能够同时处理多列,并利用高效的矩阵乘法例程。
分块回代法将方程组划分为三角块形式。例如,
先求解 ,再求解 :
普通标量算法中,相继求解的未知数之间存在顺序依赖。这限制了直接采用并行计算的可能性,不过,分块更新、多个右端向量以及稀疏依赖结构中彼此独立的部分,仍可提供可并行执行的工作。