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\]

You have no rights to post comments