{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Homework 10"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"INSERT YOUR NAME HERE"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"__Directions:__ Add work to this notebook to solve the problems below.\n",
"\n",
"Be careful to name the objects you create as described in the problem. Some problems may include some tests you can run to test your code.\n",
"\n",
"This assignment will not be collected.\n",
"\n",
"Some problems are derived from problems in these books:\n",
"* __LL__: *Programming for Computations - Python* by Svein Linge and Hans Petter Langtangen, 2nd edition.\n",
"* __L__: *A Primer on Scientific Programming with Python* by Hans Petter Langtangen, 2nd edition.\n",
"* __TAK__: *Applied Scientific Computing With Python* by Peter R. Turner, Thomas Arildsen, and Kathleen Kavanagh."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Standard imports"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"from scipy import linalg\n",
"import numpy as np\n",
"import math as m\n",
"import matplotlib.pyplot as plt"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 1. The dominant eigenpair"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Consider the matrix defined below:"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"array([[5, 5, 5, 5, 5],\n",
" [4, 4, 4, 4, 5],\n",
" [3, 3, 3, 4, 5],\n",
" [2, 2, 3, 4, 5],\n",
" [1, 2, 3, 4, 5]])"
]
},
"execution_count": 2,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"A = np.array([[max(5-row,col+1) for col in range(5)] for row in range(5)])\n",
"A"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"This matrix has five distinct real eigenvalues.\n",
"\n",
"Use the *power method* to find a dominant eigenvalue and eigenvector pair. Be sure that the eigenvalue is accurate to 5 decimal places. Store the eigenvalue and eigenvector in the variables `eigenvalue_0` and `eigenvector_0`, respectively. Check that your answer is likely correct by verifying that\n",
"```python\n",
"A @ eigenvector_0 - eigenvalue_0 * eigenvector_0\n",
"```\n",
"is small.\n",
"\n",
"(This exercise is based on TAK §4.6 \\#1.)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Tests for your code:**"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"This vector should be very small:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"A @ eigenvector_0 - eigenvalue_0 * eigenvector_0"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 2. The eigenvalue of smallest absolute value"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Find the eigenvalue of smallest absolute value. Make sure the result is accurate to 5 decimal places and store the result in `eigenvalue_1`. Store the corresponding eigenvector in `eigenvector_1`. Check that your answer corresponds to an eigenvalue.\n",
"\n",
"You may use code from the notebook `Eigenvalues and Eigenvectors` used in class or code from § 4.6 of TAK.\n",
"\n",
"(This is problem \\# 2 from TAK § 4.6.)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 3. Some other eigenpairs"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Find the eigenvalue which is closest to $3$. Store the result in `eigenvalue_2`, and be sure the result is accurate to 5 decimal places. Store the corresponding eigenvector in `eigenvector_2`. Similarly store the eigenvalue nearest to $-1$ in the variables `eigenvalue_3` and store the corresponding eigenvector in `eigenvector_3`.\n",
"\n",
"Use inverse iteration with an origin shift as discussed in TAK § 4.6 and in the `Eigenvalues and Eigenvectors` notebook from class."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 4. The last eigenvector and eigenvalue pair"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The *trace* of a matrix is the sum of the diagonal entries. The trace of a matrix also is the sum of the eigenvalues (counting algebraic multiplicity).\n",
"\n",
"Compute the trace of the matrix $A$ and store the result in the variable `trace`.\n",
"\n",
"Use trace to approximate the fifth eigenvalue of $A$ (using the four other eigenvalues you have found). Since you know it is near the approximate eigenvalue, you can use inverse iteration with an origin shift to get a better approximate. Compute the fifth eigenvalue accurate to 5 decimal places and store the result in `eigenvalue_4`. Store the corresponding eigenvector in `eigenvector_4`. Check your work."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 5. Diagonalization"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Use the work from the problems above to find an invertible matrix $P$ and a diagonal matrix $D$ such that\n",
"$$A = P D P^{-1}.$$\n",
"Store $P$ in the variable `P` and $D$ in the variable `D`. Compute the inverse of $P$ and store it in the variable `P_inv`. Check that the equation is satisfied (up to error of order $10^{-4}$.\n",
"\n",
"To compute the inverse you can use `np.linalg.inv` in Numpy's linear algebra module."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 6. The shape of a dominant eigenvector"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The function below returns the matrix $B_n$, which is the $n \\times n$ matrix, which has ones on the diagonal and in the entries adjacent to the diagonal but zeros everywhere else. (This is an example of a tridiagonal matrix.)"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [],
"source": [
"def B(n):\n",
" B_n = np.zeros((n,n))\n",
" for j in range(n):\n",
" B_n[j,j] = 1\n",
" for j in range(n-1):\n",
" B_n[j,j+1] = 1\n",
" B_n[j+1,j] = 1\n",
" return B_n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Write a function `dominant_eigenvector(n, epsilon)` which returns the an approximate dominant eigenvector of $B_n$. This eigenvector must be computed using the power method. Compute until the assoicated approximate eigenvalue changes by less than `epsilon` (which must be positive).\n",
"\n",
"Note that there is not a single dominant eigenvector: scalar multiples of a dominant eigenvector are also dominant eigenvectors.\n",
"\n",
"Guess a formula for a dominant eigenvector and verify it agrees with what your function computes. Write a function `eigenvector_guess(n)` which returns your guess for the dominant eigenvector. Verify that it is correct by comparing with what your `dominant_eigenvector(n, epsilon)` and by working with the matrix $B_n$.\n",
"\n",
"*Hints:* First concentrate on the case that $n$ is odd. Normalize the dominant eigenvector so that the middle entry is one. Try plotting the eigenvector using `plt.plot(eigenvector)`. What does it look like? (It relates to waves...)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.8.5"
}
},
"nbformat": 4,
"nbformat_minor": 4
}