三角线性方程求解

形式陈述 ​

前代输入非奇异下三角矩阵 $L=(l_{ij})$ 与右端 $b$，按 $i=1,\dots ,n$ 计算

$$x_i=\frac{b_i-\sum _{j=1}^{i-1}{l}_{ij}{x}_j}{l_{ii}}.$$

回代输入非奇异上三角矩阵 $U=(u_{ij})$，按 $i=n,n-1,\dots ,1$ 计算

$$x_i=\frac{b_i-\sum _{j=i+1}^n{u}_{ij}{x}_j}{u_{ii}}.$$

两种算法的计算图都由三角结构决定：当前未知量只依赖已经求出的分量。输入是矩阵、一个或多个右端及其三角和单位对角约定；输出是解向量，若遇到零对角元则报告奇异，不能继续除法。单位对角时相应除法可以省去。

稠密单右端需要约 $n^2/2$ 次乘加和 $n$ 次除法，渐近成本为 $\mathrm{\Theta }(n^2)$，额外存储可为 $\mathrm{\Theta }(n)$；这不是分解成本之后可以忽略的“免费步骤”。若一次处理 $p$ 个右端，成本为 $\mathrm{\Theta }(n^{2}p)$，分块实现还能把工作组织成更高效的矩阵运算。带宽为 $w$ 的三角矩阵可降为 $\mathrm{\Theta }(nw)$，一般稀疏三角求解则取决于非零模式的依赖图，不能直接套稠密计数。

在标准浮点模型下，常规前代和回代具有分量后向稳定性：计算结果 $\hat{x}$ 可看成邻近三角系统的精确解，

$$(T+\mathrm{\Delta }T)\hat{x}=b,|\mathrm{\Delta }T|\lesssim {\gamma }_n|T|,$$

其中 ${\gamma }_n$ 随维数与 unit roundoff 增长。完成准则是所有依赖按顺序处理完、未遇到非法主元或非有限值；随后应计算尺度化残差。小残差能否推出小解误差，仍由三角矩阵本身的条件性决定。

直觉 ​

一般线性系统里，各未知量彼此缠绕；三角系统已经把这团依赖排成单向链。前代从顶部已知最少的方程向下传播，回代则从底部最后一个未知量向上解开。LU、Cholesky 和 QR 的价值，正是先花较大成本把一般问题改造成若干这样的有序系统。

显式求逆会破坏这份优势。为了得到 $T^{-1}b$ 而先计算整个 $T^{-1}$，相当于对所有单位向量都解一次系统，再只使用其中一个线性组合；它增加计算和存储，也给舍入误差更多传播机会。

例子与边界 ​

取上三角系统

$$\left(\begin{array}{ccc}2& -1& 1\\ 0& 3& 2\\ 0& 0& 4\end{array}\right)\left(\begin{array}{c}{x}_1\\ x_2\\ x_3\end{array}\right)=\left(\begin{array}{c}-1\\ 4\\ -4\end{array}\right).$$

回代先得 $x_3=-1$，再得 $x_2=(4-2x_3)/3=2$，最后

$$x_1=\frac{-1+x_2-x_3}{2}=1.$$

每一步只使用下方已经确定的分量，计算图和公式完全一致。

对角元非零只保证精确算术中存在唯一解，不保证问题良态。若 $T=\mathrm{diag}(1,\epsilon )$、$b=(1,1{)}^{\mathsf{T}}$，则第二个解分量为 $1/\epsilon$；极小对角元会放大右端误差并产生巨大中间量。置换有时能避开不合适的主元，但置换后的三角结构和变量顺序必须一并保存。

稀疏情形还有另一层边界：某些行彼此独立，可以并行；另一些非零模式形成长依赖链，只能顺序推进。仅凭“非零元很少”不能断言三角求解具有同样的并行度。

推论与应用 ​

LU 分解公理库Gaussian 消元与 LU 分解Gaussian elimination · LU factorization · PA equals LU把 Gaussian 消元保存为可复用的带置换 LU 分解，再用三角求解处理一个或多个右端。把求解化成一次前代和一次回代；Cholesky 使用 $L$ 与 $L^{\ast }$；QR 最小二乘最终求解上三角 $R$。多个分解共用本页，是为了让算法页面专注于如何得到因子，而不重复三角求解的更新式、成本与边界。

实现层面应调用成熟的 BLAS/LAPACK 三角求解接口，并明确转置、共轭转置、单位对角和存储布局。即使已有因子，多个右端、内存访问与稀疏依赖仍可能成为总成本的重要部分。

参考资料

• Nicholas J. Higham, Accuracy and Stability of Numerical Algorithms, 2nd ed., SIAM, 2002, Ch. 8.
• Gene H. Golub and Charles F. Van Loan, Matrix Computations, 4th ed., Johns Hopkins University Press, 2013, §3.1.
• LAPACK Users’ Guide, Solving Systems of Linear Equations.