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.


1 Answer 1


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\} \,. $$

  • $\begingroup$ 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? $\endgroup$
    – John
    Commented Jan 15, 2017 at 18:46
  • $\begingroup$ Yes, you are right. $\endgroup$ Commented Jan 15, 2017 at 18:54
  • $\begingroup$ 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. $\endgroup$
    – John
    Commented Jan 15, 2017 at 19:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.