Boundary treatment and multigrid preconditioning for semi-Lagrangian schemes applied to Hamilton-Jacobi-Bellman equations - Rotaetxe, J (2016)
We analyse two practical aspects that arise in the numerical solution of Hamilton-Jacobi-Bellman (HJB) equations by a particular class of monotone approximation schemes known as semi-Lagrangian schemes, namely boundary treatment and multigrid preconditioning. These schemes make use of a wide stencil to achieve convergence and result in discretization matrices that are less sparse and less local than those coming from standard finite difference schemes. This leads to computational difficulties not encountered there. We start by considering the overstepping of the domain boundary and analyse the accuracy and stability of stencil truncation. This truncation imposes a stricter CFL condition for explicit schemes in the vicinity of boundaries than in the interior, such that implicit schemes become attractive. Then, we show that for problems posed on a (semi) infinite domain whose boundary has no regular points we can avoid such truncation by means of a smooth transformation of the domain. Next, we consider the error analysis for semi-Lagrangian schemes with truncated stencils. The stencil truncation alters properties of the semi-Lagrangian scheme that were used for the derivation of error bounds. Hence, using an alternative approach, relying on a regularization procedure due to Krylov and a switching system approximation to the HJB equation, we derive error bounds for the truncated scheme. Finally, motivated by the stricter CFL condition of the scheme with truncated stencils, we consider implicit time stepping schemes. This involves solving non-linear systems of algebraic equations for semi-Lagrangian discretization matrices, hence, we study the use of geometric, algebraic and aggregation-based multigrid preconditioners to construct efficient solvers.