0
$\begingroup$

Let $f :[a,b]\to\mathbb{R}$ be any function which is twice differentiable in $(a,b)$ with only one root $\alpha$ in $(a,b)$. Let $f'(x)$ and $f''(x)$ denote the first and second order derivatives of $f(x)$ with respect to $x$. If $\alpha$ is a simple root and is computed by the Newton-Raphson method, then the method converges if

$$|f(x)f''(x)|<|f'(x)|^2.$$

How to show this argument?

$\endgroup$
1
$\begingroup$

I'll offer only a sketch proof. We can show the error terms $\varepsilon_n:=\alpha-x_n$ satisfy $\varepsilon_{n+1}=-\frac{f^{\prime\prime}(\xi_n)}{f^\prime(\xi_n)}\varepsilon_n^2$ for some $\xi_n$ between $x_n$ and $\alpha$. We're assured of convergence if $$\left|\frac{f^\prime(\xi_n)}{f^{\prime\prime}(\xi_n)}\right|>|\varepsilon_n|.$$But the given inequality may be rearranged, viz.$$\left|\frac{f^\prime(\xi_n)}{f^{\prime\prime}(\xi_n)}\right|>\left|\frac{f(\xi_n)}{f^\prime(\xi_n)}\right|\approx|\xi_n-\alpha|\sim|\epsilon_n|.$$

$\endgroup$
  • $\begingroup$ But the given relation is $\epsilon_{n+1}=-\frac{f''(\zeta_n)}{2f'(\zeta_n)}\epsilon_n^2$. $\endgroup$ – Mittal G Mar 5 '19 at 17:26
  • $\begingroup$ @MittalG The aim is to force $\left|\frac{\varepsilon_{n+1}}{\varepsilon_n}\right|<1$. $\endgroup$ – J.G. Mar 5 '19 at 17:36
1
$\begingroup$

Look at $$g(x)=x-\frac{f(x)}{f'(x)}.$$ Then $$g'(x)=\frac{f(x)f''(x)}{f'(x)^2}$$ and by assumption $|g^\prime(x)|<1$. Now apply the fixed-point formulation of your choice.

$\endgroup$
  • $\begingroup$ In the derivative, power $2$ should be in the denominator. $\endgroup$ – Mittal G Mar 6 '19 at 8:57
  • $\begingroup$ @MittalG : Thank you, there was a closing brace in the wrong position. $\endgroup$ – Lutz Lehmann Mar 6 '19 at 10:12
  • $\begingroup$ Why |g'(x)|<1? Which is the assumption? $\endgroup$ – Francesco Boi Oct 11 '19 at 8:32
  • $\begingroup$ @FrancescoBoi : This is the contraction condition for a fixed-point iteration. See the Banach fixed-point theorem and that the supremum of the absolute value of the derivative is a Lipschitz constant. $\endgroup$ – Lutz Lehmann Oct 11 '19 at 8:35

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.