{ "metadata": { "name": "", "signature": "sha256:018a9288f4317a3a026f1dfc2a2e2b094aa1e333673a00eb40cf15a309c57608" }, "nbformat": 3, "nbformat_minor": 0, "worksheets": [ { "cells": [ { "cell_type": "heading", "level": 1, "metadata": {}, "source": [ "Newton method with double root" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Consider the function\n", "$$\n", "f(x) = (x-1)^2 \\sin(x)\n", "$$\n", "for which $x=1$ is a double root." ] }, { "cell_type": "code", "collapsed": false, "input": [ "from numpy import sin,cos,linspace,zeros,abs\n", "from matplotlib.pyplot import plot,xlabel,ylabel" ], "language": "python", "metadata": {}, "outputs": [], "prompt_number": 35 }, { "cell_type": "code", "collapsed": false, "input": [ "def f(x):\n", " return (x-1.0)**2 * sin(x)\n", "\n", "def df(x):\n", " return 2.0*(x-1.0)*sin(x) + (x-1.0)**2 * cos(x)" ], "language": "python", "metadata": {}, "outputs": [], "prompt_number": 36 }, { "cell_type": "code", "collapsed": false, "input": [ "x = linspace(0.0,2.0,100)\n", "plot(x,f(x))\n", "xlabel('x')\n", "ylabel('f(x)')" ], "language": "python", "metadata": {}, "outputs": [ { "metadata": {}, "output_type": "pyout", "prompt_number": 37, "text": [ "" ] }, { "metadata": {}, "output_type": "display_data", "svg": [ "\n", "\n", "\n", "\n" ], "text": [ "" ] } ], "prompt_number": 37 }, { "cell_type": "code", "collapsed": false, "input": [ "def newton(x0,m):\n", " n = 50\n", " x = zeros(50)\n", " x[0] = x0\n", " print \"%6d %24.14e\" % (0,x[0])\n", " for i in range(1,50):\n", " x[i] = x[i-1] - m*f(x[i-1])/df(x[i-1])\n", " if i > 1:\n", " r = (x[i] - x[i-1])/(x[i-1]-x[i-2])\n", " else:\n", " r = 0.0\n", " print \"%6d %24.14e %14.6e\" % (i,x[i],r)\n", " if abs(f(x[i])) < 1.0e-16:\n", " break" ], "language": "python", "metadata": {}, "outputs": [], "prompt_number": 38 }, { "cell_type": "markdown", "metadata": {}, "source": [ "We first apply the standard newton method." ] }, { "cell_type": "code", "collapsed": false, "input": [ "newton(2.0,1)" ], "language": "python", "metadata": {}, "outputs": [ { "output_type": "stream", "stream": "stdout", "text": [ " 0 2.00000000000000e+00\n", " 1 1.35163555744248e+00 0.000000e+00\n", " 2 1.18244356861394e+00 2.609520e-01\n", " 3 1.09450383817604e+00 5.197630e-01\n", " 4 1.04837639635805e+00 5.245347e-01\n", " 5 1.02452044172239e+00 5.171749e-01\n", " 6 1.01235093391487e+00 5.101245e-01\n", " 7 1.00619920246051e+00 5.055037e-01\n", " 8 1.00310567444820e+00 5.028711e-01\n", " 9 1.00155437342780e+00 5.014666e-01\n", " 10 1.00077757303341e+00 5.007412e-01\n", " 11 1.00038888338214e+00 5.003726e-01\n", " 12 1.00019446594325e+00 5.001868e-01\n", " 13 1.00009723903915e+00 5.000935e-01\n", " 14 1.00004862103702e+00 5.000468e-01\n", " 15 1.00002431089794e+00 5.000234e-01\n", " 16 1.00001215554384e+00 5.000117e-01\n", " 17 1.00000607779564e+00 5.000059e-01\n", " 18 1.00000303890375e+00 5.000029e-01\n", " 19 1.00000151945336e+00 5.000015e-01\n", " 20 1.00000075972705e+00 5.000007e-01\n", " 21 1.00000037986362e+00 5.000004e-01\n", " 22 1.00000018993183e+00 5.000002e-01\n", " 23 1.00000009496592e+00 5.000001e-01\n", " 24 1.00000004748296e+00 5.000000e-01\n", " 25 1.00000002374148e+00 5.000000e-01\n", " 26 1.00000001187074e+00 5.000000e-01\n", " 27 1.00000000593537e+00 5.000000e-01\n" ] } ], "prompt_number": 39 }, { "cell_type": "markdown", "metadata": {}, "source": [ "Newton method is converging linearly. Now try the modified Newton method." ] }, { "cell_type": "code", "collapsed": false, "input": [ "newton(2.0,2)" ], "language": "python", "metadata": {}, "outputs": [ { "output_type": "stream", "stream": "stdout", "text": [ " 0 2.00000000000000e+00\n", " 1 7.03271114884954e-01 0.000000e+00\n", " 2 1.06293359720705e+00 -2.773614e-01\n", " 3 1.00108318855754e+00 -1.719679e-01\n", " 4 1.00000037565568e+00 1.750696e-02\n", " 5 1.00000000000005e+00 3.469257e-04\n" ] } ], "prompt_number": 40 } ], "metadata": {} } ] }