三角线性方程求解

形式陈述 ​

三角求解处理线性方程组理路线性方程组System of linear equations可写为矩阵方程 Ax=b 的有限个一次方程系统。 $Lx=b$ 或 $Ux=b$。前代输入非奇异下三角矩阵理路矩阵Matrix以有限行列集合为索引、取值于半环，并以中间指标求和定义乘法的函数。 $L=(l_{ij})$ 与右端 $b$，按 $i=1,\dots ,n$ 计算

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

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

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

在标准浮点模型理路浮点算术标准误差模型Standard floating-point arithmetic model以每次基本运算的小相对扰动和 gamma 记号组织多步浮点误差分析。下，常规前代和回代具有分量后向稳定性：计算结果 $\hat{x}$ 可看成邻近三角系统的精确解，

其中 ${\gamma }_n=nu/(1-nu)$，要求 $nu<1$ 并排除分析范围之外的溢出、下溢。分量界还保留结构零：$t_{ij}=0$ 强制 $\mathrm{\Delta }{t}_{ij}=0$，所以邻近系统仍是三角系统。非零系数的小相对扰动不保证解的每个分量都有小相对误差。完成准则是所有依赖按顺序处理完、未遇到非法主元或非有限值；随后应计算尺度化残差。小残差能否推出小解误差，仍由三角矩阵本身的条件性决定。