0
$\begingroup$

In the Newton-Raphson method we come across the following equation: $$x_{n+1}=x_n - \frac{f(x_n)}{f'(x_n)}$$

Can you please let me know if we can calculate the derivative term like this - $$f'(x_n) = \frac{f(x_n) - f(x_{n-1})}{x_n-x_{n-1}}$$

Will rate of convergence of the original Newton-Raphson Method and this modified method be different? Will all set of problems solvable by the original Newton-Raphson Method be solvable by the above modified method too?

$\endgroup$
  • 1
    $\begingroup$ I think that this could be extremely unsafe when far from the solution and you could face many unpleasant situations. Close to the solution, what you write is effectively the computation of the derivative by finite difference and it would work. If I may ask, do you have any reason for looking at such a scheme ? $\endgroup$ – Claude Leibovici May 29 '14 at 12:57
  • 1
    $\begingroup$ @ClaudeLeibovici It's a common root finding method: the secant method. Sure, it can throw an exception when the secant is horizontal, but so can Newton-Raphson. $\endgroup$ – user147263 May 29 '14 at 13:07
  • $\begingroup$ @wordsthatendinGRY. My real concern is that the derivative can be very wrong when far from the solution. I would even prefer starting using a secant method and finish polishing the solution using what the OP proposes. $\endgroup$ – Claude Leibovici May 29 '14 at 13:10
  • 1
    $\begingroup$ @ClaudeLeibovici What the OP proposes is exactly the secant method. $\endgroup$ – user147263 May 29 '14 at 13:12
  • $\begingroup$ @ClaudeLeibovici There is no analytic first derivative for my problem. Hence, I wanted to use the previous iteration value to calculate the derivative and make the solver faster. $\endgroup$ – Discretizer May 30 '14 at 4:00
2
$\begingroup$

You have rediscovered the secant method.

The secant method a bit slower in the vicinity of the root than Newton-Raphson: its order is $1.618$ instead of $2$. However, since there is just one function evaluation per step (versus two for N-R: $f$ and $f'$), it may actually be faster. Depends on how complicated the derivative is.

Will all set of problems solvable by the original Newton-Raphson Method be solvable by the above modified method too?

This is much too broad to have an affirmative answer. Both methods converge from a vicinity of a root, if the function is reasonable. Both can fail to converge from further away. The basins of attraction of a root can be quite complicated (fractal), with tiny difference in initial position changing the outcome. Briefly: no, they are different methods, and you may find one method failing whether the other succeeds.

$\endgroup$
0
$\begingroup$

The answer of user147263 is not correct. The secant method is not the same as the Newton method with numerical gradients.

Generally the Secant method is defined as:

$x_n = x_{n-1} - f(x_{n-1}) \frac{x_{n-1} - x_{n-2}}{f(x_{n-1}) - f(x_{n-2})} = \frac{x_{n-2} f(x_{n-1}) - x_{n-1} f(x_{n-2})}{f(x_{n-1}) - f(x_{n-2})}.$

The Newton method with a finite difference approximation for the derivatives is different to this, because you can choose the delta $\Delta\tilde{x}$ for the finite difference independently from $\Delta x = x_{n-1} - x_{n-2}$.

Regards

$\endgroup$

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.