1.1 Finite Difference Approximations.md

1.1 Finite Difference Approximations

Let $u(x)$ represent a smooth function of one variable over an interval containing a particular point of interest $\bar{x}$. To approximate $u'(\bar{x})$ by a finite difference approximation based only on values of $u$ at a finite number of points near $\bar{x}$, one obvious choice would be $$D_{+} u(\bar{x}) \equiv \frac{u(\bar{x}+h)-u(\bar{x})}{h} \quad (1.1.1)$$ for some small value of $h$, which is a one-sided approximation to $u'$ since $u$ is evaluated only at values of $x\geq\bar{x}$.

Another one-sided approximation would be $$D_{-} u(\bar{x}) \equiv \frac{u(\bar{x})-u(\bar{x}-h)}{h}. \quad (1.1.2)$$

Each of these formulas gives a first order accurate approximation to $u'(\bar{x})$, meaning that the size of the error $E(h) \equiv Du(\bar{x})-u'(\bar{x})$ is proportional to $h$.

Another option is to use the centered approximation $$D_0 u(\bar{x}) \equiv \frac{u(\bar{x}+h)-u(\bar{x}-h)}{2 h}=\frac{1}{2}\left(D_{+} u(\bar{x})+D_{-} u(\bar{x})\right) \quad (1.1.3)$$ that gives a second order accurate approximation. It has an error proportional to $h^2$ and gives a better approximation than either of the one-side approximations.

1.1.1 Truncation errors

The standard approach to analyzing the error in a finite difference approximation is to expand each of the function values of $u$ in a Taylor series $$f(x)=\sum_{n=0}^{\infty}\frac{f^{(n)}(a)}{n!}(x-a)^n=\sum_{k=0}^{n}\frac{f^{(k)}(a)}{k!}(x-a)^k+O\left((x-a)^{n+1}\right)$$ about the point $\bar{x}$ provided that $u$ is sufficiently smooth, for example, $$u(\bar{x}+h)=u(\bar{x})+h u^{\prime}(\bar{x})+\frac{1}{2} h^2 u^{\prime \prime}(\bar{x})+\frac{1}{6} h^3 u^{\prime \prime \prime}(\bar{x})+\frac{1}{24} h^4 u^{(4)}(\bar{x})+O\left(h^5\right), \quad (1.1.4a)$$ $$u(\bar{x}-h)=u(\bar{x})-h u^{\prime}(\bar{x})+\frac{1}{2} h^2 u^{\prime \prime}(\bar{x})-\frac{1}{6} h^3 u^{\prime \prime \prime}(\bar{x})+\frac{1}{24} h^4 u^{(4)}(\bar{x})+O\left(h^5\right). \quad (1.1.4b)$$

Using $(1.1.4a)$ and $(1.1.4b)$ could compute that $$D_{+} u(\bar{x})=\frac{u(\bar{x}+h)-u(\bar{x})}{h}=u^{\prime}(\bar{x})+\frac{1}{2} h u^{\prime \prime}(\bar{x})+\frac{1}{6} h^2 u^{\prime \prime \prime}(\bar{x})+\frac{1}{24} h^3 u^{(4)}(\bar{x})+O\left(h^4\right),$$ $$D_{-} u(\bar{x})=\frac{u(\bar{x})-u(\bar{x}-h)}{h}=u^{\prime}(\bar{x})-\frac{1}{2} h u^{\prime \prime}(\bar{x})+\frac{1}{6} h^2 u^{\prime \prime \prime}(\bar{x})-\frac{1}{24} h^3 u^{(4)}(\bar{x})+O\left(h^4\right),$$ $$D_0 u(\bar{x})=\frac{1}{2}\left(D_{+} u(\bar{x})+D_{-} u(\bar{x})\right)=u^{\prime}(\bar{x})+\frac{1}{6} h^2 u^{\prime \prime \prime}(\bar{x})+O\left(h^4\right).$$

Then the error in $D_0 u(\bar{x})$ is $$D_0 u(\bar{x})-u^{\prime}(\bar{x})=\frac{1}{6} h^2 u^{\prime \prime \prime}(\bar{x})+O\left(h^4\right).$$ For $h$ sufficiently small, the error will be dominated by the first term $\frac{1}{6} h^2 u^{\prime \prime \prime}(\bar{x})$ and all the other terms will be negligible. So the error is expected to behave like a constant times $h^2$, where the contant has the value $\frac{1}{6}u^{\prime \prime \prime}(\bar{x})$. This confirms the second order accuracy of this approximation.

Note that all the odd order terms of $h$ drop out of the Taylor series expansion for $D_0 u(\bar{x})$. This is typical with centered approximations and generally leads to a higher order approximation.

1.1.2 Derivation of finite difference approximations

The method of undetermined coefficients can be used to derive a finite difference approximation to $u'(\bar{x})$ based on a given set of points. To give a one-sided approximation to $u'(\bar{x})$ based on $u(\bar{x})$, $u(\bar{x}-h)$, and $u(\bar{x}-2h)$ in the form of $$D_2 u(\bar{x})=au(\bar{x})+bu(\bar{x}-h)+cu(\bar{x}-2h),$$ we can expand in Taylor series and collect terms to have $$D_2 u(\bar{x})=(a+b+c) u(\bar{x})-(b+2 c) h u^{\prime}(\bar{x})+\frac{1}{2}(b+4 c) h^2 u^{\prime \prime}(\bar{x})-\frac{1}{6}(b+8 c) h^3 u^{\prime \prime \prime}(\bar{x})+\cdots.$$ If it is going to agree with $u'(\bar{x})$ to higher orders, we need

$$\begin{aligned} a+b+c & =0, \\\ b+2 c & =-1 / h, \\\ b+4 c & =0 . \end{aligned}$$

Solving this linear system gives $$a=3/2h, \quad b=-2/h, \quad c=1/2h,$$ and $$D_2 u(\bar{x})=\frac{1}{2h}(3u(\bar{x})-4u(\bar{x}-h)+u(\bar{x}-2h)).$$ The error in this approximation is $$D_2 u(\bar{x})-u^{\prime}(\bar{x}) = -\frac{1}{6}(b+8 c) h^3 u^{\prime \prime \prime}(\bar{x})+\cdots = -\frac{1}{3} h^2 u^{\prime \prime \prime}(\bar{x})+O\left(h^3\right).$$

1.1.3 Second order derivatives

The standard second order centered approximation $D^2 u(\bar{x})$ to the second derivative $u''(\bar{x})$ can be obtained by repeatedly applying first order differences. By defining a centered approximation with step size $h/2$ $$\hat{D}_0 u(x) \equiv \frac{1}{h}\left(u\left(x+\frac{h}{2}\right)-u\left(x-\frac{h}{2}\right)\right),$$ we find that

$$\begin{aligned} D^2 u(\bar{x}) & =\hat{D}_0\left(\hat{D}_0 u(\bar{x})\right) \\\ & =\frac{1}{h}\left(\left(\frac{u(\bar{x}+h)-u(\bar{x})}{h}\right)-\left(\frac{u(\bar{x})-u(\bar{x}-h)}{h}\right)\right) \\\ & =\frac{1}{h^2}(u(\bar{x}-h)-2 u(\bar{x})+u(\bar{x}+h)) \\\ & =u^{\prime \prime}(\bar{x})+\frac{1}{12} h^2 u^{(4)}(\bar{x})+O\left(h^4\right). \end{aligned}$$

In fact,

$$\begin{aligned} D^2 u(\bar{x}) & =\frac{1}{h}\left(\left(\frac{u(\bar{x}+h)-u(\bar{x})}{h}\right)-\left(\frac{u(\bar{x})-u(\bar{x}-h)}{h}\right)\right) \\\ & =\frac{1}{h}\left(D_{-} u(\bar{x}+h)-D_{-} u(\bar{x})\right) \\\ & =D_{+}\left(D_{-} u(\bar{x})\right) \\\ & =D_{+} D_{-} u(\bar{x}). \end{aligned}$$

Similarly, we have $D^2 u(\bar{x}) = D_{-} D_{+} u(\bar{x})$.

1.1.4 A general approach to deriving the coefficients

The method of undetermined coefficients in Section 1.1.2 can be extended to compute the finite difference coefficients of the approximation to $u^{(k)}(\bar{x})$, based on an arbitrary stencil of $n \geq k+1$ points $x_1, \ldots, x_n$. Assume that $u(x)$ is sufficiently smooth, i.e., at least $n+1$ times continuously differentiable in the interval containing $\bar{x}$ and all the stencil points, then the Taylor series expansions of $u$ at each stencil point $x_i$ about $\bar{x}$ yield $$u\left(x_i\right)=u(\bar{x})+\left(x_i-\bar{x}\right) u^{\prime}(\bar{x})+\cdots+\frac{1}{k !}\left(x_i-\bar{x}\right)^k u^{(k)}(\bar{x})+\cdots,$$ for $i=1, \ldots, n$. We want to find a linear combination of $u(x_1), \ldots, u(x_n)$ that agrees with $u^{(k)}(\bar{x})$ as well as possible. So we want $$c_1 u\left(x_1\right)+c_2 u\left(x_2\right)+\cdots+c_n u\left(x_n\right)=u^{(k)}(\bar{x})+O\left(h^p\right),$$ where $p$ is as large as possible and $h$ is some measure of the width of the stencil such that $\max _{1 \leq i \leq n}\left|x_i-\bar{x}\right| \leq C h$ for some small contant $C$. Following the approach of Section 1.1.2, we choose the coefficients $c_j$ such that

$$\frac{1}{(i-1) !} \sum_{j=1}^n c_j\left(x_j-\bar{x}\right)^{i-1}= \begin{cases}1 & \text { if } i-1=k \\ 0 & \text { otherwise }\end{cases}$$

for $i=1, \ldots, n$. Provided that the stencil points $x_j$ are distinct, the equivalent $n \times n$ Vandermonde system

$$\left[\begin{array}{ccc}1 & \cdots & 1 \\ x_1-\bar{x} & \cdots & x_n-\bar{x} \\ \vdots & \cdots & \vdots \\ \frac{\left(x_1-\bar{x}\right)^k}{k !} & \cdots & \frac{\left(x_n-\bar{x}\right)^k}{k !} \\ \vdots & \cdots & \vdots \\ \frac{\left(x_1-\bar{x}\right)^{n-1}}{(n-1) !} & \cdots & \frac{\left(x_n-\bar{x}\right)^{n-1}}{(n-1) !}\end{array}\right]\left[\begin{array}{c}c_1 \\ c_2 \\ \vdots \\ c_k \\ \vdots \\ c_n\end{array}\right]=\left[\begin{array}{c}0 \\ 0 \\ \vdots \\ 1 \\ \vdots \\ 0\end{array}\right]$$

is nonsingular and has a unique solution.