2.第二章 電力網(wǎng)絡(luò)方程求解技術(shù)

《2.第二章 電力網(wǎng)絡(luò)方程求解技術(shù)》由會員分享，可在線閱讀，更多相關(guān)《2.第二章 電力網(wǎng)絡(luò)方程求解技術(shù)（41頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

1、 第二章 電力網(wǎng)絡(luò)方程的求解技術(shù) 在電力系統(tǒng)的分析計(jì)算中，暫態(tài)分析一般關(guān)注電壓和電流，電力網(wǎng)絡(luò)模型常為線性的節(jié)點(diǎn)電壓方程；穩(wěn)態(tài)分析一般關(guān)注功率和電壓，其電力網(wǎng)絡(luò)模型常為非線性潮流方程，而非線性潮流方程也必須通過求解線性的修正方程才能得到其解。所以，無論是電力系統(tǒng)穩(wěn)態(tài)分析，還是暫態(tài)分析幾乎都會涉及線性方程組的求解問題，而且線性方程組的求解往往是計(jì)算量最大的一部份工作。所以，研究線性方程組的求解技術(shù)對電力系統(tǒng)分析計(jì)算有重要的意義。 線性方程組的解法可歸納為直接法和迭代法。從理論上來說，假定每一步運(yùn)算過程中沒有舍入誤差，直接法經(jīng)過有限次運(yùn)算，最后得到方程組的解就是精確解。但是，這只是理想化

2、的假定，在計(jì)算過程中，完全杜絕舍入誤差是不可能的，只能控制和約束由有限位算術(shù)運(yùn)算帶來的舍入誤差的增長和危害，這樣直接法得到的解也不一定是絕對精確的。 迭代法就是用某種極限過程去逐步逼近線性方程組精確解的方法。該方法具有對計(jì)算機(jī)的存貯單元需求少，程序設(shè)計(jì)簡單、原始系數(shù)矩陣在計(jì)算過程中不變等優(yōu)點(diǎn)，是求解大型稀疏系數(shù)矩陣方程組的重要方法。迭代法不是用有限步運(yùn)算求精確解，而是通過迭代得到滿足一定精度要求的方程組的近似解。 在數(shù)值計(jì)算歷史上，直接解法和迭代解法交替生輝。一種解法的興旺與計(jì)算機(jī)的硬件環(huán)境和問題規(guī)模是密切相關(guān)的。一般說來，對同等規(guī)模的線性方程組，直接法對計(jì)算機(jī)的要求高于迭代法。對于中等規(guī)

3、模的線性方程組，由于直接法的準(zhǔn)確性和可靠性高，一般都用直接法求解。對于高階方程組和稀疏方程組，用迭代法可避免直接法帶來的高舍入誤差。 計(jì)算機(jī)在電力系統(tǒng)應(yīng)用的初期，曾經(jīng)因?yàn)閮?nèi)存容量的限制采用過迭代法求解電力網(wǎng)絡(luò)的線性方程式組。迭代法的致命缺點(diǎn)是存在收斂性問題。自從稀疏技術(shù)成功地在電力系統(tǒng)應(yīng)用之后，迭代法幾乎完全被所代替。但隨著電力系統(tǒng)規(guī)模的快速擴(kuò)大，使得直接法很難滿足在線應(yīng)用的要求，要求采用并行計(jì)算技術(shù)提高電力系統(tǒng)分析計(jì)算的速度。由于迭代法有較好的并行性，也許會再次得到廣泛的應(yīng)用。 由于電力網(wǎng)絡(luò)結(jié)構(gòu)的特點(diǎn)，在以導(dǎo)納矩陣表示的電力網(wǎng)絡(luò)方程中系數(shù)矩陣和常數(shù)矢量中非零元素非常少，這種情況下的矩陣和

4、矢量是稀疏的。在與稀疏矩陣和稀疏矢量相關(guān)的運(yùn)算中，有零元素參與的運(yùn)算是沒有必要進(jìn)行的，對零元素的存儲也是多余的。所以，可以采用“排零存儲”、“排零運(yùn)算”的辦法，只存儲稀疏矩陣和稀疏矢量中的非零元素及必要的檢索信息，只取這些非零元素來進(jìn)行運(yùn)算，省去對零元素的存儲和與零元素進(jìn)行的運(yùn)算，這樣可以大大減少存儲量，提高計(jì)算速度。這種作法用計(jì)算機(jī)程序來實(shí)現(xiàn)就是稀疏技術(shù)。它包括了稀疏矩陣技術(shù)和稀疏矢量技術(shù)兩方面。和不采用稀疏技術(shù)相比，采用稀疏技術(shù)可以加快計(jì)算速度幾十甚至上百倍，而且對計(jì)算機(jī)的內(nèi)存要求也可以大大降低。電力系統(tǒng)規(guī)模越大，使用稀疏技術(shù)帶來的效益就越明顯?？梢哉f，稀疏技術(shù)的引入是對電力系統(tǒng)計(jì)算技術(shù)的

5、一次革命，使許多原來不能做的電網(wǎng)計(jì)算可以很容易地實(shí)現(xiàn)。 第一節(jié) 線性方程組的迭代解法 一、 線性方程組的迭代解法的思路 用迭代法求解線性方程組就是對方程組進(jìn)行等價變換，構(gòu)造同解方程組，以此構(gòu)造迭代關(guān)系式 （2-1） 式中，稱為迭代矩陣。任取初始矢量，代入式（2-1）中，經(jīng)迭代計(jì)算得到解序列。若解序列收斂，設(shè)的極限為，對迭代式兩邊取極限 即，是方程組的解，此時稱迭代法收斂，否則稱迭代法發(fā)散。迭代法的優(yōu)點(diǎn)是占有存儲空間少，程序?qū)崿F(xiàn)簡單，尤其適用于大型稀疏矩陣；不盡人意之處是要面對判斷迭代是否收斂和收斂速度的問題。 迭代式（2-1）收斂與否完

6、全決定于迭代矩陣的性質(zhì)，與迭代初始值的選取無關(guān)?？梢宰C明迭代矩陣的譜半徑 （2-2） 是迭代收斂的充分必要條件，其中是矩陣的特征根。 因此，稱譜半徑小于1的矩陣為收斂矩陣。計(jì)算矩陣的譜半徑，需要求解矩陣的特征值，通常這是較為繁重的工作?？梢酝ㄟ^計(jì)算矩陣的范數(shù)等方法簡化判斷收斂的工作，其中，計(jì)算矩陣的1范數(shù)和范數(shù)的方法比較簡單。（向量的1范數(shù)等于向量元素絕對值之和，向量的范數(shù)范數(shù)等于向量元素絕對值的最大值。矩陣的1范數(shù)等于矩陣列向量的1范數(shù)的最大值；矩陣的范數(shù)等于矩陣行向量的1范數(shù)的最大值。） （2-3）

7、 （2-4） 式（2-3）、式（2-4）分別是矩陣1范數(shù)和范數(shù)的計(jì)算公式?？梢宰C明，只要迭代矩陣滿足或，就可以判斷迭代序列是收斂的。但要注意的是，當(dāng)或時，可以有，因此不能判斷迭代序列發(fā)散。 在計(jì)算中當(dāng)相鄰兩次的向量誤差的某種范數(shù)小于給定精度時，則停止迭代計(jì)算，并視為方程組的近似解。 二、 雅可比（Jacobi）迭代法 1、 雅可比迭代格式 設(shè)元線性方程組 （2-5） 其矩陣形式為。若將式（2-5）中每個方程的留在方程左邊，其余各項(xiàng)移到方程右邊；方程兩邊除以則得到下列同解方程組： 記構(gòu)造迭代形式

8、 或?qū)懗删仃囆问? （2-6） 式（2-6）稱為雅可比迭代。令 （2-8） （2-9） 得雅克比迭代式的矩陣形式 （2-10） 式中，為雅克比迭代矩陣。 2、 雅可比迭代收斂條件 當(dāng)方程組的系數(shù)矩陣具有某些性質(zhì)時，可直接判定由它生成的雅可比迭代矩陣是收斂的。 定理：若方程組的系數(shù)矩陣，滿足下列條件之一，則其雅可比迭代法是收斂的。 （1）為行對角占優(yōu)陣，即 （2）為列對角占優(yōu)陣，即 定理：若方程組的系數(shù)矩陣為對稱正定

9、陣，并且也為對稱正定，則雅可比迭代收斂。（為的對角線元素組成的對角線矩陣） 3、 雅可比迭代算法 三、 高斯-塞德爾（Gauss-Seidel）迭代法 1、 高斯-塞德爾迭代格式 在雅可比迭代中，的計(jì)算公式是 (2-11) 事實(shí)上，在計(jì)算前，已經(jīng)得到的值，不妨將已算出的分量直接代入迭代式中，及時使用最新計(jì)算出的分量值。因此的計(jì)算公式可改為： (2-12) 式（2-12）稱為高斯—塞德爾迭代式。 2、 高斯—塞德爾迭代的收斂條件 定理：若方程組系數(shù)矩陣A為列或行對角優(yōu)時，則高斯塞德爾迭代收斂

10、。 定理：若方程組系數(shù)矩陣A為對稱正定陣，則高斯塞德爾迭代收斂。 對于方程組，如果由它構(gòu)造高斯-塞德爾迭代和雅可比迭代都收斂，那么，多數(shù)情況下高斯—塞德爾迭代比雅可比迭代的收斂效果要好，但是情況并非總是如此。 3、 高斯—塞德爾迭代算法 四、 逐次超松弛（SOR）迭代法 1、 逐次超松弛迭代格式 方程組的雅可比迭代形式，記其中是下三角矩陣，是上三角矩陣。得高斯-塞德爾的迭代形式： （2-13） 記，有 （2-14） 這樣可視為的修正量，如果將改為加上修正量乘一個因子，迭代格改為：

11、 整理得 　　　 （2-15）　　 這里為修正因子，稱為松弛因子，而式（2-15）稱為松弛迭代。 2、 逐次超松弛迭代收斂的條件 定理：逐次超松弛迭代收斂的必要條件。 定理：若為正定矩陣，則當(dāng)時，逐次超松弛迭代恒收斂。 以上定理給出了逐次超松弛迭代因子的范圍。對于每個給定的方程組，確定究竟取多少為最佳，這是比較困難的問題。 通常，把的迭代稱為亞松弛迭代，把的迭代稱為高斯-塞德爾迭代，而把的迭代稱為松弛迭代。 3、 逐次超松弛迭代算法 　　 第二節(jié) 線性方程組的直接解法 線性方程組可以用消去法直接求解，雖然是很古老的方法，但是計(jì)算實(shí)踐表明，對電力系統(tǒng)

12、來說是很有效的。這是因?yàn)殡娏ο到y(tǒng)中常見的大型線性方程組的系數(shù)矩陣，如導(dǎo)納矩陣是十分稀疏的，所以當(dāng)充分利用矩陣的稀疏性時，直接解法的計(jì)算速度很快。與上節(jié)介紹的迭代法相比，雖然直接解法占用計(jì)算機(jī)的內(nèi)存量要大一些，但是它沒有收斂性問題。 本節(jié)對消去法進(jìn)行一般的數(shù)學(xué)描述，給出適用于電子數(shù)字計(jì)算機(jī)的表達(dá)式，并介紹它的常用變態(tài)形式—因子表解法和三角分解解法。 一、 高斯消去法 高斯順序消去法的基本思想是：對線性代數(shù)方程組所對應(yīng)的增廣矩陣（A|B）進(jìn)行一系列“把某一行元素倍加到另一行上”的初等變換，使得（A|B）中A的對角線以下的元素消去為0，從而使原方程組等價的轉(zhuǎn)化為容易求解的上三角形線性代數(shù)方程組

13、，再通過回代得到上三角形線性代數(shù)方程組的解，即可求得原方程組的解。高斯消去法求解線性方程組分為兩個步驟：消去運(yùn)算（前代運(yùn)算）和回代運(yùn)算。 1、 消去（前代）運(yùn)算 設(shè)有線性方程組： （2-16） 將系數(shù)矩陣和常數(shù)向量合并寫成增廣矩陣： （2-17） 消去運(yùn)算有兩種方法，按列消去和按行消去。首先討論按列消去的過程，其步驟是： 第一步，消去第一列。 首先，把增廣矩陣的第一行規(guī)格化為 1 … （2-18） 式中：

14、 （2-19） 然后，用式（2-18）所表示的行消去的第一列對角線以下各元素，結(jié)果使的第2~n行其他元素化為 （2-20） 式中：上標(biāo)（1）表示該元素第一次運(yùn)算的結(jié)果。這時矩陣變?yōu)椋? 與之對應(yīng)的方程組是,它與同解。矩陣未標(biāo)出的元素為零，下同。 第二步，消去第二列。 首先，把增廣矩陣的第二行規(guī)格化為 0 1 … （2-21） 式中： （2-22） 然后，用式（2-21）所表示的行消去的第二列對角線以下各元素,，，，結(jié)果使的第3~n行其他元素化為 （2

15、-23） 式中：上標(biāo)（2）表示該元素第二次運(yùn)算的結(jié)果。這時矩陣變?yōu)椋? 一般地，在消去第k列時要做以下的運(yùn)算： （2-24） （2-25） 式（2-24）稱為規(guī)格化運(yùn)算，式（2-25）稱為消去運(yùn)算。 經(jīng)過對矩陣的n次消去運(yùn)算，即k從1依次取到n按式（2-24），（2-25）運(yùn)算，使矩陣A對角線以下的元素全部化為零，從而得到增廣矩陣 （2-26） 與之對應(yīng)的方程組是，即 （2-27） 它與原方程組同解。 以上算法首先消去中第一列對角線下的元素，然后消去

16、第二列對角線下的元素，依次直到對角線下的所有元素都被消去為止。這種消去算法稱為按列消去法。 下面介紹按行消去法，它首先消去中第二行對角線左邊的元素，然后消去第三行對角線左邊的元素，依次直到對角線左邊的所有元素都被消去為止。其步驟是： 第一步，首先對增廣矩陣的第一行做規(guī)格化運(yùn)算，結(jié)果為： 1 … （2-28） 式中： （2-29） 第二步，首先用式（2-28）所表示的行消去的第二行對角線左邊的元素，結(jié)果使的第2行其他元素化為 （2-30） 這時矩陣變?yōu)椋? 然后，對增廣矩陣的第

17、二行做規(guī)格化運(yùn)算，變?yōu)椋? 0 1 … （2-31） 式中： （2-32） 這時矩陣變?yōu)椋? 顯然，與之對應(yīng)的方程組是,它與同解。 第三步，首先用式（2-28）所表示的行消去的第三行對角線左邊的第一元素；然后用式（2-31）所表示的行消去的第三行對角線左邊的第二元素；最后用第三行對角線元素對第三行做規(guī)格化運(yùn)算。 一般地，在消去第k行時要做如下的運(yùn)算： （2-33） （2-34） 經(jīng)過n次消去運(yùn)算，得到與式（2-26）相同的增廣矩陣，和與式（2-26）相同的同解

18、方程。 2、 回代運(yùn)算 將方程組展開為： （2-35） 可見，經(jīng)消去運(yùn)算后系數(shù)矩陣變?yōu)橐簧先蔷仃嚵恕；卮\(yùn)算就是由式（2-35）求出原方程解的過程?？梢圆捎冒葱谢卮惴ɑ虬戳谢卮惴?。 按行回代以行自下而上的順序進(jìn)行。其過程為：首先由第個方程得到解： （2-36） 然后，將代入第個方程，解出： （2-37） 再將將，代入第個方程可解出： （2-38） 如此，如已得到的解分量，，…，，得出求解分量的算法

19、 （2-39） 式（2-39）就是按行回代的一般公式。 按列回代的計(jì)算公式是： （2-40） 也是按，，，的順序依次求各位置數(shù)。 二、 因子表法 1、 因子表 從上節(jié)高斯消去過程可以看出①線性方程組常數(shù)項(xiàng)不影響系數(shù)矩陣的消去結(jié)果；②常數(shù)項(xiàng)的消去運(yùn)算只與系數(shù)矩陣的下三角中即將被化為1或0的元素有關(guān)；③回代求方程的解只與消去運(yùn)算完成后的上三角元素有關(guān)。 在實(shí)際計(jì)算中，常常遇到方程需多次求解，每次僅改變常數(shù)項(xiàng)，而系數(shù)矩陣保持不變。在這種情況下，如每次求解都做一次對系數(shù)矩陣和常數(shù)項(xiàng)完整消去運(yùn)算，很明顯將會有大量重復(fù)的運(yùn)算。如果常數(shù)項(xiàng)變化時，只

20、需對常數(shù)項(xiàng)做消去運(yùn)算就行了，這就是因子表法。 因子表就是記錄線性方程組求解過程中消去（前代）和回代運(yùn)算所需數(shù)據(jù)的一種表格。回代運(yùn)算所需數(shù)據(jù)由對系數(shù)矩陣消去運(yùn)算所得的上三角矩陣元素確定。為了對常數(shù)項(xiàng)進(jìn)行消去（前代）運(yùn)算，還必須記錄消去（前代）過程中所需的運(yùn)算數(shù)據(jù)。消去（前代）過程又分為規(guī)格化和消去運(yùn)行，以按列消去為例，由式（2-24）和（2-25）可知，消去（前代）過程對常數(shù)項(xiàng)第個元素的運(yùn)算包括 （2-41） （2-42） 可見，常數(shù)項(xiàng)的消去運(yùn)算只與系數(shù)矩陣的下三角部分和常數(shù)項(xiàng)有關(guān)。將

21、式（2-31）和（2-42）中的運(yùn)算因子按它們下標(biāo)指定的位置放在下三角部分，和消去運(yùn)算得到的上三角矩陣放在一起，就得到了因子表 （2-43） 式（2-43）因子表中對角線元素為消去過程中規(guī)格化為1之前的對角元素；下三角元素為消去過程中消去為0之前的下三角元素。式中，對角線及下三角部分用于對常數(shù)項(xiàng)的消去（前代）運(yùn)算，上三角元素用來進(jìn)行回代元算。因子表也常寫成如下的形式： （2-44） 式中 2、 使用因子表解線性

22、方程組 （1） 形成因子表（按列消去） （2） 對常數(shù)項(xiàng)做消去運(yùn)算 （3） 回代運(yùn)算得方程的解 三、 三角分解法 1、 矩陣的三角分解 設(shè)方陣A可用一個下三角矩陣L與一個單位上三角矩陣U的乘積表示，即： （2-45） 展開為： （2-46） 將式（2-46）右邊兩矩陣相乘，其元素應(yīng)與左邊矩陣相應(yīng)元素的值相等。比較第一行元素，得： （2-47） 可見，L中第一列的對角線元素與A中第一列的對角線元素相同，U中第一行非對角線元素等于A中第一行非對角線元素用對角線元素規(guī)格化以后的值

23、。比較第一列元素，得： （2-48） 可見，L中第一列非對角線元素與A中第一列非對角線元素相同。比較第二行（），得： （2-49） 可見，L中第二列的對角線元素等于A中第二列對角線元素經(jīng)第一次消去后的值。U中第二行非對角線元素等于A中第二行上三角非對角線元素經(jīng)第二次消去后的值。比較第二列（） （2-50） 可見，L中第二列非對角線元素等于A中第二列下三角非對角線元素經(jīng)第一次消去后的值。 以上分析得到的結(jié)論是：三角分解的L矩陣中的下三角元素與式（2-44）因子表的下三角部分（包括對角線元素）相等；U矩陣中的上三角

24、元素與式（2-34）因子表的上三角部分（不包括對角線元素）相等。L矩陣、U矩陣稱為因子表矩陣，可由高斯消去法得到。 另一種三角分解的方法是將A分解為單位下三角矩陣L、對角線矩陣D和單位上三角矩陣的乘積 （2-51） 展開為 （2-52） 式中，如取U與式（2-45）中的U相同；D為角線矩陣，由式（2-45）中L矩陣的對角線元素組成。則式（2-51）中L的非對角元素為式（2-45）中L中的非對角元除以所在列的對角線元素而得。當(dāng)A為對稱矩陣時，有 即，當(dāng)A為對稱矩陣時，式（2-51）中的L和U互為轉(zhuǎn)置。 2、 用三角分解法解線性方程

25、組 設(shè)線性方程組： （2-53） 系數(shù)矩陣分解為，引入中間矢量和，并令： （2-54） （2-55） 則方程組（2-53）變?yōu)? （2-56） 這樣，解線性方程組（2-53）可由以下幾個步驟完成： 1）由式（2-56）求出，稱

26、為前代運(yùn)算。 2）由式（2-55）求出，稱為除法運(yùn)算。 3）由式（2-54）求出，稱為回代運(yùn)算。 （1）前代運(yùn)算 將L分解為一個單位矩陣與一個嚴(yán)格下三角矩陣的和，式（2-56）變?yōu)椋? （2-57） 將式（2-57）展開，得 （2-58） 按式（2-58）寫出求解的計(jì)算流程如式（2-59），稱為按行前代。 （2-59） 式（2-57）展開也可寫成如下的形式： （2-60） 按式（2-60）寫出求解的另一計(jì)算流程為如式（2-61），稱為按列前代。

27、 （2-61） 前代運(yùn)算從下標(biāo)小的元素開始，由前向后進(jìn)行。實(shí)際上就是用對常數(shù)項(xiàng)的消去運(yùn)算。 （2）除法運(yùn)算 按式（2-55） （2-62） （3）回代運(yùn)算 將U分解為一個單位矩陣與一個嚴(yán)格上三角矩陣的和，式（2-54）式變?yōu)椋? （2-63） 將式（2-52）兩邊展開 （2-64） 按式（2-64）寫出求解的計(jì)算流程如式（2-65），稱為按行回代。 （2-65） 式（2-64）也可展開為如下的形式： （2-66）

28、 按式（2-66）寫出求解的另一計(jì)算流程如式（2-67），稱為按列回代。 （2-67） 回代運(yùn)算從下標(biāo)大的元素開始，由后向前進(jìn)行。 可見，利用方程組系數(shù)矩陣三角分解得到的因子表，先用因子表的下三角部分對常數(shù)項(xiàng)做前代運(yùn)算，然后用因子表的對角線部分對回代的結(jié)果做除法運(yùn)算，再用因子表的上三角部分對除法運(yùn)算的結(jié)果做回代運(yùn)算，就得到了方程的解。 第三節(jié) 稀疏存儲技術(shù) 稀疏矩陣是零元素占有很大比例的矩陣。電力網(wǎng)絡(luò)的導(dǎo)納矩陣就是稀疏矩陣，而且網(wǎng)絡(luò)越大稀疏程度越大。在求解電力網(wǎng)絡(luò)方程時，利用稀疏技術(shù)進(jìn)行“排零存儲，排零計(jì)算”可以節(jié)省大量的存儲空間和計(jì)算時間。 一、稀疏

29、存儲 稀疏存儲就是只存儲矩陣中的非零元素，有多種方法，其中三角檢索存儲方法特別適合于矩陣三角分解的算法。這里介紹按行存儲上三角部分非零元素，按列存儲下三角部分非零元素的方法。令矩陣A是n階方陣，定義數(shù)組： U：大小等于A的上三角部分非零元素個數(shù)的一維數(shù)組，用于按行存儲A的上三角部分非零元素的值； JU：大小等于A的上三角部分非零元素個數(shù)的一維數(shù)組，用于按行存儲A的上三角部分非零元素的列號； IU：大小等于A的階數(shù)（行數(shù)）的一維數(shù)組，用于存儲A中上三角部分每行第一個非零元素在U中的位置； L：大小等于A的下三角部分非零元素個數(shù)的一維數(shù)組，用于按列存儲A的下三角部分非零元素的值； IL

30、：大小等于A的下三角部分非零元素個數(shù)的一維數(shù)組，用于按列存儲A的下三角部分非零元素的行號； JL：大小等于A的階數(shù)（列數(shù)）的一維數(shù)組，用于存儲A中下三角部分每列第一個非零元素在L中的位置； D：大小等于A的階數(shù)的一維數(shù)組，用于存儲A中對角線元素的值。 如方陣： 采用三角檢索存儲方法時各數(shù)組的內(nèi)容如下： 序號 1 2 3 4 U JU 2 4 3 IU 1 3 4 4 L IL 2 4 4 JL 1 2 3 4 D 用這種方式存儲了矩陣元素后，檢索可采用如下的流程：

31、 （2-68） 二、稀疏存儲技術(shù)在求解線性方程組中的應(yīng)用 1.形成因子表 設(shè)線性方程組系數(shù)矩陣A的階數(shù)為n，為其第行，第列的元素，由第二節(jié)所述因子表和高斯消去法的關(guān)系，先寫出常規(guī)不采用稀疏存儲技術(shù)時形成因子表的算法流程： （2-69） 式（2-69）所示流程執(zhí)行完畢，矩陣A的上三角部分就是式（2-45）中矩陣U的上三角元素；矩陣A的下三角部分就是式（2-45）中矩陣L的下三角元素。在上算法中，顯然，如果，規(guī)格化計(jì)算不必做；如果或，消去計(jì)算不必做。如果要實(shí)現(xiàn)排零計(jì)算，上述算法需要添加判斷語句，反而會增加計(jì)算量。 如果系數(shù)矩陣按三角檢索方法存儲，零元素已排除，不僅

32、節(jié)省了存儲空間，計(jì)算時也不必做零元素判斷，從而也節(jié)省了計(jì)算時間。 下面介紹的算法假定線性方程組系數(shù)矩陣已按三角檢索方法存儲，數(shù)組U、IU、JU、L、IL、JL、D開始時存儲系數(shù)矩陣，因子分解后存儲因子表。并假定已為在分解過程中新生成的非零元素預(yù)留了空間。算法流程如下： （2-70） （2-70）流程執(zhí)行完畢數(shù)組U、D、L中存放的數(shù)據(jù)為式（2-51）三角分解式矩陣U、D、L的元素。 2.前代運(yùn)算 按式（2-60）所示算法，寫出采用三角檢索存儲方式的按列前代算法流程 （2-71） 3、除法運(yùn)算 （2-72） 4、回代運(yùn)算 按

33、式（2-5）所示算法，寫出采用三角檢索存儲方式的按行回代算法流程 （2-73） 第四節(jié) 因子表法的圖形描述 電力網(wǎng)絡(luò)節(jié)的節(jié)點(diǎn)導(dǎo)納矩陣與電力網(wǎng)絡(luò)的結(jié)構(gòu)有對應(yīng)關(guān)系，其上三角或下三角中的非對角元非零元素與電力網(wǎng)絡(luò)的支路一一對應(yīng)。因子分解得到的因子表矩陣也可與一個圖對應(yīng)起來。本節(jié)利用網(wǎng)絡(luò)圖形象地說明稀疏矩陣的因子表分解和前代、回代過程，進(jìn)而引出稀疏矢量技術(shù)。 一、定義和術(shù)語 令A(yù)是對稱陣，其非零元素的分布為： （2-74） U是A的因子表上三角矩陣，且A=UTDU。U的非零元素分布為： （2-75） 式中，“”表

34、示在因子分解的過程中出現(xiàn)的新非零元素，稱為注入元。 將A與一由邊和邊兩端的節(jié)點(diǎn)組成的圖對應(yīng)起來，并做如下定義： A圖：與矩陣A的上三角部分有相同網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的網(wǎng)絡(luò)圖。節(jié)點(diǎn)號與A的行號相對應(yīng)。邊與A的上三角部分非零非對角元相對應(yīng)。 有向A圖：在A圖上，將每條邊規(guī)定方向?yàn)閺男√柟?jié)點(diǎn)指向大號節(jié)點(diǎn)所得到的圖。小號節(jié)點(diǎn)為邊的發(fā)點(diǎn)，大號節(jié)點(diǎn)為邊的收點(diǎn)。 賦權(quán)有向A圖 A圖 有向A圖 賦權(quán)有向A圖：在有向A圖上，與A中非零非對角元對應(yīng)的邊稱為節(jié)點(diǎn)間的互邊，并賦邊權(quán)為該元素的值。在有向A圖節(jié)點(diǎn)上添加接地邊，稱之為節(jié)點(diǎn)的自邊，并用A的對角元值賦邊權(quán)值。這樣得到的圖為賦權(quán)

35、有向A圖。 同樣地，因子表矩陣U也可用圖來描述，其因子圖、有向因子圖、賦權(quán)有向因子圖的定義與A圖、有向A圖、賦權(quán)有向A圖的定義類似。 因子圖 有向因子圖 賦權(quán)有向因子圖 二、因子分解過程的圖形描述 因子分解過程從小號節(jié)點(diǎn)到大號節(jié)點(diǎn)依次進(jìn)行，為規(guī)格化和消去兩個步驟。 1、規(guī)格化運(yùn)算 第次消去的規(guī)格化運(yùn)算就是用第行的對角元去除第行上三角部分的所用元素，零元素不必計(jì)算。 （2-76） 參見圖，規(guī)格化運(yùn)算就是用式（2-76）對節(jié)點(diǎn)發(fā)出的所有互邊的邊權(quán)進(jìn)行修正。在圖上就是對節(jié)點(diǎn)發(fā)出的所有互邊的邊權(quán)修正為除以節(jié)點(diǎn)的自邊權(quán)后的值。 規(guī)格化運(yùn)算不增加

36、新的邊，即不產(chǎn)生注入元。 2、消去運(yùn)算 消去運(yùn)算只需在行（）與列（）軸線相交的位置上進(jìn)行，公式為： （2-77） 由于A是對稱陣，節(jié)點(diǎn)的列元素可用規(guī)格化后的行元素代替，即上式變?yōu)椋? （2-78） 同樣由于A是對稱陣，消去運(yùn)算只需在上三角部分進(jìn)行（消去后下三角部分元素與上三角部分對稱元素相等），所以式（2-78）中每個元素的列號都大于行號，即。 當(dāng)時，是對對角元的消去運(yùn)算，式（2-78）變?yōu)椋? （2-79） 式（2-79）的作用是修正節(jié)點(diǎn)發(fā)出的所有互邊的收點(diǎn)

37、的自邊權(quán)，即將收點(diǎn)的自邊權(quán)修正為減去互邊權(quán)的平方乘與節(jié)點(diǎn)的自邊權(quán)的積后的值。 當(dāng)時，是對上三角部分的非對角元的消去元算。在圖上就是對節(jié)點(diǎn)發(fā)出的所有互邊的收點(diǎn)兩兩之間的互邊進(jìn)行修正。按式（2-78），對節(jié)點(diǎn)之間的互邊修正的公式為： （2-80） 可見，對非對角元消去就是將節(jié)點(diǎn)發(fā)出的所有互邊的收點(diǎn)兩兩之間的互邊權(quán)值修正為減去兩條相夾邊邊權(quán)與節(jié)點(diǎn)自邊權(quán)三者的乘積后的值。如兩個收點(diǎn)之間原來無互邊，消去運(yùn)算后會生成新的互邊，這就是因子分解過程中出現(xiàn)的注入元。 當(dāng)所用節(jié)點(diǎn)按從小到大的順序做完規(guī)格化和消去運(yùn)算后，賦權(quán)有向A圖就變成了賦權(quán)有向因子圖。 3、算法流程

38、總結(jié) 在圖上進(jìn)行因子分解就是以賦權(quán)有向A圖為起始，按節(jié)點(diǎn)號從小到大的順序執(zhí)行下面的操作。如已執(zhí)行到節(jié)點(diǎn)： （1）規(guī)格化運(yùn)算，將節(jié)點(diǎn)發(fā)出的所用互邊權(quán)值修正為除以節(jié)點(diǎn)自邊權(quán)值后的值。 （2）對角元消去運(yùn)算，將節(jié)點(diǎn)發(fā)出的所用互邊的收點(diǎn)的自邊權(quán)值修正為減去該收點(diǎn)與節(jié)點(diǎn)的互邊權(quán)值的平方與節(jié)點(diǎn)自邊權(quán)值的乘積后的值。 （3）非對角元消去運(yùn)算，將節(jié)點(diǎn)發(fā)出的所用互邊的收點(diǎn)兩兩之間的互邊權(quán)值修正為減去該兩收點(diǎn)分別與節(jié)點(diǎn)的互邊權(quán)值及節(jié)點(diǎn)自邊權(quán)值三者乘積后的值。 三、前代、回代過程的圖形描述 1、前代過程 當(dāng)A為對稱矩陣時L=UT ，在按列前代流程（2-61）中由代替，前代過程可表述為 將算法與因

39、子矩陣和因子圖對應(yīng)起來，有： （1）對應(yīng)節(jié)點(diǎn)號； （2）前代的順序是從小號節(jié)點(diǎn)到大號節(jié)點(diǎn)，； （3）之間的邊由指向，是發(fā)點(diǎn)，是收點(diǎn)； （4）為之間互邊權(quán)值，對應(yīng)之間無互邊，在圖中不出現(xiàn)； （5）z元素的初值為b中的元素； 如果定義為節(jié)點(diǎn)的點(diǎn)位，其初值為第個常數(shù)項(xiàng)的值。上述流程就是在圖上用小號節(jié)點(diǎn)的點(diǎn)位修正大號節(jié)點(diǎn)的點(diǎn)位的操作，修正公式為： （2-81） 可見，前代過程就是以節(jié)點(diǎn)號從小到大的順序?qū)?jié)點(diǎn)發(fā)出的邊的收點(diǎn)的點(diǎn)位按（2-81）修正的過程。的邊不在圖上出現(xiàn)，隱含地使用了稀疏技術(shù)。若小號節(jié)點(diǎn)的點(diǎn)位，也不必修正。 2、規(guī)格化過程 將前代結(jié)束后

40、規(guī)格化就是各點(diǎn)的點(diǎn)位除以因子圖上各自節(jié)點(diǎn)的自邊權(quán)值： （2-82） 3、回代過程 將第二節(jié)按列回代流程（2-67）重寫如下： 將算法與結(jié)合因子矩陣和因子圖對應(yīng)起來，有： （1）對應(yīng)節(jié)點(diǎn)號； （2）回代的順序是從大號節(jié)點(diǎn)到小號節(jié)點(diǎn)，； （3）之間的邊由指向，是發(fā)點(diǎn)，是收點(diǎn)； （4）為之間互邊權(quán)值，對應(yīng)之間無互邊，在圖中不出現(xiàn)； （5）x的元素初值是規(guī)格化運(yùn)算后各節(jié)點(diǎn)的點(diǎn)位； 上述流程就是在圖上用大號節(jié)點(diǎn)點(diǎn)位修正小號節(jié)點(diǎn)點(diǎn)位的操作，修正公式為： （2-83） 可見，回代過程就是以節(jié)點(diǎn)號從大到小的順序?qū)χ赶?/p>

41、節(jié)點(diǎn)的邊的發(fā)點(diǎn)的點(diǎn)位按（2-83）修正的過程。的邊不在圖上出現(xiàn)，隱含地使用了稀疏技術(shù)。若大號節(jié)點(diǎn)的點(diǎn)位，不必修正。 4、流程總結(jié) （1）將常數(shù)矢量（獨(dú)立矢量）的元素值賦值為賦權(quán)有向因子圖相應(yīng)節(jié)點(diǎn)的初始點(diǎn)位； （2）以節(jié)點(diǎn)號從小到大的順序?qū)?jié)點(diǎn)發(fā)出的邊的收點(diǎn)的點(diǎn)位按（2-81）修正。如已前代到節(jié)點(diǎn)，則將節(jié)點(diǎn)對應(yīng)的所用收點(diǎn)的點(diǎn)位修正為減去該收點(diǎn)與節(jié)點(diǎn)的互邊權(quán)值與節(jié)點(diǎn)的點(diǎn)位的乘積后的值。如果節(jié)點(diǎn)的點(diǎn)位為零，則不必修正； （3）按（2-82）式對點(diǎn)位規(guī)格化，點(diǎn)位為零不必計(jì)算； （4）以節(jié)點(diǎn)號從大到小的順序?qū)χ赶蚬?jié)點(diǎn)的邊的發(fā)點(diǎn)的點(diǎn)位按（2-83）修正。如已回代到節(jié)點(diǎn)，則將節(jié)點(diǎn)對應(yīng)的所用發(fā)點(diǎn)的點(diǎn)

42、位修正為減去該發(fā)點(diǎn)與節(jié)點(diǎn)的互邊權(quán)值與節(jié)點(diǎn)的點(diǎn)位的乘積后的值。如果節(jié)點(diǎn)的點(diǎn)位為零，則不必修正。 （5）修正運(yùn)算結(jié)算后，各點(diǎn)的點(diǎn)位值就是方程組的解。 由上可見，將因子表分解的每一步過程都是在圖的節(jié)點(diǎn)、節(jié)點(diǎn)發(fā)出的邊、收點(diǎn)、收點(diǎn)間的邊上進(jìn)行的。由于零元素不在圖上出現(xiàn)，所以在圖上進(jìn)行因子分解自然地實(shí)現(xiàn)了“排零存儲、排零運(yùn)算”。 前代運(yùn)算是用小號節(jié)點(diǎn)的點(diǎn)位去修正所發(fā)出的邊的收點(diǎn)的電位；回代元算是用大號節(jié)點(diǎn)的電位去修正該節(jié)點(diǎn)對應(yīng)的所用發(fā)點(diǎn)的電位。由于導(dǎo)納矩陣的零元素沒有圖中對應(yīng)的邊，所以圖上的前代、回代運(yùn)算自然就“排零運(yùn)算”了。 第五節(jié) 稀疏矢量技術(shù) 上節(jié)用圖上因子分解的方法說明了在因子分解過程中

43、如何利用稀疏矩陣的特點(diǎn)。在因子分解的每一步，不論是規(guī)格化運(yùn)算還是消去運(yùn)算，都是在某點(diǎn)相聯(lián)的邊上進(jìn)行的，這在矩陣中相當(dāng)于以行和列為軸線，只取用軸線上的非零元素以及只在行列軸線上的非零元素相交叉的位置上進(jìn)行操作運(yùn)算。計(jì)算中自然地實(shí)現(xiàn)了排零計(jì)算。 在前代回代過程中，如果前代之前獨(dú)立矢量b中只有少數(shù)是非零元素，即圖上只有少數(shù)的節(jié)點(diǎn)的點(diǎn)位不是零，大多數(shù)節(jié)點(diǎn)的點(diǎn)位都是零，由圖上的前代過程可知，前代中對零點(diǎn)位的點(diǎn)進(jìn)行的前代操作是多余的，可以省略。如果在解矢量x中，我們只對其中的少數(shù)幾個元素感興趣，解矢量中大多數(shù)元素盡管回代后其值不等于零，但我們對它們不感興趣，即我們只取用回代后點(diǎn)位中少數(shù)感興趣的節(jié)點(diǎn)的點(diǎn)位

44、。則在回代過程中與這些待求點(diǎn)位無關(guān)的回代操作也是多余的，可以省略。在前代回代中，哪些計(jì)算步是必不可少的，哪些計(jì)算步是多余的，這是稀疏矢量法要解決的間題。 仍以對稱矩陣的情況討論。 一、概念和定義 稀疏獨(dú)立矢量：一個給定的只有少量非零元素的獨(dú)立矢量。 稀疏解矢量：一個只有少數(shù)元素待求的解矢量。 道路樹：在有向因子圖上，僅取從每個節(jié)點(diǎn)發(fā)出的邊的收點(diǎn)為最小號的邊得到的有向樹。在連通的A圖形成的因子圖上。道路樹只有一顆，且只有一個根節(jié)點(diǎn)。根節(jié)點(diǎn)是編號最大的節(jié)點(diǎn)，無發(fā)出的邊。 點(diǎn)的路：在道路樹上節(jié)點(diǎn)沿道路樹到根節(jié)點(diǎn)所經(jīng)過的路徑，是道路樹的一個子集。每個點(diǎn)的路只有一條。 點(diǎn)集的路集：一個點(diǎn)集

45、中所有點(diǎn)的路的并集。也是道路樹的一個子樹。 二、性質(zhì)和定理 性質(zhì)1：有向因子圖上任一點(diǎn)發(fā)出的邊的收點(diǎn)必在該點(diǎn)的路上。 性質(zhì)2：有向因子圖上任何邊的兩個端節(jié)點(diǎn)的路集就是其中編號小的節(jié)點(diǎn)的路。即邊的大號節(jié)點(diǎn)一定在小號節(jié)點(diǎn)的路上。 性質(zhì)3：如果有向因子圖中任何一組點(diǎn)集中的節(jié)點(diǎn)兩兩之間都有邊，則該點(diǎn)集的路集就是該點(diǎn)集中編號最小的節(jié)點(diǎn)的路。 定理1：在有向因子圖上，前代運(yùn)算只在稀疏獨(dú)立矢量中非零元點(diǎn)集的路集上進(jìn)行。（那些點(diǎn)需要做前代） 定理2：路集上任一點(diǎn)的前代運(yùn)算必須在路集上比該點(diǎn)編號小且其路經(jīng)過該點(diǎn)的點(diǎn)的前代完成之后才能進(jìn)行，而路集中分支點(diǎn)以上的幾條路先做哪個沒有關(guān)系。（做前代的順序

46、） 定理3：在有向因子圖上，回代運(yùn)算只在稀疏解矢量的待解元素的點(diǎn)集的路集上進(jìn)行。（那些點(diǎn)需要做回代） 定理4：任一點(diǎn)的回代運(yùn)算都必須在該點(diǎn)的道路上比該點(diǎn)編號大的點(diǎn)的回代運(yùn)算完成之后進(jìn)行，而路集中分支點(diǎn)以上幾條路先沿那條路回代沒有關(guān)系。（做回代的順序） 注意：定理1、3說明了那些點(diǎn)需要做前代、回代運(yùn)算，使用時一是要注意前代、回代的順序，二是要注意前代、回代運(yùn)算還是要按賦權(quán)有向因子圖節(jié)點(diǎn)之間的關(guān)系進(jìn)行，而不是按路集圖節(jié)點(diǎn)間的關(guān)系進(jìn)行。 三、路集的形成 以上可見，稀疏矢量技術(shù)使用的基礎(chǔ)是形成稀疏獨(dú)立矢量和稀疏解矢量的路集。 形成單個節(jié)點(diǎn)的路的算法流程： （2-84） 式中：IU(

47、p)：因子表矩陣中節(jié)點(diǎn)p對應(yīng)的行的上三角部分第一各個非零非對角元在U中的位置；JU(IU(p))：IU(p)對應(yīng)的列號，有向因子圖上即節(jié)點(diǎn)p發(fā)出的最小節(jié)點(diǎn)號。 形成點(diǎn)集的路集的算法流程： （2-85） 式中：G為點(diǎn)集。 第六節(jié) 節(jié)點(diǎn)優(yōu)化編號 稀疏技術(shù)的核心關(guān)鍵有兩點(diǎn)，一是排零存儲和排零運(yùn)算，二是節(jié)點(diǎn)優(yōu)化編號。排零存儲和排零運(yùn)算有效地避免對計(jì)算結(jié)果沒有影響的存儲和計(jì)算，大大提高程序的計(jì)算效力。節(jié)點(diǎn)的編號是指節(jié)點(diǎn)在導(dǎo)納矩陣中的排列順序，對于計(jì)算效率的影響也是至關(guān)重要的，它直接影響到矩陣A的因子表矩陣的稀疏度。嚴(yán)格地說，最優(yōu)編號是一個組合優(yōu)化問題，求其最優(yōu)解是困難的，

48、但在實(shí)際工程中，有許多實(shí)用的次優(yōu)的編號方法得到了廣泛的應(yīng)用。 1.Tinney-1編號法（靜動態(tài)編號法） 這種方法也稱靜態(tài)節(jié)點(diǎn)優(yōu)化編號方法。這種方法統(tǒng)計(jì)每一個節(jié)點(diǎn)的出線度，即該節(jié)點(diǎn)和其它節(jié)點(diǎn)相連結(jié)的支路數(shù)，然后按節(jié)點(diǎn)出線度由小到大按順序進(jìn)行編號。對于出線度相同的節(jié)點(diǎn)。哪個排在前邊是任意的。這種編一號方法的出發(fā)點(diǎn)是認(rèn)為在圖上因子分解的過程中出線度小的節(jié)點(diǎn)消去時產(chǎn)生注入元的可能性也小。 這種編號方法簡單，但編號效果較差。由因子分解過程可知：①出線度少的節(jié)點(diǎn)消去后產(chǎn)生的注入元不一定比出線度多的節(jié)點(diǎn)消去后產(chǎn)生的注入元少；②已編號的節(jié)點(diǎn)消去后，未消去節(jié)點(diǎn)的出線度會發(fā)生變化?；诘冖邳c(diǎn)，引出了半動態(tài)

49、節(jié)點(diǎn)優(yōu)化編號算法。 2.Tinney-2編號法（半動態(tài)編號法） 這種方法也稱最小度算法。首先統(tǒng)計(jì)所有節(jié)點(diǎn)的出線度，然后選出出線度最小的節(jié)點(diǎn)先進(jìn)行編號。編號后，用因子分解的辦法消去該節(jié)點(diǎn)，消去時只進(jìn)行網(wǎng)絡(luò)結(jié)構(gòu)變化的處理，而不進(jìn)行實(shí)際的消去運(yùn)算。在消去節(jié)點(diǎn)剩下的子圖上重復(fù)上述編號過程，直到所有節(jié)點(diǎn)都編了號為止。 這種方法可使注入元數(shù)大大減少，而程序復(fù)雜性和計(jì)算量又增加不多，是一種使用十分廣泛的編號方法。但是，由于每步編號仍按最小出線度作為編號準(zhǔn)則，而出線度最少不等于消去該節(jié)點(diǎn)時產(chǎn)生的注入元最少，因此。也可以按產(chǎn)生注入元最少作為準(zhǔn)則來編號，這就是動態(tài)節(jié)點(diǎn)優(yōu)化編號方法。 3.Tinney-3編

50、號法（動態(tài)編號法） 動態(tài)節(jié)點(diǎn)優(yōu)化編號法和上面的Tinney-2編號的不同之處是對所有待編號的節(jié)點(diǎn)，統(tǒng)計(jì)消去該節(jié)點(diǎn)時產(chǎn)生的注入元數(shù)目，并以該數(shù)目最小為優(yōu)先編號的準(zhǔn)則。節(jié)點(diǎn)編號后，將其消去，在剩下的子圖上重復(fù)上述編號過程，直到所有節(jié)點(diǎn)都編了號為止。 這種方法在每步編號前都要對所有待編號節(jié)點(diǎn)統(tǒng)計(jì)消去后產(chǎn)生的注入元數(shù)，程序的復(fù)雜程度和計(jì)算量都很大，而最終編號結(jié)果相對于Tinney-2的結(jié)果略有改善，效益改善并不特別明顯，所以Tinney-3編號沒有Tinney-2編號用的普遍。 4.Tinney-2編號法流程和算法 （1） 進(jìn)行隨意的人工編號 （2） 統(tǒng)計(jì)原始網(wǎng)絡(luò)各節(jié)點(diǎn)所連接的支路數(shù)，并保

51、存各節(jié)點(diǎn)連接的支路的對端節(jié)點(diǎn)號。 （3） 找出未優(yōu)化編號的網(wǎng)絡(luò)中連接支路最少的接點(diǎn)，如為k。 （4） 修正消去節(jié)點(diǎn)k后新網(wǎng)絡(luò)各節(jié)點(diǎn)連接的支路數(shù)和對端節(jié)點(diǎn)號。做法是：①與節(jié)點(diǎn)k相連的節(jié)點(diǎn)的連接支路數(shù)-1，并在這些節(jié)點(diǎn)的對端節(jié)點(diǎn)中去掉k。②與節(jié)點(diǎn)k相連的節(jié)點(diǎn)每兩兩之間如果原來沒有支路，則此兩個節(jié)點(diǎn)的連接支路數(shù)+1，并將節(jié)點(diǎn)號分別保存在對端節(jié)點(diǎn)號中。 （5） 返回（3），直到所有節(jié)點(diǎn)都參與了優(yōu)化。 Tinney-2節(jié)點(diǎn)優(yōu)化編號的算法流程如下 （2-86） 式中：n：節(jié)點(diǎn)數(shù)； LN(n)：一維數(shù)組，按原始節(jié)點(diǎn)編號存放節(jié)點(diǎn)相連的支路（節(jié)點(diǎn)）數(shù)，不包括接地支路； NN(n)()：二維動態(tài)數(shù)組，存放節(jié)點(diǎn)相連接的節(jié)點(diǎn)。第二維在執(zhí)行過程中可擴(kuò)展； NP(n)：一維數(shù)組，開始時存放原始節(jié)點(diǎn)編號順序，執(zhí)行完后存放優(yōu)化后的節(jié)點(diǎn)編號順序。 作業(yè)： 1、 加文件輸入、輸出部分，編制高斯-賽德爾迭代法求解線性方程組的計(jì)算機(jī)程序； 2、 分別用三種節(jié)點(diǎn)優(yōu)化編號法重新排列節(jié)點(diǎn)順序，重新形成節(jié)點(diǎn)導(dǎo)納矩陣，并做三角分解，比較三種方法的效果。 3、 編寫采用稀疏技術(shù)的求解線性方程組的計(jì)算機(jī)程序；