下三角矩阵方程组的运算成本求解疑问

我来帮你把这个向前替换法的运算成本掰碎了说清楚，绝对好懂！

先明确问题场景 #

我们要解的是下三角矩阵方程组 $Tx=b$，其中 $T=(t_{ij})$ 是下三角矩阵，方程组展开后长这样：
$$
\begin{cases}
t_{11}x_1=b_1 \
t_{21}x_1+t_{22}x_2 =b_2\
\vdots \
t_{n1}x_1+t_{n2}x_2+\dots+t_{nn}x_n =b_n\
\end{cases}
$$
换用求和符号写更简洁：$\sum_{j=1}^{i} t_{ij}x_j=b_i, \ i=1,2,\dots,n$

求解这个方程组用的是向前替换法，核心公式是：
$$x_i=(b_i-\sum_{j=1}^{i-1} t_{ij}x_j)/t_{ii}, \ i=1,2,\dots,n$$

逐步骤算每一步的运算量 #

我们挨个看每个$x_i$的计算要用到多少次运算：

• 当$i=1$时：$x_1 = b_1 / t_{11}$，这里只需要1次除法，求和项是空的，所以没乘法和减法。
• 当$i=2$时：先算$t_{21}x_1$（1次乘法），再算$b_2 - t_{21}x_1$（1次减法），最后除以$t_{22}$（1次除法），总共1乘+1减+1除。
• 当$i=k$（$k$从3到$n$）时：先算求和项里的$k-1$个乘积（$k-1$次乘法），再用$b_k$减去这个和（1次减法），最后除以$t_{kk}$（1次除法）。

总运算量汇总 #

现在把所有步骤的运算次数加起来：

乘法总次数 #

从$i=2$到$i=n$，每个$i$对应$i-1$次乘法，加起来就是：
$$1 + 2 + 3 + \dots + (n-1) = \frac{n(n-1)}{2}$$

减法总次数 #

只有$i\geq2$的时候需要减法，一共$n-1$次。

除法总次数 #

每个$x_i$都要做1次除法，从$i=1$到$i=n$，总共$n$次。

如果把乘法和减法算作**浮点运算（Flop）**的话，总浮点运算次数是：
$$\frac{n(n-1)}{2} + (n-1) = \frac{(n+1)(n-1)}{2} = \frac{n^2 -1}{2}$$
当$n$很大的时候，这个数近似于$\frac{n^2}{2}$，这也是向前替换法的渐近复杂度。

内容的提问来源于stack exchange，提问作者Numbermind