20
$\begingroup$

It was suggested that this might be a better place for this question than Mathematics Stack Exchange where I asked it before.

Suppose one has a black-box function which can be evaluated anywhere (cheaply) on a specified interval $[a,b]$ and has no noise (except floating point granularity, say). What would be the best way to find the discontinuities of this function? I don't know how many discontinuities there might be and there may be none.

I can think of some straightforward methods (uniform sampling, refine where there are large differences between samples, ...), but perhaps there is a better way?

The function is "reasonable" in that one could assume that it has at most finitely many discontinuities, the same for higher derivatives, I don't mind if small pathological discontinuities are missed ... (the application is automated plotting of 1d functions).

--

Thanks to all who replied, particularly Pedro; the method described in Pachón, Platte and Trefethen seems to be the best approach to me, so I go now to implement it

|cite|improve this question
$\endgroup$
  • $\begingroup$ I have to wonder if any of the proposed methods can handle $$\frac1{x}-\left\lfloor\frac1{x}\right\rfloor$$ $\endgroup$ – J. M. May 3 '12 at 5:55
  • $\begingroup$ @J.M. : I will add a plot of this function when I have finished the implementation. $\endgroup$ – n00b May 4 '12 at 8:49
  • $\begingroup$ @n00b : You might find this concept useful. : mathoverflow.net/q/165038/14414 $\endgroup$ – Rajesh Dachiraju Jan 4 '15 at 4:21
18
$\begingroup$

If you're using Matlab, you may be interested in the Chebfun project. Chebfun takes a function, samples it and tries to represent it as a polynomial interpolant. If your function has discontinuities, Chebfun should be able to detect them with the splitting on command. You can find some examples here.

If you're interested in the underlying algorithms, a good reference is Pachón, Platte and Trefethen's paper "Piecewise Smooth Chebfuns".

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Thanks Pedro, I'm familiar with Chebfun which is great, but huge (and comes with a hefty implicit cost via the Matlab licence). So I'm really looking for a small tight algorithm for this problem which I would implement myself. $\endgroup$ – n00b May 1 '12 at 11:09
  • $\begingroup$ @n00b: Good point. I've added a reference to the paper describing the underlying algorithms, e.g. for edge detection. $\endgroup$ – Pedro May 1 '12 at 11:31
  • $\begingroup$ Ah, excellent! I had not seen this paper and, contrary to my expectations, it seems that the Chebfun discontinuity finder does not actually use Chebfuns -- so this looks to be eminently usable. I will read it carefully and inspect the corresponding code .... $\endgroup$ – n00b May 1 '12 at 12:00
11
$\begingroup$

I suspect that chebfun algorithm must appear to be more practical, but it is neccesary to mention one more way to detect discontinuities, namely the discrete wavelet transform. You can get an idea how it works by looking at this Mathematica documentation page, see section > Applications > Detect Discontinuities and Edges.

Briefly speaking, you can take DWT of $f$ at uniformly sampled points and look at high-frequency coefficients. The largest of them most probably correspond to discontinuity points.

|cite|improve this answer
$\endgroup$
8
$\begingroup$

Weighted Essentially Non-Oscillatory (WENO) methods use "smoothness indicators" to detect discontinuities in finite volume and difference methods. From the description of Chebfun that Pedro gave, it seems as though the general idea is the same: construct a set of interpolating polynomials and use them to compute some measure of smoothness.

See G.S. Jiang, and C.W. Shu, Efficient implementation of weighted ENO schemes, J.Comput.Phys., vol. 126, pp. 202--228, 1996.

|cite|improve this answer
$\endgroup$
5
$\begingroup$

Along with @Pedro, I would look at edge detection algorithms. A discontinuity is an infinity on the derivative, so consider looking at an increasingly fine mesh and targeting regions of interest.

The finite difference approximation to the derivative of a continuous function should reduce as the mesh is refined. Comparing the finite difference result for the derivative between meshes could then reveal divergences in the gradient which signal discontinuities.

Edit: Ok, so although a discontinuity has an infinite derivative, an infinite derivative is not always a discontinuity (thanks @n00b for pointing out an example). For an example like $f(x) = \mathrm{sign}(x) \sqrt{|x|}$ at $x=0$, the finite difference will reduce as the step size $h_x \rightarrow 0$, as I described, even though the analytic derivative is not continuous.

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ One subtlety of the problem is that, although a discontinuity can be seen as having an infinity in the derivative, the opposite is not true -- the function sign(x) * sqrt( |x| ) is perfectly continuous at x=0, but the derivative is infinite there $\endgroup$ – n00b May 1 '12 at 21:02
  • $\begingroup$ I also disagree with the comment that "any continuous function should be smooth at small enough scale". Smoothness has to do with continuous derivatives; continuity of the original function is a necessary condition, but not a sufficient one. $\endgroup$ – Geoff Oxberry May 1 '12 at 23:32
  • 1
    $\begingroup$ @GeoffOxberry: removed that statement. It's a reasonable result in FD, but not analytically. $\endgroup$ – Phil H May 2 '12 at 9:23

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.