{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Newton's Method ##\n",
    "\n",
    "Newton's Method is a technique for approximating a root to an equation of the form $f(x)=0$.  What is required is an initial estimate for the root, called $x_1$, and an iterative formula:\n",
    "\n",
    "$$x_{n+1} = x_n - \\frac{f(x_n)}{f^{\\prime}(x_n)}$$\n",
    "\n",
    "This produces a sequence $x_1, x_2, x_3, \\ldots $ which converges to the root (hopefully).\n",
    "\n",
    "\n",
    "\n",
    "An implementation of Newton's Method is shown in the code block below.  You can change the function $f$, and the initial\n",
    "guess $x_1$. Clicking evaluate will run two iterations of Newton's method and return the next two approximations.  Feel free to add some more lines\n",
    "of code to find more iterations - just duplicate the last two lines of code and update the index:\n",
    "\n",
    "```python\n",
    "x4=NewtonIt(x3);\n",
    "print(x4);\n",
    "```\n",
    "\n",
    "### Run the calculations yourself...###"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "0.8700736957962091\n",
      "0.8712214142629191\n"
     ]
    }
   ],
   "source": [
    "import math\n",
    "import numpy as np\n",
    "from sympy import *\n",
    "\n",
    "x = Symbol('x');              # declare the variable for function\n",
    "y = cos(x)+5*x-5;             # change this to whatever function you like\n",
    "dy = y.diff(x);               # python will compute the derivative of y\n",
    "f = lambdify(x, y, 'numpy')   # convert y to a lambda function f so we can evaluate it as 'f(4)', etc.\n",
    "df = lambdify(x, dy, 'numpy') # convert dy to a lambda function df so we can evaluate it as 'df(4)', etc.\n",
    "def NewtonIt(x):\n",
    "    return x-(f(x)/df(x));  # Newtons Iterative Formula which we are calling \"NewtonIt\"\n",
    "\n",
    "x1=1;                   # initial guess\n",
    "print(x1);              # prints x1 in output window below\n",
    "x2=NewtonIt(x1);        # one iteration of Newtons Method - output below\n",
    "print(x2);\n",
    "x3=NewtonIt(x2);        # a second iteration of Newtons Method\n",
    "print(x3);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " <aside class=\"callout panel panel-info\">\n",
    " <div class=\"panel-heading\">\n",
    " <h3 id=\"sage-syntax\">Syntax for entering mathematical expressions in Python (`sympy`, `numpy`)</h3>\n",
    " </div>\n",
    " <div class=\"panel-body\">\n",
    " <p><ul>\n",
    "\t <li><p> Use `*` for multiplication, for example 10x would be input as `10*x`. </p></li>\n",
    "\t <li><p> Powers of x are input using `**`.  For example the square function $x^2$ is input as `x**2`.</p></li>\n",
    "\t <li><p> The exponential function $e^x$ is input as `exp(x)`. </p></li>\n",
    "\t <li><p> The natural logarithm $\\ln(x)$ (i.e. base e) is input as `log(x)` or `ln(x)`.</p></li>\n",
    " </ul>\n",
    " </div>\n",
    " </aside>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h3> Using a loop to compute more iterations...</h3>\n",
    "\n",
    "If you have Python programming experience you could write a `for` loop to automate the iterations. Replace everything from the initial guess (line 6 and below) down with something like:\n",
    "\n",
    "```python\n",
    "xn=1;                      # initial guess\n",
    "print(xn);\n",
    "for i in range(10):\n",
    "    xn=NewtonIt(xn)\n",
    "    print('{:.20f}'.format(xn));\n",
    "```\n",
    "\n",
    "This will produce 10 iterations, each value shown to 20 decimal places.  <br><br>\n",
    "\n",
    "You could get even fancier and run a `while` loop where the stopping condition is that two iterations agree to some specified number of decimal places.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "0.87007369579620907896\n",
      "0.87122141426291910271\n",
      "0.87122151449508777876\n",
      "0.87122151449508866694\n",
      "0.87122151449508844490\n",
      "0.87122151449508866694\n",
      "0.87122151449508844490\n",
      "0.87122151449508866694\n",
      "0.87122151449508844490\n",
      "0.87122151449508866694\n"
     ]
    }
   ],
   "source": [
    "import math\n",
    "import numpy as np\n",
    "from sympy import *\n",
    "\n",
    "x = Symbol('x');              # declare the variable for function\n",
    "y = cos(x)+5*x-5;             # change this to whatever function you like\n",
    "dy = y.diff(x);               # python will compute the derivative of y\n",
    "f = lambdify(x, y, 'numpy')   # convert y to a lambda function f so we can evaluate it as 'f(4)', etc.\n",
    "df = lambdify(x, dy, 'numpy') # convert dy to a lambda function df so we can evaluate it as 'df(4)', etc.\n",
    "def NewtonIt(x):\n",
    "    return x-(f(x)/df(x));  # Newtons Iterative Formula which we are calling \"NewtonIt\"\n",
    "\n",
    "xn = 1;                      # initial guess\n",
    "print(xn);\n",
    "for i in range(10):\n",
    "    xn=NewtonIt(xn)\n",
    "    print('{:.20f}'.format(xn));"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}