Jump to content

Using High Order Finite Differences/Preliminary Estimates

From Wikibooks, open books for an open world

Introduction

[edit | edit source]

The One-dimensional Problem

[edit | edit source]

Continuous Problem

[edit | edit source]

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

    on  

subject to the boundary conditions

.

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

Making use of inequality () that

and using the equation together with the Cauchy Schwartz inequality

.

It follows

.

and that

.

Now, consider when    solves the approximate problem

    on  

subject to the boundary conditions  ,  with    near  .
Since   ,


.

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

,

are wanted, then

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

[edit | edit source]

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

    on  

subject to the boundary conditions

.

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

letting  ,  and applying the rule (),    so that   .


Then      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

.

For simplicities sake, assume a uniform mesh  .

That is to say      for   .

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

.

Define  .  It will be shown that there exist unique

   with   

that solve the equations

   for   .

In addition, and most importantly, the    approximate    in the sense

for some bound    independent of  .

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  ,  namely

and the other is the linear operator

applied to the vector  .

The notation

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

.

The linear operator     is defined by

.

Then     can be thought of as

.

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

,

when applied to the vector  .

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

,

where the vector  .

One last piece of notation, for the vector  

the interior points of  ,  denoted by  ,  is the    dimensional vector

.

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

   with   

that solve the equation ()

,

In addition, and most importantly, the    approximate    in the sense

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

where   ,

,

and   .

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

The proof is done by first showing that the operator      is positive definite.

In particular for  

.

To prove what is said immediately above

.

Rearrange  summation by parts  ()

as

Now, let    to get

Set      for   .

Set      and      for   .

Since   ,   the identity becomes

,

which is then in turn

.

This has proven the equality

.

Making use of ()

If    then

and

.

We have the following

,

where   .

This finishes the proof of the claim ().

Since the operator is linear and positive definite,   ,   the solution to (), exists and is unique.

The next part is to observe

.

and putting this together with ()     

and

.

The notation

will be used for the exact values of  ,  as well as the notation

for the interior points of  .

The vector    satisfies the problem

,

with  .

So the estimate () can be applied to get

.

Recall ()

,

where    and  .

Now,

and

.

So each component of        has the form

.

This leads to the estimate

,

where

  .

After combining the inequalities () and ()

.


Generalities about Difference Solutions

[edit | edit source]

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    is a linear operator that is positive definite, which means to say there exists a constant  ,  not depending on    such that

.

Then as was explained for matrices at ()

.

Now, if the exact solution    to some problem is given by

except that    is only known up to some degree of approximation by  ,  then the solution    to the equation

,

is an approximation to the desired exact solution  .  Since

,

the closeness of the approximation can be estimated with

.

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

,

with    independent of  .  Then for the exact solution  ,  to whatever problem,

.

When    is known to some degree of approximation by  , that is when

 

then for  ,  the solution to  ,

.

Third Order Estimation

[edit | edit source]

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      and      will have the same meaning as in the section Solution by Finite Differences. The notations

   and   

are redefined to represent the five-point operator.

.


.



.

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     are rearranged to make the summation procedure to be performed easier to follow. These identities are verified simply by comparing coefficients.







The intent of this section is to establish the inequality.

.

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  .   So    and then












Take into account that  .   So    and then


This organization of the terms leads to

It is known from () that the sum   .   Using this and moving the first and last terms of the second sum

Using ()


,

,

,

the inequality next follows.

Now, using ()

.

Taking      and      yields

.

In identical fashion

.

The sought inequality has been established.

.


Two-dimensional Domain

[edit | edit source]

.







.







.







Grid Vectors

[edit | edit source]

Discrete Laplacian

[edit | edit source]

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

.
with

and


The second partial derivatives

     and     

can be approximated on the grid by difference quotients

     and      .

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    then can be approximated on the interior of the grid by

.

.

.


The second partial derivative

can be approximated on the grid by difference quotients
.

These difference quotients are given by

.

.

.