# Find all polynomials in $\mathbb{P_n}$ such that the Fixed point iteration converges for all initial guesses

Determine all polynomial fixed point functions, $$p \in \mathbb{P_n}$$ for some $$n \geq 0$$, that satisfy: Fixed point iterations on $$p$$ will always converge to some fixed point for any initial guess.

Attempt: Suppose $$p(x)=a_0+a_1x+ \ldots +a_nx^n$$. Then first of all we need $$p$$ to have a fixed point. Therefore, $$p(x)=x$$ for some $$x \in \mathbb{R}$$. I am not sure if this gives enough estimates on the coefficients $$a_i$$.

To get convergence for all initial guesses $$x_0$$, we can impose that $$p$$ is a contractive map. Thus, we require $$|p(x)-p(y)|=|\sum_{i=1}^na_i(x^i-y^i)|< |x-y|$$

One obvious solution is $$a_i=0$$ for $$i \geq 2$$ and $$|a_1|<1$$. Are there any non-trivial solutions as well and how can I find them?

• You can easily exclude all polynomials of degree $n \ge 2$. Commented May 15 at 15:37
• @MartinR That was my guess too, but how do I show that? Thank you for the insight Commented May 15 at 15:41

If $$\deg(f) \ge 2$$ then $$p(x)/x \to \infty$$ for $$n \to \infty$$, so that $$|p(x)| \ge 2 |x|$$ for all sufficiently large $$x$$. It follows that the fixed point iteration does not converge for all initial values.
If $$f(x) = a+bx$$ with $$b \ne 1$$ then $$f(x) - \frac{a}{1-b} = b \left( x - \frac{a}{1-b}\right)$$ so that the fixed point iteration converges for all initial values if and only if $$|b| < 1$$, i.e. if $$\deg(f) \le 1$$ and $$f$$ is a contraction. (This includes the case of constant polynomials.)
That leaves us with the cases $$f(x) = x$$ and $$f(x) = a+x$$ with $$a \ne 0$$, which are easy.