# Minimum iterations to guarantee a forward error of $\epsilon$

can anyone shed some light into this for me.

I am asked to numerically solve $$x\arctan(x) = 1$$ and to ensure that the error $$\epsilon$$ is less than $$10^{-3}$$. Now I usually use Newton's method for this and I have seen the following formula$$n \leq \frac{1}{\log(2)} \cdot \log \left( \frac{\log(\epsilon)}{\log(|p_0 - p|)}\right)$$ where $$n$$ is the number of iterations. It also says that $$p_0$$ is our initial guess and $$p$$ is the actual root. Now how would one go about this if they did not know the exact root? How can we use this formula?

• There can't be a general formula like that that is independent of the equation under consideration. Also, what do you mean by error, do you mean any $x$ such that $x |\arctan x -1| \le {1 \over 10^3}$? Or do you mean the numerical solution is no more that ${1 \over 10^3}$ away from a true solution? Commented Feb 27, 2020 at 3:37
• I mean that $x \arctan (x) - 1 \leq 10^{-3}$ Commented Feb 27, 2020 at 3:40
• I don't think that $x \arctan (x) - 1 \leq 10^{-3}$ could be a convergence criteria. Commented Feb 27, 2020 at 5:49

I'm not sure if this is what you were looking for.

Let $$f(x) = x \arctan x -1$$, note that $$f$$ is even, $$f(0) = -1$$ and $$f$$ is increasing and unbounded on $$x \ge 0$$. In particular, a unique solution exists on $$x \ge 0$$.

Since you are only concerned about finding a point $$x^*$$ such that $$|f(x^*)| < {1 \over 10^3}$$, there is a particularly simple & fast strategy.

In the following I am assuming that $$x \ge 0$$ and $$x^*$$ is the unique solution.

Note that $$f'(x) \ge 0$$, $$f''(x) >0$$ (hence $$f'$$ is strictly increasing) and $$f'(0) = 0$$. In particular, $$f$$ is convex.

Since $$f$$ is convex, if we start with any $$x_0 >0$$ (so that the iteration is defined) and use Newton's method $$x_{n_1} = x_n - {f(x_n) \over f'(x_n)}$$, then $$x_1 \ge x^*$$ and subsequently $$x^* \le x_{n+1} \le x_n$$.

In particular, as long as we start with $$x_0 >0$$, the iteration is well defined and $$x_n \to x^*$$. Since $$f'(x^*) >0$$, the convergence is quadratic.

So, just iterate until $$f(x_n) < {1 \over 10^3}$$.

If I pick $$x_0 = 1$$ then $$x_1 \approx 1.670$$, $$x_2 \approx 1.623$$ and $$f(x_2) < 2 \times 10^{-12}$$.

More detail:

A brief analysis shows that $$|x_{n+1}-x^*| \le {1 \over 2} |{f''(\xi_n) \over f'(x_n)}| |x_n-x^*|^2$$, where $$\xi_n \in [x^*,x_{n+1}]$$.

We can show that $$f''(x_n) \in (0,1]$$ for all $$x$$ and $$f'(x_n) \ge f'(x_0) \ge 1$$, so we have $$|x_{n+1}-x^*| \le {1 \over 2} |x_n-x^*|^2$$.

Since $$f(1)<0$$ and $$f(2)>0$$ we see that $$|x_0-x^*| \le 1$$ and a little work shows that $$|x_n-x^*| \le {1 \over 2}^{{1 \over 2} n (n+1)}$$. Choosing $$n=5$$ gives $${1 \over 2}^{{1 \over 2} n (n+1)} < {1 \over 10^4}$$, so five iterations with exact numerics will guarantee that we are close to the solution and since $$f'(x) \le 2$$ for $$x \le 2$$ we know that $$|f(x_5)| = |f(x_5)-f(x^*)| \le 2|x_5-x^*| \le 2 {1 \over 10^4}$$ which is adequate.

• @APMATH24: Glad to be able to help :-). Commented Feb 27, 2020 at 5:23