{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# CSC338. Homework 8\n",
    "\n",
    "Due Date: Wednesday March 18, 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 `hw8.py`.\n",
    "- PDF file named `hw8_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. Fixed-Point Iteration -- 3pts\n",
    "\n",
    "In homework 7, we considered using fixed-point iteration to find a root of the equation\n",
    "$f(x) = x^2 - 3x + 2 = 0$ using these 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",
    "Analyze the convergence properties of each of the corresponding fixed-point iteration schemes\n",
    "for the root x = 2 by analyzing $g_i'(x)$.\n",
    "Do you expect the fix-point iteration to diverge or converge?\n",
    "Do these expectations match your empirical results from homework 7?\n",
    "\n",
    "## Question 2. Newton's Method\n",
    "\n",
    "### Part (a) -- 4 pts\n",
    "\n",
    "Write a function `newton` to find a root of `f(x)` using Newton's Method.\n",
    "This Python function should take as argument both the mathematical function `f` and \n",
    "its derivative `df`, and return a list of successively better estimates of a\n",
    "root of `f` obtained from applying Newton's method."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def newton(f, df, x, n=5):\n",
    "    \"\"\" Return a list of successively better estimate of a root of `f` \n",
    "    obtained from applying Newton's method. The argument `df` is the\n",
    "    derivative of the function `f`. The argument `x` is the initial estimate\n",
    "    of the root. The length of the returned list is `n + 1`.\n",
    "    \n",
    "    Precondition: f is continuous and differentiable\n",
    "                  df is the derivative of f\n",
    "    \n",
    "    >>> def f(x):\n",
    "    ...     return x * x - 4 * np.sin(x)\n",
    "    >>> def df(x):\n",
    "    ...     return 2 * x - 4 * np.cos(x)\n",
    "    >>> newton(f, df, 3, n=5)\n",
    "    [3,\n",
    "     2.1530576920133857,\n",
    "     1.9540386420058038,\n",
    "     1.9339715327520701,\n",
    "     1.933753788557627,\n",
    "     1.9337537628270216]\n",
    "    \"\"\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Part (b) -- 2 pts\n",
    "\n",
    "Use your function from part (a) to solve for a root of\n",
    "\n",
    "$$f(x) = x^2 - 3x + 2 = 0$$\n",
    "\n",
    "Start with $x_0$ = 3, and stop when the root is accurate to at least 8 significant decimal digits.\n",
    "\n",
    "Show your work in your python file, and store the root you find in the variable `newton_root`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def f(x):\n",
    "    return x ** 2 - 3 * x + 2\n",
    "\n",
    "newton_root = None"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Part (c) -- 6 pts\n",
    "\n",
    "Consider the following non-linear equations $h_i(x) = 0$.\n",
    "\n",
    "1. $h_1(x) = x^3 - 5x^2 + 8x - 4$\n",
    "2. $h_2(x) = x cos(20x) - x$\n",
    "3. $h_3(x) = e^{-2x} + e^{x} - x - 4$\n",
    "\n",
    "Write out the statement for updating the iterate $x_k$ using Newton’s\n",
    "method for solving each of the equations $h_i(x) = 0$.\n",
    "\n",
    "For each $h_i$, do you expect Newton's method to converge?\n",
    " \n",
    "Include your solution in your PDF writeup.\n",
    "\n",
    "\n",
    "### Part (d) -- 3 pt\n",
    "\n",
    "Use the `newton` function to try and solve $h_i(x) = 0$, for `n = 100` iterations, starting with `x = 1.5`.\n",
    "\n",
    "Save the return values of calls to the function `newton` to the variables `newton_h1`,  `newton_h2`,  `newton_h3`,."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "newton_h1 = None\n",
    "newton_h2 = None\n",
    "newton_h3 = None"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Question 3. Secant Method\n",
    "\n",
    "### Part (a) [5 pt]\n",
    "\n",
    "Write a function `secant` to find a root of `f(x)` using the secant method.\n",
    "The function should return a list of successively better estimates of a\n",
    "root of `f` obtained from applying the secant method."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def secant(f, x0, x1, n=5):\n",
    "    \"\"\" Return a list of successively better estimate of a root of `f` \n",
    "    obtained from applying secant method. The arguments `x0` and `x1` are\n",
    "    the two starting guesses. The length of the returned list is `n + 2`.\n",
    "    \n",
    "    >>> secant(lambda x: x ** 2 + x - 4, 3, 2, n=6)\n",
    "    [3,\n",
    "     2,\n",
    "     1.6666666666666667,\n",
    "     1.5714285714285714,\n",
    "     1.5617977528089888,\n",
    "     1.5615533980582523,\n",
    "     1.561552812843596,\n",
    "     1.5615528128088303]\n",
    "    \"\"\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Part (b) [1 pt]\n",
    "\n",
    "Use the `secant` function to find a root of $f(x) = x^3 + x^2 + x - 4$,\n",
    "accurate up to 8 significant decimal digits.\n",
    "\n",
    "Show your work in your Python file. You can choose starting positions $x_0$\n",
    "and $x_1$.\n",
    "\n",
    "Save the result in the variable `secant_root`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "secant_root = None"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Part (c) [4 pt]\n",
    "\n",
    "Show that the iterative method\n",
    "\n",
    "$$x_{k+1} = \\frac{x_{k-1} f(x_k) - x_k f(x_{k-1})}{f(x_k) - f(x_{k-1})}$$\n",
    "\n",
    "is mathematically equivalent to the secant method for solving a scalar nonlinear equation $f(x) = 0$.\n",
    "\n",
    "Include your solution in your PDF writeup.\n",
    "\n",
    "\n",
    "### Part (d) [2 pt]\n",
    "\n",
    "When implemented in finite-precision floating-point arithmetic, what advantages or disadvantages\n",
    "does the formula given in part (c) have compared with the formula for the secant method\n",
    "given in lecture?\n",
    "\n",
    "This is the formula given in lecture:\n",
    "\n",
    "$$x_{k+1} = x_k - f(x_k)\\frac{x_k - x_{k-1}}{f(x_k) - f(x_{k-1})}$$\n",
    "\n",
    "Include your solution in your PDF writeup."
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}