# coding: utf-8

# # CSC338. Homework 7
# 
# Due Date: Wednesday March 11, 9pm
# 
# Please see the guidelines at https://www.cs.toronto.edu/~lczhang/338/homework.html
# 
# ### What to Hand In
# 
# Please hand in 2 files:
# 
# - Python File containing all your code, named `hw7.py`.
# - PDF file named `hw7_written.pdf` containing your solutions to the written parts of the assignment. Your solution can be hand-written, but must be legible. Graders may deduct marks for illegible or poorly presented solutions.
# 
# If you are using Jupyter Notebook to complete the work, your notebook can be exported as a .py file (File -> Download As -> Python). Your code will be auto-graded using Python 3.6, so please make sure that your code runs. There will be a 20% penalty if you need a remark due to small issues that renders your code untestable.
# 
# **Make sure to remove or comment out all matplotlib or other expensive code before submitting your homework!**
# 
# Submit the assignment on **MarkUs** by 9pm on the due date. See the syllabus for the course policy regarding late assignments. All assignments must be done individually.

# In[ ]:


import math
import numpy as np


# ## Question 1.
# 
# ### Part (a) -- 4 pt
# 
# Consider the problem of finding the roots of the functions $f_1$, $f_2$,
# $f_3$ and $f_4$.  What is the (absolute) condition number of each problem? 
# 
# 1. $f_1(x) = sin(\frac{x}{100})$, at $x = 0$
# 2. $f_2(x) = x^3 - 5x^2 + 8x - 4$, at $x = 2$
# 3. $f_3(x) = x cos(20x) - x$, at $x = 0$
# 4. $f_4(x) = x^3$, at $x = 0$
# 
# Include your solution in your PDF writeup. Show your work. 
# 
# ### Part (b) -- 6 pt
# 
# What is the convergence rate of each of the following sequences?
# Your answer should be either "linear", "superlinear but not quadratic",
# "quadratic", "cubic", or "something else".
# Include your solution in your PDF writeup. Show your work. 
# 
# 1. $x_n = 10^{-2n}$
# 2. $x_n = 2^{-n^2}$
# 3. $x_n = 2^{-n \log n}$
# 
# ## Question 2. Interval Bisection
# 
# ### Part (a) -- 4 pt
# 
# Write a function `bisect` that returns a list of intervals where
# the root of the function `f(x)` lies. Each interval should be half the size
# of the previous, and should be obtained using the interval bisection method.

# In[ ]:


def bisect(f, a, b, n):
    """Returns a list of length n+1 of intervals 
    where f(x) = 0 lies, where each interval is half 
    the size of the previous, and is obtained using
    the interval bisection method.
    
    Precondition: f continuous,
                  a < b
                  f(a) and f(b) have opposite signs
                  
    Example:
    >>> bisect(lambda x: x - 1, -0.5, 2, n=5)
    [(-0.5, 2),
     (0.75, 2),
     (0.75, 1.375),
     (0.75, 1.0625),
     (0.90625, 1.0625),
     (0.984375, 1.0625)]
    """


# ### Part (b) -- 4 pt
# 
# During lecture, we compared the following two computations of the midpoint between
# floating-point numbers a and b:

# In[ ]:


a = 5
b = 5.1

mid1 = a + (b - a) / 2
mid2 = (a + b) / 2


# Using a toy floating-point system, we saw in class
# that `mid2` can be outside of the range of [a, b].
# 
# Use the same idea to construct two floating-point values `float_a` and `float_b`
# where `(float_a + float_b) / 2` is not bewteen `float_a` and `float_b`.
# Recall that Python uses IEEE Double Precision
# for floating-point arithmetic (i.e., round to even in base 2 with a mantissa of 53 bits).
# 
# Discuss how you arrived at the answer in your PDF writeup.

# In[ ]:


float_a = 0
float_b = 0


# ### Part (c) -- 2pt
# 
# Suppose you would like to use the interval bisection method
# to find the root of a function $f(x)$, starting with an interval (a, b).
# 
# What is the minimum number of interval bisection iterations necessary
# to guarantee that your estimate of a root is 
# accurate to 10 decimal places?
# 
# Include your solution in your PDF writeup.
# 
# ## Question 4. Fixed-Point Iteration
# 
# ### Part (a) -- 4 pt
# 
# Write a function `fixed_point` to find the fixed-point of a function `f`
# by repeated application of `f`. The function should return a list of
# values `[x, f(x), f(f(x)), ...]`.

# In[ ]:


def fixed_point(f, x, n=20):
    """ Return a list lst = [x, f(x), f(f(x)), ...] with 
    `lst[i+1] = f(lst[i])` and `len(lst) == n + 1`
    
    >>> fixed_point(lambda x: math.sqrt(x + 1), 3, n=5)
    [3,
     2.0,
     1.7320508075688772,
     1.6528916502810695,
     1.6287699807772333,
     1.621348198499395]
    """


# ### Part (b) -- 6 pt
# 
# To find a root of the equation
# 
# $$f(x) = x^2 - 3x + 2 = 0$$
# 
# we can consider fixed-point problems involving the following different functions:
# 
# 1. $g_1(x) = \frac{x^2 + 2}{3}$
# 2. $g_2(x) = \sqrt{3x - 2}$
# 3. $g_3(x) = 3 - \frac{2}{x}$
# 
# Use the `fixed_point` function to generate the fixed-point iterations for
# each of these functions.
# Choose the starting value of $x$ to be $x_0 = 3$.
# 
# Does fixed-point iteration converge for each of the functions?
# Include the output of your call to `fixed_point` in your PDF writeup.
# If the iteration converges, what is the approximate the convergence rate
# of convergence?
# (linear, superliner, quadratic, etc).
# 
# Include your solution in your PDF writeup.