I have a function $f(x)$ defined on a domain $D$, but such that the image $f(D)$ may contain extra regions not included in its domain. I am interested in solving the fixed-point equation $x=f(x)$. If I do a fixed-point iteration:

$$x_{n+1} = f(x_n)$$

starting from a point $x_0\in D$, I risk that some point $x_n\notin D$ falls outside the domain.

Are there techniques to deal with such an $f$? For simplicity let's assume that $f$ is smooth in $D$.

  • $\begingroup$ I think almost every function $f$ is like that not necessarily $D = f(D)$, but if you know that truly that converged solution of your equation defined as: $x - f(x) = 0$ should be in $D$, your method to solve it numerically should be able to get it to you at the end within a defined tolerance. I think using iteration equation of: $x_{n+1} = f(x_{n})$ generally has a really poor performance and accuracy. Why you don't use Newton-Raphson here? $\endgroup$ – Alone Programmer Apr 7 '20 at 2:46

You can modify the iteration, for example by including a projection. That's because if $x\in D$ is indeed a fixed point of the function, i.e. $x=f(x)$, then it is also a fixed point of $x=\Pi(f(x))$ where $\Pi$ is some kind of operation so that $$ \Pi(x) = \begin{cases} x & \text{if $x\in D$} \\ \text{some $y\in D$} & \text{otherwise}. \end{cases} $$ An example is the orthogonal projection onto $D$ if $D$ is a convex set. But anything else that satisfies the statement above is valid as well.

So, with this, your iteration then becomes $x_{n+1}=\Pi(f(x_n))$ and that avoids the problem of walking out of the domain.

The question you need to answer, however, is whether the combined operation $\Pi\circ f$ is still a contraction. If your fixed point lies in the interior of $D$, then if $f$ is a contraction at $x$, then $\Pi\circ f$ is clearly also a contraction at $x$. But it may not be far away from the fixed point, and it's not obvious that the iteration will converge.

  • $\begingroup$ Thanks. I was thinking about something along these lines. Also it would be useful to have a guarantee that a fixed point of $\Pi\circ f$ is also a fixed point of $f$ (so the converse of your statement). What I am doing (and seems to work for my particular problem) is to do a random projection of $f(x)\notin D$ into some random point of $D$. But I have not really thought about formalizing this and its theoretical convergence properties. $\endgroup$ – becko Apr 7 '20 at 18:15
  • $\begingroup$ No, the converse is definitely not true. For $f(x)=2x$, you have that $x=0$ is the only fixed point. But if $\Pi$ is the projection onto $[1,2]$, then $x=1$ is a fixed point of $\Pi\circ f$. $\endgroup$ – Wolfgang Bangerth Apr 7 '20 at 20:27
  • $\begingroup$ I suspect that the random projection is fine if $\text{dist}(x_\text{fixed},\partial D)>0$ for at least one fixed point. It might lead to slow convergence, though. $\endgroup$ – Wolfgang Bangerth Apr 7 '20 at 20:28

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.