Using High Order Finite Differences/Preliminary Estimates

The One-dimensional Problem

Continuous Problem

This book is primarily concerned with finite difference approximations to the solutions of partial differential equations. However, it is both useful in itself and instructive to study the solution of some one-dimensional problems by finite differences.

Consider the meager problem to solve

$-y^{\prime \prime }(x)=f(x)$    on  $a\le x\le b$

subject to the boundary conditions

$y(a)=y(b)=0$.

The following inequality derived next motivates the analysis of the higher-dimensional problems involving the Laplacian operator.

$\underset{a}{\overset{b}{\int }}-y(x)y^{\prime \prime }(x)dx=\underset{a}{\overset{b}{\mid }}-y(x)y^{\prime }(x)+\underset{a}{\overset{b}{\int }}{|y^{\prime }(x)|}^{2}dx=\underset{a}{\overset{b}{\int }}{|y^{\prime }(x)|}^{2}dx$

Making use of inequality () that

$\underset{a}{\overset{b}{\int }}{|y^{\prime }(x)|}^{2}dx\ge \frac{{\pi }^2}{(b-a{)}^2}\underset{a}{\overset{b}{\int }}{|y(x)|}^{2}dx$

and using the equation together with the Cauchy Schwartz inequality

$\underset{a}{\overset{b}{\int }}-y(x)y^{\prime \prime }(x)dx=\underset{a}{\overset{b}{\int }}y(x)f(x)dx\le \sqrt{\underset{a}{\overset{b}{\int }}{|y(x)|}^{2}dx}\sqrt{\underset{a}{\overset{b}{\int }}{|f(x)|}^{2}dx}$.

It follows

$\frac{{\pi }^2}{(b-a{)}^2}\underset{a}{\overset{b}{\int }}{|y(x)|}^{2}dx\le \sqrt{\underset{a}{\overset{b}{\int }}{|y(x)|}^{2}dx}\sqrt{\underset{a}{\overset{b}{\int }}{|f(x)|}^{2}dx}$.

and that

$\sqrt{\underset{a}{\overset{b}{\int }}{|y(x)|}^{2}dx}\le \frac{(b-a{)}^2}{{\pi }^2}\sqrt{\underset{a}{\overset{b}{\int }}{|f(x)|}^{2}dx}$.

Now, consider when  $z(x)$  solves the approximate problem

$-z^{\prime \prime }(x)=g(x)$    on  $a\le x\le b$

subject to the boundary conditions  $z(a)=z(b)=0$,  with  $g(x)$  near  $f(x)$.
Since  $-(y(x)-z(x){)}^{\prime \prime }=(f(x)-g(x))$ ,

$\sqrt{\underset{a}{\overset{b}{\int }}{|y(x)-z(x)|}^{2}dx}\le \frac{(b-a{)}^2}{{\pi }^2}\sqrt{\underset{a}{\overset{b}{\int }}{|f(x)-g(x)|}^{2}dx}$.

This inequality just above will be generalized to both discrete and higher dimensional analogs. This will enable the analysis of the accuracy of finite difference methods for several kinds of equations.

Another point to make is, if non-zero boundary conditions

$y(a)=A,y(b)=B$,

are wanted, then

$y(x)+\frac{(B-A)}{(b-a)}(x-a)+A$

will solve the new problem. So there will not be a loss of generality by assuming zero boundary conditions, in most cases. In the higher dimensional case this will have the effect of separating the problem into two parts.

Solution by Finite Differences

Return to () the problem to solve from the previous section.

$-y^{\prime \prime }(x)=f(x)$    on  $a\le x\le b$

subject to the boundary conditions

$y(a)=y(b)=0$.

This problem may be better by means other than finite differences. For example,

letting  $g(x)=\underset{a}{\overset{x}{\int }}(x-t)f(t)dt$,  and applying the rule (),  $g^{\prime }(x)=(x-x)f(x)+\underset{a}{\overset{x}{\int }}\frac{\partial }{\partial x}(x-t)f(t)dt=\underset{a}{\overset{x}{\int }}f(t)dt$  so that   $g^{\prime \prime }(x)=f(x)$.

Then   $y(x)=g(x)-\frac{g(b)}{b-a}(x-a)$   is a solution of the problem.

However, it will illustrate the finite difference method without being to difficult to follow, for a start. Partial differential equations can on the other hand be difficult to solve by direct analytic methods.

Begin with a partition of the interval given by

$a=x_0<x_1<x_2<\dots <x_n<x_{n+1}=b$.

For simplicities sake, assume a uniform mesh  $h=(b-a)/(n+1)$.

That is to say  $x_i-x_{i-1}=h$    for   $i=1,2,\dots ,n+1$.

For the beginning approximate the second derivative by the second order accurate difference operator

$\frac{d_h^2}{d_h{x}^2}y(x)=h^{-2}(y(x-h)-2y(x)+y(x+h))$.

Define  $f_i=f(x_i)$.  It will be shown that there exist unique

$y_0,y_1,y_2,,\dots ,y_n,y_{n+1}$   with   $y_0=y_{n+1}=0$

that solve the equations

$-h^{-2}(y_{i-1}-2y_i+y_{i+1})=f_i$   for   $i=1,2,\dots ,n$.

In addition, and most importantly, the  $y_i$  approximate  $y(x)$  in the sense

$\sqrt{{\sum }_{i=1}^n{|y(x_i)-y_i|}^2}\le \sqrt{n}B{h}^2$

for some bound  $B$  independent of  $h$.

At this point some clarification must be made and some notation introduced. The term finite difference operator is used for two different, but related operators. One is the difference quotient applied to the function  $y(x)$,  namely

$\frac{d_h^2}{d_h{x}^2}y(x)=h^{-2}(y(x-h)-2y(x)+y(x+h))$

and the other is the linear operator

$h^{-2}(y_{i-1}-2y_i+y_{i+1})$

applied to the vector  $\overrightarrow{y}=<y_0{y}_1{y}_2\dots y_n{y}_{n+1}>$.

The notation

$(\frac{d_h^2}{d_h{x}^2}{)}_i\overrightarrow{y}=h^{-2}(y_{i-1}-2y_i+y_{i+1})$

will be used to distinguish between the two. The equations () can be written as

$-(\frac{d_h^2}{d_h{x}^2}{)}_i\overrightarrow{y}=f_i$.

The linear operator   $(\frac{d_h^2}{d_h{x}^2}{)}_I$  is defined by

$(\frac{d_h^2}{d_h{x}^2}{)}_I\overrightarrow{y}=<(\frac{d_h^2}{d_h{x}^2}{)}_1\overrightarrow{y}(\frac{d_h^2}{d_h{x}^2}{)}_2\overrightarrow{y}\dots (\frac{d_h^2}{d_h{x}^2}{)}_n\overrightarrow{y}>$.

Then   $(\frac{d_h^2}{d_h{x}^2}{)}_I$  can be thought of as

$(\frac{d_h^2}{d_h{x}^2}{)}_I=<(\frac{d_h^2}{d_h{x}^2}{)}_1(\frac{d_h^2}{d_h{x}^2}{)}_2\dots (\frac{d_h^2}{d_h{x}^2}{)}_n>$.

This representation of a linear operator differs from the matrix notation usually used. This has the advantage of allowing estimates to be generalized more easily to higher order operators and two or three dimensional domains.

In fact this linear operator is well studied and has the matrix representation

$\left[\begin{array}{ccccccccc}-2& 1& 0& 0& \cdots & 0& 0& 0& 0\\ 1& -2& 1& 0& \cdots & 0& 0& 0& 0\\ ⋮& ⋮& \ddots & ⋮& \cdots & ⋮& ⋮& ⋮& ⋮\\ ⋮& ⋮& ⋮& ⋮& \ddots & ⋮& ⋮& ⋮& ⋮\\ ⋮& ⋮& ⋮& ⋮& \cdots & ⋮& \ddots & ⋮& ⋮\\ 0& 0& 0& 0& \cdots & 0& 1& -2& 1\\ 0& 0& 0& 0& \cdots & 0& 0& 1& -2\end{array}\right]$,

when applied to the vector  $<y_1{y}_2\dots y_n{>}^T$.

The eigenvalues, eigenvectors, and inverse are known for this matrix, and can be found in some references. If it were just for the sake of this one introductory example the details of this matrix would be used for the analysis. As is being pointed out a method of analysis that generalizes to higher order operators and domains is being developed instead.

Finally the equations () can be written as

$-(\frac{d_h^2}{d_h{x}^2}{)}_I\overrightarrow{y}=\overrightarrow{f}$,

where the vector  $\overrightarrow{f}=<f_1{f}_2\dots f_n>$.

One last piece of notation, for the vector  $\overrightarrow{y}=<y_0{y}_1{y}_2\dots y_n{y}_{n+1}>$, 

the interior points of  $\overrightarrow{y}$,  denoted by  ${\overrightarrow{y}}^o$,  is the  $n$  dimensional vector

${\overrightarrow{y}}^o=<y_1{y}_2\dots y_n>$.

Restating the problem, it will be shown that there exist unique

$\overrightarrow{y}=<y_0{y}_1{y}_2\dots y_n{y}_{n+1}>$   with   $y_0=y_{n+1}=0$

that solve the equation ()

$-(\frac{d_h^2}{d_h{x}^2}{)}_I\overrightarrow{y}=\overrightarrow{f}$,

In addition, and most importantly, the  $y_i$  approximate  $y(x)$  in the sense

$\sqrt{{\sum }_{i=1}^n{|y(x_i)-y_i|}^2}\le \sqrt{n}B{h}^2$

where the bound  $B$  is independent of  $h$  and if fact a good estimate of  $B$  is

$B=M({\alpha }_n{)}^{-1}{h}^2$

where   $M=\frac{1}{12}\underset{a\le x\le b}{\max }(f^{(iv)}(x))$,

${\alpha }_n=2(1-\cos (\pi \frac{1}{n+2}))\to \frac{{\pi }^2}{(n+2{)}^2}$,

and   $B\to \frac{M}{{\pi }^2}$.

The remainder of this section is a proof of the claim () immediately above.

The proof is done by first showing that the operator   $-(\frac{d_h^2}{d_h{x}^2}{)}_I$   is positive definite.

In particular for  ${\alpha }_n=2(1-\cos (\pi \frac{1}{n+2}))\to \frac{{\pi }^2}{(n+2{)}^2}$

$-({\overrightarrow{y}}^o{)}^T(\frac{d_h^2}{d_h{x}^2}{)}_I\overrightarrow{y}\ge {\alpha }_n{h}^{-2}\Vert {\overrightarrow{y}}^o\underset{2}{\overset{2}{\Vert }}$.

To prove what is said immediately above

$\begin{array}{cc}-h^2({\overrightarrow{y}}^o{)}^T(\frac{d_h^2}{d_h{x}^2}{)}_I\overrightarrow{y}=& {\sum }_{i=1}^n{y}_i(-y_{i-1}+2y_i-y_{i+1})\\ =& -{\sum }_{i=1}^n{y}_i((y_{i+1}-y_i)-(y_i-y_{i-1}))\end{array}$.

Rearrange  summation by parts  ()

$\sum _{i=1}^m{w}_i(v_i-v_{i-1})=w_m{v}_m-w_0{v}_0-\sum _{i=0}^{m-1}{v}_i(w_{i+1}-w_i)$

as

$-\sum _{i=0}^{m-1}{v}_i(w_{i+1}-w_i)=-w_m{v}_m+w_0{v}_0+\sum _{i=1}^m{w}_i(v_i-v_{i-1})$

Now, let  $m=n+1$  to get

$-\sum _{i=0}^n{v}_i(w_{i+1}-w_i)=-w_{n+1}{v}_{n+1}+w_0{v}_0+\sum _{i=1}^{n+1}{w}_i(v_i-v_{i-1})$

Set   $v_i=y_i$   for   $i=0,1,\dots ,n+1$.

Set   $w_0=y_0$   and   $w_i=y_i-y_{i-1}$   for   $i=1,2,\dots ,n+1$.

Since   $v_0=v_{n+1}=0$,   the identity becomes

$-\sum _{i=1}^n{v}_i(w_{i+1}-w_i)=\sum _{i=1}^{n+1}{w}_i(v_i-v_{i-1})$,

which is then in turn

$-\sum _{i=1}^n{y}_i((y_{i+1}-y_i)-(y_i-y_{i-1}))=\sum _{i=1}^{n+1}(y_i-y_{i-1})(y_i-y_{i-1})$.

This has proven the equality

$-h^2({\overrightarrow{y}}^o{)}^T(\frac{d_h^2}{d_h{x}^2}{)}_I\overrightarrow{y}=\sum _{i=1}^{n+1}(y_i-y_{i-1}{)}^2$.

Making use of ()

If  $v_0=v_{n+1}=0$  then

$\sqrt{{\sum }_{i=1}^{n+1}(v_i-v_{i-1}{)}^2}\ge \sqrt{2(1-\cos (\pi \frac{1}{n+2}))}\sqrt{{\sum }_{i=1}^n{v}_i^2}$

and

$\sqrt{2(1-\cos (\pi \frac{1}{n+2}))}\to \frac{\pi }{n+2}$.

We have the following

${\sum }_{i=1}^{n+1}(y_i-y_{i-1}{)}^2\ge 2(1-\cos (\pi \frac{1}{n+2})){\sum }_{i=1}^n{y}_i^2$,

where   $2(1-\cos (\pi \frac{1}{n+2}))\to \frac{{\pi }^2}{(n+2{)}^2}$.

This finishes the proof of the claim ().

Since the operator is linear and positive definite,   $\overrightarrow{y}$,   the solution to (), exists and is unique.

The next part is to observe

$-({\overrightarrow{y}}^o{)}^T(\frac{d_h^2}{d_h{x}^2}{)}_I\overrightarrow{y}=({\overrightarrow{y}}^o{)}^T\overrightarrow{f}\le \sqrt{({\overrightarrow{y}}^o{)}^T{\overrightarrow{y}}^o}\sqrt{(\overrightarrow{f}{)}^T\overrightarrow{f}}$.

and putting this together with ()     $-({\overrightarrow{y}}^o{)}^T(\frac{d_h^2}{d_h{x}^2}{)}_I\overrightarrow{y}\ge {\alpha }_n{h}^{-2}\Vert {\overrightarrow{y}}^o{\Vert }^2$

${\alpha }_n{h}^{-2}({\overrightarrow{y}}^o{)}^T{\overrightarrow{y}}^o\le \sqrt{({\overrightarrow{y}}^o{)}^T{\overrightarrow{y}}^o}\sqrt{(\overrightarrow{f}{)}^T\overrightarrow{f}}$

and

$\sqrt{({\overrightarrow{y}}^o{)}^T{\overrightarrow{y}}^o}\le ({\alpha }_n{)}^{-1}{h}^2\sqrt{(\overrightarrow{f}{)}^T\overrightarrow{f}}$.

The notation

$\overrightarrow{y}(x)=<y(x_0)y(x_1)y(x_2)\dots y(x_n)y(x_{n+1})>$

will be used for the exact values of  $y(x)$,  as well as the notation

${\overrightarrow{y}}^o(x)=<y(x_1)y(x_2)\dots y(x_n)>$

for the interior points of  $\overrightarrow{y}(x)$.

The vector  $(\overrightarrow{y}(x)-\overrightarrow{y})$  satisfies the problem

$-(\frac{d_h^2}{d_h{x}^2}{)}_I(\overrightarrow{y}(x)-\overrightarrow{y})=(\frac{d_h^2}{d_h{x}^2}{)}_I\overrightarrow{y}(x)-\overrightarrow{f}$,

with  $(y(a)-y_0)=(y(b)-y_{n+1})=0$.

So the estimate () can be applied to get

$\sqrt{({\overrightarrow{y}}^o(x)-{\overrightarrow{y}}^o{)}^T({\overrightarrow{y}}^o(x)-{\overrightarrow{y}}^o)}\le ({\alpha }_n{)}^{-1}{h}^2\sqrt{((\frac{d_h^2}{d_h{x}^2}{)}_I\overrightarrow{y}(x)-\overrightarrow{f}{)}^T((\frac{d_h^2}{d_h{x}^2}{)}_I\overrightarrow{y}(x)-\overrightarrow{f})}$.

Recall ()

$\frac{d_h^2}{d_h{x}^2}f(x)=f^{\prime \prime }(x)+(\frac{1}{24}{f}^{(iv)}(z_h)+\frac{1}{24}{f}^{(iv)}(z_{-h}))h^2$,

where  $x-h<z_{-h}<x$  and  $x<z_h<x+h$.

Now,

$(\frac{d_h^2}{d_h{x}^2}{)}_I\overrightarrow{y}(x)=<\frac{d_h^2}{d_h{x}^2}y(x_1)\frac{d_h^2}{d_h{x}^2}y(x_2)\dots \frac{d_h^2}{d_h{x}^2}y(x_n)>$

and

$\overrightarrow{f}=<y^{\prime \prime }(x_1)y^{\prime \prime }(x_2)\dots y^{\prime \prime }(x_n)>$.

So each component of    $((\frac{d_h^2}{d_h{x}^2}{)}_I\overrightarrow{y}(x)-\overrightarrow{f})$    has the form

$(\frac{1}{24}{f}^{(iv)}(z_h)+\frac{1}{24}{f}^{(iv)}(z_{-h}))h^2$.

This leads to the estimate

$\sqrt{((\frac{d_h^2}{d_h{x}^2}{)}_I\overrightarrow{y}(x)-\overrightarrow{f}{)}^T((\frac{d_h^2}{d_h{x}^2}{)}_I\overrightarrow{y}(x)-\overrightarrow{f})}\le \sqrt{n}M{h}^2$,

where

  $M=\frac{1}{12}\underset{a\le x\le b}{\max }(f^{(iv)}(x))$.

After combining the inequalities () and ()

$\Vert {\overrightarrow{y}}^o(x)-{\overrightarrow{y}}^o{\Vert }_2\le \sqrt{n}M({\alpha }_n{)}^{-1}{h}^4$.

Generalities about Difference Solutions

Before moving on to describe the effect of using a higher order finite difference operator, it is useful to study some generalities about the solutions of linear equations. This provides the needed motivation to the design of methods and proofs.

Suppose  $L$  is a linear operator that is positive definite, which means to say there exists a constant  $\alpha >0$,  not depending on  $\overrightarrow{x}$  such that

${\overrightarrow{x}}^{T}L\overrightarrow{x}\ge \alpha {\overrightarrow{x}}^T\overrightarrow{x}$.

Then as was explained for matrices at ()

$\Vert L^{-1}{\Vert }_2\le (\alpha {)}^{-1}$.

Now, if the exact solution  $\overrightarrow{y}(x)$  to some problem is given by

$L\overrightarrow{y}(x)=\overrightarrow{f}(x)$

except that  $\overrightarrow{f}(x)$  is only known up to some degree of approximation by  $\overrightarrow{f}$,  then the solution  $\overrightarrow{y}$  to the equation

$L\overrightarrow{y}=\overrightarrow{f}$,

is an approximation to the desired exact solution  $\overrightarrow{y}(x)$.  Since

$L(\overrightarrow{y}(x)-\overrightarrow{y})=(\overrightarrow{f}(x)-\overrightarrow{f})$,

the closeness of the approximation can be estimated with

$\Vert (\overrightarrow{y}(x)-\overrightarrow{y}){\Vert }_2\le \Vert L^{-1}{\Vert }_2\Vert (\overrightarrow{f}(x)-\overrightarrow{f}){\Vert }_2\le (\alpha {)}^{-1}\Vert (\overrightarrow{f}(x)-\overrightarrow{f}){\Vert }_2$.

With regards to finite difference methods the strategy will be to define a linear operator  $L_h$  such that

${\overrightarrow{y}}^T{L}_h\overrightarrow{y}\ge \alpha {\overrightarrow{y}}^T\overrightarrow{y}$,

with  $\alpha$  independent of  $h$.  Then for the exact solution  $\overrightarrow{y}(x)$,  to whatever problem,

$\Vert (\overrightarrow{y}(x)-\overrightarrow{y}){\Vert }_2\le (\alpha {)}^{-1}\Vert (L_h\overrightarrow{y}(x)-L_h\overrightarrow{y}){\Vert }_2$.

When  $L_h\overrightarrow{y}(x)$  is known to some degree of approximation by  $\overrightarrow{f}$, that is when

 $\Vert L_h\overrightarrow{y}(x)-\overrightarrow{f}{\Vert }_2\le B_h$

then for  $\overrightarrow{y}$,  the solution to  $L_h\overrightarrow{y}=\overrightarrow{f}$,

$\Vert (\overrightarrow{y}(x)-\overrightarrow{y}){\Vert }_2\le (\alpha {)}^{-1}\Vert (L_h\overrightarrow{y}(x)-\overrightarrow{f}){\Vert }_2\le (\alpha {)}^{-1}{B}_h$.

Third Order Estimation

In this section the properties of the five-point finite difference operator for the approximation to the second derivative is studied. The notations introduced in the previous sections of this chapter will be reused. The notations   $\overrightarrow{y}$   and   ${\overrightarrow{y}}^o$   will have the same meaning as in the section Solution by Finite Differences. The notations

$(\frac{d_h^2}{d_h{x}^2}{)}_i$   and   $(\frac{d_h^2}{d_h{x}^2}{)}_I$

are redefined to represent the five-point operator.

$-h^2(\frac{\underset{h}{\overset{2}{\partial }}}{{\partial }_h{x}^2}{)}_{1}y=$.
$\frac{1}{12}{y}_4-\frac{1}{3}{y}_3-\frac{1}{2}{y}_2+\frac{5}{3}{y}_1-\frac{11}{12}{y}_0$

$-h^2(\frac{\underset{h}{\overset{2}{\partial }}}{{\partial }_h{x}^2}{)}_{i}y=$.
$\frac{1}{12}{y}_{i+2}-\frac{4}{3}{y}_{i+1}+\frac{5}{2}{y}_i-\frac{4}{3}{y}_{i-1}+\frac{1}{12}{y}_{i-2}$

$\text{for}i=2,3,\dots n-1\text{and}$

$-h^2(\frac{\underset{h}{\overset{2}{\partial }}}{{\partial }_h{x}^2}{)}_{n}y=$.

$-\frac{11}{12}{y}_{n+1}+\frac{5}{3}{y}_n-\frac{1}{2}{y}_{n-1}-\frac{1}{3}{y}_{n-2}+\frac{1}{12}{y}_{n-3}$

The five-point operator for the second derivative is third-order accurate at the ponts nearest the endpoints of the interval and being a centered difference operator, is fourth-order accurate for the more internal points.

The expressions for   $(\frac{d_h^2}{d_h{x}^2}{)}_i$  are rearranged to make the summation procedure to be performed easier to follow. These identities are verified simply by comparing coefficients.

$-h^2(\frac{\underset{h}{\overset{2}{\partial }}}{{\partial }_h{x}^2}{)}_{1}y=\frac{7}{6}(-y_2+2y_1-y_0)$

$\begin{array}{cc}+& (\frac{1}{12}(y_4-y_3)-\frac{1}{3}(y_3-y_2)+\frac{5}{12}(y_2-y_1)-\frac{1}{6}(y_1-y_0))\\ \end{array}$

$-\frac{1}{12}(-y_2+2y_1-y_0)$

$-\frac{1}{12}(-y_3+2y_2-y_1)$

$-h^2(\frac{\underset{h}{\overset{2}{\partial }}}{{\partial }_h{x}^2}{)}_{i}y=\frac{7}{6}(-y_{i+1}+2y_i-y_{i-1})$

$-\frac{1}{12}(-y_{i+2}+2y_{i+1}-y_i)$

$-\frac{1}{12}(-y_i+2y_{i-1}-y_{i-2})$

$\text{for}i=2,3,\dots n-1\text{and}$

$-h^2(\frac{\underset{h}{\overset{2}{\partial }}}{{\partial }_h{x}^2}{)}_{n}y=\frac{7}{6}(-y_{n+1}+2y_n-y_{n-1})$

$\begin{array}{cc}+& (-\frac{1}{12}(y_{n-2}-y_{n-3})+\frac{1}{3}(y_{n-1}-y_{n-2})-\frac{5}{12}(y_n-y_{n-1})+\frac{1}{6}(y_{n+1}-y_n))\\ \end{array}$

$-\frac{1}{12}(-y_n+2y_{n-1}-y_{n-2})$

$-\frac{1}{12}(-y_{n+1}+2y_n-y_{n-1})$

The intent of this section is to establish the inequality.

$-h^2({\overrightarrow{y}}^o{)}^T(\frac{\underset{h}{\overset{2}{\partial }}}{{\partial }_h{x}^2}{)}_I\overrightarrow{y}\ge \frac{2}{3}{\sum }_{i=1}^{n+1}(y_i-y_{i-1}{)}^2$.

This is the most technically difficult part of making estimates as to the accuracy of finite difference approximations. The remainder of the analysis follows by applying the reasoning described in the section Generalities about Difference Solutions. The estimates of the accuracy to which five-point finite differences estimate the second derivative of a function are easier and will be covered in a separate section.

Take into account that  $y_0=0$.   So  $y_1=(y_1-y_0)$  and then

$-h^2{y}_1(\frac{\underset{h}{\overset{2}{\partial }}}{{\partial }_h{x}^2}{)}_1\overrightarrow{y}=\frac{7}{6}{y}_1(-y_2+2y_1-y_0)$

$\begin{array}{cc}+& y_1(\frac{1}{12}(y_4-y_3)-\frac{1}{3}(y_3-y_2)+\frac{5}{12}(y_2-y_1)-\frac{1}{6}(y_1-y_0))\\ \end{array}$

$-\frac{1}{12}{y}_1(-y_2+2y_1-y_0)-\frac{1}{12}{y}_1(-y_3+2y_2-y_1)$

$=\frac{7}{6}{y}_1(-y_2+2y_1-y_0)$

$-\frac{1}{12}{y}_1(-y_2+2y_1-y_0)-\frac{1}{12}{y}_2(-y_3+2y_2-y_1)$

$+\frac{1}{12}(y_2-y_1{)}^2+\frac{1}{6}(y_1-y_0{)}^2$

$-\frac{1}{12}(y_3-y_2)(y_2-y_1)+\frac{1}{12}(y_2-y_1)(y_1-y_0)$

$\begin{array}{cc}+& (\frac{1}{12}(y_4-y_3)-\frac{1}{3}(y_3-y_2)+\frac{1}{3}(y_2-y_1)-\frac{1}{3}(y_1-y_0))(y_1-y_0)\\ \end{array}$

$-h^2{y}_i(\frac{\underset{h}{\overset{2}{\partial }}}{{\partial }_h{x}^2}{)}_i\overrightarrow{y}=\frac{7}{6}{y}_i(-y_{i+1}+2y_i-y_{i-1})$

$-\frac{1}{12}{y}_i(-y_{i+2}+2y_{i+1}-y_i)-\frac{1}{12}{y}_i(-y_i+2y_{i-1}-y_{i-2})$

$=\frac{7}{6}{y}_i(-y_{i+1}+2y_i-y_{i-1})$

$-\frac{1}{12}{y}_{i+1}(-y_{i+2}+2y_{i+1}-y_i)-\frac{1}{12}{y}_{i-1}(-y_i+2y_{i-1}-y_{i-2})$

$+\frac{1}{12}(y_{i+1}-y_i{)}^2+\frac{1}{12}(y_i-y_{i-1}{)}^2$

$-\frac{1}{12}(y_{i+2}-y_{i+1})(y_{i+1}-y_i)-\frac{1}{12}(y_i-y_{i-1})(y_{i-1}-y_{i-2})$

$\text{for}i=2,3,\dots n-1\text{and}$

Take into account that  $y_{n+1}=0$.   So  $y_n=-(y_{n+1}-y_n)$  and then

$-h^2{y}_n(\frac{\underset{h}{\overset{2}{\partial }}}{{\partial }_h{x}^2}{)}_n\overrightarrow{y}=\frac{7}{6}{y}_n(-y_{n+1}+2y_n-y_{n-1})$

$\begin{array}{cc}+& y_n(-\frac{1}{12}(y_{n-2}-y_{n-3})+\frac{1}{3}(y_{n-1}-y_{n-2})-\frac{5}{12}(y_n-y_{n-1})+\frac{1}{6}(y_{n+1}-y_n))\\ \end{array}$

$-\frac{1}{12}{y}_n(-y_n+2y_{n-1}-y_{n-2})-\frac{1}{12}{y}_n(-y_{n+1}+2y_n-y_{n-1})$

$=\frac{7}{6}{y}_n(-y_{n+1}+2y_n-y_{n-1})$

$-\frac{1}{12}{y}_{n-1}(-y_n+2y_{n-1}-y_{n-2})-\frac{1}{12}{y}_n(-y_{n+1}+2y_n-y_{n-1})$

$+\frac{1}{6}(y_{n+1}-y_n{)}^2+\frac{1}{12}(y_n-y_{n-1}{)}^2$

$-\frac{1}{12}(y_n-y_{n-1})(y_{n-1}-y_{n-2})+\frac{1}{12}(y_{n+1}-y_n)(y_n-y_{n-1})$

$\begin{array}{cc}+& (y_{n+1}-y_n)(\frac{1}{12}(y_{n-2}-y_{n-3})-\frac{1}{3}(y_{n-1}-y_{n-2})+\frac{1}{3}(y_n-y_{n-1})-\frac{1}{3}(y_{n+1}-y_n))\\ \end{array}$

This organization of the terms leads to

$-h^2({\overrightarrow{y}}^o{)}^T(\frac{\underset{h}{\overset{2}{\partial }}}{{\partial }_h{x}^2}{)}_I\overrightarrow{y}=-h^2{\sum }_{i=1}^n{y}_i(\frac{\underset{h}{\overset{2}{\partial }}}{{\partial }_h{x}^2}{)}_i\overrightarrow{y}=$

${\sum }_{i=1}^n{y}_i(-y_{i+1}+2y_i-y_{i-1})+\frac{1}{6}{\sum }_{i=1}^{n+1}(y_i-y_{i-1}{)}^2-\frac{1}{6}{\sum }_{i=2}^{n-1}(y_{i+1}-y_i)(y_i-y_{i-1})$

$\begin{array}{cc}+& (\frac{1}{12}(y_4-y_3)-\frac{1}{3}(y_3-y_2)+\frac{1}{3}(y_2-y_1)-\frac{1}{3}(y_1-y_0))(y_1-y_0)\\ \end{array}$

$\begin{array}{cc}+& (y_{n+1}-y_n)(\frac{1}{12}(y_{n-2}-y_{n-3})-\frac{1}{3}(y_{n-1}-y_{n-2})+\frac{1}{3}(y_n-y_{n-1})-\frac{1}{3}(y_{n+1}-y_n))\\ \end{array}$

It is known from () that the sum   ${\sum }_{i=1}^n{y}_i(-y_{i+1}+2y_i-y_{i-1})={\sum }_{i=1}^{n+1}(y_i-y_{i-1}{)}^2$.   Using this and moving the first and last terms of the second sum

$-h^2({\overrightarrow{y}}^o{)}^T(\frac{\underset{h}{\overset{2}{\partial }}}{{\partial }_h{x}^2}{)}_I\overrightarrow{y}=$

${\sum }_{i=1}^{n+1}(y_i-y_{i-1}{)}^2+\frac{1}{6}{\sum }_{i=2}^n(y_i-y_{i-1}{)}^2-\frac{1}{6}{\sum }_{i=2}^{n-1}(y_{i+1}-y_i)(y_i-y_{i-1})$

$\begin{array}{cc}+& (\frac{1}{12}(y_4-y_3)-\frac{1}{3}(y_3-y_2)+\frac{1}{3}(y_2-y_1)-\frac{1}{6}(y_1-y_0))(y_1-y_0)\\ \end{array}$

$\begin{array}{cc}+& (y_{n+1}-y_n)(\frac{1}{12}(y_{n-2}-y_{n-3})-\frac{1}{3}(y_{n-1}-y_{n-2})+\frac{1}{3}(y_n-y_{n-1})-\frac{1}{6}(y_{n+1}-y_n))\\ \end{array}$

Using ()

$|{\sum }_{i=3}^{n-2}(y_{i+1}-y_i)(y_i-y_{i-1})|\le \frac{1}{2}(y_3-y_2{)}^2+{\sum }_{i=4}^{n-2}(y_i-y_{i-1}{)}^2+\frac{1}{2}(y_{n-1}-y_{n-2}{)}^2$,

$|(y_3-y_2)(y_2-y_1)|\le \frac{1}{2}{\alpha }_1^2(y_2-y_1{)}^2+\frac{1}{2}(y_3-y_2{)}^2/{\alpha }_1^2$,

$|(y_n-y_{n-1})(y_{n-1}-y_{n-2})|\le \frac{1}{2}{\beta }_1^2(y_n-y_{n-1}{)}^2+\frac{1}{2}(y_{n-1}-y_{n-2}{)}^2/{\beta }_1^2$,

the inequality next follows.

$-h^2({\overrightarrow{y}}^o{)}^T(\frac{\underset{h}{\overset{2}{\partial }}}{{\partial }_h{x}^2}{)}_I\overrightarrow{y}\ge {\sum }_{i=1}^{n+1}(y_i-y_{i-1}{)}^2-\frac{1}{6}(y_1-y_0{)}^2-\frac{1}{6}(y_{n+1}-y_n{)}^2$

$+\frac{1}{12}(1-1/{\alpha }_1^2)(y_3-y_2{)}^2+\frac{1}{6}(1-\frac{1}{2}{\alpha }_1^2)(y_2-y_1{)}^2$

$+\frac{1}{6}(1-\frac{1}{2}{\beta }_1^2)(y_n-y_{n-1}{)}^2+\frac{1}{12}(1-1/{\beta }_1^2)(y_{n-1}-y_{n-2}{)}^2$

$\begin{array}{cc}+& (\frac{1}{12}(y_4-y_3)-\frac{1}{3}(y_3-y_2)+\frac{1}{3}(y_2-y_1))(y_1-y_0)\\ \end{array}$

$\begin{array}{cc}+& (y_{n+1}-y_n)(\frac{1}{12}(y_{n-2}-y_{n-3})-\frac{1}{3}(y_{n-1}-y_{n-2})+\frac{1}{3}(y_n-y_{n-1}))\\ \end{array}$

Now, using ()

$|(\frac{1}{12}(y_4-y_3)-\frac{1}{3}(y_3-y_2)+\frac{1}{3}(y_2-y_1))(y_1-y_0)|\le$

$\frac{1}{24}({\alpha }_2^2(y_4-y_3{)}^2+\frac{1}{{\alpha }_2^2}(y_1-y_0{)}^2)+\frac{1}{6}({\alpha }_3^2(y_3-y_2{)}^2+\frac{1}{{\alpha }_3^2}(y_1-y_0{)}^2)$

$\frac{1}{6}({\alpha }_4^2(y_2-y_1{)}^2+\frac{1}{{\alpha }_4^2}(y_1-y_0{)}^2)$.

Taking   ${\alpha }_1^2=\frac{1+\sqrt{5}}{2},{\alpha }_2^2=8,$   and   ${\alpha }_3^2={\alpha }_4^2=2+\frac{3-\sqrt{5}}{4}$   yields

$-\frac{1}{6}(y_1-y_0{)}^2+\frac{1}{12}(1-1/{\alpha }_1^2)(y_3-y_2{)}^2+\frac{1}{6}(1-\frac{1}{2}{\alpha }_1^2)(y_2-y_1{)}^2$

$+(\frac{1}{12}(y_4-y_3)-\frac{1}{3}(y_3-y_2)+\frac{1}{3}(y_2-y_1))(y_1-y_0)\ge$

$-\frac{1}{3}((y_4-y_3{)}^2+(y_3-y_2{)}^2+(y_2-y_1{)}^2+(y_1-y_0{)}^2)$.

In identical fashion

$-\frac{1}{6}(y_{n+1}-y_n{)}^2+\frac{1}{6}(1-\frac{1}{2}{\beta }_1^2)(y_n-y_{n-1}{)}^2+\frac{1}{12}(1-1/{\beta }_1^2)(y_{n-1}-y_{n-2}{)}^2$

$+(y_{n+1}-y_n)(\frac{1}{12}(y_{n-2}-y_{n-3})-\frac{1}{3}(y_{n-1}-y_{n-2})+\frac{1}{3}(y_n-y_{n-1}))\ge$

$-\frac{1}{3}((y_{n+1}-y_n{)}^2+(y_n-y_{n-1}{)}^2+(y_{n-1}-y_{n-2}{)}^2+(y_{n-2}-y_{n-3}{)}^2)$.

The sought inequality has been established.

$-h^2({\overrightarrow{y}}^o{)}^T(\frac{\underset{h}{\overset{2}{\partial }}}{{\partial }_h{x}^2}{)}_I\overrightarrow{y}\ge \frac{2}{3}{\sum }_{i=1}^{n+1}(y_i-y_{i-1}{)}^2$.

Two-dimensional Domain

$-h^2(\frac{\underset{h}{\overset{2}{\partial }}}{{\partial }_h{x}^2}{)}_{1,j}e=$.

$\frac{1}{12}{e}_{4,j}-\frac{1}{3}{e}_{3,j}-\frac{1}{2}{e}_{2,j}+\frac{5}{3}{e}_{1,j}-\frac{11}{12}{e}_{0,j}$

$=\frac{7}{6}(-\frac{1}{1}{e}_{2,j}+\frac{2}{1}{e}_{1,j}-\frac{1}{1}{e}_{0,j})$

$\begin{array}{cc}+& (\frac{1}{12}(e_{4,j}-e_{3,j})-\frac{1}{4}(e_{3,j}-e_{2,j})+\frac{5}{12}(e_{2,j}-e_{1,j})-\frac{1}{4}(e_{1,j}-e_{0,j}))\\ \end{array}$

$-h^2(\frac{\underset{h}{\overset{2}{\partial }}}{{\partial }_h{x}^2}{)}_{i,j}e=$.

$\frac{1}{12}{e}_{i+2,j}-\frac{4}{3}{e}_{i+1,j}+\frac{5}{2}{e}_{i,j}-\frac{4}{3}{e}_{i-1,j}+\frac{1}{12}{e}_{i-2,j}$

$=\frac{7}{6}(-\frac{1}{1}{e}_{i+1,j}+\frac{2}{1}{e}_{i,j}-\frac{1}{1}{e}_{i-1,j})$

$+\frac{1}{12}(e_{i+2,j}-e_{i+1,j})-\frac{1}{12}(e_{i+1,j}-e_{i,j})$

$+\frac{1}{12}(e_{i,j}-e_{i-1,j})-\frac{1}{12}(e_{i-1,j}-e_{i-2,j})$

$\text{for}i=2,3,\dots m-1\text{and}$

$-h^2(\frac{\underset{h}{\overset{2}{\partial }}}{{\partial }_h{x}^2}{)}_{m,j}e=$.

$-\frac{11}{12}{e}_{m+1,j}+\frac{5}{3}{e}_{m,j}-\frac{1}{2}{e}_{m-1,j}-\frac{1}{3}{e}_{m-2,j}+\frac{1}{12}{e}_{m-3,j}$

$=\frac{7}{6}(-\frac{1}{1}{e}_{m+1,j}+\frac{2}{1}{e}_{m,j}-\frac{1}{1}{e}_{m-1,j})$

$\begin{array}{cc}+& (-\frac{1}{12}(e_{m-2,j}-e_{m-3,j})+\frac{1}{4}(e_{m-1,j}-e_{m-2,j})-\frac{5}{12}(e_{m,j}-e_{m-1,j})+\frac{1}{4}(e_{m+1,j}-e_{m,j}))\\ \end{array}$

Discrete Laplacian

To approximate u(x, y) numerically, use the grid

$(x_i,y_j),0\le i\le m+1,0\le j\le n+1$.
with
$x_i=ih,y_i=jk$
and
$h=a/(m+1),k=b/(n+1)$

The second partial derivatives

$\frac{{\partial }^2}{\partial x^2}u(x,y)$      and      $\frac{{\partial }^2}{\partial y^2}u(x,y)$

can be approximated on the grid by difference quotients

$(\frac{\underset{h}{\overset{2}{\partial }}}{{\partial }_h{x}^2})u(x_i,y_j)$      and      $(\frac{\underset{k}{\overset{2}{\partial }}}{{\partial }_k{y}^2})u(x_i,y_j)$.

These difference quotients can be chosen by the number of points or the order of accuracy. In either case they will be the same as explained in the section on difference quotients in the chapter Definitions and Basics. The possibilities arising from choosing difference quotients with less than the maximum order of accuracy using some other criteria such as a minimization of the size of or differences in the coefficients, relative to order, is not analyzed at this point.

Since it is cumbersome to include many indices in notations for difference operators the same expression for a difference quotient that approximates a second derivative will be reused for different order operators. The matter as to which one will be made clear when needed. Certain generalities apply to any one of them and can be discussed in this light.

The Laplacian  $\mathrm{\Delta }u(x,y)$  then can be approximated on the interior of the grid by

${\mathrm{\Delta }}_{h,k}u(x_i,y_j)=\frac{\underset{h}{\overset{2}{\partial }}}{{\partial }_h{x}^2}u(x_i,y_j)+\frac{\underset{k}{\overset{2}{\partial }}}{{\partial }_k{y}^2}u(x_i,y_j)$

$(\frac{\underset{h}{\overset{2}{\partial }}}{{\partial }_h{x}^2})u(x_1,y_j)=$.

$\frac{-\frac{1}{12}u(x_1+3h,y_j)+\frac{1}{3}u(x_1+2h,y_j)+\frac{1}{2}u(x_1+h,y_j)-\frac{5}{3}u(x_1,y_j)+\frac{11}{12}u(x_1-h,y_j)}{h^2}$

$(\frac{\underset{h}{\overset{2}{\partial }}}{{\partial }_h{x}^2})u(x_i,y_j)=$.

$\frac{-\frac{1}{12}u(x_i+2h,y_j)+\frac{4}{3}u(x_i+h,y_j)-\frac{5}{2}u(x_i,y_j)+\frac{4}{3}u(x_i-h,y_j)-\frac{1}{12}u(x_i-2h,y_j)}{h^2}$

$\text{for}i=2,3,\dots m-1\text{and}$

$(\frac{\underset{h}{\overset{2}{\partial }}}{{\partial }_h{x}^2})u(x_m,y_j)=$.

$\frac{\frac{11}{12}u(x_m+h,y_j)-\frac{5}{3}u(x_m,y_j)+\frac{1}{2}u(x_m-h,y_j)+\frac{1}{3}u(x_m-2h,y_j)-\frac{1}{12}u(x_m-3h,y_j)}{h^2}$

The second partial derivative
$\frac{{\partial }^2}{\partial y^2}u(x,y)$
can be approximated on the grid by difference quotients
$(\frac{\underset{k}{\overset{2}{\partial }}}{{\partial }_k{y}^2})u(x_i,y_j)$.

These difference quotients are given by

$(\frac{\underset{k}{\overset{2}{\partial }}}{{\partial }_k{y}^2})u(x_i,y_1)=$.

$\frac{-\frac{1}{12}u(x_i,y_1+3k)+\frac{1}{3}u(x_i,y_1+2k)+\frac{1}{2}u(x_i,y_1+k)-\frac{5}{3}u(x_i,y_1)+\frac{11}{12}u(x_i,y_1-k)}{k^2}$

$(\frac{\underset{k}{\overset{2}{\partial }}}{{\partial }_k{y}^2})u(x_i,y_j)=$.

$\frac{-\frac{1}{12}u(x_i,y_j+2k)+\frac{4}{3}u(x_i,y_j+k)-\frac{5}{2}u(x_i,y_j)+\frac{4}{3}u(x_i,y_j-k)-\frac{1}{12}u(x_i,y_j-2k)}{k^2}$

$\text{for}j=2,3,\dots n-1\text{and}$

$(\frac{\underset{k}{\overset{2}{\partial }}}{{\partial }_k{y}^2})u(x_i,y_n)=$.

$\frac{\frac{11}{12}u(x_i,y_n+k)-\frac{5}{3}u(x_i,y_n)+\frac{1}{2}u(x_i,y_n-k)+\frac{1}{3}u(x_i,y_n-2k)-\frac{1}{12}u(x_i,y_n-3k)}{k^2}$