Gaussian elimination: Encyclopedia II - Gaussian elimination - Example

Gaussian elimination - Example

Suppose you need to find numbers x, y, and z such that the following three equations are all simultaneously true:

This is called a system of linear equations for the unknowns x, y, and z. They are called linear because each term is either constant or is a constant times a single variable to the first power. The goal is to transform this system to an equivalent one so that we can easily read off the solution. The operations to transform a system of equations to another, whilst still preserving the solutions are as follows:

• multiply or divide an equation by a non-zero number
• switch two equations
• add or subtract a (not necessarily integer) multiple of one equation to another one

The strategy is as follows: eliminate x from all but the first equation, eliminate y from all but the second equation, and then eliminate z from all but the third equation.

In our example, we eliminate x from the second equation by adding 3/2 times the first equation to the second, and then we eliminate x from the third equation by adding the first equation to the third. The result is:

Now we eliminate y from the first equation by adding −2 times the second equation to the first, and then we eliminate y from the third equation by adding −4 times the second equation to the third:

Finally, we eliminate z from the first equation by adding −2 times the third equation to the first, and then we eliminate z from the second equation by adding 0.5 times the third equation to the second:

We can now read off the solution by dividing: x = 2, y = 3 and z = −1.

This algorithm works generally, also for bigger systems. Sometimes it is necessary to switch two equations: for instance if y had not occurred in the second equation after our first step above, we would have switched the second and third equation and then eliminated y from the first equation. It is possible that the algorithm gets "stuck": for instance if y had not occurred in the second and the third equation after our first step above. In this case, the system does not have a unique solution.

Usually, in practice, one does not deal with the actual systems in terms of equations but instead makes use of the coefficient matrix (which is also suitable for computer manipulations), so doing this, our original system would then look like

and in the end we are left with

or, after dividing the rows by 2, 1/2 and −1, respectively:

In this case we apply matrix operations equivalent to the equation operations, namely:

• Multiply or divide a row by a non-zero value.
• Switch two rows.
• Add or subtract a (not necessarily integer) multiple of one row to another row.

Adapted from the Wikipedia article "Example", under the G.N U Free Docmentation License. Please also see http://en.wikipedia.org/wiki