微分代数系统结构化分析
李光远1,2?,冯 勇2
【摘 要】摘要：对工程和科学问题进行建模和仿真的时候,人们常常很自然地会用微分代数系统对这些问题进行描述.为了检验微分代数系统的初始相容性并进行求解,对微分代数系统进行结构化分析非常重要.本文对经典的微分代数系统结构化分析方法进行了深入的研究;提出了一种新的结构化分析方法,可以高效地对大规模、高阶高指标的微分代数系统进行结构化分析,并快速检验其初始相容性;证明了该方法的终止性,分析了其最坏时间复杂度.该方法的关键在于对最大加权二部子图的使用,而最大加权二部子图则来源于原始系统的加权二部图.实验结果显示,该方法能高效地完成对微分代数系统的结构化分析. 【期刊名称】控制理论与应用 【年(卷),期】2017(034)008 【总页数】9
【关键词】微分代数系统;结构化分析;初始相容性;加权二部图;算法
1 引言(Introduction)
对工程和科学问题进行建模和仿真的时候,人们常常很自然地会使用微分代数系统对物理系统进行描述,微分代数系统也引起了越来越多的关注[1].典型的物理系统如多体动力系统、航空器飞行轨迹追踪、优化控制系统、工艺过程、电子电路仿真和机器人路径规划问题等等,都可以用微分代数系统进行模拟[2-4].一旦求解出了建模的微分代数系统,就可以对相应的物理系统进行仿真.微分代数系统包含了微分方程和代数方程的特性,以及混合这两种方程所导致的其他特性[5],为了求解微分代数系统就需要对其进行结构化分析,选择合适的求解方法.另外,
在求解微分代数系统之前,为了确保所建立的模型是合理并且可解的,也需要通过结构化分析对微分代数系统的初始相容性进行验证.因此,无论是为了求解微分代数系统还是验证其初始相容性,都需要对微分代数系统进行结构化分析.
到目前为止,学界已经提出了很多关于微分代数系统结构化分析的方法,这些方法几乎都需要将微分代数系统的微分指标降为0(关于微分指标的定义,可以参考文献[6]和文献[7]),将系统转化常微分方程.Pantelides在文献[8]中率先提出了微分代数系统的初始相容性问题,并给出了一种对微分代数系统进行结构化分析的方法.Pantelides方法利用一种简单二部图算法,找出微分代数系统中的最小结构化奇异子集(minimally structurally singular,MSS),然后对MSS中的方程进行微分,从而修改二部图,重复上述两个步骤直到方程组中的所有MSS子集都被找出来为止(关于结构化奇异以及MSS的定义,可以参考文献[8]).这种方法取得了较好的效果并得到了广泛的运用,但这种方法只能处理一阶的微分代数系统,如果用于处理高阶的微分代数系统,则该方法的处理时间和空间都会成倍地增加.在文献[9]中,Gear提出了另一种方法,Gear方法通过一系列的符号操作找出微分代数系统中的代数方程,并对这些代数方程进行微分,重复这些处理过程直到微分代数系统被转化为常微分方程,这是一种符号方法并能将微分指标完全降低为0.但是对普通的非线性微分代数系统,Gear方法需要进行大量的操作,其中很多操作都比较困难,有时甚至根本就不能完成.Mattsson和S?derlind在文献[10]中提出了一种虚拟方法.在这种虚拟方法中,对原系统中部分或全部方程进行微分,新得到的方程与原方程系统共同构成了一个增广的方程系统.用代数变量替换微分变量,就可以将这个增广的方程系统转化为一个纯粹的代数方程系统并最终对其进行求解.为了实现增广的方程系统向代数方程系统的转化,这种虚拟方法需要
对许多方程进行不必要的微分,这就增加了操作的复杂性,极大地降低了处理的效率.Pryce提出了一种签名方法,或者说叫Σ-方法[11-12].Σ-方法定义了一种签名矩阵Σ =(σij),σij是第i个方程中第j变量导数的最高次阶,如果该方程中没有出现这个变量,则取σij为-∞.在得到这个矩阵的最大横截面之后(highest-value transversal,HVT),就可以通过一个不动点迭代算法求这个HVT的对偶,得到的结果就是需要微分的方程与微分的次数c,以及微分后各个变量导数的最高次阶d(关于最大横截面的定义,可以参考文献[11,13]).Σ-方法的实现有赖于方程系统的稀疏性,并且忽略了这样一个事实,那就是方程的解析形式和稀疏结构可能会改变解的范围,而这在实际应用中是非常重要的.并且Σ-方法对方程系统的奇异性验证并不是一开始就进行,而是在最后通过一个Jacobian矩阵来完成的,而这个Jacobian矩阵的构建需要使用先前求得的c和d.因此,不管微分代数系统是否结构化非奇异,Σ-方法都需要完整地执行一遍,这对一些结构化奇异的系统显然是不必要的.对于较大规模的问题,秦小林等人充分利用了其稀疏性,提出了一种三角分块化的方法[14].借助三角分块化技术,秦方法改进了Σ-方法,使其在解决大规模的微分代数系统时具有更高的效率,但这种方法的基础依然是签名矩阵和不动点迭代算法.
本文以加权二部图表示微分代数系统,提出了一种高效的微分代数系统结构化分析方法.该方法定义了微分代数系统的最大加权二部图和对应的最大加权二部子图,并通过对系统最大加权二部子图进行适当的操作,实现了对微分代数系统,尤其是大规模、高阶高指标的微分代数系统的结构化分析.最后,通过实验对该方法进行了验证.
2 最大加权二部子图(Maximal weighted bipartite sub-graph)
微分代数系统结构化分析
