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 difference schemes for elliptic equations, in particular, for equations with singular solutions and exterior problems. A model problem corresponding to the Laplace equation on a semi-infinite strip is considered. The boundary impedance (Neumann-to-Dirichlet map) is computed as the square root of an operator using the standard three-point finite difference scheme with optimally chosen variable steps. The finite difference approximation of the boundary impedance for data of given smoothness is the problem of rational approximation of the square root on the operator's spectrum. We have implemented Zolotarev's optimal rational approx-imant obtained in terms of elliptic functions. We have also found that a geometrical progression of the grid steps with optimally chosen parameters is almost as good as the optimal approximant. For bounded operators it increases from second to exponential the convergence order of the finite difference impedance with the convergence rate proportional to the inverse of the logarithm of the condition number. For the case of unbounded operators in Sobolev spaces associated with elliptic equations, 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 obtained for the Laplace equation remain valid for more general elliptic problems with variable coefficients. © 2000 John Wiley & Sons, Inc.