0
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ Yes, you’re doing it wrong. You’re supposed to look for a root of $g$, not a root of $g’$. $\endgroup$
    – bubba
    May 29, 2021 at 9:27
  • $\begingroup$ 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? $\endgroup$
    – Altair21
    May 29, 2021 at 9:31

1 Answer 1

0
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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 :-) $\endgroup$ May 29, 2021 at 14:25
  • $\begingroup$ 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. $\endgroup$ May 29, 2021 at 15:05
  • $\begingroup$ Thanks for the detailed answer ! $\endgroup$ May 29, 2021 at 15:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.