\input defs
\parindent 0in
\parskip 12pt
\def\Lhat{{\hat L}}
\def\uhat{{\hat u}}
\def\ehat{{\hat e}}
\def\fhat{{\hat f}}
\def\tauhat{{\hat \tau}}
\def\uj{u\ind{}{j}}
\def\ujp{u\ind{}{j+1}}
\def\ujph{u\ind{}{\jph}}
\def\ujm{u\ind{}{j-1}}
\def\ubar{\bar u}
%
\centerline{
\hfill \bf PHY/CAM 381C \hfill FINITE DIFFERENCE METHODS \hfill MAR 6, 1997 \hfill
}
%
\vskip 0.1in

\centerline{
	\hfill \bf EXPECTED BEHAVIOUR OF FINITE-DIFFERENCE APPROXIMATIONS \hfill
}
\centerline{\bf \hfill(CONVERGENCE \& ACCURACY) \hfill}

We have already seen that the basic ``control parameter'' of a typical
FDA (finite-difference approximation) is the mesh-spacing, $h$.
Fundamentally, for sensibly constructed FDA's, we expect the error 
in the approximation to go to 0 as $h$  goes to 0.

{\bf NOTATION:} Let 
$$
	L \, u = f
                                                                \eqno(19.1)
$$
denote a general {\sl differential\/} system.  For simplicity and 
concreteness, you can think of $u = u(x)$ as a single function of one 
variable, but the following discussion also applies to cases in 
multiple independent variables ($u(x,t), u(x,y,t), \,\cdots$ etc.),
as well as multiple {\sl dependent\/} variables ($u = {\bf u} = 
[ u_1, u_2, \, \cdots, u_n]$).

In (19.1), $L$ is some differential operator ($L = d^2/dx^2$ in the BVP
example we've studied previously), and $f$ is some specified function.
We will generically denote an FDA of (19.1) by
$$
	\Lhat \uhat = \fhat
                                                                \eqno(19.2)
$$
where $\uhat$ is the discrete solution, $\fhat$ is the specified 
function evaluated on the finite-difference mesh, and $\Lhat$ is 
the finite-difference approximation to $L$.

{\bf DEFINITIONS}\hfill

{\bf Truncation Error:} The truncation error, $\tauhat$, of an FDA is 
defined by
$$
	\tauhat \equiv \Lhat u - \fhat
                                                                \eqno(19.3)
$$
where $u$ satisfies the continuum system~(19.1).  We note that the {\sl form\/}
of the truncation error can always be computed (often using Taylor series 
expansions) from the finite difference approximation and the 
differential equations---we will see an example shortly.

{\bf Order of a Finite-Difference Approximation:} Assuming that the FDA
is characterized by a {\sl single\/} discretization scale, $h$, we 
say that the FDA is {\sl $p$-th order accurate} or simply 
{\sl $p$-th order} if 
$$
	\lim_{h \to 0} \tauhat = O(h^p) \quad\quad
   \hbox{\rm for some integer~} p
                                                                \eqno(19.4)
$$

{\bf Solution Error:} The solution error, $\ehat$, associated with an 
FDA is defined by
$$
	\ehat \equiv u - \uhat
                                                                \eqno(19.5)
$$

{\bf RELATION BETWEEN TRUNCATION ERROR AND SOLUTION ERROR} \hfill

Is is common to tacitly assume that 
$$
	\tauhat = O(h^p) \quad\quad\hbox{\rm implies}\quad\quad \ehat = O(h^p)
$$
This assumption is often warranted but it is extremely instructive 
to consider {\sl why\/} it is warranted and to investigate in some 
detail the {\sl nature\/} of the solution error, $\ehat$, for a simple 
yet representative example.

{\bf Example:} Consider one of the simplest possible differential systems:
$$
	L \, u(x) \equiv \lb \fr{d}{dx} - 1 \rb \, u(x) = 0
	\quad \hbox{\rm~on~~} 0 \le x \le 1 \quad \hbox{\rm~with~~} u(0) = 1
                                                                \eqno(19.6)
$$
Clearly,  the unique solution of this DE is 
$$
	u(x) = e^x.
$$
We introduce a uniform finite-difference mesh, $x_j$,
$$
	x_j = j h, \quad j = 0, 1, \, \cdots \, n-1 
   \quad \quad \hbox{\rm where~~}h = \fr{1}{n-1}
$$
and consider the following difference {\sl operators:}
$$
\dop x+ \uj \equiv h^{-1} \lb \ujp - \uj \rb                 
                                                                \eqno(19.7)
$$
$$
\dav x+ \uj \equiv \half \lb \ujp + \uj \rb                 
                                                                \eqno(19.8)
$$
Now consider Taylor series expansions of $\uj$ and $\ujp$ about 
$$
\ujph \equiv u(x\ind{}{\jph}) \equiv 
u\lb\half\lb x\ind{}j + x\ind{}\jpo \rb\rb \equiv \ubar
$$
We have
$$\eqalign{
\ujp & = \ubar + \lb \half h \rb \ubar' + \half \lb \half h \rb^2 \ubar''
 + \fr{1}{6} \lb \half h \rb^3 \ubar''' 
 + \fr{1}{24} \lb \half h \rb^4 \ubar'''' + O(h^5) \cr
\uj  & = \ubar - \lb \half h \rb \ubar' + \half \lb \half h \rb^2 \ubar''
 - \fr{1}{6} \lb \half h \rb^3 \ubar''' 
 + \fr{1}{24} \lb \half h \rb^4 \ubar'''' + O(h^5) \cr
}
$$
so 
$$\eqalignno{
\dop x+ \uj & \equiv h^{-1} \lb \ujp - \uj \rb =
	\ubar' + \fr{1}{24}h^2\ubar''' + O(h^4)                        &(19.9)\cr
\dav x+ \uj & \equiv \half \lb \ujp + \uj \rb =
   \ubar + \fr{1}{8}h^2\ubar'' + O(h^4)                           &(19.10)\cr
}
$$
Thus, we can identify the {\sl difference operators}, $\dop x+$ and 
$\dav x+$, with (formal) power series (in $h$) of {\sl differential 
operators}:
$$\eqalignno{
\dop x+ & \equiv \fr{d}{dx} + \fr{1}{24}h^2\fr{d^3}{dx^3} + O(h^4) &(19.11)\cr
\dav x+ & \equiv 1 + \fr{1}{8}h^2\fr{d^2}{dx^2} + O(h^4)           &(19.12)\cr
}$$

We now write down our FDA of (19.6):
$$
\lb \fr{d}{dx} - 1 \rb \, u(x) = 0 \quad\longrightarrow\quad
	\lb \dop x+ - \dav x+ \rb \, \uj = 0 
                                                                \eqno(19.13)
$$
(i.e. $\Lhat = \dop x+ - \dav x+$). Explicitly, we have
$$
\fr{\ujp - \uj}{h} = \fr{\ujp + \uj}{2} \quad\quad
 j = 0, 1, \, \cdots \, n -2 \quad\quad \hbox{\rm with~~} u_0 = u(0) = 1
                                                                \eqno(19.14)
$$

Let us first consider the {\sl truncation error\/}  associated with 
(19.13,19.14):
$$\eqalign{
	\tauhat  \equiv \Lhat u - \fhat = \Lhat u 
      & = \lb \dop x+ - \dav x+ \rb \, u \cr
		& = \lb \fr{d}{dx} + \fr{1}{24}h^2\fr{d^3}{dx^3} -  
              1 - \fr{1}{8}h^2\fr{d^2}{dx^2} + O(h^4) \rb \, \ubar \cr
	 	& = \lb \fr{d}{dx} - 1 \rb \, \ubar + 
          h^2 \lb \fr{1}{24} \fr{d^3}{dx^3} - \fr{1}{8}\fr{d^2}{dx^2} \rb \,
           \ubar + O(h^4) = O(h^2) \cr
}$$
where we have used the original differential equation (19.6)  in the 
form  
$$
\lb \fr{d}{dx} - 1 \rb \, \ubar = 0.
$$

Thus, since $\tauhat = O(h^2)$, our FDA is {\sl second order}. Note, however,
that we had to be careful about choosing the $x$ value about which 
we performed our Taylor series expansions---in general we must choose 
the expansion point which gives the {\sl highest-order\/} truncation
error or, intuitively, the point about which the scheme is naturally 
``centred''.

The FDA~(19.14) is sufficiently simple (and linear) that we can solve 
it explicitly:
$$\eqalign{
\fr{\ujp - \uj}{h}  = \fr{\ujp + \uj}{2} \quad\longrightarrow\quad
	\ujp & = \lb \fr{h^{-1}+\half}{h^{-1}-\half}\rb \, \uj 
    = \lb \fr{1+\fr{h}{2}}{1-\fr{h}{2}} \rb \, \uj \equiv \rho \, \uj
	\quad\hbox{\rm~where~}\rho \equiv \fr{1+\fr{h}{2}}{1-\fr{h}{2}}
}$$
Thus we have
$$
u_j = \rho^j \, u_0 = \rho^j
                                                                \eqno(19.15)
$$
where $\rho^j$ denotes the $j$-th power of $\rho$ and we have used the 
initial condition $u_0 = 1$. Now, we can write $\rho^j$ as 
follows:
$$
	\rho^j = \exp\lb j \ln \rho \rb = 
				\exp \lb j \lb \ln \lb 1 + \fr{h}{2} \rb -          
                           \ln \lb 1 - \fr{h}{2} \rb \rb \rb.
$$
Then, using the Taylor series expansion 
$$
	\ln(1 + x) = x - \fr{1}{2}x^2 + \fr{1}{3}x^3 + O(x^4)
$$
we have
$$
\ln \lb 1 + \fr{h}{2} \rb - \ln \lb 1 - \fr{h}{2} \rb =
	h + \fr{1}{12}h^3 + O(h^5)
$$
so that 
$$\eqalign{
	\rho^j = \exp\lb jh + \lb jh \rb \fr{1}{12}h^2 + O(h^4) \rb & =
   \exp\lb jh \rb \exp \lb jh \fr{h^2}{12} + O(h^4) \rb =
   e^{x_j}\lb 1 + \fr{h^2}{12}\,x_j + O(h^4) \rb \cr
	& = e^{x_j} + \fr{1}{12}h^2\,{x_j}\,e^{x_j} + O(h^4)
}$$
Thus, the {\sl solution error}, $\ehat$ is given by
$$
\ehat = u - \uhat = -\fr{1}{12}h^2 x e^x + O(h^4) = O(h^2)
                                                                \eqno(19.16)
$$
Note in particular, the {\sl form\/} of the solution error; to leading
order it is 
$$
h^2 \times \,\, -\fr{1}{12}xe^x = -h^2 \times e_2(x)
$$
where $e_2(x)$ is a {\sl function} ($\fr{1}{12}xe^x$) with smoothness 
(i.e. magnitude of derivatives) comparable to the continuum solution,
$u(x) = e^x$. 

There is another way to derive~(19.16) which clearly illustrates the 
fundamental lesson concerning the errors in finite difference 
approximations.

Let us {\sl assume\/} that $u$ and $\uhat$ are related by the 
asymptotic ($h\to0$) expansion,
$$
	\uhat = u + h^2\,e_2 + h^4\,e_4 + \, \cdots
                                                                \eqno(19.17)
$$
which we call a {\sl Richardson expansion} (after L.F.~Richardson, who
studied such matters in the early part of this century).

We start with the FDA
$$
\Lhat \, \uhat = 0 \quad\longrightarrow\quad
	\lb \dop x+ - \dav x+ \rb \, \uhat = 0
$$
and replace both $\Lhat$ and $\uhat$ by their ``continuum expansions''
(19.11,19.12,19.17):
$$
\lb \fr{d}{dx} - 1 + h^2 \lb \fr{1}{24}\fr{d^3}{dx^3} - 
		\fr{1}{8}\fr{d^2}{dx^2}\rb + O(h^4)\rb  
\lb u + h^2 \, e_2 + O(h^4) \rb = 0
$$
We now demand that this equation vanish, {\sl order by order,} in $h$.
For the $O(1)$ and $O(h^2)$ cases we have 
$$\eqalign{
	O(1):~&~~\lb\fr{d}{dx} - 1\rb \, u = 0 \quad\longrightarrow\quad
	u = e^2 \quad\quad\hbox{\rm ({\sl consistency\/} of FDA)} \cr
	O(h^2):~&~~\lb\fr{d}{dx} - 1\rb \,e_2 = 
		\lb\fr{1}{8}\fr{d^2}{dx^2} - \fr{1}{24}\fr{d^3}{dx^3}\rb \, u \cr
}$$
Thus, we see that the error function, $e_2$, {\sl itself\/} satisfies a 
differential equation which is very similar in form to the original 
DE.  Moreover, given that we know $u(x) = e^x$, we can solve this
DE for $e_2$.  Specifically, we have 
$$
	\lb \fr{d}{dx} - 1 \rb \, e_2 = \fr{1}{12}\,e^x \quad\longrightarrow\quad
	e_2 = \fr{1}{12} x e^x 
                                                                \eqno(19.18)
$$
and since our original {\sl assumption}~(19.17) was 
$$
	\uhat = u + h^2\,e_2 + O(h^4) = u + \fr{1}{12}h^2 x e^x + O(h^4)
$$
we get 
$$
	\ehat \equiv u - \uhat = -\fr{1}{12}h^2 x e^x + O(h^4)
$$
as previously.

{\bf COMMENTS}\hfill

Even in cases where we {\sl don't\/} know the continuum solution (this 
clearly includes most of the interesting instances where we are likely to 
apply finite-difference techniques), it is still very useful to 
think of {\sl difference operators\/} and {\sl difference solutions\/}
in terms of asymptotic expansions in powers of the mesh spacing, $h$:
$$\eqalign{
\Lhat & = L + h^2\,L_2 + h^4\,L^4 + O(h^6) \cr
\uhat & = u + h^2\,e_2 + h^4\,e^4 + O(h^6) \cr
}$$
so that
$$
\Lhat \, \uhat = \fhat 
$$
actually represents an (infinite) hierarchy of differential systems 
$$\eqalign{
L \, u & = f \cr
L \, e_2 & = -L_2 \, u \cr
& \hbox{\rm etc.}
}$$
In other words, in FDA's of continuum systems, the error is not 
``random''---rather, in principle, it is no less computable than the 
fundamental solution itself.

\vfill\eject
\bye
