**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 |

.5 |
1 |
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:

P^{T}*P*L*U*X
= P^{T}*B

Or

L*U*X =
P^{T}*B

Now
P^{T}*B is just B with its rows rearranged. It is easy to calculate P^{T}*B. It is

15 |

3 |

14 |

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

L*(U*X)
= (P^{T}*B)

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

L*X^{U}
= B^{P} where
we have used X^{U } to stand for
U*X, and B^{P }for P^{T}*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*X^{U} = B^{P } is
easy. That gives us the result for X^{U}. That is, we now know that

U*X
= X^{U}

where we
have numbers for all the coefficients in U and X^{U}. 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.