Linear Algebraic Equations

The most efficient method for solving a set of linear algebraic equations is Gaussian elimination, usually arranged as an LU-decomposition of the matrix. Consider the n x n linear system

The Gaussian elimination is done by multiplying one row of the matrix by a constant, adding the result to another row, and the constant is chosen to insure that one of the entries in the second row is then zero. For example, suppose the matrix had a first row of [2 3 6 ...] and a second row of [ ­1 4 5 ...]. If we multiply the first row by 0.5 and add it to the second row, the second row becomes [ 0 5.5 8 ...]. The same thing is done to the right-hand side; then the value of x (the solution) is not changed because we are just adding two equations, both of which are true. The algorithm to do this is shown below, assuming that the diagonal term is always non-zero, and usually large.

At this point, the resulting matrix is triangular: all elements below the diagonal are zero. Then we solve for x by starting at the bottom.

The best way to see what is happening is to look at the elements of A as the process takes place. (movie)

The number of multiplications and divisions necessary is: