Say you've got this ridiculously large system of equations that you need to solve. Well, you might try to sit down and do it by hand. After the first ten pages of paper, you'll come to the realization that computers are really good at computing things. Maybe it'd be easier to just whip up some code to do it for you. There's always MATLAB, but why not reinvent the wheel?
First, take all your equations and represent them as the matrix A. Next, take the solutions to these equations and represent them as the column vector b. The x values will be represented by the column vector x. This is the familiar form Ax = b.
The first step in solving the system is getting the A matrix into upper triangular form. You can do this via Gaussian Elimination (or Givens rotations, or a variety of other methods). I'll produce methods for doing those sorts of things eventually. Now having your upper triangular matrix A and a modified form of b, we can get to the back substitution.
But what exactly is back substitution? Well first, we should take a look at an example system of equations. Say you've reduced a 4x4 matrix into upper triangular form like so:
| 1 2 3 4 |
| 0 5 6 7 |
| 0 0 8 9 |
| 0 0 0 10 |
This represents the system:
x1 + 2x2 + 3x3 + 4x4 = b1
5x2 + 6x3 + 7x4 = b2
8x3 + 9x4 = b3
10x4 = b4
You'll notice that there's four equations and four unknows. This is a good thing. You may also notice that it is quite easy to solve for x4 - just divide b4 by 10 and you'll have it. So now we've got one of the unknowns solved for. Then take this x4 and substitute it back into all the other equations (hence the name).
Now, x3 is easy to solve for: subtract b3 - 9x4 and divide that by 8. And now you've got x3. Substitute that into all the other equations and keep going. This is a very easy algorithm to code. Here's pseudocode for it. Translate it into your language of your choosing.
loop i = n ... 1 /* a loop on the rows of A */
loop j = i+1 ... n /* loop on columns */
bi -= aij * xj
endloop
xi = bi/aii
endloop
What about a brief analysis of back substitution? Sure, I can do that. First off, the number of operations for back substitution is as follows: n divisions, (n-1)n/2 multiplications, and (n-1)n/2 additions & subtractions. The time required using one processor is O(n^2). If we've got a whole bunch of processors (the same number as the number of equations), we can reduce this to O(n).
Back substitution is a relatively slow process. It's a fan-in algorithm, which means we are essentially solving things in a binary tree-like structure. This isn't particularly fast, and it does not parallelize well either. Luckily, there are other methods which are faster.
| 
