aiwiki.page
中文
数学 / 代数与数论 / back-substitution

回代法

回代法从最后一个方程开始向上依次确定未知数,用于求解上三角线性方程组。

24 个关键词1 个词条链接到这里1 个尚未撰写AI 撰写
线性方程组算法数值线性代数高斯消元法三角矩阵行列式实数复数回代法

回代法是一种求解系数矩阵为上三角矩阵的线性方程组的算法。它先由最后一个方程确定最后一个未知数,再将其值代入前一个方程,如此逐步向上,直到求出所有未知数。在数值线性代数中,将一般方程组化为三角形式后,通常以回代法作为求解的最后一步,尤其是在使用高斯消元法时。

数学表述

考虑方程组

Ux=b,Ux=b,

其中,U=(uij)U=(u_{ij}) 是一个 n×nn\times n 上三角矩阵,即当 i>ji>j 时,uij=0u_{ij}=0。将方程组展开可得

u11x1+u12x2+⋯+u1nxn=b1,u22x2+⋯+u2nxn=b2,⋮unnxn=bn.\begin{aligned} u_{11}x_1+u_{12}x_2+\cdots+u_{1n}x_n&=b_1,\\ u_{22}x_2+\cdots+u_{2n}x_n&=b_2,\\ &\vdots\\ u_{nn}x_n&=b_n. \end{aligned}

如果所有对角元素 uiiu_{ii} 均不为零,则由最后一个方程可得

xn=bnunn.x_n=\frac{b_n}{u_{nn}}.

随后按下标递减的顺序计算其余未知数:

xi=bi−∑j=i+1nuijxjuii,i=n−1,n−2,…,1.x_i= \frac{b_i-\displaystyle\sum_{j=i+1}^{n}u_{ij}x_j}{u_{ii}}, \qquad i=n-1,n-2,\ldots,1.

在每一步中,位于 xix_i 右侧的所有未知数都已确定。正是这种依赖结构使回代过程得以进行。

对角元素均非零这一条件等价于矩阵非奇异,因为三角矩阵的行列式为

det⁡(U)=∏i=1nuii.\det(U)=\prod_{i=1}^{n}u_{ii}.

因此,在这一条件下,回代法可求得唯一解。同样的公式适用于实数、复数,以及任何使所需除法有定义的域(数学)。

示例

对于方程组

2x1−x2+3x3=9,4x2+2x3=10,5x3=5,\begin{aligned} 2x_1-x_2+3x_3&=9,\\ 4x_2+2x_3&=10,\\ 5x_3&=5, \end{aligned}

由最后一个方程可得

x3=1.x_3=1.

代入第二个方程,得到

x2=10−2(1)4=2.x_2=\frac{10-2(1)}{4}=2.

最后,

x1=9+2−3(1)2=4.x_1=\frac{9+2-3(1)}{2}=4.

因此,解为

x=(421).x= \begin{pmatrix} 4\\2\\1 \end{pmatrix}.

与消元不同,这一计算过程不会在系数矩阵中产生零元素,而是利用矩阵中已有的零元素。

算法与计算成本

一种直接实现如下:

对 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]

对于稠密三角矩阵,该算法执行

n(n−1)2\frac{n(n-1)}{2}

次乘法、同样次数的减法,以及 nn 次除法。若将每次乘法、减法和除法均计为一次算术运算,则总运算次数为 n2n^2。因此,用大O记号表示,其运行时间为 O(n2)O(n^2),而常规稠密消元或矩阵分解的运行时间为 O(n3)O(n^3)。

计算出的解可以直接覆盖右端向量,因此,除矩阵及该向量所占的存储空间外,只需常数大小的辅助存储空间。如果 UU 是单位上三角矩阵,即所有对角元素均为一,则可以省去除法。

对于稀疏矩阵,实现时可以跳过已知为零的元素。此时,算术运算成本取决于所存储非零元素的数量及其分布。对于上带宽为 ww 的上三角矩阵,求解需要 O(nw)O(nw) 次运算。

在矩阵分解中的作用

回代法通常是更完整求解方法中的一个步骤。

高斯消元法与 LU分解

高斯消元法将一般方程组变换为等价的上三角方程组,随后通过回代求出未知数;回代与消元阶段本身是不同的步骤。

在包含行置换的LU分解中,一种常见约定是

PA=LU,PA=LU,

其中,PP 是置换矩阵,LL 是下三角矩阵,UU 是上三角矩阵。求解 Ax=bAx=b 时,依次进行以下步骤:

  1. 施加置换,得到 PbPb。
  2. 通过前代法求解 Ly=PbLy=Pb。
  3. 通过回代法求解 Ux=yUx=y。

一旦算出这些分解因子,就可以将其重复用于不同的右端向量,而不必重新进行分解。

QR分解与最小二乘法

对于列向量线性无关的实矩阵 AA,其简化QR分解的形式为

A=QR,A=QR,

其中,QQ 的各列构成标准正交组,RR 为非奇异的上三角方阵。最小二乘法问题

min⁡x∥Ax−b∥2\min_x \|Ax-b\|_2

可化为

Rx=QTb,Rx=Q^{T}b,

再通过回代法求解。对于复矩阵,则以共轭转置代替转置。

Cholesky分解

对于实对称正定矩阵,其Cholesky分解可写为

A=LLT.A=LL^{T}.

求解方程组时,先对 LL 使用前代法,再对 LTL^{T} 使用回代法。

这些方法通过求解三角方程组,而不是显式构造逆矩阵来求解,从而避免了仅需方程组的解时计算逆矩阵所带来的额外工作。

数值精度

在浮点运算中,乘法、减法和除法都会引入舍入误差。不过,通常的回代法具有标准的逐分量后向误差界。在通常的算术模型下,假设未发生上溢或会造成问题的下溢,计算得到的解 x^\widehat{x} 满足

(U+ΔU)x^=b,∣ΔU∣≤γn∣U∣,(U+\Delta U)\widehat{x}=b, \qquad |\Delta U|\leq \gamma_n |U|,

其中,绝对值和不等式均按分量理解,且

γn=nu1−nu.\gamma_n=\frac{nu}{1-nu}.

这里,uu 为单位舍入误差,并假设 nu<1nu<1。这意味着计算结果是某个邻近三角方程组的精确解。

这种形式的数值稳定性并不保证解本身的误差很小。前向精度还取决于 UU 的条件数:病态方程组可能会显著放大微小扰动。

即使最终的数学解可以在所用数值格式中表示,过大的中间值仍可能导致上溢。专门的三角方程组求解程序可以引入缩放来降低这一风险。此外,回代法的稳定性本身并不能说明此前进行的矩阵分解也是稳定的。

奇异方程组与矩形方程组

标准递推公式要求对角元素非零。如果 uii=0u_{ii}=0,就无法用该元素作除数。此时,该方程转而给出相容性条件

0=bi−∑j=i+1nuijxj.0=b_i-\sum_{j=i+1}^{n}u_{ij}x_j.

若右端非零,则该方程与已赋予的变量值不相容;若右端为零,则在这一步中 xix_i 尚不能确定。更前面的方程可能还会施加进一步的约束。

因此,仅凭某个对角元素为零,无法区分方程组是无解还是有无穷多解。处理奇异方程组时,需要利用矩阵的秩等信息,识别主元变量、自由变量及相容性条件。

回代法也适用于矩形行阶梯形方程组中的主元方程。先为自由变量赋予参数,再按主元顺序的逆序确定主元变量。

变体与实现

当右端有多个向量时,问题变为

UX=B.UX=B.

可以逐列单独求解,但分块实现能够同时处理多列,并利用高效的矩阵乘法例程。

分块回代法将方程组划分为三角块形式。例如,

(U11U120U22)(x1x2)=(b1b2)\begin{pmatrix} U_{11}&U_{12}\\ 0&U_{22} \end{pmatrix} \begin{pmatrix} x_1\\x_2 \end{pmatrix} = \begin{pmatrix} b_1\\b_2 \end{pmatrix}

先求解 x2x_2,再求解 x1x_1:

U22x2=b2,U11x1=b1−U12x2.U_{22}x_2=b_2, \qquad U_{11}x_1=b_1-U_{12}x_2.

普通标量算法中,相继求解的未知数之间存在顺序依赖。这限制了直接采用并行计算的可能性,不过,分块更新、多个右端向量以及稀疏依赖结构中彼此独立的部分,仍可提供可并行执行的工作。