root_finding/complex_newton.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Newton method for complex roots"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Consider the function\n",
    "$$\n",
    "f(x) = x^5 + 1\n",
    "$$\n",
    "The roots lie on the unit circle in the complex plane. We can write\n",
    "$$\n",
    "-1 = \\exp(i(2n+1)\\pi), \\qquad n=0,1,2,\\ldots\n",
    "$$\n",
    "The fifth roots are\n",
    "$$\n",
    "(-1)^{1/5} = \\exp(i(2n+1)\\pi/5), \\qquad n=0,1,2,3,4\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [],
   "source": [
    "%matplotlib inline\n",
    "%config InlineBackend.figure_format = 'svg'\n",
    "from numpy import abs,exp,array,real,imag,pi\n",
    "import matplotlib.pyplot as plt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Lets compute the exact roots and plot them on a graph."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(0.8090169943749475+0.5877852522924731j) (-1.0000000000000002+0j)\n",
      "(-0.30901699437494734+0.9510565162951536j) (-1+4.440892098500626e-16j)\n",
      "(-1+1.2246467991473532e-16j) (-1+6.123233995736766e-16j)\n",
      "(-0.30901699437494756-0.9510565162951535j) (-1+7.216449660063518e-16j)\n",
      "(0.8090169943749473-0.5877852522924732j) (-1+6.661338147750939e-16j)\n"
     ]
    },
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"utf-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       "  \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Created with matplotlib (http://matplotlib.org/) -->\n",
       "<svg height=\"252.018125pt\" version=\"1.1\" viewBox=\"0 0 393.204664 252.018125\" width=\"393.204664pt\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       " <defs>\n",
       "  <style type=\"text/css\">\n",
       "*{stroke-linecap:butt;stroke-linejoin:round;}\n",
       "  </style>\n",
       " </defs>\n",
       " <g id=\"figure_1\">\n",
       "  <g id=\"patch_1\">\n",
       "   <path d=\"M 0 252.018125 \n",
       "L 393.204664 252.018125 \n",
       "L 393.204664 0 \n",
       "L 0 0 \n",
       "z\n",
       "\" style=\"fill:none;\"/>\n",
       "  </g>\n",
       "  <g id=\"axes_1\">\n",
       "   <g id=\"patch_2\">\n",
       "    <path d=\"M 44.845313 228.14 \n",
       "L 379.645313 228.14 \n",
       "L 379.645313 10.7 \n",
       "L 44.845313 10.7 \n",
       "z\n",
       "\" style=\"fill:#ffffff;\"/>\n",
       "   </g>\n",
       "   <g id=\"matplotlib.axis_1\">\n",
       "    <g id=\"xtick_1\">\n",
       "     <g id=\"line2d_1\">\n",
       "      <path clip-path=\"url(#pd0419f1402)\" d=\"M 66.284993 228.14 \n",
       "L 66.284993 10.7 \n",
       "\" style=\"fill:none;stroke:#b0b0b0;stroke-linecap:square;stroke-width:0.8;\"/>\n",
       "     </g>\n",
       "     <g id=\"line2d_2\">\n",
       "      <defs>\n",
       "       <path d=\"M 0 0 \n",
       "L 0 3.5 \n",
       "\" id=\"m7709a9220b\" style=\"stroke:#000000;stroke-width:0.8;\"/>\n",
       "      </defs>\n",
       "      <g>\n",
       "       <use style=\"stroke:#000000;stroke-width:0.8;\" x=\"66.284993\" xlink:href=\"#m7709a9220b\" y=\"228.14\"/>\n",
       "      </g>\n",
       "     </g>\n",
       "     <g id=\"text_1\">\n",
       "      <!-- −1.5 -->\n",
       "      <defs>\n",
       "       <path d=\"M 10.59375 35.5 \n",
       "L 73.1875 35.5 \n",
       "L 73.1875 27.203125 \n",
       "L 10.59375 27.203125 \n",
       "z\n",
       "\" id=\"DejaVuSans-2212\"/>\n",
       "       <path d=\"M 12.40625 8.296875 \n",
       "L 28.515625 8.296875 \n",
       "L 28.515625 63.921875 \n",
       "L 10.984375 60.40625 \n",
       "L 10.984375 69.390625 \n",
       "L 28.421875 72.90625 \n",
       "L 38.28125 72.90625 \n",
       "L 38.28125 8.296875 \n",
       "L 54.390625 8.296875 \n",
       "L 54.390625 0 \n",
       "L 12.40625 0 \n",
       "z\n",
       "\" id=\"DejaVuSans-31\"/>\n",
       "       <path d=\"M 10.6875 12.40625 \n",
       "L 21 12.40625 \n",
       "L 21 0 \n",
       "L 10.6875 0 \n",
       "z\n",
       "\" id=\"DejaVuSans-2e\"/>\n",
       "       <path d=\"M 10.796875 72.90625 \n",
       "L 49.515625 72.90625 \n",
       "L 49.515625 64.59375 \n",
       "L 19.828125 64.59375 \n",
       "L 19.828125 46.734375 \n",
       "Q 21.96875 47.46875 24.109375 47.828125 \n",
       "Q 26.265625 48.1875 28.421875 48.1875 \n",
       "Q 40.625 48.1875 47.75 41.5 \n",
       "Q 54.890625 34.8125 54.890625 23.390625 \n",
       "Q 54.890625 11.625 47.5625 5.09375 \n",
       "Q 40.234375 -1.421875 26.90625 -1.421875 \n",
       "Q 22.3125 -1.421875 17.546875 -0.640625 \n",
       "Q 12.796875 0.140625 7.71875 1.703125 \n",
       "L 7.71875 11.625 \n",
       "Q 12.109375 9.234375 16.796875 8.0625 \n",
       "Q 21.484375 6.890625 26.703125 6.890625 \n",
       "Q 35.15625 6.890625 40.078125 11.328125 \n",
       "Q 45.015625 15.765625 45.015625 23.390625 \n",
       "Q 45.015625 31 40.078125 35.4375 \n",
       "Q 35.15625 39.890625 26.703125 39.890625 \n",
       "Q 22.75 39.890625 18.8125 39.015625 \n",
       "Q 14.890625 38.140625 10.796875 36.28125 \n",
       "z\n",
       "\" id=\"DejaVuSans-35\"/>\n",
       "      </defs>\n",
       "      <g transform=\"translate(54.143587 242.738437)scale(0.1 -0.1)\">\n",
       "       <use xlink:href=\"#DejaVuSans-2212\"/>\n",
       "       <use x=\"83.789062\" xlink:href=\"#DejaVuSans-31\"/>\n",
       "       <use x=\"147.412109\" xlink:href=\"#DejaVuSans-2e\"/>\n",
       "       <use x=\"179.199219\" xlink:href=\"#DejaVuSans-35\"/>\n",
       "      </g>\n",
       "     </g>\n",
       "    </g>\n",
       "    <g id=\"xtick_2\">\n",
       "     <g id=\"line2d_3\">\n",
       "      <path clip-path=\"url(#pd0419f1402)\" d=\"M 118.246345 228.14 \n",
       "L 118.246345 10.7 \n",
       "\" style=\"fill:none;stroke:#b0b0b0;stroke-linecap:square;stroke-width:0.8;\"/>\n",
       "     </g>\n",
       "     <g id=\"line2d_4\">\n",
       "      <g>\n",
       "       <use style=\"stroke:#000000;stroke-width:0.8;\" x=\"118.246345\" xlink:href=\"#m7709a9220b\" y=\"228.14\"/>\n",
       "      </g>\n",
       "     </g>\n",
       "     <g id=\"text_2\">\n",
       "      <!-- −1.0 -->\n",
       "      <defs>\n",
       "       <path d=\"M 31.78125 66.40625 \n",
       "Q 24.171875 66.40625 20.328125 58.90625 \n",
       "Q 16.5 51.421875 16.5 36.375 \n",
       "Q 16.5 21.390625 20.328125 13.890625 \n",
       "Q 24.171875 6.390625 31.78125 6.390625 \n",
       "Q 39.453125 6.390625 43.28125 13.890625 \n",
       "Q 47.125 21.390625 47.125 36.375 \n",
       "Q 47.125 51.421875 43.28125 58.90625 \n",
       "Q 39.453125 66.40625 31.78125 66.40625 \n",
       "z\n",
       "M 31.78125 74.21875 \n",
       "Q 44.046875 74.21875 50.515625 64.515625 \n",
       "Q 56.984375 54.828125 56.984375 36.375 \n",
       "Q 56.984375 17.96875 50.515625 8.265625 \n",
       "Q 44.046875 -1.421875 31.78125 -1.421875 \n",
       "Q 19.53125 -1.421875 13.0625 8.265625 \n",
       "Q 6.59375 17.96875 6.59375 36.375 \n",
       "Q 6.59375 54.828125 13.0625 64.515625 \n",
       "Q 19.53125 74.21875 31.78125 74.21875 \n",
       "z\n",
       "\" id=\"DejaVuSans-30\"/>\n",
       "      </defs>\n",
       "      <g transform=\"translate(106.104939 242.738437)scale(0.1 -0.1)\">\n",
       "       <use xlink:href=\"#DejaVuSans-2212\"/>\n",
       "       <use x=\"83.789062\" xlink:href=\"#DejaVuSans-31\"/>\n",
       "       <use x=\"147.412109\" xlink:href=\"#DejaVuSans-2e\"/>\n",
       "       <use x=\"179.199219\" xlink:href=\"#DejaVuSans-30\"/>\n",
       "      </g>\n",
       "     </g>\n",
       "    </g>\n",
       "    <g id=\"xtick_3\">\n",
       "     <g id=\"line2d_5\">\n",
       "      <path clip-path=\"url(#pd0419f1402)\" d=\"M 170.207696 228.14 \n",
       "L 170.207696 10.7 \n",
       "\" style=\"fill:none;stroke:#b0b0b0;stroke-linecap:square;stroke-width:0.8;\"/>\n",
       "     </g>\n",
       "     <g id=\"line2d_6\">\n",
       "      <g>\n",
       "       <use style=\"stroke:#000000;stroke-width:0.8;\" x=\"170.207696\" xlink:href=\"#m7709a9220b\" y=\"228.14\"/>\n",
       "      </g>\n",
       "     </g>\n",
       "     <g id=\"text_3\">\n",
       "      <!-- −0.5 -->\n",
       "      <g transform=\"translate(158.06629 242.738437)scale(0.1 -0.1)\">\n",
       "       <use xlink:href=\"#DejaVuSans-2212\"/>\n",
       "       <use x=\"83.789062\" xlink:href=\"#DejaVuSans-30\"/>\n",
       "       <use x=\"147.412109\" xlink:href=\"#DejaVuSans-2e\"/>\n",
       "       <use x=\"179.199219\" xlink:href=\"#DejaVuSans-35\"/>\n",
       "      </g>\n",
       "     </g>\n",
       "    </g>\n",
       "    <g id=\"xtick_4\">\n",
       "     <g id=\"line2d_7\">\n",
       "      <path clip-path=\"url(#pd0419f1402)\" d=\"M 222.169048 228.14 \n",
       "L 222.169048 10.7 \n",
       "\" style=\"fill:none;stroke:#b0b0b0;stroke-linecap:square;stroke-width:0.8;\"/>\n",
       "     </g>\n",
       "     <g id=\"line2d_8\">\n",
       "      <g>\n",
       "       <use style=\"stroke:#000000;stroke-width:0.8;\" x=\"222.169048\" xlink:href=\"#m7709a9220b\" y=\"228.14\"/>\n",
       "      </g>\n",
       "     </g>\n",
       "     <g id=\"text_4\">\n",
       "      <!-- 0.0 -->\n",
       "      <g transform=\"translate(214.217485 242.738437)scale(0.1 -0.1)\">\n",
       "       <use xlink:href=\"#DejaVuSans-30\"/>\n",
       "       <use x=\"63.623047\" xlink:href=\"#DejaVuSans-2e\"/>\n",
       "       <use x=\"95.410156\" xlink:href=\"#DejaVuSans-30\"/>\n",
       "      </g>\n",
       "     </g>\n",
       "    </g>\n",
       "    <g id=\"xtick_5\">\n",
       "     <g id=\"line2d_9\">\n",
       "      <path clip-path=\"url(#pd0419f1402)\" d=\"M 274.130399 228.14 \n",
       "L 274.130399 10.7 \n",
       "\" style=\"fill:none;stroke:#b0b0b0;stroke-linecap:square;stroke-width:0.8;\"/>\n",
       "     </g>\n",
       "     <g id=\"line2d_10\">\n",
       "      <g>\n",
       "       <use style=\"stroke:#000000;stroke-width:0.8;\" x=\"274.130399\" xlink:href=\"#m7709a9220b\" y=\"228.14\"/>\n",
       "      </g>\n",
       "     </g>\n",
       "     <g id=\"text_5\">\n",
       "      <!-- 0.5 -->\n",
       "      <g transform=\"translate(266.178836 242.738437)scale(0.1 -0.1)\">\n",
       "       <use xlink:href=\"#DejaVuSans-30\"/>\n",
       "       <use x=\"63.623047\" xlink:href=\"#DejaVuSans-2e\"/>\n",
       "       <use x=\"95.410156\" xlink:href=\"#DejaVuSans-35\"/>\n",
       "      </g>\n",
       "     </g>\n",
       "    </g>\n",
       "    <g id=\"xtick_6\">\n",
       "     <g id=\"line2d_11\">\n",
       "      <path clip-path=\"url(#pd0419f1402)\" d=\"M 326.09175 228.14 \n",
       "L 326.09175 10.7 \n",
       "\" style=\"fill:none;stroke:#b0b0b0;stroke-linecap:square;stroke-width:0.8;\"/>\n",
       "     </g>\n",
       "     <g id=\"line2d_12\">\n",
       "      <g>\n",
       "       <use style=\"stroke:#000000;stroke-width:0.8;\" x=\"326.09175\" xlink:href=\"#m7709a9220b\" y=\"228.14\"/>\n",
       "      </g>\n",
       "     </g>\n",
       "     <g id=\"text_6\">\n",
       "      <!-- 1.0 -->\n",
       "      <g transform=\"translate(318.140188 242.738437)scale(0.1 -0.1)\">\n",
       "       <use xlink:href=\"#DejaVuSans-31\"/>\n",
       "       <use x=\"63.623047\" xlink:href=\"#DejaVuSans-2e\"/>\n",
       "       <use x=\"95.410156\" xlink:href=\"#DejaVuSans-30\"/>\n",
       "      </g>\n",
       "     </g>\n",
       "    </g>\n",
       "    <g id=\"xtick_7\">\n",
       "     <g id=\"line2d_13\">\n",
       "      <path clip-path=\"url(#pd0419f1402)\" d=\"M 378.053102 228.14 \n",
       "L 378.053102 10.7 \n",
       "\" style=\"fill:none;stroke:#b0b0b0;stroke-linecap:square;stroke-width:0.8;\"/>\n",
       "     </g>\n",
       "     <g id=\"line2d_14\">\n",
       "      <g>\n",
       "       <use style=\"stroke:#000000;stroke-width:0.8;\" x=\"378.053102\" xlink:href=\"#m7709a9220b\" y=\"228.14\"/>\n",
       "      </g>\n",
       "     </g>\n",
       "     <g id=\"text_7\">\n",
       "      <!-- 1.5 -->\n",
       "      <g transform=\"translate(370.101539 242.738437)scale(0.1 -0.1)\">\n",
       "       <use xlink:href=\"#DejaVuSans-31\"/>\n",
       "       <use x=\"63.623047\" xlink:href=\"#DejaVuSans-2e\"/>\n",
       "       <use x=\"95.410156\" xlink:href=\"#DejaVuSans-35\"/>\n",
       "      </g>\n",
       "     </g>\n",
       "    </g>\n",
       "   </g>\n",
       "   <g id=\"matplotlib.axis_2\">\n",
       "    <g id=\"ytick_1\">\n",
       "     <g id=\"line2d_15\">\n",
       "      <path clip-path=\"url(#pd0419f1402)\" d=\"M 44.845313 223.342703 \n",
       "L 379.645313 223.342703 \n",
       "\" style=\"fill:none;stroke:#b0b0b0;stroke-linecap:square;stroke-width:0.8;\"/>\n",
       "     </g>\n",
       "     <g id=\"line2d_16\">\n",
       "      <defs>\n",
       "       <path d=\"M 0 0 \n",
       "L -3.5 0 \n",
       "\" id=\"me2c746f101\" style=\"stroke:#000000;stroke-width:0.8;\"/>\n",
       "      </defs>\n",
       "      <g>\n",
       "       <use style=\"stroke:#000000;stroke-width:0.8;\" x=\"44.845313\" xlink:href=\"#me2c746f101\" y=\"223.342703\"/>\n",
       "      </g>\n",
       "     </g>\n",
       "     <g id=\"text_8\">\n",
       "      <!-- −1.00 -->\n",
       "      <g transform=\"translate(7.2 227.141921)scale(0.1 -0.1)\">\n",
       "       <use xlink:href=\"#DejaVuSans-2212\"/>\n",
       "       <use x=\"83.789062\" xlink:href=\"#DejaVuSans-31\"/>\n",
       "       <use x=\"147.412109\" xlink:href=\"#DejaVuSans-2e\"/>\n",
       "       <use x=\"179.199219\" xlink:href=\"#DejaVuSans-30\"/>\n",
       "       <use x=\"242.822266\" xlink:href=\"#DejaVuSans-30\"/>\n",
       "      </g>\n",
       "     </g>\n",
       "    </g>\n",
       "    <g id=\"ytick_2\">\n",
       "     <g id=\"line2d_17\">\n",
       "      <path clip-path=\"url(#pd0419f1402)\" d=\"M 44.845313 197.362027 \n",
       "L 379.645313 197.362027 \n",
       "\" style=\"fill:none;stroke:#b0b0b0;stroke-linecap:square;stroke-width:0.8;\"/>\n",
       "     </g>\n",
       "     <g id=\"line2d_18\">\n",
       "      <g>\n",
       "       <use style=\"stroke:#000000;stroke-width:0.8;\" x=\"44.845313\" xlink:href=\"#me2c746f101\" y=\"197.362027\"/>\n",
       "      </g>\n",
       "     </g>\n",
       "     <g id=\"text_9\">\n",
       "      <!-- −0.75 -->\n",
       "      <defs>\n",
       "       <path d=\"M 8.203125 72.90625 \n",
       "L 55.078125 72.90625 \n",
       "L 55.078125 68.703125 \n",
       "L 28.609375 0 \n",
       "L 18.3125 0 \n",
       "L 43.21875 64.59375 \n",
       "L 8.203125 64.59375 \n",
       "z\n",
       "\" id=\"DejaVuSans-37\"/>\n",
       "      </defs>\n",
       "      <g transform=\"translate(7.2 201.161246)scale(0.1 -0.1)\">\n",
       "       <use xlink:href=\"#DejaVuSans-2212\"/>\n",
       "       <use x=\"83.789062\" xlink:href=\"#DejaVuSans-30\"/>\n",
       "       <use x=\"147.412109\" xlink:href=\"#DejaVuSans-2e\"/>\n",
       "       <use x=\"179.199219\" xlink:href=\"#DejaVuSans-37\"/>\n",
       "       <use x=\"242.822266\" xlink:href=\"#DejaVuSans-35\"/>\n",
       "      </g>\n",
       "     </g>\n",
       "    </g>\n",
       "    <g id=\"ytick_3\">\n",
       "     <g id=\"line2d_19\">\n",
       "      <path clip-path=\"url(#pd0419f1402)\" d=\"M 44.845313 171.381351 \n",
       "L 379.645313 171.381351 \n",
       "\" style=\"fill:none;stroke:#b0b0b0;stroke-linecap:square;stroke-width:0.8;\"/>\n",
       "     </g>\n",
       "     <g id=\"line2d_20\">\n",
       "      <g>\n",
       "       <use style=\"stroke:#000000;stroke-width:0.8;\" x=\"44.845313\" xlink:href=\"#me2c746f101\" y=\"171.381351\"/>\n",
       "      </g>\n",
       "     </g>\n",
       "     <g id=\"text_10\">\n",
       "      <!-- −0.50 -->\n",
       "      <g transform=\"translate(7.2 175.18057)scale(0.1 -0.1)\">\n",
       "       <use xlink:href=\"#DejaVuSans-2212\"/>\n",
       "       <use x=\"83.789062\" xlink:href=\"#DejaVuSans-30\"/>\n",
       "       <use x=\"147.412109\" xlink:href=\"#DejaVuSans-2e\"/>\n",
       "       <use x=\"179.199219\" xlink:href=\"#DejaVuSans-35\"/>\n",
       "       <use x=\"242.822266\" xlink:href=\"#DejaVuSans-30\"/>\n",
       "      </g>\n",
       "     </g>\n",
       "    </g>\n",
       "    <g id=\"ytick_4\">\n",
       "     <g id=\"line2d_21\">\n",
       "      <path clip-path=\"url(#pd0419f1402)\" d=\"M 44.845313 145.400676 \n",
       "L 379.645313 145.400676 \n",
       "\" style=\"fill:none;stroke:#b0b0b0;stroke-linecap:square;stroke-width:0.8;\"/>\n",
       "     </g>\n",
       "     <g id=\"line2d_22\">\n",
       "      <g>\n",
       "       <use style=\"stroke:#000000;stroke-width:0.8;\" x=\"44.845313\" xlink:href=\"#me2c746f101\" y=\"145.400676\"/>\n",
       "      </g>\n",
       "     </g>\n",
       "     <g id=\"text_11\">\n",
       "      <!-- −0.25 -->\n",
       "      <defs>\n",
       "       <path d=\"M 19.1875 8.296875 \n",
       "L 53.609375 8.296875 \n",
       "L 53.609375 0 \n",
       "L 7.328125 0 \n",
       "L 7.328125 8.296875 \n",
       "Q 12.9375 14.109375 22.625 23.890625 \n",
       "Q 32.328125 33.6875 34.8125 36.53125 \n",
       "Q 39.546875 41.84375 41.421875 45.53125 \n",
       "Q 43.3125 49.21875 43.3125 52.78125 \n",
       "Q 43.3125 58.59375 39.234375 62.25 \n",
       "Q 35.15625 65.921875 28.609375 65.921875 \n",
       "Q 23.96875 65.921875 18.8125 64.3125 \n",
       "Q 13.671875 62.703125 7.8125 59.421875 \n",
       "L 7.8125 69.390625 \n",
       "Q 13.765625 71.78125 18.9375 73 \n",
       "Q 24.125 74.21875 28.421875 74.21875 \n",
       "Q 39.75 74.21875 46.484375 68.546875 \n",
       "Q 53.21875 62.890625 53.21875 53.421875 \n",
       "Q 53.21875 48.921875 51.53125 44.890625 \n",
       "Q 49.859375 40.875 45.40625 35.40625 \n",
       "Q 44.1875 33.984375 37.640625 27.21875 \n",
       "Q 31.109375 20.453125 19.1875 8.296875 \n",
       "z\n",
       "\" id=\"DejaVuSans-32\"/>\n",
       "      </defs>\n",
       "      <g transform=\"translate(7.2 149.199894)scale(0.1 -0.1)\">\n",
       "       <use xlink:href=\"#DejaVuSans-2212\"/>\n",
       "       <use x=\"83.789062\" xlink:href=\"#DejaVuSans-30\"/>\n",
       "       <use x=\"147.412109\" xlink:href=\"#DejaVuSans-2e\"/>\n",
       "       <use x=\"179.199219\" xlink:href=\"#DejaVuSans-32\"/>\n",
       "       <use x=\"242.822266\" xlink:href=\"#DejaVuSans-35\"/>\n",
       "      </g>\n",
       "     </g>\n",
       "    </g>\n",
       "    <g id=\"ytick_5\">\n",
       "     <g id=\"line2d_23\">\n",
       "      <path clip-path=\"url(#pd0419f1402)\" d=\"M 44.845313 119.42 \n",
       "L 379.645313 119.42 \n",
       "\" style=\"fill:none;stroke:#b0b0b0;stroke-linecap:square;stroke-width:0.8;\"/>\n",
       "     </g>\n",
       "     <g id=\"line2d_24\">\n",
       "      <g>\n",
       "       <use style=\"stroke:#000000;stroke-width:0.8;\" x=\"44.845313\" xlink:href=\"#me2c746f101\" y=\"119.42\"/>\n",
       "      </g>\n",
       "     </g>\n",
       "     <g id=\"text_12\">\n",
       "      <!-- 0.00 -->\n",
       "      <g transform=\"translate(15.579688 123.219219)scale(0.1 -0.1)\">\n",
       "       <use xlink:href=\"#DejaVuSans-30\"/>\n",
       "       <use x=\"63.623047\" xlink:href=\"#DejaVuSans-2e\"/>\n",
       "       <use x=\"95.410156\" xlink:href=\"#DejaVuSans-30\"/>\n",
       "       <use x=\"159.033203\" xlink:href=\"#DejaVuSans-30\"/>\n",
       "      </g>\n",
       "     </g>\n",
       "    </g>\n",
       "    <g id=\"ytick_6\">\n",
       "     <g id=\"line2d_25\">\n",
       "      <path clip-path=\"url(#pd0419f1402)\" d=\"M 44.845313 93.439324 \n",
       "L 379.645313 93.439324 \n",
       "\" style=\"fill:none;stroke:#b0b0b0;stroke-linecap:square;stroke-width:0.8;\"/>\n",
       "     </g>\n",
       "     <g id=\"line2d_26\">\n",
       "      <g>\n",
       "       <use style=\"stroke:#000000;stroke-width:0.8;\" x=\"44.845313\" xlink:href=\"#me2c746f101\" y=\"93.439324\"/>\n",
       "      </g>\n",
       "     </g>\n",
       "     <g id=\"text_13\">\n",
       "      <!-- 0.25 -->\n",
       "      <g transform=\"translate(15.579688 97.238543)scale(0.1 -0.1)\">\n",
       "       <use xlink:href=\"#DejaVuSans-30\"/>\n",
       "       <use x=\"63.623047\" xlink:href=\"#DejaVuSans-2e\"/>\n",
       "       <use x=\"95.410156\" xlink:href=\"#DejaVuSans-32\"/>\n",
       "       <use x=\"159.033203\" xlink:href=\"#DejaVuSans-35\"/>\n",
       "      </g>\n",
       "     </g>\n",
       "    </g>\n",
       "    <g id=\"ytick_7\">\n",
       "     <g id=\"line2d_27\">\n",
       "      <path clip-path=\"url(#pd0419f1402)\" d=\"M 44.845313 67.458649 \n",
       "L 379.645313 67.458649 \n",
       "\" style=\"fill:none;stroke:#b0b0b0;stroke-linecap:square;stroke-width:0.8;\"/>\n",
       "     </g>\n",
       "     <g id=\"line2d_28\">\n",
       "      <g>\n",
       "       <use style=\"stroke:#000000;stroke-width:0.8;\" x=\"44.845313\" xlink:href=\"#me2c746f101\" y=\"67.458649\"/>\n",
       "      </g>\n",
       "     </g>\n",
       "     <g id=\"text_14\">\n",
       "      <!-- 0.50 -->\n",
       "      <g transform=\"translate(15.579688 71.257867)scale(0.1 -0.1)\">\n",
       "       <use xlink:href=\"#DejaVuSans-30\"/>\n",
       "       <use x=\"63.623047\" xlink:href=\"#DejaVuSans-2e\"/>\n",
       "       <use x=\"95.410156\" xlink:href=\"#DejaVuSans-35\"/>\n",
       "       <use x=\"159.033203\" xlink:href=\"#DejaVuSans-30\"/>\n",
       "      </g>\n",
       "     </g>\n",
       "    </g>\n",
       "    <g id=\"ytick_8\">\n",
       "     <g id=\"line2d_29\">\n",
       "      <path clip-path=\"url(#pd0419f1402)\" d=\"M 44.845313 41.477973 \n",
       "L 379.645313 41.477973 \n",
       "\" style=\"fill:none;stroke:#b0b0b0;stroke-linecap:square;stroke-width:0.8;\"/>\n",
       "     </g>\n",
       "     <g id=\"line2d_30\">\n",
       "      <g>\n",
       "       <use style=\"stroke:#000000;stroke-width:0.8;\" x=\"44.845313\" xlink:href=\"#me2c746f101\" y=\"41.477973\"/>\n",
       "      </g>\n",
       "     </g>\n",
       "     <g id=\"text_15\">\n",
       "      <!-- 0.75 -->\n",
       "      <g transform=\"translate(15.579688 45.277192)scale(0.1 -0.1)\">\n",
       "       <use xlink:href=\"#DejaVuSans-30\"/>\n",
       "       <use x=\"63.623047\" xlink:href=\"#DejaVuSans-2e\"/>\n",
       "       <use x=\"95.410156\" xlink:href=\"#DejaVuSans-37\"/>\n",
       "       <use x=\"159.033203\" xlink:href=\"#DejaVuSans-35\"/>\n",
       "      </g>\n",
       "     </g>\n",
       "    </g>\n",
       "    <g id=\"ytick_9\">\n",
       "     <g id=\"line2d_31\">\n",
       "      <path clip-path=\"url(#pd0419f1402)\" d=\"M 44.845313 15.497297 \n",
       "L 379.645313 15.497297 \n",
       "\" style=\"fill:none;stroke:#b0b0b0;stroke-linecap:square;stroke-width:0.8;\"/>\n",
       "     </g>\n",
       "     <g id=\"line2d_32\">\n",
       "      <g>\n",
       "       <use style=\"stroke:#000000;stroke-width:0.8;\" x=\"44.845313\" xlink:href=\"#me2c746f101\" y=\"15.497297\"/>\n",
       "      </g>\n",
       "     </g>\n",
       "     <g id=\"text_16\">\n",
       "      <!-- 1.00 -->\n",
       "      <g transform=\"translate(15.579688 19.296516)scale(0.1 -0.1)\">\n",
       "       <use xlink:href=\"#DejaVuSans-31\"/>\n",
       "       <use x=\"63.623047\" xlink:href=\"#DejaVuSans-2e\"/>\n",
       "       <use x=\"95.410156\" xlink:href=\"#DejaVuSans-30\"/>\n",
       "       <use x=\"159.033203\" xlink:href=\"#DejaVuSans-30\"/>\n",
       "      </g>\n",
       "     </g>\n",
       "    </g>\n",
       "   </g>\n",
       "   <g id=\"line2d_33\">\n",
       "    <defs>\n",
       "     <path d=\"M 0 3 \n",
       "C 0.795609 3 1.55874 2.683901 2.12132 2.12132 \n",
       "C 2.683901 1.55874 3 0.795609 3 0 \n",
       "C 3 -0.795609 2.683901 -1.55874 2.12132 -2.12132 \n",
       "C 1.55874 -2.683901 0.795609 -3 0 -3 \n",
       "C -0.795609 -3 -1.55874 -2.683901 -2.12132 -2.12132 \n",
       "C -2.683901 -1.55874 -3 -0.795609 -3 0 \n",
       "C -3 0.795609 -2.683901 1.55874 -2.12132 2.12132 \n",
       "C -1.55874 2.683901 -0.795609 3 0 3 \n",
       "z\n",
       "\" id=\"m516fecb3ce\" style=\"stroke:#1f77b4;\"/>\n",
       "    </defs>\n",
       "    <g clip-path=\"url(#pd0419f1402)\">\n",
       "     <use style=\"fill:#1f77b4;stroke:#1f77b4;\" x=\"306.24428\" xlink:href=\"#m516fecb3ce\" y=\"58.335768\"/>\n",
       "     <use style=\"fill:#1f77b4;stroke:#1f77b4;\" x=\"190.055166\" xlink:href=\"#m516fecb3ce\" y=\"20.583636\"/>\n",
       "     <use style=\"fill:#1f77b4;stroke:#1f77b4;\" x=\"118.246345\" xlink:href=\"#m516fecb3ce\" y=\"119.42\"/>\n",
       "     <use style=\"fill:#1f77b4;stroke:#1f77b4;\" x=\"190.055166\" xlink:href=\"#m516fecb3ce\" y=\"218.256364\"/>\n",
       "     <use style=\"fill:#1f77b4;stroke:#1f77b4;\" x=\"306.24428\" xlink:href=\"#m516fecb3ce\" y=\"180.504232\"/>\n",
       "    </g>\n",
       "   </g>\n",
       "   <g id=\"patch_3\">\n",
       "    <path d=\"M 44.845313 228.14 \n",
       "L 44.845313 10.7 \n",
       "\" style=\"fill:none;stroke:#000000;stroke-linecap:square;stroke-linejoin:miter;stroke-width:0.8;\"/>\n",
       "   </g>\n",
       "   <g id=\"patch_4\">\n",
       "    <path d=\"M 379.645313 228.14 \n",
       "L 379.645313 10.7 \n",
       "\" style=\"fill:none;stroke:#000000;stroke-linecap:square;stroke-linejoin:miter;stroke-width:0.8;\"/>\n",
       "   </g>\n",
       "   <g id=\"patch_5\">\n",
       "    <path d=\"M 44.845313 228.14 \n",
       "L 379.645313 228.14 \n",
       "\" style=\"fill:none;stroke:#000000;stroke-linecap:square;stroke-linejoin:miter;stroke-width:0.8;\"/>\n",
       "   </g>\n",
       "   <g id=\"patch_6\">\n",
       "    <path d=\"M 44.845313 10.7 \n",
       "L 379.645313 10.7 \n",
       "\" style=\"fill:none;stroke:#000000;stroke-linecap:square;stroke-linejoin:miter;stroke-width:0.8;\"/>\n",
       "   </g>\n",
       "  </g>\n",
       " </g>\n",
       " <defs>\n",
       "  <clipPath id=\"pd0419f1402\">\n",
       "   <rect height=\"217.44\" width=\"334.8\" x=\"44.845313\" y=\"10.7\"/>\n",
       "  </clipPath>\n",
       " </defs>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "n = array([0,1,2,3,4])\n",
    "r = exp(1j*(2*n+1)*pi/5) # 5'th roots of -1\n",
    "plt.plot(real(r),imag(r),'o')\n",
    "plt.grid(True)\n",
    "plt.axis('equal')\n",
    "for x in r:\n",
    "    print(x,x**5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Define the function and its derivative."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [],
   "source": [
    "def f(x):\n",
    "    return x**5 + 1.0\n",
    "\n",
    "def df(x):\n",
    "    return 5.0*x**4"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now implement Newton method as a function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [],
   "source": [
    "def newton(f,df,x0,M=100,eps=1.0e-15):\n",
    "    x = x0\n",
    "    for i in range(M):\n",
    "        dx = - f(x)/df(x)\n",
    "        x  = x + dx\n",
    "        print(i,x,abs(f(x)))\n",
    "        if abs(dx) < eps * abs(x):\n",
    "            return x"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We call Newton method with a complex initial guess for the root."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 (0.85+0.8j) 1.4844926068747277\n",
      "1 (0.7869450486819533+0.6530228729743794j) 0.3587868496977192\n",
      "2 (0.8000098256925355+0.5887168663596131j) 0.04466991909204323\n",
      "3 (0.8091271135998733+0.587660739881959j) 0.0008311338875735857\n",
      "4 (0.8090169566882729+0.5877852118808937j) 2.762870121656608e-07\n",
      "5 (0.8090169943749507+0.5877852522924782j) 3.014107274014632e-14\n",
      "6 (0.8090169943749475+0.5877852522924731j) 2.220446049250313e-16\n",
      "7 (0.8090169943749475+0.5877852522924731j) 2.220446049250313e-16\n",
      "Root =  (0.8090169943749475+0.5877852522924731j)\n"
     ]
    }
   ],
   "source": [
    "x0 = 1.0 + 1.0j\n",
    "x = newton(f,df,x0)\n",
    "print('Root = ',x)"
   ]
  }
 ],
 "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.6.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}