One version of the multigrid method (Q1083837)

Many authors have investigated finite difference or finite element methods of solving boundary value problems with the help of the multigrid method. In many cases this approach guarantees the high performance of algorithms, for which the computational work for finding the grid solutions as the step h tends to zero is proportional to the number of grid nodes. Moreover, the precision is increased if we use linear combinations of solutions on different grids. In a previous paper the author considered a method for finding a finite difference solution of the Poisson equation. The method was based on using an auxiliary grid and on solving reduced equations on the main grid. In this work the modification of this algorithm is presented for more general boundary value problems. It is proved, under natural assumptions on the asymptotic expansion of the approximation error for finite difference equations, that the computational work required for the considered multigrid method is proportional to the number of nodes. It is also proved that, without additional assumptions on the smoothness of the solution of the original problem, the precision can be improved by taking combinations of solutions on different grids.