# Fixed-point iteration when image and domain are not the same

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$$.

• 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? – Alone Programmer Apr 7 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.
• 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. – becko Apr 7 at 18:15
• 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$. – Wolfgang Bangerth Apr 7 at 20:27
• 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. – Wolfgang Bangerth Apr 7 at 20:28