Monotone Hamilton–Jacobi–Bellman schemes and policy iteration — Examples

Fix a node $i$. Let $U_j=0$ for every index and let $V_{i-1}=1$ with all other entries zero. Since $N\ge 3$, the two neighbors are distinct; hence $U\le V$, while $S_c(U{)}_i=0,\frac{V_{i+1}-V_{i-1}}{2h}=-\frac{1}{2h},S_c(V{)}_i=0+\tau \min \{-\frac{1}{2h},\frac{1}{2h}\}=-\frac{\tau }{2h}<0.$ Thus $S_c(U{)}_i>S_c(V{)}_i$ despite $U\le V$, which disproves monotonicity.

For the same arrays, if $0<\tau \mathrm{/}h\le 1$, the upwind update at $i$ has the unchanged zero row for action $a=1$ and a nonnegative row value $\tau \mathrm{/}h$ for action $a=-1$, so its action minimum is zero. This finite contrast is consistent with the nonnegative CFL weights in [F2].

Under (stay, exit), the policy equations are $V_1=0$ and $V_2=2$, so $V=(0,2)$. At state $1$, the stay row has value $0$, while the go row has $-V_1+V_2=2>0$; hence the strict-improvement set contains state $1$. At state $2$, both exit actions have value $2=V_2$ and reset has value $V_1-V_2=-2$, so state $2$ is not switched.

The new policy (go, exit) solves $2V_1-V_2=0$ and $V_2=2$, hence $V=(1,2)$. At state $1$, go has value $-1+2=1=V_1$ and stay has value $0$; at state $2$, both exit rows remain tied at $2$ and reset has value $1-2=-1$. No strict improvement remains, so the algorithm terminates. The duplicate exit tie is retained exactly as specified, and the strict switch increases state $1$ from $0$ to $1$ as [F2] requires.

Direct differentiation gives $u_t=-u$ and $u_{xx}=-4{\pi }^{2}u$. Therefore $u_t-u_{xx}=(-1+4{\pi }^2)u=f$, proving the exact PDE identity in [F1]. The diffusion-dominance condition is automatic since $b=0$; the CFL condition is $2\tau \mathrm{/}{h}^2\le 1$, which is exactly the stated time-step bound.

The discrete second difference is $D_{xx}^{h}u(x_i,t_n)=-\frac{4{\sin }^2(\pi h)}{h^2}u(x_i,t_n)\mathrm{.}$ Taylor expansion in time gives $(u(x_i,t_n+\tau )-u(x_i,t_n))\mathrm{/}\tau =u_t(x_i,t_n)+O(\tau )$, while $u_{xx}-D_{xx}^{h}u=(\frac{4{\sin }^2(\pi h)}{h^2}-4{\pi }^2)u=O(h^2),$ because $\sin z=z+O(z^3)$ at $z=0$. Thus the exact normalized residual is $O(\tau +h^2)$, agreeing with [F2]. No accumulated error is claimed.

Completing the square as in [F1], the unconstrained maximizing control is $a_{\ast }=-p\mathrm{/}2$. It lies in $[-1,1]$ exactly when $\mathrm{\mid }p\mathrm{\mid }\le 2$, where substitution gives $H(p)=p^2\mathrm{/}4$. If $p>2$, the concave quadratic is maximized at $a=-1$ and gives $p-1$; if $p<-2$, it is maximized at $a=1$ and gives $-p-1$. This proves the displayed formula.

For $\mathrm{\mid }p\mathrm{\mid }\le 2$, choose a nearest $a_m\in A_m$ to $a_{\ast }$. Then $H(p)-H_m(p)=(a_m-a_{\ast }{)}^2\le m^{-2}$ by [F1] and [F2]. For $\mathrm{\mid }p\mathrm{\mid }>2$, the maximizing endpoint belongs to $A_m$, so $H_m(p)=H(p)$. Also $H_m(p)\le H(p)$ since $A_m\subset A$. Taking the supremum proves the global error bound. Because $m^{-2}\to 0$, condition [F3] is satisfied for every bounded momentum set (in fact for all momenta), so the stated convergence theorem applies along any mesh family satisfying its remaining hypotheses.

Away from $x=0,1\mathrm{/}2$ and the moving fronts $d_{{\mathbb{T}}^1}(x,0)=t$, the function is either constant zero or has $u_t=-1$ and $\mathrm{\mid }{u}_x\mathrm{\mid }=1$; it satisfies the PDE classically. Near a moving front on the increasing-distance side, put $s=x-t$ in a local lift; on the other side put $s=1-x-t$. In either case $u=\max (s,0)$. There is no $C^1$ upper test at this convex kink: its directional slopes would have to be at least $1$ in the positive $s$ direction and at most $0$ in the negative direction. Any $C^1$ lower test has $s$-slope $p\in [0,1]$. Use a second coordinate tangent to the moving front: the profile is constant in that direction, so the test's tangential derivative is zero. Thus ${\varphi }_t=-p$ and ${\varphi }_x=p$ on the increasing-distance side, or ${\varphi }_x=-p$ on the decreasing-distance side; in both cases its residual is $-p+\mathrm{\mid }p\mathrm{\mid }=0$. At the antipode $x=1\mathrm{/}2$ for $t<1\mathrm{/}4$, the local profile is $1\mathrm{/}2-t-\mathrm{\mid }x-1\mathrm{/}2\mathrm{\mid }$. Its upper tests have spatial slope $p\in [-1,1]$ and time derivative $-1$, giving residual $-1+\mathrm{\mid }p\mathrm{\mid }\le 0$; no lower test exists at that concave cusp. Thus the sub- and supersolution tests hold everywhere for $0<t<1\mathrm{/}4$. The initial trace is $u_0$.

At $x=0$, the sampled data have $U_0=0$ and $U_{\pm 1}=h$ because $u_0(\pm h)=h$. For either semi-Lagrangian action the footpoint is $\pm \tau$; linear interpolation between $0$ and $\pm h$ returns $\tau$ when $\tau \le h$, so the action minimum is $\tau$. For the upwind update the forward difference is $1$ and the backward difference is $-1$; multiplying by $a=1$ and $a=-1$, respectively, gives drift contribution $1$ for both actions. The CFL condition is $\tau \mathrm{/}h\le 1$, so its minimum update is also $\tau$. Since $u(0,\tau )=0$, both one-step errors equal $\tau$. Taking $\tau =h\mathrm{/}2$ gives $h^2\mathrm{/}\tau =2h\to 0$, and [F3] supplies convergence for the refined semi-Lagrangian family under its full hypotheses.