User:Djmvfb/cs228/LU-Decomposition of aMatrix

Suppose that, for matrices AX=B, the coefficient matrix A can be written as the product of a lower triangular matrix and an upper triangular matrix. I.E.

$\mathbf {A} =\mathbf {LU} ={\begin{bmatrix}1&0&0&0&\cdots &0\\m_{21}&1&0&0&\cdots &0\\m_{31}&m_{32}&1&0&\cdots &0\\\vdots &\vdots &\vdots &\vdots &\ddots &\vdots \\m_{n1}&m_{n2}&m_{n3}&m_{n4}&\cdots &1\end{bmatrix}}*{\begin{bmatrix}n_{11}&n_{12}&n_{13}&\cdots &n_{1n}\\0&n_{22}&n_{23}&\cdots &n_{2n}\\0&0&n_{33}&\cdots &n_{3n}\\\vdots &\vdots &\vdots &\ddots &\vdots \\0&0&0&\cdots &n_{mn}\end{bmatrix}}$

Suppose we can do this above (Matrix multiplication is a tricky subject, kids).
Then the solution of the system can proceed as:

${\begin{array}{lcl}\mathbf {AX} &=&\mathbf {B} \\\mathbf {(LU)X} &=&\mathbf {B} \\\mathbf {L(UX)} &=&\mathbf {B} \\\end{array}}$

Let Y=UX.
Thus,

$\mathbf {LY} =\mathbf {B} \ {\mbox{ for }}\ \mathbf {Y} ={\begin{bmatrix}y_{1}\\\vdots \\y_{n}\end{bmatrix}}$

But! Solving LY=B is solving a system in reducing form -- solving it only involves back substitution. This requires a computation complexity of $O(n^{2})$.
To solve this system, we are looking at a computational complexity:

$O(x^{3})+O(n^{2})=O(n^{3})$

There really is not much gain in efficiency with one system solved, however the efficiency for many systems is quite efficient.

So we need to solve for Y in LY=B. Is that what we wanted? No! We want X!
But Y=UX or UX=Y.
So, we know U and Y. U is the upper triangular. Its a breeze with back-substitution.