第三章-电力网络计算中的稀疏技术PPT课件

.,1,第三章电力网络计算中的稀疏技术,.,2,3.1概述,电网计算中要遇到大量的矩阵和矩阵的运算以及矩阵和矢量的运算由电力网络本身的结构特点所决定，这些矩阵和矢量中往往只有少量的元素是非零元素，大部分元素都是零元素。这些矩阵和矢量是稀疏的。矩阵稀疏度:一个nm阶矩阵A，如果其中的非零元素有,则定义矩阵A的稀疏度是:,.,3,3.1概述,例如:对于节点导纳矩阵，如果电力网络中每个节点的平均出线度是，即平均每个节点和条支路(不包括接地支路)相连，则节点导纳矩阵的稀疏度为:式中N是节点数，即导纳矩阵的维数对于实际电力系统，节点平均出线度一般为35，对500个节点的电力系统，若取4，其导纳矩阵的稀疏度仅为l。对于稀疏矢量的稀疏度也有类似的定义。把稀疏度很小的矩阵和矢量称为稀疏矩阵和稀疏矢量。,.,4,3.1概述,在进行稀疏矩阵和稀疏矢量的运算中，可以采用“排零存储”、“排零运算”的办法，可以大大减少存储量，提高计算速度。为实现这一作法所采用的程序技术称为稀疏技术它包括了稀疏矩阵技术和稀疏矢量技术两方面和不采用稀疏技术相比，采用稀疏技术可以加快计算速度几十甚至上百倍，而且对计算机的内存要求也可以大大降低电力系统规模越大，使用稀疏技术带来的效益就越明显可以说，稀疏技术的引入是对电力系统计算技术的一次革命，使许多原来不能做的电网计算可以很容易地实现。,.,5,3.1概述,最早将稀疏矩阵技术引入电力系统潮流计算的是美国学者WFTinney他于1967年发表了一篇关于利用稀疏矩阵和节点优化编号技术求解稀疏线性方程组的论文，并将稀疏矩阵技术用于牛顿法潮流计算中，大大提高了潮流计算的计算速度。60年代，计算100节点的系统的潮流已是十分困难的了，使用稀疏矩阵技术以后，几千个节点甚至上万个节点的大系统的潮流计算都可以实现了。到目前为止，几乎所有实用的电力网络分析程序都不同程度地使用了稀疏矩阵技术。,.,6,3.1概述,80年代中期，在利用并开发了矩阵的稀疏性的基础上，又进一步开发了矢量的稀疏性，即在求解稀疏线性代数方程组时，识别和稀疏矢量有关的有效的计算步，排除不必要的计算步，进一步减少了计算量，使整个计算的计算量减少到最低程度。自从1985年WF.Tinney首次发表了稀疏矢量法的论文以来，虽然还不能说稀疏矢量法已为所有的电力系统计算工作者所掌握，但其计算效力巳在电网计算的许多领域中显示出来，是一种很有发展前途的技术。掌握并灵活运用稀疏矩阵和稀疏矢量技术可以大大改变现有电力网络计算程序的面貌，使之达到一个新的更高的水平。,.,7,32稀疏技术,一、稀疏矢量和稀疏矩阵的存储稀疏矢量和稀疏矩阵的存储特点是排零存储：只存储其中的非零元素和有关的检索信息。存储的目的是为了在计算中能方便地访问使用，这就要求:(1)所采用的存储格式节省内存;(2)方便地检索和存取;(3)网络矩阵结构变化时能方便地对存储的信息加以修改。,.,8,稀疏矢量的存储：只需存储矢量中的非零元素值和相应的下标。对稀疏矩阵，有几种不同的存储方法，除了和矩阵的稀疏结构的特点有关，还和使用时所采用的算法有关。不同的算法往往要求对稀疏矩阵中的非零元素有不同的检索方式。因此，应根据应用对象的实际情况来选择合适的存储方式。,.,9,3.2稀疏技术,1.散居格式定义三个数组，分别存储下列信息：VA存储A中非零元素aij的值，共个，IA存储A中非零元素aij的行指标i，共个，JA存储A中非零元素aij的列指标j,共个。总共需要3个存储单元。,.,10,3.2稀疏技术,散居格式的优点:A中的非零元在上面数组中的位置可任意排列，修改灵活；缺点：因其存储顺序无一定规律，检索起来不方便。例如：在上面数组中查找下标是i，j的元素aij，需要在数组IA中找下标是i同时在JA数组中的下标是j的元素，最坏的可能性要在整个数组中查找一遍，工作量极大。因此，有必要按某一事先约定的顺序来存储稀疏矩阵A中的非零元，以使查找更为方便快捷。,.,11,3.2稀疏技术,2.按行（列）存储格式按行(列)顺序依次存储A中的非零元，同一行(列)元素依次排在一起。以按行存储为例，其存储格式是：VA按行存储矩阵A中的非零元aij，共个，JA按行存储矩阵A中非零元的列号，共个，IA记录A中每行第一个非零元素在VA中的位置，共n个。,.,12,3.2稀疏技术,查找第i行的非零元素：即在VA中取出从k=IA(i)到IA(i+1)共IA(i+1)IA(i)个非零元就是A中第i行的全部非零元，非零元的值是VA(k)，其列号由JA(k)给出。找第i行第j列元素aij在VA中的位置：对k从IA(i)到IA(i+1)-1，判列号JA(k)是否等于j，如等，则VA(k)即是要找的非零元aij。这种存储方案可以用于存储任意稀疏矩阵，A可以不是正方矩阵。如果A是方矩阵，可以把A的对角元素提出来单独存储，而对角元素的行列指标都无需记忆。,.,13,3.2稀疏技术,3三角检索存储格式三角检索的存储格式特别适合稀疏矩阵的三角分解的计算格式。有几种不同的存储格式，这里以按行存储A的上三角部分非零元，按列存A的下三角部分非零元这种存储格式来说明。令A是nn阶方阵：U存A的上三角部分的非零元的值，按行依次存储；JU存A的上三角部分的非零元的列号；IU存A中上三角部分每行第一个非零元在U中的位置(首地址)；L按列存储A中下三角非零元素的值；IL按列存储A中下三角非零元素的行号；JL存储A的下三角部分每列第一个非零元在L中的位置(首地址)；D存储A的对角元素的值，其检索下标不需要存储.,.,14,例：,有了IU表即可知道A的上三角部分第i行的非零元的数目：IU(i+1)-IU(i)。第一行：IU(2)-IU(1)312。如果要查找A中的上三角第i行所有非零元素，只要扫描k从IU(i)到IU(i+1)-1即可，JU(k)指出了该元素的列号，U(k)是该非零元素的值对于按列存储的格式进行查找的情况类同。,列号,位置,.,15,3.2稀疏技术,三角检索存储格式在矩阵A的稀疏结构已确定的情况下使用是十分方便的。但在计算过程中，如果A的稀疏结构发生了变化，即其中的非零元素的分布位置发生变化，相应的检索信息也要随着变化，很不方便。有两种办法处理这类问题。第一种办法事先估计出在随后的计算中A的哪些位置可能产生注入元素(即原来是零元素，在计算过程中变成非零元素)，在存储时事先留了位置，即把这个原来是零元素的也按非零元素一样来存储，这样在计算中该元素由零元素变成非零元素时就不必改变原来的检索信息。第二种办法可以用下面介绍的链表存储格式。其特点是当矩阵A的结构发生变化时修改灵活，不必事先存储这些零元素，也不必在产生非零注入元素时进行插入等处理。,.,16,32稀疏技术,4.链表（Link)存储格式以按行存储的格式为例来说明。这时需要按行存储格式中的三个数组外还需要增加数组：VA按行存储矩阵A中的非零元aij，共个，JA按行存储矩阵A中非零元的列号，共个，IA记录A中每行第一个非零元素在VA中的位置，共n个。LINK下一个非零元素在VA中的位置，对每行最后一个非零元素，该值置为0。NA每行非零元素的个数。,.,17,当新增加一个非零元素时，可把它排在最后，并根据该非零元素在该行中的位置的不同来修改其相邻元素的LINK值例如，新增a13，把a13排在第11个位置，把a12的LINK值由3改为11，a13本身的LINK值置为3，NA(1)增加1，变为4。,a13,11,11,3,4,a13,3,.,18,3.2稀疏技术,二、稀疏矩阵的因子分解对nn阶矩阵A可以通过LU分解的方法分解成为一个下三角矩阵L和一个单位上三角矩阵U的乘积：ALULU分解分为两步：（1）按行规格化运算；（2）消去运算或更新运算。也可以将A分解成一个单位下三角矩阵L、一个对角矩阵D和一个单位下三角矩阵U的乘积形式。ALDU,.,19,32稀疏技术,三、利用系数矩阵因子表求解稀疏线性代数方程组对n维线性代数方程组：,.,20,1.前代运算将L分解成一个单位矩阵和一个严格下三角矩阵之和,先求z1，再求z2，.，最后求zn。,.,21,32稀疏技术,2.除法运算,.,22,32稀疏技术,3.回代运算：将U分解为一个单位矩阵和一个严格上三角矩阵之和,.,23,先求xn，.，最后求x1,节点编号优化,.,24,3.3稀疏矩阵的图论描述,在电力网络分析中，稀疏线性代数方程组的系数矩阵的稀疏结构和电力网络的拓扑结构相对应。节点导纳矩阵的非对角非零元素和电力网络的串联支路有一一对应的关系，导纳矩阵的稀疏结构可以用图来描述。稀疏矩阵的因子表的稀疏结构也可以用图来描述。在因子分解的过程中，矩阵的稀疏结构将发生变化，相应的图的结构也将发生变化。本节内容就是利用网络图对稀疏矩阵的因子分解和稀疏矢量的前代回代过程进行分析。电网矩阵（计算，变换)矩阵网络拓扑,.,25,1基本定义和术语,假设Ax=b中，A是对称的稀疏矩阵(3-11)，b是独立矢量，x是解矢量。将A分解成因子表(3-12)，则A=UTDU（式1）。下面给出几个定义：A图：是和矩阵A有相同拓扑关系的网络图。（图3.1a）有向A图：是在给定的A图上，对于给定的节点编号，规定每条边的正方向都是由小号节点指向大号节点，形成的有向图。（图3.1b）赋权有向A图：在有向A图上，将A的非对角非零元素所对应的边称为互边，并将该边的边权赋之以该非零元素的值；将A的对角元素用接地边模拟，称为自边，赋以该对角元素的值。这样即得到赋权有向A图，它保存了矩阵A中的所有信息。（图3.1c）按同样的方式可以来描述因子表U。（见书5758页）,转到3.5,.,26,2.因子分解过程的图论描述,将对称矩阵A因子分解就是要将（311）式的矩阵A分解成（312）式的矩阵U和D，D是对角线矩阵，并使A=UTDU。在图上，就是要将赋权有向A图变成赋权有向因子图。因子分解的过程按照节点号由小到大的顺序依次进行，每步计算包括了规格化运算和消去运算两个步骤。也就是将第49页上的计算流程在图上实现。（1）规格化运算（图3.3）由于A是对称矩阵，当需要对A的第p行元素进行规格化计算时，只需要对A矩阵中上三角部分中的第p行非零元素进行。如图，因子分解过程进行到第p步时，需要规格化的三个元素的列号分别是j，k，l。规格化运算的公式为:api=api/apppi,i=j,k,l（式2）这在赋权有向A图上，相当于对节点p发出的所有互边的边权加以修正，新的边权等于原边权除以节点p的自边边权。这种操作只改变节点p发出的互边边权，边数并未增加。,.,27,（2）消去运算(图3.4)取第p行第p列为轴线，第p步的消去运算实际上就是要对处于轴线上的非零元素所在的行列相交叉的位置上的元素进行消去运算。如图，需要对处于第p行第p列上的非零元素所在的j，k，l行和j，k，l列相交叉的位置上的共9个元素进行消去运算。如果只保留上三角矩阵，只需要对三个对角元素和三个非对角元素进行消去运算。对对角元素的修正公式是aii=aii-aipapipi,i=j,k,l（式3）因为在消去运算之前已经对api进行过规格化运算，而式中的aip还没有进行过规格化，而aip=apiapp因此使用上三角元素计算时，消去运算的公式应该用下式：aii=aiiapi2apppi,i=j,k,l（式4）在赋权有向A图上，就是对节点p发出的边的收点j,k,l上的自边边权进行修正，边权减少api2app。,.,28,对于上三角部分的非零元素，共有三个需要修正，即ajk,akl,ajl,如图3.4。对于非对角元素，消去运算的公式为：aim=aimaipapmim,pi,pmi,m从j,k,l中取值（式5）因为只储存A的上三角部分，所以aip（下三角元素）应该用api代替，上述公式变为：aim=aimapiapmappim,pi,pi，说明边是由小号节点指向大号节点ifuij0then/uij0，说明是上三角矩阵U中的非零元素zj=zj-uijziendifendloop,.,31,将这段程序和赋权有向因子图连系起来看，uij0就表示赋权有向因子图上节点i，j之间有边；uij0，则图上不出现边。把zi定义为赋权有向因子图上的点位，用ei表示；赋权有向因子图上的互边的边权是uij，则上面的程序可以写成：ej=ej-uijeiij,ji（式7）线性代数方程组中独立矢量或解矢量中的非零元素可以用赋权有向因子图上节点的点位来描述，而前代过程可在赋权有向因子图上用点位的变化来描述。首先，在赋权有向因子图上，将每个节点的点位赋值以独立矢量b中相应的非零元素的值。然后在赋权有向因子图上按节点号i从小到大顺序（因为是前代）依次按（式7）修正该节点i发出边的对端节点j的点位，将对端节点j的点位减小uijei。这一过程一种进行到将所有点都扫描完。如果节点i的点位为零，说明zi为零，上述修正不需要做。这一过程结束后，因子图上的点位就是前代的结果。（对照51页式36a）,.,32,2.规格化过程规格化过程的实质是求解Dy=z中的y，D是对角元素矩阵，z在前代过程中已经求出。因此求解y很容易，只需要做除法运算yi=zi/dii在赋权有向因子图上，也就是将前代结束后节点i的点位ei除以节点i的自边边权，即eiei/dii（式8）。3.回代过程令赋权有向因子图上的点位已经是经过前代和规格化后的值。按节点号j从n开始，由大到小，对所有指向j的边其发端节点i的点位进行修正（也就是逆着各边的方向），修正公式为：eieiuijejij，ij（式9）当所有节点的点位都修正完毕，回代过程结束。此时，赋权有向因子图上的点位就是要求的解矢量x。,.,33,4.总结在图上进行前代回代的计算步骤如下：(1)将独立矢量b的非零元素赋值为赋权有向因子图上的点位。(2)扫描i从1到n-1。用（式7）修正节点i发出的边的对端节点j的点位。（3）对所有节点用（式8）对点位进行规格化。（4）扫描j从n到2。对所有指向节点j的边的发端节点i，用（式9）修正其点位。5.例题（63页）板书,.,34,4.不对称稀疏矩阵的图上因子分解,定义（第64页）图3.7图3.8,.,35,.,36,.,37,.,38,.,39,.,40,.,41,.,42,.,43,.,44,3.5节点编号优化,稀疏技术的核心关键有两点：一是排零存储和排零运算，二是节点优化编号。排零存储和排零运算有效地避免对计算结果没有影响的存储和计算，大大提高程序的计算效力。节点的编号顺序对于计算效力的影响也是至关重要的，它直接影响到矩阵A的因于表矩阵的稀疏度。严格地说，最优编号是一个组合优化问题，求其最优解是困难的，但在实际工程中，有许多实用的次优的编号方法得到了广泛的应用。,.,45,.,46,3.5节点编号优化,节点编号的优化:寻求一种使注入元素数目最少的节点编号方式。为此，可以比较各种不同的节点编号方案在三角分解中出现的注入元素数目，从中选取注入元素最少的节点编号方案。但这样做需要分析非常多的方案。例如对仅有5个节点的电力网络来说，其编号的可能方案就有5！120个。一般，对n个节点的电力网络来说，节点编号的可能方案就有n!个，工作量非常大。因此，在实际计算工作中往往采取一些简化的方法，求出一个相对的节点编号优化方案，并不一定追求“最优”方案。,.,47,3.5节点编号优化,1Tinney-1编号方法又称为静态接点优化编号方法:在编号以前，首先统计电力网络各节点的出线