（电力系统及其自动化专业论文）电力系统小干扰稳定分布式并行算法研究.pdf

交换量不大；并行求解得到的特征值和特征向量与串行算法完全一致。算法既能 适应按区域分布的数据，也能高效正确的完成全网的小干扰稳定特征值搜索过 程，具有较高的加速比和理想的并行效率。因而本文所实现的三种小干扰稳定分 布式并行算法具备分布式计算、在线应用的广阔前景。 关键词：小干扰稳定分析；分布式计算；并行计算；p c 机群；电力系统 a b s t r a c t w j t l lt h ei n t e r e o n n e e t i o no f p o w e r $ y s t c l n s 。i n t e r - a r e al o wf r e q u e n c yo s c i l l a t i o n o c c u r so c c a s i o n a l l y , i n s u f f i c i e n tc l a m p i n go ft h ew e a k - i n t e r c o n n e c t e dp o w e rg r i dh a s b e c o m eas e r i o u si s s u ea f f e c t i n gt h ep o w e rs y s t ms t a b i l i t y o n - l i n es m a l ls i g n a l s t a b i l i t ya s 剐葛锄e i i _ tm a yp r e v e n tt h es y s t e mf r o mt h eo s c i l l a t i o n ；h o w e v o r , i ti m t i n c l u d e di nd y n a i n i cs e c u r i t ya s s e s s m e n t i ti sm a i n l yb e c a u s et h eo n - l i n ed a t ao f t h e w h o l es y s t e mc a nn o tb ec o l l e c t e dt o g e t h e ra n ds of a rn oa l g o r i t h mi sd e v e l o p e dt o d e a lw i t ht h i ss i t u a t i o n t od e a lw i t ht h eg e o g r a p h i c a ld i s t r i b u t e do n - l i n ed a t aa n dt oa c h i e v eh i g h p e r f o r m a n c e ，t h es t r a t e g yo f t h ep a r a l l e la l g o r i t h m sp r o p o s e di nt h i sp a p e ri st od e c o m p o s et h e e l l t i r es y s t c m i n t os e v e r a ls u b s y s t e m sa n d t h e n t h e m a i n r e s e a r e h i s 舔f o l l o w i n g ： 1 a p a r a l l e la l g o r i t h mu s e dt os o l v et h e l i n e a re q u a t i o n s ，n a m e d m u l t i - p o r ti n v e r s e m a t r i xp a r a l l e la l g o r i t h m p r o p o s e db yc h i n ae p r li si l l u s t r a t e di nd e t a i la n d a p p l i e d t ot h ee i g e n v a l 鹏a l g o r i t h m st om a n a g et h ed i s t r i b u t e dj a c o b e a nm a t r i x 2 t h er e a s o n , p r o e e d u r ea n dw h a tar o l ei tp l a y si na l lt h ee i g c n v a l u ea l g o r i t h m so f t h ev e c t o rn o r m a l i z a t i o na l ei n t r o d u c e dd e t a i l e d l y , t h em o s te f f e c t i v ep a r a l l e l i m p l e m e n t a t i o no f t h e v e c t o rn o r m a l i z a t i o ni ss e l e c t e d 3 s e v e r a lc o n v e r g e n te r i t e r i o ma r ec o m p a r e da n dt h em o s te f f e c t i v ea n ds u i t a b l e w a y f o rp a r a l l e li m p l e m e n t a t i o ni ss e l e c t e d 4 t h r e ed i s t r i b u t e dp a r a l l e lc o m p u t i n ga l g o r i t h m sa p r o p o s e d , i e t h ei n v e r s e i t e r a t i o n r a y l e i g hq u o t i e n t i t e r a t i o na l g o r i t h m , t h es i m u l t a n e o u si t e r a t i o n a l g o r i t h ma n dt h ei m p l i c i tr e s t a r ta m o l d ia l g o r i t h m t oa e l a i c v et h eb e s tp a r a l l e l e t f i e i e n e ys e v e r a ld i f f e r e n tp a r a l l e li m p l e m e n t a t i o mh a v e b e e ne x h a u s t e d 5 b a s e do nm p i , t h ea l g o r i t h m sp r o p o s e di nt h i sp a p e ra 坞d e v e l o l 脚i nf o r l r a n l a n g u a g eo nl i n u xp l a t f o r ma n dt e s t e d0 1 3 p cd u s t e r s s i m u l a t i o nr e s u l t so na s m a l l8 c a l es y s t e m , al a r g ei n t e r - c o n n e c t e ds y s t e ma n da1 0 0 0 0 - b u ss y s t e m 黜 s h o w n b a s e d0 1 3 s u e l ai 饿, a r e h , t h r e es m a l ls i g n a ls t a b i l i t yd i s t r i b u t e dp a r a l l e lc o m p u t i n g a l g o i i t h m s a r ed e v e l o p e da n di m p l e m e n t e d , i e t h ei n v e r s ei t e r a t i o n r a y l e i g l a q u o t i e n ti t e r a t i o na l g o r i t h m , t h es i m u l t a n e o u si t e r a t i o na l g o r i t h ma n dt h ei m p l i c i t r e s t a r ta m o l d ia l g o r i t h m a l lo ft h ep r o p o s e da l g o r i t h m sh a v en o tm a d eg r e a t m o d i f i e a t i o na n da n ya p p r o x i m a t i o no ns e r i a lc o d e s w i t hn om a n yt i m e st o c o m m u n i c a t ea n dn om u c hd a t at oe x c h a n g e t h ee i g e n v a l u e sa n dt h ec o r r e s p o n d i n g e i g e n v e c t o r ss o u g h tb y t h e s ep r o p o s e da l g o r i t h m s 黜t h es a m ea st h er e s u l t ss o u g h t b ys e r i a lc o d e s t h u st h ep r o p o s e da l g o r i t h m sc a nm a n a g et h eg e o g r a p h i cd i s t r i b u t e d d a t aa n ds e e kt h ee i g e n v a l u e se f f i c i e n t l yw i t hh i g h $ p e c d - u pa n di d e a le f f i c i e n c y , w h i c hh a sb r o a dp r o s p e c t i v ea p p l i c a t i o n s k e yw o r d s ：s m a l ls i g n a ls t a b i l i t ya n a l y s i s ；d i s t r i b u t e dc o m p u t i n g ；p a r a l l e l a l g o r i t h m ；p cc l u s t e r s ；p o w e rs y s t e m 第l 章绪论 第1 章绪论 1 1 小干扰稳定及小干扰稳定分析 1 1 1 小干扰稳定问题 在现代电力系统的发展中，为了解决能源分布和电力负荷需求的不一致； 协调火力、水力和核能各种电源的运行；利用时差、季节差错开负荷高峰，减 少电力系统的总装机容量；在发生电力系统扰动或故障时，各地区发电能相互 支援，电力系统广泛采取互联运行方式，出现了覆盖不同地区、跨越地理范围 达数千公里、包含大量动态元件的大型互联电力系统。 在电力管理体制方面，世界范围内电力工业正在进行以打破垄断、引进竞 争为特征的电力体制改革。在庞大复杂的电力系统中引入电力市场竞争机制， 给电力系统分析提出了新的挑战。在电力市场环境下，电力交易复杂多变，电 力系统经常运行在极限状态。一旦电力系统局部发生故障，如果处理不正确或 不及时，就会出现连锁故障，导致大范围的停电事故。 低频振荡是在现代电力系统中发生频繁、对系统稳定运行造成严重影响的 一类事故。弱联系的电网互联、远距离输送大量功率，都将损害互联系统的小 干扰稳定性，使得系统在扰动下发生不良阻尼或增幅的振荡。由于其振荡频率 很低，一般在0 1 - 2 5 h z 问，故称为低频振荡。国内外不少电力系统都出现过 低频振荡问题，低频振荡成为制约联络线输送功率极限提高和互联电力系统安 全稳定运行最重要的因素之一。 上世纪5 0 年代，前苏联在建设古比雪夫一一莫斯科输电系统时发现，当系 统输电功率达到某一定值后，系统会在没有任何明显的扰动下出现增幅振荡。 为解决这个问题，专家们研制了“强力式励磁调节器”，即在原有的电压调节器 基础上，引入其它偏差信号，进行发电机的励磁调节。该装置有效的解决了自 发振荡的问题【u 。 1 9 6 4 年美国西部系统即w s c c ，将水电为主的西北部与火电为主的西南部 用2 3 0 k v 联络线连接后，也出现了功率振荡。此后，该系统分别在1 9 9 2 年1 2 月8 日、1 9 9 3 年3 月1 4 日、1 9 9 5 年7 月1 1 日、1 9 9 6 年7 月2 日和1 9 9 6 年8 月l o 日先后发生了五次低频振荡。其中1 9 9 6 年8 月1 0 日最为典型和严重。美 中国电力科学研究院博士论文电力系统小干扰稳定分布式并行算法研究 国电力科学研究院使用p s a p a c 软件包中的暂态中期稳定性程序e t m s p 和小 信号稳定程序包s s s p 程序，对该事故分别进行了时域仿真和小扰动特征值分 析，并用e t m s p 中的频谱分析确定了实际信号和仿真信号中的频谱分量。根 据实际事故记录和仿真结果可知，8 1 0 事故是系统发生一系列事件后、运行状 态持续恶化而出现的小扰动稳定问题，通过调节或增加电力系统稳定器p s s 和 调整h v d c 控制都能改善负阻尼区间振荡模式( 频率为o 2 8 h z ) 。事故分析提 出了如下建议：只用时域法和潮流计算不足以理解8 1 0 事件，小扰动分析和信 号处理分析应该成为分析工具的一部分；应对研究和工程人员进行培训，使他 们了解与小扰动有关的物理现象、分析工具及补救措施f 2 1 【6 】。 在巴西内部电网互联期间，也屡次出现了低频振荡现象。1 9 7 5 年至1 9 8 0 年期间，巴西南部和东南地区由薄弱的2 3 0 k v 输电系统联结，功率从东南向南 部输送。由于南部地区的几个火电厂的发电机总出问题以致停运，系统经常运 行在稳定极限边缘，在扰动下频繁出现南部系统相对于东南系统的不衰减振荡， 导致互联解列、地区性低频减载动作。由于那时没有合适的工具来估算这种现 象，只能采用暂时性措施如采用最大角度7 0 度作为运行条件限制等。到1 9 8 1 年，为了能输送伊泰普6 0 h z 电站的电力，投运了7 5 0 k v 交流线以联络巴西的 东南部和南部。此时在互联系统与伊泰普6 0 h z 电站之间又出现了一种新的摆 动形态。在这种情况下，为改善系统阻尼，专家们对p s s 进行了大量的深入研 究，在p s s 的研究手段、运行经验、技术条件和安装投运等方面积累了丰富的 经验 7 1 。1 9 9 8 年，巴西南北两个大电力系统通过5 0 0 k v 、1 0 0 0 m w 容量的交流 线路，并使用串联补偿进行了南一北互联，互联带来大约6 0 0 m w 的功率增益。 但同时互联将导致系统会出现一个弱阻尼的区间低频振荡( o 1 7 h z ) 。当时使用 了巴西国家实验室c e p e l 开发的用于小干扰稳定分析和设计的软件p a c d y n 对 南北互联的进行了初期规划研究。分析指出，改善东部地区各发电机的p s s 或 在南一北线路中加装可控串补t c s c ，将是解决南一北振荡技术上可行的办法。 这个结论后来通过暂态稳定模拟得到证实i s l 。 欧洲电网在互联时，也出现过低频振荡现象。1 9 9 5 年东德的一个区域电网 ( v e a g ) 和欧洲中部的电力系统( c e n t r e l ) 接入已互联的欧洲西部系统 ( u c p t e ) 后，在1 9 9 7 年上半年出现了阻尼不良的区间振荡。研究认为发生 振荡的原因是从v e a g 和c e n t r e l 向u c p l 咂电力系统输送功率过多。为了研究 功率输送对电力系统稳定性的影响，专家们使用s t u t t g a r t 大学的详细电力系统 动态模型，模拟了u c p t e c e n t r e l 电力系统在1 9 9 6 年秋季的静态和动态工况， 得出了如下结论：从u c p t e c e n l r e l 电力系统的周边部分输送大面积的功率到 中心部分容易导致阻尼恶化；功率流向不同对阻尼的影响不同；改善区间振荡 2 第1 章绪论 阻尼的方法包括：降低电压调节器的暂态增益；降低水电站的调速器的暂态增 益；在周边电力系统的一些电厂内安装适当参数的电力系统稳定器【9 】。 我国的电力系统从上世纪8 0 年代初开始，也发生过多次低频振荡现象。如 1 9 8 3 年湖南电力系统的风常线、湖北电力系统的葛凤线、1 9 8 4 年广东一香港互 联系统联络线、1 9 9 4 年南方互联系统的天广线、1 9 9 8 年川渝电网的二滩电力送 出系统，2 0 0 3 年南方电网罗马线、天生桥至广东、广东至香港的联络线，这些 联络线上均能观察到显著的功率波动n 1 1 2 1 。最近的一次造成较大影响的低频振荡 事故发生在2 0 0 5 年1 0 月2 9 日华中电网。这次功率振荡涉及全网大部分5 0 0 k v 线路、主要大机组和鄂西北2 2 0 k v 电网，振荡频率为0 7 7 h z 。三峡外送系统振 荡幅度较大，其中斗双线振荡最大，振幅为7 8 0 m w ；机组中，三峡电厂机组振 荡最大，单机振幅为2 7 0 m w ；5 0 0 k v 中枢点中，左二5 0 0 k v 母线电压振荡最 大，振幅为4 0 k v 。使用电力系统分析综合程序( p s a s p ) 进行仿真，得出如下 结论：鄂西北电网存在弱阻尼模式，在扰动下会发生大幅度功率振荡：鄂西北 弱阻尼振荡引发了三峡机组和全系统振荡。但仿真结果显示，三峡机组的振荡 幅度比实际录波要小。还需要对仿真模型和参数，如全网机组的惯性时间常数 等因素进行进一步调查和试验研究，提高仿真精度。 低频振荡事故研究结果表明，低频振荡产生的主要原因是系统存在负阻尼。 产生负阻尼的原因很多，系统中主要发电机配备有高放大倍数的快速励磁系统 是重要原因之一。许多研究表明，在正常实用范围内，励磁电压调节器的负阻 尼作用会随着开环增益的增大而加强。负阻尼理论得到了学术界的广泛认可， 相应的研究已相当成熟。按照负阻尼理论所设计的，以发电机功率、发电机组 的轴速度和发电机机端电压频率为信号的附加励磁控制装置一一电力系统稳定 器p s s ，在现场运行过程中，对低频振荡起到了很好的抑制作用。p s s 已成为 使用最广、最简单而有效的附加励磁控制。除p s s 装置具有抑制低频振荡作用 外，t c s c 控制装置也是目前考虑比较多的有效措施之- - “。 1 1 2 小干扰稳定分析方法简述 大型电力系统小于扰稳定分析主要采用时域仿真法和特征值分析方法。 时域仿真法，能模拟系统受到扰动后各个系统参量随时间变化的具体过渡 过程，从而反映系统的稳定程度。其优点是能充分考虑电力系统的非线性因素， 对建模几乎没有限制。时域仿真法通常用于研究大干扰下电力系统的暂态稳定 性；时域仿真法用于大型电力系统小干扰稳定分析时，可以利用时域仿真得到 的仿真曲线推算振荡模式的频率和阻尼。然而，不同系统变量的仿真曲线与扰 3 中嗣电力科学研究院博士论文 电力系统小干扰稳定分布式并行算法研究 动的形式和地点有关，而小干扰稳定研究的是系统固有的性质，一次扰动并不 能保证激发全部的关键模式，因此需改变扰动进行多次仿真；其次，对于低频 机电振荡现象，仿真时间必须足够长，要仿真的系统参量多，因此计算量很大； 另外，任一条仿真曲线都包含了系统众多模式的动态，难以了解关键模式在全 系统中的行为；最后，时域仿真法给出的关键模式的定量信息非常有限，难以 有效的设计控制器。 特征值分析方法，严格建立在现代控制理论基础上，是研究电力系统小干 扰稳定最有效的方法。该方法将描述电力系统动态过程的状态方程线性化，将 电力系统视为用标准线性状态方程描述的一般动态系统，系统的小干扰稳定性 与状态方程中的状态矩阵的特征值和特征向量密切相关。系统的振荡模式完全 由状态方程中状态矩阵的特征对确定，特征值的实部表示振荡模式的阻尼，虚 部对应振荡模式的频率，而特征向量则反映系统状态变量在该振荡模式下参与 系统动态的行为。特征值分析方法能深刻刻画振荡模式，有效地计算振荡模式 的定量信息，从而能用于确定控制器最佳安装地点和控制器的参数设计【1 0 】。 按照特征值的搜索范围，特征值分析方法可分为全部特征值法和部分特征 值法两类。 全部特征值法，可用于搜索出系统所有的振荡模式。最有效的方法是q r 算法，但该方法仅适用于对称与非对称的中、小型矩阵，对于大规模矩阵问题， 却无能为力。例如在目前计算精度下，当矩阵维数高达5 0 0 阶以上时，q r 法 将可能产生显著的计算误差，甚至不能得出计算结果。对于大规模的电力系统， 尤其在分析电力系统低频振荡问题时，发电机及其调节器，以及各种投入系统 的动态元件，均需要采用比较精确的数学模型，线性化后矩阵的阶数将高达数 千阶以上，远远超出了q r 法的适用范围。而且，在进行电力系统小于扰稳定 分析时，我们通常仅对低频振荡特征值及其相应特征向量中对应ad 、a6 的 分量感兴趣，而q r 法求出了所有的特征值和特征向量，造成了运算量的极大 浪费【1 1 】。 为了解决上述困难和问题，上世纪8 0 年代以来，提出了一类计算部分对稳 定性起关键影响特征值的分析方法。按照这些算法对系统状态矩阵的不同处理， 又可以分为两种；降阶选择模式分析法和全维部分特征值分析法。 降阶选择模式分析法【l l 】，是将矩阵经过降阶处理后再进行计算，其基本原 理是，在全系统线性化方程宕= 肋工中，将全部状态变量4 x 按某种原则分成 保留变量4 局和不保留变量4 尼，可得： 第l 章绪论 甜瞪2 煳 由( 1 1 ) 进行拉氏变换并消去4 彪，得： a 毫= 4 。+ 4 ：似一如) 。1 4 1 战 其中i 为单位阵，s 为微分算子。令 4 0 ) = 4 。+ 4 ：( 盯一如) 。1 4 1 ( 1 1 ) ( 1 - 2 ) ( 1 - 3 ) a r ( s ) 具有两个重要性质：州s ) 的特征值亦为a 的特征值；设l h 和u n 分别为 a 和州s ) 的特征向量，则u 。和中对应于x l 的元素相等。上述两个性质， 保证了“降阶”系统不畸变原系统的振荡模式和模态。因此，可通过对矩阵a “s ) 进行特征值和特征向量计算来分析所感兴趣的振荡模式和模态。降阶模式分析 法的主要优点是：a “s ) 比原系统状态矩阵a 维数大大降低，在一定程度上减缓 了“维数灾”问题，同时也节省了计算量。 常用的降阶选择模式分析法有两种：s m a 法【1 2 】和a e s o p s 法【1 3 】【1 4 1 。s m a 法主要问题是：迭代收敛性差、难以选取保留变量、难以给定特征值和特征向 量的初始估计值；a e s o p s 法的主要问题是：如何选择合适的受扰发电机以及 如何给定合适的初始估计值，使之能有效的求得最关心的各个主导特征值1 1 1 。 全维部分特征值分析方法的主要思想是【”1 ，将全系统状态矩阵4 经过适当 变换后成为一个与它维数相同的矩阵4 ，使4 阵中所研究的一个或小部分特征 值相应的变换成为4 中模最大的一个或较大的几个特征值，然后采用适合于计 算矩阵按模最大特征值或者一部分按模递减特征值的计算方法，求出4 中的这 些特征值，最后经过反变换得出彳中所关心的特征值。 常用的状态矩阵变换形式包括复位移逆法、s 矩阵法、m o b i u s 变换。其中 复位移逆法的变换形式为： 4 = ( 4 一。1 ( 1 川 其中g 为复数位移，设矩阵4 的一个特征值及其相应特征向量分别为 r 和五， 则： 由上式可得： 4 互= 0 一班) - i 置= 丑置 ( 1 5 ) 5 中国电力科学研究院博士论文电力系统小干抗稳定分布式并行算法研究 x t = 0 一私h 置 麒t = 嫡+ 訇x t ( 1 6 ) 0 - 7 ) 显然矩阵a 和矩阵4 的特征向量相等，而两者的特征值之间有如下关系： a = g + 石1 ( 1 8 ) 可见a 阵中最靠近q 的几个特征值被映射到a r 中模最大的几个特征值。 目前，在大型互联电力系统的小干扰稳定分析中，全维部分特征值算法是 最常用的分析方法。本文对分布式并行算法的研究均是基于此类算法。因此， 在1 2 节中将详细介绍在电力系统小于扰稳定分析中常用的几种全维部分特征 值算法。 1 1 3 在线分布式并行计算任务的提出 现代电力系统迫切需要在线的稳定性定量分析和控制决策。 随着电力系统规模的迅速扩展、各种高新技术应用于电网、电力市场竞争 机制的引入，使得电力系统运行方式复杂多变，电力系统发生事故后造成的社 会影响和经济影响越来越大，对电力系统安全稳定运行的要求变得越来越高。 为时刻保障电力系统安全稳定运行，在系统正常运行时，要求运行人员必须实 时、全面的了解电力系统的运行状态和潜在的事故隐患，掌握足够的系统安全 可靠信息与可用的发电调整冗余，并按实时工况来动态地修正运行极限值和控 制策略，以使系统远离潜在的不稳定事故；而在电力系统已经发生事故时，要 求调度人员能迸行正确的分析和判断，并迅速的采取准确的控制措旌以防止事 故的蔓延。 随着e m s s c a d a 系统功能的不断完善和广泛使用，电力系统计算逐渐地 从传统的基于多个典型方式的离线计算转为接入实时数据的在线计算。各种基 于在线数据的高级应用如电力系统在线动态安全分析，引起了广泛的研究。 动态安全分析( d y n a m i cs e c u r i t ya s s e s s m e n t ，d s a ) 是指对电力系统的运 行状态进行实时仿真、监测和控制，评价系统受到扰动后过渡到新的稳定运行 状态的能力，并对必要的预防措施和补救措施给出适当的参考方案，以保障电 力系统的安全稳定运行1 6 1 。在线的动态安全分析则是基于电力系统在线实时数 第l 章绪论 据和动态信息，在给定的时间间隔( 如5 至1 5 分钟) 内，对电力系统做出动态 安全评估。基于在线动态安全分析的稳定控制可以根据系统的实际工况和预想 事故来进行最优的控制，不存在运行工况的匹配问题，避免了对大量不相关工 况的仿真计算，极大地减少了计算量。通过动态安全分析的稳定性定量分析和 灵敏度分析可以确定控制策略并进行校核以获得最优的控制方案。 由1 1 所述可知，对系统的小干扰稳定性进行实时的监控和预警，对于预防 低频振荡事故和防止事故蔓延是非常必要的。但值得注意的是，当前的在线动 态安全分析概念中，仅仅强调要在一定的时间内完成大量预想事故的暂态稳定 分析与评价，并没有明确提出涵盖小干扰稳定在线计算的任务。其主要困难是 缺少完整的全网在线数据和适应电网在线数据按区域分布的快速算法。 由于管理体制和竞争机制等原因，全网内每个区域仅拥有自己本地的在线 数据，各区域数据相互并不完全透明，全网各区域在线数据的集中既存在管理 方面的问题，也存在技术上的困难。为此，目前区域电网在线动态安全分析， 对外网系统通常采用等值的方法。这对暂态稳定仿真影响可能不大，但对小干 扰稳定分析则会带来很大影响。这是因为系统中的关键模式通常是区间振荡模 式，涉及某几个区域的大部分机组。对外部系统进行动态等值，可能会丢掉该 模式的部分信息，甚至找不到该模式。 因此，必须研究解决适用于在线计算的、能基于按区域分布的在线数据的 小干扰稳定分布式并行计算算法作为实现小干扰稳定在线动态安全分析的一种 有效方法。 1 2 小干扰稳定全维部分特征值串行算法 1 2 1 几种常用算法 常用的求取矩阵按模最大的一个或几个特征值的特征值算法有幂法、 r a y l o i g h 商迭代法、同时迭代法和隐式重启动a m o l d i 方法。 ( 1 ) 幂法【1 5 】 其基本原理如下： 设彳q 。其特征值和特征向量分别为盖i 和b ，- - 1 ，2 ，一，而且有： r i 阮i k i l 以l 7 中国电力科学研究院博士论文电力系统小干扰稳定分布式并行算法研究 对于如下所示的初始向量“。： 执行下述迭代过程： 口。= q 毋 g 0 j - i ( 1 - 9 ) 批5 南 m 则s 次迭代之后矿由下式决定： a s u o - - e g 彳墨= 唰曰 = 硝 g 墨+ 喜g ( 莉”e “刀g 皇 。4 。 由上式可见迭代序列 以收敛于特征向量p j ，而相应特征值 l 由下式给出： a l 础( ，) ( 1 1 2 ) 该算法的数值稳定性较好，但其迭代收敛速度较慢。另夕卜，该方法一次只 能求出一对特征值和特征向量。 ( 2 ) r a y l e i g b 商迭代法i 嘲 酬咖商的概念最初是在实对称矩阵中提出。设4 为弗阶实对称矩阵，对 于任一非零向量工，称r ( 曲：下x r a x 为对应于向量z 的瑞利( r a y l e g h ) 商。对 工工 于对称矩阵彳，其特征值次序记为a 五五五，则r a y l v i g h 商具有 如下性质： 五足五 其中： 五2 骤r r ( 力 艇 脚 第1 章绪论 以= r 删r f m r ( 力 而对于非对称阵或n o n - h v r m i f i a n 阵，广义r a y l c i g h 商定义如下： 顾力：下w r a x 广工 向量w 是彳的左特征向量的估计。 r a y l e i g h 商迭代法则是以逆迭代法为基础，即以下述迭代序列求取最靠近初 始位移矿的特征值及其相应特征向量，但每次迭代过程后都用下述r a y l c i g h 商 修改位移矿： 矿+ 1 = a - q k i ) 一l “t “t + l 2 j；羽vr+l ( - s ) 。矿4 矿 矿2 7 万 ( t - t 籼 显然，由于r a y l e i g h 商迭代法使用移动位移，所以每次迭代中都需要对矩阵 组哪 进行l u 分解。 上述r a y l e i g h 商迭代法的迭代收敛速度较快，但其对于初始位移矿的要求 较高。另外与幂法相同，该方法一次也只能求出一对特征值和特征向量。 下文将提到的逆迭代转l h y l e i g h 商迭代法是将逆迭代法和r a y l e i g h 商迭代 法相结合而形成的算法。其中逆迭代法是由幂法和复位移逆变换组合而成。逆 迭代转r a y l e i g h 商迭代法，是先用逆迭代法求出一个较好的估计值，然后以此 估计值为初值，用r a y l c i g h 商迭代法求出特征值。 ( 3 ) 同时迭代法【1 8 1 9 1 该方法的基本原理为：设a g 。其特征值和特征向量分别为 i 和毋，i = i ， 2 ，h ，而且有； k i k i k l 阮i a = 除 中田电力科学研究院博士论文电力系统小干扰稳定分布式并行算法研究 其中： a 。= d i a g ：h 丸 a 。= d 妇 以+ 五 记矩阵a 的右特征向量阵为： q = 【q t 幺】= h q 。l 口。q 。】 其中q i 为对应于特征值 i 的特征向量。设有m 个相互独立的初始向量： v - - 雄l 2 “】c 对于上述初始向量执行以下运算： 由于c ，可以化为： 矿= a u 。 u = q e + q g 其中g e c _ 叶n 。，g c ( n 哪) 。为系数矩阵。显然有： ( 1 一1 5 ) ( 1 - 1 6 ) y = a u = q a 。c o + 幺a 6 g( 1 1 7 ) 式( 1 1 7 ) q ，等式右边第一项所占比例比其在式( 1 1 6 ) 中所占比例大，或者说矩阵 y 的各列中，属于q 6 的分量受到了某种程度的抑制。采用以下迭代过程进一步 求解以。中的特征值。首先定义： g = u h u * u h q c ： h = u h v * u h q a 。c o 其中上标h 表示复矩阵的共轭转置运算。假设驴镇非奇异，则： g - i h c o 。( u 日q ) - 1u 日q a 。c o = c o a 。c o 或者说，若矩阵b 为方程g b = h 的解则： e b * 人。e f l - i s ) ( 1 1 9 ) ( 1 - z o ) 第1 章绪论 上式表明矩阵以。和g 包含矩阵口的近似特征值和左特征向量。若矩阵p 为矩 阵矩阵曰的右特征向量阵： 则： p * c | 。1 w = ? * q 人。+ q 人6 c ：e - 1 ( 1 - 2 1 ) ( 1 2 2 ) 式( 1 2 2 ) q b ，w 给出了一套更为精确的矩阵4 右特征向量的估计值。令初始向 量集u - _ 矾重复以上运算直至收敛。 上述算法一次可以求出若干个主导特征值及其特征向量。 ( 4 ) a r n o l d i 方i 5 妒1 】_ 【嚣1 a m o l d i 方法自提出后就引起了学者们浓烈的兴趣。s a a d ，h o ，g a r r a t t , s a d k a n e 。s o r e n s e a ，m o r g a n 和z h o n g x i a oj i a 等人发表了各种文章，基于a m o l d i 方法提出了多种改良版本，包括块a m o l d i 方法，使用c h c b y c h e v 加速的a m o l d i 方法，多项式预处理a m o l d i 方法，位移求逆a m o l d i 方法，调和a m o l d i 方法， 隐式重启动a m o l d i 方法和精华类a m o l d i 方法等。隐式重启动a r n o l d i 方法是 a m o l d i 算法实现的一个重要技术，是当前收敛性能最好、最稳定的a m o l d i 方 法。 基本的a r n o d i 算法的原理是，首先给定单位范数的向量m ，由其生成m 维 的空间e = k ( 彳，v 0 = s p a n ( v l ，彳m ，a ”1 v 0 ，通过a m o l d i 过程生成该空 间上的一组正交基y = ( v l ，v 2 ，y 坍) ，生成正交向量的过程即为将彳- l 正交 化的过程，并通过此正交基约化彳阵为h ( 即v 7 a v ) ，然后再将h 阵约化为 块三角阵死r 的特征值为彳的特征值，特征向量需转换。 基本a l n o l m 算法做如下形式的k 步a m o l d i 分解： 彳圪= k 皿+ 以( 1 - 2 3 ) 设圪”，形圪= ，以矿是上h e s s e n b , 既 g 矩阵，五且 中国电力科学研究院博士论文 电力系统小干扰稳定分布式并行算法研究 形五= 0 ，气是第七个坐标向量。 k 步a m o l d i 分解可按如下迭代公式扩展一步： 可以推出： , - - - n ：, l l ：，= 去五 = 哌v k + l 】 一叫骆噶w ：，l q l 2 【- 履乏j f f k + l = w - - 骆”h ，w ( 1 2 4 ) ( i - 2 5 ) ) ( 1 - 2 6 ) 0 - 2 7 ) ( i - 2 8 ) a = 圪h 珥h + 五h 矗，噶圪h = 厶，噶以“= 0 ( 1 2 9 ) 由于原始a r n o l d i 法在k 较大的情况下收敛，所以必须对一高维数 h 韶s e n b e r g 矩阵进行全特征分析，运算量较大。而且该方法通常收敛于矩阵的 最外层的特征值，在特征值分离程度较好时，收敛速度快，而对于密集性特征 值时，则需要很多步才能收敛。所以通常计算时固定k ，每k 步重启一次。重 启时，希望利用已积累的信息逐次重新构造更好的投影子空间以期最终求得所 需要的特征对。 隐式重启动a m o l d i 方法是a m o l d i 算法实现的一个重要技术。该技术通过 带位移的q r 算法来构造新的子空间，可以节省矩阵一向量积。该技术的关键 在于寻找一个好的位移选取策略，若位移选取的好，则a m o l d i 方法可能收敛很 快，常用的位移策略是以那些不需要的r i m 值作为位移，称为准确位移。该位 移策略是a m o l d i 方法本身所能提供的最好、最廉价的位移策略，且利用该位移 策略重启动时不需要从第一步开始，从而可以在每次重新启动时显著节省计算 量和存储量。m o r g a n 对使用“准确位移”策略的隐式重启动a m o l d i 算法( i r a ) 的分析表明：重新开始以后生成的子空间保留了原有子空间的近似特征向量 ( r i t z 向量) 。 第1 章绪论 隐式重启动a r n o l d i 方法的基本原理说明如下。假定要求计算k 个特征值， k r y l o v 子空间维数限制为m = k + p ，则第一次迭代计算形如式( 1 2 3 ) 的步a m o l d i 分解： 4 圪+ ，= v k + ，峨+ ，+ 丘， ( 1 - 3 们 隐式重启动a r n o l d i 算法通过选择p 个平移点，对以+ ，执行p 次隐式q r 步。为简便计，以p 一1 为例描述i r a 重启动过程。设平移点取为，令q r 分 解为风+ l 一j = q r ，则由式( 1 - 3 0 ) ( 彳一朋k “一k “( 致q 一# 田= 五札t + 。 ( a - p j 3 v 。“一圪+ ，q 足= 五“磊 ( a 一声田( k + ，q ) - ( v k h q x r q ) = 五+ 。也q 彳( 圪+ ，q ) 一( k + 。q ) ( r q + l a p ) = 五“t q 0 - 3 0 ( 1 - 3 2 ) ( 1 - 3 3 ) ( 1 - 3 4 ) 记= k + l q ，磁l = 胄q + ，显然日厶仍是上h e 鹳咖矩阵。注意到 式( 1 3 4 ) 右端l + 1 q 的第k 列非零，因此式( 1 3 4 ) 并不是一个标准的a m o l d i 分解。式( 1 - 3 4 ) 可重新表示为 研州嘭噍， 磊豺“吼以，m s s ， 其中吒= t “纵，九= t + l 既+ l 。上式的前k 列可写为 a 瞄= 瞄研+ ( 藏。噍+ 允) ( 1 3 6 ) 令片= z 囊l 矗+ 哝厶，显然上式是一k 步a m o l d i 分解，可以在此基础上 开始新一轮迭代，注意到这种重启动方法可减少k 次矩阵向量乘法。 对上述各种全维部分特征值算法进行分析可知，在迭代搜索过程中涉及到 系统状态矩阵a 的计算全部为矩阵彳或者其变换形式4 与向量的乘法，因此， 在算法的研究过程中，我们关心更多的是矩阵向量积的实现。 中国电力科学研究院博士论文 电力系统小干扰稳定分布式并行算法研究 1 2 2 实现算法的相关技术 通常，在使用上述各种部分特征值方法时，会结合使用多项技术，如加速 技术、预处理技术、收缩技术、监视向量技术和稀疏技术等。 ( 1 ) 加速技术嗍 加速技术，即用于加快各种方法收敛性的技术，主要有两种，一种是通过 预处理改变矩阵特征值的分布，即预处理技术，见下面所述；另一种是在执行 过程中，改变初始矩阵彳o 的选取，使印伽( x o ) 更接近置阳疗如，屯，石，】 这包括在同时迭代法和a m o l d i 法中使用c h e b y s h e v 多项式，以及在a m o l d i 法 中使用隐式重启动技术重新构造每次循环的初始矩阵x ( o ) 。 ( 2 ) 预处理技术【2 9 】 最初的预处理是线性方程组迭代解法的一种加速技术。八十年代后期，矩 阵特征值问题的预处理技术成为了矩阵特征值问题领域的热门课题，其目的是 改变矩阵的特征值分布以加快收敛速度。 前面提到的谱变换技术，实际上就是一种预处理技术。但显然，使用这种 预处理技术的目的并不是为加快收敛速度，纯粹只是为了改变特征值的分布。 上述介绍的各种部分特征值算法均是求解按模最大的一个或几个特征值的算 法，而在电力系统分析中，我们所关心的只是低频振荡模式，即频率范围为 0 1 2 5 h z 内的模式，更确切的，我们只关心在此频段内的负阻尼或阻尼不足的 模式，但这些模式通常并不是模最大的特征值。所以，要想直接使用部分特征 值方法分析低频振荡，首先需要将我们所关心矩阵的低频振荡模式转换为一个 相关矩阵的模最大的特征值。由前面的介绍可知，使用谱交换即能达到这种转 换。 ( 3 ) 收缩技术【1 5 】 在使用同时迭代法和a m o l d i 法求解多个特征值时，所求的若干个特征值并 不是同时收敛的。在迭代过程中，如果让已收敛的特征值和特征向量仍然参与 迭代，一方面未收敛的特征值可能继续收敛到已收敛的特征值上，另一方面也 浪费了计算量。收缩技术，即是将已收敛的特征值收缩掉，以达到改善特征值 分离程度的目的，有利于特征值簇的收敛。其基本思想是计算已求出特征值对 应不变子空间的一个酉基，然后强迫迭代中计算的向量与此基正交。简单的收 第1 章绪论 缩技术可以采用4 锁定机制”，即假设矿的前j 列已收敛，记为k ，贝i j 在以后 的迭代中，只需计算lk ，彳。砭i ，不再更新k 。这样可明显减少矩阵向量相乘 的次数；在作正交化时，由于k 已是正交化规范矩阵，则正交化的计算量也可 进一步减少。 ( 4 ) 监视向量技术【1 5 】 在使用同时迭代法和a m o l d i 法求解多个特征值时，如果需要求出矩阵的 k 个主导特征值，则为了得到较快的迭代收敛速率，保证全部的主导特征值都 收敛，通常需要取初始向量矩阵的列数m k ，其中所增加的向量称为监视向 量。实际上m 即为i c a 3 , 1 0 v 子空间维数，理论上，增大胁能提高收敛速度，但 相应的