Home | 18.022 | Chapter 15

Tools    Index    Up    Previous    Next


15.4 Solving Inhomogeneous Equations: Gaussian Elimination

Given a set of equations, there are several operations which can be performed on them that do not affect their content.
They are:

1. Add a multiple of one to another (adding left sides  to left sides and rights to rights.)

Proof

2. Reorder them.

Comment

3. Multiply both sides of any of them by a non-zero number.

These are called elementary row operations.
Solving the equations means finding an equivalent set of equations having a very simple form: each equation has only one variable in it,  its coefficient is 1, and the variable appears alone on the left hand side of the equation. The equation then provides an explicit expression for the corresponding variable.
We solve linear equations by performing a sequence of elementary row operations that transforms the original coefficient matrix into an identity matrix. This procedure is called Gaussian elimination.

Discussion:

1. Suppose we have a 3 by 3 coefficient matrix C, we define the column vector v to have the right side of the jth equation as its jth component, and we let the column vector r have components x, y and z.
Then the linear equations take the form C r = v, where the the left hand side represents the matrix product of the 3 by 3 matrix C and the 3 by 1 matrix r.

2. If the coefficient matrix C is the identity matrix we have a solution: C = I implies C r = I r = r = v.

3. Gaussian elimination is exactly the usual standard method for solving equations, which goes as follows: solve the first equation for any variable that occurs in it in terms of the rest. Use that equation to eliminate that variable from all other equations. Repeat these steps on another equation and variable. Repeat until you have an explicit expression for the last variable. Substitute for that variable in all the equations, eliminating it from them; take the next variable and repeat, until you have an explicit expression for all the variables.

Solving the equation means, apart from rearranging right and left sides, multiplying the equation by a constant to make the coefficient of the associated variable into 1. Eliminating the variable from other equations means adding or subtracting the row corresponding to the equation to the other rows so as to make the coefficient of the variable solved for in that equation into zero, in every other equation. Thus the standard method is Gaussian elimination.

Example