{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Practice Final"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Reference Books\n",
"\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.\n",
"\n",
"### Topics\n",
"\n",
"The final exam will focus on material not tested on the midterm. However, this class is cumulative, and it is necessary to understand earlier material as well. In particular, it is expected that students have developed a working knowledge of Python.\n",
"\n",
"The following is a list of topics that may be explicitly tested on the final exam. See the [course's calendar page](http://wphooper.com/teaching/2020-fall-computation/calendar.php) for notebooks used in lecture and for where the material appears in the textbooks above.\n",
"\n",
"* Basic math\n",
"* Lists (covered in the Plotting Graphs notebook)\n",
"* Closure (functions returning functions, covered in the plotting graphs notebook)\n",
"* Numerical differentiation\n",
"* Numerical integration\n",
"* Matrices and vectors\n",
"* Gaussian elimination\n",
"* LU Factorization\n",
"* Least squares\n",
"* Dictionaries\n",
"* Eigenvalues and Eigenvectors\n",
"* Random numbers (especially the use of `numpy.random.random_sample` or equivalently `numpy.random.random`)\n",
"\n",
"### Sources of review\n",
"\n",
"* The homework assignments and solutions.\n",
"* The textbooks listed above and exercises on the topics above.\n",
"* The notebooks available on the [Class' Calendar page](http://wphooper.com/teaching/2020-spring-computation/calendar.php)\n",
"* Class videos, available from Blackboard Collaborate.\n",
"\n",
"### Exam format\n",
"\n",
"The exam will be given similar to how quizzes have been given in the course. You will download notebooks from blackboard at specific times and have a fixed amount of time to complete each part.\n",
"\n",
"The exam is scheduled for Monday, December 14th from 3:30pm to 5:45pm. This two hours and 15 minutes will be divided into intervals, with each interval of time allowing you to work on one notebook.\n",
"\n",
"You will be required to be signed in to blackboard collaborate for the duration of the exam."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Standard imports"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"import numpy as np\n",
"from numpy import random\n",
"from matplotlib import pyplot as plt"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 1. Composite Simpson's Rule"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Simpson's Rule is the Quadrature Rule defined on an arbitrary interval $[a,b]$ by the formula\n",
"$$S_{[a,b]}(f) = \\frac{b-a}{6} \\left[\\,f(a)+4\\, f\\left(\\frac{a+b}{2}\\right) + f(b) \\right].$$\n",
"This is an approximate for $\\int_a^b f~dx$. \n",
"\n",
"Write a function `compound(t, f)` which takes as input a numpy array `t` of length `m = len(t)`, \n",
"$$t = [t_0, t_1, \\ldots, t_{m-1}]$$\n",
"with $t_0 < t_1 < t_2 < \\ldots < t_{m-1}$ and a function `f(x)` representing a function \n",
"$f:{\\mathbb R} \\to {\\mathbb R}$. Evaluating `compound(t, f)` should return the sum \n",
"$$\\sum_{i=0}^{m-2} S_{[t_i, t_{i+1}]}(\\,f).$$\n",
"This is a composite integration rule."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Tests for your code:**"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"t = np.linspace(3, 5, 11)\n",
"print(\"t = {}\".format(t))\n",
"f = lambda x: x**3\n",
"print(\"f(x) = x^3\")\n",
"ans = compound(t, f)\n",
"print(\"Your answer was {}.\".format(ans))\n",
"print(\"The correct answer is {}.\".format(1/4*(5**4 - 3**4)))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 2. Manipulating Matrices 5"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Write a function `manipulate(M)` which takes as input a matrix `M` (given as numpy array of floats) such that `M` has `n` rows and `n+1` columns for some `n ≥ 1`. The function `manipulate(M)` should add scalar multiples of the last column to each of the other columns and return the result. The scalars should be chosen such that the resulting matrix has all zero entries on the diagonal. (The *diagonal* consists of entries with the same row number and column number.) You may assume that no zero appears in the last column of `M`.\n",
"\n",
"For example, if\n",
"$$M = \\left(\\begin{matrix} 2 & 9 & 1 \\\\\n",
" 5 & 6 & 2 \\end{matrix}\\right),$$\n",
"then `manipulate(M)` should change column zero by adding $-2$ times column two, and change column one by adding $-3$ times column $2$. The matrix\n",
"$$M = \\left(\\begin{matrix} 0 & 6 & 1 \\\\\n",
" 1 & 0 & 2 \\end{matrix}\\right)$$\n",
"should be returned."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Tests for your code:**"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"M1 = np.array( [ [ 2., 9., 1.],\n",
" [ 5., 6., 2.] ])\n",
"correct1 = np.array( [ [ 0., 6., 1.],\n",
" [ 1., 0., 2.] ])\n",
"assert (manipulate(M1) - correct1 < 10**-12).all(), \\\n",
" \"manipulate(M1) is incorrect.\""
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"M2 = np.array([[ 0., 1., 5., 2.],\n",
" [-5., -1., 8., 5.],\n",
" [ 9., -8., 6., 5.]])\n",
"correct2 = np.array([ [ 0. , 1.4, 2.6, 2. ],\n",
" [-5. , 0. , 2. , 5. ],\n",
" [ 9. , -7. , 0. , 5. ] ])\n",
"assert (manipulate(M2) - correct2 < 10**-12).all(), \\\n",
" \"manipulate(M2) is incorrect.\""
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 3. Approximation by a quadratic polynomial"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Consider the following inner product on real-valued functions defined on the set $\\{1, 2, \\ldots, 10\\}$:\n",
"$$\\langle f, g\\rangle = \\sum_{k=1}^{10} k\\,f(k) g(k).$$\n",
"It can be shown that the polynomials\n",
"$$q_0(x)=1, \\quad q_1(x)=x-7, \\quad \\mathrm{and} \\quad q_2(x)=x^2 - 12.6 x + 33.2$$\n",
"are orthogonal with respect to this inner product. These three polynomials span the collection of all polynomials of degree less than or equal to two."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Write a function `projection(h)` which takes as input a dictionary $h$ mapping each of the integers in the set $\\{1, 2, \\ldots, 10\\}$ to floating point real numbers. Calling `projection(h)` should return a function. The function returned should be the polynomial obtained by projecting `h` to the space of polynomials of degree less than or equal to two."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"To assist you, the inner product described above has been implemented below as `ip(f,g)`. The inputs `f` and `g` can be either functions defined on the set $\\{1, 2, \\ldots, 10\\}$ or dictionaries whose keys include the set $\\{1, 2, \\ldots, 10\\}$. Also the three polynomials $q_0$, $q_1$ and $q_2$ have been defined as functions below."
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [],
"source": [
"def ip(f, g):\n",
" if type(f) == dict:\n",
" # Make it so that we can use function notation for f.\n",
" f = f.__getitem__\n",
" if type(g) == dict:\n",
" # Make it so that we can use function notation for g.\n",
" g = g.__getitem__\n",
" total = 0.0\n",
" for k in range(1,11):\n",
" total += k * f(k) * g(k)\n",
" return total\n",
"q0 = lambda x: 1.0\n",
"q1 = lambda x: x - 7.0\n",
"q2 = lambda x: x**2 - 12.6*x + 33.2"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"*Remark: *You are asked to return a *function*, so you should use closure\n",
"or return a lambda function."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Tests for your code:**"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"A test follows which tests that `projection(h)` returns the correct function,\n",
"in the case when `h` is a dataset given by a dictionary. If your code is correct,\n",
"the resulting graph should match the one below."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"h = {1: 1.110, 2: 0.961, 3: 0.104, 4: 0.121, 5: -0.274, \n",
" 6: -0.230, 7: 0.611, 8: 0.487, 9: 1.718, 10: 2.341}\n",
"ph = projection(h)\n",
"\n",
"# Test that ph is a function\n",
"from types import FunctionType\n",
"assert type(ph) == FunctionType, \"Error: ph should be a function\"\n",
"\n",
"x = np.array(range(1, 11))\n",
"hx = [] # Construct the image of x under h\n",
"for i in h:\n",
" hx.append(h[i])\n",
"plt.plot(x, hx, \"or\") # Plot h(i)\n",
"\n",
"x = np.linspace(1,10)\n",
"phx = [] # Construct the image of x under ph\n",
"for xi in x:\n",
" phx.append(ph(xi)) \n",
"plt.plot(x,phx) # Plot the graph of ph(x)\n",
"\n",
"plt.show()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Your output from the above should look like the following graph:\n",
""
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 4. Inside a union of disks"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"A radius $r>0$ and a center point $(a, b)$ determine a disk in the plane:\n",
"$$D_r(a,b) = \\{(x,y):~(x-a)^2 + (x-b)^2 \\leq r^2\\}.$$\n",
"\n",
"We'll use a dictionary mapping centers to radii to represent a finite union of disks. For example, a dictionary of the form:\n",
"$$\\{(a_0,b_0): r_0, (a_1,b_1): r_1, ..., (a_{n-1},b_{n-1}): r_{n-1}\\}$$\n",
"will represent the union of disks \n",
"$$\\bigcup_{j=0}^{n-1} D_{r_j}(a_j, b_j).$$\n",
"\n",
"Write a function `inside(d, x, y)` which takes as input a dictionary `d` representing a finite union of disks as described above, and two numbers `x` and `y`. The function should return `True` if the point `(x,y)` lies in the union of disks and should return `False` if the point does not lie in the union."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Tests for your code:**"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"A test has been provided below with an accompanying figure of the disk union and points being tested."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"d = {(0,0): 3, (3,0): 2}\n",
"assert inside(d, 2, 0), \"The point (2, 0) should be inside.\"\n",
"assert inside(d, 1, -2), \"The point (1, -2) should be inside.\"\n",
"assert inside(d, 4, 1), \"The point (4, 1) should be inside.\"\n",
"assert not inside(d, 2, 2.8), \"The point (2, 3) should be outside.\"\n",
"assert not inside(d, 2.3, 2), \"The point (2.5, 2) should be outside.\""
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"x = [2, 1, 4, 2, 2.3]\n",
"y = [0, -2, 1, 2.8, 2]\n",
"from matplotlib.patches import Circle\n",
"from matplotlib.transforms import Bbox\n",
"ax = plt.axes()\n",
"plt.xlim(-3,5)\n",
"plt.ylim(-3,3)\n",
"ax.set_aspect('equal')\n",
"for pt in d:\n",
" r = d[pt]\n",
" disk = Circle(pt, r)\n",
" disk.set_alpha(0.3)\n",
" ax.add_patch(disk)\n",
"plt.grid(True, linestyle='-')\n",
"plt.plot(x, y, \".r\")\n",
"plt.show()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 5. Eigenvalues and Eigenvectors of a matrix Y"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The matrix $Y$ defined below has four distinct real eigenvalues. We'll denote the largest eigenvalue by $\\lambda$. It turns out that $-\\lambda$ is also an eigenvalue, and all other eigenvalues lie in the open interval $(-\\lambda, \\lambda)$. "
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [],
"source": [
"Y = np.array([[ -1., 0., 8., -4.],\n",
" [ 11., 8., -30., 12.],\n",
" [ 26., 18., -55., 20.],\n",
" [ 51., 36., -126., 48.]])"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Write a function `eigenpair(epsilon)` which takes as input a postive floating point number `epsilon`. The function should apply an iterative method (such as the power method) to find approximations for $\\lambda$ and the associated eigenvector $v$. Iteration should stop when successive approximations of $\\lambda$ differ in absolute value by less than `epsilon`. A pair $(\\lambda, v)$ consisting of the approximation of $\\lambda$ and the approximation of $v$ should be returned. "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Hint: How can you apply a shift to make $v$ a dominant eigenvector?"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Tests for your code:**"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"lam,vec = eigenpair(10**-5)\n",
"diff = (Y @ vec) - (lam * vec)\n",
"print(\"The difference between Y*v and lambda*v is {}\".format(diff))\n",
"assert (abs(diff) < 10**-5).all(), \\\n",
" \"The pair returned is not close to an eigenpair.\""
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 6. Finding an eigenvalue close to -3"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The matrix $A$ below has a real eigenvalue $\\lambda$ which is very close to $-3$."
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [],
"source": [
"A = np.array([[ 4, 1, 2, 4],\n",
" [-2, 4, -1, 2],\n",
" [ 1, -2, 3, 4],\n",
" [ 3, 4, 2, 1]\n",
" ])"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We define $B = (A+3I)^{-1}$. This matrix is approximately given below."
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [],
"source": [
"B = np.array([[-0.36363636, -0.54545455, -0.27272727, 0.90909091],\n",
" [-0.81818182, -0.72727273, -0.36363636, 1.54545455],\n",
" [-1.40909091, -1.36363636, -0.43181818, 2.52272727],\n",
" [ 1.79545455, 1.81818182, 0.78409091, -3.23863636]])"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Use powers of $B$ to compute the eigenvalue `lambda_A` of $A$ which is closest to $-3$. Store the associated eigenvector in `eigenvector_A`. Both quantities should be correct to six decimal places."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 7. Finding a final eigenvalue"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The matrix $C$ below has four distinct eigenvalues. Three of them are given below (correct to several digits of accuracy). Find the fourth and store the result in `eigvalue_3` to approximately the same accuracy."
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [],
"source": [
"C = np.array([[ 5, 1, 2, 4],\n",
" [-2, 4, -1, 2],\n",
" [ 1, -2, 3, 4],\n",
" [ 3, 4, 2, 10]\n",
" ])\n",
"eigvalue_0 = 12.92391499\n",
"eigvalue_1 = 1.23951179\n",
"eigvalue_2 = 1.60202972"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 8. Shifting polynomials"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Recall that a polynomial \n",
"$$p(x) = \\sum_{k=0}^d c_k x^k$$\n",
"can be represented by a dictionary with one entry for every non-zero coefficient. The dictionary representing $p$ would then map a degree $k$ with a non-zero $c_k$ to the floating point number $c_k$. For example `{9:3.0, 7:2.0}` would represent $3 x^9 + 2x^7$.\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Write a function `shift(p, t)` which takes as input a dictionary `p` representing a polynomial $p(x)$ and a floating point real number $t$. The function should return the dictionary representing the polynomial\n",
"$$q(x) = p(x+t).$$"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"*Help:* To do this, you need to know the coefficients of $(x+t)^k$. We have\n",
"$$(x+t)^k = \\sum_{i=0}^k \\binom{k}{i} t^{k-i} x^i.$$\n",
"The binomial coefficient $\\binom{k}{i}$ can be computed using the `binom` function from the `scipy.special` package. For example, $\\binom{4}{2}=6$ and this can be seen using the following python code:\n",
"```\n",
"from scipy.special import binom\n",
"binom(4, 2)\n",
"```"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Tests for your code:**"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"If $p$ is given below:\n",
"$$p(x) = x^2 + 3x$$\n",
"then $q(x)$ will have the form:\n",
"$$q(x) = p(x+t) = (x+t)^2 + 3(x+t).$$\n",
"Simplifying we see that\n",
"$$q(x) = (x^2+ 2 tx + t^2) + (3x+3t)$$\n",
"and\n",
"$$q(x) = 1 x^2 + (2t + 3) x + (t^2 + 3t).$$"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"p = {2:1, 1:3} \n",
"for t in range(1, 10):\n",
" expected_q = {2:1, 1:2*t+3, 0:t**2+3*t}\n",
" q = shift(p, t)\n",
" assert q == expected_q, f'Error when t={t}'"
]
}
],
"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
}