Objectives
-
Find and use an LU decomposition of a matrix to solve a linear system.
-
Explore properties related to LU decomposition, including uniqueness, invertibility, and the effect of swapping rows.
Print preview
Worksheet Participate
Triangular coefficient matrix.
Solve the linear systems \(AX=B\) using substitution.
1.
\(A=\begin{bmatrix} 1 \amp 0 \amp 0 \\ 2 \amp 2 \amp 0 \\ -3 \amp 1 \amp -2 \end{bmatrix}\text{,}\) \(B=\begin{bmatrix} 3 \\ 8 \\ -6 \end{bmatrix}\)
2.
\(A=\begin{bmatrix} 2 \amp -2 \amp 3 \\ 0 \amp -1 \amp 4 \\ 0 \amp 0 \amp -5 \end{bmatrix}\text{,}\) \(B=\begin{bmatrix} -8 \\ -10 \\ 10 \end{bmatrix}\)
Would you prefer using elimination or substitution to solve these systems? What if the linear system did not have a triangular coefficient matrix?
3. Products of triangular matrices.
Consider two lower triangular matrices,
\begin{align*}
L_1=\begin{bmatrix} a \amp 0 \amp 0 \\ b \amp c \amp 0 \\ d \amp e \amp f \end{bmatrix}, \amp \amp \amp \amp L_2=\begin{bmatrix} g \amp 0 \amp 0 \\ h \amp i \amp 0 \\ j \amp k \amp l \end{bmatrix} \text{.}
\end{align*}
Calculate the product \(L_1L_2\) (or enough of it) and explain why \(L_1L_2\) is lower triangular.
4. Uniqueness?
In an earlier example, we showed that
\begin{equation*}
\underbrace{\left[\begin{array}{rrr} 1 \amp 0 \amp 2 \\ 1 \amp 1 \amp -1 \\ -3 \amp -1 \amp -7 \end{array}\right]}_A = \underbrace{\left[\begin{array}{rrr} 1 \amp 0 \amp 0 \\ 1 \amp 1 \amp 0 \\ -3 \amp -1 \amp 1 \end{array}\right]}_L\underbrace{\left[\begin{array}{rrr} 1 \amp 0 \amp 2 \\ 0 \amp 1 \amp -3 \\ 0 \amp 0 \amp -4 \end{array}\right]}_U\text{.}
\end{equation*}
Consider a diagonal matrix, \(D=\left[\begin{array}{rrr} 2 \amp 0 \amp 0 \\ 0 \amp -1 \amp 0 \\ 0 \amp 0 \amp 1 \end{array}\right]\text{.}\) Calculate \(LD\) and \(D^{-1}U\text{.}\)
What does \(\big(LD\big)\big(D^{-1}U\big)\) equal? What does this tell you about the uniqueness of LU factorizations?
5.
Solve \(AX=B\) using LU decomposition for
\begin{align*}
A=\begin{bmatrix}
2 \amp -3 \amp 1 \\
-4 \amp 5 \amp 0 \\
2 \amp -2 \amp 2
\end{bmatrix},
\amp \amp B= \begin{bmatrix}8 \\ -13 \\ 8 \end{bmatrix}\text{.}
\end{align*}
6.
Recall we define \(L\) in terms of elementary matrices which are invertible, but all we’ve said about \(U\) is that \(U\) is the result of applying some row operations.
(a)
Suppose \(U=\begin{bmatrix} 1 \amp -1 \\ 0 \amp 0 \end{bmatrix}\text{.}\) Calculate \(A=\begin{bmatrix} 2 \amp 0 \\ 1 \amp 1 \end{bmatrix}\begin{bmatrix} 1 \amp -1 \\ 0 \amp 0 \end{bmatrix}\) and determine whether or not \(A\) is invertible. Will \(LU\) be invertible for any lower triangular matrix \(L\text{?}\)
(b)
Determine whether or not \(A\) is invertible if \(A=\begin{bmatrix} 2 \amp 0 \amp 0\\ 1 \amp 1 \amp 0 \\ -1 \amp 3 \amp 1 \end{bmatrix}\begin{bmatrix} 1 \amp 0 \amp 1 \\ 0 \amp 3 \amp 1 \\ 0 \amp 0 \amp 0 \end{bmatrix}
\text{.}\) Does \(AX=B\) have exactly one solution for any possible \(B\text{?}\)
7.
A matrix obtained from the identity matrix by swapping rows some number of times is called a permutation matrix, and it’s always invertible (perform the same swaps in the reverse order). When computers solve \(AX=B\) they often perform a permutation \(P\) and find an LU decomposition for \(PA\) so that they are solving \(PAX=PB\) by solving \(LUX=PB\text{.}\)
Solve the system in Exercise 5 above again, this time by using Sage to calculate \(P,L\text{,}\) and \(U\text{.}\) Then by hand, calculate \(PB\) and use substitution to solve \(LY=PB\) and \(UX=Y\text{.}\) Verify that you get the same answer you got before.
