# LU-decomposition

• Feb 14th 2011, 12:16 AM
Swlabr
LU-decomposition
The LU-decomposition of a matrix A can be used to solve the system of equations Ax=v for the vector x. But...why would you do this? Is it more computationally effective? Or is the reason more subtle than that?...
• Feb 14th 2011, 01:32 AM
FernandoRevilla
Suppose for example \$\displaystyle Ax=v\$ with \$\displaystyle A\$ invertible and you know \$\displaystyle L\$ and \$\displaystyle U\$. The system \$\displaystyle Ly=v\$ is triangular and let \$\displaystyle y_0\$ be its solution. The system \$\displaystyle Ux=y_0\$ is also triangular and let \$\displaystyle x_0\$ be its solution. Then, \$\displaystyle Ax_0=L(Ux_0)=Ly_0=v\$ . That is, we have solved \$\displaystyle Ax=v\$ by means of two triangular systems.

Fernando Revilla
• Feb 14th 2011, 02:06 AM
Swlabr
Quote:

Originally Posted by FernandoRevilla
Suppose for example \$\displaystyle Ax=v\$ with \$\displaystyle A\$ invertible and you know \$\displaystyle L\$ and \$\displaystyle U\$. The system \$\displaystyle Ly=v\$ is triangular and let \$\displaystyle y_0\$ be its solution. The system \$\displaystyle Ux=y_0\$ is also triangular and let \$\displaystyle x_0\$ be its solution. Then, \$\displaystyle Ax_0=L(Ux_0)=Ly_0=v\$ . That is, we have solved \$\displaystyle Ax=v\$ by means of two triangular systems.

Fernando Revilla

Yes, I know this. My question, however, is why you would bother to do it this way? Why not just triangularize your matrix and go from there?
• Feb 14th 2011, 02:28 AM
Ackbeet
The benefit is more when you have multiple systems of the form \$\displaystyle Ax = b_{k},\$ for multiple \$\displaystyle b_{k}\$'s. Then, once you've done the LU factorization once, solving each system doesn't require any more row reductions, just back substitutions, which are fast. If you were going to solve only one system, then for exact methods, you'd do Gaussian elimination with back substitution, and for iterative methods (such as with very large, sparse matrices), you'd do something fancy like Gauss-Seidel (but more advanced).