How are Linear Algebraic Equations Solved?

Part 2

The “Elimination and Back Substitution” method discussed in Part 1 is a good pencil-and-paper way to solve a small system of linear equation (up to 3 or 4 or so).  It also is the basis for a more sophisticated method which has been used historically a great deal on computers.  It is called the LU Decomposition Method (abbreviated as just LU).  The motivation for this method originally was to enable solving several different versions of a linear equation system that only differ in the data on the “right-hand-side”.  That is, the matrix of coefficients on the left is unchanged.

Here is the idea for solving with LU is to call a math library to decompose our matrix into an LU form, then “easily” compute the solution using two phases of substitution like back substitution.  This sounds like cheating, right?  If the computer is going to do the LU decomposition, then why not just let it finish the job?  The answer is that we will do just that, but you need to understand some of these fundamentals before you will understand the more complicated calculations the computer will do later.

So what is an LU decomposition?  Given a (square) matrix A, we get back three matrices from the decomposition:

A = P *L * U

where

P is a permutation matrix.  This means it is an identity matrix with the rows scrambled.  That all it is. It captures the effect of the algorithm deciding that a different row than the first is the best to begin with, or similar later decisions.

L is a “lower triangular” matrix:  that is, one with all elements above the diagonal set to zero.

U is an “upper triangular” matrix: :  that is, one with all elements below the diagonal set to zero.  Note how similar this idea is to the first stage of the EBS method we did in Part 1: we began by changing the equations until all the elements below the diagonal were zero.

In our case, for this system we have:

1*x + 2 *y + 3*z = 14

2*x + 2*y + 3*z = 15

1*x – 2*y + 2*z  = 3

and the corresponding matrix problem, A*X=B has

A=

 1 2 3 2 2 3 1 -2 2

and B=

 14 15 3

The LU (or PLU) decomposition of A is

P =

 0 0 1 1 0 0 0 1 0

L=

 1 0 0 0.5 1 0 0.5 -1/3 1

U=

 2 2 3 0 -3 .5 0 0 5/3

If you multiply L times U (please do that) you get back the A matrix except the rows are misordered.  If you then that matrix by P (with P on the left), you get back A exactly.

Forward and Back Substitution

Now lets see how we can solve the equations.

We have

A*X = B

Or

P*L*U*X = B

First, we get rid of P but multiplying through by its inverse.  The inverse of a permutation matrix is just is transpose, so this is easy:

PT*P*L*U*X = PT*B

Or

L*U*X = PT*B

Now  PT*B is just B with its rows rearranged.  It is easy to calculate PT*B.  It is

 15 3 14

Let’s reorganize this last equation slightly by grouping some terms.  We get

L*(U*X) = (PT*B)

It is not really necessary, but it can help us think about the problem if we relabel the terms like this:

L*XU = BP  where we have used XU  to stand for U*X, and BP for PT*B.

Remember that in the previous tutorial we realized that any system of the form LX=B or UX=B is really easy to solve by starting with the equation with only one non-zero coefficient and substituting that value forward (for L) or backward (for U).  So solving L*XU = BP  is easy.  That gives us the result for XU.   That is, we now know that

U*X = XU

where we have numbers for all the coefficients in U and XU.    This system is easy to solve too by back substitution.  So now we have the desired solution, X.

So that is how you solve a (square) linear equation system if you have an LU decomposition of the matrix of coefficients.