Optimal finite difference grids and rational approximations of the square root I. Elliptic problems

The main objective of this paper is optimization of second-order finite dif ference schemes for elliptic equations, in particular, for equations with s ingular solutions and exterior problems. A model problem corresponding to t he Laplace equation on a semi-infinite strip is considered. The boundary im pedance (Neumann-to-Dirichlet map) is computed as the square root of an ope rator using the standard three-point finite difference scheme with optimall y chosen variable steps. The finite difference approximation of the boundar y impedance for data of given smoothness is the problem of rational approxi mation of the square root on the operator's spectrum. We have implemented Z olotarev's optimal rational approximant obtained in terms of elliptic funct ions. We have also found that a geometrical progression of the grid steps w ith optimally chosen parameters is almost as good as the optimal approximan t. For bounded operators it increases from second to exponential the conver gence order of the finite difference impedance with the convergence rate pr oportional to the inverse of the logarithm of the condition number. For the case of unbounded operators in Sobolev spaces associated with elliptic equ ations, the error decays as the exponential of the square root of the mesh dimension. As an example, we numerically compute the Green function on the boundary for the Laplace equation. Some features of the optimal grid obtain ed for the Laplace equation remain valid for more general elliptic problems with variable coefficients. (C) 2000 John Wiley & Sons, Inc.