第三章稀疏技术的应用.doc

第三章 稀疏技术的应用第一节 节点导纳矩阵及其稀疏存储一、 节点导纳矩阵 节点导纳矩阵Y是电力网络的一种数学模型。它描述网络的连接情况和支路的导纳值，广泛用于电力系统的潮流计算。包含网络中所有节点的导纳矩阵称为全节点导纳矩阵。电力系统计算用的导纳矩阵通常是不完全的，是从完整的全节点导纳矩阵中除去对应参考点的行和列形成的。 如图3.1简单网络，若将中性点（地）记为0号节点，则网络的全节点导纳矩阵为44矩阵。 (3-1)显然是奇异矩阵。它各行（列）的所有元素之和为零，即其行列式值为零。应用于网络方程为 这里是所有节点(包括0号节点)注入电流的列向量。按照克希荷夫第一(电流)定律,应有，即他们是相关的。其中任意一个必为其余各个电流元素之和的负值。 是节点电压列向量,是各节点相对于某一共同参考点的电压(电位差)。若已知，则可求。反之，给定时，因是奇异阵，其逆不存在，故没有唯一解。从电路关系上看，只要各节点电压差保持一定关系，各节点电压数值可因选取的参考点不同而共同浮动，亦即可有无穷多解。12 y12 y13y233y20y10图3.1 简单网络 为了便于计算，选取其中任一节点作为参考点，通常取此节点电压为零，其余各节点电压均为该节点对此参考点的电压（电位差）。参考点电压为零，其电流又可由其他节点注入电流之和求得，所以可将中对应参考点的列和行删去，免去与之有关的计算。习惯上，一般取中性点（地）为参考点，即零电位点。删去相应的列和行，形成通常的节点导纳矩阵。 （3-2） 有时某个网络或某种计算中，需要改变参考点，例如将节点r取代地作为参考点，则先恢复原来完整的全节点导纳矩阵，再删去新的参考点r对应的行和列。即可获得新的对应节点r为参考点的节点导纳矩阵。以此导纳矩阵作网络方程计算时，要注意所用的节点电压是各节点对新参考点的电压，而不是原来的对地电压。例如，原来是以地为参考点时，由网络方程可解得某节点的注入电流 而当改以r节点为参考点时，由网络方程可得： 式中为以r节点为参考点时的节点电压。它与原来以地为参考点时的电压关系为 由这二个方程求得的注入电流应该是相同的。将的值代入。得 但 从而 说明两种算法的结果是一致的。 若计算所用网络没有接地支路，是所谓“悬浮”网络，Y就是全节点导纳矩阵，是奇异矩阵。求解此网络时，应改选另一适当的节点为参考点，形成新的节点导纳矩阵。这个矩阵不包括与r节点对应的行和列，即这时比Y少一阶。应该注意的是，运算用的电压是各节点对参考点的电压。但一般电力系统要求的是各节点的对地电压，所以在计算完后，还应将求得的电压加上参考点的对地电压。观察式（3-2）的导纳矩阵Y，当图3.1任意两节点间有支路直接相连，相应的对称的元素为 即导纳矩阵是对称的。自然，若任意两节点间没有支路直接相连，相应的对称的元素都为零，即导纳矩阵非对角非零元素数应等于网络支路数的两倍，以矩阵上（或下）三角而言，则其非对角非零元素数正好等于网络的支路数。实际上，电力系统网络各节点往往只与其中几个节点有支路相连，而与其余大部分节点无联系，因而导纳矩阵有许多零元素，是很稀疏的。如果网络中具有非标准变化的变压器支路，例如间为非标准变比变压器支路时，其等值电路可有如图3.2（a）和(b)两种。其中为变压器导纳值。ijij 图3.2 变压器等值电路 （a） （b）对应图3.2（a）中电路，有 (3-3)式中和分别为支路i-j对i和j节点自导纳的增量。对应图3.2（b）等值电路，有 (3-4) 有些网络还装有改变线路两端电压（电流）相角的移相器，移相器的等值电路示于图3.3。图中为移相器导纳，为移相器所移动的相角，即 i j 图3.3 移相器的等值电路 据此可求得导纳矩阵各有关元素为 (3-5)由上式可知，移相器的存在并不影响对角元素，但影响非对角元素，使，破坏了导纳矩阵的对称性。通常移相器较少，计算时可将它单独处理。不考虑移相器时，网络仍然是对称的。有些变压器既能改变电压又能改变相角，此时可将式（3-3）或式（3-4）与式（3-5）结合计算，不再赘述。导纳矩阵对应于网络支路的联接状况，当支路联接状况改变时，例如断开某一支路，并入某一支路或者改变线路参数等，导纳矩阵也就相应改变。但这种改变只涉及与变化支路有关的元素，即两个对角元素与两个非对角元素。如支路的改变只改变和、四个元素，其他元素不变。这正是用节点导纳矩阵描述网络的方便之处。二、导纳矩阵的形成 当网络给定时，节点导纳矩阵很容易形成，比较式（3-2）和图3-1可知，节点导纳的阶数等于网络的节点数（不包括参考节点）。矩阵的对角元素即自导纳等于与该节点连接的所有支路的导纳之和，非对角元素即互导纳则为连接两点支路导纳的负值。 电力网络一般由输电线路和变压器等元件组成。当元件的等值电路已知时，则由这些元件组成的网络可知，从而可形成该网络的节点导纳矩阵。 b/2 b/2 图3.4 输电线路的等值电路 r、x电力系统输电线路的等值电路如图3.4所示。其中r、x为线路串联电阻、电抗，b/2为线路容纳，据此可得 (3-6) 变压器支路的等值电路已示于图3.2。当变压器绕组电阻（常可忽略），漏抗及变比给定时，用（a）所示的等值电路，有 (3-7)5134 图3.5 6个节点的网络26 无论按式（3-6）还是按式（3-7）计算，都需知道支路的五个参数i、j、r、x、b/2(或)， 输入全部支路的这些参数可以形成网络的节点导纳矩阵。由于计算公式不同，需要区分是输电线支路还是变压器支路。区别方式可由程序设计者自定。例如，在变压器支路两端对一个节点号前，人为增加一个负号，就可以简单地将变压器支路与输电支路区别开来。由于变压器支路对两端节点自导纳的作用不同。应该限定负号加在某一侧。这里规定负号加在图3.2（a）的漏抗侧。如图3.5网络。这是6个节点的网络，网络节点数n=6，支路数l=7，支路参数如表3-1所示。 表3-1 6个节点网络的支路参数ijrxb/2( 或K )-1223242534545-6 输入支路参数 L F 判断支路类型 判断标准侧 按输电线支路计算 按变压器支路计算 N 最后支路？ END 图3.6 形成网络节点导纳矩阵框图读者可按自己熟悉的计算机语言编写程序。这样形成的节点导纳矩阵，各元素与一个二维数组一一对应。这种存储方式称为满阵存储,特点是程序设计简单、使用方便、支路参数不必按支路顺序读入，适用于节点少的网络。由于矩阵是对称的，而且对于较多节点的电力网络，矩阵中必然存在许多零元素。显然，这种存储方式占用许多不必要的计算机容量。因此应该采用稀疏存储方式。三、导纳矩阵的稀疏存储根据节点导纳稀疏、对称的特点，为了节省计算机内存容量和较少计算机工作量，免除零元素的存储和运算，应只存储非零元素。这种存储方式叫做稀疏存储方式。稀疏存储方式很多，根据矩阵的对称性，下面以只存上三角元素为例介绍几种用一维数组存储的方式。方式1. 设有一维数组DY，Y，IY，JY，将对角元素存于DY数组中，即，也就是说，。将非对角元素存在于Y数组中，各元素的行号和列号分别存在于用以识别的IY和JY数组中，即 其意义为，若网络第k支路两端点为i、j，即矩阵上三角部分的第k个非零元素位于第i行第j列，则有，这样就将矩阵各元素的值和行号i,列号j分别存于各数组的对应位置。虽然，对每一组、i和j来说iN，若认为L=1.5N，则共需2N+4L=8N个内存单元。这种方式也称为散居格式。方式2. DY，Y和JY各数组含义与前相同，但Y中各元素按一定规律排列。设按行顺序排列，因而也称为按行格式。另设IS数组，它存的是各行第一个非对角非零元素在Y中的位置号，即： 第一行 第二行 第i行 个元素 个元素 个元素 这里是第i行非对角非零元素个数。IS共有n个元素，分别是 （3-8） 显然IS（l）=1。第n行没有非对角元素，IS（n）没有实际意义。为便于程序处理，仍令IS（n）等于式（3-9）的计算结果，即 采用这种方式时，导纳矩阵第i行共有IS（i+1）-IS(i)个非对角非零元素。它们在Y中的排列是从第IS(i)个至第IS(i+1)-1个。有时，某一行i可能没有非对角非零元素，则由式（3-8）知IS（i+1）必等于IS（i）。反过来，如IS(i+1)-IS(i)=0，则可判断出第i行没有非对角非零元素。 这种方式占用内存单元为3N+3L=7.5N个。也可采用IS数组存末元素地址，或直接存每行非对角非零元素个数的方式。这时查找元素要采用与之相应的办法。方式3. DY、Y数组的含义同前，用KY数组来表示出数组Y中上三角（不计对角元素）元素实际位置的顺序号。如已知，它在上三角位置的序号为 （3-9）也就是在数组KY的对应位置存入的值，即 或表示为 ， 这种方式所占有内存单元数为N+2L=4N个 仍以图3.5为例，分别用上面三种方式存储时，各数组的存储数值示于表3-2。由于三种方式Y、DY存储的内容相同，将之列在表的左边。 三种存储方式中，方式1所占内存略多，方式3占用内存较少。考虑到导纳值为复数，在本例中，如果采用满阵方式存储需用662=72个内存单元，而方式1需用内存单元为表3-2 三种存储方式比较DYY方式1方式2方式31Y1YJYISKY212113232642457525684347105457136561562+72+7+7=40个；方式2为39个；方式3为33个。可见在本例中满矩阵方式与稀疏方式占用单元之比约2：1。这是小网络，稀疏存储的优点还不突出。如果对一个节点数为100、支路数为150的中型电力系统，则采用满矩阵存储时需用20000个存储单元，而用方式1时仅占用800个存储单元。二者的比值为2000：800=25：1。稀疏存储方式大大节省了计算机的存储单元。当占用内存相差不大时，实际应用就应考虑各方式灵活性和方便性。方式3占用内存最少，但求解时处理复杂。处理复杂本身也就增加了内存量和计算工作量，还增加了程序设计的困难。通常，方式2对程序处理较为灵便，应用较多。但若支路连接情况使非零元素变为零元素，或者相反，方式2的非零元素序号排列顺序几乎要全部发生变化，调整比较复杂。其他如方式1并不要求非零元素按某种顺序排列，因而在网络发生变化时调整要简单得多。现代的适合大规模运算的程序为了数据的存取调整方便，常使用链表等方式存储，读者可根据自己工作的需要自行学习。不同的存储方式其程序实现方法和运算方法不同。读者可以根据自己熟悉的语言编写按不同稀疏存储方式的形成节点导纳矩阵的源程序。应该说明的是，编制程序的方法、技巧很多，运用自己的知识，编写的程序方便存取，简便实用就是最佳的。 第二节 稀疏向量求解法在求解线性代数方程式（2-1）时，可能出现两种稀疏向量。其一，方程组右端项是稀疏的列向量，即I中只有若干个非零元素，其他为零元素。例如右端项只有、行分别有非零元素和，其余为零元素。其二，又如只需求解未知向量V中的若干个元素，无需求解所有的量，即要求的解是稀疏的列向量。导纳矩阵Y的逆矩阵是阻抗矩阵Z。如果只要求解节点的自阻抗，可以在节点注入单位电流，其他节点的注入电流为零，则节点的电压即为。为求，可令式（2-1）的注入电流向量I为 （3-10）利用因子表进行前回代，求出节点的电压，则 上例中式(2-1)的右端项是稀疏的式(3-10)，求解的向量也是稀疏的，即只求，其余的可以不算，这是最典型的应用稀疏向量算法的例子。电力系统分析中可以应用稀疏向量算法的例子很多。例如用补偿法计算节点、间的支路断开时的潮流，需要求出从断口、间看进去的网络内阻抗。这时可以在节点、分别注入电流+1和-1，求、间的电压差，则内阻抗为 又如计算节点的三相短路电流，需要求解。以上这些例子若能充分利用矩阵的稀疏性进行求解，就可以大大节省计算时间。稀疏向量求解法首先是要识别快速前代运算和回代运算所必须的运算，找出前代运算和回代运算的因子表路径，避免与求解无关的运算。一、 前代因子表路径的确定利用稀疏性提高计算速度的途径之一是避免零元素的运算。以右端项为稀疏向量的前代运算为例，由式(2-17)得 令 则 (3-11) 前代运算是求解上列N个方程，求出 由于下三角阵L和方程右端项I是稀疏的，在式(3-11)中，如果满足条件 (3-12) 或 (3-13)则无需求解式(3-11)就可以肯定 (3-14)因为如果式(2-1)是非奇异方程组，则有 在前代过程中，如果满足式(3-12)和式(3-13)，从而也满足式(3-14)的方程，定义为无效方程，是快速前代过程中无需运算的方程。与此相反，不能完全满足式(3-12)和式(3-13)两个条件的方程定义为有效方程，即这些方程需要进行非零运算才能求出。快速前代运算只对有效方程运算即可。4110919141318875620161715113212（a） 系统接线图15101520 5 10 15 20（b）Y矩阵及因子表结构图 3.7 20节点网络示例图如果定义为有效方程的子集，由上面分析可知，无效方程是没有非零运算的方程，即有 有效方程的解（，）可能不等于零。现以20个节点的网络为例，该网络接线如图3.7(a)所示，节点优化后的编号标于图中，因子表的矩阵结构示于图3.7(b)中。图中“*”表示原导纳阵的非零元素，“”表示形成因子表后增加的非零元素。从图可以看出L、D、U矩阵的结构和非零元素的位置。由于网络的导纳阵是对称的，故L和U有相似的结构。当然如果待求解的方程是有解的，L、D、U的逆是存在的。确定因子表前代路径，直观的做法是利用下三角阵L，对稀疏的右端项进行前代运算，即 （3-15）寻找具有非零运算的有效方程不能用这种方法，因为这样搜索太费时间了。先讨论右端项的稀疏向量只有一个非零元素的前代因子表路径。假定图3.7(a)中节点2有电流注入，其他节点的注入电流为零，即 （3-16）现在讨论快速前代有效方程的确定方法。（1）因为，故前代结果。可以这样推理，若右端项第一个非零元素在第行，则 (2) 因为，故L中第二行是有效方程，简称第2方程是有效方程，可求得 检查L矩阵的第2列，有非零非对角元素、即有 的非零运算，故L矩阵中第11、20两方程为有效方程。可以认为 （3）因为，故得，L矩阵中第3方程为无效方程。由于L中第2列向量第一个非零，非对角元素是第11行，可以推理 (4) 由于，L矩阵中第11列有非零非对角元素、即有 的非零运算，故第11、20方程有效方程。可以认为 （5）由于，L矩阵中第12列有非零非对角元素、即有 的非零运算。故第15、20方程是有效方程。可以认为 （6）由于，L矩阵中第15列有非零非对角元素、即有 的非零运算。故第17、18、20方程是有效方程。可以认为 （7）由于，L矩阵中第17列有非零非对角元素、即有 的非零运算。故第17、18、20方程是有效方程。可以认为 （8）由于有 和有 故有 第13、14方程为无效方程。同理，由于 故 第16方程是无效方程。总结上述前代有效方程与有效方程所在列的非零非对角元素之间的关系如表3-3所示。表3-3列 号该列非零非对角元素的行号有效方程序号211121517181911, 2012, 2015, 2017, 18, 2018, 19, 1019, 202011, 2012, 2015, 2017, 18, 2018, 19, 2019, 202011212从上表看出序号是重复的。实际有效方程的序号为：2、11、12、15、17、18、19、20。其中11、12、15、17、18、19、20分别是下三角矩阵L中第2、11、15、17、18、19列的第一个非对角非零元素。1920181715图3.7 前代因子表路径有效方程确定后，快速前代运算可只在有效方程中进行。如果把有效方程的序号排成顺序，就可以得到一条指导前代进行顺序的前代因子表路径。例如本节讨论的，其他节点注入电流为零的20个节点系统的前代因子表路径如图3.7所示。图中节点的数字标号标明有效方程的序号，顺序是从小到大，用箭头表明前代运算是从方程序号小的方向进行。可以说，有效方程序号的有序排列就形成因子表的运算路径。由以上的讨论可以得出，设右端项非零元素在行，且右端项稀疏向量只有一个非零元素时，则求有效方程序列和前代因子表路径的步骤如下：（1） 第个方程为第一个有效方程，是前代因子表路径的始端；（2） 若L矩阵列的第一个非对角非零元素的行号为，则第个方程是第2个有效方程，是路径的第二个节点；（3） 若L矩阵列的第一个非对角非零元素的行号为，则第个方程是第三个有效方程；（4） 照此类推，若是第个有效方程，L阵中第列第一个非对角非零元素的行号为，则第个方程是第个有效方程。直至找到，第N个方程被确定为有效方程（N是网络阶数），即找到最后一个有效方程。 有20个节点的系统和，以2为始端的前代因子表路径如图3.7所示。这个前代因子表路径的各节点号为有效方程的第一个非对角非零元素的行号。在稀疏矩阵的稀疏存储中，很容易从存储信息中找到每列的第一个非零非对角元素的行号，因而运算中很容易确定前代因子表路径。前代因子表路径的节点数K与右端项稀疏向量非零元素所在行号有关，与L矩阵的稀疏程度有关。值越大、L矩阵稀疏则K值小。一般来说KN，实践证明网络节点数N增大时，K不随N比例增大，或说N增大时，K/N减少，因此大系统的网络沿前代因子表路径进行快速前代运算（FFS）可以大大地节省运算时间，避免无效方程的运算。下面讨论右端项有多个非零元素的前代因子表路径。右端项稀疏向量有多个非零元素是，可以依次假定只有一个非零元素，求出单一非零元素前代因子表路径。右端项有多个非零元素的前代因子表路径，可以是多个单一前代因子表路径的组合。例如在20节点的网络中，右端项稀疏向量为： 共有三个非零元素，可分别对始端方程2、6、12求出前代因子表路径如下：201918176151211216图3.8 前代因子表路径2、6、12 以2为始端的路径（简称路径2）为 2、11、12、15、17、18、19、20 以6为始端的路径为 6、16、17、18、19、20 以12为始端的路径为 12、15、17、18、19、20把三条路径画在同一路径图中，如图3.8所示。前代因子表路径12与路径2重叠，如果后者已经找出，则前者无需重复进行。故寻找右端项稀疏向量有多个非零元素的前代因子表路径时，先从序号小的路径开始。本例应从路径2开始，其后若序号大的前代因子表路径与已有的重合，就可以不算了。例如本例中路径2已包括路径12，故后者可以不算了。始端为6的路径与始端为2的路径有部分重合，在确定路径6时，运算到第三步，确定有效方程的序号17。因序号17同时是路径2的有效方程的序号，表明往后两条路径是重合的，无需重复计算。可以找出全网络的前代因子表路径，20节点系统的全部前代因子表路径如图3.9所示。从中可以找到从任一节点开始的前代因子表路径。201918176151211216图3.9 全网络前代因子表路径1383109141457二、 回代因子表路径的确定回代运算是已知列向量，对上三角阵U进行回代，求出线性方程组的未知量向量。 （3-17）前面已经讲过，稀疏列向量的另一种形式是未知量是一稀疏向量。显然如果研究的问题只需要未知列向量的部分结果，则无需浪费时间去找不必要的量。这与前面讨论的右端项是稀疏列向量时，前代运算只需对前代因子表路径的有效方程进行运算，无需对无效方程进行运算的做法一样。回代运算也可以找出相应的回代因子表路径，只对有效方程进行运算，就可以求出要求的未知量。这种计算方法称快速回代法（FBS）。先讨论只求一个未知量的情况。回代因子表路径的思路是：根据要求出的未知量研究需要进行那些运算。在20个节点的网络图中，要求出因上三角矩阵U中的第二行有两个非零对角元素、。由式(2-26)得 因前代运算的结果是已知的，为求出需要先求出和。所以要求解第11，20两个方程。 与上相似的分析，U矩阵中的11行有二个非零非对角元素、。为要求出需要求解第12、20两个方程，求出和。类似的方法可以推算出需要进行运算的方程序列，也定义为有效方程序列： 2、11、12、15、17、18、19、20以上是按求解的要求，需要进行运算的方程序列。可以看出有效方程与前代因子表路径2的有效方程相同。但回代因子表路径是从20指向2。要求计算多个未知量时，分别求出每一未知量的回代因子表路径组合在一块，就得多个未知量的快速回代因子表路径。20节点网络的回代因子表路径见图3.10。201918176151211216图3.10 20节点系统全部回代因子表路径1383109141457以上讨论了稀疏向量的快速前代、回代算法。沿着因子表路径可以很快地求出稀疏向量解。在因子表的稀疏存储信息中，很容易求得U矩阵中每行或L矩阵中每列第一个非零非对角元素的位置，很容易确定因子表路径。三利用高斯消去L阵的前代因子表路径确定上面以寻找有效方程确定前代因子表，推理严谨，过程分析比较复杂，但结论很清晰。表3-3表明，所谓有效方程在稀疏向量的非零元素确定后，即确定了有效方程的起点，其路径的方向是由小到大从起点到最大点（根节点）。第1组有效方程的序号实际上就是起点所在列非零元素个数，按节点号由小到大的顺序排列。下一组有效方程所在列号就是上一列（即上一组有效方程所在列）的第1个非零元素（最小序号）的行号。依此下行，即可列出表3-3来。表中的第一列就是前代因子表的路径。这一路径实际上可由图3.7（b）直接求出。将图3.7（b）示于下图3.11所示。按照前面所述，在图3.11中先找出起点的对角元素，由起点纵向连结到该列第1个非零元素，然后横向连结该行的对角线元素。这一连接有效地连接了两组有效方程的运算，排除了位于这两个对角元素中间的所有列的无效运算，因而成为“有效短接”。依此进行，直到根节点，可求得图3.11的以粗箭头表示的有效短接图。 15101520 1 5 10 15 20 图3.11 20节点因子表图 将粗箭头连接的对角线节点连结在一起，即得图3.11按式（3-16）稀疏向量注入的快速迭代前代因子表路径如图3.12所示。 同样地，用此方法可以求得多个稀疏注入量的快速迭代前代因子表路径图，或全部因子表路 2径图。它与前面所求得的前代因子路径图完全一 11致。这种方法省去了许多有效运算和无效运算的 12复杂分析过程，因而比之上面所述的方法要简便得多。然而，对一个大型的复杂网络，要先求得 15它的因子表，其工作量也是相当巨大的。 17 18四前代因子表路径确定的图形法 19 我们在前面已经讲述了，因子表是在高斯消 20 去的过程中形成的，而高斯消去等价于网络化简。 图3.12 快速迭代前代因子表我们能否直接对网络图通过网络的等值变换化简 路径图来求得前代因子表的路径？答案应该是肯定的！因为高斯消去生成图3.11的过程，可以对图3.7（a）的系统接线图通过网络化简来重现。只要在等值变换去除的节点及支路时，保留其节点和与之相连的支路中的某一条支路，该支路的对端节点号在与之相连支路中编号最小。仍以图3.7（a）的20节点系统接线图为例，见图3.13所示。 4 10 9 1 18 14 19 13 8 7 6 5 15 17 16 20 3 12 11 2 图3.13 20节点系统接线图高斯消去是按节点的编号由小到大消去。因此，网络化简也按此顺序进行。先消去节点1，则等值变换是在节点1连接支路1-9及支路1-13的对端节点9到13之间，新增一条支路；则节点1所连接的支路全部去除，只保留节点1与对端节点号最小的支路。本次消去，对端节点号最小是9，则保留支路1-9，改为虚线，以示该支路不参与后面的消去过程。同理对节点2、3、4进行化简，得图3.14（a）。图中，新增支路以粗实线表示，保留支路用虚线表示，以下同。 4 10 9 1 4 10 9 1 18 14 19 13 18 14 19 13 8 7 6 5 8 7 6 5 15 17 16 20 15 17 16 20 3 12 11 2 3 12 11 2 （a）化简节点1、2、3和4