1
$\begingroup$

Consider a continuous function $f: \mathbb{R}^n \rightarrow \mathbb{R}^n$ with the following property. There exists $c \in (0,1)$ such that for all $x,y \in \mathbb{R}^n$ it holds that $\left\| f(x) - f(y) \right\| \leq c \left\| x-y \right\|$, where $\left\| \cdot \right\|$ is the Euclidean norm.

From Banach's fixed-point theorem, we know that, for any $x^{(0)} = x_0 \in \mathbb{R}^n$, the sequence $$ x^{ (k+1) } := f \left( x^{ (k) } \right) $$ converges to the unique fixed-point $\bar{x}$ of $f$, i.e. $\lim_{ k \rightarrow \infty } f( x^{(k)} ) = \bar{x} = f( \bar{x} )$.

Now consider $y^{ (0) } = x_0$ are the sequence $$ y^{ (k) } := f \left( \frac{1}{k} \sum_{i=0}^{k-1} y^{(i)} \right). $$ For instance, $y^{(1)} = x^{(1)} = f(x_0)$, $y^{(2)} = f\left( \frac{1}{2}\left(x_0 + f(x_0) \right) \right)$, $y^{(3)} = f \left( \frac{1}{3}\left( x_0 + f(x_0) + f\left( \frac{1}{2}\left(x_0 + f(x_0) \right) \right) \right) \right)$.

What happens to $\lim_{k \rightarrow \infty} y^{(k)} $? Does it converge to some point? In particular to $\bar{x}$?

$\endgroup$
  • $\begingroup$ You mean, there exist $c \in (0,1)$ and some norm $\| \cdot \|$ such that for all $x, y \ldots$. $\endgroup$ – Robert Israel Nov 26 '13 at 22:02
  • 1
    $\begingroup$ Assuming what Robert suggested is the correct interpretation, we have $\lim\limits_{k\to\infty} y^{(k)} = \overline{x}$. $\endgroup$ – Daniel Fischer Nov 26 '13 at 22:03
  • $\begingroup$ Yes, thanks. Let me slightly rephrase it then. $\endgroup$ – user693 Nov 26 '13 at 22:03
  • $\begingroup$ Dear Daniel, thanks for the tip. I am also wondering about this, but I was not able to prove it. Can you give me a hint? $\endgroup$ – user693 Nov 26 '13 at 22:04
  • $\begingroup$ Sure. Let me play a bit to see if I find something nice to show it, or whether the crude argument must suffice. $\endgroup$ – Daniel Fischer Nov 26 '13 at 22:14
2
$\begingroup$

Let $z_k =\displaystyle \dfrac{1}{k} \sum_{i=0}^{k-1} y^{(i)}$, Thus $$z_k = \dfrac{1}{k} (y^{(k-1)} + (k-1) z_{k-1}) = \dfrac{1}{k} \left(f(z_{k-1}) + (k-1) z_{k-1} \right)$$ while $$\overline{x} = \dfrac{1}{k} (f(\overline{x}) + (k-1) \overline{x})$$ and so

$$ \eqalign{ \|z_k - \overline{x}\| &\le \dfrac{1}{k} \left\|f(z_{k-1}) - f(\overline{x})\right\| + \dfrac{k-1}{k} \left\| z_{k-1} - \overline{x}\right\|\cr &\le \dfrac{c + k-1}{k} \|z_{k-1} - \overline{x}\|}$$

Since $\sum_{k=1}^\infty 1/k = \infty$, $\prod_{k=1}^\infty (1 - (1-c)/k) = 0$, so $\|z_k - \overline{x}\| \to 0$.

$\endgroup$
  • $\begingroup$ Thanks a lot for the solution. You have shown that $\frac{1}{k} \sum_{i=0}^{k-1} y^{(i)} \rightarrow \bar{x}$. Why this implies that $y^{(k)} \rightarrow \bar{x}$? $\endgroup$ – user693 Nov 26 '13 at 22:41
  • 1
    $\begingroup$ $y^{(k)} = f(z_k)$ and $f$ is continuous. $\endgroup$ – Robert Israel Nov 26 '13 at 22:42
  • $\begingroup$ Ok, thanks. So $\lim_{k \rightarrow \infty} y^{(k)} = \lim_{k \rightarrow \infty} f( z_k ) = f\left( \lim_{k \rightarrow \infty} z_k \right) = f( \bar{x} ) = \bar{x}$. $\endgroup$ – user693 Nov 26 '13 at 22:44
  • $\begingroup$ Why does it hold that $\prod_{k=1}^{\infty} 1 - (1-c)/k $ is equal to $0$? $\endgroup$ – user693 Nov 27 '13 at 8:39
  • 1
    $\begingroup$ Limit comparison test of $\sum_k -\log(1 - (1-c)/k)$ and $\sum_k 1/k$. More generally, there's a "well-known" theorem on infinite products: if $0 \le u_n < 1$, then $\prod_n (1 - u_n) > 0$ iff $\sum_n u_n < \infty$. $\endgroup$ – Robert Israel Nov 28 '13 at 4:21

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.