Miniproject 4

Initial due date: Sunday, March 26 at 11:59pm ET

Overview

Eigenvalues of a matrix are incredibly useful and important for many applications. (Some of these applications are in Miniprojects 1-3.) But computing eigenvalues of a matrix, even of relatively small size, can be difficult or impossible to do exactly. So we need numerical approximation methods for most practical uses of eigenvalues. This miniproject will teach you one such method.

Prerequisites: You'll need to know what an eigenvalue and eigenvector for a matrix are, and how to find these using SymPy. You'll also need to know how to multiply matrices and vectors.

Background

Complete the following warmup exercises first. These don't go in your writeup. They are just here to teach you some terminology you'll need in the main assignment.

Definition: Suppose \(A\) is an \(n \times n\) matrix and \(\lambda_1, \lambda_2, \dots, \lambda_n\) are its eigenvalues. Then \(\lambda_1\) is called the dominant eigenvalue of \(A\) if \(|\lambda_1| > |\lambda_i|\) for all \(i \neq 1\). The eigenvectors corresponding to \(\lambda_1\) are called dominant eigenvectors of \(A\).

Example: The matrix \(A = \begin{bmatrix} -2 & 0 \\ 0 & 1 \end{bmatrix}\) has eigenvalues of \(-2\) and \(1\). Of these, \(\lambda = -2\) is the dominant eigenvalue since \(|-2| > |1|\). A dominant eigenvector for \(A\) would be \([1,0]^T\) since that's an eigenvector corresponding to the dominant eigenvalue \(\lambda = -2\).

Example: The matrix \(A = \begin{bmatrix} -1 & 0 \\ 0 & 1 \end{bmatrix}\) doesn't have a dominant eigenvalue, since its two eigenvalues are \(-1\) and \(1\), and neither \(|-1| > |1|\) nor \(|1| > |-1|\).

Exercise: Find the dominant eigenvalue and a dominant eigenvector for
\[B = \left[\begin{matrix}11 & 0 & -4\\17 & -2 & -5\\30 & 0 & -11\end{matrix}\right]\]
Answer: \(\lambda_1 = -2\) is the dominant eigenvalue and \(\mathbf{v}_1 = [0,1,0]^T\) is a dominant eigenvector.

Assignment

1. Suppose \(A\) is a \(100 \times 100\) matrix. This is actually considered "small" for most real-world applications. If we wanted to find its eigenvalues using the basic method we learned in class, we would need to solve the equation \(\det(A - \lambda I_{100}) = 0\) for \(\lambda\). How easy or hard would this be? Why?

The first problem illustrates the computational issues with using our basic method for finding eigenvalues. So rather than find the eigenvalues of a matrix algebraically, it's often enough to (1) find just the dominant eigenvalue, and (2) get a reasonable numerical approximation to it. The rest of this miniproject walks you through one method for doing this.

2. Let \(A = \begin{bmatrix} -5 & 14 \\ 9 & 15 \end{bmatrix}\). Choose any nonzero vector in \(\mathbb{R}^2\) and call it \(\mathbf{x}_0\). Compute \(\mathbf{x}_1 = A \mathbf{x}_0\).
3. Compute \(\mathbf{x}_2 = A \mathbf{x}_1\). Notice, this is the same as \(A \cdot A \cdot \mathbf{x}_0\) or \(A^2 \mathbf{x}_0\).
4. Compute \(\mathbf{x}_3 = A \mathbf{x}_2\), which is the same as \(A^3 \mathbf{x}_0\).
5. The vectors you are computing are getting larger and larger in terms of their components, but how much is their overall direction changing? Take each of the vectors you computed (\(\mathbf{x}_0, \mathbf{x}_1, \mathbf{x}_2, \mathbf{x}_3\)) and find a unit vector that points in the same direction. (Here is a short refresher on how to do this; make sure to turn your sound off!) And, see below for some SymPy notes on this.
6. Continue this process: For \(i = 4, \dots, 10\), compute \(A^i\mathbf{x}_0\) and then find a unit vector that points in the same direction.
7. You should notice that the results of your calculations seem to be stabilizing around a single unit vector. If this isn't apparent, check your work and/or do a few more iterations of this process. What is that unit vector?
8. Multiply the unit vector you found by the original matrix. Use the result to explain why the unit vector you found in the previous step is approximately an eigevector for the original matrix. What is the (approximate) eigenvalue associated with this approximate eigenvector?
9. Now use SymPy to find the exact values of the eigenvalues of \(A\). Which one is dominant? Which of these eigenvalues did the method above produce? What was the percent error in your approximation?
10. Adapt the method from above to approximate the dominant eigenvalue and eigenvector for
    \[B = \displaystyle \left[\begin{matrix}9 & -4 & 1 & 1\\0 & -3 & -4 & -3\\10 & -2 & -1 & -4\\-9 & 9 & 0 & -7\end{matrix}\right]\]
    Be sure to fully explain your reasoning and show your code.
11. Use SymPy to find the exact value of the eigenvalues. The results will look like an explosion of math notation. So, after getting the exact values, run the following code to get approximations of the exact values:

for eigenvalue in B.eigenvals().keys():
    print(N(eigenvalue))

This will print approximate values of the eigenvalues. Which one is dominant? What is the percentage error in your approximation?

Notes on this Miniproject

You will be really well served to use SymPy as much as possible on this miniproject. You should be doing no work by hand; and moreover, tapping in to some of SymPy's capabilities will lighten your load considerably.

Here are some things you can do with SymPy that are relevant to this Miniproject.

• To raise a matrix to a power, use ** just like we raise numbers or symbols to powers.
• Mathematically, to find the length of a vector, we compute \(\sqrt{x_1^2 + x_2^2 + \cdots + x_n^2}\) where \(x_1, x_2, \dots x_n\) are its components. But a more economical way to do it is to use the dot product and compute \(\sqrt{\mathbf{v} \cdot \mathbf{v}}\). In SymPy, to find the dot product of the vector a with the vector b, enter a.dot(b). To take the square root of an number \(x\), enter sqrt(x). You can put these functions together with what you already know how to do in SymPy to automate much of the math in question 5.
• SymPy works with exact values, but sometimes (like now) we need approximations. To convert an exact value to an approximation, wrap it in N( ). For example try N(sqrt(5)).
• Sometimes we want to print off a vector or a matrix not in its "pretty" form, but as plain text so it will not take up so much space. To do this in SymPy, just put print( ) around the thing you want to display. For example, try print(Matrix(2,2,[1,2,3,4])).
• The approximation method in this miniproject involves iteration, and computer languages are good at this. The for loop construction in Python is helpful. Here's an example of a for loop that would print off the squares of the numbers 1 through 100:

for i in range(1,101):
    print(i**2)

In Python, ranges stop just before the upper limit, so range(1,101) is 1, 2, 3, …, 100.

Submission and Grading

Formatting and special items for grading

Please review the section on Miniprojects in the document Standards For Student Work in MTH 302 before attempting to write up your submission. Note that all Miniprojects:

• Must be typewritten. If any portion of the submission has handwritten work or drawings, it will be marked Incomplete and returned without further comment.
• Must represent a good-faith effort at a complete, correct, clearly communicated, and professionally presented solution. Omissions, partial work, work that is poorly organized or sloppily presented, or work that has numerous errors will be marked Incomplete and returned without further comment.
• Must include clear verbal explanations of your work when indicated, not just math or code. You can tell when verbal explanations are required because the problems say something like "Explain your reasoning".

Your work here is being evaluated partially on whether your math and code are correct; but just as much on whether your reasoning is correct and clearly expressed. Make sure to pay close attention to both.

Miniproject 3 must be done in a Jupyter notebook using SymPy to carry out all mathematical calculations. A sample notebook, demonstrating the solution to a Calculus problem, can be found here. Study this first before writing up your work.

How to submit

You will submit your work on Blackboard in the Miniproject 4 folder under Assignments > Miniprojects. But you will not upload a PDF for Miniprojects. Instead you will share a link that allows me (Talbert) to comment on your work. As explained in one of the Jupyter and Colab tutorials, the process goes like this:

1. In the notebook, click "Share" in the upper right.
2. Do not share with me by entering my email. Instead, go to General Access, and in the pulldown menu select "Anyone with the link", then set the permissions to "Commenter".
3. Then click "Copy Link".
4. On Blackboard, go to the Assignments area, then Miniprojects. Select Miniproject 4.
5. Under Assignment Submission, where it says Text Submission, click "Write Submission".
6. Paste the link to your notebook in the text area that appears.
7. Then click "Submit" to submit your work.

I will then evaluate your work using the link. Specific comments will be left on the notebook itself. General comments will be left on Blackboard.