next up previous
Next: Implementation Up: Elimination Previous: Elimination

Gaussian Elimination

Let us turn to the general problem (1.1):

If , we can eliminate the unknown from each of the succeeding equations. A typical step is to subtract from equation i the multiple of the first equation. The results will be denoted with a superscript 2 . The step is carried out by first forming

and then forming

and

The multiple of the first equation is chosen to make , that is, to eliminate the unknown from equation i . Doing this for each we arrive at the system

Notice that if we start out with A stored in a C or FORTRAN array, we can save a considerable amount of storage by overwriting the with the as they are created. Also, we can save the multipliers in the space formerly occupied by the entries of A and just remember that all the elements below the diagonal in the first column are really zero after elimination. Later we shall see why it is useful to save the multipliers. Similarly the original vector b can be overwritten with the as they are formed.

Now we set the first equation aside and eliminate from equations in the same way. If , then for we first form

and then

and

This results in

As before, we set the first two equations aside and eliminate from equations . This can be done as long as . The elements are called pivot elements or simply pivots. Clearly, the process can be continued as long as no pivot vanishes. Assuming this to be the case, we finally arrive at

 

In the computer the elements of the original matrix A are successively overwritten by the as they are formed, and the multipliers are saved in the places corresponding to the variables eliminated. The process of reducing the system of equations (1.1) to the form (1.11) is called (forward) elimination. The result is a system with a kind of coefficient matrix called upper triangular. An upper triangular matrix is one for which

It is easy to solve a system of equations (1.11) with an upper triangular matrix by a process known as back substitution. If , we solve the last equation for

Using the known value of , we then solve equation n - 1 for , and so forth. A typical step is to solve equation k ,

for using the previously computed :

The only way this process can break down (in principle) is if a pivot element is zero. The objective of this lesson is to exercise the array constructs in the language. Therefore, the other important considerations will be avoided.

The algorithm for elimination is quite compact:
 


next up previous
Next: Implementation Up: Elimination Previous: Elimination


J. C. Diaz