Register to reply

LU factorization

Share this thread:
matqkks
#1
Nov28-12, 09:54 AM
P: 153
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.
Phys.Org News Partner Mathematics news on Phys.org
Heat distributions help researchers to understand curved space
Professor quantifies how 'one thing leads to another'
Team announces construction of a formal computer-verified proof of the Kepler conjecture
HallsofIvy
#2
Nov28-12, 07:38 PM
Math
Emeritus
Sci Advisor
Thanks
PF Gold
P: 39,533
One motivation is that it makes solving equations very easy! If A= LU where, of course, L is a "lower diagonal" and U is "upper diagonal", then we can solve Ax= b by writing it as LUx= b so that Ux= y= L[sup]-1[sup]b, which can be done by 'back substitution" and then solving x= U-1y again by back substitution.

For example, if
[tex]A= LU= \begin{bmatrix}2 & 0 \\ 1 & 3\end{bmatrix}\begin{bmatrix}1 & 3 \\ 0 & 2\end{bmatrix}\begin{bmatrix}x_1 \\ x_2 \end{bmatrix}= \begin{bmatrix}2 \\ 1\end{bmatrix}[/tex]
We can let Ux= y so the equation becomes
[tex]Ly= \begin{bmatrix}2 & 0 \\ 1 & 3\end{bmatrix}\begin{bmatrix}y_1 \\ y_2\end{bmatrix}= \begin{bmatrix}2 & 1 \end{bmatrix}[/tex]

The first row is equivalent to the equation [itex]2y_1= 2[/itex] so we have immediately [itex]y_1= 1[/itex]. With that value, the second equation, [itex]y_1+ 3y_2= 1[/itex] becomes [itex]1+ 3y_2= 1[/itex] so that [itex]3y_2= 0[/itex] and [itex]y_2= 0[/itex].

Then, since we defined y to be Ux, we have
[tex]x= \begin{bmatrix} 1 & 3 \\ 0 & 2 \end{bmatrix}\begin{bmatrix}x_1 \\ x_2\end{bmatrix}= \begin{bmatrix}1 \\ 0 \end{bmatrix}[/tex]

Now, the second row gives the equation [itex]2x_2= 0[/itex] so that [itex]x_2= 0[/itex] and then the top row becomes [itex]x_1+ 3x_2= x_1= 1[/itex].
lurflurf
#3
Nov28-12, 09:03 PM
HW Helper
P: 2,264
Much of linear algebra can be seen as factoring operators. Triangular equations are easy to solve so it is helpful to solve an equation by factoring it into two triangular equations. Another views is to thing about solving an equation by a usual method like row reduction. In doing so we throw away a lot of of the matrix, and as a result if we solve many equations with the same operator we needlessly repeat work. We can by slight modification of row reduction keep this information at almost no cost. If we solve the equation many times we can reuse the information each time. This is the LU decomposition.


Register to reply

Related Discussions
QR factorization Calculus & Beyond Homework 1
How do I factorize (x-1)(x-2)(x-3)(x-4) -48 Precalculus Mathematics Homework 7
Factorization of rings problem Calculus & Beyond Homework 2
LU factorization General Math 0
Factorization for x^3 - 4x^2 -x = 0 Calculus & Beyond Homework 7