Back Substitution(回代法)是求解上三角线性方程组的一种经典数值方法。当一个线性系统通过高斯消元法或其他方式被转化为上三角形式后,即可使用回代法从最后一个方程开始,逐个求解未知变量。
一个 n 元线性方程组若其系数矩阵为上三角矩阵(即主对角线下方元素全为零),则形式如下:
a₁₁x₁ + a₁₂x₂ + … + a₁ₙxₙ = b₁
a₂₂x₂ + … + a₂ₙxₙ = b₂
⋱
aₙₙxₙ = bₙ
for i from n downto 1:
x[i] = b[i]
for j from i+1 to n:
x[i] = x[i] - A[i][j] * x[j]
x[i] = x[i] / A[i][i]
Back Substitution 常用于以下场景: