Contraction Mapping

Let $C\subseteq R$ and $F: C\to C$ $F$ is contractive if $\quad \exists \quad \lambda<1$ such that

$$\vert F(x)-F(y)\vert \le\lambda\vert x-y\vert\quad \forall \, x, y \mbox { in domain of } F$$

See Figure 23 for a simple contraction example

Figure 23: Contraction Mapping

the values between $x$ and $y$ get mapped into a smaller range in $z$.

Contractive Mapping Theorem: Let $C\subseteq R$ closed subset. If $F: C\to C$ is contractive of $C$ to $C\rightarrow F$ has unique fixed point. Moreover,this fixed point is a limit of every sequence $x_{n+1}F(x_n)$ with $x_0\in C$.

$\Box$

Remark In homework: Prove that $F:[a,b]\to {\bf R}^1$, if $F'$ is continuous and $\vert F'(x)\vert<1$ on $[a,b]$ then $F$ is a contraction map.

$$\begin{eqnarray*} F'(x_n)=\lim_{x_{n+1}\to x_n} \frac{F(x_{n+1})-F(x_n)}{x_{n+1... ...{n+1})-F(x_n)\vert<\lim_{x_{n+1\to x_n}} \vert x_{n+1}-x_n\vert \end{eqnarray*}$$

considering this, can iterative map:

$$% latex2html id marker 8387\vert F(x_{n+1})-F(x_n)\vert<\vert x_{n+1}-x_n\vert\quad\therefore \mbox {contractive}.$$

$F$ has a fixed point if $F:[a,b]\to [a,b]$    and it will be unique if $\vert F'(x)\vert<1\quad x\in(a,b)$ so either $[a,b]$ is the whole $R$, or there is no guarantee of a fixed point.

$\Box$

Quick Summary on Results on Fixed Point Iteration:

$$\mbox {let }I=[a,b]$$

Theorem: 1 if $g\in C(I)$ and $g\in I \quad \forall x \quad \in I\Rightarrow g$ has a fixed point in $I$.

Theorem: 2 Suppose in addition $g'(x)$ exist on $(a,b)$ and that $0<k<1$ with $\vert g'(x)\vert\le k<1\quad \forall x\in (a,b)$ there fixed point is unique.

Theorem: 3 Let $g(I)\subseteq I\equiv [a,b]$ and $\vert g'(x)\vert\le k<1\forall x\in I$ for $x_0\in I$ the sequence $x_n=g(x_{n-1}) n=1,2 \cdots$ converges to the fixed point $s$ and the $n^{th}$ error $e_n=x_n-s$ satisfies

$$\vert e_n\vert\le\frac{k^n}{1-k}\vert x_1-x_0\vert$$

Remark: Theorem 3 is ``nonlocal'' convergence theorem because it specifies a KNOWN interval $I=[a,b]$ and gives convergence for any $x_0\in I$. It is often the case that we don't know the interval I, but we hope that if we pick $x_0$ sufficiently close to $s$, it would still converge: ``local convergence'':

Theorem 4: let $g'(x)$ e continuous in some open interval containing $\delta$, where $s=g(s)$. If $\vert g'(x)\vert< 1 \Rightarrow \exists\varepsilon >0$ such that the $x_n=g(x_{n-1})$ is convergent whenever $\vert x_0-s\vert<\varepsilon$.

Corollary: Suppose $g'(x)$ continues, $g(x)$ continued in an open interval containing $s$ and $\vert g'(b)\vert>1.$ Then there is a neighborhood of $s$ in which no initial guess (except $x_0=s$)will work.

$\Box$

Problem: Complex root? Easy to fix: separate the real and imaginary parts, form a vector root problem and follow the prescription described for systems of nonlinear equations (see 12.3.1).

$\Box$

Remark What happens in Newton and Secant Methods if $f'(p_n)$ and $f(p_n)$ go simultaneously to $0$? This is a situation when we have a NON-SIMPLE root, or a root WITH MULTIPLICITY. See Figure 24 for a comparison between a simple and a multiple root.

Figure 24: (a) Simple Root, (b) Multiple Root.

In these sort of situations we need to use a variation of some things we've learned.

A solution $p$ of $f(x)=0$ is zero of multiplicity $m$ if $f(x)$ can be written $f(x)=(x-p)^m q(x)$ for $x\ne p$ where $$\lim_{x\to p}q(x)\ne 0$$. Here $q(x)$ represents portion of $f(x)$ not contributing to zero of $f$.

All algorithms assumed a simple root. So, how do we identify whether there's a simple root:

1)

$f\in C^1[a,b]$ has $p$ root simple in $(a,b)\iff f(p)=0$ but $f'(p)\ne 0$.

2)

$f\in C^m[a,b]$ has $p$ of $m$ multiplicity $p\iff$

$$O=f(p)=f'(p)=f''(p)\cdots f^{(m-1)}(p)\mbox { but } f^m(p)\ne 0.$$

$\Box$

Method for handling multiple zeros:

$$\mbox {let }\mu=\frac{f(x)}{f'(x)}$$

if $p$ is $m$- root $m\ge 1\Rightarrow f(x)\equiv (x-p)^mq(x)$

$$\mu(x)=\frac{(x-p)^m q(x)}{m(x-p)^{m-1}q(x)+(x-p)^m q'(x)}=... ...-p)q'(x)}_ {\mbox {has root $p$} \mbox { but multiplicity 1}}}$$

Now, apply Fixed Point iteration to

$$\begin{eqnarray*} &&g(x)=x-\frac{\mu(x)}{\mu'(x)}\\ &&g(x)=x-\frac{f(x)f'(x)}{[f'(x)]^2-f(x)f''(x)} \end{eqnarray*}$$

this is the difference between 2 small numbers! COULD BE A PROBLEM. So although we have a way to do the computation, we have to be careful.

$\Box$

Remark Acceleration of Linear Methods: Is there a way to accelerate convergence of any linear Method? Use Aitken's $\Delta^2$ Method (see Aitken acceleration 13.1).