3
$\begingroup$

I have two related questions about numerical methods for root solving:

1) $f: R \to R$ is continuous and piece-wise smooth, with $f(a)f(b) < 0$.
$f$ has very high number of knot-points and computing analytic expression for $f'$ is not possible. To find a root of $f$ in $[a,b]$, I can try the following:

  • Use bracketing methods like bisection, secant, Brent
  • Use Newton's method with numerical approximation of derivative ( being careful about choice of $\delta$, so that $(x-\delta)$ and $(x + \delta)$ falls between two consecutive knot-points )

My question is: Does the second option have any advantage over first ?

My intuition is that having to compute numerical derivative compensates any advantage Newton's method has over (say) secant method, in terms of stability and convergence rate.

2) $f: R^2 \to R^2$, continuous, piece-wise smooth, known to have a root in some given rectangle. Writing $f=(f_1, f_2)$ and $g = f_1^2 + f_2^2$ , I can try

  • Nelder-Mead on $g$
  • Gradient descent with numerical gradient estimation

Is it correct to think that second method will perform worse than first because of numerical approximation ?
Also is there any other method without derivative that I can try ? ( possibly some analogue of secant or Brent method )
[ I am a newbie to numerical analysis, so any reference would be helpful. Most sources on higher order root solving seems to talk about gradients ]

Improve this question
$\endgroup$
7
  • 2
    $\begingroup$ I am not sure what the theoretical answer is, but in my experience, the second method performs terribly. $\endgroup$
    – Igor Rivin
    Commented Dec 19, 2016 at 18:59
  • $\begingroup$ When you say you can not derive - do you mean numerically or analytically? Conversrely, do you sample $f$ on as many grid points as you want? If the answer is positive, then the Newton method will work, with the right choice of differentiation scheme. $\endgroup$
    – Amir Sagiv
    Commented Dec 19, 2016 at 21:21
  • $\begingroup$ @AmirSagiv I meant that I dont have analytic expression for df/dx , only numerical approximation like (f(x+d) -f(x-d))/2d . I understand that Newtons method works, but is it better or worse or equal to (say) secant method when derivative is calculated numerically like this ? $\endgroup$
    – Sujay
    Commented Dec 19, 2016 at 21:30
  • $\begingroup$ Ok. Do you have any estimation on the number of knots? If you don't, then any finite difference scheme won't work well, because you can never know if your differentiation is small enough. The other method, unfortunately, I don't know. $\endgroup$
    – Amir Sagiv
    Commented Dec 19, 2016 at 21:33
  • $\begingroup$ @Amir I know the exact position of knot points, so that wont be a problem. But if d above is chosen very small, precision error happens ( dividing two near zero quantities). $\endgroup$
    – Sujay
    Commented Dec 19, 2016 at 21:42

1 Answer 1

Reset to default
2
$\begingroup$

Obviously, within the realm of piecewise-smooth functions one can find examples where any derivative-based approach fails. I believe you're looking for the term "derivative free optimization".

Improve this answer
$\endgroup$

You must log in to answer this question.

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