Newton’s Method versus the Secant Method

We now compare Newton’s method with the secant method as a way of computing (Sqrt[2]) by solving the equation f(x) = (x^(2 ))-2 = 0.

Remember first that the Newton iteration is 

(Subscript[x, i+1])= (Subscript[x, i])+((f((Subscript[x, i])))/(f'((Subscript[x, i])))) = g((Subscript[x, i]))

so the first step is to code the Newton iteration g(x).

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

g[x_] := x - (x^2 -2)/(2x);

g[x]

Now as before, we can iterate it using Nest (if we just want the answer) and NestList (if we want to see the intermediate results):

N[Nest[g,2,6],50]

N[(Sqrt[2]),50]

As before, we’ll use the CorrectDigits function that we wrote in order to measure how well we’re doing:

CorrectDigits[approximation_,truevalue_] := Block[{$MaxExtraPrecision=10000},N[Abs[Log10[Abs[(N[approximation,10000] - truevalue)/truevalue]]]]];

NewtonDigits = CorrectDigits[#,(Sqrt[2])] & /@ NestList[g,2,6]

Now we work out the secant method! Recall the picture for the secant method: we keep track of the two previous steps, and then use the line through those points to predict the location of the root.

(Subscript[x, i+1])= (Subscript[x, i])- f((Subscript[x, i])) (((Subscript[x, i])-(Subscript[x, i-1]))/(f((Subscript[x, i]))-f((Subscript[x, i-1]))))

It is surprisingly hard to use subscripted things as variable names in a Mathematica function, so we’ll call these x_ and xold_

SecantIteration[{x_,xOld_},f_] := 
{x - f[x] ((x - xOld)/(f[x] - f[xOld])),x};

Our function is still f(x) = (x^2)-2, so

N[Nest[SecantIteration[#,f]&,{2,3},6],50]

But you can see that the number of correct digits here is much less:

N[(Sqrt[2]),50]

As we iterate, we can track the number of correct digits (remembering that we get a sequence of pairs, with the current estimate in the first position, so we need to compare First[] of each pair to (Sqrt[2]) to get the number of correct digits).

SecantDigits = CorrectDigits[First[#],(Sqrt[2])] & /@ NestList[SecantIteration[#,f]&,{2,3},6]

That’s enough data to fit both lists of correct digits to an exponential:

FindFit[NewtonDigits,a (b^n),{a,b},n]

FindFit[SecantDigits, a (b^n),{a,b},n]

And we see (amazingly, I think!) that our theoretical predictions were right on: the number of correct digits basically doubles with each iteration of Newton’s method and goes up by a factor of the golden ratio ϕ for each step of the Secant method. Just to check:

(1.0 + (Sqrt[5]))/2

How good is the fit? Well, we can plot it:

Show[Plot[{0.34755 (((2.02635))^n),0.3681 (((1.66893))^n)},{n,1.0,7.0},PlotRange->Full,Filling->Axis,PlotLabels->{"Newton","Secant"}],ListPlot[NewtonDigits],ListPlot[SecantDigits]]