Contraction Mapping

Theorem (Contraction Mapping Principle in [MH]). Let

$T:C_b(A,{\mathbb{R}}^m)\to$

$C_b(A,{\mathbb{R}}^m)$ be a given mapping such that there is a constant

$\lambda ,0⩽$

$\lambda <1$ with

$$\Vert T(f)-T(g)\Vert ⩽\lambda \Vert f-g\Vert$$
for all

$f,g\in C_b(A,{\mathbb{R}}^m)$. Then

$T$ (is continuous and) has a unique fixed point; that is, there exists a unique point

$f_0\in C_b(A,{\mathbb{R}}^m)$ such that

$T\left(f_0\right)=f_0$.

Actually, we can replace

$C_b(A,{\mathbb{R}}^m)$ by any complete metric space.

Theorem (Contraction mapping in [DD] or [R]). If

$T:X\to X$ is a contraction mapping on a complete metric space

$(X,d)$, then there is exactly one solution

$x\in X$ of

$T(x)=x$.

Recall theorem in p.113 [MH],

$C_b(A,{\mathbb{R}}^m)$ is a Banach space. Thus,

$C_b(A,{\mathbb{R}}^m)$ is a complete metric space.

Now, we take a closer look at contraction mapping theorem.

Converse.

$X=\{(x,y):y=\sin (1/x),x\in (0,1]\}$ is non-closed in

${\mathbb{R}}^2$, but for all contraction mapping has unique fixed point. Please see Elekes (2011) for more detail.

Weak. Consider

$f:[0,\mathrm{\infty })\to [0,\mathrm{\infty })$ given by

$$f(x)=\sqrt{1+x^2}.$$

Since

$$f^{\prime }(\xi )=\frac{\xi }{\sqrt{1+{\xi }^2}}<1\text{ for each }\xi \in [0,\mathrm{\infty }),$$
by the mean value theorem

$$|f(x)-f(y)|=f^{\prime }(\xi )|x-y|<|x-y|\text{ for every }x,y\in [0,\mathrm{\infty }).$$

But

$f$ clearly has no fixed points.

Application of Contraction Mapping

Solve linear equation (Jacobi & Gaussian Seidel Method).

Consider the linear system

$Ax=b$ where

$A\in {\mathbb{R}}^{m\times m}$ and

$x,b\in {\mathbb{R}}^m$. We write

$A=D-L-U$ where

$D$ is diagonal,

$L$ is lower triangular, and

$U$ is upper triangular. Then,

$b=Ax=(D-L-U)x=Dx-(L+U)x$. Thus, it's sufficient to convert to the problem of finding fixed point.

$$x=D^{-1}(L+U)x+D^{-1}b:=T(x).$$

On the other hands, an

$n\times n$ matrix

$A$ is said to be diagonally dominant if for each row the sum of the absolute values of the off-diagonal terms is less than the absolute value of the diagonal term. If

$A$ is diagonally dominant, show that

$$\left|a_{ii}\right|>\sum _{j\ne i}\left|a_{ij}\right|\text{ for all }i.$$

Theorem. Show the Jacobi scheme

$x_{n+1}=D^{-1}(L+U)x_n+D^{-1}b$ converges to a solution of

$Ax=b$

Proof. Define

$$K=max\{\frac{1}{\left|a_{ii}\right|}\sum _{\begin{array}{c}j=1\\ j\ne i\end{array}}^m\left|a_{ij}\right|:i=1,2,\dots ,m\}$$
and by diagonally dominant, we know

$K<1$. Focus on

$i$-component of

$T(x)-T(y)$

$$\begin{array}{rl}(T(x)-T(y){)}_i=& |\frac{1}{a_{ii}}(b_i-\sum _j{a}_{ij}{x}_j+a_{ii}{x}_i)-\frac{1}{a_{ii}}(b_i-\sum _j{a}_{ij}{y}_j+a_{ii}{y}_i)|\\ & =\frac{1}{\left|a_{ii}\right|}\left|\sum _{\begin{array}{c}j=1\\ j\ne i\end{array}}^m{a}_{ij}(x_j-y_j)\right|⩽\frac{1}{\left|a_{ii}\right|}\sum _{\begin{array}{c}j=1\\ j\ne i\end{array}}^m\left|a_{ij}\right|\Vert x-y\Vert ⩽K\Vert x-y\Vert .\end{array}$$

Theorem. The Gauss-Seidel scheme

$x_{n+1}=(D-L{)}^{-1}U{x}_n+(D-L{)}^{-1}b$ converges to a solution of

$Ax=b$

Proof. Prove it by yourself.

Volterra integral equation

Consider Volterra integral equation

$$f(x)=a+{\int }_0^{x}k(x,y)f(y)dy$$

Concrete example (p.117 in [MH]). Show that the method of successive approximations applied to

$f(x)=1+{\int }_0^{x}f(y)dy$ leads to the usual formula for

$e^x$.

$$\begin{array}{rl}T(0)& =1;\\ T(T(0))& =1+{\int }_0^{x}dy=1+x\\ T(T^2(0))& =1+{\int }_0^x(1+y)dy=1+x+\frac{x^2}{2};\end{array}$$
Hence, this sequence converges

$e^x$.

Theorem. If

$\underset{x\in [0,r]}{sup}{\int }_0^x|k(x,y)|dy=\lambda <1$ then

$$f(x)=a+{\int }_0^{x}k(x,y)f(y)dy$$
has a unique solution on

$[0,r]$.

Proof. See the blackboard.

Example (Ex. 5.6.5 in [MH]). Convert

$dy/dx=3xy,y(0)=1$ to an integral equation and set up an iteration scheme to solve it.
Let

$y(x)=a+{\int }_0^{x}3sy(s)ds$. By

$y(0)=1$, we have

$a=1$. Let initial function

$y=0$.

$$\begin{array}{rl}T(0)& =1;\\ T(T(0))& =1+{\int }_0^{x}3sds=1+\frac{3}{2}{x}^2\\ T(T^2(0))& =1+{\int }_0^{x}3s(1+\frac{3}{2}{s}^2)ds=1+\frac{3}{2}{x}^2+\frac{1}{2}{\left(\frac{3}{2}{x}^2\right)}^2;\end{array}$$
Hence, this sequence converges

$e^{\frac{3}{2}{x}^2}$.

More on integral equations

Theorem (Ex. 5.26 in [MH]). Let

$k(x,y)$ be a continuous real-valued function on the square

$U=\{(x,y)\mid 0⩽x⩽1$,

$0⩽y⩽1\}$ and assume

$|k(x,y)|<1$ for each

$(x,y)\in U$. Let

$A:[0,1]\to \mathbb{R}$ be continuous. Prove that there is a unique continuous real-valued function

$f(x)$ on

$[0,1]$ such that

$$f(x)=A(x)+{\int }_0^{1}k(x,y)f(y)dy.$$

Proof. Prove it by yourself.

Proposition. Let

$f:[0,1]\to \mathbb{R}$ be a continuous function. The unique solution

$v$ of the boundary value problem

$$\begin{array}{rl}& -v^{\prime \prime }=f,\\ & v(0)=0,v(1)=0,\end{array}$$
is given by

$$v(x)={\int }_0^{1}g(x,y)f(y)dy$$
where

$$g(x,y)=\{\begin{array}{ll}x(1-y)& \text{ if }0\le x\le y\le 1\\ y(1-x)& \text{ if }0\le y\le x\le 1\end{array}$$

Proof. Skip!

Let's summarize integral equations which we mentioned.

1. Fredholm Integral Equations
   
   $$u(x)=f(x)+\lambda {\int }_a^{b}K(x,t)u(t)dt$$
2. Volterra Integral Equations
   
   $$u(x)=f(x)+\lambda {\int }_0^{x}K(x,t)u(t)dt.$$

Logistic equation (chaos)

$$x_{n+1}=r{x}_n(1-x_n)$$
Demo, Wiki

Existence & Uniqueness of ODE

Intuiation

Focus on IVP for first-order system ODE

$$\begin{array}{rl}& x^{\prime }(t)=f(x(t),t)\\ \text{(}\mathrm{♣}\text{)}& & x(t_0)=x_0\end{array}$$

Concrete example. (Ex. 7.5.3 in [MH]) Consider the IVP for first-order system ODE

$$\begin{array}{rl}& y^{\prime }(x)=\sqrt{|y|}\\ & y(0)=0\end{array}$$
Solve it directly,

$\frac{dy}{\sqrt{y}}=dx$, and get

$y=\frac{1}{4}(x+c{)}^2$. By IC, we have

$$y=\frac{1}{4}{x}^2$$
for

$x\ge 0$. However,

$$\{\begin{array}{ll}0& \text{ for }0\le x\le \lambda \\ \frac{1}{4}(x-\lambda {)}^2& \text{ for }x\ge \lambda \end{array}$$
is also a solution for all

$\lambda \ge 0$.

Since

$\sqrt{|y|}$ is not good enough, the solution is not unique. If

$f(x,y(x))$ is continuous, then by Peano existence theorem, there exist at least one solution for all IC.

Back to

$(\mathrm{♣})$, define a operator

$$\mathrm{\Phi }(x)(t)=x_0+{\int }_{t_0}^{t}f(x(s),s)ds.$$
If

$x(t)$ is a solution to

$(\mathrm{♣})$, then

$x(t)$ is fixed point of

$\mathrm{\Phi }$.

The problem of finding a solution to

$(\mathrm{♣})$ transforms to a problem of finding a fixed-point of

$\mathrm{\Phi }$.

Concrete example. (Ex. 7.5.5 in [MH]) Find a function

$x(t)$ satisfying

$x^{\prime }(t)=x(t)$ with initial value

$x(0)=1$.
Define

$$\mathrm{\Phi }(x)(t)=1+{\int }_0^{t}x(s)ds,x_0(t)=1$$. Then

$$\begin{array}{rl}& x_1(t)=1+{\int }_0^t{x}_0(s)ds=1+t\\ & x_2(t)=1+{\int }_0^t{x}_1(s)ds=1+t+\frac{t^2}{2}\\ & x_3(t)=1+{\int }_0^t{x}_2(s)ds=1+t+\frac{t^2}{2}+\frac{t^3}{3\cdot 2}\end{array}$$
By induction, we have

$x_k(t)=1+t+\frac{t^2}{2}+\cdots +\frac{t^k}{k!}$
which converges to

$$x(t)=\sum _{k=0}^{\mathrm{\infty }}\frac{t^k}{k!}=e^t.$$

Existence and uniqueness of IVP for ODE

Theorem (locally existence for ODEs). Let

$I=[t_0-T,t_0+T]$. Let

$f:I\times {\overline{B}}_R\left(x_0\right)\to {\mathbb{R}}^n$ be a given continuous mapping. Let

$C=sup\{\Vert f(t,x)\Vert \mid (t,x)\in I\times {\overline{B}}_R\left(x_0\right)\}$. Suppose there is a constant

$K$ such that

$$\Vert f(t,x)-f(t,y)\Vert ⩽K\Vert x-y\Vert$$
for all

$t\in I,x,y\in {\overline{B}}_R\left(x_0\right)$. Let

$\delta <min\{T,R/C,1/K\}$. Then there is a unique continuously differentiable map

$x:[t_0,t_0+\delta ]\to$

${\mathbb{R}}^n$ and

$x\in {\overline{B}}_R(x_0)$ such that (

$\mathrm{♣}$) holds.

Note that

$f$ only need to be locally Lipschitz continuous. Moreover,

$\Vert x-y\Vert$ is the Euclidean norm on

${\mathbb{R}}^n$ instead of

$C^0$ norm.

Proof. See the blackboard.

Example

Example (p.221 in [MH] and p.310 in [DD]) Consider IVP for ODE

$x^{\prime }(t)=x^2$,

$x(0)=1$.
Let

$T,R$ be undetermined. Now

$$\begin{array}{rl}C& =sup\{|f(t,x)|\mid -T⩽t⩽T,-R⩽x-1⩽R\}\\ & =sup\{x^2\mid -R⩽x-1⩽R\}\\ & =(R+1{)}^2.\end{array}$$
Thus,

$R/C=R/(R+1{)}^2$. Also,

$\partial f/\partial x=2x$, so

$$\begin{array}{rl}K& =sup\{2|x|\mid -R⩽x-1⩽R\}\\ & =2(r+1).\end{array}$$

Since

$a$ is not involved we can just choose

$T$ large enough so that it does not interfere, say,

$T=100$. Then, by the theorem, we must choose

$$\delta <min\{\frac{R}{(R+1{)}^2},\frac{1}{2(R+1)}\}.$$

This will work for any choice of

$r$. For example, if we let

$R=1$ we get a time of existence

$\delta <1/4$, i.e.

$[0,1/4]$.

On the other hand, solve by separation of variable

$\frac{x^{\prime }}{x^2}=1$,
and we obtain,

$$x(t)=\frac{1}{1-t}$$
on

$[0,1)$. Therefore, we can re-consider the new IVP for ODE

$$x^{\prime }=x^2,x(a)=\frac{1}{1-a},$$
for

$a=1/4$. Again, let

$a=1/4$,

$$\begin{array}{rl}C& =sup\{|f(t,x)|\mid -T⩽t⩽T,-R⩽x-\frac{1}{1-a}⩽R\}\\ & =sup\{x^2\mid -R⩽x-\frac{1}{1-a}⩽R\}\\ & =(R+\frac{1}{1-a}{)}^2.\end{array}$$
To maximize

$\delta$, let

$R=\frac{1}{1-a}$, which yields

$\delta =\frac{1-a}{4}$. Hence,

$a_2=a_1+(1-a_1)/4=7/16$, i.e.

$[0,7/16]$. Continues this process, we can get

$$a_{n+1}=a_n+\frac{1-a_n}{4}=\frac{3a_n+1}{4}\text{. }$$
and

$a_n\to 1$ as

$n\to \mathrm{\infty }$.

Example (Cont'd Ex. 7.5.3 in [MH] and p.312 in [DD]). Finally, we show

$f(x,y)=\sqrt{|y|}$ is not Lipschitz for

$y_1=0$,

$y_2=h$ and

$x\in \mathbb{R}$.

$$\underset{h\to 0}{lim}\frac{|f(0,h)-f(0,0)|}{|h|}=\underset{h\to 0}{lim}\frac{1}{|h{|}^{1/2}}=+\mathrm{\infty }.$$