Gaussian Elimination = LU factorization

Contents

  1. Gaussian Elimination
  2. Gaussian elimination with an augmented matrix
  3. LU factorization
  4. Forward Substitution
  5. Solving the Linear System

Gaussian Elimination

In Figure 1 we illustrate how Gaussian Elimination is used to transform a linear system of three equations in three unknowns into an upper triangular system by considering the problem

This leaves the upper triangular system

which is easier to solve, via backward substitution to be discussed later.

Gaussian elimination with an augmented matrix

In Figure 2 we show how it is not necessary to write down the entire linear equations: it suffices to perform Gaussian elimination on the matrix of coefficients, augmented by the right-hand side.

LU factorization

Next, let us consider the computation of the LU factorization of a square matrix. We will ignore for now when this computation can be computed, and focus on the computation itself.

Given $ A \in \Snxn $, its LU factorization is given by $ A = L U $, where $ L \in \Snxn $ is unit lower triangular (it has ones on the diagonal) and $ U \in \Snxn $ is upper triangular. We will derive an algorithm for computing this operation by partitioning

where we use our usual notation that lower-case Greek letter denote scalars, lower-case Roman letters vectors, and upper-case Roman letters matrices.

Now, $A = L U $ implies

so that

or

This suggests the following steps for overwriting a matrix $ A $ with its LU factorization:

This will leave $ U $ in the upper triangular part of $ A $ and the strictly lower triangular part of $ L $ in the strictly lower triangular part of $ A $. (Notice that the diagonal elements of $ L $ need not be stored, since they are known to equal one.)

This algorithm is presented as an iteration using our notation in

It is illustrated for the coefficient matrix from Figure 1 in Figure 4. Examination of the computations in Figure 2 and Figure 4 highlights how Gaussian elimination and LU factorization require the some computations on the coefficient matrix.

Forward Substitution

It is often the case that the coefficient matrix for the linear system is available {\em a priori} and the right-hand side becomes available later. In this case, one may want to perform Gaussian elimination or, equivalently, LU factorization on the coefficient matrix. In

we illustrate that if the multipliers are stored, typically over the elements that were zeroed when a multiplier was used, then the computations that were performed during Gaussian Elimination can be applied {\em a postiori}, once the right-hand side becomes available. This process is often referred to as {\em forward substitution}.

Next, we show how forward substitution is the same as solving the linear system $ L z = b $ where $ b $ is the right-hand side and $ L $ is the matrix that resulted from the LU factorization (and is thus unit lower triangular, with the multipliers from Gaussian Elimination stored below the diagonal).

Given unit lower triangular matrix $ L \in \Snxn $ and vectors $ z, b \in \Sn $, consider the equation $ L z = b $ where $ L $ and $ b $ are known and $ z $ is to be computed. Partition

Now, $L z = b $ implies

so that

or

This suggests the following steps for overwriting the vector $ b $ with the solution vector $ z $:

This algorithm is presented as an iteration using our notation in Figure 7. It is illustrated for the matrix $ L $ that results from Equation (\ref{eqn:example1}) in Figure 6. Examination of the computations in Figure 5 and Figure 6 highlights how forward substitution and the solution of $ L z = b $ are related.

Solving the Linear System

What we have seen is that Gaussian Elimination can be used to convert a linear system into an upper triangular linear system, which can then be solved. We also showed that computing the LU factorization of a matrix is the same as performing Gaussian Elimination on the matrix of coefficient. Finally, we showed that forward substitution is equivalent to solving $ L z = b $, where $ L $ is the unit lower triangular matrix that results from the LU factorization. We can now show how the solution of the linear system can computed using the LU factorization.

Let $ A = L U $ and assume that $ A x = b $, where $ A $ and $ b $ are given. Then $ ( L U ) x = b $ or $ L ( U x ) = b $. Let us introduce a dummy vector $ z = U x $. Then $ L z = b $ and $ z $ can be computed as described in the previous section. Once $ z $ has been computed, $ x $ can be computed by solving $ U x = z $ where now $ U $ and $ z $ are known.

LinearAlgebraWiki: GEvsLU (last edited 2007-01-31 02:47:48 by RobertVanDeGeijn)