LU factorization

[matqkks]

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.

 

[Ackbach]

Well, LU is one of the fastest ways computers use to solve linear systems of equations of the form $\mathbf{Ax}=\mathbf{b}$. It's especially useful if you have a lot of RHS's for which you want to find solutions, because once you find L and U, you're off to the races (they don't change for different RHS's).

One good application would be in solving a large circuit. You could easily get 10 or 20 linear equations to solve, and the computer can do that faster than a person, typically.

Solving linear systems is important in modeling parts, like a landing gear for an aircraft, for example. There you'd typically do a Finite Element Analysis, resulting in a large, sparse linear system to solve. For those size problems, you're not going to use an exact method like LU, but methods tailored to sparse matrices.

 

[Fernando Revilla]

The $LU$ factorization is also useful to solve the second order differential system $Bx''=Ax$ with $A,B\in\mathbb{R}^{n\times n}$ symmetric and $B$ positive definite. The $LU$ factorization can be written ($B$ positive definite) as $B=LL^t$ (Choleski's factorization). We can find $C$ such that $A=LCL^t$ ($C=L^{-1}A(L^{-1})^t$).

Being $C$ symmetric, and using the Spectral Theorem we can write $C=PDP^t$ with $P$ orthogonal. The substitutions $y=L^tx$ and $z=P^ty$ transforms $Bx''=Ax$ into a diagonal system $z''=Dz$.