Finite Difference Methods
Green’s functions
For a linear differential operator acting on $u$, that is $\mathcal{L} \left[ u \left( x \right) \right]$, which has a differential equation of the form
$$ \begin{equation*} \mathcal{L}\left[ u \left( x \right) \right] = f \left(x \right), \end{equation*} $$then the Green’s function for the operator $\mathcal{L}$, denoted by $G\left( x,s \right)$, can be used to solved the differential equation as
$$ \begin{equation*} u(x) = \int^x G\left(x,s \right) f\left( s \right) \, \mathrm{d}s. \end{equation*} $$Finite Difference Methods
Consider the approximations to the first-order derivative:
- Forward Difference Quotient: $$ \begin{equation*} D_{j}^{+} u = \dfrac{u_{j+1} - u_j}{h} \end{equation*} $$
- Backwards Difference Quotient: $$ \begin{equation*} D_{j}^{-} u = \dfrac{u_{j} - u_{j-1}}{h} \end{equation*} $$
- Central Difference Quotient: $$ \begin{equation*} D_{j}^{0} u = \dfrac{u_{j+1} - u_{j-1}}{2h} \end{equation*} $$
With these, approximations to second-order derivatives can be constructed, for example:
$$ \begin{equation*} \begin{aligned} D_{j}^{\pm} u & = \dfrac{ D_j^{+} u - D_j^{-} u }{h} \\ & = \dfrac{ \dfrac{u_{j+1} - u_j}{h} - \dfrac{u_j - u_{j-1}}{h} }{h} \\ & = \dfrac{ u_{j+1} - 2 u_j + u_{j-1} }{h^2}. \end{aligned} \end{equation*} $$The errors for the approximation of the derivatives are given by
- $u\left( x_j \right) - D_{j}^{+}u = -\dfrac{h}{2} u^{\prime\prime}\left( \xi\right)$ where $\xi \in \left( x_j, x_{j+1} \right)$
- $u\left( x_j \right) - D_{j}^{-}u = \dfrac{h}{2} u^{\prime\prime}\left( \xi\right)$ where $\xi \in \left( x_{j-1}, x_{j} \right)$
- $u\left( x_j \right) - D_{j}^{0}u = -\dfrac{h^2}{6} u^{\prime\prime\prime}\left( \xi\right)$ where $\xi \in \left( x_{j-1}, x_{j+1} \right)$
- $u\left( x_j \right) - D_{j}^{\pm}u = -\dfrac{h^2}{24}\left( u^{(4)}\left( \xi_1\right) + u^{(4)}\left( \xi_2\right) \right)$ where $\xi_1 \in \left( x_{j-1}, x_{j} \right)$ and $\xi_2~\in~\left( x_{j}, x_{j+1} \right)$.
Stability Analysis
Let $V_h$ be the set of discrete functions defined on the nodal points $x_j$ and $V_h^0 \subset V_h$ contain the discrete functions $v_h \in V_h$ which vanish at $x_0$ and $x_n$, i.e. $v_0 =0$ and $v_n=0$.
Let $\mathcal{L}_h$ be the discretization of a linear differential operator which acts on $u_h \in V_h$, i.e. $\mathcal{L}_h \left[ u_h \right]$. If the discrete inner product for both $v_h$ and $w_h \in V_h$ is defined as
$$ \begin{align*} \left( v_h, w_h \right)_{h}^{} & = h \sum\limits_{j=0}^{n} c_j v_j w_j \end{align*} $$where 1 $c_j = 1$ for $j=1, \ldots n-1$ and $c_0 = c_n = \frac{1}{2}$ and a norm is defined as
$$ \begin{equation*} \left\Vert v_h \right\Vert_h = \sqrt{ \left( v_h, v_h \right)_h } \end{equation*} $$for a $v_h \in V_h$.
Then the operator $\mathcal{L}_h$ is symmetric, i.e.
$$ \begin{equation*} \left( \mathcal{L}_h \left[ v_h \right], w_h \right)_h = \left( v_h, \mathcal{L}_h \left[ w_h \right]\right)_h \quad \forall \, w_h , \, v_h \in V^0_h \end{equation*} $$and positive definite, that is
$$ \begin{equation*} \left( \mathcal{L}_h \left[ v_h \right], v_h \right)_h \ge 0 \quad \forall \, v_h \in V^0_h \end{equation*} $$and
$$ \begin{equation*} \left( \mathcal{L}_h \left[ v_h \right], v_h \right)_h = 0 \Longleftrightarrow v_h = 0 . \end{equation*} $$-
This is just the composite trapezium rule, so that the discrete inner product is the discrete analogue to
$$\begin{equation*} \left( w, v \right) = \int w(x) v(x) \, \mathrm{d}x \end{equation*} $$i.e. it approximates an integral. ↩︎
For any $v_h \in V_h$
$$ \begin{equation*} \left\Vert v_h \right\Vert_h \le \dfrac{1}{\sqrt{2}} \Bigg( h \sum \limits_{j=0}^{n-1} \left( \dfrac{v_{j+1} - v_j}{h} \right)^2 \Bigg)^{1/2}. \end{equation*} $$Convergence
The finite difference solution $u_h$ can be characterised by a discrete Green’s function. Define $G^k\left(x\right) \in V_h^0$ such that
$$ \begin{equation*} \mathcal{L}_h \left[ G^k\left(x\right) \right] = e^k\left(x\right) \end{equation*} $$where $e^k \in V_h^0$ satisfies $e^k\left( x_j \right) = \delta_{kj}$. Then
$$ \begin{equation*} G^k \left( x_j \right) = h G\left( x_j, x_k \right) . \end{equation*} $$Let $\left\Vert v_h \right\Vert_{h,\infty} = \max \limits_{0 \le j \le n}\left| v_h\left( x_j \right) \right|$ be the discrete maximum norm.
Assume that $f \in C^2 \left( \left[ 0,1 \right] \right)$, then the nodal error, given by $e\left( x_j \right) = u\left(x_j\right) - u_h\left(x_j\right)$ satisfies:
$$ \begin{equation*} \left\Vert u - u_h \right\Vert_{h,\infty} \le \dfrac{h^2}{96} \left\Vert f^{\prime\prime} \right\Vert_\infty . \end{equation*} $$Galerkin Method
Consider the elementary problem:
$$ \begin{equation*} \left( \alpha u^{\prime} \right)^{\prime} + \beta u^{\prime} + \gamma u = f\left( x \right) \quad \textsf{on} \quad (0,1) \quad \textsf{with} \quad u(0) = u(1)=0 \end{equation*} $$where $\alpha$, $\beta$, $\gamma \in C^0 \left( \left[ 0, 1 \right] \right)$ and $\alpha(x) \ge \alpha_0 >0$ for all $x \in \left[ 0, 1 \right]$.
Next, on $L^2$, define the scalar product
$$ \begin{equation*} \left( f, v \right) = \int \limits_0^1 f v \, \mathrm{d}x \end{equation*} $$and a bilinear form $a : \left( \cdot, \cdot \right)$ which maps $H_0^1 \times H^1_0 \rightarrow \mathbb{R}$
$$ \begin{equation*} a\left( u, v \right) = \int \limits_0^1 \left( \alpha u^\prime v^\prime + \beta u^\prime v + \gamma u v \right) \, \mathrm{d}x \end{equation*} $$and consider the weak form
$$ \begin{equation*} \textsf{Find} \quad u \in H^1_0 \quad \textsf{such that} \quad a\left(u,v \right) =\left( f, v\right) \quad \forall \, v \in H^1_0 \left(0, 1 \right). \end{equation*} $$- Let $u$ be a $C^2$ be a solution of the elementary problem, then $u \in H^1_0$ also solves the weak form problem.
- Let $u \in H^1_0$ be a solution of the weak problem. If and only if $u \in C^2 \left( [ 0, 1 ] \right)$ then $u$ also solves the elementary problem.
Suppose that $f(x)$ is integrable on $(0,1)$ and
$$ \begin{equation*} \int \limits_0^1 \phi(x) f(x) \, \mathrm{d}x = 0 \quad \forall \, \phi(x) \in C^\infty_0\left(\left[ 0,1 \right]\right) \end{equation*} $$then $f(x)=0$.
Let $\Omega \subset \mathbb{R}^n$ be contained in $n$-dimensional cube of length $s$, then
$$ \begin{equation*} \bigl\Vert v \bigr\Vert_{L^2\left(\Omega\right)} \le s \left| v \right|_{H_0^1\left( \Omega \right)}. \end{equation*} $$Let
$$ \begin{equation*} C = \dfrac{1}{\alpha_0} \left( \bigl\Vert \alpha \bigr\Vert_\infty + C_p^2 \left\Vert \gamma \right\Vert_\infty \right) \end{equation*} $$then
$$ \begin{equation*} \left| u - u_h \right| \le C \min\limits_{ w_h \in V_h} \left| u - w_h \right|_{H_0^1\left(0,1\right)}. \end{equation*} $$