2
$\begingroup$

I was experimenting with ratios of success iterations of Newton's method for a class assignment, and I noticed that for $x_n$ near a root $x^*$ of $f$, for which $f(x^*)\neq 0$, then $$ \left(\frac{f_{n+1}}{f_n}\right)^2\approx\left|\frac{f_n}{f_{n-1}}\right| $$ or alternatively $$ \frac{\ln\left|f_{n+1}/f_n\right|}{\ln\left|f_n/f_{n-1}\right|}\approx 2 $$ Where $f_n = f(x_n)$ and $x_n = x_{n-1} - \frac{f(x_{n-1})}{f'(x_{n-1})}$ as usual.

I attempted to prove this as follows: $$ \begin{aligned} f\left(x_{n+1}\right) = f\left(x_n - \frac{f(x_n)}{f'(x_n)}\right)&\approx f(x_n) - \frac{f(x_n)}{f'(x_n)}f'(x_n) + \frac12\left(\frac{f(x_n)}{f'(x_n)}\right)^2f''(x_n) + \cdots \\ & = \frac12\left(\frac{f(x_n)}{f'(x_n)}\right)^2f''(x_n) \end{aligned} $$ and so $$ \frac{f(x_{n+1})}{f(x_n)}\approx\frac12\frac{f(x_n)f''(x_n)}{(f'(x_n))^2} $$ and then plugging this into the original approximation yields $$ \frac{f^2(x_n)}4\left(\frac{f''(x_n)}{(f'(x_n))^2}\right)^2\approx\frac12\frac{f(x_{n-1})f''(x_{n-1})}{(f'(x_{n-1}))^2} $$ and I can't see how this is useful, or where to go from here.

I also thought this might be related to the "quadratic convergence" of Newton's method, but I can't quite fit it into the equation.

Is the result above true? If so, how can I prove it?

$\endgroup$

1 Answer 1

2
$\begingroup$

Since $x_n$ is near $x^*$, we can set $x_{n-1} = x^* + C*\epsilon$. Because of quadratic convergence, $x_n = x^* + C*\epsilon^2$ and $x_{n+1} = x^* + C*\epsilon^4$. Because $C * \epsilon << 1$, we can approximate $f(x_{n-1}) = f(x^* + C * \epsilon) = C * \epsilon * f'(x^*)$ (analogously for the other ones). At last $f(x_{n+1}) / f(x_n) = \epsilon^2$ and $f(x_n) / f(x_{n-1}) = \epsilon$.

$\endgroup$
1
  • $\begingroup$ This is a bit sloppy but it gets the main ideas. $\endgroup$
    – Ian
    Jan 29, 2018 at 16:08

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .