第三章 电力网络计算中的稀疏技术

1、第三章第三章 电力网络计算中的稀疏技术电力网络计算中的稀疏技术3.1 3.1 概概 述述 电网计算中要遇到大量的电网计算中要遇到大量的矩阵和矩阵矩阵和矩阵的运算以及的运算以及矩阵和矢矩阵和矢量量的运算的运算 由电力网络本身的结构特点所决定，这些矩阵和矢量中往由电力网络本身的结构特点所决定，这些矩阵和矢量中往往往只有少量的元素是非零元素，大部分元素都是零元素只有少量的元素是非零元素，大部分元素都是零元素 。这些矩阵和矢量是这些矩阵和矢量是稀疏稀疏的。的。 矩阵稀疏度矩阵稀疏度: :一个一个n nm m阶矩阵阶矩阵A A，如果其中的非零元素有，如果其中的非零元素有,则定义矩阵则定义矩阵A A的的稀

2、疏度稀疏度是是: : %100nm3.1 3.1 概概 述述 例如例如: :对于对于节点导纳矩阵节点导纳矩阵，如果电力网络中每个节点的平，如果电力网络中每个节点的平均出线度是均出线度是，即平均每个节点和，即平均每个节点和条支路条支路( (不包括接地不包括接地支路支路) )相连，则节点导纳矩阵的稀疏度为相连，则节点导纳矩阵的稀疏度为: : 式中式中N N是节点数，即导纳矩阵的维数对于实际电力系统，是节点数，即导纳矩阵的维数对于实际电力系统，节点平均出线度一般为节点平均出线度一般为3 35 5，对，对500500个节点的电力系统，个节点的电力系统，若若 取取4 4，其导纳矩阵的稀疏度仅为，其导纳矩

3、阵的稀疏度仅为l l。 对于稀疏矢量的稀疏度也有类似的定义。对于稀疏矢量的稀疏度也有类似的定义。 把稀疏度很小的矩阵和矢量称为把稀疏度很小的矩阵和矢量称为稀疏矩阵和稀疏矢量稀疏矩阵和稀疏矢量。%1001N3.1 3.1 概概 述述 在进行在进行稀疏矩阵和稀疏矢量稀疏矩阵和稀疏矢量的运算中，可以采用的运算中，可以采用“排零存排零存储储”、“排零运算排零运算”的办法，可以大大的办法，可以大大减少存储量，提高减少存储量，提高计算速度计算速度。 为实现这一作法所采用的程序技术称为为实现这一作法所采用的程序技术称为稀疏技术稀疏技术它包括它包括了了稀疏矩阵技术和稀疏矢量技术稀疏矩阵技术和稀疏矢量技术两方面

4、两方面 和不采用稀疏技术相比，采用稀疏技术可以加快计算速度和不采用稀疏技术相比，采用稀疏技术可以加快计算速度几十甚至上百倍，而且对计算机的内存要求也可以大大降几十甚至上百倍，而且对计算机的内存要求也可以大大降低低 电力系统规模越大，使用稀疏技术带来的效益就越明电力系统规模越大，使用稀疏技术带来的效益就越明显可以说，显可以说，稀疏技术的引入是对电力系统计算技术的一稀疏技术的引入是对电力系统计算技术的一次革命次革命，使许多原来不能做的电网计算可以很容易地实现。，使许多原来不能做的电网计算可以很容易地实现。3.1 3.1 概概 述述 最早将稀疏矩阵技术引入电力系统潮流计算的是最早将稀疏矩阵技术引入电

5、力系统潮流计算的是美国学者美国学者W WF FTinneyTinney他于他于19671967年发表了一篇关于年发表了一篇关于利用稀疏矩阵利用稀疏矩阵和节点优化编号技术求解稀疏线性方程组和节点优化编号技术求解稀疏线性方程组的论文，并将的论文，并将稀稀疏矩阵技术用于牛顿法潮流计算疏矩阵技术用于牛顿法潮流计算中，大大提高了潮流计算中，大大提高了潮流计算的计算速度。的计算速度。 6060年代，计算年代，计算100100节点的系统的潮流已是十分困难的了，节点的系统的潮流已是十分困难的了，使用稀疏矩阵技术以后，几千个节点甚至上万个节点的大使用稀疏矩阵技术以后，几千个节点甚至上万个节点的大系统的潮流计算都

6、可以实现了。系统的潮流计算都可以实现了。 到目前为止，几乎所有实用的电力网络分析程序都不同程到目前为止，几乎所有实用的电力网络分析程序都不同程度地使用了稀疏矩阵技术。度地使用了稀疏矩阵技术。 3.1 3.1 概概 述述 8080年代中期，在利用并开发了矩阵的稀疏性的基础上，又年代中期，在利用并开发了矩阵的稀疏性的基础上，又进一步开发了矢量的稀疏性，即在求解稀疏线性代数方程进一步开发了矢量的稀疏性，即在求解稀疏线性代数方程组时，识别和稀疏矢量有关的有效的计算步，排除不必要组时，识别和稀疏矢量有关的有效的计算步，排除不必要的计算步，进一步减少了计算量，使整个计算的计算量减的计算步，进一步减少了计算

7、量，使整个计算的计算量减少到最低程度。少到最低程度。 自从自从19851985年年W WF.TinneyF.Tinney首次发表了稀疏矢量法的论文以首次发表了稀疏矢量法的论文以来，虽然还不能说稀疏矢量法已为所有的电力系统计算工来，虽然还不能说稀疏矢量法已为所有的电力系统计算工作者所掌握，但其计算效力巳在电网计算的许多领域中显作者所掌握，但其计算效力巳在电网计算的许多领域中显示出来，是一种很有发展前途的技术。掌握并灵活运用稀示出来，是一种很有发展前途的技术。掌握并灵活运用稀疏矩阵和稀疏矢量技术可以大大改变现有电力网络计算程疏矩阵和稀疏矢量技术可以大大改变现有电力网络计算程序的面貌，使之达到一个新

8、的更高的水平。序的面貌，使之达到一个新的更高的水平。3 32 2 稀疏技术稀疏技术一、稀疏矢量和稀疏矩阵的存储一、稀疏矢量和稀疏矩阵的存储 稀疏矢量和稀疏矩阵的存储特点是稀疏矢量和稀疏矩阵的存储特点是排零存储排零存储：只存储其中：只存储其中的非零元素和有关的检索信息。的非零元素和有关的检索信息。 存储的存储的目的目的是为了在计算中能方便地访问使用，这就是为了在计算中能方便地访问使用，这就要求要求: : (1)(1)所采用的存储格式节省内存所采用的存储格式节省内存; ; (2)(2)方便地检索和存取方便地检索和存取; ; (3)(3)网络矩阵结构变化时能方便地对存储的信息加以修改网络矩阵结构变化

9、时能方便地对存储的信息加以修改。稀疏矢量稀疏矢量的存储：只需存储矢量中的非零元素的存储：只需存储矢量中的非零元素值和相应的下标。值和相应的下标。对稀疏矩阵对稀疏矩阵，有几种不同的存储方法，除了，有几种不同的存储方法，除了和和矩阵的稀疏结构的特点有关，还和使用时所采用矩阵的稀疏结构的特点有关，还和使用时所采用的算法有关的算法有关。不同的算法往往要求对稀疏矩阵中的非零元素不同的算法往往要求对稀疏矩阵中的非零元素有不同的检索方式。因此，应根据应用对象的实有不同的检索方式。因此，应根据应用对象的实际情况来选择合适的存储方式。际情况来选择合适的存储方式。3.2 3.2 稀疏技术稀疏技术1.1.散居格式散

10、居格式 定义三个数组，分别存储下列信息：定义三个数组，分别存储下列信息： VAVA存储存储A A中非零元素中非零元素a aijij的值，共的值，共个，个， IAIA存储存储A A中非零元素中非零元素a aijij的行指标的行指标i i，共，共个，个， JAJA存储存储A A中非零元素中非零元素a aijij的列指标的列指标j,j,共共个。个。 总共需要总共需要33个存储单元。个存储单元。3.2 3.2 稀疏技术稀疏技术 散居格式的散居格式的优点优点:A:A中的非零元在上面数组中的位置可任意中的非零元在上面数组中的位置可任意排列，修改灵活；排列，修改灵活； 缺点缺点：因其存储顺序无一定规律，检索

11、起来不方便。：因其存储顺序无一定规律，检索起来不方便。 例如例如：在上面数组中查找下标是：在上面数组中查找下标是i i，j j的元素的元素a aijij，需要在数，需要在数组组IAIA中找下标是中找下标是i i同时在同时在JAJA数组中的下标是数组中的下标是j j的元素，最坏的元素，最坏的可能性要在整个数组中查找一遍，工作量极大。的可能性要在整个数组中查找一遍，工作量极大。 因此，有必要因此，有必要按某一事先约定的顺序来存储稀疏矩阵按某一事先约定的顺序来存储稀疏矩阵A A中中的非零元，以使查找更为方便快捷。的非零元，以使查找更为方便快捷。3.2 3.2 稀疏技术稀疏技术2.2.按行（列）存储格

12、式按行（列）存储格式 按行按行( (列列) )顺序依次存储顺序依次存储A A中的非零元，同一行中的非零元，同一行( (列列) )元素依元素依次排在一起。次排在一起。 以按行存储为例，其存储格式是：以按行存储为例，其存储格式是： VAVA按行存储矩阵按行存储矩阵A A中的非零元中的非零元a aijij，共，共个，个， JA JA按行存储矩阵按行存储矩阵A A中非零元的列号，共中非零元的列号，共个，个， IA IA记录记录A A中每行第一个非零元素在中每行第一个非零元素在VAVA中的位置，共中的位置，共n n个。个。3.2 3.2 稀疏技术稀疏技术 查找第查找第i i行的非零元素行的非零元素：即在

13、：即在VAVA中取出从中取出从k=IA(i)k=IA(i)到到IA(i+1)IA(i+1)共共IA(i+1)IA(i+1)IA(i)IA(i)个非零元就是个非零元就是A A中第中第i i行的全部非零元，行的全部非零元，非零元的值是非零元的值是VA(k)VA(k)，其列号由，其列号由JA(k)JA(k)给出。给出。 找第找第i i行第行第j j列元素列元素a aijij在在VAVA中的位置：中的位置：对对k k从从IA(i)IA(i)到到IA(i+1)-1IA(i+1)-1，判列号，判列号JA(k)JA(k)是否等于是否等于j j，如等，则，如等，则VA(k)VA(k)即是即是要找的非零元要找的

14、非零元a aijij。 这种存储方案可以这种存储方案可以用于存储任意稀疏矩阵用于存储任意稀疏矩阵，A A可以不是正可以不是正方矩阵。方矩阵。 如果如果A A是方矩阵，可以把是方矩阵，可以把A A的对角元素提出来单独存储，而的对角元素提出来单独存储，而对角元素的行列指标都无需记忆。对角元素的行列指标都无需记忆。3.2 3.2 稀疏技术稀疏技术3 3三角检索存储格式三角检索存储格式 三角检索的存储格式特别适合稀疏矩阵的三角分解的计算三角检索的存储格式特别适合稀疏矩阵的三角分解的计算格式。有几种不同的存储格式，这里以格式。有几种不同的存储格式，这里以按行存储按行存储A A的上三的上三角部分非零元角部

15、分非零元，按列存按列存A A的下三角部分非零元的下三角部分非零元这种存储格这种存储格式来说明。令式来说明。令A A是是n nn n阶方阵：阶方阵：UU存存A A的上三角部分的非零元的值，按行依次存储；的上三角部分的非零元的值，按行依次存储；JUJU存存A A的上三角部分的非零元的列号；的上三角部分的非零元的列号；IUIU存存A A中上三角部分每行第一个非零元在中上三角部分每行第一个非零元在U U中的位置中的位置 ( (首地址首地址) )；LL按列存储按列存储A A中下三角非零元素的值；中下三角非零元素的值；ILIL按列存储按列存储A A中下三角非零元素的行号；中下三角非零元素的行号；JLJL存

16、储存储A A的下三角部分每列第一个非零元在的下三角部分每列第一个非零元在L L中的位置中的位置( (首地址首地址) )；DD存储存储A A的对角元素的值，其检索下标不需要存储的对角元素的值，其检索下标不需要存储. .例：44434233232221141211000000aaaaaaaaaaA有了有了IUIU表即可知道表即可知道A A的上三角部分第的上三角部分第i i行的非零元的数目：行的非零元的数目：IU(i+1)-IU(i+1)-IU(i)IU(i)。第一行：。第一行： IU(2)-IU(1)IU(2)-IU(1)3 31 12 2。如果要查找如果要查找A A中的上三角第中的上三角第i i

17、行所有行所有非零元素，只要扫描非零元素，只要扫描k k从从IU(i)IU(i)到到IU(i+1)-1IU(i+1)-1即可，即可，JU(k)JU(k)指出了该元指出了该元素的列号，素的列号，U(k)U(k)是该非零元素的是该非零元素的值值对于按列存储的格式进行查找的情对于按列存储的格式进行查找的情况类同。况类同。列号列号位置位置3.2 3.2 稀疏技术稀疏技术 三角检索存储格式三角检索存储格式在矩阵在矩阵A A的的稀疏结构稀疏结构已确定的情况下使已确定的情况下使用是十分方便的。但在计算过程中，如果用是十分方便的。但在计算过程中，如果A A的稀疏结构发的稀疏结构发生了变化，即其中的非零元素的分布

18、位置发生变化，相应生了变化，即其中的非零元素的分布位置发生变化，相应的检索信息也要随着变化，很不方便。有两种办法处理这的检索信息也要随着变化，很不方便。有两种办法处理这类问题。类问题。 第一种办法第一种办法事先估计出在随后的计算中事先估计出在随后的计算中A A的哪些位置可能的哪些位置可能产生注入元素产生注入元素( (即原来是零元素，在计算过程中变成非零即原来是零元素，在计算过程中变成非零元素元素) )，在存储时事先留了位置，即把这个原来是零元素，在存储时事先留了位置，即把这个原来是零元素的也按非零元素一样来存储，这样在计算中该元素由零元的也按非零元素一样来存储，这样在计算中该元素由零元素变成非

19、零元素时就不必改变原来的检索信息。素变成非零元素时就不必改变原来的检索信息。 第二种办法第二种办法可以用下面介绍的链表存储格式。其特点是当可以用下面介绍的链表存储格式。其特点是当矩阵矩阵A A的结构发生变化时修改灵活，不必事先存储这些零的结构发生变化时修改灵活，不必事先存储这些零元素，也不必在产生非零注入元素时进行插入等处理。元素，也不必在产生非零注入元素时进行插入等处理。3 32 2 稀疏技术稀疏技术4.4.链表（链表（ Link) Link) 存储格式存储格式 以按行存储的格式为例来说明。以按行存储的格式为例来说明。 这时需要按行存储格式中的三个数组外还需要增加数组：这时需要按行存储格式中

20、的三个数组外还需要增加数组： VAVA按行存储矩阵按行存储矩阵A A中的非零元中的非零元a aijij，共，共个，个， JA JA按行存储矩阵按行存储矩阵A A中非零元的列号，共中非零元的列号，共个，个， IA IA记录记录A A中每行第一个非零元素在中每行第一个非零元素在VAVA中的位置，共中的位置，共n n个。个。 LINKLINK下一个非零元素在下一个非零元素在VAVA中的位置，对每行最后一个中的位置，对每行最后一个非零元素，该值置为非零元素，该值置为0 0。 NANA每行非零元素的个数。每行非零元素的个数。44434233232221141211aaaaaaaaaaA当新增加一个非零元

21、素时，可把当新增加一个非零元素时，可把它排在最后，并根据该非零元素它排在最后，并根据该非零元素在该行中的位置的不同来修改其在该行中的位置的不同来修改其相邻元素的相邻元素的LINKLINK值例如，新增值例如，新增a a1313，把，把a13排在第排在第1111个位置，把个位置，把a a1212的的LINKLINK值由值由3 3改为改为1111， a13本身的本身的LINKLINK值置为值置为3 3，NA(1)NA(1)增加增加1 1，变，变为为4 4。a13111134a1333.2 3.2 稀疏技术稀疏技术二、稀疏矩阵的因子分解二、稀疏矩阵的因子分解 对对nn阶矩阵阶矩阵A可以通过可以通过LU

22、分解的方法分解成为一个分解的方法分解成为一个下下三角矩阵三角矩阵L和一个和一个单位上三角矩阵单位上三角矩阵U的乘积：的乘积：ALU LU分解分为两步分解分为两步： （1）按行规格化运算；）按行规格化运算； （2）消去运算或更新运算。）消去运算或更新运算。 也可以将也可以将A分解成一个分解成一个单位下三角矩阵单位下三角矩阵L、一个、一个对角矩阵对角矩阵D和一个和一个单位下三角矩阵单位下三角矩阵U的乘积形式。的乘积形式。 ALDU3 32 2 稀疏技术稀疏技术三、利用系数矩阵因子表求解稀疏线性代数方程组三、利用系数矩阵因子表求解稀疏线性代数方程组 对对n维线性代数方程组：维线性代数方程组：bAx

23、LDUA bLz zDy yUx 1.1.前代运算前代运算 将将L L分解成一个分解成一个单位矩阵单位矩阵和一个和一个严格下三角矩阵严格下三角矩阵 之和之和LbLz 11niiizlbzLbz11,22,2, 311 ,1 , 31 , 23213211,2,1 ,2, 31 , 31 , 2321321000000000nnnnnnnnnnnnnzlzllzlllbbbbzzzzllllllbbbbzzzz先求先求z z1 1，再求，再求 z z2 2 ，.，最后求最后求z zn n。3 32 2 稀疏技术稀疏技术2.2.除法运算除法运算zDy iiiidzy/3 32 2 稀疏技术稀疏技术

24、3.3.回代运算：将回代运算：将U U分解为一个分解为一个单位矩阵单位矩阵和一个和一个严格上严格上三角矩阵三角矩阵 之和之和UyUx xUyxnnnnnnnnnnnnxxxxuuuuuuuuyyyyxxxx121, 1, 21, 23 , 2, 11, 113121211210000nnnnnnnnnnnnnnxuuuxuuuxuuxuyyyyxxxx00000000, 1,2, 111,21,21, 132313212121121先求先求x xn n，.，最后求，最后求x x1 1节点编号优化节点编号优化 3.3 稀疏矩阵的图论描述 在电力网络分析中，在电力网络分析中，稀疏线性代数方程组的系

25、数矩阵的稀疏线性代数方程组的系数矩阵的稀疏结构和电力网络的拓扑结构相对应稀疏结构和电力网络的拓扑结构相对应。节点导纳矩阵的非节点导纳矩阵的非对角非零元素和电力网络的串联支路有一一对应的关系对角非零元素和电力网络的串联支路有一一对应的关系，导，导纳矩阵的稀疏结构可以用图来描述。稀疏矩阵的因子表的稀纳矩阵的稀疏结构可以用图来描述。稀疏矩阵的因子表的稀疏结构也可以用图来描述。在因子分解的过程中，矩阵的稀疏结构也可以用图来描述。在因子分解的过程中，矩阵的稀疏结构将发生变化，相应的图的结构也将发生变化。本节内疏结构将发生变化，相应的图的结构也将发生变化。本节内容就是利用网络图对稀疏矩阵的因子分解和稀疏矢

26、量的前代容就是利用网络图对稀疏矩阵的因子分解和稀疏矢量的前代回代过程进行分析。回代过程进行分析。 电网电网矩阵（计算，变换矩阵（计算，变换) 矩阵矩阵网络拓扑网络拓扑1 基本定义和术语 假设假设Ax=bAx=b中，中，A A是对称的稀疏矩阵是对称的稀疏矩阵(3-11)(3-11)，b b是独立矢量，是独立矢量，x x是是解矢量。将解矢量。将A A分解成因子表分解成因子表(3-12)(3-12)，则，则A=UTDU （式（式1）。 下面给出几个定义：下面给出几个定义： A A图图：是和矩阵：是和矩阵A A有相同拓扑关系的网络图。有相同拓扑关系的网络图。（图（图3.1a3.1a） 有向有向A A图

27、图：是在给定的：是在给定的A A图上，对于给定的节点编号，图上，对于给定的节点编号， 规定每条边的正方向都是由小号节点指向大号节点，形成的规定每条边的正方向都是由小号节点指向大号节点，形成的有向图。有向图。（图（图3.1b3.1b） 赋权有向赋权有向A A图图：在有向：在有向A A图上，将图上，将A A的非对角非零元素所对的非对角非零元素所对应的边称为互边，并将该边的边权赋之以该非零元素的值；应的边称为互边，并将该边的边权赋之以该非零元素的值；将将A A的对角元素用接地边模拟，称为自边，赋以该对角元素的的对角元素用接地边模拟，称为自边，赋以该对角元素的值。这样即得到赋权有向值。这样即得到赋权有

28、向A A图，它保存了矩阵图，它保存了矩阵A A中的所有信息。中的所有信息。（图（图3.1c3.1c） 按同样的方式可以来描述因子表按同样的方式可以来描述因子表U U。（。（见书见书57575858页页）转到3.52.因子分解过程的图论描述 将对称矩阵将对称矩阵A A因子分解就是要将因子分解就是要将（311）式的矩阵式的矩阵A A分解成分解成（3 31212）式的矩阵式的矩阵U U和和D D， D D是对角线矩阵，并使是对角线矩阵，并使A=UTDU 。在。在图上，就是要将赋权有向图上，就是要将赋权有向A A图变成赋权有向因子图。因子分解的图变成赋权有向因子图。因子分解的过程按照节点号由小到大的顺

29、序依次进行，每步计算包括了规格过程按照节点号由小到大的顺序依次进行，每步计算包括了规格化运算和消去运算两个步骤。化运算和消去运算两个步骤。也就是将第也就是将第4949页上的计算流程在图上实现。页上的计算流程在图上实现。 （1 1）规格化运算）规格化运算（图3.3） 由于由于A A是对称矩阵，当需要对是对称矩阵，当需要对A A的第的第p p行元素进行规格化计算行元素进行规格化计算时，只需要对时，只需要对A A 矩阵中上三角部分中的第矩阵中上三角部分中的第p p行非零元素进行。如行非零元素进行。如图，因子分解过程进行到第图，因子分解过程进行到第p p步时，需要规格化的三个元素的列步时，需要规格化的

30、三个元素的列号分别是号分别是j j，k k，l l。规格化运算的公式为。规格化运算的公式为: :api = api/app pi, i=j, k, l pi, i=j, k, l （式（式2 2） 这在赋权有向这在赋权有向A A图上，图上，相当于对节点相当于对节点p p发出的所有互边的边发出的所有互边的边权加以修正，新的边权等于原边权除以节点权加以修正，新的边权等于原边权除以节点p p的自边边权。的自边边权。这种这种操作只改变节点操作只改变节点p p发出的互边边权，边数并未增加。发出的互边边权，边数并未增加。 （2 2）消去运算）消去运算 (图3.4) 取第取第p p行第行第p p列为轴线，第

31、列为轴线，第p p步的消去运算实际上就是步的消去运算实际上就是要对处于轴线上的要对处于轴线上的非零元素非零元素所在的行列相交叉的位置上的所在的行列相交叉的位置上的元素进行消去运算。如图，需要对处于第元素进行消去运算。如图，需要对处于第p p行第行第p p列上的非列上的非零元素所在的零元素所在的j j，k k，l l行和行和j j，k k，l l列相交叉的位置上的共列相交叉的位置上的共9 9个元素进行消去运算。如果只保留上三角矩阵，只需要对个元素进行消去运算。如果只保留上三角矩阵，只需要对三个对角元素和三个非对角元素进行消去运算。三个对角元素和三个非对角元素进行消去运算。 对对角元素的修正公式是

32、对对角元素的修正公式是 aii = aii - aipapi pi, i=j, k, l （式（式3） 因为在消去运算之前已经对因为在消去运算之前已经对api进行过规格化运算，而式中进行过规格化运算，而式中的的aip还没有进行过规格化，而还没有进行过规格化，而 aip = apiapp 因此使用上三角元素计算时，消去运算的公式应该用因此使用上三角元素计算时，消去运算的公式应该用下式：下式： aii = aii api2app pi, i=j, k, l （式（式4） 在赋权有向在赋权有向A图上，就是对节点图上，就是对节点p发出的边的收点发出的边的收点j, k, l上的自边边权进行修正，边权减少

33、上的自边边权进行修正，边权减少api2app。 对于上三角部分的非零元素，共有三个需要修正，即对于上三角部分的非零元素，共有三个需要修正，即a ajk jk, , a akl kl, , a ajl jl, , 如图如图3.43.4。对于非对角元素，消去运算的公式为：。对于非对角元素，消去运算的公式为： a aim im = = a aim im a aip ipa apm pm im, pi, pmim, pi, pm i, m i, m从从j, k, lj, k, l中取值中取值 （式（式5 5） 因为只储存因为只储存A A的上三角部分，所以的上三角部分，所以a aip ip（下三角元素）

34、应该用（下三角元素）应该用a api pi代替，上述公式变为：代替，上述公式变为： a aim im = = a aim im a api pia apmpma apppp im, pi, pmim, pi, pi/ ji，说明边是由小号节点指向大号节点，说明边是由小号节点指向大号节点 if uif uij ij0 0 then / uij0 / uij0 ，说明是上三角矩阵，说明是上三角矩阵U U中的非零元素中的非零元素 zj=zj-uijzi end if end loop 将这段程序和赋权有向因子图连系起来看，将这段程序和赋权有向因子图连系起来看， u uij ij0 0 就表示赋权就表

35、示赋权有向因子图上节点有向因子图上节点i i，j j之间有边；之间有边； u uij ij0 0，则图上不出现边。，则图上不出现边。 把把z zi i 定义为赋权有向因子图上的点位，用定义为赋权有向因子图上的点位，用e ei i 表示；赋权有向因表示；赋权有向因子图上的互边的边权是子图上的互边的边权是u uij ij，则上面的程序可以写成：，则上面的程序可以写成： ej = ej - uij ei ij, ji ij, ji （式（式7 7） 线性代数方程组中独立矢量或解矢量中的非零元素可以用赋线性代数方程组中独立矢量或解矢量中的非零元素可以用赋权有向因子图上节点的点位来描述，而前代过程可在赋

36、权有向因权有向因子图上节点的点位来描述，而前代过程可在赋权有向因子图上用点位的变化来描述。首先，在赋权有向因子图上，将每子图上用点位的变化来描述。首先，在赋权有向因子图上，将每个节点的点位赋值以独立矢量个节点的点位赋值以独立矢量b b中相应的非零元素的值。然后在赋中相应的非零元素的值。然后在赋权有向因子图上按节点号权有向因子图上按节点号i i从小到大顺序（因为是前代）依次按从小到大顺序（因为是前代）依次按（式（式7 7）修正该节点）修正该节点i i发出边的对端节点发出边的对端节点j j的点位，将对端节点的点位，将对端节点j j的点的点位减小位减小u uij ij e ei i 。这一过程一种进

37、行到将所有点都扫描完。如果节点。这一过程一种进行到将所有点都扫描完。如果节点i i的点位为零，说明的点位为零，说明z zi i 为零，上述修正不需要做。这一过程结束后，为零，上述修正不需要做。这一过程结束后，因子图上的点位就是前代的结果。（对照因子图上的点位就是前代的结果。（对照5151页式页式3 36a6a） 2 . 2 . 规格化过程规格化过程 规格化过程的实质是求解规格化过程的实质是求解Dy=z中的中的y y，D是对角元素矩阵，是对角元素矩阵，z在前代过程中已经求出。因此求解在前代过程中已经求出。因此求解y很容易，只需要做除法运算很容易，只需要做除法运算 yi = zi/dii 在赋权有

38、向因子图上，也就是将前代结束后节点在赋权有向因子图上，也就是将前代结束后节点i i的点位的点位e ei i 除除以节点以节点i i的自边边权，即的自边边权，即 （式（式8 8）。）。 3. 3. 回代过程回代过程 令赋权有向因子图上的点位已经是经过前代和规格化后的值。令赋权有向因子图上的点位已经是经过前代和规格化后的值。按节点号按节点号j j从从n n开始，由大到小，对所有指向开始，由大到小，对所有指向j j的边其发端节点的边其发端节点i i的点的点位进行修正（也就是逆着各边的方向），修正公式为：位进行修正（也就是逆着各边的方向），修正公式为： （式（式9 9） 当所有节点的点位都修正完毕，回

39、代过程结束。当所有节点的点位都修正完毕，回代过程结束。 4. 4.总结总结 在图上进行前代回代的计算步骤如下：在图上进行前代回代的计算步骤如下： (1) 将独立矢量将独立矢量b的非零元素赋值为赋权有向因子图上的点位。的非零元素赋值为赋权有向因子图上的点位。 (2) 扫描扫描i从从1到到n-1。用（式用（式7）修正节点）修正节点i发出的边的对端节点发出的边的对端节点j 的点位。的点位。 （3） 对所有节点用（式对所有节点用（式8）对点位进行规格化。）对点位进行规格化。 （4） 扫描扫描j从从n到到2 。对所有指向节点。对所有指向节点j的边的发端节点的边的发端节点i，用，用 （式（式9）修正其点位

40、。）修正其点位。 5. 例题（例题（63页页 ）板书）板书4.不对称稀疏矩阵的图上因子分解 定义（第定义（第6464页）页） 图图3.73.7 图图3.83.8 3.5 3.5 节点编号优化节点编号优化 稀疏技术的核心关键有两点：一是稀疏技术的核心关键有两点：一是排零存储和排零运算排零存储和排零运算，二是二是节点优化编号节点优化编号。 排零存储和排零运算有效地排零存储和排零运算有效地避免对计算结果没有影响的存避免对计算结果没有影响的存储和计算，大大提高程序的计算效力储和计算，大大提高程序的计算效力。 节点的编号顺序对于计算效力的影响也是至关重要的，它节点的编号顺序对于计算效力的影响也是至关重要

41、的，它直接直接影响到矩阵影响到矩阵A A的因于表矩阵的稀疏度的因于表矩阵的稀疏度。严格地说，。严格地说，最最优编号优编号是一个组合优化问题，求其最优解是困难的，但在是一个组合优化问题，求其最优解是困难的，但在实际工程中，有许多实用的实际工程中，有许多实用的次优的编号次优的编号方法得到了广泛的方法得到了广泛的应用。应用。3.5 3.5 节点编号优化节点编号优化 节点编号的优化节点编号的优化: :寻求一种使注入元素数目最少的节点编寻求一种使注入元素数目最少的节点编号方式号方式。为此，可以。为此，可以比较各种不同的节点编号方案在三角比较各种不同的节点编号方案在三角分解中出现的注入元素数目，从中选取注

42、入元素最少的节分解中出现的注入元素数目，从中选取注入元素最少的节点编号方案点编号方案。但这样做需要分析非常多的方案。但这样做需要分析非常多的方案。 例如对仅有例如对仅有5 5个节点的电力网络来说，其编号的可能方案个节点的电力网络来说，其编号的可能方案就有就有5 5！120120个。一般，对个。一般，对n n个节点的电力网络来说，节个节点的电力网络来说，节点编号的可能方案就有点编号的可能方案就有n!n!个，工作量非常大。因此，在实个，工作量非常大。因此，在实际计算工作中往往采取一些简化的方法，求出一个相对的际计算工作中往往采取一些简化的方法，求出一个相对的节点编号优化方案，并不一定追求节点编号优化方案，并不一定追求“最优最优”方案。方案。3.5 3.5 节点编号优化节点编号优化1 1Tinney-1Tinney-1编号方法编号方法 又称为又称为静态接点优化编号方法静态接点优化编号方法: :在编号以前，首先在编号以前，首先统计电统计电力网络各节点的出线度，然后，按出线度