Exercise 1

  • Compute the conditioning of $A$ and $A^t A$ for a few random matrices $A$. How do you think the conditioning of $A$ and $A^t A$ are related generally?

  • The linear least squares problem lead us to the normal equations:

$A^t A x = A^t b$

Based on your observations, if $A$ is poorly conditioned then normal equations can be very poorly conditioned! For the second part of the exercise, consider the following alternative: Suppose we perform a $QR$ decomposition of $A$. Try replacing $A$ in the normal equations with its $QR$-decomposition and simplifying as much as possible. What do you get? Use this to solve the linear least squares problem.

  • Finally, using either the least squares solver you developed or using the lstsq function from scipy.linalg, find the "best fit" line through the dataset:
x = [-0.01, 0.078, 0.191, 0.318, 0.467, 0.54, 0.694, 0.76, 0.898, 0.988]
y = [0.988, 1.056, 1.142, 1.156, 1.221, 1.279, 1.349, 1.367, 1.463, 1.536]

Although this is commonly refered to as linear regression, you can see that it really isn't exclusive to lines! You could easily adapt the code to fit quadratics, cubics and so on.

Exercise 2

  • Try implementing power iteration to approximate the largest eigenvalue of a random SPD matrix. (You can form a random SPD matrix by computing a random matrix $A$ and taking $A^t A$.)

  • Similarly, try computing the minimum eigenvalue using inverse iteration. (If you'd like, you can try adding the updating shift too!)

Exercise 3

  • Using either the eigvals or eigvalsh function in scipy.linalg, try verifying the maximum and minimum eigenvalues you got in the previous problem.

Exercise 4

Since linear regression is a common task, let's see if we can shorten up our least squares approach from earlier. On the same data set as exercise 1, see if you can use Numpy's polyfit(x, y, deg) to compute the best fit line instead.

Alternatively, the scipy.stats module has a function linregress. This only gives you a best fit line, but it does provide you with more information about how good the fit is.