## Solving Simultaneous Equations Using LU Decomposition (Cholesky Factorisation)

Any square matrix can be written as a product of upper and lower triangular matrices (LU decomposition). We can use this to solve a system of simultaneous linear equations
$A \mathbf{x} = \mathbf{b}$
.
Consider the system of linear equations:
$2x_1+x_3=4$

$-3x_1+4x_2-2x_3=-3$

$x_1+7x_2-5x_3=6$

In matrix form this system is
$\left( \begin{array}{ccc} 2 & 0 & 1 \\ -3 & 4 & -2 \\ 1 & 7 & -5 \end{array} \right) \begin{pmatrix}x_1\\x_2\\x_3\end{pmatrix} = \begin{pmatrix}4\\-3\\6\end{pmatrix}$
(1)
We factorise the coefficient matrix into the product of a lower and an upper triangular matrix. The factorisation is not unique and we can choose the entries on the main diagonal of the lower triangular matrix to all be 1 for ease of calculation.
$\left( \begin{array}{ccc} 2 & 0 & 1 \\ -3 & 4 & -2 \\ 1 & 7 & -5 \end{array} \right) =\left( \begin{array}{ccc} 1 & 0 & 0 \\ x_1 & 1 & 0 \\ x_2 & x_3 & 1 \end{array} \right) \left( \begin{array}{ccc} y_1 & y_2 & y_3 \\ 0 & y_4 & y_5 \\ 0 & 0 & y_6 \end{array} \right) = \left( \begin{array}{ccc} y_1 & y_2 & y_3 \\ -x_1y_1 & x_1y_2+y_4 & x_1y_3+y_5 \\ x_2y_1 & x_2y_2+x_3y_4 & x_2y_3+x|_3y_5+y_6 \end{array} \right)$

Then
$\left( \begin{array}{ccc} 2 & 0 & 1 \\ -3 & 4 & -2 \\ 1 & 7 & -5 \end{array} \right) = \left( \begin{array}{ccc} y_1 & y_2 & y_3 \\ -x_1y_1 & x_1y_2+y_4 & x_1y_3+y_5 \\ x_2y_1 & x_2y_2+x_3y_4 & x_2y_3+x|_3y_5+y_6 \end{array} \right)$

Identifying coefficients and solving gives
$y_1=2, \: y_2=0, \: y_3=1, \: y_4=4, \: y_5=-1/2, \: y_7=-37/8, x_1=-3/2, \: x_2=1/2, x_3=7/4$
.
Then
$\left( \begin{array}{ccc} 2 & 0 & 1 \\ -3 & 4 & -2 \\ 1 & 7 & -5 \end{array} \right) =\left( \begin{array}{ccc} 1 & 0 & 0 \\ -3/2 & 1 & 0 \\ 1/2 & 7/4 & 1 \end{array} \right) \left( \begin{array}{ccc} 2 & 0 & 1 \\ 0 & 4 & -1/2 \\ 0 & 0 & -37/8 \end{array} \right)$

Now (1) becomes
$\left( \begin{array}{ccc} 1 & 0 & 0 \\ -3/2 & 1 & 0 \\ 1/2 & 7/4 & 1 \end{array} \right) \left( \begin{array}{ccc} 2 & 0 & 1 \\ 0 & 4 & -1/2 \\ 0 & 0 & -37/8 \end{array} \right) \begin{pmatrix}x_1\\x_2\\x_3\end{pmatrix} = \begin{pmatrix}4\\-3\\6\end{pmatrix}$

We can now consider the system
$\left( \begin{array}{ccc} 1 & 0 & 0 \\ -3/2 & 1 & 0 \\ 1/2 & 7/4 & 1 \end{array} \right) \begin{pmatrix}w_1\\w_2\\x_w\end{pmatrix} = \begin{pmatrix}4\\-3\\6\end{pmatrix}$

Solving gives
$w_1=4$

$-3/2w_1+w_2=-3 \rightarrow w_2=-3+3/2w_1=-3+3/2 \times 4=3$

$w_3=6-1/2w_1-7/4w_2=1-1/2 \times 4-7/4 \times 3=-5/4$

Now solve
$\left( \begin{array}{ccc} 2 & 0 & 1 \\ 0 & 4 & 1/2 \\ 0 & 0 & -37/8 \end{array} \right) \begin{pmatrix}x_1\\x_2\\x_3\end{pmatrix} = \begin{pmatrix}4\\3\\-5/4\end{pmatrix}$

$x_3=(-5/4)/(-37/8)=10/37$

$4x_2-1/2x_3=3 \rightarrow x_2=(3+1/2x_2)/4= 29/37$

$2x_1 +x_3=4 \rightarrow x_1=(4-x_3)/2=69/37$