Why is the MatLab statement "if abs(xnew - xold) < 1e-7" not decent?

I'm trying to implement Newton's method, which finds the root of an equation. Consider the floating point number system fl(10, 4,−8, 8). What is wrong with the MatLab statement below?

if abs(xnew - xold) < 1e-7
  ... ...
end

Why is the following code better?

if abs(xnew - xold) < 1e-7 + eps * abs(xnew)
  ... ...
end

Answer 1

[Matt J]

I don't recognize the notation fl(10, 4,−8, 8). However, I think the issue is that 1e-7 might be a huge number compared to xnew,xold if the natural magnitude of these quantities are much less than 1e-7. It would then make a very silly stopping tolerance.

I wonder if the improved code is really supposed to be

 if abs(xnew - xold)<=min(1e-7,  c*eps(xnew))

where c>=1 is some user-chosen parameter. Thus if 1e-7 too large, the tolerance will switch to c*eps(xnew), which will definitely be small compared to xnew.

[Elena]

Thanks a lot!

The notation fl(10, 4,−8, 8) is not a MatLab function. It represents a floating point number system fl(b, p, emin, emax) where b is the base, p is the precision and the exponent e is in the interval emin <= e <= emax.

But from our lecture notes, it should be written as abs(xnew - xold) < 1e-7 + eps * abs(xnew). The following is the code snippet from our lecture notes.

[Matt J]

If it's from your lecture notes then it's your lecturer's job to explain it. It doesn't look like anything standard as far as I can tell, so all we can do is guess.

The addition of eps*abs(xnew) only serves to ensure that your tolerance is at least eps*abs(xnew), but there are other ways of doing that, such as

max(1e-7,  eps*abs(xnew))

Although, I really think that eps*abs(xnew) is supposed to be eps(xnew) as in my proposal, since that is officially the smallest change possible in xold-xnew.

Another possibility is that it is meant to bound the relative error

 abs(xnew-xold)/abs(xnew) <= tol

Relative errors in floating point can never get smaller than eps, so it makes sense to ensure the right hand side is at least eps, e.g.,

 abs(xnew-xold)/abs(xnew) <= tol+eps

Rearranging would lead to something close to your lecturer's version, but not exactly

abs(xnew-xold) <= (tol+eps)*abs(xnew)

To me, it would make a bit more sense to do

abs(xnew-xold) <= max(tol,eps)*abs(xnew)

[Elena]

Nice inference! It makes sense! Thanks, dude!!