Back
 JAMP  Vol.6 No.6 , June 2018
Analysis on Sixth-Order Compact Approximations with Richardson Extrapolation for 2D Poisson Equation
Abstract: By using Richardson extrapolation and fourth-order compact finite difference scheme on different scale grids, a sixth-order solution is computed on the coarse grid. Other three techniques are applied to obtain a sixth-order solution on the fine grid, and thus give out three kinds of Richardson extrapolation-based sixth order compact computation methods. By carefully analyzing the truncation errors respectively on 2D Poisson equation, we compare the accuracy of these three sixth order methods theoretically. Numerical results for two test problems are discussed.

1. Introduction

High order and high efficiency numerical computation for partial differential equations is very important in many scientific and engineering modeling problems. Compared to low order (second order) methods, high order methods can achieve satisfactory errors on much coarser grids and thus greatly curtail the computational cost [1] . Although the most extensively used methods to obtain high order accuracy are spectral methods [2] [3] , these methods have some limitations. The most significant one is that the discretization of PDE by spectral methods leads to the solution of large systems of linear or non-linear equations involving full matrices [4] . In contrast, finite difference (and finite element) methods lead to systems with sparse matrices that can be handled by efficient iterative methods to reduce the computation complexity and computation cost substantially [5] . Therefore, taking into account the computational efficiency, we focus on developing numerical algorithms based on high order finite difference methods here. Among various high order finite difference methods, high order compact (HOC) finite difference schemes are extremely noticeable. Compared to using straightforward central differences to obtain high order accuracy on a larger stencil which results the increase of bandwidth of the coefficient matrix and rises to a problem at the points close to the boundaries, the HOC schemes only use the center and adjacent points (i.e., a 9-points stencil is used in HOC schemes in 2D) which avoid extra special treatments for those points close to the boundaries and further improve computational efficiency. In the past two decades, HOC schemes have been well studied. Various fourth order compact (FOC) finite difference schemes have been developed for Poisson equations, convection-diffusion equations, and Navier-Stokes equations [6] [7] [8] [9] .

Recently, there has been growing interest in developing sixth order compact finite difference schemes. By using Taylor series expansion, Soptz and Carey [10] developed a compact scheme which can achieve sixth order accuracy only when the derivatives of the source term can be determined analytically. Sutmann used Padé approximation discussed by Lele [11] on the Taylor expansion for the discretized Laplace operator to develop sixth order compact schemes [12] . Although the schemes need less grid points than the straightforward expansion approach, they are not fully compact since other grid points, since other grid points (besides the center and adjacent points) are involved.. Chu and Fan [13] proposed a three-point combined compact difference scheme, which can achieve sixth order accuracy for the inner grid points and fifth order accuracy for the boundary grid points. However, their scheme asks to compute the dependent variables and their derivatives together which results in a triple-tridiagonal system with high computational cost for solution. In addition, it has a stability problem that, for certain problems with a large meshsize, the computed solution may be oscillatory [14] . Although a finer meshsize may avoid numerical oscillations, the use of fine mesh is contradictory to the motivation of using higher order compact schemes. There are other sixth order finite difference schemes generated similarly [15] [16] , but all of them share common weak points such as:

1) derivatives of source term appeared in the right-hand side which require analytical forms or approximations for the derivatives with certain order accuracy;

2) not complete compact schemes which may cause problems near to the boundaries;

3) complicated resulting linear systems which increase the difficulty of choosing effective iterative solvers.

Another category of sixth order compact approximations is based on Richardson extrapolation which is a technique introduced by Lewis Fry Richardson in the early of 20th century [17] . In numerical analysis, Richardson extrapolation is a sequence acceleration method used to improve the rate of convergence of a sequence and is also the basis of Romberg integration [18] . Although assumptions of smoothness and monotone truncation error convergence in the mesh spacing are involved, using Richardson extrapolation to get higher order accurate solutions is more convenient than developing direct discretizations [19] . We can avoid complicated stencils, wider bandwidth matrices, special considerations for near-boundary points, additional stability analysis, etc. In addition, highly efficient solvers for the resulting large sparse linear system can be easily applied in such sixth order methods. Further more, Richardson extrapolation does not require any knowledge of the underlying methodology except the order of accuracy, which guarantees the minimal intervention to the existing computational tools [20] . Sun et al. [21] first proposed to use Richardson extrapolation on two fourth order solutions of different grained grids to compute sixth order solutions on the fine grid. Then, Wang [22] developed a multiscale multigrid (MSMG) method as a very efficient solver to compute sixth order solutions for the 2D Poisson equation with Richardson extrapolation. Since the extrapolated sixth order solution is only generated on the coarse grid, the key issue of using Richardson extrapolation in the sixth order solution computation is how to obtain sixth order solutions on the fine grid. The most direct way is to inject sixth order coarse grid solution into the fine grid, which allows a subset of fine grid points to get sixth order solutions. Then, other strategies are required to compute sixth order solutions for the rest of the fine grid points and finally make the entire fine grid solution reach sixth order accuracy. At present, there are three such kind of strategies worthy of analysis and discussion. They are: 1) operator based interpolation; 2) multiple coarse grid computation; 3) complete Richardson extrapolation.

In this paper, our goal is to analyze and compare these Richardson extrapolation-based sixth order methods in computational accuracy. Therefore, we first describe these three Richardson extrapolation-based sixth order methods in Section 2. Then, we give a detailed analysis on their truncation errors in Section 3. After that, we use numerical experiments to verify our theoretical analysis in Section 4. At last, the conclusion and comments are given in Section 5.

2. Sixth Order Compact Approximations with Richardson Extrapolation

Consider a 2D Poisson equation in the form of

u x x + u y y = f ( x , y ) , ( x , y ) Ω , (1)

where Ω is a rectangular domain with suitable boundary conditions defined on Ω . The solution u and the forcing term f ( x , y ) are assumed to be sufficiently smooth and have necessary continuous partial derivatives. Ω can be discretized with uniform meshsize h in the x and y coordinate directions. The mesh points are ( x i , y j ) with x i = i h and y j = j h .

Assume we have pth order accurate approximate solutions u i , j 2 h and u i , j h on the Ω 2 h grid and Ω h grid. A (p + 2)th order accurate solution u ˜ i , j 2 h on the Ω 2 h grid can be obtained by the general Richardson extrapolation, which can be written as [18]

u ˜ i , j 2 h = 2 p u 2 i , 2 j h u i , j 2 h 2 p 1 . (2)

To get a sixth order solution, FOC schemes are first used to compute fourth order accurate solutions u i , j 2 h and u i , j h on the coarse grid Ω 2 h and fine grid Ω h , respectively. Then the Richardson extrapolation formula as

u ˜ i , j 2 h = 16 u 2 i , 2 j h u i , j 2 h 15 (3)

is used to compute the sixth order accurate solution u ˜ i , j 2 h on the coarse grid Ω 2 h [22] .

2.1. Richardson Extrapolation with Operator Based Interpolation

One method using Richardson extrapolation to compute a sixth order accurate solution on the fine grid is to use an operator based interpolation scheme, proposed by Wang and Zhang [22] , which iteratively updates the fine grid points in a specific sequence until some convergence condition is satisfied. This process is an iterative refinement procedure and similar to basic iterative methods [5] . The operator based interpolation for the 2D Poisson Equation (1) has the formula as [22]

u ˜ i , j h = 1 20 [ F i , j 4 ( u i + 1, j h + u i 1, j h + u i , j + 1 h + u i , j 1 h ) ( u i + 1, j + 1 h + u i + 1, j 1 h + u i 1, j + 1 h + u i 1, j 1 h ) ] . (4)

2.2. Richardson Extrapolation with Multiple Coarse Grid Computation

The second Richardson extrapolation sixth order computation is to use multiple coarse grids. For a 2D problem, the fine grid can be coarsened into four coarse grids, each of which is composed of one subset of fine grid points from: (even, even) fine grid points, (even, odd) fine grid points, (odd, even) fine grid points, and (odd, odd) fine grid points. The sixth order solution for (even, even) fine grid points comes from Richardson extrapolation. Dai et al. [23] proposed a direct sixth order computation for other three groups of fine grid points based on multiple coarse grids. First, tridiagonal systems are built on the X-odd grid view, which is constructed by (even, even) fine grid points (marked in red) and (odd, even) fine grid points (marked in black) as Figure 1, for computing the sixth order solution of (odd, even) fine grid points. Then, tridiagonal systems are built on the Y-odd grid view, which is constructed by (even, even) fine grid points (marked in red) and (even, odd) fine grid points (marked in blue) as Figure 2, for computing the sixth order solution of (even, odd) fine grid points. At last, for the (odd, odd) fine grid points (marked in green) surrounded by other fine grid points with sixth order solutions (marked in red) as Figure 3,

Figure 1. Illustration of the MCG updating strategy in 2D. (a) X-odd grid view: (even, even) + (odd, even) coarse grid; (b) Y-odd grid view: (even, even) + (even, odd) coarse grid; (c) The fine grid after X-odd and Y-odd grid view computation.

Figure 2. Illustration of the interpolation strategy in 2D. (a) Rotated grid interpolation scheme; (b) Standard grid interpolation scheme.

Figure 3. Comparison of the error and CPU for the Problem 1.

only one step of operator interpolation is needed to reach the sixth order solution. Computation details can be found in [23] .

2.3. Completed Richardson Extrapolation

The third approach of using Richardson extrapolation for computing sixth order solutions is Completed Richardson extrapolation. Completed Richardson extrapolation was developed by Roache and Knupp [19] and once used to produce a fourth order accurate solution on the fine grid. It did not use the extrapolated fourth order solution but rather the correction between the second order solution and the fourth order solution in the interpolation process. Similarly, by using the correction between the fourth order solution and the extrapolated sixth order solution rather than the improved solution itself, we could compute a sixth order solution on the entire fine grid.

Assume u i , j be the exact solution at node ( i , j ) on the fine grid. With the definition of fourth order accurate solution, we have

u i , j = u i , j h + A i , j h 4 + O ( h 6 ) , (5)

where As are the coefficients of the leading error term.

For the (even, even) fine grid points, we could directly inject extrapolated coarse grid solution to get sixth order solution. The correction between the fourth order solution and the extrapolated sixth order solution, say c i , j h , can be used to approximate the leading error term A i , j h 4 . By using Equation (3), we can deduce

A i , j h 4 = c i , j h = 1 15 ( u i , j h u i / 2 , j / 2 2 h ) , i = even , j = even (6)

Then, we could use the correction (6) to approximate corrections for other three subsets of fine grid points, and thus compute sixth order solutions for them.

For the (odd, odd) fine grid points, the rotated grid interpolation, as Figure 2(a), is used to approximate the coefficient A of the leading error term

A i , j = 1 4 ( A i + 1 , j + 1 + A i + 1 , j 1 + A i 1 , j + 1 + A i 1 , j 1 ) + O ( h 2 ) ; i = odd , j = odd . (7)

is used to obtain the formula for sixth order solution computation as

u ˜ i , j h = u i , j h + c i , j h , i = o d d , j = o d d ; (8)

where

c i , j h = 1 4 ( c i + 1 , j + 1 h + c i + 1 , j 1 h + c i 1 , j + 1 h + c i 1 , j 1 h ) .

For the (odd, even) and (even, odd) fine grid points, the standard grid interpolation, as Figure 2(b), is used to approximate the coefficient A of the leading error term

A i , j = 1 4 ( A i + 1 , j + A i 1 , j + A i , j + 1 + A i , j 1 ) + O ( h 2 ) , i = odd , j = even ; i = even , j = odd . (9)

is used to obtain the formula for sixth order solution computation as

u ˜ i , j h = u i , j h + c i , j h , i = odd , j = even ; i = even , j = odd ; (10)

where

c i , j h = 1 4 ( c i + 1 , j h + c i 1 , j h + c i , j + 1 h + c i , j 1 h ) .

3. Truncation Error Analysis

In this section, we will give an analysis of truncation errors to compare the accuracy of three Richardson extrapolation-based sixth order methods described in Section 2. All of these methods need to use FOC schemes to get the fourth order solutions on fine and coarse grids. We first analyze the truncation error of the FOC schemes. For more general applications, we will derive the truncation error for the FOC scheme with unequal meshsizes [8] .

Denote Δ x and Δ y to be the meshsizes in the x and y coordinate directions, respectively. The standard second order central difference operators are

δ x 2 u i , j = u i + 1 , j 2 u i , j + u i 1 , j Δ x 2 , δ y 2 u i , j = u i , j + 1 2 u i , j + u i , j 1 Δ y 2

By using Taylor series, we have

δ x 2 u i , j = u x x + Δ x 2 12 u x 4 + Δ x 4 360 u x 6 + Δ x 6 20160 u x 8 + O ( Δ x 8 ) , (11)

and

δ y 2 u i , j = u y y + Δ y 2 12 u y 4 + Δ y 4 360 u y 6 + Δ y 6 20160 u y 8 + O ( Δ y 8 ) . (12)

From Equations (11) and (12) we can discretize Equation (1) at the grid point x i , j as

δ x 2 u i , j + δ y 2 u i , j = f i , j + 1 12 ( Δ x 2 u x 4 + Δ y 2 u y 4 ) + 1 360 ( Δ x 4 u x 6 + Δ y 4 u y 6 ) + 1 20160 ( Δ x 6 u x 8 + Δ y 6 u y 8 ) + O ( Δ 8 ) . (13)

By taking two times partial derivatives of x and y on both sides of Equation (1), respectively, we have

u x 4 = f x x u y y x x , (14)

and

u y 4 = f x x u x x y y . (15)

Using central difference operators and Taylor series in Equations (14) and (15) gives

( u x 4 ) i , j = δ x 2 f i , j 1 Δ y 2 ( δ x 2 u i , j + 1 2 δ x 2 u i , j + δ x 2 u i , j 1 ) Δ x 2 12 f x 4 Δ x 4 360 f x 6 1 Δ y 2 ( Δ x 2 12 ( Δ y 2 u x 4 y 2 + Δ y 4 12 u x 4 y 4 ) Δ x 4 360 Δ y 2 u x 6 y 2 ) + Δ y 2 12 u x 2 y 4 + Δ y 4 360 u x 2 y 6 + O ( Δ 6 ) , (16)

and

( u y 4 ) i , j = δ y 2 f i , j 1 Δ x 2 ( δ y 2 u i + 1 , j 2 δ y 2 u i , j + δ y 2 u i 1 , j ) Δ y 2 12 f y 4 Δ y 4 360 f y 6 1 Δ x 2 ( Δ y 2 12 ( Δ x 2 u x 2 y 4 + Δ x 4 12 u x 4 y 4 ) Δ y 4 360 Δ x 2 u x 2 y 6 ) + Δ x 2 12 u x 4 y 2 + Δ x 4 360 u x 6 y 2 + O ( Δ 6 ) . (17)

By continuously taking partial derivatives of x on both sides of Equation (14), we get

f x 4 = u x 6 + u x 4 y 2 (18)

f x 6 = u x 8 + u x 6 y 2 . (19)

Similarly, by continuously taking partial derivatives of y on both sides of Equation (15), we get

f y 4 = u y 6 + u x 2 y 4 (20)

f y 6 = u y 8 + u x 2 y 6 . (21)

Substituting Equations (18) and (19) in Equation (16) gives

( u x 4 ) i , j = δ x 2 f i , j 1 Δ y 2 ( δ x 2 u i , j + 1 2 δ x 2 u i , j + δ x 2 u i , j 1 ) Δ x 2 12 u x 6 + Δ y 2 12 u x 2 y 4 + Δ x 2 Δ y 2 144 u x 4 y 4 Δ x 4 360 u x 8 + Δ y 4 360 u x 2 y 6 + O ( Δ 6 ) . (22)

And, substituting Equations (20) and (21) in Equation (17) gives

( u y 4 ) i , j = δ y 2 f i , j 1 Δ x 2 ( δ y 2 u i + 1 , j 2 δ y 2 u i , j + δ y 2 u i 1 , j ) Δ y 2 12 u y 6 + Δ x 2 12 u x 4 y 2 + Δ x 2 Δ y 2 144 u x 4 y 4 Δ y 4 360 u y 8 + Δ x 4 360 u x 6 y 2 + O ( Δ 6 ) . (23)

Then, we use Equations (22) and (23) to replace the u x 4 and u y 4 terms in Equation (13) as

δ x 2 u i , j + δ y 2 u i , j = f i , j + 1 12 ( Δ x 2 δ x 2 f i , j + Δ y 2 δ y 2 f i , j ) 1 12 ( Δ x 2 Δ y 2 ( δ x 2 u i , j + 1 2 δ x 2 u i , j + δ x 2 u i , j 1 ) + Δ y 2 Δ x 2 ( δ y 2 u i + 1 , j 2 δ y 2 u i , j + δ y 2 u i 1 , j ) ) + ( τ 4 ) i , j + ( τ 6 ) i , j + O ( Δ 8 ) , (24)

where

( τ 4 ) i , j = 1 144 ( u x 4 y 2 + u x 2 y 4 ) Δ x 2 Δ y 2 1 240 ( u x 6 Δ x 4 + u y 6 Δ y 4 ) ,

( τ 6 ) i , j = 1 1728 ( Δ x 4 Δ y 2 + Δ x 2 Δ y 4 ) u x 4 y 4 + 1 4320 ( Δ x 2 Δ y 4 u x 2 y 6 + Δ x 4 Δ y 2 u x 6 y 2 ) 11 60480 ( Δ x 6 u x 8 + Δ y 6 u y 8 ) .

Let us use the second order central difference operators in Equation (24),

multiply 6 Δ x 2 on both sides, and denote the mesh aspect ratio λ = Δ x Δ y , we can

get a general FOC scheme like the one presented in [8] as

m 1 ( u i + 1 , j + 1 + u i + 1 , j 1 + u i 1 , j + 1 + u i 1 , j 1 ) + m 2 ( u i , j + 1 + u i , j 1 ) + m 3 ( u i + 1 , j + u i 1 , j ) m 4 u i , j = Δ x 2 2 ( 8 f i , j + f i + 1 , j + f i 1 , j + f i , j + 1 + f i , j 1 ) , (25)

where the coefficients are

m 1 = ( 1 + λ 2 ) / 2 , m 2 = 5 λ 2 1 , m 3 = 5 λ 2 , m 4 = 10 ( 1 + λ 2 ) .

The fourth order truncation error of the FOC scheme (25) is

τ ˜ 4 = { 1 24 λ 2 ( u x 4 y 2 + u x 2 y 4 ) 1 40 ( u x 6 + u y 6 λ 4 ) } Δ x 4 . (26)

And, the sixth order truncation error of the FOC scheme (25) is

τ ˜ 6 = { 1 288 ( 1 λ 2 + 1 λ 4 ) u x 4 y 4 + 1 720 ( u x 2 y 6 λ 4 + u x 6 y 2 λ 2 ) 11 10080 ( u x 8 + u y 8 λ 6 ) } Δ x 6 . (27)

In a special case with Δ x = Δ y = h , the FOC scheme has the form as

u i + 1 , j + 1 + u i + 1 , j 1 + u i 1 , j + 1 + u i 1 , j 1 + 4 ( u i , j + 1 + u i , j 1 + u i + 1 , j + u i 1 , j ) 20 u i , j = h 2 2 ( 8 f i , j + f i + 1 , j + f i 1 , j + f i , j + 1 + f i , j 1 ) . (28)

The fourth order and sixth order truncation errors of the FOC scheme (28) are

τ FOC4 = { 1 24 ( u x 4 y 2 + u x 2 y 4 ) 1 40 ( u x 6 + u y 6 ) } h 4 , (29)

τ FOC6 = { 1 144 u x 4 y 4 + 1 720 ( u x 2 y 6 + u x 6 y 2 ) 11 10080 ( u x 8 + u y 8 ) } h 6 . (30)

Now we can take a look at the truncation error after applying Richardson extrapolation. From the definition of the fourth order accurate solutions on the fine and coarse grids, we have

u h = u h 4 + τ FOC4 + τ FOC6 , (31)

u 2 h = u 2 h 4 + 16 τ FOC4 + 64 τ FOC6 . (32)

Using the Richardson extrapolation Formula (3) gives

u 2 h = u 2 h 6 16 5 τ FOC6 . (33)

Thus, the sixth order truncation error after applying Richardson extrapolation has the form as

τ Extrapo = 16 5 τ FOC6 . (34)

For all Richardson extrapolation-based sixth order compact approximations, the truncation error of (even, even) fine grid points is τ Extrapo because the corresponding sixth order solution is injected from the extrapolated solution of the standard coarse grid. For other three subsets of fine grid points, three computational strategies (operator based interpolation, multiple coarse grid computation, and completed Richardson extrapolation) could be used to obtain sixth order solutions. In the following part, the truncation error analysis for these methods are given respectively.

3.1. Truncation Error of Operator Based Interpolation

The operator based interpolation scheme is from the 9-point FOC scheme (28), which can be iteratively used to approach sixth order solutions for (odd, odd), (odd, even) and (even, odd) fine grid points. It generates a sixth order error in the form as

τ o p = τ FOC4 h 2 = { 1 24 ( u x 4 y 2 + u x 2 y 4 ) 1 40 ( u x 6 + u y 6 ) } h 6 . (35)

The operator based interpolation Equation (4) can be written as

u i , j = u ˜ i , j + τ o p = 1 20 [ F i , j 4 ( u i + 1 , j + u i 1 , j + u i , j + 1 + u i , j 1 ) ( u i + 1 , j + 1 + u i + 1 , j 1 + u i 1 , j + 1 + u i 1 , j 1 ) ] + τ o p . (36)

For any linear equation A u = F , there is a corresponding residual equation A e = r , where e is the error and r is the residual. According to Equation (36), we could get the operator based interpolation on error as

0 = e ˜ i , j + τ o p = 1 20 [ r i , j 4 ( e i + 1 , j + e i 1 , j + e i , j + 1 + e i , j 1 ) ( e i + 1 , j + 1 + e i + 1 , j 1 + e i 1 , j + 1 + e i 1 , j 1 ) ] + τ o p . (37)

When the iterative process of using operator based interpolation converges, the residual r tends to 0. Then Equation (37) becomes to

0 = 1 20 [ 4 ( e i + 1 , j + e i 1 , j + e i , j + 1 + e i , j 1 ) + ( e i + 1 , j + 1 + e i + 1 , j 1 + e i 1 , j + 1 + e i 1 , j 1 ) ] + τ o p . (38)

At this time, the main component of the error is the truncation error.

Assume the truncation errors on (odd, odd), (odd, even) and (even, odd) fine grid points as α o p , β o p and γ o p , respectively. A system of equations on the truncation error for three subsets of fine grid points is generated from Equation (38) as

{ 4 × τ Extrapo + 4 × ( β o p + β o p ) + 4 × ( β o p + β o p ) 20 α o p = τ o p , i = odd , j = odd ; 4 × β o p + 4 × ( τ Extrapo + τ Extrapo ) + 4 × ( α o p + α o p ) 20 β o p = τ o p , i = odd , j = even ; 4 × γ o p + 4 × ( α o p + α o p ) + 4 × ( τ Extrapo + τ Extrapo ) 20 γ o p = τ o p , i = even , j = odd . (39)

From Equation (39), we get

{ α o p = τ Extrapo + 1 6 τ o p , i = odd , j = odd ; β o p = τ Extrapo + 7 48 τ o p , i = odd , j = even ; γ o p = τ Extrapo + 7 48 τ o p , i = even , j = odd . (40)

3.2. Truncation Error of Multiple Coarse Grid Computation

After applying Richardson extrapolation to get sixth order solutions for (even, even) fine grid points, in the multiple coarse grid computation, X-odd grid view and Y-odd grid view are constructed to compute sixth order solutions for (odd, even) and (even, odd) fine grid points, respectively [23] . The X-odd grid view composed by (even, even) and (odd, even) indexed fine grid points is a view of unequal meshsize grid with meshsizes h and 2h in the x and y coordinate directions, respectively. The Y-odd grid view composed by (even, even) and (even, odd) indexed fine grid points is a view of unequal meshsize grid with meshsizes 2h and h in the x and y coordinate directions, respectively. The sixth order computations on the X-odd grid view and the Y-odd grid view by using tridiagonal solvers lead to sixth order truncation errors τ x -odd and τ y -odd , respectively. By using the general fourth order truncation error Equation (26) and setting corresponding mesh aspect ratio λ , we have explicit forms of τ x -odd and τ y -odd as

τ x -odd = { 4 × 1 24 ( u x 4 y 2 + u x 2 y 4 ) 1 40 ( u x 6 + 16 × u y 6 ) } h 6 , λ x -odd = 1 2 ; (41)

τ y -odd = 4 × { 4 × 1 24 ( u x 4 y 2 + u x 2 y 4 ) 1 40 ( 16 × u x 6 + u y 6 ) } h 6 , λ y -odd = 2. (42)

As for the computation of (odd, even) fine grid points on the X-odd grid view

with the mesh aspect ratio λ x -odd = 1 2 , the coefficients in Equation (25) are set as

m 1 = 5 8 , m 2 = 1 4 , m 3 = 19 4 , m 4 = 50 4 .

Assume the truncation error of (odd, even) fine grid points to be α m c g , an equation upon the error of X-odd grid view is generated from Equation (25) with the above coefficients as

5 8 × 4 τ Extrapo + 1 4 × ( α m c g + α m c g ) + 19 4 × ( τ Extrapo + τ Extrapo ) 50 4 α = τ x -odd , (43)

which gives

α m c g = τ Extrapo + τ x -odd 12 . (44)

As for the computation of (even, odd) fine grid points on the Y-odd grid view with the mesh aspect ratio λ y -odd = 2 , the coefficients in Equation (25) are set as

m 1 = 5 2 , m 2 = 19 , m 3 = 1 , m 4 = 50.

Assume the truncation error of (even, odd) fine grid points to be β m c g , an equation upon the error of Y-odd grid view is generated from Equation (25) with the above coefficients as

5 2 × 4 τ Extrapo + 19 × ( τ Extrapo + τ Extrapo ) + 1 × ( β m c g + β m c g ) 50 β m c g = τ y -odd , (45)

which gives

β m c g = τ Extrapo + τ y -odd 48 . (46)

The update for (odd, odd) fine grid points uses the operator based interpolation Equation (4) and updated sixth order solutions of (even, even), (odd, even) and (even, odd) fine grid points. Assume the truncation error of (odd, odd) fine grid points to be γ m c g , an equation upon the error of the fine grid points is generated by Equation (36) as

4 τ Extrapo + 4 × ( α m c g + α m c g ) + 4 × ( β m c g + β m c g ) 20 γ m c g = τ o p , (47)

which gives

γ m c g = τ Extrapo + τ x -odd 30 + τ y -odd 120 + τ o p 20 . (48)

3.3. Truncation Error of Completed Richardson Extrapolation

The completed Richardson extrapolation uses two kinds of interpolation on the correction Equation (6) of (even, even) fine grid points to approximate corrections for other fine grid points. As we all know, interpolation brings error. Next, we will analyze how much of the error.

The A coefficients in Equations (7) and (9) can be viewed as a function of u which has the form of A ( u ) = τ FOC4 / h 4 . Based on the Taylor series expansion, the O ( h 2 ) term in Equation (7) has an explicit form as the

h 2 2 ( 2 ( τ FOC4 / h 4 ) x 2 + 2 ( τ FOC4 / h 4 ) y 2 ) ; while the O ( h 2 ) term in Equation (9) has an explicit form as h 2 4 ( 2 ( τ FOC4 / h 4 ) x 2 + 2 ( τ FOC4 / h 4 ) y 2 ) .

The second order truncation error for Equation (7), which uses rotated grid interpolation to approximate (odd, odd) fine grid points, has the form as

τ RotateInter = { 1 24 u x 4 y 4 + 1 120 ( u x 6 y 2 + u x 2 y 6 ) 1 80 ( u x 8 + u y 8 ) } h 2 ; (49)

while the second order truncation error for Equation (9), which uses standard grid interpolation to approximate (odd, even) and (even, odd) fine grid points, has the form as

τ StandInter = { 1 48 u x 4 y 4 + 1 240 ( u x 6 y 2 + u x 2 y 6 ) 1 160 ( u x 8 + u y 8 ) } h 2 . (50)

We find that τ RotateInter = 2 τ StandInter .

Consider (odd, odd) fine grid points at first. Equation (7) can be re-written as

A i , j = 1 4 ( A i + 1, j + 1 + A i + 1, j 1 + A i 1, j + 1 + A i 1, j 1 ) + τ RotateInter , i = odd , j = odd . (51)

The sixth order computation for the (odd, odd) fine grid points is only related to (even, even) fine grid points. For the (even, even) fine grid points, by using definition of fourth order solutions obtained from the FOC scheme, we have

A even,even = 1 h 4 [ u even,even u even,even 4 τ FOC6 ] . (52)

After injecting the extrapolated coarse grid solution into the fine grid, we have

u even,even = u even,even 6 + τ Extrapo . (53)

Substituting Equation (53) into Equation (52) gives

A even,even = 1 h 4 [ u even,even 6 u even,even 4 τ FOC6 + τ Extrapo ] = 1 h 4 [ c even,even τ FOC6 + τ Extrapo ] . (54)

By using Equations (8), (51) and (54), we get the truncation error of the (odd, odd) fine grid points as

τ CompEx1 = u i , j u i , j 6 = ( u i , j 4 + A i , j h 4 + τ FOC6 ) ( u i , j 4 + 1 4 ( c i + 1 , j + 1 + c i + 1 , j 1 + c i 1 , j + 1 + c i 1 , j 1 ) ) = ( u i , j 4 + A i , j h 4 + τ FOC6 ) ( u i , j 4 + 1 4 ( A i + 1 , j + 1 + A i + 1 , j 1 + A i 1 , j + 1 + A i 1 , j 1 ) h 4 + τ FOC6 τ Extrapo ) = τ RotateInter h 4 + τ Extrapo , i = odd , j = odd . (55)

Then consider (odd, even) and (even, odd) fine grid points. Equation (9) can be re-written as

A i , j = 1 4 ( A i + 1 , j + A i 1 , j + A i , j + 1 + A i , j 1 ) + τ StandInter , i = odd , j = even ; i = even , j = odd . (56)

The sixth order computation for the (odd, even) and (even, odd) fine grid points are related to both (even, even) and (odd, odd) fine grid points. For the updated (odd, odd) fine grid points, we have

u odd,odd = u odd,odd 6 + τ CompEx1 = u odd,odd 6 + τ RotateInter h 4 + τ Extrapo . (57)

By using the definition of fourth order solutions obtained from the FOC scheme, we have

A odd,odd = 1 h 4 [ u odd,odd u odd,odd 4 τ FOC6 ] . (58)

Substituting Equation (57) into Equation (58) gives

A odd,odd = 1 h 4 [ u odd,odd 6 u odd,odd 4 τ FOC6 + τ RotateInter h 4 + τ Extrapo ] = 1 h 4 [ c odd,odd τ FOC6 + τ RotateInter h 4 + τ Extrapo ] . (59)

By using Equations (10), (54), (56) and (59), we get the truncation errors of the (even, odd) and (odd, even) fine grid points as

τ CompEx2 = u i , j u i , j 6 = ( u i , j 4 + A i , j h 4 + τ FOC6 ) ( u i , j 4 + 1 4 ( c i + 1 , j + c i 1 , j + c i , j + 1 + c i , j 1 ) ) = ( u i , j 4 + A i , j h 4 + τ FOC6 ) ( u i , j 4 + 1 4 ( A i + 1 , j + A i 1 , j + A i , j + 1 + A i , j 1 ) h 4 + τ FOC6 1 2 τ RotateInter h 4 τ Extrapo ) = τ StandInter h 4 + 1 2 τ RotateInter h 4 + τ Extrapo = τ RotateInter h 4 + τ Extrapo , i = odd , j = even ; i = even , j = odd . (60)

We find that the truncation errors of (odd, odd), (odd, even) and (even, odd) fine grid points have the same form as ( τ RotateInter h 4 + τ Extrapo ), which is larger than the truncation error of (even, even) fine grid points ( τ Extrapo ) generated from Richardson extrapolation as we expect. It is because another interpolation is involved, i.e., Equation (55) or Equation (60).

In summary, these three Richardson extrapolation-based methods are able to compute the sixth order accurate solution on the entire fine grid. For (even, even) fine grid points, all methods use Richardson extrapolation to get the sixth order solution with truncation error τ Extrapo . For other three subsets of fine grid points, different computational strategies are used to obtain sixth order solutions, which add errors of different magnitude on the truncation error τ Extrapo . Table 1 lists the truncation errors of the three different Richardson extrapolation-based sixth order compact computations, respectively. Since the error expressions involve various high-order partial derivatives of u, it is hard to conclude a quantitative relationship. By comparing the coefficients of common items, we predict that the completed Richardson extrapolation method should be more accurate than the other two methods. We think the operator based interpolation method has comparable accuracy to the multiple coarse grid computation method. We cannot estimate which one is more accurate than the other because there exists uncertainty of high order partial differential terms in the explicit truncation errors and it is hard to determine the magnitude and sign of them.

Table 1. Truncation error comparison.

4. Numerical Results

We tested three Richardson extrapolation-based sixth order methods on two 2D Poisson equations. The 9-point FOC scheme (28) was used to get fourth order solutions on different scale grid levels.

One merit of using Richardson extrapolation for sixth order computation lies in that we can easily choose highly efficient solvers for the resulting large sparse linear systems. In our experiments, we chose a multiscale multigrid (MSMG) computational framework [22] , which uses multigrid methods to speed up the linear system solution, at the same time, involves a multiscale strategy to obtain higher order accurate solution by extrapolating the computed lower order solutions. The standard V(1, 1)-cycle is selected. The initial guess for the V-cycle on Ω 4 h was the zero vector. The V-cycle on Ω 2 h and Ω h stopped when the L2-norm of the difference of the successive solutions was reduced by a factor of 1010. The stopping criteria for the iterative operator based interpolation and Gauss-Seidel procedure was 10−10. All reported errors were the maximum absolute errors over the discrete grid of the finest level.

The codes were written in Fortran 77 programming language and run on a PC, which has Intel Core i7-4770 with 3.40 GHz and 16 GB RAM.

4.1. Test Problems

Problem 1.

2 u x 2 2 u y 2 = α sin ( π b y ) , ( x , y ) Ω = [ 0 , λ ] × [ 0 , b ] ,

where the boundary conditions are

u ( 0 , y ) = u ( λ , y ) = u ( x , 0 ) = u ( x , b ) = 0.

The parameters are chosen as

α = F π R b , λ = 10 7 m , b = 2 π × 10 6 m , F = 0.3 × 10 7 m 2 s 2 , R = 0.6 × 10 3 m s 1 .

The analytical solution is

u = α ( b π ) 2 sin ( π y b ) ( e π x b 1 ) .

Problem 2.

2 u x 2 2 u y 2 = 2 π 2 sin ( π x ) cos ( π y ) , ( x , y ) Ω = [ 0 , 4 ] × [ 0 , 1 ] ,

which has the Dirichlet boundary condition.

The analytical solution is

u ( x , y ) = sin ( π x ) cos ( π y ) .

4.2. Accuracy and Efficiency Comparison

We refined the grid from N = 32 to N = 256 for both test problems. For convenience, we used three abbreviations to represent three Richardson extrapolation-based sixth order methods to be compared. “Op-Six” is short for the sixth order method with Richardson extrapolation and operator based interpolation; “MCG-Six” means the sixth order method with Richardson extrapolation and multiple coarse grid computation; “CR-Six” denotes the sixth order method with completed Richardson extrapolation.

For both test problems, we compare the accuracy and efficiency of three methods by computing maximum errors and accuracy order, and recording the CPU time in seconds. The results of Problem 1 are shown in Table 2 and Table 3 and Figure 3. The results of Problem 2 are shown in Table 4 and Table 5 and Figure 4.

Figure 4. Comparison of the error and CPU for the Problem 2.

Table 2. Accuracy comparison results for Problem 1.

Table 3. Efficiency comparison results for Problem 1.

Table 4. Accuracy comparison results for Problem 2.

Table 5. Efficiency comparison results for Problem 2.

As for the accuracy, it is clear that all the methods are able to obtain approximate solutions with sixth order accuracy. After comparing the errors of the three methods, we found that, for both test problmes, the solutions solved by the CR-Six method were more accurate than those solved by the Op-Six method and the MCG-Six method. This observation is consistent with our analysis in Section 3. Meanwhile, we notice that the Op-Six computed a little bit more accurate solutions than the MCG-Six method for Problem 1 yet reversed for Problem 2, which shows that there is no fixed conclusion about the accuracy comparison between them.

As for the efficiency, we found that the MCG-Six method and the CR-Six method required less CPU cost than the Op-Six method. The reason is that the Op-Six method involves an iterative refinement procedure with low convergence rate. There is no evident difference between the MCG-Six method and the CR-Six method on CPU cost.

Although the CR-Six method performed better than the other two methods on accuracy and efficiency for the above two test problems, we need to point out that this advantage is for “simple” problems with “good” conditions. Here the “simple” and “good” mean those problems which are not hard to solve (e.g., small Reynolds number) and have smooth solutions, forcing functions and coefficients in the domain. Since the success of CR-Six method relies on the effectiveness of interpolation of the corrections, sufficiently smooth are necessary to guarantee an effective interpolation. We think the CR-Six method may ask for more restrictions on equations than the other two methods for the sixth order approximations on the finest grid. The robustness analysis and numerical experiments on various “difficult” problems is worth exploring in the future.

5. Concluding Remarks

Compared to the sixth order compact schemes derived by Hermitian polynomial, the Richardson extrapolation-based sixth order compact approximations have many obvious advantages, such as simple stencils, complete compact, easy implementation, suitable for high efficient linear system solvers, etc. We studied three Richardson extrapolation-based sixth order compact computation methods and analyzed the truncation errors of them respectively. All three methods were able to compute the sixth order accurate solution on the fine grid if Richardson extrapolation is applied to the fourth order solutions on fine and coarse grids successfully in the domain. From the truncation error analysis, we got a possible qualitative relationship on the accuracy among these sixth order methods, although it is not completely accurate. We also discussed the multigrid method which is suitable for the Richardson extrapolation-based sixth order methods.

Two 2D Poisson equations are tested in the numerical part. We compared the accuracy and efficiency among three sixth order methods. The test results on accuracy are generally consistent with the observation from the theoretical analysis. The completed Richardson extrapolation method usually performs better in accuracy than the operator based interpolation with Richardson extrapolation method and the multiple coarse grid computation with Richardson extrapolation method. As expected, the efficiency of the operator based interpolation with Richardson extrapolation is lower than the other two sixth order methods.

The exploration of using Richardson extrapolation on sixth order compact computation for high dimensional problems has already begun. In fact, the operator based interpolation with Richardson extrapolation method and the multiple coarse grid computation with Richardson extrapolation method have been used to solve 3D convection-diffusion equations and show exciting performance [24] . The error analysis to 3D cases could be conducted and reported in the future.

Since Richardson extrapolation-based sixth order methods require two comparable uniform grids (i.e., fine grid with meshsize h and coarse grid with meshsize 2h), the application of this technique to more practical problems in irregular domain with various boundary conditions (i.e., Dirichlet, Neumann, or mixed conditions) has limitations and is not straight forward. One undergoing study is to use the proposed methodology with finite difference ghost-cell technique to obtain high accuracy high efficiency solutions for Poisson equation with mixed boundary conditions. The finite difference ghost-cell technique [25] keeps unchanged the symmetry of the stencil and uniform meshsize through adding extra points (ghost points) outside the domain. Another thing we want to point out is Richardson extrapolation can also be used to improve the accuracy of solutions obtained from finite element methods [26] , although we used finite difference methods to illustrate the idea in this paper. And, compared to high order spectral methods which ask for simple/regular geometry of the problem domain or special strategies (i.e., spectral elements, domain decomposition, and etc.) for complex/irregular domains, using finite element methods to provide basic solutions and Richardson extrapolation to improve them would be a more flexible way to handle complex geometries appearing in many engineering problems.

Cite this paper: Dai, R. and Lin, P. (2018) Analysis on Sixth-Order Compact Approximations with Richardson Extrapolation for 2D Poisson Equation. Journal of Applied Mathematics and Physics, 6, 1139-1159. doi: 10.4236/jamp.2018.66097.
References

[1]   Wang, Z.J., et al. (2013) High-Order CFD Methods: Current Status and Perspective. International Journal for Numerical Methods in Fluids, 72, 811-845.
https://doi.org/10.1002/fld.3767

[2]   Canuto, C., Hussaini, M.Y., Quarteroni, A. and Zang, T.A. (1998) Spectral Methods in Fluid Dynamics. Springer, New York.

[3]   Canuto, C., Hussaini, M.Y., Quarteroni, A. and Zang, T.A. (2006) Spectral Methods: Fundamentals in Single Domains. Springer, New York.

[4]   Bueno-Orovio, A., Pérez-Garcia, V.M. and Fenton, F.H. (2006) Spectral Methods for Partial Differential Equations in Irregular Domains: The Spectral Smoothed Boundary Method. SIAM Journal on Scientific Computing, 28, 886-900.
https://doi.org/10.1137/040607575

[5]   Saad, Y. (1996) Iterative Methods for Sparse Linear Systems. PWS Publishing, New York.

[6]   Kalita, J.C., Datal, D.C. and Dass, A.K. (2002) A Class of Higher Order Compact Schemes for the Unsteady Two-Dimensional Convection Diffusion Equation with Variable Convection Coefficients. International Journal for Numerical Methods in Fluids, 38, 1111-1131.
https://doi.org/10.1002/fld.263

[7]   Spotz, W.F. and Carey, G.F. (1995) High-Order Compact Scheme for the Steady Stream-Function Vorticity Equations. International Journal for Numerical Methods in Engineering, 38, 3497-3512.
https://doi.org/10.1002/nme.1620382008

[8]   Zhang, J. (2002) Multigrid Method and Fourth Order Compact Difference Scheme for 2D Poisson Equation with Unequal Mesh-Size Discretization. Journal of Computational Physics, 179, 170-179.
https://doi.org/10.1006/jcph.2002.7049

[9]   Zhang, J., Geng, Z. and Dai, R. (2012) Analysis on Two Approaches for High Order Accuracy Finite Difference Computation. Applied Mathematics Letters, 25, 2081-2085.
https://doi.org/10.1016/j.aml.2012.05.003

[10]   Spotz, W.F. and Carey, G.F. (1996) A High-Order Compact Formulation for the 3D Poisson Equation. Numerical Methods for Partial Differential Equations, 12, 235-243.
https://doi.org/10.1002/(SICI)1098-2426(199603)12:2<235::AID-NUM6>3.0.CO;2-R

[11]   Lele, S.K. (1992) Compact Finite Difference Schemes with Spectral-Like Resolution. Journal of Computational Physics, 103, 16-42.
https://doi.org/10.1016/0021-9991(92)90324-R

[12]   Sutmann, G. and Steffen, B. (2006) High-Order Compact Solvers for the Three-Dimensional Poisson Equation. Journal of Computational and Applied Mathematics, 187, 142-170.
https://doi.org/10.1016/j.cam.2005.03.041

[13]   Chu, P.C. and Fan, C. (1998) A Three-Point Combined Compact Difference Scheme. Journal of Computational Physics, 140, 370-399.
https://doi.org/10.1006/jcph.1998.5899

[14]   Zhang, J. and Zhao, J. (2005) Truncation Error and Oscillation Property of the Combined Compact Difference Scheme. Applied Mathematics and Computation, 161, 241-251.
https://doi.org/10.1016/j.amc.2003.12.023

[15]   Nabavi, M., Kamran Siddiqui, M.H. and Dargahia, J. (2007) A New 9-Point Sixth-Order Accurate Compact Finite-Difference Method for the Helmholtz Equation. Journal of Sound and Vibration, 307, 972-982.
https://doi.org/10.1016/j.jsv.2007.06.070

[16]   Kyei, Y., Roop, J.P. and Tang, G. (2010) A Family of Sixth-Order Compact Finite-Difference Schemes for the Three-Dimensional Poisson Equation. Advances in Numerical Analysis, 2010, Article ID: 352174.

[17]   Richardson, L.F. (1910) The Approximate Arithmetical Solution by Finite Differences of Physical Problems Involving Differential Equations, with an Application to the Stresses in a Masonry Dam Trans. Proceedings of the Royal Society of London. Series A, 210, 307-357.

[18]   Cheney, W. and Kincard, E. (1999) Numerical Mathematics and Computing. 4th Edition, Cole Publishing, Pacific Grove.

[19]   Roache, P.J. and Knupp, P.M. (1993) Completed Richardson Extrapolation. Communications in Numerical Methods in Engineering, 9, 365-374.
https://doi.org/10.1002/cnm.1640090502

[20]   Burg, C. and Erwin, T. (2009) Application of Richardson Extrapolation to the Numerical Solution of Partial Differential Equations. Numerical Methods for Partial Differential Equations, 25, 810-832.
https://doi.org/10.1002/num.20375

[21]   Sun, H. and Zhang, J. (2004) A High Order Finite Difference Discretization Strategy Based on Extrapolation for Convection Diffusion Equations. Numerical Methods for Partial Differential Equations, 20, 18-32.
https://doi.org/10.1002/num.10075

[22]   Wang, Y. and Zhang, J. (2009) Sixth Order Compact Scheme Combined with Multigrid Method and Extrapolation Technique for 2D Poisson Equation. Journal of Computational Physics, 228, 137-146.
https://doi.org/10.1016/j.jcp.2008.09.002

[23]   Dai, R., Zhang, J. and Wang, Y. (2014) Multiple Coarse Grid Acceleration for Multiscale Multigrid Computation. Journal of Computational and Applied Mathematics, 269, 75-85.
https://doi.org/10.1016/j.cam.2014.03.021

[24]   Dai, R., Wang, Y. and Zhang, J. (2013) Fast and High Accuracy Multiscale Multigrid Method with Multiple Coarse Grid Updating Strategy for 3D Convection Diffusion Equation. Computers & Mathematics with Applications, 66, 542-559.
https://doi.org/10.1016/j.camwa.2013.06.008

[25]   Gibou, F. and Fedkiw, R. (2005) A Fourth Order Accurate Discretization for the Laplace and Heat Equations on Arbitrary Domains, with Applications to the Stefan Problem. Journal of Computational Physics, 202, 577-601.
https://doi.org/10.1016/j.jcp.2004.07.018

[26]   Lin, Q. and Xie, H. (2013) Extrapolation of the Finite Element Method on General Meshes. International Journal of Numerical Analysis and Modeling, 10, 139-153.

 
 
Top