FDM.tex

\documentclass[a4paper]{article}

\author{Hidde-Jan Jongsma}
\title{Finite Element Method}
\date{\today}

% Extra symbols and enviroments
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{mathtools}

% Use full page
\usepackage{fullpage}

% Create graphics in LaTex
\usepackage{tikz}

% Extra commands
\newcommand{\Reals}{\mathbb{R}}

\newcommand{\dd}{\mathrm{d}}

\newcommand{\dun}{\frac{\partial u}{\partial n}}
\newcommand{\dux}{\frac{\partial u}{\partial x}}
\newcommand{\duxx}{\frac{\partial^2 u}{\partial x^2}}
\newcommand{\duxxx}{\frac{\partial^3 u}{\partial x^3}}

\newcommand{\duy}{\frac{\partial u}{\partial y}}
\newcommand{\duyy}{\frac{\partial^2 u}{\partial y^2}}
\newcommand{\duyyy}{\frac{\partial^3 u}{\partial y^3}}
\newcommand{\lapu}{\nabla^2 u}

\newcommand{\vct}{\mathbf}

\providecommand{\abs}[1]{\lvert#1\rvert}
\providecommand{\norm}[1]{\lVert#1\rVert}

\newcommand{\LO}{\ensuremath{L_2(\Omega)}}
\newcommand{\HO}{\ensuremath{H^1(\Omega)}}
\newcommand{\HOzero}{\ensuremath{H^1_{(0}(\Omega)}}

\begin{document}

\section{Finite difference method}

In the finite difference method, we discretize the exact solution of
the Helmholtz problem $u(x)$ on a grid $R$ defined on a domain $\Omega
\subseteq \Reals^d$, $d = 1, 2, 3$. Suppose we have a one dimensional
problem with $\Omega = (0, 1)$. We want to approximate $u$ in a fixed
number of points, say $N$. We create a uniform grid
\begin{equation}
  X_h = \left\{ x_i\ |\ x_i = h i,\ i = 0, 1, \ldots, N \right\}
\end{equation}
where we take our gridsize $h = 1/N$. We denote $u_i = u(x_i)$. Now,
we want to discretize our equation for $u$ on $\Omega$
\begin{equation}
  \frac{\dd^2 u}{\dd x^2} + f u = g, \quad \text{on}\ \Omega.
\end{equation}
We can approximate the second derivate of $u$ in a point $x_i$ by
using the Taylor expansion of $u$ at $x_i$. The value of $u$ at points
$x_{i + 1}$ and $x_{i - 1}$ are given by
\begin{align}
  u_{i + 1} & = u_{i} + h \frac{\dd u}{\dd x}
    + \frac{h^2}{2} \frac{\dd^2 u}{\dd x^2}
    + \frac{h^3}{6} \frac{\dd^3 u}{\dd x^3}
    + \frac{h^4}{24} \frac{\dd^4 u}{\dd x^4} 
    + \mathcal{O}(h^5) \\
%
  u_{i - 1} & = u_{i} - h \frac{\dd u}{\dd x}
    + \frac{h^2}{2} \frac{\dd^2 u}{\dd x^2}
    - \frac{h^3}{6} \frac{\dd^3 u}{\dd x^3}
    + \frac{h^4}{24} \frac{\dd^4 u}{\dd x^4}
    + \mathcal{O}(h^5).
\end{align}
By adding these equations, we obtain an estimate for $\dd^2 u / \dd
x^2$ in the point $x_i$,
\begin{equation}
  \frac{\dd^2 u}{\dd x^2}(x_i)
  \approx
    \frac{1}{h^2} \left[ u_{i + 1} - 2 u_i + u_{i - 1} \right].
\end{equation}
This method provides an approximation of order $\mathcal{O}(h^2)$,
since the local error is
\begin{equation*}
  - \frac{h^2}{12} \frac{\dd^4 u}{\dd x^4}(x_i).
\end{equation*}
When we refine our grid, and let $h \rightarrow 0$, the error in our
approximation to the exact solution $u$ goes to $0$ as rapidly as
$h^2$. Of course, the computational effort necessary will increase as
we make our grid smaller.

\subsection{Five-point formula}

We can easily expand the finite difference approach to two dimensions,
by approximating $\nabla^2 u = \dd^2 u / \dd x^2 + \dd^2 u / \dd y^2$
as
\begin{equation}
  \nabla^2 u(x, y) \approx \frac{1}{h^2} \left[
      u(x + h, y) + u(x - h, y) + u(x, y + h)
      + u(x, y - h) - 4 u(x, y) \right].
\end{equation}
This equation is known as the five-point formula, since it
incorporates the value of $u$ at five different points in the plane.
An arrangement of points used for the approximation of a differential
equation is called a \emph{stencil}. The stencil used in the
five-point method is shown in Figure \ref{fig:5pt} and is named the
five-point stencil.

The five-point formula can be modified to account for an irregular
grid. However, this method is often only order $\mathcal{O}(h)$
accurate, where $h$ is a bound on the step size. This method is
commonly used at the boundary of the domain. For small $h$, one can
shift the boundary points such that the regular five-point method can
be used. The errors introduced by this transformation have been shown
to be no greater than those introduced by the use of an irregular
grid \cite{}[BOOK CHAPTER].

\begin{figure}
  \begin{center}
    \begin{tikzpicture}
    \tikzstyle{every node}=[draw,circle,fill=black,minimum size=4pt,
                            inner sep=0pt]

      \draw (0,0) node (0) [label=left:${(x - h, y)}$] {}
        -- ++(0:2.0cm) node (1) [label=-5:${(x, y)}$] {}
        -- ++(90:2.0cm) node (2) [label=right:${(x, y + h)}$] {} 
        ++(-90:4.0cm) node (3) [label=right:${(x, y - h)}$] {}
        ++(45:2.82842712cm) node (4) [label=right:${(x + h, y)}$] {};

      \draw (1) -- (3);
      \draw (1) -- (4);
    \end{tikzpicture}
  \end{center}
  \caption{Five-point stencil.} \label{fig:5pt}
\end{figure}

%\subsection{Linear System}
%In the two dimensional case, we transform the Helmholtz problem to
%\begin{equation}
%  \frac{1}{h^2} \left[
%      u_{i + 1, j} + u_{i - 1, j} + u_{i, j + 1}
%      + u_{i, j - 1} - 4 u_{ij} \right]
%  + f_{ij} u_{ij}
%  = g_{ij},
%\end{equation}
%alternatively written as
%\begin{equation}
%      - u_{i + 1, j} - u_{i - 1, j} - u_{i, j + 1}
%      - u_{i, j - 1} + (4 - h^2 f_{ij}) u_{ij} 
%  = - h^2 g_{ij},
%\end{equation}
%where 
%\begin{equation*}
%  u_{ij} = u(ih, jh), \quad
%  f_{ij} = f(ih , jh) \quad
%  \text{and}\ g_{ij} = g(ih, jh).
%\end{equation*}
%If we 

\end{document}