\documentclass{amsart}

\usepackage{amsmath}
\usepackage{amssymb}

\input{macros}

\begin{document}
\noindent
\Large Math 554\hfill Autumn 2014

\noindent
Homework Set 8\hfill Due Monday November 24
\bigskip

%\begin{flushleft}
%\begin{tabular}{lp{5.5in}}
%\kern-.1in{\bf Reading} & Coddington \& Levinson, Chapter 1 \S\S 1--6\\
%&Skim through Birkhoff \& Rota, Chap.\ 1 \S\S 1--6, 9--10; Chap.\ 2 \S\S
%1--2, 4; Chap.\ 3 \S\S 1--5; Chap.\ 6 \S\S 1--4
%\end{tabular}
%\end{flushleft}


\begin{enumerate}
\item
\begin{enumerate}
\item Let $f:\R\times\C^n\to\C$ be continuous. Suppose $x:\R\to\C$ is a
solution of the $n^{\mathrm{th}}$-order equation 
$$\mbox{($\ast$)}\qquad\qquad
x^{(n)}=f(t,x,x',\vdots,x^{(n-1)}),$$ i.e., for each $t\in\R$, $x^{(n)}(t)$
exists and $x^{(n)}(t)=f(t,x(t),\ldots, x^{(n-1)}(t))$. Show that $x\in
C^n(\R)$.
\item Define $F:\R\times\C^n\to\C^n$ by
$F(t,y)=[y_2,y_3,\ldots,y_n,f(t,y_1,\ldots,y_n)]^T$ (so $F$ is continuous).
Suppose $y:\R\to\C^n$ is a solution of the first-order system 
$$\mbox{($\ast\ast$)}\qquad\qquad
y'=F(t,y),$$ i.e., for each $t\in\R$, $y'(t)$ exists and $y'(t)=F(t,y(t))$.
Show that $y\in C^1(\R)$, and moreover for $1\le j\le n$, $y_j\in
C^{n-j+1}(\R)$.
\item Show that if $x\in C^n(\R)$ is a solution of ($\ast$), then
$y=[x,x',\ldots, x^{(n-1)}]^T$ is a $C^1$ solution of ($\ast\ast$).
Moreover, if $x$ satisfies the initial conditions $$x^{(k)}(t_0)=x^k_0
\qquad(0\le k\le n-1),$$ then $y$ satisfies the initial conditions
$y(t_0)=[x^0_0,\ldots, x^{n-1}_0]^T$.
\item Show that if $y$ is a $C^1$ solution of ($\ast\ast$), then $x=y_1$ is
a $C^n$ solution of ($\ast$). Moreover, if $y$ satisfies the initial
conditions $y(t_0)=y_0$, then $x$ satisfies the initial conditions
$x^{(k)}(t_0)=(y_0)_{k+1}$ $(0\le k\le n-1)$.
\item Show that the first-order system corresponding to the linear
$n^{\mathrm{th}}$-order equation
$x^{(n)}+a_1(t)x^{(n-1)}+\cdots+a_n(t)x=b(t)$ is of the form $y'=A(t)y+B(t)$
where $A(t)\in\C^{n\times n}$ and $B(t)\in\C^n$, and identify $A(t)$ and
$B(t)$.
\end{enumerate}
\item Let $A\in\C^{n\times n}$ have $\rho (A)<1$.
\begin{enumerate}
\item Show by example that $A$ need not be a contraction with respect to the
Euclidean metric.
\item Show that there is an inner product on $\C^n$ so that $A$ is a
contraction with respect to the norm induced by the inner product.
\item Show that for any $x\in\C^n$, $A^kx\to 0$ as $k\to\infty$.
\end{enumerate}
\item For each of th following IVP's, compute the Picard iterates and
identify the solution to which they converge.
\begin{enumerate}
\item $x'=tx$,\qquad $x(0)=1$\qquad ($x$ scalar)
\item $x'=Ax$,\qquad $x(0)=x_0$\qquad where $A\in\C^{n\times n}$ is a
constant matrix $(x\in\C^n)$.
\end{enumerate}
\item (Gronwall's Inequality --- integral forms) Let $\v$, $\psi$, $\a$ be
real-valued continuous functions on the interval $I=[a,b]$. Suppose $\a\ge
0$ on $I$, and that $$\v(t)\le\psi(t)+\int^t_a\a(s)\v(s)ds\quad \forall\,t\in
I.$$ 
\begin{enumerate}
\item Show that 
$$
\v(t)\le\psi(t)+\int^t_a\exp\left(\int^t_s\a(r)dr\right)\a(s)\psi(s)ds
\quad \forall\,t\in I\ .
$$

\noindent
Hint: Let $u(t)=\int^t_a\a(s)\v(s)ds$ and show that $u'-\a u\le \a\psi$.
\item Supposed that $\psi(t)\equiv c$ (a constant). Show that
$$\v(t)\le c\exp\left(\int^t_a\a(s)ds\right)\quad \forall\,t\in I\ .$$
\end{enumerate}
\item (Iterative Methods for Linear Systems)
\begin{enumerate}
\item Fix $M\in\C^{n\times n}$ and $g\in\C^n$. Given any $x_0\in\C^n$,
define the sequence $\{x_k\}$ iteratively by $x_{k+1}=M{x_k}+g$. Show that
if $\r(M)<1$, then $I-M$ is invertible, and for any choice of $x_0\in\C^n$,
$x_k\to x_\ast$, the unique solution of $(I-M)x=g$. 
\item Suppose $A\in\C^{n\times n}$ is invertible, $b\in\C^n$ is given, and
we want to solve the linear system $Ax=b$ for $x\in\C^n$. A \index{splitting
method}\emph{splitting method} writes $A$ as $A=S-T$ where $S$ is invertible
(and linear systems $Sx=y$ are easily solved), and given $x_0\in\C^n$,
define $\{x_k\}$ by $Sx_{k+1}=Tx_k+b$. Show that if $\r(S^{-1}T)<1$, then
for any choice of $x_0\in\C^n$, $x_k\to x_\ast$, the unique solution of
$Ax=b$.
\item Suppose $A\in\C^{n\times n}$ with nonzero diagonal entries. Write
$A=L+D+U$, where $L$ is strictly lower triangular, $D$ is diagonal, and $U$
is strictly upper triangular. The \emph{Jacobi iteration} is the splitting
method where $S=D$, $T=-(L+U)$. The \index{Gauss-Seidel
iteration}\index{iteration!Gauss-Seidel}\emph{Gauss-Seidel iteration} is the
splitting method where $S=D+L$, $T=-U$. Show that if $A$ is \emph{strictly
(row) diagonally dominant} (i.e., for $1\le i\le n$, $|a_{ii}|>\sum_{1\le
j\le n,j\ne i}|a_{ij}|)$, then $A$ is invertible, and for any given $x_0$,
the Jacobi iteration generates a sequence $\{x_k\}$ which converges to the
unique solution $x_\ast$ of $Ax=b$. 

\noindent
(Hint: Show $\|
|D^{-1}(L+U)|\|_\infty<1$ in the operator norm $\| |\cdot|\|_\infty$ on
$\C^{n\times n}$ induced by the $\ell^\infty$-norm $\|\cdot\|_\infty$ on
$\C^n$.)
\end{enumerate}
[\emph{Remark}: It can be shown that if $A$ is strictly (row) diagonally dominant,
then the Gauss-Seidel iteration converges. As one would expect from the
proof of the Contraction Mapping Fixed Point Theorem, the rate of
convergence depends on $\r(S^{-1}T)$. For some classes of matrices $A$, it
can be shown that $\r_G=\r^2_J$, where $\r_G$ and $\r_J$ are $\r(S^{-1}T)$
for Gauss-Seidel an Jacobi, respectively, so Gauss-Seidel takes roughly half
the number of iterations as Jacobi to achieve the same accuracy. 
%See \S\S 7.1--7.2 of Ortega. 
With the goal of further decreasing $\r(S^{-1}T)$,
Gauss-Seidel has been generalized to the \emph{successive over-relaxation method} 
(SOR): the iteration takes
the form $$(D+\omega L)x_{k+1}=D_{x_k}+\omega[b-(D+U)x_k]$$ where $\omega$
(fixed) is called the relaxation parameter ($\omega<1$ is called
under-relaxation, $\omega>1$ is called over-relaxation); the method was
originally developed for matrices arising from discretizing elliptic PDE's
where values of $\omega>1$ tend to give faster convergence, so the name SOR
has stuck; Gauss-Seidel is SOR with $\omega=1$. Dividing through by
$\omega$, SOR is seen to be a splitting  method $$S_\omega x_{k+1}=T_\omega
x_k+b,$$ where $$S_\omega=\frac{1}{\omega}(D+\omega L)\quad\mbox{and}\quad
T_\omega=\frac{1}{\omega}((1-\omega)D-\omega U).$$ The iteration matrix $M$
(as in (a)) is $$M_\omega=S^{-1}_\omega T_\omega=(D+\omega
L)^{-1}((1-\omega)D-\omega U).$$ It can be shown that if $A\in\R^{n\times n}$
is symmetric positive-definite, then $\r(M_\omega)<1$ (and thus the SOR
iteration converges) iff $0<\omega<2$ (the Ostrowski-Reich Theorem). One
direction (that $0<\omega<2$ is necessary) is shown easily.]
\begin{enumerate}
\item[(d)]Suppose $A\in\C^{n\times n}$ with nonzero diagonal elements,
$\omega\in\R$, and $$M_\omega=(D+\omega L)^{-1}((1-\omega)D-\omega U).$$ Show
that $\r(M_\omega)\ge |\omega-1|$ (and thus $\r(M_\omega)\ge 1$ for
$\omega\le 0$ and for $\omega\ge 2$). 

\noindent
(Hint: Use $$\det(D+\omega L)^{-1}=\det
D^{-1}\quad \mbox{and}\quad \det((1-\omega)D-\omega U)=\det((1-\omega)D)$$ to show that
$\det(M_\omega)=(1-\omega)^n$.)
\item[(e)]Let $A\in\C^{n\times n}$. A matrix $C\in\C^{n\times n}$ is called
an \index{approximate inverse}\index{inverse!approximate}\emph{approximate
inverse} for $A$ if $\r(I-CA)<1$. Show that if $C$ is an approximate inverse
for $A$, then $A$ is invertible, $C$ is invertible, and for any given
$x_0\in\C^n$, the iteration $x_{k+1}=x_k+C(b-Ax_k)$ generates a sequence
$\{x_k\}$ which converges to the unique solution $x_\ast$ of $Ax=b$.
\end{enumerate}
[\emph{Remark}: $r_k=b-Ax_k$ is called the
\index{residual}\emph{residual} at the $k^{\mathrm{th}}$ iteration.]

\item
One-sided uniqueness theorem ($n=1,\ \F=\R$)

\begin{enumerate}
\item
A real-valued function $f(t,u)$ is said to satisfy a one-sided
Lipschitz condition in $u$ if 
$$
u_1 > u_2\quad \Rightarrow\quad f(t,u_1)-f(t,u_2)\le 
L (u_2-u_1)\quad \forall\ t\in\R.
$$
Show that if $f$ is continuous in $t$ and $u$ and satisfies
a one-sided
Lipschitz condition in $u$, then there is at most one 
solution to the IVP $u'=f(t,u),\ u(t_0)=0,$ for $t\ge t_0$.
\item
Let $f(t,u)$ be a real-valued continuous function in $t$ 
and $u$, and suppose that $f$ is decreasing in $u$ for all 
$t$, i.e., $u_2>u_1$ implies that $f(t,u_2)\le f(t,u_1)$.
Show that if $u(t)$ and $v(t)$ are both solutions to
$u'=f(t,u)$, then
$$
|u(t)-v(t)|\le |u(s)-v(s)|\quad\mbox{whenever}\quad 
t\ge s\ .
$$ 
Deduce uniqueness for the IVP 
$u'=f(t,u),\ u(t_0)=0,$ for $t\ge t_0$. Show, however,
that uniqueness may fail for $t<t_0$.
\end{enumerate}
\end{enumerate}
\end{document}

\noindent
\item Use the Contraction Mapping Fixed Point Theorem to prove the following
part of the Inverse Function Theorem:
\begin{enumerate}
\item[]If $\Phi:N\to\R^n$ is a $C^1$ mapping on a neighborhood
$N\subset\R^n$ of $x_0\in\R^n$ satisfying $\Phi(x_0)=y_0$ and
$\Phi'(x_0)\in\R^{n\times n}$ is invertible, then $\Phi$ has a continuous
right inverse $\Psi$ on some neighborhood of $y_0$.
\end{enumerate}
Fill in the details of the following outline. Let $|\cdot|$ denote the
Euclidean norm on $\R^n$ and $\|\cdot\|$ denote the induced operator norm on
$\R^{n\times n}$. With $y\in\R^n$ as a parameter, define
$G(x;y)=x+\Phi'(x_0)^{-1}(y-\Phi(x))$ for $x\in N$. 

\noindent
[Remark: Although
$G$ is a nonlinear function of $x$, notice the similarity with problem 5(e).
In fact, for $x$ near $x_0$, $\Phi'(x_0)^{-1}$ is an approx.\ inverse for
$\Phi'(x)$.] 

\noindent
Let $G'(x;y)$ denote the Jacobian matrix of $G$ with respect to
$x$ (for each fixed $y$).
\begin{enumerate}
\item Show $\exists\,r>0$ with $\overline{B_r(x_0)}\subset N$ (where
$\overline{B_r(x_0)}=\{x\in\R^n:|x-x_0|\le r\}$) for which
$$(\forall\,y\in\R^n)\ (\forall\,x\in\overline{B_r(x_0)}\quad\|G'(x;y)\|\le
\frac{1}{2}.$$  

\noindent
(Hint: Show $G'(x;y)$ is independent of $y$, and
$G'(x_0;y)=0$.)
\item Conclude that
$$(\forall\,y\in\R^n)\ (\forall\,x_1,x_2\in\overline{B_r(x_0)})\quad |G(x_1;y)-G(x_2;y)
\le \frac{1}{2}|x_1-x_2|.$$
\item Let $$s=\frac{r}{2\|\Phi'(x_0)^{-1}\|}.$$ Show that for $$y\in
\overline{B_s(y_0)}=\{y\in\R^n:|y-y_0|\le s\}\ ,$$ $G(x;y)$ (as a function of
$x$) maps $\overline{B_r(x_0)}$ into itself.
\item Show that for each $y\in \overline{B_s(y_0)}$, $G(x;y)$ (as a function
of $x$) has a unique fixed point $x_\ast$ (which we will call $\Psi(y)$) in
$\overline{B_r(x_0)}$. Show that the map $\Psi:\overline{B_s(y_0)}\to
\overline{B_r(x_0)}$ satisfies $$\Phi(\Psi(y))=y\quad
\forall\,y\in\overline{B_s(y_0)}.$$ 
\item Show that $\Psi$ is continuous on $\overline{B_s(y_0)}$. 

\noindent
Hint: For
each fixed $y\in\overline{B_s(y_0)}$, let $G_k(x_0;y)$ denote the
$k^{\mathrm{th}}$ functional iterate of $G(x;y)$ (as a function of $x$)
starting at $x_0$:
$$G_1(x_0;y)=G(x_0;y),$$ and for $k\ge 1$,
$$G_{k+1}(x_0;y)=G(G_k(x_0;y);y).$$ Show that as functions of
$y\in\overline{B_s(y_0)}$, each $G_k(x_0;y)$ is continuous, and $G_k(x_0;y)$
converges \emph{uniformly} to $\Psi(y)$ on $\overline{B_s(y_0)}$.
\end{enumerate}
\end{enumerate}
\end{document}
