# Homework 9¶

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.

Check your work. I give some tests that should be passed if you get it correct.

Your notebook should run without printing errors and without user input. If this is not the case, points will be deducted from your grade.

You may not use eigenvalue/eigenvector methods built into python (except possibly to check your work). You must use the methods discussed in class.

Problem Sources:

• LL: Programming for Computations - Python by Svein Linge and Hans Petter Langtangen, 2nd edition.
• L: A Primer on Scientific Programming with Python by Hans Petter Langtangen, 2nd edition.
• TAK: Applied Scientific Computing With Python by Peter R. Turner, Thomas Arildsen, and Kathleen Kavanagh.
In [ ]:
# Standard imports
import numpy as np
import matplotlib.pyplot as plt
import math as m
from mpmath import mp, iv
from scipy import linalg


## 1. Determine the winner¶

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.

In [ ]:


In [ ]:
# Test
data = { 'Donovan': 12.488626865581734,
'Dennis': 12.339121151126296,
'Akeyla': 16.989828336822182,
'Miguel': 10.058766707549275,
'Seonin': 15.489321944011124 }
winner = race_winner(data)
print("{} won the race!".format(winner))
assert winner == 'Miguel', "You have the wrong winner."


## 2. Printing a polynomial¶

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.

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.

You have a lot of flexibility with how you print your answer. In the test below I define p by:

p = {0:-3, 2:-2, 3:1} # x^3 - 2x^2 - 3
s = polynomial_string(p)


Any of the following strings are acceptable returns by polynomial_string(data):

• '1*x**3-2*x**2-3'
• '-3*x**0 - 2*x**2 + x**3'
• '-3 + x**2 * (x-2)'

The test below makes use of the eval function.

In [ ]:


In [ ]:
# Test
p = {0:-3, 2:-2, 3:1} # x^3 - 2x^2 - 3
s = polynomial_string(p)
print("The polynomial is {}".format(s))
x = 0
assert eval(s) == -3, "The polynomial should evaluate to -3 when x=0."
x = 1
assert eval(s) == -4, "The polynomial should evaluate to -4 when x=1."
x = -5
assert eval(s) == -178, "The polynomial should evaluate to -178 when x=-5."


## 3. Derivatives of polynomials¶

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.

In [ ]:


In [ ]:
# Test
p = {0:3, 2:1} # x^2 + 3
der = polynomial_derivative(p)
print("The derivative of {} is {}.".format(polynomial_string(p),
polynomial_string(der)))
assert polynomial_derivative(p)=={1:2}, "The derivative should be 2*x."


## 4. Multiplying polynomials¶

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.

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 {2:1}=={0:0, 2:1} will return False.)

You can assume that f and g have nonzero coefficients.

In [ ]:


In [ ]:
# Test
f = {1:1,0:1} # f(x)=x+1
g = {1:1,0:-1} # g(x)=x-1
h = polynomial_product(f, g)
print("The product of {} and {} is {}.".format(polynomial_string(f),
polynomial_string(g),
polynomial_string(h)))
assert h == {2:1, 0:-1}, "The product is wrong or has a zero coefficient."


Recall that a quadrature formula has the form $$Q(f) = \sum_{k=0}^N c_k f(x_k).$$ Here $f$ should be a function whose domain includes the points $x_k$ and each $c_k$ is a number.

The quadrature rule $Q$ is determined by the mapping $x_k \mapsto c_k$ which we can interpret as a dictionary.

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 $$\sum_{k=0}^N c_k f(x_k).$$

In [ ]:


In [ ]:
# Test
# Simpson's rule for [0, 1]
q = {0: 1/6, 0.5: 4/6, 1: 1/6}
# The function x -> x^2
f = lambda x: x**2
# this quadrature rule should be exact:
assert abs(quadrature_evaluation(q, f)-1/3) < 10**-15, \
"incorrect result returned. The answer should be 1/3."


Near the bottom of the Numerical Integration notebook (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]$.

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<d$ and returns a dictionary representing the transformed quadrature rule $B$.

In [ ]:


In [ ]:
# Testing on the example in the Numerican Integration notebook
A = {-m.sqrt(3)/m.sqrt(5) : 5/9,
0 : 8/9,
m.sqrt(3)/m.sqrt(5) : 5/9 }
B = transformed(A, 0, m.pi)
key0, key1, key2 = sorted(B.keys())
assert abs(key0 - 0.35406272400281313) < 10**-8, \
'The point x_0 is wrong.'
assert abs(B[key0] - 0.8726646259971648) < 10**-8, \
'The coefficient c_0 is wrong.'
assert abs(key1 - 1.5707963267948966) < 10**-8, \
'The point x_1 is wrong.'
assert abs(B[key1] - 1.3962634015954636) < 10**-8, \
'The coefficient c_1 is wrong.'
assert abs(key2 - 2.78752992958698) < 10**-8, \
'The point x_2 is wrong.'
assert abs(B[key2] - 0.8726646259971648) < 10**-8, \
'The coefficient c_2 is wrong.'