LU decomposition

Skill positionModule 2 of 4 · Topic 2 of 3

2.2 LU decomposition

—Lab score— / 100Total XP—Streak—

Elimination, remembered

Gaussian elimination solves $A\mathbf{x}=\mathbf{b}$ by subtracting multiples of one row from the rows below it until the matrix is upper triangular, $U$ . The multipliers you used are worth keeping: put them below the diagonal of a lower triangular matrix $L$ with ones on the diagonal, and then $A=LU$ . The decomposition records the whole elimination, so the work is done once and reused.

A=LU,\qquad L\mathbf{y}=\mathbf{b},\qquad U\mathbf{x}=\mathbf{y}

(1)

To solve, first $L\mathbf{y}=\mathbf{b}$ by forward substitution (top to bottom), then $U\mathbf{x}=\mathbf{y}$ by back substitution (bottom to top). Each costs about $n^2$ operations, while the factorisation costs about $\tfrac{2}{3}n^3$ . With many right-hand sides (many scenarios on the same matrix) you factor once and pay only $n^2$ per scenario.

An LU by handTake

A=\begin{pmatrix}2&1\\4&5\end{pmatrix}

. The multiplier is

4/2=2

: subtract 2 times row 1 from row 2 to get

U=\begin{pmatrix}2&1\\0&3\end{pmatrix}

, and

L=\begin{pmatrix}1&0\\2&1\end{pmatrix}

. Check:

LU=\begin{pmatrix}2&1\\4&2+3\end{pmatrix}=A

. Solve

A\mathbf{x}=(3,9)

L\mathbf{y}=\mathbf{b}

gives

y_1=3

y_2=9-2\cdot3=3

; then

U\mathbf{x}=\mathbf{y}

gives

x_2=1

2x_1+1=3

, so

\mathbf{x}=(1,1)

$L$ : lower triangular, ones on the diagonal, the elimination multipliers below it.
$U$ : upper triangular, the result of the elimination; its diagonal holds the pivots.
Pivoting: swap rows so the pivot is large, giving $PA=LU$ with a permutation matrix $P$ .

A zero or tiny pivot needs a row swapFor

\begin{pmatrix}0&1\\1&1\end{pmatrix}

the first pivot is 0 and plain elimination divides by zero, yet the matrix is perfectly invertible. Swapping the rows fixes it. A pivot that is tiny rather than zero does not crash, but it produces huge multipliers and wrecks accuracy, so real libraries always pivot.

Lab · what's graded

The matrix L15 pts
The matrix U15 pts
A determinant from U15 pts
Solving with L and U15 pts
Why pivot15 pts
The steps of an LU solve10 pts
Why factor once15 pts

0/ 7 answered

1Matrix · vector15 ptsNot answered

Let $A=\begin{pmatrix}2&1\\4&5\end{pmatrix}$ . Fill in the lower triangular factor $L$ (ones on the diagonal) of $A=LU$ without row swaps.

L =

2Matrix · vector15 ptsNot answered

Let $A=\begin{pmatrix}2&1\\4&5\end{pmatrix}$ . Fill in the upper triangular factor $U$ .

U =

3Numeric answer15 ptsNot answered

The matrix $A=\begin{pmatrix}2&1&1\\4&3&3\\8&7&9\end{pmatrix}$ factors without swaps as $L=\begin{pmatrix}1&0&0\\2&1&0\\4&3&1\end{pmatrix}$ , $U=\begin{pmatrix}2&1&1\\0&1&1\\0&0&2\end{pmatrix}$ . Find $\det A$ .

\det A =

accepted: ± 0.001

4Numeric answer15 ptsNot answered

Let $A=\begin{pmatrix}2&1\\4&5\end{pmatrix}$ . Use $L=\begin{pmatrix}1&0\\2&1\end{pmatrix}$ and $U=\begin{pmatrix}2&1\\0&3\end{pmatrix}$ to solve $A\mathbf{x}=(5,13)$ . What is $x_1$ ?

x_1 =

accepted: ± 0.001

5Choice15 ptsNot answered

What goes wrong if you run plain elimination, with no row swaps, on $\begin{pmatrix}0&1\\1&1\end{pmatrix}$ ?

6Order the steps10 ptsNot answered

Put the steps of solving $A\mathbf{x}=\mathbf{b}$ with a pivoted LU in order.

Drag to reorder, or focus an item, press Space to lift it, the arrow keys to move it and Space to drop it.

1Forward substitution: solve $L\mathbf{y}=P\mathbf{b}$
2Factor $PA=LU$
3Back substitution: solve $U\mathbf{x}=\mathbf{y}$
4Apply the row swaps to the right-hand side: $P\mathbf{b}$

7Explain in words15 ptsNot answered

You must solve $A\mathbf{x}=\mathbf{b}$ for 1,000 different vectors $\mathbf{b}$ with the same $A$ . In two sentences, say how LU helps.

Graded on:The matrix is factored only once and the factors are reusedEach extra right-hand side costs only two cheap triangular solves, about n squared0 / 400 characters

Math modeKeyboard or LaTeX inputTask 1 of 7 · Ctrl ⏎ to check

LU decomposition

Skill positionModule 2 of 4 · Topic 2 of 3

2.2 LU decomposition

—Lab score— / 100Total XP—Streak—

Elimination, remembered

A=LU,\qquad L\mathbf{y}=\mathbf{b},\qquad U\mathbf{x}=\mathbf{y}

(1)

An LU by handTake

A=\begin{pmatrix}2&1\\4&5\end{pmatrix}

. The multiplier is

4/2=2

: subtract 2 times row 1 from row 2 to get

U=\begin{pmatrix}2&1\\0&3\end{pmatrix}

, and

L=\begin{pmatrix}1&0\\2&1\end{pmatrix}

. Check:

LU=\begin{pmatrix}2&1\\4&2+3\end{pmatrix}=A

. Solve

A\mathbf{x}=(3,9)

L\mathbf{y}=\mathbf{b}

gives

y_1=3

y_2=9-2\cdot3=3

; then

U\mathbf{x}=\mathbf{y}

gives

x_2=1

2x_1+1=3

, so

\mathbf{x}=(1,1)

$L$ : lower triangular, ones on the diagonal, the elimination multipliers below it.
$U$ : upper triangular, the result of the elimination; its diagonal holds the pivots.
Pivoting: swap rows so the pivot is large, giving $PA=LU$ with a permutation matrix $P$ .

A zero or tiny pivot needs a row swapFor

\begin{pmatrix}0&1\\1&1\end{pmatrix}

Lab · what's graded

The matrix L15 pts
The matrix U15 pts
A determinant from U15 pts
Solving with L and U15 pts
Why pivot15 pts
The steps of an LU solve10 pts
Why factor once15 pts

0/ 7 answered

1Matrix · vector15 ptsNot answered

Let $A=\begin{pmatrix}2&1\\4&5\end{pmatrix}$ . Fill in the lower triangular factor $L$ (ones on the diagonal) of $A=LU$ without row swaps.

L =

2Matrix · vector15 ptsNot answered

Let $A=\begin{pmatrix}2&1\\4&5\end{pmatrix}$ . Fill in the upper triangular factor $U$ .

U =

3Numeric answer15 ptsNot answered

\det A =

accepted: ± 0.001

4Numeric answer15 ptsNot answered

Let $A=\begin{pmatrix}2&1\\4&5\end{pmatrix}$ . Use $L=\begin{pmatrix}1&0\\2&1\end{pmatrix}$ and $U=\begin{pmatrix}2&1\\0&3\end{pmatrix}$ to solve $A\mathbf{x}=(5,13)$ . What is $x_1$ ?

x_1 =

accepted: ± 0.001

5Choice15 ptsNot answered

What goes wrong if you run plain elimination, with no row swaps, on $\begin{pmatrix}0&1\\1&1\end{pmatrix}$ ?

6Order the steps10 ptsNot answered

Put the steps of solving $A\mathbf{x}=\mathbf{b}$ with a pivoted LU in order.

Drag to reorder, or focus an item, press Space to lift it, the arrow keys to move it and Space to drop it.

1Forward substitution: solve $L\mathbf{y}=P\mathbf{b}$
2Factor $PA=LU$
3Back substitution: solve $U\mathbf{x}=\mathbf{y}$
4Apply the row swaps to the right-hand side: $P\mathbf{b}$

7Explain in words15 ptsNot answered

You must solve $A\mathbf{x}=\mathbf{b}$ for 1,000 different vectors $\mathbf{b}$ with the same $A$ . In two sentences, say how LU helps.

Graded on:The matrix is factored only once and the factors are reusedEach extra right-hand side costs only two cheap triangular solves, about n squared0 / 400 characters

Math modeKeyboard or LaTeX inputTask 1 of 7 · Ctrl ⏎ to check

LU decomposition

Elimination, remembered

Lab · what's graded

Log in to run your code.

LU decomposition

Elimination, remembered

Lab · what's graded

Log in to run your code.