基于GaBP算法的快速潮流计算方法

扈诗扬　汪芳宗

摘要：研究在潮流迭代求解过程中雅可比矩阵方程组的迭代求解方法及其收敛性。首先利用PQ分解法进行潮流迭代求解，并针对求解过程中雅可比矩阵对称且对角占优的特性，对雅可比矩阵方程组采用高斯置信传播算法（GaBP）进行求解，再结合Steffensen加速迭代法以提高GaBP算法的收敛性。对IEEE118、IEEE300节点标准系统和两个波兰互联大规模电力系统进行仿真计算后结果表明：随着系统规模的增长，使用Steffensen加速迭代法进行加速的GaBP算法相对于基于不完全LU的预处理广义极小残余方法（GMRES）具有更好的收敛性，为大规模电力系统潮流计算的快速求解提供了一种新思路。

关键词：潮流计算；PQ分解法；稀疏线性方程组；GaBP算法；GMRES算法；Steffensen加速迭代法

中图分类号：TM744文献标识码：A

Abstract：An iterative algorithm and its convergence of the Jacobian matrix equations for load flow iterative solution were researched. First， the PQ decoupled method was used to solve load flow equations， and according to the feature that the Jacobian matrix of correction equations is sysmmetric and diagonally dominant， the Gaussian belief propagation （GaBP） algorithm was proposed for solving the Jacobian matrix equations. The Steffensen's iteration was used to speedup GaBP convergence. Numerical simulation tests on four systems including IEEE 118node system， IEEE 300node system and two Poland test systems indicate that， with the scale expanding， contrasting to the generalized minimal residual （GMRES） method with incomplete LU decompostion preconditioner， the convergence of GaBP with Steffensen's iteration is remarkable. The method provides a new idea for the fast power flow calculation in power systems.

Key words：power flow calculation； PQ decoupled method； sparse linear equations； Gaussian belief propagation （GaBP）； generalized minimal residual （GMRES）； Steffensen's iteration

1引言

潮流计算是电力系统运行控制中最基本的工具，其结果可以帮助运行调度人员了解电网的实际运行情况，也可为后续分析计算如稳态分析做准备[1]。传统的电力系统潮流计算通常选用PQ分解法或牛顿法[2]。PQ分解法是一种定雅可比法，同时，根据系统有功主要决定于电压相角的变化，而无功主要决定于电压幅值的变化这一特性，进行相关合理假设，具有简单、快速、适应性强且收敛可靠的优点，广泛应用于高压电网在线计算[3]。而长期以来，牛顿法结合稀疏处理技术的直接求解法占主导地位。但当系统规模很大时，直接法存在矩阵三角分解耗时过长以及数值不稳定等问题[4]。因此，迭代法近年来越来越受重视，已成为电力系统中求解线性方程组的主要方法[5]。

目前，迭代法中最令人关注的是所谓的Krylov子空间方法（Krylov subspace methoed），而应用最广的子空间迭代法应该是广义极小残余方法（generalized minimal residual algorithm，GMRES）。在电力系统分析计算中，GMRES方法已得到了成功的应用[6]。文献[7]首次尝试了将GMRES方法应用于潮流计算。相关研究结果还表明：当系统规模越大时，GMRES方法的优势越明显[8-9]。

高斯置信传播算法（Gaussian beliefpropagation，GaBP）是Orishental等学者于2008年基于Belief Propagation（BP）方法[10]提出的一种针对对称对角占优线性方程组的迭代算法 [11]。它不同于经典的迭代算法，也不同于Krylov子空间算法，GaBP算法对于对称对角占优线性方程组的求解具有良好的收敛性、更低的计算复杂性以及更高的并行性[11，16]。文献[12]给出了一种改进的GaBP算法，明显改善了经典GaBP算法的收敛性使之更加适合对称对角占优线性方程组的求解。随着对算法的深入研究，GaBP算法已经被成功应用于多个领域，比如，求解线性多用户侦测问题[13]，基于稀疏贝叶斯学习算法的大规模压缩感知问题[14]以及分布式的波束形成问题[15]。另一方面，由于算法内在的信息分布式处理特性，文献[16]提出了基于GaBP算法的分布式并行算法，并用于求解大规模稀疏对称对角占优线性方程组。此外，分布式共享存储并行处理环境发展迅速，分布式并行算法变得更有价值[17]。因此，将GaBP算法引入到潮流计算，对于今后研究大规模电力系统的分布式并行计算也是非常有意义的。

本文首先对使用PQ分解法后得到的雅可比矩阵的特点进行简要分析，然后对GaBP算法进行介绍，进而引出采用Steffensen加速迭代法进行加速的GaBP算法（GaBP+Steffensen算法），并给出了Steffensen加速迭代方法在GaBP算法迭代计算过程中实现加速收敛的具体步骤。最后通过算例结果对比分析得到，与基于不完全LU方法（incomplete LU decompostion，ILU）的预处理GMRES算法（ILUGMRES算法）相比，GaBP算法具有更好的收敛性，因此GaBP算法可以有效地提高大规模电力系统潮流迭代求解的收敛性。

式中：A为线性方程组的系数矩阵，在本文中对应雅可比矩阵J；b在本文中分别代表修正方程式中的ΔP/V和ΔQ/V；x为节点变量向量，本文中为所要求解的节点电压和相角的不平衡量ΔV、Δθ。

由于指数表达式（4）相似于多元的高斯概率密度函数p（x），因此通过求解式（4）可知线性系统的解向量x实际上等于多元高斯概率密度函数p（x）中节点变量的均值向量，定义为μA-1·b。因此，求解线性系统问题转换为求解多元高斯概率密度函数p（x）中节点变量的均值。关于GaBP算法的详细推导过程可参考文献[18]。

综上所述，GaBP算法将求解线性方程组问题转化为特定图上的概率推理问题，避免了直接法中的潜在复杂操作，并且对于对称对角占优线性方程组的求解具有良好的收敛性。因此，将GaBP算法应用于本文中雅可比矩阵方程组的求解是适宜的。

4Steffensen加速迭代方法在GaBP算法

求解雅可比矩阵方程组中的应用

4.1Steffensen加速迭代方法

在已知xk，xk+1=g（xk），xk+2=g（g（xk））时，经过简单的算术运算，还可以得到更为接近于真实值的近似解，这就是Steffensen加速迭代思想，即Steffensen加速迭代法，其迭代公式如下[19]：

yk=g（xk）zk=g（yk）k+1=xk-（yk-xk）2zk-2yk+xk（5）

式中，k为迭代次数，yk、zk均为第k次迭代的变量，g（）为GaBP算法中的迭代公式，k+1为经Steffensen加速后得到的新的xk+1。

在GaBP算法执行过程中，Steffensen加速迭代法被用在迭代计算过程中，从变量xk为初值，经过两次迭代计算得到yk和zk，再计算得到新的xk+1，重复此过程直到满足收敛条件为止。

4.2Steffensen加速迭代方法实现的具体步骤

GaBP算法求解雅可比矩阵方程组主要有初始化和迭代两部分，其具体算法步骤如下：

1.初始化：

5算例分析

在CPU为Core i5 3.0 GHz，内存为4G的PC上，使用Matlab2014a平台并利用Matpower 5.0软件包对基于GaBP算法的电力系统潮流计算进行仿真测试，然后与基于ILU的预处理GMRES算法的电力系统潮流计算进行对比分析。

选用IEEE118、IEEE300节点标准系统及两个波兰互联大规模电力系统对所提算法进行测试和对比分析，其中测试系统参数均取自Matpower 5.0软件包，系统潮流数据见表1。

同样地，在计算波兰2383节点系统时，对ILU-GMRES算法与GaBP+Steffensen算法在第二次外迭代时的收敛过程进行了追踪。对比情况（分别需迭代42次、12次后收敛）如图2所示。而计算波兰2736节点系统时，则对ILUGMRES算法、GaBP+Steffensen算法在第一次外迭代时的收敛过程进行了追踪。对比情况（分别需迭代64次、45次后收敛）如图3所示。

5结论

在采用PQ分解法进行电力系统潮流计算时，GaBP算法是求解其雅可比矩阵方程组的有效方法。经理论分析以及对IEEE118、IEEE300节点标准测试系统和两个波兰互联大规模电力系统的测试结果表明：

1）经过Steffensen加速迭代法加速后的GaBP算法，收敛性有明显提高。

2）随着系统规模的增长，在每次外迭代时，经Steffensen加速迭代法加速后的GaBP算法增加的迭代次数较基于ILU的预处理GMRES算法更少，具有更好的收敛性。

综上所述，本文应用于潮流迭代计算中的经Steffensen加速迭代法加速的GaBP算法是一种新颖且收敛性良好的求解雅可比矩阵方程组的计算方法。

参考文献

[1]严正， 范翔， 赵文恺， 等. 自适应LevenbergMarquart方法提高潮流计算收敛性[J]. 中国电机工程学报， 2015， 35（8）： 1909-1910.

[2]苏津， 阳育德， 覃智君. 基于矢量化运算模式的电力系统潮流计算[J]. 电网技术， 2008， 32（3）： 88-92.

[3]刘凯， 陈红坤， 向铁元， 等. 以对称反对称分裂预条件处理GMRES（m）的不精确牛顿法潮流计算[J]. 电网技术， 2009， 33（19）： 123-124.

[4]汪芳宗， 何一帆， 叶婧. 基于稀疏近似逆预处理的牛顿-广义极小残余计算方法[J]. 电网技术， 2008， 32（14）： 51-52.

[5]LEON F D，SEMLYEN A. Iterative solvers in the Newton power flow problem： preconditioners， inexact solutions and partial Jacobian updatesp[J]. IEEE Proceedings Online， 2002， 149（4）： 479-484.

[6]汪芳宗. 大规模电力系统暂态稳定性数值计算方法[M]. 北京： 科学出版社， 2013： 62-79.

[7]SEMLYEN A. Fundamental concepts of a Krylov subspace power flow methodology[J]. IEEE Transactions on Power Systems， 1996， 11（3）： 1528-1537.

[8]廖小兵， 王文超， 李奔. ILU预处理NewtonKrylov方法的潮流计算[J]. 计算技术与自动化， 2015， 34（4）： 46-49.

[9]REIJER I， DOMENICO J P L， CORNELIS V，et al.Scalable NewtonKrylov solver for very large power flow problems[J]. IEEE Transactions on Power Systems， 2012， 27（1）： 390-396.

[10]PEARL J. Probabilistic Reasoning in Intelligent System： Nerworks of Plausible Inference[M]. New York： Morgan Kaufmann， 1988.

[11]SHENTAL O， SIEGEL P H， WOLF J K，et al.Gaussian bilief propagation solver for system of linear equations[C]// IEEE International Symposium on Information Thoery. Toronto： IEEE， 2008： 1863-1867.

[12]JOHNSON J K，BICKSON D，DOLEV D.Fixing convergence of Gaussian belief propagation[C]// IEEE International Symposium on Information Thoery. Seoul： IEEE， 2009： 1674-1678.

[13]BICKSON D， DOLEV D， SHENTAI O. Gaussian belief propagation based multiuser detection[C]// IEEE International Symposium on Information Theory. Toronto： IEEE， 2008： 1878-1882.

[14]SEEGER M W， WIPF D P. Varational Bayesian inference techniques[J]. IEEE Signal Process， 2010， 27（6）： 8191.

[15]LOONG N B， EVANS J S， HANLY S V. Distributed downlink beamforming with cooperative base stations[J]. IEEE Transactions on Information Theory， 2008， 54： 5491-5499.

[16]ELKURDI Y， GROSS W J， GIANNACOPOULOS D. Efficient Implementation of Gaussian Belief Propagation Slover for Large Sparse Diagonally Linear System[J]. IEEE Transaction Magnetics， 2012， 48（2）： 471-474.

[17]郑汉垣. 大规模稀疏线性方程组求解的并行GaBP算法研究[D]. 上海： 上海大学， 2014.

[18]BICKSON D. Gaussian Belief Propagation： Theory and Application[D]. Jerusalem：The Hebrew University of Jerusalem， 2009.

[19]宋叶志. MATLAB数值分析与应用[M]. 北京： 机械工业出版社， 2009： 149-159.

[20]ELKURDI Y， GIANNACOPOULOS D， GROSS W J. Relaxed Gaussian Belief Propagation[C]// IEEE International Symposium on Information Theory Proceedings. Cambridge： IEEE， 2012： 2003-2004.

[21]BARRETT R， BERRY M， CHAN T， et al. Templates for Solution of Linear System： Building Blocks for Iterative Methods[M]. Siam： Society for Industrial and Applied Mathematics， 1987.