高电分网络学堂-第3章.pptxVIP

1 第三章稀 疏 技 术 作业：3－1，3－2，3－5，3－7，3－9，3－12 2 3.1 概述 n m τ 稀疏度 节点导纳矩阵 α:平均出线度，N：节点数 3.1.1 电力网络的拓扑结构特点：稀疏性 3 稀疏矩阵技术：Tinney(1967) Ax＝b 开发A的稀疏性 要点是：排零存储，排零运算 节点优化编号 稀疏矢量技术: Tinney(1985) 开发b和x的稀疏性 要点是：辨识出必须计算的 3.1.2 稀疏技术的研究历史 4 3.2 稀疏技术 3.2.1 稀疏矢量和稀疏矩阵的存储 排零存储：要求节省空间，查询和检索方便 散居格式 优点：修改灵活 缺点：无规律，检索不便 需要存储3 个 稀疏矢量的存储： 需存储非零元的序号 稀疏矩阵的存储： 5 按行（列）存储 τ τ n 如何查找 aij 6 按行存储的例子 每行非零元在 7 三角检索（适合三角因子分解） A＝L＋D＋U L: 严格下三角矩阵，按列存储； D: 对角矩阵； U: 严格上三角矩阵，按行存储。 8 U: 严格上三角矩阵，按行存储。 L: 严格下三角矩阵，按列存储 D: 对角线矩阵 三角检索的例 增加一个元素时，修正困难 9 链表(LINK) 格式 增加Link数组 11 10 怎样重现第i行所有元素：找出aij和它的列号j 11 3.2.2 稀疏矩阵的因子分解 对A进行LU分解 常规程序 12 直接取p行非零元素 直接取p列非零元素 稀疏格式LU分解程序： A＝LU 上三角部分存储U 下三角部分存储L的非对角线元素 对角线部分存储L的对角线元素 可能产生新的非零元！ 13 如何得到A＝LDU？ 先将A分解成LU ，再规格化 L。这里的L与前面的 L不同。 A＝LDU中的L A=LU中的L D 14 3.2.3 解稀疏线性代数方程组 Ax＝b，其中 A＝LDU LDU x=b （1）前代运算（Forward Substitution ，FS) ，求解 Lz=b y z 15 前代 z中下标小者只影响z中下标大者。 并非所有下标大的都受影响，取决于L的稀疏性。 zj等于零的不用计算，可省略。 16 Zj只会影响下标大于j的，不会影响小于等于j的 常规程序 z  b zj=0 时的计算不用做（稀疏矢量） Lj中也有很多零元（稀疏矩阵） 下标大的也并非都受影响 17 稀疏格式程序 直接取用L中第j 列的非零元素 此处L(k)不会为零 z(j)为零的不必做（还可以进一步优化） 18 （2）除法运算，求解 Dy=z （3）回代运算（Backward Substitution，BS）求解Ux=y 19 x  y 下标大的xj可能影响下标小的xi 不是每个都受影响 20 只需计算x中的部分元素时，例如要计算xk则 jk的回代不必做， jk的也不一定都要做。 许多零元 21 由下往上 由后往前 j i 由下往上 由后往前 实用方法（略） 实用程序 n-1 22 3.3 稀疏矩阵的图论描述 为什么要用图来描述？ 人类容易识别和理解图，计算机容易识别和理解矩阵 Ax=b中的矩阵A，其非零非对角元的分布与电网络中的串联支路相对应，可以用图来描述 A=UTDU 中的U中非零元素的分布也可以用一个图来描述 图中含有的信息与矩阵中的相同 图中网络拓扑的对应关系  A U中非零元的分布 图中支路权重数值的对应关系 A, U中非零元素值。 23 3.3.1 定义、术语 A图：与矩阵A有相同拓扑的图； 有向A图：在A图上，定义边的方向为由小号点指向大号点； 赋权有向A图：互边赋权aij，自边赋权aii 24 A = A图 25 有向A图 赋权有向A图 26 因子图：与因子表矩阵U有相同拓扑结构的图； 有向因子图：定义边的方向是由小号点指向大号点； 赋权有向因子图：自边的权是Dii，互边的权是Uij 27 U = 有向因子图 28 赋权有向因子图 29 3.3.2 因子分解过程的图上描述 矩阵上的因子分解操作 x o x x x x x 2 4 5 7 图上操作 30 (2) 消去运算：对节点发出边的对端节点两两之间所夹的边进行边权修正，自边作为特例。 节点②发出边的对端节点的自边 对角元的运算（2×τ次乘法） 在规格化时已经除以 31 （1）规格化（总计算量为τ次除法） 对节点②发出的前向边进行规格化运算，修正发出边的边权 32 以上非零元素 和 节点②发出边的对端节点两两之间所夹的边相对应 注入元 非对角元（以上三角元素为例） 在规格化时已经除以 33 对称矩阵因子分解的计算量： n节点，b条边，τ个因子边，τ-b个注入元素 ①规格化：对每个节点发出的边进