CHAPTER 1(b), Newton’s Method.

1.3 Newton’s Method for One-Dimensional Maps.

We now look at Newton’s method for one-dimensional maps. The module iterate, defined below and similar to webPlot, can be used to follow the iterations involving Newton’s method.  The function  f(x)=(x^2)-2 clearly has a positive zero where (x^2)=2, or x=(2^(1/2)).

Clear[f]
f[x_]:=x^2-2

Plot[f[x],{x,-2,2}]

The Newton function is defined by  (Subscript[N, f])(x)=x-f(x)/f'(x), the fixed points of  (Subscript[N, f])(x) giving the zero’s of  f(x). For the function  f(x)=(x^2)-2, (Subscript[N, f])(x)=x-((x^2)-2)/2x=x/2+1/x. It is surprising how good Newton’s method is for finding zero’s of  an arbitrary function f(x). Starting with almost any initial guess (Subscript[x, 0]), the iterates of the Newton function almost always converge to a zero of  f(x). One of the aims of this notebook is to examine certain of those exceptional points, and we continue this study in the Chapter 11 notebook.

g[x_]:=x-f[x]/f'[x]

Plot[{x,g[x]},{x,-2,2}]

The parameters of the module are the function f(x), (whose zero’s are being considered), the end points of the interval [a,b], on which the function is being plotted, the point being iterated (Subscript[x, 0]), and the number of iterations n.

iterate[g_,a_,b_,x0_,n_]:=Module[{x,f,t},f[x_]=g[x];
	t[x_]:=x-f[x]/f'[x];
DynamicModule[{m=0,data={x0},data2,data3,data4},
  Manipulate[
data=NestList[t,x0,m];data2=Flatten[Table[{data[[i]],0,data[[i]],f[data[[i]]]},{i,Length[data]}]];
		data3=Partition[data2,2];
		data4=Drop[data3,-1];
Plot[ f[x],{x,a,b},PlotStyle->{Red,Thickness->0.005},
Epilog->{Blue, Line[data4] },AspectRatio->Automatic],
{{m,0,Dynamic[Panel[Row[{Column[{"n=","x="}],
                     Column[{m,N[data[[-1]]]}]}]] ]},0,n,1}]
]]

iterate[f,0.,2,.6,10]

If instead we do a webPlot using the Newton function (Subscript[N, f])(x), we can see very fast convergence to the root. This is because the tangent to (Subscript[N, f])(x) at the root is horizontal ((Subscript[N, f])'((Subscript[x, 0]))=0),  resulting in what we call a super attracting fixed point for (Subscript[N, f])(x) at  (Subscript[x, 0]).

webPlot[g_,{x_,xmin_,xmax_},{a1_,n_}, opts_]:=Module[{seq, r, pts, web, graph}, r[t_]:=N[g/.x->t];seq=NestList[r,a1,n]; pts=Flatten[Table[{{seq[[i]],seq[[i+1]]},{seq[[i+1]],seq[[i+1]]}}, {i,1,n}],1]; web=Graphics[{Hue[0], Line[PrependTo[pts, {seq[[1]], 0}]]}];graph=Plot[{x,r[x]}, {x, xmin, xmax}, DisplayFunction->Identity]; Show[web, graph, opts, Frame->True, PlotRange->{{xmin, xmax}, {xmin, xmax}}]];

webPlot[g[x], {x,.1,3}, {.6, 16}, AspectRatio->Automatic]

Some choices of starting point do not converge to the root. Here we obtain a type of cycling.

Clear[f]
f[x_]:=(x+2)(x^2-1)

Plot[f[x],{x,-2.5,1.2}]

iterate[f,-2.5,1.2,-1.45884,4]

Clear[g]
g[x_]:=x-f[x]/f'[x]

webPlot[g[x], {x,-1.8,.8}, {-1.45884, 4}, AspectRatio->Automatic]

Exercises 1c.

For the functions defined below, use the module iterate to illustrate the convergence in Newton’s method. Use either Solve or FindRoot, to find an approximate value to the root, when it exists.

(i)    f(x)=cos(x)-x, with starting point (Subscript[x, 0])=1,

(ii)   f(x)=(x^3)-2, with starting point (Subscript[x, 0])=1,

(iii) f(x)=(x^2)+1, with starting point (Subscript[x, 0])=1,

Exercises 1d.

Set h(x)=f(x)/f'(x), then Halley’s method considers the Newton function (Subscript[N, h])(x), which when iterated will converge to the zero’s of f(x) Plot both (Subscript[N, h])(x) and  (Subscript[N, f])(x), the Newton functions for  h(x) and  f(x) to see that for  f(x)=(((x-2))^2)(x+1), one gives a super attracting fixed point, whilst the other does not.

Exercises 1e.

Consider the function  f(x)=(x^3)-x+a  as a varies.

Show that the Newton function, (Subscript[N, f]) of  f(x) has exactly one fixed point for -√12/9<a<√12/9.  Use a Manipulate Plot to show that a 2-cycle is created when a>√12/9. FInd where 3-cycles are created