{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Homework 9\n",
"\n",
"Student's Name: PLEASE INSERT YOUR NAME HERE"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"__Directions:__ Add work to this notebook to solve the problems below. Some other cells have been included which are important for testing your work and should give you some feeback.\n",
"\n",
"Check your work. I give some tests that should be passed if you get it correct.\n",
"\n",
"**Your notebook should run without printing errors and without user input. If this is not the case, points will be deducted from your grade.**\n",
"\n",
"You may not use eigenvalue/eigenvector methods built into python (except possibly to check your work). You must use the methods discussed in class.\n",
"\n",
"Problem Sources:\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": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Standard imports\n",
"import numpy as np\n",
"import matplotlib.pyplot as plt\n",
"import math as m\n",
"from mpmath import mp, iv\n",
"from scipy import linalg"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 1. Determine the winner\n",
"\n",
"The organizers of a races use a dictionary mapping names to times (positive real numbers). Write a function `race_winner(times)` which takes as input a dictionary `times` which maps names to times and returns the name of the winner. The winner is the person with the lowest time."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Test\n",
"data = { 'Donovan': 12.488626865581734,\n",
" 'Dennis': 12.339121151126296,\n",
" 'Akeyla': 16.989828336822182,\n",
" 'Ahad': 14.851156675973165,\n",
" 'Miguel': 10.058766707549275,\n",
" 'Seonin': 15.489321944011124 }\n",
"winner = race_winner(data)\n",
"print(\"{} won the race!\".format(winner))\n",
"assert winner == 'Miguel', \"You have the wrong winner.\""
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 2. Printing a polynomial\n",
"\n",
"Example 6.2.3 on page 280 of **L** discusses the example of using a dictionary to store the non-zero coefficients of a polynomial. The dictionary representing a polynomial maps the degree $d$ of a term $c_d x^d$ to the coefficient of the term $c_d$. Read this example for more information.\n",
"\n",
"Write a function `polynomial_string(data)` which takes as input a dictionary `data` representing a polynomial and returns a string representing that polynomial. The string should be such that if the string is evaluated by python it would return the polynomial evaluated at `x`.\n",
"\n",
"You have a lot of flexibility with how you print your answer. In the test below I define `p` by:\n",
"```python\n",
"p = {0:-3, 2:-2, 3:1} # x^3 - 2x^2 - 3\n",
"s = polynomial_string(p)\n",
"```\n",
"Any of the following strings are acceptable returns by `polynomial_string(data)`:\n",
"* `'1*x**3-2*x**2-3'`\n",
"* `'-3*x**0 - 2*x**2 + x**3'`\n",
"* `'-3 + x**2 * (x-2)'`\n",
"\n",
"The test below makes use of the [`eval` function](https://docs.python.org/3/library/functions.html#eval)."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Test\n",
"p = {0:-3, 2:-2, 3:1} # x^3 - 2x^2 - 3\n",
"s = polynomial_string(p)\n",
"print(\"The polynomial is {}\".format(s))\n",
"x = 0\n",
"assert eval(s) == -3, \"The polynomial should evaluate to -3 when x=0.\"\n",
"x = 1\n",
"assert eval(s) == -4, \"The polynomial should evaluate to -4 when x=1.\"\n",
"x = -5\n",
"assert eval(s) == -178, \"The polynomial should evaluate to -178 when x=-5.\""
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 3. Derivatives of polynomials\n",
"\n",
"\n",
"Write a function `polynomial_derivative(data)` which takes as input a dictionary `data` representing a polynomial and returns a dictionary representing the derivative of the polynomial."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Test\n",
"p = {0:3, 2:1} # x^2 + 3\n",
"der = polynomial_derivative(p)\n",
"print(\"The derivative of {} is {}.\".format(polynomial_string(p),\n",
" polynomial_string(der)))\n",
"assert polynomial_derivative(p)=={1:2}, \"The derivative should be 2*x.\""
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 4. Multiplying polynomials\n",
"\n",
"Write a function `polynomial_product(f,g)` which takes as input two dictionaries `f` and `g` representing polynomials and returns a dictionary representing the product of the two polynomials. \n",
"\n",
"Be sure that there are no degrees in the returned dictionary which map to a coefficient of zero. (The reason to worry about this has to do with uniqueness of a polynomial representation. For example, the dictionaries `{2:1}` and `{0:0, 2:1}` both represent $x^2$ but\n",
"`{2:1}=={0:0, 2:1}` will return `False`.)\n",
"\n",
"You can assume that `f` and `g` have nonzero coefficients."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Test\n",
"f = {1:1,0:1} # f(x)=x+1\n",
"g = {1:1,0:-1} # g(x)=x-1\n",
"h = polynomial_product(f, g)\n",
"print(\"The product of {} and {} is {}.\".format(polynomial_string(f),\n",
" polynomial_string(g),\n",
" polynomial_string(h)))\n",
"assert h == {2:1, 0:-1}, \"The product is wrong or has a zero coefficient.\""
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 5. Quadrature rules\n",
"\n",
"Recall that a quadrature formula has the form\n",
"$$Q(f) = \\sum_{k=0}^N c_k f(x_k).$$\n",
"Here $f$ should be a function whose domain includes the points $x_k$ and each $c_k$ is a number. \n",
"\n",
"The quadrature rule $Q$ is determined by the mapping $x_k \\mapsto c_k$ which we can interpret as a dictionary.\n",
"\n",
"Write a funtion `quadrature_evaluation(q, f)` which takes as input a dictionary `q` mapping points $x_k$ to the corresponding coefficient $c_k$ and a function `f` and returns the quantity \n",
"$$\\sum_{k=0}^N c_k f(x_k).$$"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Test\n",
"# Simpson's rule for [0, 1]\n",
"q = {0: 1/6, 0.5: 4/6, 1: 1/6}\n",
"# The function x -> x^2\n",
"f = lambda x: x**2 \n",
"# this quadrature rule should be exact:\n",
"assert abs(quadrature_evaluation(q, f)-1/3) < 10**-15, \\\n",
" \"incorrect result returned. The answer should be 1/3.\""
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 6. Transforming quadrature rules\n",
"\n",
"Near the bottom of the [Numerical Integration notebook](http://wphooper.com/teaching/2020-spring-computation/nb/Numerical%20Integration.html) (under the heading *Change of coordinates formula for quadrature rules*) a formula is given for transforming a quadrature rule $A$ approximating integrals over the interval $[-1, 1]$ into a quadrature rule $B$ approximating integrals over the interval $[c,d]$. \n",
"\n",
"Write a function `transformed(A, c, d)` which takes as input a dictionary `A` representing a quadrature rule and floats `c` and `d` with $c