The Gaussian Elimination with back-substitution is more optimal and less overwhelming that Gaussian Jordan. It uses partial pivoting, i.e. the pivoting is done only using row transforms, as a result the order of the solution and variable vectors remains unchanged. This mitigates the overhead of book-keeping and column swapping.
Let us consider a matrix:
We follow a similar but simpler procedure to the Gaussian Jordan Method.
Step 1: Upper Triangular Matrix
Only the elements below the pivot element are reduced to zero by subtracting the right amount of the “pivot row”.
After iterating over each pivot element we get an upper triangular matrix:
Each in the above equation is shown with a “prime” signifying that the element has changed during the transforms
Step 2: Back-Substitution
The name back-substitution arrives from the fact that that the last equation is a univariable equation and is trivial.
This value can be “back-substituted” into the previous equation to get the value of
which further gives,
The typical back-substitution can be represented with:
Strictly talking in terms of complexity, both Gaussian Jordan Elimination and Gaussian Elimination with back-substitution are algorithms. The latter is more optimal because of the reduction in the amount of operations in the innermost for loops. The difference can be attributed to full pivoting as all rows are reduced as opposed to only a subset of rows (resultant is a triangular matrix) in Gaussian Elimination with back-substitution. This reduces the number of multiplications () and additions () by a factor of 3. We can reduce this factor to 1.5 by avoiding the calculation of the inverse in Gaussian Jordan Elimination.