# 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.