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?
Best Answer
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.