What is LU factorization?

What is the most motivating way to introduce LU factorization of a matrix? I am looking for an example or explanation which has a real impact.

-

• Exact method for solving $Ax=b$.
• Solving multiple RHS?
• (Incomplete) Preconditioning of Krylov Subspace methods?
-

I would say, solving systems of linear equations $Ax=b$. Decomposing $A=P^{-1}LU$, where $P$ is a permutation matrix, $L$ is a lower triangular matrix, and $U$ is an upper triangular matrix, we then have $LUx=Pb$, and this is solveable by forward-backward substitution.

Also, it is used for calculating the determinant of a matrix: $\det(A)=\det(P^{-1})\det(L)\det(U)$. The determinant of $\det(P^{-1})=\det P=(-1)^s$, where $s$ is the number of permutations (=entries out of the diagonal). The determinants $\det(L)$ and $\det(U)$ are just the product of the diagonal entries, $\det(L)=\prod_i l_{ii}$ and $\det(U)=\prod_i u_{ii}$ of the matrix.

And on applications: Whenever you have a multiple number of unknowns, you may search for linear relations between them, in order to solve for several or all the unknowns. Like when you have a number of apples $x$ and pears $y$, and you don't know how many, but you know several constraints (total number of fruits and total price, knowing what a single fruit costs) you can eventually state this as a system of linear equations and solve for $x$ and $y$.

-
Thanks very much for all the detailed and appealing answers. – matqkks Nov 28 '12 at 22:19

First, solving linear systems of equations is one of the most fundamental tasks in applied mathematics. Not only are many mathematical models in the applied sciences linear (Leontief model, Kirchhoff model, reaction stoichiometry), but almost all other numerical methods (e.g., for solving partial differential equations or Newton's method) are based on a reduction to systems of linear equations.

If the size of the linear system is not too large, this can be done (up to rounding errors) exactly using a direct method. The most famous is Gaussian elimination, which should be familiar from school. If you write down the procedure for Gaussian elimination in a form that can be implemented on a computer (you wouldn't want to apply elimination for a $100\times100$ matrix by hand), you end up precisely with the LU factorization algorithm. Additionally, the matrix formulation $A=LU$ allows you to apply techniques from linear algebra to prove things about the LU factorization.

An explanation with a focus on application can be found in Gilbert Strang's book Linear Algebra (especially Chapter 2.6).

-