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

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

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

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

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

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

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

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

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

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

10、AVA存储存储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.按行（列）存储格式按行（列）存储格式 按行按行( (列列) )顺序依次存储顺序依次存储A A中的非零

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

13、+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)即是要找的非零元即是要找的非零元a aijij。这种存储方案可以用于存储任意稀疏矩阵，这种存储方案可以用于存储任

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

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

16、置中的位置( (首地首地址址) )；DD存储存储A A的对角元素的值，其检索下标不需要存储的对角元素的值，其检索下标不需要存储. .例：有了有了IUIU表即可知道表即可知道A A的上三角部分第的上三角部分第i i行的非行的非零元的数目：零元的数目：IU(i+1)-IU(i)IU(i+1)-IU(i)。第一行：。第一行： IU(2)-IU(1)IU(2)-IU(1)3 31 12 2。如果要查找如果要查找A A中的上三角第中的上三角第i i行所有非零元行所有非零元素，只要扫描素，只要扫描k k从从IU(i)IU(i)到到IU(i+1)-1IU(i+1)-1即可，即可，JU(k)JU(k)指出了该

17、元素的列号，指出了该元素的列号，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) 存储格式存储格式以按行存储的格式为例来说明。以按行存储的格式为例来说明。这时需要按行存储格式中的三个数组外还需要增加数组：这时需要按行存储格式中的三个数组外还需要增加数组： VAVA按行存储矩阵按行存储矩阵A A中的非零元中的非零元a aijij，共，共个，个， JA JA按行存储矩阵按行存储矩阵A A中非零

20、元的列号，共中非零元的列号，共个，个， IA IA记录记录A A中每行第一个非零元素在中每行第一个非零元素在VAVA中的位置，共中的位置，共n n个。个。 LINK LINK下一个非零元素在下一个非零元素在VAVA中的位置，对每行最后一个非零元中的位置，对每行最后一个非零元素，该值置为素，该值置为0 0。 NA NA每行非零元素的个数。每行非零元素的个数。当新增加一个非零元素时，可把它排当新增加一个非零元素时，可把它排在最后，并根据该非零元素在该行中在最后，并根据该非零元素在该行中的位置的不同来修改其相邻元素的的位置的不同来修改其相邻元素的LINKLINK值例如，新增值例如，新增a a1313

21、，把，把a13排在第排在第1111个位置，把个位置，把a a1212的的LINKLINK值由值由3 3改为改为1111， a13本身的本身的LINKLINK值置为值置为3 3，NA(1)NA(1)增加增加1 1，变为变为4 4。a13111134a1333.2 3.2 稀疏技术稀疏技术二、稀疏矩阵的因子分解二、稀疏矩阵的因子分解对对n n阶矩阵阶矩阵A可以通过可以通过LU分解的方法分解成为一个下三角矩阵分解的方法分解成为一个下三角矩阵L和一和一个单位上三角矩阵个单位上三角矩阵U的乘积：的乘积：ALULU分解分为两步分解分为两步： （1）按行规格化运算；）按行规格化运算； （2）消去运算或更新运

22、算。）消去运算或更新运算。也可以将也可以将A分解成一个单位下三角矩阵分解成一个单位下三角矩阵L、一个对角矩阵、一个对角矩阵D和一个单位和一个单位下三角矩阵下三角矩阵U的乘积形式。的乘积形式。 ALDU3 32 2 稀疏技术稀疏技术三、利用系数矩阵因子表求解稀疏线性代数方程组三、利用系数矩阵因子表求解稀疏线性代数方程组对对n维线性代数方程组：维线性代数方程组：1.1.前代运算前代运算将将L L分解成一个单位矩阵和一个严格下三角矩阵分解成一个单位矩阵和一个严格下三角矩阵 之和之和先求先求z z1 1，再求，再求 z z2 2 ，.，最，最后求后求z zn n。3 32 2 稀疏技术稀疏技术2.2.

23、除法运算除法运算3 32 2 稀疏技术稀疏技术3.3.回代运算：将回代运算：将U U分解为一个单位矩阵和一个严格上三角矩阵分解为一个单位矩阵和一个严格上三角矩阵 之和之和先求先求x xn n，.，最后求，最后求x x1 1节点编号优化节点编号优化 3.3 稀疏矩阵的图论描述 在电力网络分析中，稀疏线性代数方程组的系数矩阵的稀疏结构和电在电力网络分析中，稀疏线性代数方程组的系数矩阵的稀疏结构和电力网络的拓扑结构相对应。节点导纳矩阵的非对角非零元素和电力网络的力网络的拓扑结构相对应。节点导纳矩阵的非对角非零元素和电力网络的串联支路有一一对应的关系，导纳矩阵的稀疏结构可以用图来描述。稀疏串联支路有一

24、一对应的关系，导纳矩阵的稀疏结构可以用图来描述。稀疏矩阵的因子表的稀疏结构也可以用图来描述。在因子分解的过程中，矩阵矩阵的因子表的稀疏结构也可以用图来描述。在因子分解的过程中，矩阵的稀疏结构将发生变化，相应的图的结构也将发生变化。本节内容就是利的稀疏结构将发生变化，相应的图的结构也将发生变化。本节内容就是利用网络图对稀疏矩阵的因子分解和稀疏矢量的前代回代过程进行分析。用网络图对稀疏矩阵的因子分解和稀疏矢量的前代回代过程进行分析。 电网电网矩阵（计算，变换矩阵（计算，变换) 矩阵矩阵网络拓扑网络拓扑1 基本定义和术语假设假设Ax=bAx=b中，中，A A是对称的稀疏矩阵是对称的稀疏矩阵( (3-

25、113-11) )，b b是独立矢量，是独立矢量，x x是解矢量。是解矢量。将将A A分解成因子表分解成因子表( (3-123-12) )，则，则A=UTDU （式（式1）。下面给出几个定义：下面给出几个定义： A A图：是和矩阵图：是和矩阵A A有相同拓扑关系的网络图。有相同拓扑关系的网络图。（图图） 有向有向A A图：是在给定的图：是在给定的A A图上，对于给定的节点编号，图上，对于给定的节点编号， 规定规定每条边的正方向都是由小号节点指向大号节点，形成的有向图。每条边的正方向都是由小号节点指向大号节点，形成的有向图。（图（图） 赋权有向赋权有向A A图：在有向图：在有向A A图上，将图上

26、，将A A的非对角非零元素所对应的边的非对角非零元素所对应的边称为互边，并将该边的边权赋之以该非零元素的值；将称为互边，并将该边的边权赋之以该非零元素的值；将A A的对角元的对角元素用接地边模拟，称为自边，赋以该对角元素的值。这样即得到赋素用接地边模拟，称为自边，赋以该对角元素的值。这样即得到赋权有向权有向A A图，它保存了矩阵图，它保存了矩阵A A中的所有信息。中的所有信息。（图）图） 按同样的方式可以来描述因子表按同样的方式可以来描述因子表U U。（。（见书见书57575858页页）转到2.因子分解过程的图论描述 将对称矩阵将对称矩阵A A因子分解就是要将因子分解就是要将（311）式的矩阵

27、式的矩阵A A分解成分解成（3 31212）式式的矩阵的矩阵U U和和D D， D D是对角线矩阵，并使是对角线矩阵，并使A=UTDU 。在图上，就是要将赋权有。在图上，就是要将赋权有向向A A图变成赋权有向因子图。因子分解的过程按照节点号由小到大的顺序依次图变成赋权有向因子图。因子分解的过程按照节点号由小到大的顺序依次进行，每步计算包括了规格化运算和消去运算两个步骤。进行，每步计算包括了规格化运算和消去运算两个步骤。也就是将第也就是将第4949页上的计页上的计算流程在图上实现。算流程在图上实现。 （1 1）规格化运算）规格化运算（图） 由于由于A A是对称矩阵，当需要对是对称矩阵，当需要对A

28、 A的第的第p p行元素进行规格化计算时，只行元素进行规格化计算时，只需要对需要对A A 矩阵中上三角部分中的第矩阵中上三角部分中的第p p行非零元素进行。如图，因子分解行非零元素进行。如图，因子分解过程进行到第过程进行到第p p步时，需要规格化的三个元素的列号分别是步时，需要规格化的三个元素的列号分别是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发出的所有互边的边权加以修正，发出的所有互边的边权加

29、以修正，新的边权等于原边权除以节点新的边权等于原边权除以节点p p的自边边权。这种操作只改变节点的自边边权。这种操作只改变节点p p发出的发出的互边边权，边数并未增加。互边边权，边数并未增加。 （2 2）消去运算）消去运算 (图) 取第取第p p行第行第p p列为轴线，第列为轴线，第p p步的消去运算实际上就是要对处步的消去运算实际上就是要对处于轴线上的于轴线上的非零元素非零元素所在的行列相交叉的位置上的元素进行消去运所在的行列相交叉的位置上的元素进行消去运算。如图，需要对处于第算。如图，需要对处于第p p行第行第p p列上的非零元素所在的列上的非零元素所在的j j，k k，l l行和行和j

30、j，k k，l l列相交叉的位置上的共列相交叉的位置上的共9 9个元素进行消去运算。如果只保留上三角矩个元素进行消去运算。如果只保留上三角矩阵，只需要对三个对角元素和三个非对角元素进行消去运算。阵，只需要对三个对角元素和三个非对角元素进行消去运算。 对对角元素的修正公式是对对角元素的修正公式是 aii = aii - aipapi pi, i=j, k, l （式（式3） 因为在消去运算之前已经对因为在消去运算之前已经对api进行过规格化运算，而式中的进行过规格化运算，而式中的aip还没有进行过规格化，而还没有进行过规格化，而 aip = apiapp 因此使用上三角元素计算时，消去运算的公式

31、应该用下式：因此使用上三角元素计算时，消去运算的公式应该用下式： aii = aii api2app pi, i=j, k, l （式（式4） 在赋权有向在赋权有向A图上，就是对节点图上，就是对节点p发出的边的收点发出的边的收点j, k, l上上的自边边权进行修正，边权减少的自边边权进行修正，边权减少api2app。 对于上三角部分的非零元素，共有三个需要修正，即对于上三角部分的非零元素，共有三个需要修正，即a ajk jk, , a akl kl, , a ajl jl, , 如图。如图。对于非对角元素，消去运算的公式为：对于非对角元素，消去运算的公式为： a aim im = = a ai

32、m 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（下三角元素）应该用（下三角元素）应该用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 / ui

33、j0 / uij0 ，说明是上三角矩阵，说明是上三角矩阵U U中的非零元素中的非零元素 zj=zj-uijzi end if end loop 将这段程序和赋权有向因子图连系起来看，将这段程序和赋权有向因子图连系起来看， u uij ij0 0 就表示赋权有向因就表示赋权有向因子图上节点子图上节点i i，j j之间有边；之间有边； u uij ij0 0，则图上不出现边。，则图上不出现边。 把把z zi i 定义为赋权有向因子图上的点位，用定义为赋权有向因子图上的点位，用e ei i 表示；赋权有向因子图上的互表示；赋权有向因子图上的互边的边权是边的边权是u uij ij，则上面的程序可以写成

34、：，则上面的程序可以写成： ej = ej - uij ei ij, ji ij, ji （式（式7 7） 线性代数方程组中独立矢量或解矢量中的非零元素可以用赋权有向因子图上线性代数方程组中独立矢量或解矢量中的非零元素可以用赋权有向因子图上节点的点位来描述，而前代过程可在赋权有向因子图上用点位的变化来描述。节点的点位来描述，而前代过程可在赋权有向因子图上用点位的变化来描述。首先，在赋权有向因子图上，将每个节点的点位赋值以独立矢量首先，在赋权有向因子图上，将每个节点的点位赋值以独立矢量b b中相应的非零中相应的非零元素的值。然后在赋权有向因子图上按节点号元素的值。然后在赋权有向因子图上按节点号i

35、 i从小到大顺序（因为是前代）依从小到大顺序（因为是前代）依次按（式次按（式7 7）修正该节点）修正该节点i i发出边的对端节点发出边的对端节点j j的点位，将对端节点的点位，将对端节点j j的点位减小的点位减小u uij ij e ei i 。这一过程一种进行到将所有点都扫描完。如果节点这一过程一种进行到将所有点都扫描完。如果节点i i的点位为零，说明的点位为零，说明z zi i 为零，为零，上述修正不需要做。这一过程结束后，因子图上的点位就是前代的结果。（对上述修正不需要做。这一过程结束后，因子图上的点位就是前代的结果。（对照照5151页式页式3 36a6a） 2 . 2 . 规格化过程规

36、格化过程 规格化过程的实质是求解规格化过程的实质是求解Dy=z中的中的y y，D是对角元素矩阵，是对角元素矩阵，z在前代过程在前代过程中已经求出。因此求解中已经求出。因此求解y很容易，只需要做除法运算很容易，只需要做除法运算 yi = zi/dii 在赋权有向因子图上，也就是将前代结束后节点在赋权有向因子图上，也就是将前代结束后节点i i的点位的点位e ei i 除以节点除以节点i i的自的自边边权，即边边权，即 （式（式8 8）。）。 3. 3. 回代过程回代过程 令赋权有向因子图上的点位已经是经过前代和规格化后的值。按节点号令赋权有向因子图上的点位已经是经过前代和规格化后的值。按节点号j

37、j从从n n开始，由大到小，对所有指向开始，由大到小，对所有指向j j的边其发端节点的边其发端节点i i的点位进行修正（也就是逆着的点位进行修正（也就是逆着各边的方向），修正公式为：各边的方向），修正公式为： （式（式9 9） 当所有节点的点位都修正完毕，回代过程结束。当所有节点的点位都修正完毕，回代过程结束。 4. 4.总结总结 在图上进行前代回代的计算步骤如下：在图上进行前代回代的计算步骤如下： (1) 将独立矢量将独立矢量b的非零元素赋值为赋权有向因子图上的点位。的非零元素赋值为赋权有向因子图上的点位。 (2) 扫描扫描i从从1到到n-1。用（式用（式7）修正节点）修正节点i发出的边的对端节点发出的边的对端节点j 的点位。的点位。 （3） 对所有节点用（式对所有节点用（式8）对点位进行规格化。）对点位进行规格化。 （4） 扫描扫描j从从n到到2 。对所有指向节点。对所有指向节点j的边的发端节点的边的发端节点i，用，用 （式（式9）修正其点位。）修正其点位。 5. 例题（例题（63页页 ）板书）板书4.不对称稀疏矩阵的图上因子分解 定义（第定义（第6464页）页） 图图 图图 3.5 3.5 节点编号优化节点编号优化