Due Wed. 9/19 at 10:55am by electronic submission.
For the matrix
$$ A = \begin{pmatrix} 1 & 2 & 1 & -1 & 1 \\ 1 & 0 & 1 & -1 & 0 \\ 1 & 2 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 \\ -1 & 0 & 0 & 0 & 0 \end{pmatrix} $$and the vector $b = \begin{pmatrix} 0\\0\\0\\0\\1 \end{pmatrix}$:
(a) Show hand calculations to compute $x = A^{-1} b$. (Hint: remember what I said in class about computing inverses of matrices.)
(b) Compute $A^{-1}$ in Julia with inv(A)
and compare it to your solution $x$. Explain why your $x$ appears in $A^{-1}$.
A = [ 1 2 1 -1 1
1 0 1 -1 0
1 2 1 0 0
1 1 0 0 0
-1 0 0 0 0]
inv(A)
Consider the matrix $$A = \begin{pmatrix} 1 & 4 & 1 \\ 1 & 2 & -1 \\ 3 & 14 & 6 \end{pmatrix}$$ from lecture 4.
In this problem, we will consider transforming this matrix by a sequence of invertible linear column operations — multiplying columns by scalars and adding/subtracting them.
(a) Come up with column operations that change the first row from $\begin{pmatrix} 1 & 4 & 1\end{pmatrix}$ to $\begin{pmatrix} 1 & 0 & 0\end{pmatrix}$, i.e. that put zeros to the right of the first pivot. Express these operations in terms of multipling $A$ on the left or right by some matrix $E$. Give $E$ and $E^{-1}$.
(Note that your operations must be invertible, like Gaussian-elimination steps — no fair just multipling the second and third columns by zero, since this would lead to a non-invertible $E$.)
(b) If we do a sequence of column operations that transform $A$ into $I$, and then do the same column operations to the $3\times 3$ identity matrix $I$, what is the resulting matrix?
(c) Carry out the process from (b): perform column operations on $A$ that transform it into $I$, and perform the same column operations on $I$. Do them both at once by "augmenting" $A$ in a certain way (maybe not the usual way). Check your result against the lecture-4 notes or with Julia to see that you got the expected result from (b).
A = [1 4 1
1 2 -1
3 14 6]
From Strang, section 2.6: Compute $L$ and $U$ for the following symmetric matrix $A$:
$$ A = \begin{pmatrix} a & a & a & a \\ a & b & b & b \\ a & b & c & c \\ a & b & c & d \end{pmatrix} $$and find four conditions on the numbers $a,b,c,d$ to get $A=LU$ with four pivots.
From Strang, section 2.6. Consider $$L = \begin{pmatrix} 1 & 0 & 0 \\ a & 1 & 0 \\ b & c & 1 \end{pmatrix}$$ for some numbers $a,b,c$.
(a) When you perform the usual Gaussian elimination steps to $L$, what matrix will you obtain?
(b) If you apply the same row operations to $I$, what matrix will you get?
(c) If you apply the same row operations to $LB$ for some $3\times n$ matrix $B$, what will you get?
Consider the following matrices:
$$ U = \begin{pmatrix} 1 & 1 & -1 \\ 0 & 1 & 2 \\ 0 & 0 & 1 \end{pmatrix}, \; L = \begin{pmatrix} 1 & 0 & 0 \\ -1 & 1 & 0 \\ -2 & 1 & 1 \end{pmatrix}, \; B = \begin{pmatrix} 1 & 2 & 3 \\ 3 & 2 & 1 \\ 1 & 0 & 1 \end{pmatrix} $$Let $A = U B^{-1} L$.
(a) Compute the second column of $A^{-1}$. (If you think about it, you can do it without inverting any matrices.)
(b) Check your answer by explicitly computing $A^{-1}$ in Julia.
# fill these in:
U = ...
L = ...
B = ...
A = U * (B \ L) # computes UB⁻¹L
inv(A) # computes A⁻¹
Suppose you have a 5×5 matrix of the form
$$A = \begin{pmatrix} \star & \star & 0 & 0 & 0 \\ \star & \star & \star & 0 & 0 \\ 0 & \star & \star & \star & 0 \\ 0 & 0 & \star & \star & \star \\ 0 & 0 & 0 & \star & \star \end{pmatrix} $$where "$\star$" denotes nonzero entries (not necessarily all the same numbers). This is called a tridiagonal matrix.
The following code constructs a random tridiagonal matrix in Julia, using a special Tridiagonal
type that allows Julia to take advantage of this structure:
A = Tridiagonal(randn(4), randn(5), randn(4))
The inverse of a tridiagonal matrix has no special pattern of nonzero entries in general:
inv(A)
But the LU factorization of a tridiagonal matrix is very special.
(a) Assuming no row swaps are required and the matrix is nonsingular, what pattern of nonzero entries do you generically expect to see in the $L$ and $U$ factors of a matrix $A$ of this form, and why?
Check your answer against your random 5×5 $A$ in Julia.
L, U = lu(A, Val{false})
display(L)
display(U)
(b) If $A$ is an $m \times m$ tridiagonal matrix (i.e. same pattern of zeros, but extended to an arbitrary size), how does the count of scalar arithmetic operations (±,×,÷) to compute the L, U factors (i.e. to perform elimination) scale with $m$? You need not give an exact count, just say whether it is roughtly proportional to $m$, $m^2$, $m^3$, etcetera for large $m$.)
You need not count operations on numbers that are guaranteed to be zero for any tridiagonal matrix. The computer can store just the nonzero entries of the matrix and only operate on those.