The Back Substitution

When our system is all factorized, we perform the back-substitution. This is trivial, but included for the sake of completeness. Back-substitution of one row in a dense system can be written as

$$x(i) \gets (x(i) - \mathbf{R}(i,i+1:n)b(i+1:n))/\mathbf{R}(i,i)$$ (2.2)

where $x(n) \gets b(n)/\mathbf{R}(n,n)$ is the special case for the last element in $x$, eg. the one we solve for first. Obviously, equation 2.2 requires $2(n-i)+2$ FLOPS, for every element in $x$. This is back-substitution on a dense system. If $b$ or $\mathbf{R}$ turns out to be sparse, we will save some work.