Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

I am trying to implement Newton's method for a given function f[x] and a starting x-value xval. The code should print out each new x-value as it approaches one of the zeroes of the functions. g[x] is a function that returns the new x-value given an old x-value.

f[x_] = x^3 - x;
g[x_] = x - (f[x]/D[f[x], x]);
zeroes = (x /. Solve[f[x] == 0, x]);
xval = 1000;
shouldStop = False;
While[Not[shouldStop], distances = g[xval] - zeroes; 
      results = Map[Less[Abs[#], 0.00001] &, Abs[distances]]; 
      xval = g[xval]; Print[N[xval]]; shouldStop = Or @@ results]

I am not sure why, but as the while loop continues, each iteration takes longer to run. Any help?

share|improve this question
1  
It's because you are using exact arithmetic (a simple Print[distances] would have shown this. You can address this by changing the initial value to xval=1000,;. –  Daniel Lichtblau Feb 27 at 17:07
    
@DanielLichtblau Might merit an answer, because more users are bound to encounter them exact arithmetic things :D –  Yves Klett Feb 27 at 17:19
    
@DanielLichtblau Thanks that makes sense now. I changed it to xval = 1000//N; and it works! –  Adam S Feb 27 at 17:52

1 Answer 1

(1) Use Print, say, to see what exactly is happening under the hood. Something like the code below would have given a strong indication of what was happening.

j = 0;
While[Not[shouldStop] && j <= 5,
 j++;
 distances = g[xval] - zeroes;
 results = Map[Less[Abs[#], 0.00001] &, Abs[distances]];
 xval = g[xval];
 Print[N[xval]];
 Print[results];
 shouldStop = Or @@ results]

(2) With the problem now understood, (exact arithmetic giving fractions with ever larger parts), one can avoid it by working with numeric arithmetic. A simple way to accomplish this would be to give an approximate number for start value, e.g. xval=1000.;.

(3) Once you ascertain that speed is now as expected, you can remove the j<=5 restriction.

I will remark that the complexity increase is pretty much quadratic per iteration. This means it is exponential in the number of iterations, but quadratic in the size of residual (since that also decreases quadratically, at least when we get within the Newton attraction region).

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.