Applied Mathematics
Vol.05 No.17(2014), Article ID:50345,6 pages
10.4236/am.2014.517252
A New Scheme for Discrete HJB Equations
Zhanyong Zou
School of Mathematics and Statistics, Guangdong University of Finance & Economics, Guangzhou, China
Email: yong_china@126.com
Copyright © 2014 by author and Scientific Research Publishing Inc.
This work is licensed under the Creative Commons Attribution International License (CC BY).
http://creativecommons.org/licenses/by/4.0/
Received 2 August 2014; revised 28 August 2014; accepted 10 September 2014
ABSTRACT
In this paper we propose a relaxation scheme for solving discrete HJB equations based on scheme II [1] of Lions and Mercier. The convergence of the new scheme has been established. Numerical example shows that the scheme is efficient.
Keywords:
Iterative Algorithm, Relaxation Scheme, HJB Equation, Convergence, Existence
1. Introduction
Consider the following Hamilton-Jacobi-Bellman (HJB) equation:
(1.1)
where is a bounded domain in
are elliptic operators of second order. Equation (1.1) is arising in stochastic control problems. See [2] and the references therein.
Equation (1.1) can be discretized by finite difference method or finite element method. See [1] [3] and the references therein. Then we obtain the following discrete HJB equation:
(1.2)
where. Equation (1.2) is a system of nonsmooth nonlinear equations. Many numerical algorithms for solving (1.2) have been proposed. See [4] -[12] and the references therein.
[1] has given two iterative algorithms for solving (1.2). At each iteration, a linear complementarity subproblem or a linear equation system subproblem is solved. See also [4] .
Scheme I.
Step 1: Given for some
we find
such that
Step 2: Let For
we find
such that
Step 3: If then the output is
otherwise
and it goes to Step 2.
Assume Let
(1.3)
That is: the lth row of matrix is the lth row of matrix
; the lth component of vector
is the lth component of vector
. Now we formulate Scheme II of Lions and Mercier in the notation above.
Scheme II.
Step 1: for some
we find
such that
(1.4)
Step 2: For we find
such that
(1.5)
Step 3: Compute as the solution of
(1.6)
Step 4: If then the output is
, otherwise
and it goes to Step 2.
In the last decade many numerical schemes have been given for solving (1.2). But the above schemes are still playing a very important role. See [4] -[6] and the references therein.
In this paper we propose, based on Scheme II above, a relaxation scheme with a parameter, which for
is just Scheme II. In our numerical example, the new scheme with
is faster than Scheme II
. The monotone convergence of the new scheme has been proved.
2. New Scheme and Convergence
We propose a new scheme which is an extension of Scheme II.
New Scheme II.
Step 1: Given
for some
find
such that
(2.1)
Step 2: For find
such that
(2.2)
Step 3: Compute as the solution of
(2.3)
Step 4: Compute
(2.4)
Step 5: If then output
otherwise
and go to Step 2.
In [13] we proposed the following conditions for (1.2).
Condition All the matrices
are M-matrices.
In [13] we have proved the following theorem.
Theorem 2.1 If Condition holds then (1.2) has a unique solution.
We have the following convergence theorem.
Theorem 2.2 Assume that Condition holds, and that
are produced by New Scheme II. Then
is monotonely decreasing and convergent to the solution of (1.2).
Proof Since all are M-matrices,
in New Scheme II are well defined.
First, we prove is decreasing monotonically, i.e.,
(2.5)
By (2.3) we have
(2.6)
which combining with (2.1) and (2.2) yields
(2.7)
Since are M-matrices, (2.7) means
(2.8)
By (2.4) we obtain
(2.9)
By, (2.8) and (2.9) we know
(2.10)
and
(2.11)
which and (2.10) implies
Similarly, by (2.3) we derive
which combining with (2.2) and (2.6) implies
Hence we have
(2.12)
By (2.4), we have
(2.13)
By (2.12), (2.13) and, we know
(2.14)
which combining with and (2.11) we derive
(2.15)
By (2.11), (2.12) and (2.13) ,we get
which combining with (2.15) implies
It is easy to derive by induction that
(2.16)
and
(2.17)
It follows that (2.5) holds.
It follows from (2.2) and (2.3) that
(2.18)
Since the set is a finite set there exist positive integers
and
with
such that
Therefore, we have
Then by (2.2) we obtain
which and (2.17) results in
(2.19)
From (2.4), (2.16) and (2.19) we have
(2.20)
It follows from (2.18), (2.19) and (2.20) that
which means is a solution of (1.2). The existence of solution has been proved.
Finally, we prove the uniqueness of solution. Assume and
are solutions of (1.2), i.e.,
(2.21)
(2.22)
It is easy to see from (2.21) and (2.22) that there exist and
such that
(2.23)
(2.24)
(2.25)
(2.26)
(2.23) and (2.26) implie. But (2.24) and (2.25) implies
. Hence
. The proof is complete. ,
3. Numerical Example
We use example 2 in [4] , i.e.,
(3.1)
where
The discretization of the above second order derivatives are:
where denote the forward and backward difference respectively in
and
,
,
. We use New Scheme II to solve the discrete problem. Take
,
and 1.1, 1.3, 1.5, 1.8, 1.9 respectively.
Table 1 and Table 2 show the ∞-norm of the residual when iteration terminates.
We see that for
and
is big for
.
Table 3 shows the relation between iteration number and relaxation number
. Table 4 and Table 5 show the value of
at
for
and
respectively.
We can see from Table 3 that the algorithm for is faster than that for
. Table 4 and Table 5 display the monotonicity of the algorithm.
Table 1. ∞-norm of the residual R.
Table 2. ∞-norm of the residual R.
Table 3. Iteration number m.
Table 4. The value of at
.
Table 5. The value of at
.
Funding
This work was supported by Educational Commission of Guangdong Province, China (No. 2012LYM-0066) and the National Social Science Foundation of China (No. 14CJL016).
References
- Lions, P.L. and Mercier, B. (1980) Approximation numerique des equations de Hamilton-Jacobi-Bellman. RAIRO Numerical Analysis, 14, 369-393.
- Bensoussan, A. and Lions, J.L. (1982) Applications of Variational Inequalities in Stochastic Control. North-Holland, Amsterdam.
- Boulbrachene, M. and Haiour, M. (2001) The Finite Element Approximation of Hamilton-Jacobi-Bellman Equations. Computers & Mathematics with Applications, 14, 993-1007. http://dx.doi.org/10.1016/S0898-1221(00)00334-5
- Hoppe, R.H.W. (1986) Multigrid Methods for Hamilton-Jacobi-Belman Equations. Numerische Mathematik, 49, 239- 254. http://dx.doi.org/10.1007/BF01389627
- Huang, C.S., Wang, S. and Teo, K.S. (2004) On Application of an Alternating Direction Method to HJB Equations. Journal of Computational and Applied Mathematics, 166, 153-166. http://dx.doi.org/10.1016/j.cam.2003.09.031
- Sun, M. (1993) Domain Decomposition Method for Solving HJB Equations. Numerical Functional Analysis and Optimization, 14, 145-166. http://dx.doi.org/10.1080/01630569308816513
- Sun, M. (1996) Alternating Direction Algorithms for Solving HJB Equations. Applied Mathematics and Optimization, 34, 267-277. http://dx.doi.org/10.1007/BF01182626
- Young, D. (1971) Iterative Solution of Large Linear Systems. AP, New York.
- Zhou, S.Z. and Chen, G.H. (2005) A Monotone Iterative Algorithm for a Discrete HJB Equation. Mathematica Applicata, 18, 639-643. (in Chinese)
- Zhou, S.Z. and Zhan, W.P. (2003) A New Domain Decomposition Method for an HJB Equation. Journal of Computational and Applied Mathematics, 159, 195-204. http://dx.doi.org/10.1016/S0377-0427(03)00554-5
- Zhou, S.Z. and Zou, Z.Y. (2008) An Itetative Algorithm for a Quasivariational Inequality System Related to HJB Equation. Journal of Computational and Applied Mathematics, 219, 1-8. http://dx.doi.org/10.1016/j.cam.2007.07.013
- Zhou, S.Z. and Zou, Z.Y. (2008) A New Iterative Method for Discrete HJB Equations. Numerische Mathematik, 111, 159-167. http://dx.doi.org/10.1007/s00211-008-0166-6
- Zhou, S.Z. and Zou, Z.Y. (2007) A Relaxation Scheme for Hamilton-Jacobi-Bellman Equations. Applied Mathematics and Computation, 186, 806-813. http://dx.doi.org/10.1016/j.amc.2006.08.025