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

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

電力系統(tǒng)中常見的大型線性方程組的系數(shù)矩陣十分稀疏，直接法解法的計算速度很快。與迭代法相比，沒有收斂性問題。矩陣的稀疏度為矩陣中的零元素與矩陣總元素之比電力網(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ù)，是指選擇算法和編制程序時，盡可能避免存儲稀疏矩陣中的零元素和避免對這些零元素進(jìn)行運(yùn)算的技術(shù)。具體而言，包括以下幾方面：稀疏存儲:對于稀疏矩陣只存儲其非零元素采用按行消元的方式進(jìn)行消元。網(wǎng)絡(luò)節(jié)點(diǎn)編號優(yōu)化技術(shù)因子表技術(shù)

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

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

占用的存儲單元分析:對于數(shù)組U,L,D共需個存儲單元，此例為10。對JU，IL共需－n個存儲單元，此例中為6；對IU，JL，共需2n個存儲單元，此例為8總計需占用2+n個存儲單元。是矩陣A中的非零元素的數(shù)目。三角檢索存儲格式在矩陣A的稀疏結(jié)構(gòu)已確定的情況下使用是十分方便的。但在計算過程中，如果A的稀疏結(jié)構(gòu)發(fā)生了變化，即其中的非零元素的分布位置發(fā)生變化，相應(yīng)的檢索信息也要隨著變化，很不方便。有兩種辦法處理事先估計注入，符號分解。鏈表格式1.4鏈表存儲格式以按行存儲的格式為例來說明。這時除了需要按行存儲格式中的三個數(shù)組外還需要增加下列數(shù)組：LINK——下一個非零元素在VA中的位置，對每行最后一個非零元素，該值置為0。NA——每行非零元素的個數(shù)。當(dāng)新增加一個非零元素時，可把它排在最后，并根據(jù)該非零元素在該行中的位置的不同來修改其相鄰元素的LINK值。例如，新增a13，把a(bǔ)13排在第11個位置，把a(bǔ)12的LINK值由3改為11，a13本身的LINK值置為3，NA(1)增加1，變?yōu)?。鏈表存儲格式重現(xiàn)第i行的所有元素：所以，只要用IA把該行第一個非零元素找到，就可以按LINK的指示找下一個非零元素。直到把該行中所有非零元素都找出來為止。當(dāng)找到第i行最后一個非零元素時LINK(A)＝0，這時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)編號分別如圖（a）(b)所示。3、節(jié)點(diǎn)編號順序的優(yōu)化

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

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

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

取