A Comparison of Power Flow by Different Ordering Schemes
Wenbo Li, Xueshan Han, Bo Zhang
The School of Electric Engineering
Shandong University
Jinan, China
Email:liwenbo_1984@foxmail.com
Abstract—Node ordering algorithms, aiming at keeping sparsity as far as possible, are widely used today. In such algorithms, their influence on the accuracy of the solution is neglected because it wonrsquo;t make significant difference in normal systems. While, along with the development of modern power systems, the problem will become more ill-conditioned and it is necessary to take the accuracy into count during node ordering. In this paper we intend to lay groundwork for the more rationality ordering algorithm which could make reasonable compromising between memory and accuracy. Three schemes of node ordering for different purpose are proposed to compare the performance of the power flow calculation and an example of simple six-node network is discussed detailed.
Keywords—power flow calculation; node ordering; sparsity; accuracy; Newton-Raphson method ; linear equations
I. INTRODUCTION
Power flow is the most basic and important concept in power system analysis and power flow calculation is the basis of power system planning, operation, scheduling and control [1].Mathematically speaking, power flow problem is to find a numerical solution of nonlinear equations. Newton method is the most commonly used to solve the problem and it involves repeated direct solutions of a system of linear equations. The solving efficiency and precision of the linear equations directly influences the performance of Newton-Raphson power flow algorithm. Based on numerical mathematics and physical characteristics of power system in power flow calculation, scholars dedicated to the research to improve the computational efficiency of linear equations by reordering nodesrsquo; number and received a lot of success which laid a solid foundation for power system analysis.
Jacobian matrix in power flow calculation, similar with the admittance matrix, has symmetrical structure and a high degree of sparsity. During the factorization procedure, nonzero entries can be generated in memory positions that correspond to zero entries in the starting Jacobian matrix. This action is referred to as fill-in. If the programming terms is used which processed and stores only nonzero terms, the reduction of fill-in reflects a great reduction of memory requirement and the number of operations needed to perform the factorization. So many extensive studies have been concerned with the minimization of the fill-ins. While it is hard to find efficient algorithm for determining the absolute optimal order, several effective strategies for determining near-optimal orders have been devised for actual applications [2, 3]. Each of the strategies is a trade-off between results and speed of execution and they have been adopted by much of industry. The sparsity-programmed ordered elimination mentioned above, which is a breakthrough in power system network computation, dramatically improving the computing speed and storage requirements of Newtonrsquo;s method [4].
After sparse matrix methods, sparse vector methods [5], which extend sparsity exploitation to vectors, are useful for solving linear equations when the right-hand-side vector is sparse or a small number of elements in the unknown vector are wanted. To make full use of sparse vector methods advantage, it is necessary to enhance the sparsity of L-1by ordering nodes. This is equivalent to decreasing the length of the paths, but it might cause more fill-ins, greater complexity and expense. Countering this problem, several node ordering algorithms [6, 7] were proposed to enhance sparse vector methods by minimizing the length of the paths while preserving the sparsity of the matrix.
Up to now, on the basis of the assumption that an arbitrary order of nodes does not adversely affect numerical accuracy, most node ordering algorithms take solving linear equations in a single iteration as research subject, aiming at the reduction of memory requirements and computing operations. Many matrices with a strong diagonal in network problems fulfill the above assumption, and ordering to conserve sparsity increased the accuracy of the solution. Nevertheless, if there are junctions of very high and low series impedances, long EHV lines, series and shunt compensation in the model of power flow problem, diagonal dominance will be weaken [8] and the assumption may not be tenable invariably. Furthermore, along with the development of modern power systems, various new models with parameters under various orders of magnitude appear in the model of power flow. The promotion of distributed generation also encourage us to regard the distribution networks and transmission systems as a whole in power flow calculation, and it will cause more serious numerical problem. All those things mentioned above will turn the problem into ill-condition. So it is necessary to discuss the effect of the node numbering to the accuracy of the solution.
Based on the existing node ordering algorithm mentioned above, this paper focus attention on the contradiction between memory and accuracy during node ordering, research how could node ordering algorithm affect the performance of power flow calculation, expecting to lay groundwork for the more rationality ordering algorithm. This paper is arranged as follows. The contradiction between memory and accuracy in node ordering algorithm is introduced in section II. Next a simple DC power flow is showed to illustrate that node ordering could affect the accuracy of the solution in section III. Then, taking a 6-node network as an example, the effect of node ordering on the performance of power flow is analyzed detailed in section IV. Conclusion is given in section VI.
-
CONTRADICTION BETWEEN MEMORY AND ACCURACY
剩余内容已隐藏，支付完成后下载完整资料
潮流不同排序方案的比较
李文博，韩学山，张波
山东大学电气工程学院 济南，中国
摘 要：今天被广泛应用的节点排序算法，旨在尽可能地保证电力系统的稀疏性。在这些算法中，因为在正常的系统中算法对每种解决方案的精确度不会有显著的差异，所以它的影响通常被忽略。然而随着现代电力系统的发展，这个问题会变得更加严重，并且在节点排序过程中必须要把计数精度考虑在内。在本文中，我们试图为更多合理性排序算法奠定了基础，这样可以使内存和准确性之间进行合理的比较。本文列举出了三种不同目的的排序方案，旨在比较潮流计算的形式，并且以一个六节点网络为例进行具体讨论。
关键词：潮流计算，节点排序，稀疏性，精确度，牛顿—拉夫逊算法，线性方程组
1引言
潮流是在电力系统的分析中最基本和最重要的概念，而潮流计算则是进行电力系统规划，运行，调度和控制的基础。从数学上来讲，潮流问题是要找到一个非线性方程组的数值解。牛顿—拉夫逊算法是解决这个问题最常用的方法，它涉及到一系列线性方程组重复的直接求解。线性方程组求解的效率和精度直接影响了牛顿 - 拉夫逊潮流算法的性能。在潮流计算中，电力系统的数值和物理特性，学者们通过重新安排节点的数目，致力于研究以便改善线性方程组的计算效率，并获得了很大的成功从而为电力系统的分析奠定了坚实的基础。
在潮流计算中的雅可比矩阵，类似于导纳矩阵，有着对称的结构和高度的稀疏性。在分解过程中，内存中的位置可以产生非零输入，从而在原始的雅可比矩阵中产生零输入。这一行动被称为最小填充。如果用只能处理和存储非零输入的编程术语，最小填充的减少反映了内存需求和执行分解所需的操作数量的大大减小。所以广泛的研究与最小填充的极小值有关。虽然很难找到为确定绝对的最佳排序的有效的算法，但是有着接近最好效果的一些有效算法已经得到了实际应用。每种策略是在结果和执行速度两者之间的折中，并且它们都被大部分工业所采纳。上面提到的稀疏性的编程排序消除，在电力系统网络计算中这是一个突破，这使得牛顿法的计算速度和存储需求显著提高。
在稀疏矩阵的方法之后，稀疏向量扩展到向量的稀疏性探索的方法，当右手边的向量是稀疏的或在未知向量元素少数想用于求解线性方程组时，这种方法对求解线性方程是有用的。为了充分利用稀疏向量方法的优点，通过节点排序加强L-1的稀疏性是十分必要的。这相当于减少路径的长度，但它可能会导致更多的最小填充，更大的复杂性和费用。为了解决这个问题，提出了一些节点排序算法，这种算法试图通过减少路径的长度，同时保持矩阵的稀疏性来增强稀疏向量方法。
到目前为止，在任意一个节点的次序不会对数值精度产生负面影响的假设的基础上，大多数节点排序算法通常会采取单一迭代解决线性方程组作为研究对象的方法，旨在减少内存需求和计算操作。许多在网络问题中的强大对角线矩阵满足上述假设，并且为了保证稀疏性的排序方法增加了解决方案的准确性。然而，如果在潮流系统模型中存在一系列非常高或低的阻抗，长的超高压线路，串联和并联补偿等问题，对角占优将被削弱和假设可能并不总是站不住脚的。此外，随着现代电力系统的发展，不同数量级参数下的新模型出现在潮流模型中。分布式发电的推广也使我们坚定地把分布网络和传输系统融入到整个电力系统潮流计算中，当然它会造成更严重的数值问题。上面提到的所有这些事情会使问题变得更加糟糕。因此，有必要讨论节点编号对计算精度的影响。
基于上述提出的节点排序算法，本文重点关注这种节点排序在内存和准确性之间的矛盾，研究节点排序算法如何能影响的电力系统潮流计算的性能，从而为更理性的排序算法奠定基础。本文安排如下：在第二部分介绍了节点排序算法的内存和准确性之间的矛盾。接下来的第三部分通过一个简单的直流潮流来说明节点的顺序可能会影响算法的精度。然后在第四部分以6个节点的网络作为一个例子，对于节点排序对潮流性能的影响进行了详细分析。在第六部分给出了结论。
2 节点排序算法中内存和精确度之间的矛盾
根据计算数学，对于用高斯消元法求解的系统的线性代数方程组，完全消元法在数值上比部分消元法更可取。许多数学论文[9-11]都会关注高斯消元法的完全消元法与部分消元法的区别。参考文献[ 9 ]表明部分消元法和完全消元法是如何影响LU分解的灵敏度。参考文献[ 10 ]提出了一种有效而廉价的测试，从而找到在部分消元法在使用时的数学难题。一旦不能满足评估标准，就会采用完全消元法，以获得更好的数值稳定性。在潮流计算中，部分消元法可以再没有任何行交汇的情况下自动实现，因为在大多数情况下，雅可比矩阵的对角占优的功能可以保证在浮点运算的数值稳定性的。虽然由于舍入误差，部分消元法在有些极限点附近不能提供准确的解决方法。如果采用完全消元法，上面执行过程中的每一步，关键因素通常选择最大的模块元素。这相当于调整潮流计算的节点排序。因此，与最大的模块元素有关的节点往往安排在前面以达到提高精度的目的。
以稀疏矩阵技术为导向的节点重新排序算法已广泛应用于电力系统计算中，旨在最大限度地减少内存需求。在这些算法中，有着较少相邻节点的节点往往首先被编号。其结果是在节点导纳矩阵的对角线项往往根据自己的模块被安排从最小到最大排列。类似地，每一个涉及到一个节点的对角线子矩阵，往往根据他们的行列式按照从最小到最大的顺序进行排列。这样从这些算法形式中的获得的结果只会偏离形成的原则，但是后续的解决方案的精度将提高。这是我们所说的按照内存原则进行节点排序和精确度之间是有矛盾的。
3 使用部分消元法和完全消元法所产生的精确度差异
对于解决系统的线性代数方程组，完全消元法在数值上比部分消元法更可取。当系统系数变广时，解的精度几乎不可能受舍入误差的影响，因此把排序对于解决方案的准确性的顺序考虑在内是必要的。
图1有着四个节点的网络样本的直流模型
以图1所示的有着四个节点的网络样本的直流模型为例。节点1是已知电压相角摆动节点;节点2-4负荷节点。按照原来的节点数量，直流潮流方程是：
为了模拟计算机数值计算操作，我们用四个有效数字来解决这个问题。没有消元地对公式（1）执行高斯消元得到的解为[ theta;2,theta;3,theta;4]T=[-0.3036,-0.3239,-0.3249]T，其与精确解[theta;2, theta;3,theta;4]T=[-0.3,-0.32,-0.321]的部分元素不同，通过完全消元法可以得到一个更加精确的解：[theta;2,theta;3, theta;4]T=[-0.3007,-0.3207,-0.3217]，并且行和列的交汇处的节点的排序是3,2,4 。所以这是一个为了获得更高精确度的一个更加合理的方案。
4 节点排序对牛顿-拉夫逊潮流计算方法的表现形式的影响
图2有着六个节点的网络样本的直流模型
在上述分析的基础上，对节点重新排序的方案将不仅影响到内存的要求，而且影响到求解线性方程组时解的精度。因此，牛顿 – 拉夫逊潮流方法的性能将随着节点排序的变化而不同。在本节中将把三种不同的排序方案应用到如图2所示的6个节点的网络，以便对它们对潮流计算中解的精度、收敛速度、计算量和内存需求量进行比较。表四所示的是性能的细节。
A 目的一：尽可能地节省内存
目前，以减少最小优化和节省内存节点，有各种各样的方案应用于近优化的节点排序。这种方案所需要的唯一信息是描述网络节点分支连接模式的一个表。对减少网络的导纳矩阵有着最佳效果的排序也是相关的雅可比矩阵表的最优的因素。在编程的复杂性和最优性之间不同的方案可以达成不同的妥协。在本文中，我们关注的编号的结果是如何影响计算性能。编程效率是超出了目前的工作范围。为了节省内存，在这一部分中，提出了与[2]中提出的第三种方案类似一个动态节点排序方案。该算法的执行步骤如下。
方案一
a 定义其中一个节点度为一。如果一个以上的节点符合这个标准，选择最原始的节点。如果没有任何节点符合要求，启动步骤b ；
b 当这个节点被淘汰，编号那些没有等效的分支节点可以被引入的节点。如果一个以上的节点符合这个标准，选择最原始的节点。如果我们不能启动步骤a和步骤b，打开步骤c ；
c 当这个节点被淘汰，编号那些有最少分支的节点。如果不止一个节点可以引入最少的分支节点，给那个最大节点度的节点编号。
一旦在上述步骤中某个节点被编号，更新相关节点度和拓扑信息。直到所有的节点都编上号，节点编号就完成了。
表1 用方案一给节点再排序
新节点号码
旧节点号码
1
1
2
3
3
2
4
4
5
6
6
5
紧跟着方案一之后，6节点网络的节点编号次序如表1所示。在求解线性方程组的过程中，没有引进最小填充，所以表格的因素和雅可比矩阵将有完全一致的结构。所以表格的因素的内存需求是0.256Kb的，这个与该雅可比矩阵相同。通常情况下，通过四五次牛顿-拉夫逊迭代方法就可以得到解。可是这个例子所需的迭代次数是三十三次，因为小阻抗分支所造成的病态性。在每次迭代期间前后替代的过程中需要123次乘法运算，整个解答过程需要7456次乘法运算。
B 目的二：用完全迭代法改善精确度
考虑到完全消元法在数值上比部分消元法更可取，在本节中，为了提高解决线性方程组的准确性而采用完全消元法，旨在减少迭代次数。这里涉及到大量的对角线子矩阵行列式的节点以便安排在前面。在某种程度上，导纳矩阵的主对角线上的入口模数可以表明雅可比矩阵的主对角线上的子矩阵的行列式的幅度。为方便起见，我们利用导纳矩阵确定数字的顺序。
方案二
a 形成节点导纳矩阵；
b 用完全消元法因式分解节点导纳矩阵。记录节点的当前位置上的变化；
c 根据因式分解的节点的最终位置确定节点的新编号；
表1 用方案二给节点再排序
新节点号码
旧节点号码
1
6
2
4
3
2
4
5
5
3
6
1
执行方案二，完整消元法可以再没有行和列交汇的情况下自动进行。对应这些节点的主对角线的入口模数通过总结更多的分支参数而变得更大，因此，节点度越大的往往首先被编号。因此，该方案的的结果可能与稀疏矩阵方法和许多引入的最小填充下形成的节点编号的原则相异。6节点网络的节点编号次序如表2所示。将产生6个最小填充，所以在一次迭代中前后替代过程中将花费更多的内存（ 0.488Kb ）和更多的操作（ 321个乘法运算） ，所需的迭代总数减少到十三次，这表明线性方程组的计算精度通过完全消元法得以提高。最后，由于迭代次数的减少乘法运算的次数减少到5573次。
C 目的三：保持稀疏性的同时提高精确度
在系统中只存在一个小的阻抗分支，所以相应于节点4和节点6的只有四个条目（子矩阵）是非常大的导纳矩阵（雅可比矩阵）。在提出替代的过程中，一旦节点4和节点6被消除，其余元素组成的子矩阵能保持良好的数值稳定性，并且其余节点的编号不会对解决方案的精确度产生影响。把准确性和稀疏性都考虑在内，我们把4节点编为1号，然后按照目的一的方法给其他节点编号。这就是我们所说的6个节点网络的方案三。6节点网络的节点编号次序如表3所示。
由于在系统中只存在一个小的阻抗分支，并且它连接到节点度为1的节点4。方案三将符合目的一的要求。因此，最小填充的数目，内存需求和分解所需的操作次数与方案一相同。为了保证收敛性，只需要9次迭代，导致计算量大大减少（仅2107次乘法运算）。迭代次数的减少表明，使用方案三可以使线性方程组得到更加精确的求解。经过分析和比较，原因如下：
与节点4有关的对角线元素比节点6小一点，因此首先消除节点4不会降低精确度。该方案能够满足完全消元法。
方案三的更少的操作次数减少计算器浮点数的舍入误差。尤其注意的是，如果首先消除节点6，非常小的值可能被添加到节点2和节点5的节点元素，这将导致严重的舍入误差。然而，如果首先消除节点4，一个相当大的值将被添加到节点6的对角线元素上，产生的新值在正常范围内。
表3用方案二给节点再排序
新节点号码
旧节点号码
1
4
2
1
lt; 剩余内容已隐藏，支付完成后下载完整资料
资料编号：[443946]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
