Cfrgtkky

Given an unknown function $f:mathbb{R} rightarrow mathbb{R}$, is it possible to find it's region of interest? By that I mean either

1. 
   

   the range in which $f$ does not converge or diverge, e.g. $f(x)=(5x)^2-x^3$
   
   For this function the range is approx. $[-5..20]$. I'm looking for an algorithm that can

   
   
   

   1.1 determine if a function diverges or converges at some point (I prefer speed over accuracy), and

   
   
   

   1.2 where those points are.

   
   


2. 
   

   the length of one period if the function is periodic, e.g $f(x)=sin(x)$
   
   For this function the length would be $2pi$. I know that a function is periodic if $f(x+c)=f(x)$ is satisfied for the entire input set. However, I need to find $c$ in a reasonable time. So I'm rather looking for an algorithm that can

   
   
   

   2.1 determine if a function is likely to be periodic (I prefer speed over accuracy), and

   
   
   

   2.2 approximate the length of that period.

   
   

Note, since this is rather a computational question, elements of $mathbb{R}$ are represented by 64bit floating point numbers. This means that (in this case) $mathbb{R}$ is finite and elements of $mathbb{R}$ have limited precision.

A more informal version

Given an unknown function, I'm trying to find the input range for which the function looks interesting if it's plotted. For example, if a function is periodic I don't want to see the period beeing plotted 10 times. Or, if the function converges I'm not interested in seeing the part where it converges to a certain value, but rather where the function is "unpredictable".

The reason behind all of this is that I'm writing a plotting library and I want to implement some sort of auto focus that automatically determines which region of a function should be plotted.

The Answer to your Questions depends heavily on the nature of the functions you want to plot. You can for example do a lot more with functions, where you know that they are continuous or better yet differentiable.

But ether way, you need to understand, that there can‘t be an algorithm, which can tell you with 100% certainty that the function in question is for example periodic based solely on finitely many function evaluations, even if you know that its analytic. This is due to the fact that one can construct a polynomial of degree n through any n+1 different points and corresponding values. Therefore Even if you would evaluate something like the sinus, it could always be that you just got bad luck and got those values where the function coincides with the sinus.

But since you only what to present the user with a first expression, I could imagine a number of ways how you could get a „feeling“ for the function. In all of those methods I will generally assume that the function is arbitrarily smooth/at least differentiable.

For the periodicity you could start by look at the zero points of the function. You could find those using Newtons method, or any other method you like. Then you could check whether the difference between those two is indeed a candidate for periodicity by checking the function value one (or more) periods outside of the already checked range. Then you could try to look for smaller periods by starting the newton method in the middle. Keep in mind, that this way, you might get something smaller then the Periode. You will have to check at least one nonzero function value as well... for those extremal points (which can be found quite easily with a slightly modified algorithm) are good candidates.

For the „region of interest“ I have bad news for you. There is nothing that really defines this in any mathematical way. It could be the range between the extremal points which lie furthest apart as in your example. on the other hand for functions like $x*sin(x)$ that range would be all of the Real line. Neither is that function periodic. From my perspective the area from -1 to 1 would be of the most interest.... but how would you classify that. This example rules out other criteria’s as well. For example curvature could be an indicator of how fast a function changes values, which could be a point of interest. But on the other hand a plateau in the function, or any unregularity could be of interest.

If I would be tasked with writing this algorithm I might try something like minimizing the average distance of the function from the upper and lower border of the image while at the same time maximizing the area that is on display. But that is only a guess that could work (in some cases at least. As I mentioned before, for any algorithm you write, I can construct a counter example)

I hope I was able to help you at least a little bit. Don‘t be discouraged that there is no perfect algorithm... Even though it might not be perfect, it could always be helpful.