A fast two-grid and finite section method for a class of integral equations on the real line with application to an acoustic scattering problem in the half-plane

We consider the numerical treatment of second kind integral equations on the real line of the form graphics (abbreviated phi = psi + K(z)phi) in which kappa is an element of L-1(R), z is an element of L-infinity(R), and,0 E BC(IR), the space of bounded continuous functions on R, are assumed known and phi is an element of BC(R) is to be determined. We first derive sharp error estimates for the finite section approximation (reducing the range of integration to [-A, A]) via bounds on (I - K-z)(-1) as an operator on spaces of weighted continuous functions. Numerical solution by a simple discrete collocation method on a uniform grid on R is then analysed: in the case when z is compactly supported this leads to a coefficient matrix which allows a rapid matrix-vector multiply via the FFT. To utilise this possibility we propose a modified two-grid iteration, a feature of which is that the coarse grid matrix is approximated by a banded matrix, and analyse convergence and computational cost. In cases where z is not compactly supported a combined finite section and two-grid algorithm can be applied and we extend the analysis to this case. As an application we consider acoustic scattering in the half-plane with a Robin or impedance boundary condition which we formulate as a boundary integral equation of the class studied. Our final result is that if z (related to the boundary impedance in the application) takes values in an appropriate compact subset Q of the complex plane, then the difference between phi(s) and its finite section approximation computed numerically using the iterative scheme proposed is less than or equal to C-1[kh log(1/kh)+(1-theta)(-1/2) (kA)(-1/2)] in the interval [-thetaA, thetaA] (theta < 1), for kh sufficiently small, where k is the wavenumber and h the grid spacing. Moreover this numerical approximation can be computed in less than or equal to C2N log N operations, where N = 2A/h is the number of degrees of freedom. The values of the constants C-1 and C-2 depend only on the set Q and not on the wavenumber k or the support of z.