主页 > 案例大全 > 论文写作模式-非对称代数Riccati方程的求解算法

论文写作模式-非对称代数Riccati方程的求解算法

2021-06-07 15:59:03

  非对称代数Riccati方程最早应用于工程应用领域和科学计算领域中。例如在输运理论中,可将确定粒子输运散射函数的问题转化为求非对称代数Riccati方程解的问题,另一重要例子来自于对马尔可夫链的Wiener-Hopf分解,可以把该问题转化为求解非对称Riccati方程和它的对偶方程最小非负解的问题。如何准确快速并且有效地求解非对称Riccati方程的最小非负解也成为数学科学研究领域的热点问题之一。尤其是当矩阵规模变的越来越大时,数值迭代法相比于直接法更加快速高效。因此,研究非对称代数Riccati方程高效率的数值解法不仅具有重要的科学意义,而且具有广泛的应用前景,对增进科学方法在国民生产和经济增长等方面起到重大作用,也值得我们去深入研究。

  考虑如下的非对称代数Riccati方程(NARE):

  其中。

  定义矩阵

  在实际计算应用中,常常我们希望求的是方程的最小非负解。若矩阵被称为是方程的最小非负解,则它满足如下的两个条件:

  (1)是方程的非负解,即且满足方程NARE(1,1);

  (2)若方程的另一个非负解,则必有

  由于非对称代数Riccati方程有着广泛的用途,近年来,非对称代数Riccati方程的研究很受专家学者的重视。在研究方面,非对称代数Riccati方程的研究一般分为理论与算法两个方向,前者主要研究解的唯一性、存在性、解集的有界性、误差界与灵敏度分析,而后者则主要建立有效的求解算法。

  为了便于讨论,我们先给出一些基本概念。

  一个矩阵,代表矩阵A的第(i,j)个元素对于两个矩阵若对于任意,,若它的所有非对角线元素都是非正的,那么称矩阵A为Z矩阵。显然任意一个Z矩阵都可以表示为,其中。一个Z矩阵被称为M矩阵,如果,其中为B的谱半径。下面给出关于M矩阵的几个引理:

  引理0.0.1.[1]。是一个Z矩阵,则下列命题等价

  (a)A是非奇异的M矩阵;

  (b)A非奇异并且;

  (c)A的所有实特征值都是正数

  引理0.0.2.[1]是M矩阵。若满足如

  则B也是一个M矩阵,特别地,对于任意的正数θ,是非奇异M矩阵。

  引理0.0.3.[1]是非奇异M矩阵,若,则

  引理0.0.4.[1]若由非对称代数Riccati方程的系数矩阵构成的矩阵

  是非奇异的M矩阵,则非对称Riccati方程(1,1)有最小非负解S,并且和都是非奇异M矩阵。若是非对称Riccati方程(1,1)的任意一个解,且使得和都是非奇异的M矩阵,则必有。

  求非对称代数Riccati方程的最小非负解的解法有直接法和迭代法两种,当处理大规模矩阵问题时,迭代法则更加有效。郭[4][21]证明了当K是一个非奇异的M矩阵或者一个不可约的M矩阵,方程NARE(1,1)有一个最小非负解,接着在这一理论的基础上提出了很多有效的数值算法。郭首先利用一些经典的数值迭代方法应用于非对称代数Riccati方程,结合方程的具体特征提出了不动点迭代法,牛顿迭代法。

  Method1.1(不动点迭代法)

  令初始值,,对计算矩阵序列直到该序列收敛,其中由下面包含的Sylvester方程解得:

  其中,

  Method1.2(牛顿法)

  令初始值,,对计算矩阵序列,直到该序列收敛,其中由下面包含的Sylvester方程解得:

  由此我们可以看出无论是Method1.1还是Method1.2,算法的每一步迭代都需要对一个形为的Sylvester方程进行求解,这使得计算量变得庞大且算法繁琐臃肿。Guo[2]证明有矩阵

  其中时

  若K为非奇异M-矩阵或不可约奇异M-矩阵,NARE(1,1)有最小非负解。在此基础上,为了避免Method1.1和Method1.2的缺点,Guo、Lin和Xu[2]提出了进一步的保结构加倍算法(SDA)。

  Method 1.3(SDA)

  其中,

  Guo、Lin和Xu[1]证明了当K为非奇异M-矩阵或不可约奇异M-矩阵时,将收敛于NARE(1,1)的最小非负解,收敛于ARE(1,1)的共轭方程的最小非负解。

  卢[25]于2001年通过研究输运理论中NARE方程的具体特点,构想提出了一个只需求解向量方程的简单迭代算法来计算对应的最小非负解。由于该算法的过程只需求解向量方程,所以该方法比Juang[26]提出了的Gauss-Jacobi方法更有加可靠有效。白,高和卢[27]又于2006年在简单迭代的基础上提出了非线性块Jacobi迭代法和非线性块Gauss-Seidel迭代法。高和白[26]在2009年基于加倍迭代提出了非精确牛顿法。

  ALI算法

  思考Bai[5]提出的求解线性方程组的一种算法。

  考虑线性方程组

  把A做如下分解:

  其中,H和S分别是Hermite矩阵和反Hermite矩阵,假设H是一个正定矩阵,取一个参数>0研究方程组

  它们的解就是方程组(1,4)的解。由此我们得到Hermite矩阵和反Hermite分裂法(HSS)

  当我们在此算法的基础上,进一步将矩阵分裂和逐次逼近进行组合,并选取一个参数>0,这就是Ba,Guo和Xu[1]提出的交替线性化隐式迭代算法(ALI)

  Method 1.4(ALI)

  令初始值,对计算矩阵序列直到该序列收敛,其中由下面线性矩阵方程解得:

  由于该算法在每一步迭代计算时只需对两个线性矩阵方程进行求解,因而避免了求解繁琐的Sylvester方程。由此看出,ALI算法要比Method1.1和Method1.2都更加行之有效,且更容易在大型并行计算中执行。文献[1]中证明,当K为非奇异M-矩阵时,方程(1,6)产生的迭代序列收敛到ARE(1,1)的最小非负解,算法是可行的。

  算法依然有很多提高的空间,国内外学者也在不断的对非对称代数Riccati方程的理论和数值解法进行不断的完善和开拓新的方向。对于这些算法,仍然有丰富的内容可以研究。随着非对称代数Riccati方程理论的完善,数值算法的研究日益丰富,新的算法将会不断的被提出。本文主要总结几种求解非对称代数Riccati方程的数值算法。文章的结构如下:

  第一章将介绍基于ALI算法提出的LI算法和MLI算法。

  第二章将介绍基于牛顿法提出的广义非精确牛顿迭代法。

  第三章将介绍多重分裂法和两步迭代法。

  第一章线性隐式迭代算法

  1.1引言

  我们考虑如下的非对称代数Riccati方程(NARE)

  (1,1)

  其中矩阵A,B,C和D分别是和的矩阵。

  定义矩阵

  最近,白提出了交替线性隐式迭代算法(ALI)求解NARE(1,1),并证明了该算法是一个可行并且行之有效的,而且ALI迭代算法有可观的计算量和快速的收敛速率。基于ALI算法,我们提出一个线性隐式迭代算法(LI)来求解方程(1,1)的最小非负解。利用LI迭代算法的简单结构和萨曼斯基技巧,我们得到一个修正的线性隐式迭代法(MLI)。MLI算法相比于ALI算法具有快速收敛速率的同时也实现了更少的计算量。在适当的条件下,我们证明了LI迭代算法和MI迭代算法的单调收敛性。

  1.2线性隐式迭代法和修正的线性隐式迭代法

  由于交替方向加倍迭代方法求解方程(1,1)具有可观的计算量和快速的收敛速率相对于不动点迭代法,ALI迭代算法利用关于非线性项XCX的更多信息,因此具有更快的收敛速率和更好的数值稳定性。

  受到ALI迭代算法的启发,通过对方程(1,1)的构造,我们提出了如下的线性隐式迭代方法:

  其中

  根据方程(2,1)可以构造下面的迭代方程

  其中当时,LI迭代算法每一迭代步的计算量是[1]。线性隐式迭代算法跟ALI算法类似,但是结构更加简单。通过ALI迭代方法的研究,线性隐式迭代法对于求解方程(1,1)在每一迭代步只需求解一个线性矩阵方程,因此具有客观的计算量和快速的收敛速度。所以LI迭代算法在实际应用中会是一个不错的数值迭代算法。

  并且迭代格式(2,2)是ALI迭代算法的子问题。因此,可以构造另一个L迭代算法:可以这样获得矩阵序列,通过如下方程获得

  其中

  虽然LI要求解一个线性矩阵方程和ALI要求解两个线性矩阵方程,可以推测LI的迭代数大概是ALI迭代方法的两倍。如果能够减少LI迭代算法的迭代步数,可以减少计算量,并且可以获得一个比较好的算法。由于在每一迭代步大部分的计算量是花在求解线性矩阵方程,因此我们可以应用萨曼斯基技巧可以得到一个修正的线性隐式迭代算法(MLI)

  对于给定的参数并且,

  其中

  修正的线性隐式迭代法:

  算法1(修正的线性隐式迭代法)

  步1输入矩阵A,B,C和D选择参数和使得

  步2计算,则停止。

  步3通过求解方程来获得

  步4令k:=k+1并且到步2

  一般地,对于s的最优值很难选择,所以我们通常在做数值实验时令s=4或者s=6得到相应的算法。

  1.3新交替线性隐式迭代算法

  文献[22]进行了大量关于ALI算法收敛速率的讨论,并给出结论:当参数α的值是系数矩阵A和D的对角线元素最大值时,ALI算法的收敛速率最快。然而,当矩阵A和D的对角线元素区别很大时,ALI算法选取的参数就不能很好的反映方程(1,1)的信息。因此,迭代格式可分别由两个迭代参数控制,如下:

  将非对称代数Riccati方程(1,1)构造成如下两个不动点方程:

  其中分别是矩阵A和D对角线上的第i个元素。

  再结合方程(2,5),可以构造如下新交替线性化隐式迭代法来求解非对称代数Riccati方程(1,1)的最小非负解

  算法2(新交替线性隐式迭代法)

  令初始值,通过计算以下两个线性矩阵方程,通过计算

  其中收敛

  在新交替线性隐式迭代法中,若那么该算法就是文献[1]所提出的ALI迭代算法。另外,若S是方程(1,1)的最小非负解,α和β将随迭代步的变化而变化,且(其中分别是的所有特征值的最小实部)则该算法是双参数隐式迭代法.

  第二章广义非精确牛顿迭代法

  2.1引言

  我们考虑如下的非对称代数Riccati方程(NARE)

  (1,1)

  其中矩阵A,B,C和D分别是和的矩阵。定义矩阵

  牛顿迭代法是求解非对称代数Riccati方程的一个行之有效的数值方法,由其产生的矩阵序列{}单调上升地收敛到方程(1,1)的最小非负解,且收敛次数是二次的。然而在每一牛顿迭代步,都需要求解一个Sylvester方程。对于Sylvester方程一般釆用Bartels-Stewart和Hessenberg-Schur算法来求解当矩阵规模越大,这些算法的计算也会变得更加繁琐而困难,使得牛顿法在实际应用中变得更加困难。为避免求解繁琐的Sylvester方程,高和白利用参数迭代法来求解Sylvester矩阵方程,通过有效的控制参数迭代法所得解的精度得到了一个有效的非精确牛顿迭代法。本文在这基础上,利用广义的参数迭代法来求解Sylvester方程,从而得到木文的广义非精确牛顿迭代法。

  本章首先简单介绍了求解NARE(1,1)的牛顿迭代法并推导了求解Sylvester方程的广义参数迭代法接着提出广义非精确牛顿迭代法并分析了该算法的局部收敛性。

  2.2广义非精确牛顿迭代法

  我们通过运用牛顿迭代法的每一牛顿步作为外迭代和广义参数迭代法作为内迭代来构造广义非精确牛顿法。

  2.1牛顿迭代法

  关于Riccati方程的函数的一阶导是,是一个线性映射,

  因此,牛顿迭代格式可以是

  牛顿迭代格式等价于

  对于每一个k,以上的迭代格式都是一个Sylvester方程。

  2.2.2广义参数迭代法

  现在我们来讲讲求解连续型Sylvester方程的广义参数迭代法

  其中矩阵M和N都是M矩阵,,利用广义卡莱变换,则有

  其中,因此且使得和都是可逆的M矩阵。

  令

  整理可得

  根据方程(3,5)建立广义参数迭代格式

  取则可得到广义的参数迭代法:

  由,则

  采用级数的部分和逼近矩阵序列的极限,可令

  则

  2.2.3广义的非精确牛顿法

  现在通过技术性的结合牛顿迭代法和加倍迭序列参数迭代法,设计了求解NARE(1,1)的非精确牛顿迭代法

  那么,牛顿迭代格式(3,2)可简洁的改写为

  同样,我们有以下的卡莱变换

  其中,所以

  其中,

  所以,如果两个矩阵和,满足并且,那么由广义参数迭代法生成的矩阵序列{}收敛

  那么以上的广义非精确牛顿迭代法可以求解NARE(1,1)的最小非负解。

  算法3.(广义非精确牛顿法)

  步1输入矩阵A,B,C和D,初始矩阵,令该算法外迭代的精度为

  内迭代的精度是

  步2令k:=0,ρ=1.

  步3计算

  步4如果k=0,那么令

  步5.如果,那么令且停止

  步6.令并且

  步7.(广义的卡莱变换)

  7.1令

  7.2通过求解

  7.3通过求解

  7.4计算

  步8.(广义参数迭代法)

  8.1令

  8.2计算

  8.3如果

  8.4令l=0

  8.5通过

  8.6通过

  8.7如果并且跳出循环

  8.8计算

  8.9令,然后回到步骤8.5

  步9令,然后回到步骤3

  由于牛顿法具有二阶收敛速度,可通过适当的控制内迭代得到的解,如果解越精确则越有利于整个广义非精确牛顿法的收敛。因此我们可通过控制广义参数迭代法来控制内迭代,在不影响计算量的前提下提出了至少k步迭代法。

  2.3收敛性分析

  定理2.3.1.令S是方程NARE(1,1)的最小非负解。假设K是一个非奇异M矩阵。那么由广义非精确牛顿迭代法以为初始点迭代产生的矩阵序列具有良好的定义并且满足。

  定理2.3.2.令S是方程(1,1)的最小非负解,定义的矩阵K是非奇异M矩阵。若是算法2以为初始点选代生成的矩阵序列,满足,其中ε是一个给定的很小的正数,并且假设那么迭代序列有良好的定义,收敛到S且满足,其中。且算法2的收敛速率是线性的。

  第三章多重分裂和两步迭代法

  3.1多重分裂法

  多重分裂法(multi-splitting of matrices)是由O'Leary和White[23]在研究线性方程组时最先提出的概念。多重分裂法将线性方程问题中的系数矩阵进行不同分裂,使得在处理器执行大型并行运算时只需对分裂所得的对应子问题进行计算,再将得到的各个子问题的结果重新组合成原问题的迭代解。该方法最终将大规模问题简化为几个规模比较小的问题,充分表现了多重分裂思想的组合型并提高了并行计算的高效性。

  定义3.1[23]

  令,若满足

  (1),并且每个都是非奇异的

  (2),其中是对角矩阵且

  则称()是A的一个多重分裂。

  利用(1)可写为

  或

  上式两端乘并求和得

  记,则迭代式为

  定义3.2[23]

  设A,B,C是实矩阵,若,且C0,则称(B,C)是A的弱正则分裂;若0,C0,则称(B,C)是A的正则分裂。

  如下是多重分裂法(4,1)收敛性的一个结论。

  定理3.3[23]

  若对于是A的弱正则分裂且A是M-矩阵,则迭代式

  (4,1)是收敛的

  3.2两步迭代法

  在大规模的并行计算中多重分裂法有着重要的应用,在本节中我们仅考虑k=1时,即单分裂的情况。对线性方程组(1,4),令A=M-N,M=F-G分别是矩阵A和矩阵M的分裂形式,其中A,M都是非奇异的矩阵,Frommer和Syd[24]建立了求解(1.4)的两步迭代法(two-stage iteration method)。

  算法4(两步迭代法)

  给定初始向量,执行以下过程

  FOR

  FOR

  END

  END

  算法3.1中的是内循环的迭代步数的标志,是一个正整数的序列。另外内循环的步数取值也可以取固定值s。

  3.3收敛性分析

  定理3.4

  令A为非奇异矩阵且是正则分裂,是弱正则分裂,为内循环迭代序列,给定初始向量满足,则算法3,1产生的序列单调递增收敛到原方程的解。

  若在算法4的基础上,将每一方程的系数矩阵再进行一次分裂然后构造两步迭代过程则形成新的算法。

  定义3.5

  对于矩阵A的一种分裂形式,若是矩阵且,则它是M-分裂。

  引理3.6

  对于M分裂,当且仅当A是M-矩阵

  记

  则有(1,6)式转化为

  将和分裂得到

  其中

  易得

  定理3.7

  按上述方式所做的矩阵分裂都是规范分裂,也是M-分裂。

  推论3.8

  由此,我们基于ALI算法构造出解NARE(1.1)的两步迭代法:

  算法5(基于ALI算法的两步迭代法)

  FOR convergence DO

  FOR跳过

  END

  FOR

  END

  END

  经过直接计算,和有如下表示:

  定理3.9

  每步内选代序列分别单调递增收敛到,即

  在前面分析的基础上综合来看可以得到以下结论

  定理3.10

  令引理2,4中定义的矩阵K为M-矩阵,S为ARE(1,1)的最小非负解,矩阵分裂都为M-分裂,取为初始矩阵,则由算法3.2得到的序列单调递增,即

  并且收敛到S。