LU Factorization

Main idea

Row reduction does the same work no matter what $\vec b$ is, so do it once and save it as $A = LU$ : $U$ is the echelon form, and $L$ remembers the multipliers you used. After that, every new $\vec b$ costs only two quick triangular solves.

A = {\htmlData{sym=0}{L}}{\htmlData{sym=1}{U}}, \qquad {\htmlData{sym=0}{L}}\vec y = \vec b, \qquad {\htmlData{sym=1}{U}}\vec x = \vec y

What the symbols mean

$L$
Lower triangular
1s on the diagonal, the row-reduction multipliers below it.
$U$
Upper triangular
The echelon form of A.

Explanation

An LU factorization is simply row reduction written down so you never have to redo it. The letters stand for "lower" and "upper": $L$ is lower triangular (all zeros above the diagonal) and $U$ is upper triangular (all zeros below it). It's good whenever you have to solve the same system over and over with different right-hand sides, which happens all the time in simulations. The three equations $A = LU$ , $L\vec y = \vec b$ , $U\vec x = \vec y$ just say: split $A$ into two triangular pieces, then solve with one piece and then the other. Triangular systems are the easy kind you solve one line at a time, so it's less work than it looks.

Why bother? Row reducing costs about $\frac23n^3$ operations, but each triangular solve costs only about $n^2$ . Notice that the elimination steps only depend on $A$ , never on $\vec b$ . So if you need to solve $A\vec x = \vec b$ for many different $\vec b$ (common in engineering), it makes sense to factor once and reuse.

Building it. Row reduce $A$ to $U$ using only "add a multiple of a row above." If you subtract $m$ times row $j$ from row $i$ , put $m$ in position $(i, j)$ of $L$ . That's the whole bookkeeping: $L$ is a record of what you did.

Solving. Forward-substitute $L\vec y = \vec b$ from the top, then back-substitute $U\vec x = \vec y$ from the bottom. The second half is exactly the back substitution you already do at the end of row reduction.

A common mistake. It's tempting to put $-m$ in $L$ , since you subtracted $m$ times the row. It's $+m$ : $L$ has to undo the elimination to rebuild $A$ , and undoing "subtract $m$ times row $j$ " means adding it back.

See it

The running cost of solving Ax = b for more and more right-hand sides with a 100×100 matrix. Redoing elimination every time costs about n³/3 ≈ 333,000 operations per solve, so after 50 solves you're near 17 million. Factoring A = LU once and then doing two triangular solves per b (about n² = 10,000 operations) stays under a million. That's why simulations factor first.

Worked examples

Example 1

Factor $A = \begin{bmatrix}2 & 1\\ 4 & 5\end{bmatrix}$ .

1
To clear the $4$ under the first pivot, subtract 2 × row 1 from row 2. That leaves $U = \begin{bmatrix}2 & 1\\ 0 & 3\end{bmatrix}$ .

Practice

Type your answer and check it. Solve them all to complete the lesson.

Problem 1+5 XP

Give $U$ for $A = \begin{bmatrix}2 & 1\\ 4 & 5\end{bmatrix}$ , row by row.

Problem 2+5 XP

Give $L$ , row by row.

Problem 3+5 XP

Solve $L\vec y = \binom39$ .

Problem 4+5 XP

Now solve $U\vec x = \vec y = \binom33$ .

Problem 5+5 XP

What is the main advantage of LU factorization?

Problem 6+5 XP

A bridge model solves $A\vec x = \vec b$ for many load vectors with $A = \begin{bmatrix}2 & 1\\ 4 & 5\end{bmatrix} = LU$ , where $L = \begin{bmatrix}1 & 0\\ 2 & 1\end{bmatrix}$ and $U = \begin{bmatrix}2 & 1\\ 0 & 3\end{bmatrix}$ . Solve it for $\vec b = \binom18$ .

Challenge problem+25 XP

The hardest one here. Get it, and you've got this lesson.

Find the LU factorization of $A = \begin{bmatrix}1 & 2 & 0\\ 2 & 5 & 3\\ 0 & 1 & 4\end{bmatrix}$ and give $U$ , row by row.

Where it's used

Circuit simulators and structural analysis software factor their huge (sparse) matrices once, then solve for many load cases or time steps.

Solving a Circuit with Two EquationsLin Alg · Electrical Engineering

The Invertible Matrix Theorem Subspaces of Rⁿ