1
$\begingroup$

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?

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

1 Answer 1

3
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .