owned this note
owned this note
Published
Linked with GitHub
---
class: mth302
---
# 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](https://www.youtube.com/watch?v=lHr0VCXmztI); 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:
```python=
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:
```python
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](https://github.com/RobertTalbert/linalg-diffeq/blob/main/course-docs/standards-for-student-work.md#standards-for-miniprojects) 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](https://github.com/RobertTalbert/linalg-diffeq/blob/main/tutorials/Example_of_solution_in_a_notebook.ipynb). 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](https://gvsu.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=ef5c0e24-5c1d-437f-be05-af730108b6d8), 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.