Mathematical Methods (10/24.539)

VI. Numerical Solution of Algebraic Equations

Gauss Elimination Method

Basic Algorithm

The Gauss Elimination Method forms the basis for all elimination techniques. The basic idea is to modify the original equations, using legal row operations, to give a simpler form for actual solution. The basic algorithm can be broken into two stages:

1. Forward Elimination (put equations in upper triangular form)

2. Back Substitution (solve for unknown solution vector)

To see how this works, consider the following system of equations:

Now, with reference to this system of N equations and N unknowns, the Forward Elimination Step (with partial pivoting) becomes:

Step 0 -- Create an augmented matrix,

Step 1 -- Determine the coefficient in the ith column with the largest absolute value and interchange rows such that this element is the pivot element (i = 1, 2, 3, to N-1)

Step 2 -- Normalize the pivot equation (i.e. divide by the i,i element)

Step 3 -- Multiply normalized eqn. i by the j,i element of eqn. j

Step 4 -- Subtract the resultant equation in Step 3 from eqn. j

repeat Steps 3 and 4 for j = i+1 to N

go to Step 1 for next i = i+1 to N-1

and the Back Substitution Step is given by:

Step 5 --

Step 6 --

repeat for i = N-1, N-2, to 1

Note: The primes here indicate that the coefficients at this stage are different from the original coefficients.

Example 6.1 illustrates this algorithm for a simple 3x3 system.

10/24.539 Lecture Notes by Dr. J. R. White, UMass-Lowell (updated August 1998).

Return to Online Courses