0

I was wondering if NR is the fastest method to find a root if all we know about a function is how to evaluate it and its derivative at any point.

Since you can use the first derivative to approximate the second I was wondering if this lets you converge on a root faster (as in $\epsilon_{n+1} \approx \epsilon_n ^3$)?

Salamander
  • 317
  • 2
  • 13
  • We can approximate the second derivative only if it exists. Can you provide an example for the situation where we can evaluate a function and its derivative and know that a second derivative exists, but can't evaluate it? –  Nov 21 '20 at 16:32
  • @ProfessorVector Maybe the function is output from some black box software that only gives the derivative and function itself at the point you specify. – Salamander Nov 21 '20 at 17:33
  • @ProfessorVector - functions where the derivative exists, but it is completely impractical to calculate it are very common. For example, you have a triangulation of the surface of some irregular closed shape, with tens of thousands of triangles, and your function is the volume of that triangulated shape below a given height. This has a derivative, except at isolated points, but no one in their right minds is actually going to bother with it. It is not too hard to suppose something similar with known first derivative, but unknown second.derivative. – Paul Sinclair Nov 22 '20 at 00:18

2 Answers2

2

About the only thing you can do to improve on Newton-Raphson is to abandon its habit of forgetting every point you've calculated except the last.

For example, instead of assuming at each step that the function is linear and using that assumption to find the next estimate of the root, you find $x_0$ by guessing, $x_1$ by assuming the function is linear and using the values $f(x_0), f'(x_0)$, $x_2$ by assuming the function is a cubic and using $f(x_0), f(x_1), f'(x_0), f'(x_1)$, then find $x_3$ by assuming the function is a quintic, etc.

But this gives only very minor improvements in convergence speed. It has been too long for me to remember, but I think converge is still quadratic in the limit.

Alternatively, instead of polynomials, you can use other families of functions in hopes of improved performance. Polynomials are not always that great at interpolating or extrapolating. For example Brent's Method, a widely-used root-finding algorithm when you don't even have derivatives, relies on inverse quadratic functions based on three previous values of the function.

Paul Sinclair
  • 43,643
  • The order is certainly not at most quadratic. Certainly with the approach you describe, the result will be at worst equivalent to Newton's method. IIRC: The limit becomes $4$ when using $n\to\infty$ points. In particular, the order is given by the solution to $x^n=2(x^{n-1}+\dots+x+1)$. – Simply Beautiful Art Nov 22 '20 at 12:32
  • It is worth pointing out that you need to somehow evaluate both $f$ and $f'$ (perhaps together as $f/f'$, though I haven't worked through the details of adding multiple points) very quickly for this to be useful. Otherwise you may as well just estimate $f'$ using an approach similar to the secant method with more points, or that which you mention at the end of your answer. – Simply Beautiful Art Nov 22 '20 at 12:41
  • Correction to the first comment, the order tends to $3$ as the number of points used tends to infinity. – Simply Beautiful Art Nov 22 '20 at 12:43
  • @SimplyBeautifulArt - I'm not surprised I was wrong, as it has been about 30 years since I had studied this idea (I admit I could have dug out my old textbook, but I was too lazy for that). And yes, if calculating $f'$ is on the same order as calculating $f$ itself, then Newton's method would have to converge within less than half as many steps as the Secant method to be faster. And that doesn't happen often. – Paul Sinclair Nov 22 '20 at 14:50
  • Another note: Without adding any difficult analysis, one may point out that intuitively the process can be thought of as approximating the second derivative for Halley's method, which implies the order tends to $3$. – Simply Beautiful Art Nov 22 '20 at 19:43
0

I came across an answer to my own question, as detailed in the linked article the following modification of Newton-Raphson does indeed only use the first derivative and converges cubically: https://www.sciencedirect.com/science/article/pii/S0377042703003911

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

Salamander
  • 317
  • 2
  • 13