{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# CSC338. Homework 7\n",
    "\n",
    "Due Date: Wednesday March 11, 9pm\n",
    "\n",
    "Please see the guidelines at https://www.cs.toronto.edu/~lczhang/338/homework.html\n",
    "\n",
    "### What to Hand In\n",
    "\n",
    "Please hand in 2 files:\n",
    "\n",
    "- Python File containing all your code, named `hw7.py`.\n",
    "- 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.\n",
    "\n",
    "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.\n",
    "\n",
    "**Make sure to remove or comment out all matplotlib or other expensive code before submitting your homework!**\n",
    "\n",
    "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."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import math\n",
    "import numpy as np"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Question 1.\n",
    "\n",
    "### Part (a) -- 4 pt\n",
    "\n",
    "Consider the problem of finding the roots of the functions $f_1$, $f_2$,\n",
    "$f_3$ and $f_4$.  What is the (absolute) condition number of each problem? \n",
    "\n",
    "1. $f_1(x) = sin(\\frac{x}{100})$, at $x = 0$\n",
    "2. $f_2(x) = x^3 - 5x^2 + 8x - 4$, at $x = 2$\n",
    "3. $f_3(x) = x cos(20x) - x$, at $x = 0$\n",
    "4. $f_4(x) = x^3$, at $x = 0$\n",
    "\n",
    "Include your solution in your PDF writeup. Show your work. \n",
    "\n",
    "### Part (b) -- 6 pt\n",
    "\n",
    "What is the convergence rate of each of the following sequences?\n",
    "Your answer should be either \"linear\", \"superlinear but not quadratic\",\n",
    "\"quadratic\", \"cubic\", or \"something else\".\n",
    "Include your solution in your PDF writeup. Show your work. \n",
    "\n",
    "1. $x_n = 10^{-2n}$\n",
    "2. $x_n = 2^{-n^2}$\n",
    "3. $x_n = 2^{-n \\log n}$\n",
    "\n",
    "## Question 2. Interval Bisection\n",
    "\n",
    "### Part (a) -- 4 pt\n",
    "\n",
    "Write a function `bisect` that returns a list of intervals where\n",
    "the root of the function `f(x)` lies. Each interval should be half the size\n",
    "of the previous, and should be obtained using the interval bisection method."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def bisect(f, a, b, n):\n",
    "    \"\"\"Returns a list of length n+1 of intervals \n",
    "    where f(x) = 0 lies, where each interval is half \n",
    "    the size of the previous, and is obtained using\n",
    "    the interval bisection method.\n",
    "    \n",
    "    Precondition: f continuous,\n",
    "                  a < b\n",
    "                  f(a) and f(b) have opposite signs\n",
    "                  \n",
    "    Example:\n",
    "    >>> bisect(lambda x: x - 1, -0.5, 2, n=5)\n",
    "    [(-0.5, 2),\n",
    "     (0.75, 2),\n",
    "     (0.75, 1.375),\n",
    "     (0.75, 1.0625),\n",
    "     (0.90625, 1.0625),\n",
    "     (0.984375, 1.0625)]\n",
    "    \"\"\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Part (b) -- 4 pt\n",
    "\n",
    "During lecture, we compared the following two computations of the midpoint between\n",
    "floating-point numbers a and b:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "a = 5\n",
    "b = 5.1\n",
    "\n",
    "mid1 = a + (b - a) / 2\n",
    "mid2 = (a + b) / 2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Using a toy floating-point system, we saw in class\n",
    "that `mid2` can be outside of the range of [a, b].\n",
    "\n",
    "Use the same idea to construct two floating-point values `float_a` and `float_b`\n",
    "where `(float_a + float_b) / 2` is not bewteen `float_a` and `float_b`.\n",
    "Recall that Python uses IEEE Double Precision\n",
    "for floating-point arithmetic (i.e., round to even in base 2 with a mantissa of 53 bits).\n",
    "\n",
    "Discuss how you arrived at the answer in your PDF writeup."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "float_a = 0\n",
    "float_b = 0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Part (c) -- 2pt\n",
    "\n",
    "Suppose you would like to use the interval bisection method\n",
    "to find the root of a function $f(x)$, starting with an interval (a, b).\n",
    "\n",
    "What is the minimum number of interval bisection iterations necessary\n",
    "to guarantee that your estimate of a root is \n",
    "accurate to 10 decimal places?\n",
    "\n",
    "Include your solution in your PDF writeup.\n",
    "\n",
    "## Question 4. Fixed-Point Iteration\n",
    "\n",
    "### Part (a) -- 4 pt\n",
    "\n",
    "Write a function `fixed_point` to find the fixed-point of a function `f`\n",
    "by repeated application of `f`. The function should return a list of\n",
    "values `[x, f(x), f(f(x)), ...]`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def fixed_point(f, x, n=20):\n",
    "    \"\"\" Return a list lst = [x, f(x), f(f(x)), ...] with \n",
    "    `lst[i+1] = f(lst[i])` and `len(lst) == n + 1`\n",
    "    \n",
    "    >>> fixed_point(lambda x: math.sqrt(x + 1), 3, n=5)\n",
    "    [3,\n",
    "     2.0,\n",
    "     1.7320508075688772,\n",
    "     1.6528916502810695,\n",
    "     1.6287699807772333,\n",
    "     1.621348198499395]\n",
    "    \"\"\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Part (b) -- 6 pt\n",
    "\n",
    "To find a root of the equation\n",
    "\n",
    "$$f(x) = x^2 - 3x + 2 = 0$$\n",
    "\n",
    "we can consider fixed-point problems involving the following different functions:\n",
    "\n",
    "1. $g_1(x) = \\frac{x^2 + 2}{3}$\n",
    "2. $g_2(x) = \\sqrt{3x - 2}$\n",
    "3. $g_3(x) = 3 - \\frac{2}{x}$\n",
    "\n",
    "Use the `fixed_point` function to generate the fixed-point iterations for\n",
    "each of these functions.\n",
    "Choose the starting value of $x$ to be $x_0 = 3$.\n",
    "\n",
    "Does fixed-point iteration converge for each of the functions?\n",
    "Include the output of your call to `fixed_point` in your PDF writeup.\n",
    "If the iteration converges, what is the approximate the convergence rate\n",
    "of convergence?\n",
    "(linear, superliner, quadratic, etc).\n",
    "\n",
    "Include your solution in your PDF writeup."
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}