0

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?

Thomas Russell
  • 10,425
  • 5
  • 38
  • 66
Discretizer
  • 100
  • 1
    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 ? – Claude Leibovici May 29 '14 at 12:57
  • 2
    @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. –  May 29 '14 at 13:07
  • @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. – Claude Leibovici May 29 '14 at 13:10
  • 1
    @ClaudeLeibovici What the OP proposes is exactly the secant method. –  May 29 '14 at 13:12
  • @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. – Discretizer May 30 '14 at 04:00
  • I totally undertand your problem. But, I should prefer a strict evaluation of the derivative by finite difference (one side or central). – Claude Leibovici May 30 '14 at 05:01
  • @ClaudeLeibovici Though I am a bit late, I just wanted to point out that this is not an issue for anything other than the speed of convergence. In fact, it tends to make the secant method more reliable than Newton's method, since it is less likely to be thrown off by unexpected local behaviors in the function e.g. a function which is monotone everywhere except one interval, which will throw off Newton's method but not the secant method. – Simply Beautiful Art Sep 14 '20 at 23:15

2 Answers2

3

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.

  • Minor nitpick: The basis of attraction for the secant method is two dimensional (since one needs two initial estimates). If we reduce consider it in one dimension and take both initial estimates from the basis of attraction, and restrict it to the largest continuous interval (no "accidental" convergence from afar), then the secant method is strictly better than Newton's method. – Simply Beautiful Art Sep 14 '20 at 23:11
1

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

ConvexHull
  • 504
  • 3
  • 10