Back to the on-screen lesson ·
Storing an elimination as two triangular factors, so that the cubic work is paid once and every further right-hand side costs only two substitutions.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to write the lower and upper factors of a small matrix, solve a system by forward and backward substitution, and say what the factorisation saves over repeated elimination and what it does not change.
You can eliminate a column and you know that elimination costs about $n^{3}$ operations while back substitution costs about $n^{2}$. You have also noticed that the elimination never looks at the right-hand side until it updates it.
$L$ is unit lower triangular: ones on the diagonal, the multipliers below, zeros above. $U$ is upper triangular, and is what the matrix became. Forward substitution solves $Ly = b$ downwards; back substitution solves $Ux = y$ upwards. With pivoting the result is $PA = LU$, and $P$ records the row swaps.
The elimination of a matrix uses nothing about the right-hand side, so it is a waste to repeat it. Store it instead. Every multiplier $m_{ij}$ goes into position $(i,j)$ of a unit lower triangular $L$; what the matrix became is the upper triangular $U$; and $LU = A$ exactly. Solving $Ax = b$ is then two triangular solves: $Ly = b$ forwards, then $Ux = y$ backwards, each costing about $n^{2}$. The arithmetic is identical to plain elimination — $y$ is precisely the right-hand side the elimination would have produced — so nothing about the accuracy changes; what changes is that the cubic part is paid once. For $m$ right-hand sides the cost goes from $m \cdot \tfrac23 n^{3}$ to $\tfrac23 n^{3} + 2mn^{2}$. Pivoting is still required, so what a real solver returns is $PA = LU$ with $P$ recording the swaps, and a new right-hand side must be permuted before it is substituted. And the alternative that looks equivalent — form $A^{-1}$ and multiply — is worse on every count: more work to build, less accurate to apply, and it destroys any sparsity the matrix had.
Another way: steps
Another way: example
$A = \begin{pmatrix} 2 & 1 \\ 6 & 1 \end{pmatrix}$: multiplier $3$, so $L = \begin{pmatrix} 1 & 0 \\ 3 & 1 \end{pmatrix}$ and $U = \begin{pmatrix} 2 & 1 \\ 0 & -2 \end{pmatrix}$. For $b = (3, 5)$: forwards gives $y = (3, -4)$, backwards gives $x_2 = 2$ and then $x_1 = \tfrac12$.
A factorisation is sometimes read as a better method. It is the same method, written down. Every operation, every rounding error and every pivoting decision is what plain elimination would have done; the only difference is that the result is kept. So the accuracy questions do not go away — the factorisation of an ill-conditioned matrix is an ill-conditioned factorisation, and a small residual after two substitutions means no more than it did before.
Forward substitution gives $y_2 = b_2 - m_{21}b_1$.
One multiplier, one subtraction.
That is exactly what the elimination did to the right-hand side.
Same arithmetic, replayed.
So the factorisation stores the elimination's instructions, and the substitutions carry them out on demand.
Nothing is recomputed.
Forming $A^{-1}$ means solving $n$ systems, so it costs more than one factorisation.
More work up front.
Applying it costs $n^{2}$ — the same as two substitutions — but with a worse error bound.
No saving, worse accuracy.
And a sparse matrix has a dense inverse, so the storage can go from linear to quadratic.
The habit to avoid entirely.
The multiplier is $\tfrac84 = 2$.
So $L$ has $2$ below the diagonal, and $U$ has second row $0$ and $7 - 2 \times 3 = 1$.
Checking: $2 \times 4 = 8$ and $2 \times 3 + 1 = 7$, so the product is the original.
Eliminating in $\begin{pmatrix} 4 & -2 \\ 8 & 1 \end{pmatrix}$ uses the multiplier $2$. Write the lower factor $L$.
This task has no paper form; do it on a device.
For the same matrix $\begin{pmatrix} 1 & -2 \\ 3 & -4 \end{pmatrix}$ with multiplier $3$, write the upper factor $U$.
This task has no paper form; do it on a device.
The same $118 \times 118$ matrix must be solved against $15$ different right-hand sides. Why factor it rather than eliminate $15$ times?
A matrix has been factored and $20$ right-hand sides are waiting. Put the five steps of dealing with one of them into order.
Number the steps in order (write the number in the box):
A factorisation of an $37 \times 37$ matrix costs $37^{3}$ units of work, and each pair of substitutions costs $37^{2}$. What does it cost altogether to solve against $10$ right-hand sides?
Answer:
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
With $L = \begin{pmatrix} 1 & 0 \\ 2 & 1 \end{pmatrix}$, $U = \begin{pmatrix} 4 & 4 \\ 0 & -8 \end{pmatrix}$ and right-hand side $(-28, -32)$, fill in the intermediate vector and then the solution.
| Value | |
|---|---|
| Intermediate, first entry | |
| Intermediate, second entry | |
| Solution, second entry | |
| Solution, first entry |
You can produce both factors and solve with them by substitution. Say in your own words why a second right-hand side is so much cheaper than the first.
8. Your turn: the factors of $\begin{pmatrix} 4 & 3 \\ 8 & 7 \end{pmatrix}$, step 3