2
$\begingroup$

In my numerical analysis class, and specifically in the section regarding fixed point iteration, the hypothesis of the fixed point theorem states:

Let $g \in C[a,b]$ be such that $g(x)\in[a,b]\ \forall\ x\in(a,b)$. Suppose, in addition, that $g'$ exists on $(a,b)$ and that a constant $0 < k < 1 $ exists with $|g'(x)| \le k, \forall\ x \in(a,b)$.

I'm confused about the last part. What exactly does "a constant $0 < k < 1 $ exists with $|g'(x)| \le k, \forall\ x \in(a,b)$" mean? Why does the absolute of the derivative of $g$ have to be less than 1 for the fixed point to exist?

Edit:

I realized that including the conclusion is probably a good idea:

Then, for any number $p_0$ in $[a,b]$, the sequence defined by $p_n = g(p_{n - 1}), n \ge 1$, converges to the unique fixed point $p$ in $[a,b]$.

Thank you

$\endgroup$
1
$\begingroup$

It is related to Banach's fixed point theorem which imposes $g:[a,b]\rightarrow [a,b]$ and $\exists k: 0\leq k< 1$ such that $\forall x,y \in [a,b]$: $$|g(x)-g(y)| \leq k |x-y|$$ also known as a contraction mapping.

On the other hand mean value theorem states that, if the function is differentiable on $(a,b)$, then $\exists c\in (x,y)$ (let's assume $x < y$) such that $$g(x)-g(y)=g'(c)(x-y)$$ Combining this with the fact that $|g'(x)| \leq k < 1, \forall x \in (a,b)$ we have $$|g(x)-g(y)|=|g'(c)||x-y| \leq k|x-y|$$ which satisfies Banach's fixed point theorem, thus there $\exists!x^* \in [a,b]: g(x^*)=x^*$.

$\endgroup$
  • $\begingroup$ Can you recommend any sources for me to read about contraction mapping? I realized part of the problem is that I don't really understand what it is $\endgroup$ – Sveinn Jan 30 '17 at 0:04
  • $\begingroup$ Assuming you are familiar with norms or metric spaces, wikipedia should be a good start en.wikipedia.org/wiki/Contraction_mapping. $\endgroup$ – rtybase Jan 30 '17 at 1:03
  • $\begingroup$ My only background in math is calculus, linear algebra, and diff eq so I actually have no idea what norms or metric spaces are $\endgroup$ – Sveinn Jan 30 '17 at 1:05
  • $\begingroup$ So you know a lot :) ... the links I posted point to general results, to make them specific, just replace $d(x,y)$ (metric) and $\left \| x-y \right \|$ (norm) with familiar $|x-y|$ (absolute value) and everywhere you read compact or complete metric space you can assume that a segment like $[a,b]$ fits in (i.e. every Cauchy sequence within $[a,b]$ has a limit within $[a,b]$ and every sequence within $[a,b]$ has a converging subsequence within $[a,b]$ also known as Bolzano–Weierstrass theorem en.wikipedia.org/wiki/Bolzano%E2%80%93Weierstrass_theorem). $\endgroup$ – rtybase Jan 30 '17 at 9:53
1
$\begingroup$

Actually, it suffices that $g$ is continuous (not differentiable) to show that $g$ has a fixed point in $[a,b]$: If $g(a)=a$ or $g(b)=b$, we are done. So assume $g(a)-a>0$ and $g(b)-b<0$. By the IVT, $x\mapsto g(x)-x$ has a zero within $(a,b)$.

$\endgroup$
  • $\begingroup$ So what is the point of the last condition? $\endgroup$ – Sveinn Jan 28 '17 at 22:33
  • $\begingroup$ For the existence of the fixed point, the condition is completely unnecessary. Maybe the condition has something to do with the particular implementation of the numerical method. $\endgroup$ – Fimpellizieri Jan 28 '17 at 22:37
  • $\begingroup$ @Hagen I would guess that the theorem, as stated in class, asserted that the fixed point was unique. $\endgroup$ – Mark McClure Jan 28 '17 at 22:38
  • $\begingroup$ I've edited the post to include the conclusion of the theorem. $\endgroup$ – Sveinn Jan 28 '17 at 22:47
1
$\begingroup$

The condition on the derivative assures that the Banach-Picard fixed point scheme works. The fixed point is unique and you may obtain it numerically very efficiently simply using $g$ to iterate, i.e.

Let $x_0\in [a,b]$ and define $x_{n+1}=g(x_n)\in [a,b]$.

The MVT implies that the sequence $(x_n)$ is Cauchy: First, $$|x_{n+1}-x_n|\leq k|x_n-x_{n-1}| \leq ... \leq k^n |x_1-x_0|\leq k^n (b-a).$$ This implies for $m>n>1$ that $|x_m-x_n|\leq k^n(b-a)/(1-k)$ whence convergence to some (unique) $x^*\in [a,b]$ as well as an error estimate: $$ |x^*-x_n | \leq \frac{k^n (b-a)}{1-k} .$$ I can add details if needed.

$\endgroup$
  • $\begingroup$ Did you mean the Banach fixed-point theorem or is this a regional alternative name? The Picard iteration for ODE is also a fixed-point iteration but unrelated to this question. $\endgroup$ – LutzL Jan 29 '17 at 12:27
  • $\begingroup$ In Anglo-Saxon countries it is called the Banach fixed-point theorem but in France sometimes Théorème de point fixe de Picard (or Banach-Picard which I have inserted in the above). As you mention it is then used in the Picard iteration scheme for ODEs. $\endgroup$ – H. H. Rugh Jan 29 '17 at 14:27

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.