高等電力系統(tǒng)分析-稀疏技術(shù)

潮流計(jì)算中的稀疏技術(shù)線性方程組的求解方法有：概述直接法：高斯消去法、三角分解法迭代法矩陣求逆法

電力系統(tǒng)中常見的大型線性方程組的系數(shù)矩陣十分稀疏，直接法解法的計(jì)算速度很快。與迭代法相比，沒有收斂性問題。矩陣的稀疏度為矩陣中的零元素與矩陣總元素之比電力網(wǎng)絡(luò)特點(diǎn)決定了電網(wǎng)的導(dǎo)納矩陣是稀疏的例如：對于節(jié)點(diǎn)數(shù)為10、100、1000的網(wǎng)絡(luò)，節(jié)點(diǎn)導(dǎo)納矩陣的稀疏度分別為：

50%—60%，95%—96%，99.5%—99.6%概述修正方程式中的雅克比矩陣與導(dǎo)納矩陣有同樣的結(jié)構(gòu)，也必將高度稀疏

所謂稀疏技術(shù)，是指選擇算法和編制程序時(shí)，盡可能避免存儲(chǔ)稀疏矩陣中的零元素和避免對這些零元素進(jìn)行運(yùn)算的技術(shù)。具體而言，包括以下幾方面：稀疏存儲(chǔ):對于稀疏矩陣只存儲(chǔ)其非零元素采用按行消元的方式進(jìn)行消元。網(wǎng)絡(luò)節(jié)點(diǎn)編號(hào)優(yōu)化技術(shù)因子表技術(shù)

稀疏技術(shù)對m×n階稀疏矩陣A，其非零元素共有個(gè)，令aij是A中第i行第j列非零元素?？梢远x三個(gè)數(shù)組，按下面的存儲(chǔ)格式存儲(chǔ)矩陣A中非零元素的信息：VA——存儲(chǔ)A中非零元素aij的值，共個(gè)IA——存儲(chǔ)A中非零元素aij的行指標(biāo)i，共個(gè)JA——存儲(chǔ)A中非零元素aij的列指標(biāo)j，共個(gè)1.1散居格式1稀疏存儲(chǔ)總共需要3個(gè)存儲(chǔ)單元優(yōu)點(diǎn)：A中非零元在數(shù)組中的位置可任意排列，修改靈活。缺點(diǎn)：其存儲(chǔ)順序無一定規(guī)律，檢索起來不方便。最差的可能性要在整個(gè)數(shù)組中查找一遍。如查找第i行的非零元素在VA中取出從k＝IA(i)到IA(i＋1)－1共IA(i＋1)－IA(i)個(gè)非零元就是A中第i行的全部非零元非零元的值是VA(k)，列號(hào)JA(k)1.2按行（列）存儲(chǔ)格式按行(列)順序依次存儲(chǔ)A中的非零元，同一行(列)元素依次排在一起。以按行為例，其存儲(chǔ)格式是：VA——按行存儲(chǔ)矩陣A中非零元aij

，共個(gè)；JA——按行存儲(chǔ)矩陣A中非零元的列號(hào)，共個(gè)；IA——記錄A中每行第一個(gè)非零元素在VA中的位置，共m個(gè)。如查找第i行第j列的元素aij在VA中的位置對k從IA(i)到IA(i＋1)－1，判斷列號(hào)JA(k)是否等于j，如等，VA(k)就是要的非零元aijU——存A的上三角部分的非零元的值，按行依次存儲(chǔ)JU——存A的上三角部分的非零元的列號(hào)IU——存A中上三角部分每行第一個(gè)非零元在U中的位置(首地址)L——按列存儲(chǔ)A中下三角非零元素的值IL——按列存儲(chǔ)A中下三角非零元素的行號(hào)JL——存儲(chǔ)A的下三角部分每列第一個(gè)非零元在L中的位置(首地址)D——存儲(chǔ)A的對角元素的值，其檢索下標(biāo)不需要存儲(chǔ)1.3三角檢索存儲(chǔ)格式特別適用于稀疏矩陣的三角分解。有幾種不同的存儲(chǔ)格式。以按行存儲(chǔ)A的上三角部分非零元．按列存A的下三角部分非零元存儲(chǔ)格式為例來說明。令A(yù)是n×n階方陣：U—存A的上三角部分的非零元的值，按行依次存儲(chǔ)JU—存A的上三角部分的非零元的列號(hào)IU—存A中上三角部分每行第一個(gè)非零元在U中的位置(首地址)L—按列存儲(chǔ)A中下三角非零元素的值IL—按列存儲(chǔ)A中下三角非零元素的行號(hào)JL—存儲(chǔ)A的下三角部分每列第一個(gè)非零元在L中的位置(首地址)D—存儲(chǔ)A的對角元素的值，其檢索下標(biāo)不需要存儲(chǔ)三角檢索存儲(chǔ)格式示例IU（3）為4，表明A矩陣上三角部分第3行的第1個(gè)非零元如果有的話應(yīng)在U的第4個(gè)位置，而U表中第4個(gè)位置沒有非零元素，為了檢索方便，IU(3)仍應(yīng)賦值4。有了IU表即可知道A的上三角部分第i行的非零元的數(shù)目如果要查找A的上三角第i行所有非零元素，只要掃描A從IU(i)到IU(i+1)－1即可，JU(k)指出了該元素的列號(hào)，U(k)是該非零元素的值。對于按列存儲(chǔ)的格式進(jìn)行查找的情況類同。IUJUUU—JU—IU—L—IL—JL—D—三角檢索存儲(chǔ)

占用的存儲(chǔ)單元分析:對于數(shù)組U,L,D共需個(gè)存儲(chǔ)單元，此例為10。對JU，IL共需－n個(gè)存儲(chǔ)單元，此例中為6；對IU，JL，共需2n個(gè)存儲(chǔ)單元，此例為8總計(jì)需占用2+n個(gè)存儲(chǔ)單元。是矩陣A中的非零元素的數(shù)目。三角檢索存儲(chǔ)格式在矩陣A的稀疏結(jié)構(gòu)已確定的情況下使用是十分方便的。但在計(jì)算過程中，如果A的稀疏結(jié)構(gòu)發(fā)生了變化，即其中的非零元素的分布位置發(fā)生變化，相應(yīng)的檢索信息也要隨著變化，很不方便。有兩種辦法處理事先估計(jì)注入，符號(hào)分解。鏈表格式1.4鏈表存儲(chǔ)格式以按行存儲(chǔ)的格式為例來說明。這時(shí)除了需要按行存儲(chǔ)格式中的三個(gè)數(shù)組外還需要增加下列數(shù)組：LINK——下一個(gè)非零元素在VA中的位置，對每行最后一個(gè)非零元素，該值置為0。NA——每行非零元素的個(gè)數(shù)。當(dāng)新增加一個(gè)非零元素時(shí)，可把它排在最后，并根據(jù)該非零元素在該行中的位置的不同來修改其相鄰元素的LINK值。例如，新增a13，把a(bǔ)13排在第11個(gè)位置，把a(bǔ)12的LINK值由3改為11，a13本身的LINK值置為3，NA(1)增加1，變?yōu)?。鏈表存儲(chǔ)格式重現(xiàn)第i行的所有元素：所以，只要用IA把該行第一個(gè)非零元素找到，就可以按LINK的指示找下一個(gè)非零元素。直到把該行中所有非零元素都找出來為止。當(dāng)找到第i行最后一個(gè)非零元素時(shí)LINK(A)＝0，這時(shí)do循環(huán)結(jié)束。2.按行消元逐行規(guī)格化的高斯消去法S1.規(guī)格化第一行S2.一、二行相消S3.規(guī)格化第二行S4.一、三行相消S5.二、三行相消S6.第三行規(guī)格化最后得到：其中，依次取1/2，3，2/5，5，-23/2，-1/12為運(yùn)算因子。由后向前取虛線上三角中元素進(jìn)行回代運(yùn)算S1.取－1S2.取1/2S3.取3/2設(shè)四節(jié)點(diǎn)網(wǎng)絡(luò)的節(jié)點(diǎn)編號(hào)分別如圖（a）(b)所示。3、節(jié)點(diǎn)編號(hào)順序的優(yōu)化

3.1、節(jié)點(diǎn)編號(hào)順序與稀疏度的關(guān)系

（a）（b）對應(yīng)這兩種編號(hào)方案的節(jié)點(diǎn)方程分別為：分別進(jìn)行三次、一次消元運(yùn)算消去系數(shù)矩陣中第一列后，這兩個(gè)系數(shù)矩陣中非零元素的分布將如下式所示?！?”表示原非零元：“Δ”表示消元后新出現(xiàn)的非零元，稱注入元。再分別進(jìn)行三次、兩次消元運(yùn)算，消去其中第二、第三列，得上三角矩陣中的非零元素分布如下式所：按方案一編號(hào)時(shí)，需經(jīng)六次消元進(jìn)入回代；按方案二編號(hào)時(shí)，僅需三次消元就可進(jìn)入回代。方案二回代過程也較簡單。差別關(guān)鍵在于消元過程中是否會(huì)出現(xiàn)注入元，取決于網(wǎng)絡(luò)節(jié)點(diǎn)編號(hào)的順序?yàn)楸３止?jié)點(diǎn)導(dǎo)納矩陣的稀疏度，降低對存貯空間的需求、減少運(yùn)算量，必須盡可能優(yōu)化節(jié)點(diǎn)編號(hào)的順序。3.2高斯消元與消去節(jié)點(diǎn)的關(guān)系以高斯消元法逐列消元，對應(yīng)于以消去節(jié)點(diǎn)法逐個(gè)消去節(jié)點(diǎn)消元過程中的注入元，在物理意義上對應(yīng)于由于消去某節(jié)點(diǎn)而出現(xiàn)新的互聯(lián)支路導(dǎo)納。3.3三種節(jié)點(diǎn)優(yōu)化編號(hào)方法靜態(tài)優(yōu)化法－按靜態(tài)聯(lián)結(jié)支路數(shù)的多少編號(hào)半動(dòng)態(tài)優(yōu)化法－按動(dòng)態(tài)聯(lián)結(jié)支路數(shù)的多少編號(hào)最常用動(dòng)態(tài)優(yōu)化法－按動(dòng)態(tài)增加支路數(shù)的多少編號(hào)三種節(jié)點(diǎn)優(yōu)化編號(hào)方法編號(hào)結(jié)果不同靜態(tài)優(yōu)化法－按靜態(tài)聯(lián)結(jié)支路數(shù)的多少編號(hào)如果編號(hào)為消去1，2，3后，如果繼續(xù)消去4，則出現(xiàn)新支路BD，出現(xiàn)注入元：缺點(diǎn)是在連接支路一樣時(shí)，有編號(hào)順序問題。如果編號(hào)如右則無問題：半動(dòng)態(tài)優(yōu)化法－按各節(jié)點(diǎn)動(dòng)態(tài)聯(lián)結(jié)支路數(shù)的多少編號(hào)先編號(hào)F，然后消去F取E，并消去：缺點(diǎn)是對環(huán)網(wǎng)，可能出現(xiàn)注入元對放射型網(wǎng)絡(luò)，保證不會(huì)產(chǎn)生注入元。再取A，然后消去A重復(fù)。。。例題：如下圖按靜態(tài)法編號(hào)為1，2消去后，不產(chǎn)生注入元3消去后，產(chǎn)生注入元（B，F(xiàn)）－（6，4）4消去后，產(chǎn)生注入元（B，D）－（6，7）產(chǎn)生兩個(gè)注入元如果按半動(dòng)態(tài)編號(hào)：

先取A（＃1），再取G（＃2）再取C，可見仍然是兩個(gè)注入元

取