{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Newton's Method - Illustrative Examples\n", "\n", "This code illustrate Newton's method for various functions defined below. In particular, it contains a few examples which show the importance of every hypothesis in the theoretical quadratic convergence result." ] }, { "cell_type": "code", "execution_count": 42, "metadata": {}, "outputs": [], "source": [ "import numpy as np\n", "import pylab as pl\n", "import matplotlib.pyplot as plt\n", "plt.rcParams['figure.dpi']= 100 # parameter for resolution of graphics\n", "import time\n", "\n", "v = 1 # variant corresponding to the number of the function below\n", "Niter = 10 # Number of iterations\n", "x0 = -1 # Initialization\n", "a = -2.5 # Lower bound for the plot interval\n", "b = 2.5 # Upper bound for the plot interval" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Various objective functions\n", "\n", "Here we consider multiple functions to be tested with Newton's method\n", "\n", "Case 0: $f(x) = x^2$ (quadratic function, convergence in $1$ iteration)\n", "\n", "Case 1: $f(x) = x^6/6-x^2/2+x$ (here the choice of the initialization is important)\n", "\n", "Case 2: $f(x) = x^2-\\sin x$ \n", "\n", "Case 3: $f(x) = x^2+\\exp x$\n", "\n", "Case 4: $f(x) = x^4$ (this does not verify the non-degeneracy hypothesis: quadratic convergence is not attained)\n", "\n", "Case 5: $f(x) = \\sqrt{1+x^2}$ (here the choice of initialization is important: for $|x|<1$ we have cubic convergence, while for $|x|\\geq 1$ the algorithm diverges)" ] }, { "cell_type": "code", "execution_count": 43, "metadata": {}, "outputs": [], "source": [ "def fun(x,v): # function definition\n", " if v==0:\n", " return x**2\n", " if v==1:\n", " return x**6/6-x**2/2+x\n", " if v==2:\n", " return x**2-np.sin(x)\n", " if v==3:\n", " return x**2+np.exp(x)\n", " if v==4:\n", " return x**4\n", " if v==5:\n", " return np.sqrt(1+x**2)\n", "def der(x,v): # first derivative\n", " if v==0:\n", " return 2*x\n", " if v==1:\n", " return x**5-x+1\n", " if v==2:\n", " return 2*x-np.cos(x)\n", " if v==3: \n", " return 2*x+np.exp(x)\n", " if v==4:\n", " return 4*x**3\n", " if v==5:\n", " return x/np.sqrt(1+x**2)\n", "def der2(x,v): # second derivative\n", " if v==0: \n", " return 2\n", " if v==1:\n", " return 5*x**4-1\n", " if v==2: \n", " return 2+np.sin(x)\n", " if v==3:\n", " return 2+np.exp(x)\n", " if v==4:\n", " return 12*x**2\n", " if v==5:\n", " return 1/np.sqrt(1+x**2)**3\n", "\n", "# List of optimizers for the above functions\n", "if v==0:\n", " analytic = 0\n", "if v==1:\n", " analytic = -1.1673039782614187\n", "if v==2:\n", " analytic = 0.45018361129487355\n", "if v==3:\n", " analytic = -0.35173371124919584\n", "if v==4:\n", " analytic = 0\n", "if v==5:\n", " analytic = 0" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Algorithm: Newton method in dimension one\n", "\n", "