\documentclass[11pt]{article} 
\usepackage[T1]{fontenc}
\usepackage{enumerate}
\usepackage{amsmath}
\usepackage{amsxtra}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
%\usepackage{enumitem}
\usepackage{url}
\usepackage{color,hyperref}
\hypersetup{colorlinks,breaklinks,
             linkcolor=blue,urlcolor=blue,
           anchorcolor=blue,citecolor=blue}

\usepackage[margin=3cm]{geometry}
\newcommand{\eps}{\varepsilon}
\newcommand{\Z}{\mathbb{Z}}
\renewcommand{\L}{\mathcal{L}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\A}{\mathcal{A}}
\newcommand{\K}{\mathcal{K}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\dist}{\text{dist}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\vb}[1]{\mathbf{#1}}
\renewcommand{\phi}{\varphi}
\newcommand{\limn}{\lim_{n\to \infty}}
\newenvironment{bp}{\color{blue}\begin{proof}}{\end{proof}}
\newenvironment{bs}{\color{blue}\begin{proof}[Solution]}{\end{proof}}
\renewcommand{\bar}[1]{\overline{#1}}
\renewcommand{\Im}{\text{Im}}
\renewcommand{\Re}{\text{Re}}
\newcommand{\dudn}{\frac{\partial u}{\partial n}}
\def\Xint#1{\mathchoice
{\XXint\displaystyle\textstyle{#1}}%
{\XXint\textstyle\scriptstyle{#1}}%
{\XXint\scriptstyle\scriptscriptstyle{#1}}%
{\XXint\scriptscriptstyle\scriptscriptstyle{#1}}%
\!\int}
\def\XXint#1#2#3{{\setbox0=\hbox{$#1{#2#3}{\int}$ }
\vcenter{\hbox{$#2#3$ }}\kern-.6\wd0}}
\def\ddashint{\Xint=}
\def\dashint{\Xint-}
\newcommand{\usc}{\text{USC}}
\newcommand{\w}{\mathbf{w}}
\newcommand{\lsc}{\text{LSC}}

\newtheorem*{thm*}{Theorem}

\begin{document}



{ \large \textbf{\textsc{Math 8590 -- Homework 4 (Due Friday Nov 2)}}}
\thispagestyle{empty}
\vspace{0.1in}

Please hand in your solution to 1 problem from those below.

\begin{enumerate}
\item Implement both fast sweeping and fast marching in the programming language of your choice for solving the one dimensional eikonal equation
\[|u'(x)| = f(x) \text{ for }x \in (0,1),\]
with boundary conditions $u(0)=u_0$ and $u(1)=u_1$. Experiment with different funtions $f\geq 0$ and different boundary conditions. Are the boundary conditions always attained continuously? Which method is faster? Produce some plots of solutions to hand in, and turn in a working version of your code.
\item Suppose the numerical solutions $u_h$ of our monotone scheme $S_h=0$ are uniformly Lipschitz continuous, i.e., there exists $C>0$ such that
\[|u_h(x) - u_h(y)| \leq C|x-y| \ \ \text{ for all } x,y \in [0,1]^n_h \text{ and } h>0.\]
This is a stronger form of stability. Prove the Barles-Souganidis convergence theorem from class without assuming \textbf{strong uniqueness}. You can assume that ordinary uniqueness holds, that is, there is at most one viscosity solution satisfying the boundary conditions in the usual sense. [Hint: Use the Arzel\`a-Ascoli Theorem to extract a subsequence $u_{h_k}$ converging uniformly to a continuous function $u \in C([0,1]^n)$. Show that $u$ is the unique viscosity solution, and conclude that the entire sequence must converge uniformly to $u$.]
\item Suppose that $S_h$ depends only on the forward and backward neighboring grid points in each direction, so that we can write
\[S_h(u,u(x),x) = F(\nabla^-_1u(x),-\nabla^+_1u(x),\dots, \nabla^-_nu(x),-\nabla^+_nu(x),u(x),x).\]
Let us set $F=F(a_1,\dots,a_{2n},z,x)$. You may assume that $H$ and $F$ are smooth.
\begin{enumerate}
\item[(a)] Show that $S_h$ is monotone if and only if $F_{a_i}\geq 0$ for all $i$. 
\item[(b)] Show that $S_h$ is consistent if and only if 
\[F(p_1,-p_2,\dots,p_n,-p_n,z,x) = H(p,z,x)\]
for all $p \in \R^n, z\in \R$ and $x \in [0,1]_h^n$.
\item[(c)] Find a monotone and consistent scheme for the linear PDE
\[a_1u_{x_1} + \cdots + a_nu_{x_n} = f(x),\]
where $a_1,\dots,a_n$ are real numbers. Compare your scheme with the direction of the projected characteristics. [Hint: Your solution should depend on the signs of the $a_i$.]
\item[(d)] Suppose that $H$ is Lipschitz continuous and define 
\[a := \sup \left\{ |D_pH(p,z,x)| \, : \, p \in \R^n,\, z \in \R, \, x\in [0,1]^n \right\}.\]
The Lax-Friedrichs scheme is defined by
\[S_h(u,u(x),x) := H\left(\nabla_h u(x),u(x),x\right) - \frac{ah}{2}\Delta_h u(x),\]
where 
\[\nabla_h u(x) := \left(\frac{u(x+he_1) - u(x-he_1)}{2h},\dots,\frac{u(x+he_n) - u(x-he_n)}{2h}\right),\]
and
\[\Delta_h u(x) := \sum_{i=1}^n \frac{u(x+he_i)-2u(x)+u(x-he_i)}{h^2}.\]
Show that the Lax-Friedrichs scheme is monotone and consistent.
[Hint: Rewrite the scheme as a function of the forward and backward differences $\nabla_i^\pm u(x)$, as above.]
\end{enumerate}
\item Let $U:=B^0(0,1)$ and $\eps>0$. Consider the nonlocal integral equation  
\[\text{(I$_\eps$)} \ \ \left\{\begin{aligned}
(1+c\eps^2)u_\eps(x) - \dashint_{B(x,\eps)} u_\eps \, dy &= c\eps^2f(x)&&\text{if } x \in U\\
u_\eps(x) &= 0&&\text{if } x \in \Gamma_\eps,\end{aligned}\right.\]
where $c=\frac{1}{2(n+2)}$, $u_\eps:\Gamma_\eps \cup U \to \R$, $f\in C(\bar{U})$, and
\[\Gamma_\eps = \{x \in \R^n\setminus U \, : \, \text{dist}(x,\partial U) \leq \eps\}.\]
Follow the steps below to show that as $\eps\to 0^+$, $u_\eps$ converges uniformly to the viscosity solution $u$ of
\[\text{(P)} \ \ \left\{\begin{aligned}
u-\Delta u &= f&&\text{in } U\\
u &= 0&&\text{on } \partial U.\end{aligned}\right.\]
The proof is based on recognizing (I$_\eps$) as a monotone approximation scheme for (P). Unless otherwise specified, any function $u:U \to \R$ is implicitly extended to be identically zero on $\Gamma_\eps$. 
\begin{enumerate}[(a)]
\item Show that there exists a unique function $u_\eps\in C(\bar{U})$ solving (I$_\eps$). [Hint: Show that the mapping $T:C(\bar{U}) \to C(\bar{U})$ defined by
\[T[u](x):= \frac{1}{1+c\eps^2}\dashint_{B(x,\eps)} u \, dy + \frac{c\eps^2}{1+c\eps^2} f(x)\]
is a contraction mapping. Use the usual norm $\|u\|:=\max_{\bar{U}} |u|$ on $C(\bar{U})$. Then appeal to Banach's fixed point theorem.]
\item Define $S_\eps:L^\infty(U\cup \Gamma_\eps)\times \R\times U \to \R$ by
\[S_\eps(u,t,x) := (1+c\eps^2)t - \dashint_{B(x,\eps)} u\, dy.\]
Show that $S_\eps$ is monotone, i.e., for all $t \in \R$, $x \in U$, and $u,v\in L^\infty(U\cup \Gamma_\eps)$ 
\[u\leq v \text{ on } B(x,\eps) \implies S_\eps(u,t,x) \geq S_\eps(v,t,x).\]
\item Show that the following comparison principle holds: Let $u,v \in L^\infty(U\cup \Gamma_\eps)$ such that $u\vert_{\bar{U}},v\vert_{\bar{U}} \in C(\bar{U})$. If $u\leq v$ on $\Gamma_\eps$ and $S_\eps(u,u(x),x)\leq S_\eps(v,v(x),x)$ at all $x \in U$, then $u\leq v$ on $U$.
\item Use the comparison principle to show that there exists $C>0$ such that 
\[|u_\eps(x)| \leq C(1 + 3\eps-|x|^2),\]
for all $x \in U$ and $0 < \eps \leq 1$, where $C$ depends only on $\|f\|=\max_{\bar{U}}|f|$. 
[Hint: Compare against $v(x):=C(1+3\eps-|x|^2)$ and $-v$, and adjust the constant $C$ appropriately.]
\item Use the method of weak upper and lower limits to show that $u_\eps \to u$ uniformly on $\bar{U}$, where $u$ is the viscosity solution of (P). You may assume a comparison principle holds for (P) for semicontinuous viscosity solutions. That is, if $u\in \usc(\bar{U})$ is a viscosity subsolution of (P) and $v\in \lsc(\bar{U})$ is a viscosity supersolution, and $u\leq v$ on $\partial U$, then $u \leq v$ in $U$.  [Hint: You will find the identity in the hint from HW1 Problem 4 useful.] 
\end{enumerate}

\end{enumerate}

\end{document}

