LU factorization

a repository of mathematical know-how

LU factorization

Title: *

Area of mathematics: *

A comma-separated list of areas of mathematics to which this article applies. Use ">" to tag in a subcategory. Example: Analysis > Harmonic analysis, Combinatorics

Keywords:

A comma-separated list of keywords associated with this article. Example: free group

Used in:

A comma-separated list of examples of where this technique is used. Example: Cauchy-Schwarz inequality

Parent articles:		Order

Body:

[QUICK DESCRIPTION]
The LU factorization is perhaps the most common method for solving linear systems of equations.  It is equivalent to Gaussian elimination, but preserves information so that new systems with the same matrix can be solved efficiently.
This factorization has the form
[maths] A = LU [/maths]
where $L$ is lower triangular (that is, $\ell_{ij}=0$ if $j>i$), and $U$ is upper triangular (that is $u_{ij}=0$ if $i>j$).

Usually it is used in a modified form $PA=LU$ where $P$ is a permutation matrix (that is, all entries are zero or one, and only one entry in each row and in each column is non-zero).

[PREREQUISITES]
Linear algebra.

[EXAMPLE comp-LU]
To compute the LU factorization use recursion, which is essentially the algorithmic version of [[induction]].

The $1\times 1$ case is easy: $[a_{11}]=[1]\,[a_{11}]$.

If 
[maths] A = \left[\begin{array}{cc} A_1&b\\ c^T&d \end{array}\right] [/maths]
then we can recursively compute the LU factorization of $A_1=L_1 U_1$.
Then an LU factorization of $A$ can be given by
[maths] A = \left[\begin{array}{cc} L_1 & \\ m^T&1\end{array}\right]
\left[\begin{array}{cc} U_1 & v\\ &w\end{array}\right] [/maths]
where $L_1 v = b$, $m^T U_1 =c^T$, and $m^T v+w = d$, which can all be solved provided $A_1$ is non-singular.

[GENERAL DISCUSSION]
This method can be modified to give a constructive proof of the existence of the LU factorization provided every principal (north-west) square submatrix of $A$ is non-singular.
This recursive construction creates an $L$ matrix with 1's on the diagonal.
It can be easily modified to create a $U$ matrix with 1's on the diagonal.

A different recursive construction can be given where we use the decomposition
[maths] A = \left[\begin{array}{cc} \alpha&\beta^T\\ \gamma&A_1 \end{array}\right]. [/maths]
This gives equivalent computations, but done in a different order.

This is a stub

A stub is an article that is not sufficiently complete to be interesting.

Notifications

File attachments

Changes made to the attachments are not permanent until you save this post. The first "listed" file will be included in RSS feeds.

Attach new file:

Images are larger than 640x480 will be resized. The maximum upload size is 1 MB. Only files with the following extensions may be uploaded: jpg jpeg gif png svg.

Revision information

Log message:

An explanation of the additions or updates being made to help other authors understand your motivations.

LU factorization

Recent articles

Active forum topics

Recent comments