Department of Applied Mathematics and Theoretical Physics

Numerical Analysis Course

LU Factorisation

The LU factorisation of a square matrix $A$ is its decomposition as the product $LU$ where the matrix $L$ is lower triangular and the matrix $U$ is upper triangular.

Note that the LU factorisation of a given matrix $A$ is not unique (but it can be made so by requiring, for example, that the diagonal entries of $L$ are 1).

Not all matrices have an LU decomposition, if we do not allow pivoting. However, if the matrix is non-singular, it always has an LUP decomposition (LU with pivoting - where $P$ is a permutation matrix).

Contents

Theory

The LU factorisation without pivoting can be implemented as follows:

1. Set $A_0 = A$

2. For all $k = 1, ... ,n$, set $u_k^{\top}$ to the $k^\mathrm{th}$ row of $A_{k-1}$, and set $l_k$ to the $k^\mathrm{th}$ column of $A_{k-1}$, scaled so that $L_{k,k} = 1$.

3. Set $A_k = A_{k-1} - l_k u_k^{\top}$.

4. Increment $k$ by one, and go back to step 2.

In the above, $n$ is the dimension of $A$, the $l_k$ are the columns of $L$ and the $u_k^{\top}$ are the rows of $U$.

Aim

The aim of this GUI is to illustrate LU factorisation without pivoting.

The GUI

Running the downloadable MATLAB® code on this page opens a GUI which demonstrates the LU algorithm without pivoting.

IB_LU_GUI

Interface

You can enter any square matrix you like. If you want to just see the structure of the matrices (black square for non-zero entries and white square for zero entries), you can click on the 'Structure only' radio button. The GUI shows by default both the structure and the values of the entries. Notice that if your matrix or its entries are large, it is advisable to switch to the 'structure only' mode. As soon as you enter a matrix, it will appear as your current $A_k$.

To start the LU algorithm, click on the 'Next' push button. You will see the new $L$, the new $U$ and the new $A_k$. To keep track of the current row (or equivalently column), there is a display to the right of the 'Next' push button. Keep going until the algorithm terminates (when the string 'Finished!' appears). To start a new iteration, input another matrix.

Note: if the matrix entered does not have an LU factorisation without pivoting, a warning message will appear at the problematic stage and the algorithm will stop.

Try, for example, the matrix:

[1 1 1; 1 1 2; 1 2 1];

To close the GUI, click on the 'Close' push button.

Code

All files as zip archive: lu_fac_all.zip