title: Different implementations of Newton's method in floating point arithmetic
body: <p>I'm solving a one dimensional non-linear equation with Newton's method. I'm trying to figure out why one of the implementations of Newton's method is converging exactly within floating point precision, wheres another is not.</p>
  
  <p>The following algorithm does not converge:</p>
  
  <p><img src="https://i.stack.imgur.com/S8nl3.png" alt="enter image description here"></p>
  
  <p>whereas the following does converge:</p>
  
  <p><img src="https://i.stack.imgur.com/m45wH.png" alt="enter image description here"></p>
  
  <p>You may assume that the functions f and f' are smooth and well behaved. The best explanation I was able to come up with is that this is somehow related to what's called <em>iterative improvement</em> (Golub and Van Loan, 1989). Any further insight would be greatly appreciated!</p>
  
  <p>Here is a simple python example illustrating the issue</p>
  
  <pre><code># Python
  def f(x):
      return x*x-2.
  
  def fp(x):
      return 2.*x
  
  xprev = 0.
  
  # converges
  x = 1. # guess
  while x != xprev:
      xprev = x
      x = (x*fp(x)-f(x))/fp(x)
  print(x)
  
  # does not converge
  x = 1. # guess
  while x != xprev:
      xprev = x
      dx = -f(x)/fp(x)
      x = x + dx
  print(x)
  </code></pre>
  
  <p>Note: I'm aware of how floating point numbers work (please don't post your favourite link to a website telling me to never compare two floating point numbers). Also, I'm not looking for a solution to a problem but for an explanation as to why one of the algorithms converges but not the other.</p>
  
  <p><strong>Update:</strong>
  As @uhoh pointed out, there are many cases where the second method does not converge. However, I still don't know why the second method converges so much more easily in my real world scenario than the first. All the test cases have very simple functions <code>f</code> whereas the real world <code>f</code> has several hundred lines of code (which is why I don't want to post it). So maybe the complexity of <code>f</code> is important. If you have any additional insight into this, let me know!</p>