# Stable method for solving a HJB equation

I am considering finite difference methods and their error analysis for solving HJB equation of the following form: $$v_t=|\sigma(x)v_x|,\quad x\in \mathbb{R},$$ where $\sigma$ is a given function on $\mathbb{R}$ (with possible regularity assumptions).

Could you give me a simple (perhaps first-order) FD scheme and its error analysis (stability and convergence in spatial discretization) for solving the above equation? I will also appreciate if you could give me some references(textbook/paper) on this subject. I just want to study the common techniques to study such numerical methods.

I know there are a lot of literature for solving HJB equations in quite general form. But I hope to start with this concrete example.

One may prefer to write your equation in the form $$v_t = \sigma(x) |v_x|$$ where $\sigma(x) \ge 0$ for $x \in R$. You need to define an initial condition e.g. $$v(x,0) = v^0(x) .$$ Let me skip a treatment of boundary conditions (you hardly can solve the equation numerically on an unbounded domain). Note that the exact solution $v(x,t)$ for a fixed $x$ is non-decreasing function in time.

The simplest (first order accurate) numerical scheme is based on Rouy-Tourin method. You aim to find the values $v_i^n$ that approximate the unknown exact values $v(x_i,t^n)$ for discrete points $x_i \in R$ and $t^n > 0$. Let me suppose uniform steps $h=x_{i+1}-x_i$ and $\tau=t^{n+1}-t^n$.

Firstly, $v_i^0 = v^0(x_i)$. Furthermore, the scheme can be formally written as follows $$v_i^{n+1} = v_i^n + \tau \sigma(x_i) |\partial_x v_i^n|$$ where a proper finite difference $\partial_x v_i^n$ (backward or forward one sided) shall be used to approximate $\partial_x v(x_i,t^n)$.

To make the story short such appropriate approximation is based on the fact that the solution $v$ for a fixed $x$ is non-decreasing, therefore one has to choose one sided finite difference depending which of three values, $v_{i-1}^n$, $v_i^n$, $v_{i+1}^n$ is maximal. Namely $$\partial_x v_i^n = (v_{i+1}^n - v_i^n)/h \,\,\hbox{ if } \,\, v_{i+1} \ge \max\{v_i^n,v_{i-1}^n \}$$ or $$\partial_x v_i^n = (v_{i}^n - v_{i-1}^n)/h \,\,\hbox{ if } \,\, v_{i-1} \ge \max\{v_i^n,v_{i+1}^n \}$$ or $$\partial_x v_i^n = 0 \,\,\hbox{ if } \,\, v_{i} \ge \max\{v_{i-1}^n,v_{i+1}^n \}$$ There are other first order accurate methods, e.g. Osher-Sethian scheme, but this one is considered less diffusive''. The stability of scheme can be proved if all local Courant numbers $$C_i = \tau \sigma(x_i) / h$$ are less or equal to one. In fact in such case the discrete minimum and maximum principle is fulfilled for numerical solution (e.g. no unphysical oscillations).

As a reference I would recommend the book of Sethian or/and the book of Osher-Fedkiw, it is easy to find the exact references (P.S. see level set methods).

P.S. I was asked about stability in comments. In fact, as I mentioned above, one can prove even more. The scheme can be written equivalently as $$v_i^{n+1} = (1 - C_i) v_i^n + C_i \max \{ v_{i-1}^n, v_i^n, v_{i+1}^n\}$$ so for $C_i \le 1$ the value $v_i^{n+1}$ is the convex combination of two values, consequently $$v_i^{n+1} \le \max \{v_{i-1}^n,v_i^n, v_{i+1}^n\} \,.$$

• Thanks for your replying. May I know whether the two references you suggested are those books about level-set methods? Do you mean the authors discussed FDM for HJB equations in the corresponding chapters in their books? – John Jan 15 '17 at 18:46
• Yes, you are right. – Peter Frolkovič Jan 15 '17 at 18:54
• Thanks. May you elaborate more or give a reference about how to prove the stability of the scheme you mentioned in the answer? I fail to find the analysis in the book. – John Jan 15 '17 at 19:06