# How many iterations of Newton's method are needed to achieve a given precision?

Consider using Newton's method to solve the equation $arctan(x) = 0$. Using an initial guess of $x_0 = 1/2$ produces a sequence that converges rapidly. After $8$, iterations, $x_8$ is accurate to well over 2000 decimal places.

(i) Verify with a computer that $x_8$ is a solution accurate to over $2000$ decimal places.

I was just learning Newton's Method and saw this problem. I think I might be going ahead but it seems good to know.

Here is my attempt: (Sorry if I'm wrong. I am just really interested in this problem)

         In[1]:newton1[function_, variable_, initial_, iterations_] :=
Module[{p, f, x},
Subscript[p, 1] = initial;
f[x_] := function /. variable -> x;
Do[
Subscript[p, i] =
Subscript[p, i - 1] -
f[Subscript[p, i - 1]]/f'[Subscript[p, i - 1]];,
{i, 2, iterations}];
Subscript[p, iterations]
]

In[1]:Timing[approx = newton1[arctan(x)=0, x, 1/2, 8]]

Out[1]:{0.826805, Indeterminate}


or I was wondering if the program could be this:

              In[1]: f[x_] := arctan[x] = 0;

In[1]: mynewton[function_, variable_, initial_, iterations_] :=
Module[{f, x, p},
f[x_] := function /. variable -> x;
Subscript[p, 1] = initial;
Do[
Subscript[p, i] =
Subscript[p, i - 1] -
f[Subscript[p, i - 1]]/f'[Subscript[p, i - 1]];,
{i, 2, iterations}];
Table[Subscript[p, i], {i, 1, iterations}]
]

In[1]: N[mynewton[f[x], x, 1/2, 8], 8]

Out[1]: {0.50000000, Indeterminate, Indeterminate, Indeterminate, \
Indeterminate, Indeterminate, Indeterminate, Indeterminate}


Again sorry if I am wrong. I am really interested in learning this part of the program. I will be able to continue to other questions like this after help with this one on my own. I really did try. I was studying various types of Newton's Programs but can not figure this one out. Can someone please help write the input?

-
–  Michael E2 Oct 9 '13 at 23:34

I have a hard time following your code, but it doesn't look to me that you are on the right path. Here is how I would tackle this problem.

f[x_] := ArcTan[x]
df[x_] = f'[x];
iterStep[x_] := x - f[x]/df[x]
root = With[{n = 8}, Nest[iterStep, 1/2, n]];

Block[{$MaxExtraPrecision = 4000}, Abs @ root < 10^-2500]  True Block[{$MaxExtraPrecision = 4000}, Abs @ root < 10^-2600]


False

I interpret the last two results as saying that root approximates zero to more than 2500 decimal places, but less than 2600 decimal places.

-

Of course m_goldberg has the proper mathematica-esque soluiton, but for education purpose heres a working version of your loop approach..

    newton1[function_, variable_, initial_, iterations_] := Module[{p, f},
p[1] = initial;
f[x_] := function /. variable -> x;
Do[p[i] = p[i - 1] - f[p[i - 1]]/f'[p[i - 1]] // N;, {i, 2,
iterations}]; p[iterations] ];

newton1[ArcTan[x], x, 1/2, 8]


Explicit use of Subscript[] is usually not a good idea.. , and you had a bunch of other issues. Note also there is no reason to actually carry around all the p[i..] except the last one, but i left that alone

-

Nest seems perfect for Newton's method.

newtonStep[f_] := # - f[#]/f'[#] &;
Block[{$MaxExtraPrecision = 5000}, N[Nest[newtonStep[ArcTan], 1/2, 8], 10] ] (* 8.829190025*10^-2598 *)  With NestList, you can observe the convergence. newtonStep[f_] := # - f[#]/f'[#] &; Block[{$MaxExtraPrecision = 5000},
N[NestList[newtonStep[ArcTan], 1/2, 8], 10]
]

(* { 0.5000000000,
-0.07955951125,
0.0003353022040,
-2.513147366*10^-11,
1.058187453*10^-32,
-7.899444718*10^-97,
3.286233612*10^-289,
-2.365941712*10^-866,
8.829190025*10^-2598} *)


A gain in speed may obtained by computing approximate results all along. I found that to get a single significant digit in the 8th iterate, I could do without the extra precision, but I needed to start with 2600 digits of precision. To get the results above, I needed 2610.

NestList[newtonStep[ArcTan], 0.52610, 8] //  N[#, 10] &


Remark: The convergence rate is unusually fast (cubic instead of quadratic) because the second derivative of ArcTan is zero at the root.

-
wanted to note a subtle thing here: NestList operates symbolically resulting is a huge expression of nested ArcTan expressions, which is evaluated numerically at the end by the N[] wrapper. It runs way faster with essentiually the same precision if you put an N inside the newtonStep function.. newtonStep[f_]:=N[#-f[#]/f'[#],500]&; –  george2079 Oct 10 '13 at 15:30
@george2079 Interesting: I knew the exact expression would grow very large, but it didn't seem slow enough to worry about. Testing your comment, I found this: It turns out on the beta V10 I was using, there is essentially no difference in speed, exact vs approximate, 0.005981 vs. 0.005963. But on V9, it's about 2.7 vs. 0.0075`. On the other hand, I found 500 digits of precision insufficient for more than 6 iterations. –  Michael E2 Oct 10 '13 at 17:00