预条件处理CG法大规模电力系统潮流计算_刘洋

DOI:10.13334/j.0258-8013.pcsee.2006.07.017第26卷第7期2006年4月中国电机工程学报Vol.26No.7Apr.2006©2006Chin.Soc.forElec.Eng.ProceedingsoftheCSEE文章编号：0258-8013(2006)07-0089-06中图分类号：TM711文献标识码：A学科分类号：470×40预条件处理CG法大规模电力系统潮流计算刘洋，周家启，谢开贵，胡小正，程建翼，曾伟民311123（1.重庆大学高电压与电工新技术教育部重点实验室，沙坪坝区重庆市400044；2.中国电力企业联合会可靠性管理中心，北京市宣武区100761；3.湖北省电力公司，湖北省武汉市430077）ThePreconditionedCGMethodforLargeScalePowerFlowSolutionLIUYang,ZHOUJia-qi,XIEKai-gui,HUXiao-zheng,CHENGJian-yi,ZENGWei-min311123（1.TheKeyLabofHighVoltageEngineeringandElectricalNewTechnology,MOE,ShapingbaDistrict,Chongqing400044,China;2.ElectricReliabilityManagementCenter,ChinaElectricityCouncil,XuanwuDistrict,Beijing100761,China;3.HubeiProvincialElectricPowerCompany,Wuhan430077,HuibeiProvince,China）ABSTRACT:Thispaperpresentsadetailedinvestigation关键词：电力系统；潮流计算；预条件处理；CG法；不完全Cholesky分解；优化排序intotheproblemofthepreconditionedCGmethodforLarge-scalepowerflowsolution.ThepreconditionedCGmethodwasusedinsteadofthetraditionalLUdirectmethodforsolutionofthelargesparsesetsoflinearequations.Studiescomparingtheperformanceofkindsofpreconditionerhavebeenpreformed.AnIncompleteCholeskypreconditionerbasedonanovelorderingschemehasbeenpresentedwhichhasbeenprovedmoreeffectiveforusingCGmethodforpowerflowcomputation.TestshavebeenperformedwithnetworksofIEEETestSystemsandsynthesizedbulksystems,andshownthebettereffectivenessincomputationfortheproposedmethodthanotherpreconditioners,evensoforsuperlarge-scalepowersystemcomparingwithLUdirectmethod.0引言实现区域大电网互联以及电力市场环境下实时、超实时安全控制和潮流跟踪都迫切需要快速地进行大规模甚至超大规模电力潮流方程的全局求[1]解。对高维的形如Ax=b的稀疏线性修正方程组的反复求解是潮流计算的主要部分。已有的各种类型的潮流新算法[2-4]一般局限在物理模型及功能上的改善，而对修正方程组的求解问题，数学上依然基于传统的求解方式，即采用稀疏矩阵技术的某种直接法(如Gauss消去法和LU分解等[3-5])。修正方程组的系数矩阵是不规则的，即使采用某种节点优化KEYWORDS:powersystem;powerflow;preconditioner;CGmethod;incompletecholesky;orderingscheme[5]排序的技术(如Tinney等提出的MLMD排序)，直接摘要：研究了预条件处理的CG(ConjugateGradient)法求解大规模电力系统潮流方程的问题。采用预处理CG法代替传统的LU直接法对高维稀疏潮流方程进行求解，详细比较各种预条件处理技术对CG法潮流方程求解的效果，提出一种新的节点优化排序的IncompleteCholesky预处理方法，实验分析证明它是CG法快速求解潮流的一种十分有效的预处理方法。对IEEE-30、IEEE-118和多个合成的大规模电力系统进行潮流计算，结果表明：这种预处理方法比其它预处理方法需要更少的迭代次数和浮点运算次数，对超大规模电力系统潮流问题也比传统LU直接法更具速度和存储优势。在电力系统互联程度不断增加使其潮流计算面临大规模甚至超大规模计算压力时，该方法能够成为传统方法的一个替代。法在求解过程中由于矩阵的超大规模，也常常带来[6]大量的非零元素，明显增加了计算量和存储量；更重要的是，直接法由于其固有的前推回代特点，难以将其向量化，实现并行求解，因而很难满足大[7]规模求解时的时间和空间需要。随着电网规模的扩大、网络结构越来越复杂、网络负荷越来越重、实时控制需求的增加等，这种传统的方法受到了新的挑战。近几年，已有学者逐步在电场及电网络分析中使用迭代法求解线性方程组[8-11]迭代法一般可分为古典迭代法和Krylov迭代法。[12]基金项目：国家自然科学基金项目(50307015)；重庆市科技计划项2类。古典迭代法包括Jacobi、SOR等方法，目前已很少用于直接求解大型稀疏线性方程组，而是作为预条件子与Krylov法结合使用。Krylov法是90年目(2003-7951)。ProjectSupportedbyNationalNaturalScienceFoundationofChina(50307015)．PDF文件使用pdfFactoryPro试用版本创建卷代才完整提出的一类迭代法，它具有存储量少，计算量少且易于并行等优点，非常适合于并行求解大型稀疏线性方程组。结合预条件处理技术的Krylov法具有良好的收敛特性和较高的数值稳定性，已是kö÷æ-n(1)1x-xk£2x-x0çAAç1+nø÷è式中：分别是A的最小、最大特征值。1n由该收敛定理可看出：当时，CG法的1n目前求解大型稀疏线性方程组的最主要方法[12-13]。收敛速度是相当慢的，且实际的数例还表明，它的数值稳定性也不够理想。为了提高它的收敛速度和改进数值性能，必须对系数矩阵进行预处理，即将Krylov法中有2类重要方法：CG(ConjugateGradient)和GMRES(GeneralizedMinimalRESidual)。CG法适用于对称正定方程组，而GMRES法适用于非对称情况。本文主要研究快速分解的潮流计算，运用CG法对解耦后的有功和无功修正方程进行反复求解，从而实现大规模电力潮流方程的快速求解。CG法快速潮流计算本质上是一种双层迭代法，由外部的牛顿迭代和内部的CG迭代组成。由于舍入误差的存在，CG迭代的收敛性及收敛速度将严格依赖于其线性方程组系数矩阵A的条件数，为改善系数矩阵的条件数，时常对线性方程组进行适当变换，此过程称为预条件处理过程(preconditioning)[12]。目前多种预条件处理技术已用于实际计算，然而其作用的机理鲜为人知，而且许多预条件处理技术都和方程的物理背景有密切关系，因而在何种情况下采用何种预条件处理技术已成为当今科学计算研究领给定问题Ax=b转换成一相关问题Ax=b，使条件数(A)=max(A)min(A)尽可能接近于1。这里A=C-1AC-1，x=Cx，b=Cb，C为对称正定阵。2-1定义预条件矩阵M=C2，即采用左条件预处理的方程组变为M-1Ax=M-1b。为使该算法有效，-1所寻找的预条件矩阵M，除了使MA尽可能接近单位阵外，还必须使方程组Mz=r容易求解。这2个条件是相互对立的。考虑A为大型的稀疏矩阵，M的2种极端取法是：（1）M为矩阵A的完全分解，如M=A=LU，L、U分别是A的完全LU分解的上、下对角阵。这时M-1A=I，不需要任何迭代，但求解方程组Mz=r即是作A的完全LU分解求解，CG法丧失价值。（2）M取矩阵A的对角元素。这时方程组[13]域的一个难点。-1Mz=r的求解极为简单，但是MA可能仍具有很本文基于Linux/Intel构架设计实现各种不同预条件处理的CG法计算程序，以此详细比较各种预条件处理对CG法求解潮流方程的效果，并提出一种新的节点优化排序的IncompleteCholesky预处理方法，实验分析证明，它是CG法快速求解潮流的一种十分有效的预处理方法。对IEEE-30、IEEE-118和多个合成的大规模电力系统进行潮流计算，结果表明：这种预处理比其它预处理方法需要更少的迭代次数和浮点运算次数，对超大规模电力系统潮流问题也比传统的LU直接法更具速度和存储优势。大的条件数，CG法的收敛速度相当的慢。目前实用的预处理矩阵的取法均介于这2种极端情况之间，如基于迭代法的Jacobi预处理和SOR预处理以及基于直接法的ILU（IncompleteLU）预[14]处理。2优化排序IncompleteCholesky预处理本文在详细比较各种不同预处理技术CG法对潮流方程求解效果基础上，提出一种新的优化排序IncompleteCholesky分解预处理技术，仿真实验证明，它是CG法快速求解潮流的一种十分有效的预处理方法，并优于其他方法。1预处理CG法与各种预条件处理技术相结合的CG法是目前求解对称正定大型稀疏线性方程组的主要方法。每步迭代中，CG法只需要一次矩阵向量乘法和10n次浮点运算，每次的运算量是O(n2)(LU分解等Gauss消去法的时间复杂度是O(n3))。矩阵A本身在计算过程中不改变，因而不产生非零填充，从而更适合于大型稀疏问题。潮流方程有功无功解耦后，修正方程式的系数矩阵A不但是超稀疏的对称矩阵，且通常具有对角占优性，预条件阵M需在某种意义下尽可能地接近A，故可视M存在稳定的Cholesky分解，即TM=LDL，D为对角线矩阵，L为单位下三角矩阵。也就是说，由于A具有对称对角占优性，可令其Cholesky分解因子作为预条件阵M。Cholesky分解比LU分解的运算和存储均少一半，对角占优也使其不[14]对CG法的收敛性有如下定理：A为一对称正定矩阵，求解Ax=b的CG法有PDF文件使用pdfFactoryPro试用版本创建期刘洋等：预条件处理CG法大规模电力系统潮流计算91（8）如uÏC(T)，S(T)←S(T)∪{u}；存在选主元问题，同时忽略分解过程中产生的任何非零元填充，系数矩阵A的高稀疏性在整个分解中被保持，从而得到无填充的IncompleteCholesky分000（9）如C(T)不为，则转(7)，否则，输出S(T)，00停止。以IEEE-30节点系统为例，对其解耦潮流有功方程的系数矩阵B¢分别采用不同的排序方式，得到的矩阵分解前、后非零元分布如图1所示，采用本文的节点优化排序方式后，三角分解后的填充量虽较MIMD排序法略微增加，但较自然排序法大为减少，并且矩阵的非零元集中分布在主对角线周围，这也是可利用的矩阵结构，因为当三角分解带状矩阵时，三角因子也是带形的，因此可节省较多的计算量。解，记为I(0)。C-1CG法的快速收敛要求MA尽可能接近单位阵，即要求剩余矩阵R=A-M的范数应尽可能的小。所以当Cholesky分解本身存在较大的填充数值时，用I(0)分解预处理后的系数矩阵可能依然有较C大的条件数。对于这个问题的