Pre-Midterm Practice Quiz

1. [2 pts]

In float8 (E4M3) the machine epsilon is \(\epsilon_{\mathrm{mach}} = 0.125\). Let

\[ x = 1.0, \qquad e = 0.0625. \]

What is \(x + e\) when computed in float8, and when computed in float16?

  1. float8: \(1.0\); float16: \(1.0625\)
  2. float8: \(1.0\); float16: \(1.0\)
  3. float8: \(1.0625\); float16: \(1.0625\)
  4. float8: \(1.0625\); float16: \(1.0\)

2. [2 pts]

An invertible \(N \times N\) matrix \(A\) has already been factored as \(A = PLU\). What is the cost of solving \(Ax = b\) for one new right-hand side \(b\)?

  1. \(O(N^2)\)
  2. \(O(N^3)\)
  3. \(O(N)\)
  4. \(O(N^3)\) the first time, \(O(N)\) afterwards

3. [2 pts]

A is an invertible \(N \times N\) matrix and bs is a list of \(K\) right-hand sides.

lu, piv = scipy.linalg.lu_factor(A)
for b in bs:
    x = scipy.linalg.lu_solve((lu, piv), b)

Compared with calling np.linalg.solve(A, b) inside the loop, which statement is correct?

  1. Both give the same solutions; this version factors once at \(O(N^3)\) and then pays \(O(N^2)\) per right-hand side, whereas solve refactors at \(O(N^3)\) on every iteration.
  2. Both give the same solutions at the same cost; lu_factor is only a stylistic choice.
  3. This version is cheaper but less accurate, because the factorization is reused without pivoting.
  4. np.linalg.solve is cheaper because it never forms \(L\) and \(U\).

4. [2 pts]

Let \(Q\) be an orthogonal matrix and \(x\) a vector with \(\lVert x \rVert_2 = 5\). What is \(\lVert Q x \rVert_2\)?

  1. \(5\)
  2. \(1\)
  3. \(25\)
  4. It depends on \(Q\).

5. [Essay] [3 pts]

Explain your answer to question 4 more generally: for any orthogonal \(Q\) and any \(x\), what is \(\lVert Q x \rVert_2\)? Give the intuition, and state and prove any general claims you can.

6. [2 pts]

Consider \(x_{t+1} = A x_t\) with

\[ A = \begin{bmatrix} 0.6 & 0.1 \\ 0.5 & 0.8 \end{bmatrix} \]

and an arbitrary \(x_0 \in \mathbb{R}^2\). And note the following.

A = np.array([[0.6, 0.1], [0.5, 0.8]])
Lambda, Q = np.linalg.eig(A)
print(Lambda)
print(Q)
[0.45505103+0.j 0.94494897+0.j]
[[-0.56786837+0.j -0.27843404+0.j]
 [ 0.82311938+0.j -0.96045535+0.j]]

Which statement is correct?

  1. \(x_t\) converges to \(0\) for every \(x_0\).
  2. \(\lVert x_t \rVert_2\) grows without bound for generic \(x_0\).
  3. Whether \(x_t\) converges depends on the direction of \(x_0\).
  4. \(x_t\) converges to a fixed point \(\bar{x} \neq 0\).

7. [Essay] [3 pts]

Explain your answer to question 6.

8. [2 pts]

A = np.array([[0.5, 0.2], [0.1, 0.8]])
print(A ** 2)
print(A @ A)
print(np.linalg.matrix_power(A, 2))
[[0.25 0.04]
 [0.01 0.64]]
[[0.27 0.26]
 [0.13 0.66]]
[[0.27 0.26]
 [0.13 0.66]]

Which of the three printed matrices equal \(A^2 = A A\)?

  1. Only the second and third.
  2. All three.
  3. Only the first.
  4. Only the third.

9. [2 pts]

A = np.array([[0.6, 0.1], [0.5, 0.8]])
Lambda, Q = np.linalg.eig(A)
print(np.max(np.abs(Lambda)) < 1)
v = Q[:, 1]
print(np.allclose(A @ v, Lambda[1] * v))

Which statement is correct?

  1. The first print checks \(\rho(A) < 1\), and v is an eigenvector of \(A\) with eigenvalue Lambda[1], so both lines print True.
  2. The first print checks that every eigenvalue is positive, and v is an eigenvector of \(A\).
  3. The first print checks \(\rho(A) < 1\), but v collects the second entry of each eigenvector, so the second line prints False.
  4. Both lines print True, but abs is unnecessary because the eigenvalues of a real matrix are real.

10. [2 pts]

The figure shows \(\lVert x_t \rVert_2\) for \(x_{t+1} = A x_t\) from the same \(x_0\) under three different matrices.

Which matrix has spectral radius greater than \(1\)?

  1. Matrix I
  2. Matrix II
  3. Matrix III
  4. It cannot be determined from the norms alone.

11. [Essay] [3 pts]

Explain your answer to question 10.

12. [2 pts]

The matrix

\[ A = \begin{bmatrix} 0.9 & 0.3 \\ 0.3 & 0.9 \end{bmatrix} \]

has eigenvalues \(1.2\) and \(0.6\). For which of these discount factors does \(\sum_{s=0}^{\infty} \beta^s A^s\) converge?

  1. \(\beta = 0.8\) only.
  2. \(\beta = 0.9\) only.
  3. Both \(\beta = 0.8\) and \(\beta = 0.9\).
  4. Neither, since \(\rho(A) > 1\).

13. [Essay] [3 pts]

Explain your answer to question 12.

14. [2 pts]

A is an \(n \times n\) matrix, d is a vector of length \(n\), and \(0 < \beta < 1\).

pv = np.linalg.solve(np.eye(n) - beta * A, d)

Which infinite sum does pv equal, and what condition makes that sum converge?

  1. \(\sum_{s=0}^{\infty} \beta^s A^s d\), provided \(\beta \rho(A) < 1\).
  2. \(\sum_{s=0}^{\infty} \beta^s A^s d\), provided \(\rho(A) < 1\).
  3. \(\sum_{s=1}^{\infty} \beta^s A^s d\), provided \(\beta \rho(A) < 1\).
  4. \(\sum_{s=0}^{\infty} \beta^s A d\), provided \(\beta < 1\).

15. [2 pts]

Two employment models have the same steady-state shares. Their transition matrices have eigenvalues

\[ A_1: \quad 1,\ 0.9, \qquad A_2: \quad 1,\ 0.4. \]

Which model’s deviations from its steady state decay faster?

  1. The model with \(A_1\).
  2. The model with \(A_2\).
  3. They decay at the same rate, because both have an eigenvalue of \(1\).
  4. Neither decays, because both have an eigenvalue of \(1\).

16. [2 pts]

A = np.array([[1, 2], [2, 1]])
x = np.array([1, 1])
print(x.T @ A @ x)
6

Is \(A\) positive definite?

  1. Yes, since \(x^{\top} A x = 6 > 0\).
  2. No, it is negative definite.
  3. We need more vectors or another method, and \(A\) might be negative definite.
  4. We need more vectors or another method, but \(A\) cannot be negative definite.

17. [Essay] [3 pts]

A symmetric matrix \(A\) has the reported eigenvalues

\[ \left[-10^{-17},\ 0.5,\ 1.1\right], \]

computed in float64. How would you categorize \(A\) in terms of positive (semi-)definite, negative definite, or indefinite? Explain.

18. [Essay] [3 pts]

X = np.array([[1, 2, 3], [0, 5, 7]])
y = np.array([5, 10])
beta_hat, *_ = scipy.linalg.lstsq(X, y)
print(np.allclose(X @ beta_hat, y))
True

Is beta_hat the unique solution to \(\min_{\beta} \lVert y - X \beta \rVert_2^2\)? If \(\beta\) were regression coefficients, how would you interpret them given your answer? Explain.