# How to solve using Newton-Raphson where we are given the intervals for the derivatives?

I am solving some questions of Newton Raphson Method when I found this question.

The equation $$g(x) = 0$$ has a simple root in $$(1,2)$$. The function $$g(x)$$ is such that $$|g'(x)| \ge 4$$ and $$|g''(x)| \le 3$$. Suppose that the Newton-Rapson method converges for all initial approximations in $$(1,2)$$. Find the maximum number of iteration required to obtain root correct to $$6$$ decimal places after rounding.

I tried solving it by considering $$f(x)$$ as $$g'(x)$$ and iterating through the steps but I was not able to find the root even after $$5-6$$ iterations. Am I doing it wrong?

• Yes, you’re doing it wrong. You’re supposed to look for a root of $g$, not a root of $g’$. May 29, 2021 at 9:27
• Yea I know that but since we haven't been given any more info the only way is to solve for g`(x). or is there any other way? May 29, 2021 at 9:31

There is a well-known inequality based on the linear Taylor formula with quadratic remainder term, $$g(N_g(x))=\underbrace{g(x)+g'(x)s}_{=0}+\int_0^1(1-\tau)g''(x+\tau s)s^2\,d\tau,$$ where $$s=-g'(x)^{-1}g(x)$$ is the Newton update and $$N_g(x)=x+s$$ is the Newton step. Inserting the lower bound $$m_1$$ for $$g'(x)$$ and upper bound $$M_2$$ for $$g''$$ gives the recursive inequality $$|g(N(x))|\le \frac12M_2|s|^2\le \frac{M_2}{2m_1^2} |g(x)|^2.$$ Now $$\frac{|g(x)|}{m_1}$$ is a proxy and upper bound for the distance from $$x$$ to the root. The inequality can be iterated as $$\left(\frac{M_2|g(N_g^k(x))|}{2m_1^2}\right)\le \left(\frac{M_2|g(x)|}{2m_1^2}\right)^{\!\large 2^k}$$ This means that you want $$\left(\frac{M_2 }{2m_1}\right)^{2^k-1}\le 10^{-6}$$ or so, depending on how you interpret "$$6$$ decimal places". This is under the optimistic assumption that the upper bound of $$g'$$ is close to the lower bound.
For a strict argument and assuming that $$m_1=4$$ is a strict lower bound on $$g'$$, one has $$M_1=m_1+M_2$$ as upper bound for the first derivative, $$|g(x)|\le M_1$$ as the maximal distance in the interval is $$1$$, so that the inequality becomes $$\frac{2m_1}{M_2} \left(\frac{M_2M_1 }{2m_1^2}\right)^{2^k}\le 10^{-6}$$ which slightly increases the necessary number of iterations.
• Nice, elegant and simple answer (...after reading it !). DO you think that the sign of $g(x_0)$ could have a significant impact (by Darboux theorem) ? Cheers :-) May 29, 2021 at 14:25
• See the Newton-Kantorivich theorem. As long as $\frac12M_2m_1^{-2}|g(x_0)|<1$ and twice the first step, that is, $x_0+2s_0$, remains inside the interval, the Newton method will converge (quadratically). The Darboux theorem has stricter conditions on monotonicity and curvature, but then gives a larger interval for convergence, so it does not really compare. May 29, 2021 at 15:05