Numerical Methods For Engineering: Linear Algebraic Equations

Gaussian Elimination

One of the most popular techniques for solving simultaneous linear equations is the Gaussian elimination method. The approach is designed to solve a general set of n equations and n unknowns.

Gaussian elimination consists in these two steps:

Forward Elimination of Unknowns:

In the first step of forward elimination, the first unknown, x1 is eliminated from all rows below the first row. The first equation is selected as the pivot equation to eliminate x1. So, to eliminate x1 in the second equation, one multiplies the first equation by a21/a11 to give:

This procedure of eliminating x1, is now repeated for the third equation to the n-th equation to reduce the set of equations as:

This is the end of the first step of forward elimination. Now for the second step of forward elimination, we start with the second equation as the pivot equation and a'22 as the pivot element. So, to eliminate x2 in the third equation, by multiplying the second equation by a'32/a'22 and subtracting it from the third equation. This makes the coefficient of x2 zero in the third equation. The same procedure is now repeated for the fourth equation till the n-th equation to give:

The next steps of forward elimination are conducted by using the third equation as a pivot equation and so on. That is, there will be a total of n-1 steps of forward elimination.

Back Substitution:

Now the equations are solved starting from the last equation as it has only one unknown.

Then the second last equation, that is the (n-1)th equation, has two unknowns: Xn and Xn-1, but Xn is already known. This reduces the (n-1)th equation also to one unknown. Back substitution hence can be represented for all equations by the formula:

*Example Naive Gaussian Elimination: In the next two videos we can see the 2 steps of the method (explained before)

References:

Holistic Numerical Methods Institute - Gaussian Elimination

Gauss-Jordan Elimination

Gauss-Jordan Elimination is a variant of Gaussian Elimination. Again, we are transforming the coefficient matrix into another matrix that is much easier to solve, and the system represented by the new augmented matrix has the same solution set as the original system of linear equations. In Gauss-Jordan Elimination, the goal is to transform the coefficient matrix into a diagonal matrix, and the zeros are introduced into the matrix one column at a time. We work to eliminate the elements both above and below the diagonal element of a given column in one pass through the matrix.

Procedure:

Note: If you're unable to do step 2, stop! the system has either infinite or no solutions

Example:

It is now obvious, by inspection, that the solution to this linear system is x=3, y=1, and z=2. Again, by solution, it is meant the x, y, and z required to satisfy all the equations simultaneously.

References:

http://www.krellinst.org/AiS/textbook/unit2/example_projects/starter/math/matrix/gauss.html

http://ceee.rice.edu/Books/CS/chapter2/linear44.html

LU Descomposition

Another way of solving a system of equations is by using a factorization technique for matrices called LU decompostion. This factorization involves two matrices, one lower triangular matrix and one upper triangular matrix.

How to find an LU decomposition? Hints:

* To get the matrix U, just use row operations until an upper triangular matrix is formed.

* To get L, start with the idenity matrix and use the following rules. Any row operations that involves adding a multiple of one row to another, for example, Ri + kRj, put the value –k in the ith-row, jth-column of the identity matrix. Any row operations that involves getting a leading one on the main diagonal, for example, kRi, put the value 1/k in the position of the identity matrix where the leading one occurs.

Example: (Steps)

Find an LU decomposition of the following matrix.