8
$\begingroup$

What numerical methods are available for finding the fixed point of an operator $A$ that is acting on functions $f : [a,b] \rightarrow [a,b]$? I am looking for the function $f$ for which $Af = f$.

Essential details:

My function $f$ is actually a probability density function of a distribution on the circle (i.e. on the periodic internal $[0,2\pi)$). This also means that $0 \le f(x) \le 1$ for any $x \in [0,2\pi)$, which makes the problem easier. Let's say we have this function sampled with some density and we can compute the operator $A$ numerically. The distribution is not necessarily continuous, i.e. it might look like this:

Discontinuous distribution

I am looking for methods and suggestions on how to do this. I am going to try to implement this in Mathematica first.

All messy details of my practical problem:

This is how I actually compute the operator $A$:

  1. I take distribution which I have as a large number of samples drawn from it
  2. I estimate the PDF and convolve it with a "square" kernel ("square" means it's similar to the figure above). This gives me a rather smooth function.
  3. I threshold the function to get another binary-valued function $g:[a,b] \rightarrow {0,1}$.
  4. From this binary-valued function I compute a large number of samples drawn from the distribution again

I mentioned this because it means that instead of working with PFDs, we could also work with the smooth function (after the convolution) or the binary-valued function. Actually I was working with the binary valued function in practice.

I know that fixed points of plain real functions (not operators) can be "attracting" or "repulsing", i.e. when applying the function repeatedly to a number, it either converges to a fixed point, or is repulsed by it. I do not know what type the fixed point of my operator is.

I know that my operator always has the uniform distribution as a fixed point, but sometimes (depending on my parameters) it might have another one. It is this other one I need to find.

I did try applying the operator repeatedly to see what happens, and sometimes it converges to the fixed point I want. But even if it doesn't converge, a fixed point may still exists (or it may only converge to that fixed point if I use a different initial condition). So I need a more robust method.

Even more messy details:

Actually my distributions are not on $[0,2\pi)$, but on a periodic interval $[0,a)$. The fixed point will exist only for a certain value of $a$. When I apply the operator repeatedly, and $a$ is a little off from the right value, the distribution appears to "rotate" on the periodic interval. By measuring the amount of rotation, I can correct for the value of $a$.

Why did I mention this complex (seemingly too localized) detail, that's not essential to the question? Because when you read that the distribution is on a periodic interval, you will notice that if one distribution is a fixed point, any rotation of that distribution on the interval will also be a fixed point. This may get you thinking if numerical errors in computing the application of the operator to the fixed point will cause the fixed point to appear to "rotate" slightly. I can compensate for this, so this is not a problem.

$\endgroup$
  • $\begingroup$ Please help tag the question! I had no idea what tag to choose from the existing ones, but I needed to choose one, so I took optimization (which I think is not really appropriate). $\endgroup$ – Szabolcs Jan 18 '12 at 21:46
  • $\begingroup$ Is $A$ linear? If so, this is equivalent to seeking an eigenvector corresponding to the eigenvalue of 1, and you could attempt to do so by the inverse power method on $A-I$. $\endgroup$ – Jack Poulson Jan 18 '12 at 21:58
  • $\begingroup$ @JackPoulson Unfortunately $A$ is not linear. $\endgroup$ – Szabolcs Jan 18 '12 at 22:19
  • $\begingroup$ I retagged as linear-algebra (in the slightly more abstract sense) for the time being. I'd also tag operator-algebra, but I'm not too keen on new tags today. Thoughts, everybody? $\endgroup$ – J. M. Jan 18 '12 at 22:25
  • 2
    $\begingroup$ J.M.: it's probably not well tagged as linear algebra given that $A$ isn't linear. $\endgroup$ – Bill Barth Jan 19 '12 at 0:34
3
$\begingroup$

This is a classic example of what is known as an inverse problem. You want to find a function $f$ that reproduces known behavior, rather than asking what behavior is produced by $f$.

One approach for doing this is to use an approach like reverse Monte Carlo, developed by Lyubartsev and Laaksonen. What they did was to try to find a potential $u(r)$ that reproduced a known radial distribution function $g(r)$. What you are looking to do is to find a function $f$ that reproduces ${\mathcal A}f = f$, so while the entirety of the approach may not be suitable, you will want to pay special attention to the iteration procedure they use—that is, how do they go from guess $u^{(k)}(r)$ to guess $u^{(k+1)}(r)$.

$\endgroup$

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.