求解HJB方程的兩類迭代法研究

楊建鵝，黃曉梅

(江西師范大學數學與信息科學學院，江西 南昌330022)

0 引言

HJB方程最早出現于用動態規劃解最優控制問題，之后在科學、工程、經濟領域中得到廣泛應用［1～5］。本文考慮如下HJB方程:

其中，Ω是R2上的有界區域，?Ω為Ω充分光滑的邊界，Fj為光滑函數，Lj為如下二階橢圓算子:

對方程(1)采用有限差分法或有限元方法進行離散，可以得到如下離散格式的 HJB方程［6～8］:

其中，Aj∈Rn×n，Fj∈Rn，j=1，2，…，k。方程(2)是非光滑的方程組。

條件A:Aj=()，j=1，2，…，k，是L矩陣(即≤0，p≠q，p，q=1，2，…，n)且Aj，j =1，2，…，k，是嚴格對角占優的。

目前人們提出了很多迭代算法解離散HJB方程［8～14］。本文基于上下解策略，提出兩類新的迭代法求解方程(2)，該算法的特點是簡單易行。下面給出上解集和下解集的定義。

1 算法

下面給出求解離散HJB方程的兩類算法。

1.1 算法1(Jacobi型迭代算法)

第1步:取ε＞0，初始值U0∈S1，m∶=0;

第2步:計算

第3步:如果‖Um+1－Um‖＜ε，則停止計算;否則令m∶=m+1，轉第2步。

1.2 算法2(Gauss-Seidel型迭代算法)

第1步:取ε＞0，初始值U0∈S1，m∶=0;

第2步:計算

第3步:‖Um+1－Um‖＜ε，則停止計算;否則令m∶=m+1，轉第2步。

注:當k=1時，算法1、算法2分別為求解線性方程組的Jacobi迭代法和Gauss-Seidel迭代法。若U0∈S0，算法1和算法2也是收斂的。

2 算法的收斂性

這一節，給出算法1和算法2的收斂性定理。在證明算法1和算法2的收斂性定理之前，先給出幾個重要的引理。

引理1［9］:設系數矩陣Aj，j=1，…，k，滿足條件A或條件B，那么對任意的sl(l=1，…，n)，矩陣A(s1，…，sn)為M矩陣。

引理2:設系數矩陣Aj，j=1，…，k，滿足條件A或條件B，且{Um}是算法1產生的迭代序列，那么{Um}是一個單調下降的上解序列，即{Um}?S1且Um+1≤Um，m=0，1，2，…。

證明:既然U0∈S1，由歸納法原理，只需要證明對任意m，若Um∈S1，則Um+1∈S1，且Um+1≤Um。

由算法1及上述不等式知

從而Um+1≤Um。

由算法1的第2步知:

那么存在某個ji(1≤ji≤k)，使得

也就是說，

而Um+1≤Um，故

定理1:設系數矩陣Aj，j=1…，k，滿足條件A或條件B，且{Um}是算法1產生的迭代序列，那么{Um}單調收斂于方程(2)的解。

證明:由引理2知:Um+1≤Um，m=0，1，2，…。下面證明{Um}有下界。

對任意的m=0，1，…，都存在一組(s1，…，sn)，使得－Fj}≥0。

既然A(s1，…，sn)為M矩陣，那么方程A(s1，…，sn)W－F(s1，…，sn)=0存在唯一解。記為W (s1，…，sn)。由于

所以，Um≥W(s1，…，sn)。令

又由于

在上式中令m→∞，則

從而

因此U*是方程(2)的解。

引理3:設系數矩陣Aj，j=1，…k，滿足條件A或條件B，且{Um}是算法2產生的迭代序列，那么{Um}是一個單調下降的上解序列，即{Um}?S1且Um+1≤Um，m=0，1，2，…。

證明:由算法2可知，U0∈S1，利用歸納法原理，只需要證明對任意m，若Um∈S1，則Um+1∈S1，且Um+1≤Um。假設Um∈S1，下面證明Um+1≤Um。由算法2知，

根據歸納法原理知，Um+1≤Um。

下面證明Um+1∈S1。對任意的i=1，2，…，n，

定理2:設系數矩陣Aj，j=1，…，k，滿足條件A或條件B，且{Um}算法2產生的迭代序列，那么{Um}單調收斂于方程(2)的解。

證明:證明過程類似定理1的過程，此處省略。

注:在算法1和算法2中若取初始值為下解，則算法產生的迭代序列單調上升收斂于方程(2)的解。

3 數值實驗

考慮下列問題:

其中，

在數值實驗中，取迭代終止準則ε=10－6，初始值為U0=(A1)－1F1。表1和表2分別給出網格點(0.5，0.2)處的迭代值，迭代次數及前后2次迭代的誤差，其中網格點(0.5，0.2)處的精確值為0.587 78，誤差取為‖Um+1－Um‖∞。

(1)算法1終止時的迭代次數為51次，花費時間為0.781 00 s。

表1 Jacobi型迭代法解HJB方程所得的結果

(2)算法2終止時的迭代次數為27，花費時間為0.343 00 s。

表2 Gauss-Seidel型迭代法解HJB方程所得的結果

通過比較表1與表2，發現取同一個初值時，Gauss-Seidel型迭代算法比Jacobi型迭代算法迭代次數少將近一半，所花時間也減少了一半左右，所得到的解也更接近精確解。因而Gauss-Seidel型迭代算法比Jacobi型迭代算法收斂速度更快。

［1］ Bellman R.Dynamic Programming［M］.New Jersey: Princeton Univ Press，1957.

［2］ Stanislaw S.Hamilton-Jacobi-Bellman equations and dynamic programming for power-maximizing relaxation of radiation［J］.International Journal of Heat and Mass Transfer，2007，50:2714－2732.

［3］ Bellman R.Adaptive Control Processes:A Guided Tour［M］.New Jersey:Princeton University Press，1961:1－42.

［4］ Bensoussan A，Lions J L.Impulse Control and Quasi-Variational Inequalities［M］.Paris:Gauthier Villars，1984:1－31.

［5］ Fleming W H，Rishel R.Deterministic and Stochastic Optimal Control［M］.Berlin:Springer，1975:1－27.

［6］ Boulbrachene M，Haiour M.The finite element approximation of Hamilton-Jacobi-Bellman equations［J］.Comput.Math.Appl.，2001，14:993－1007.

［7］ Lions P L，Mercier B.Approximation numerique des equations de Hamilton-Jacobi-Bellman［J］.RAIRO Numerique Analyse，1980，14:369－393.

［8］ Sun M.Domain decomposition method for solving HJB equations［J］.Numer.Funct.Anal.Optim.，1993，14: 145－166.

［9］ Zhou S Z，Zhan W P.A new domain decomposition method for an HJB equatoin［J］.J.Comput.Appl.Math.，2003，159:195－204.

［10］ Hoppe R H W.Multigrid methods for Hamilton-Jacobi-Belman equations［J］.Numer.Math.，1986，49:239－254.

［11］ Huang C S，Wang S，Teo K S.On application of an alternating direction method to HJB equations［J］.J.Comput.Appl.Math.，2004，166:153－166.

［12］ Sun M.Alternating direction algorithms for solving HJB equations［J］.Appl.Math.Optim.，1996，34:267－277.

［13］ Zhou S Z，Chen G H.A monotone iterative algorithm for a discrete HJB equation(in Chinese)［J］.Math.Appl.2005，18:639－643.

［14］Xu H R，Sun Z，Xie S L.An iterative algorithm for solving a kind of discrete HJB equation with M-functions［J］.Appl.Math.Lett.，2011，24(3):279－282.