0

Suppose that $x_0,x_1,\dots$ are the successive approximations of a solution of some iterative scheme (can think of successive approximations in Newton-Rapson method in finding root of a non-linear equation, for example). In general the following stopping criteria are used in approaching the root.

  1. $|x_{n+1}-x_n|<\epsilon$ (absolute error)
  2. $|f(x_n)|<\epsilon$
  3. $\frac{|x_{n+1}-x_n|}{|x_n|}<\epsilon$. (relative error)

I can understand the first two why they are used, how they work, when they fail, and so on. However, in books it is said that the third criterion is better than the first two. However, I am not able to see (i) why the third one works and (ii) how that is better than the first two.

Any explanation on this is greatly appreciated.

Kumara
  • 706

1 Answers1

1

The third has the advantage that unless you set $\epsilon$ too small you are (essentially) guaranteed to have values that will meet it. This is about computer numbers, not mathematical numbers. If you have $53$ bits in the mantissa of your floating point number, changing the lowest bit will make a relative change of about $2^{-53}$ in the number. The only way this can fail is if you are at the end of the exponent range for your representation.

By contrast, for specific functions there may not be any $x$ values that satisfy the first two. If you set $\epsilon=2^{-20}$ in the first and $x$ is of order $2^{40}$ you cannot satisfy it unless $x_{n+1}=x_n$. For the second if $f(x)$ is changing rapidly near the root there may not be any $x$ values that give a value that small.

This does not mean that the third is necessarily better than the first two. If you know something about $f$ you can analyze the problem and convince yourself that one of the first two will work.

Ross Millikan
  • 374,822
  • Thank you. Still I have the following questions. The first criterion is a necessary condition for convergence. Like that, can we say that the third criterion is a necessary or sufficient condition? The other question is when $x_n$'s converge, $x_{n+1}\approx x_n$. So the ratio will be close to $1$. So shouldn't the criterion be the ratio being $\approx 1$? – Kumara Jan 27 '19 at 15:39
  • The ratio will not be close to $1$ because $x_{n+1}-x_n$ is much smaller than either of them. Mathematically, if you are converging to a root all of them will be satisfied (with different values of $\epsilon$ for the same distance from the root). The first two can fail in a computer environment as I described, but that is based on the characteristics of computer numbers. – Ross Millikan Jan 27 '19 at 15:52