Cascade Iterative Algorithms in Finite Element Method for Non-linear Elliptic Equations

V.V. Shaidurov
Institute of Computational Modelling of RAS, Russia

Abstract

Dirichlet problem is considered for a weakly nonlinear elliptic equation of second order. Implementation of standard finite-element method with piecewise linear elements on triangles results in the system of nonlinear algebraic equations. To solve it, a cascade organization of conjugate-gradient method is used on a sequence of nested grids and gives a simple version of multigrid without preconditioning and projection onto the coarser grid. Cascade algorithm begins at comparatively coarse grid, where the number of unknowns in discrete nonlinear system is less of several orders than this number at finest grid. Therefore we suppose that this system is previously solved with sufficiently high accuracy and appropriate computational complexity. At each finer grid, the nonlinear system is linearized by Newton method with "frozen derivative" and is approximately solved by conjugate-gradient method; initial guess is obtained by interpolation of approximate solution from the previous coarser grid. It is proved that this cascade algorithm has the same optimal exponent in computational complexity as the traditional multigrid, when they reduce iteration error to the level of discretization one in energy norm. Some numerical experiments confirm this theoretical result.