求解一類(lèi)HJB方程的非線(xiàn)性SOR迭代法

摘要:采用非線(xiàn)性SOR迭代法求解一類(lèi)特殊的Hamilton-Jacobi-Bellman(HJB)方程， 該迭代法可以看成為求解線(xiàn)性方程組的SOR迭代法在求解HJB方程上的推廣. 在一定條件下此方法具有單調(diào)收斂性.

關(guān)鍵詞:非線(xiàn)性SOR;HJB方程;M-函數(shù);單調(diào)收斂

中圖分類(lèi)號(hào):O241.6文獻(xiàn)標(biāo)識(shí)碼:A

A Nonlinear SOR Iterative Method for a Kind of HJB Equation

SUN Zhe，WU Lei

(College of Mathematics and Econometrics， Hunan Univ， Changsha， Hunan 410082， China)

Abstract: A nonlinear SOR iteration method is used to solve a kind of HJB equation. The method is an extension of SOR iteration method from linear problem to HJB equation. Under proper conditions， it has some good monotone convergence.

Key words: nonlinear SOR; HJB equation; M-function; monotone convergence

1 預(yù)備知識(shí)

Hamilton-Jacobi-Bellman(HJB)方程最早出現(xiàn)于用動(dòng)態(tài)規(guī)劃解最優(yōu)控制問(wèn)題， 之后在力學(xué)、電磁學(xué)、水文學(xué)、化學(xué)、工程、經(jīng)濟(jì)管理以及參數(shù)識(shí)別、最優(yōu)控制等領(lǐng)域有廣泛的應(yīng)用. 因此它的數(shù)值解的研究是一個(gè)非常熱門(mén)的話(huà)題， 近年來(lái)， 取得了許多進(jìn)展， 參見(jiàn)文獻(xiàn)[1-4，6-9].本文將繼續(xù)研究一類(lèi)HJB方程的新的迭代算法.

首先引入M-函數(shù)的定義， 其定義來(lái)自文獻(xiàn)[5].

定義1 設(shè) 是由 到 上的連續(xù)映射. 我們稱(chēng) 為M-函數(shù)， 如果 滿(mǎn)足下面兩個(gè)條件:

(a) 逆保序性: 對(duì)任意 ， 如果 ，則 ;

(b) 非對(duì)角反單調(diào)性: 對(duì)每一指標(biāo)對(duì) 和任意 ， 一維函數(shù) ，

(1)

是非增函數(shù).

如果 是M-矩陣，則函數(shù) 是M-函數(shù).本文考慮以下HJB方程.

求 ，使得

(2)

其中 ， ，是M-函數(shù).

對(duì)于方程(2)，我們假設(shè)下面兩個(gè)條件成立:

條件A: 方程(2)存在一個(gè)解 ;

條件B: 函數(shù)

(即 的第 個(gè)分量取為 的第 個(gè)分量)是M-函數(shù)， ， .

注1: (1)當(dāng)函數(shù) 是仿射映射時(shí)，即 ， ，條件B退化為[8]中的條件 ，而且條件B成立就有條件A成立.

(2) 對(duì)于M-函數(shù)的情形，條件B成立并不意味著條件A也成立.如:

，

其中 .容易驗(yàn)證 是M-函數(shù)，但是方程 在 中無(wú)解.

命題 1 設(shè)條件A和條件B成立，則方程(2)存在唯一解.

證明: 設(shè) 是(2)的解，則

既然方程(2)存在解，則存在一列指標(biāo)使得

利用 的逆保序性，可得 .

類(lèi)似地，我們可以證明 .從而 .命題得證.證畢

命題 2 設(shè)F是M-函數(shù).則對(duì)于任意的 和

， 由(1)定義的一元函數(shù) 是逆保序的，也就是說(shuō): 如果

， 那么 .

證明: 不妨假設(shè) ，對(duì)于任意指標(biāo) ，利用 的非對(duì)角反單調(diào)性可得

.注意到.則

.從而由 的逆保序性可得

所以 .這與假設(shè)矛盾!命題得證.證畢

2 算法

接下來(lái)我們將引進(jìn)上解的概念，若 滿(mǎn)足 ，則稱(chēng) 為方程(2)的一個(gè)上解. 方程(2)的所有上解的集合記為 ， 稱(chēng)為上解集.

命題 3 設(shè)條件A和條件B成立，則 且對(duì)任意 ，成立

證明: 因?yàn)?，所以 .設(shè) 則成立 故存在一列子標(biāo)

使得 由函數(shù) 的逆保序性知 .證畢

接下來(lái)給出本文中的算法.

算法1:

第1)步: 給定取

， ;

第2)步: 計(jì)算 使得

(3)

第3)步: 計(jì)算 ，令

第4)步: 如果 則轉(zhuǎn)第5)步否則令 返回到第2)步;

第5)步: 如果 ， 則停止計(jì)算， 否則，令 ， ， 返回到第2)步.

注2: (1) 該算法中，每次迭代只須求解 個(gè)一維的HJB方程，因而計(jì)算十分簡(jiǎn)便.

(2) 當(dāng) 且 為仿射映射時(shí)，算法1就退化為求解線(xiàn)性方程組的SOR迭代算法， 所以該算法可以看成是SOR迭代法的推廣.

命題 4 如果條件A和條件B成立， 那么對(duì)任意 ，存在 使得

.

證明 既然 ，由命題2可得 .從而對(duì)任意 成立

由 及 的非對(duì)角反單調(diào)性可得

(4)

另一方面， 意味著

. (5)

結(jié)合(4)和(5)得

既然關(guān)于變量 的一元函數(shù) 是連續(xù)函數(shù)，由上式知存在 ，使得

.

證畢.

3 算法的收斂性

命題 5 設(shè)條件A和條件B成立，則由算法1生成的迭代序列 滿(mǎn)足:

證明 既然 ，則 從而 (6)

由命題4，存在 使得

(7)

結(jié)合(6)得

從而存在某個(gè) 使得

利用命題2可得 .所以根據(jù)算法1，我們有

(8)

這就意味著

從而對(duì)于任意 及 利用 的非對(duì)角反單調(diào)性可得

這就是說(shuō)對(duì)任意 成立

(9)

注意到(8)，則由命題2可得對(duì)成立

從而，利用(7)，我們得到

(10)

結(jié)合(9)和(10)得

所以，且類(lèi)似地，我們可以證明對(duì)任意 有

和

從而可得 且

利用數(shù)學(xué)歸納法可得

且

再由命題3，則成立

證畢.

下面給出算法1的收斂性定理.

定理1 設(shè)條件A和條件B成立，則算法1產(chǎn)生的迭代序列 是單調(diào)下降的上解序列. 而且當(dāng) 時(shí)，此序列收斂于 .

證明 由命題5知，是單調(diào)有界序列， 所以存在 使得 .再由算法1， 對(duì)任意 及 成立

(11)

和

.

在上式中令 ，則由(11)可得

.

也就是說(shuō)對(duì)任意 成立

從而 .所以 是(2)的解.利用命題1，我們有 .證畢.

4 簡(jiǎn)單應(yīng)用

考慮下列互補(bǔ)問(wèn)題: 求 使得

且 (12)

其中矩陣 是M-矩陣. 令

互補(bǔ)問(wèn)題(12)等價(jià)于下列HJB方程: 求 使得

(13)

不難證明方程(13)滿(mǎn)足條件A和條件B， 所以我們可以尋求算法1來(lái)求解方程， 從而得到下列算法.

算法2:

第1)步:給定取;

第2)步:計(jì)算 使得

第3)步: 計(jì)算 ， 令

第4)步:如果 則轉(zhuǎn)第5)步否則令 返回到第2)步;

第5)步:如果 ， 則停止計(jì)算， 否則，令 ， ，返回到第2)步.

注3:(1) 既然 為M-矩陣， 則

.所以算法2中第2)步就等價(jià)于求解

從而算法2就退化為我們熟知的PSOR迭代算法.

(2) 向量 是問(wèn)題(13)的一個(gè)上解.

由定理1，我們得到算法2的下列收斂性結(jié)論.

定理2 算法2所生成的迭代序列 是單調(diào)下降的上解序列且該序列收斂于 .

參考文獻(xiàn)

[1]BENSOUSSAN A， LIONS J L. Applications of variation-

al inequalities in stochastic control[M].North-Holland， Amsterdam，1982.

[2]HOPPE R H W. Multigrid methods for Hamilton-Jacobi- Bellman equations[J]. Numerische Mathematik， 1986，49: 239-254.

[3]HUANG C S， WANG S， TEO K S. On application of an alternating direction method to HJB equations[J]. Journal of Computational and Applied Mathematics， 2004，166: 153-166.

[4]LIONS P L， MERCIER B. Approximation numerique des equations de Hamilton-Jacobi-Bellman[J].RAIRO Numeri- cal analysis， 1980，14: 369-393.

[5]MORE J J， RHEINBOLDT W C. On P- and S- functions and related class of n-dimensional nonlinear mappings[J]. Linear Algebra and its Applications， 1973， 6: 45-68.

[6]SUN M. Domain decomposition method for solving HJB equations[J]. Numerical Functional Analysis and Optimiz- ation，1993，14:145-166.

[7]ZHOU S Z， ZOU Z Y. A new iterative method for discrete HJB equations[J].Numerische Mathematik，2008，111:159- 167.

[8]ZHOU S Z， ZOU Z Y. A relaxation scheme for Hamilton- Jacobi-Bellman equations[J]. Applied Mathematics andComputation，2007，186:806-813.

[9]周叔子，陳光華.解離散HJB方程的一個(gè)單調(diào)迭代法[J]. 應(yīng)用數(shù)學(xué)，2005，18(4):639-643.

ZHOU Shu-zi， CHEN Guang-hua. A Monotone Iterative Algorithm for a Discrete Hamilton-Jacobi-Bellman Equa-

tion[J]. Mathematica Applicata，2005，18(4):639-643.