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

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

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

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

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

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

6、全決定于迭代矩陣的性質(zhì)，與迭代初始值的選取無關(guān)?？梢宰C明迭代矩陣的譜半徑 （2-2） 是迭代收斂的充分必要條件，其中是矩陣的特征根。 因此，稱譜半徑小于1的矩陣為收斂矩陣。計算矩陣的譜半徑，需要求解矩陣的特征值，通常這是較為繁重的工作?？梢酝ㄟ^計算矩陣的范數(shù)等方法簡化判斷收斂的工作，其中，計算矩陣的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ù)的計算公式?？梢宰C明，只要迭代矩陣滿足或，就可以判斷迭代序列是收斂的。但要注意的是，當或時，可以有，因此不能判斷迭代序列發(fā)散。 在計算中當相鄰兩次的向量誤差的某種范數(shù)小于給定精度時，則停止迭代計算，并視為方程組的近似解。 二、 雅可比（Jacobi）迭代法 1、 雅可比迭代格式 設(shè)元線性方程組 （2-5） 其矩陣形式為。若將式（2-5）中每個方程的留在方程左邊，其余各項移到方程右邊；方程兩邊除以則得到下列同解方程組： 記構(gòu)造迭代形式

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

9、陣，并且也為對稱正定，則雅可比迭代收斂。（為的對角線元素組成的對角線矩陣） 3、 雅可比迭代算法 三、 高斯-塞德爾（Gauss-Seidel）迭代法 1、 高斯-塞德爾迭代格式 在雅可比迭代中，的計算公式是 (2-11) 事實上，在計算前，已經(jīng)得到的值，不妨將已算出的分量直接代入迭代式中，及時使用最新計算出的分量值。因此的計算公式可改為： (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、 逐次超松弛迭代收斂的條件 定理：逐次超松弛迭代收斂的必要條件。 定理：若為正定矩陣，則當時，逐次超松弛迭代恒收斂。 以上定理給出了逐次超松弛迭代因子的范圍。對于每個給定的方程組，確定究竟取多少為最佳，這是比較困難的問題。 通常，把的迭代稱為亞松弛迭代，把的迭代稱為高斯-塞德爾迭代，而把的迭代稱為松弛迭代。 3、 逐次超松弛迭代算法 　　 第二節(jié) 線性方程組的直接解法 線性方程組可以用消去法直接求解，雖然是很古老的方法，但是計算實踐表明，對電力系統(tǒng)

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

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

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

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

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

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

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

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

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

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

22、方程組 （1） 形成因子表（按列消去） （2） 對常數(shù)項做消去運算 （3） 回代運算得方程的解 三、 三角分解法 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中的非對角元除以所在列的對角線元素而得。當A為對稱矩陣時，有 即，當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、為前代運算。 2）由式（2-55）求出，稱為除法運算。 3）由式（2-54）求出，稱為回代運算。 （1）前代運算 將L分解為一個單位矩陣與一個嚴格下三角矩陣的和，式（2-56）變?yōu)椋? （2-57） 將式（2-57）展開，得 （2-58） 按式（2-58）寫出求解的計算流程如式（2-59），稱為按行前代。 （2-59） 式（2-57）展開也可寫成如下的形式： （2-60） 按式（2-60）寫出求解的另一計算流程為如式（2-61），稱為按列前代。

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

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

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ī)格化計算不必做；如果或，消去計算不必做。如果要實現(xiàn)排零計算，上述算法需要添加判斷語句，反而會增加計算量。 如果系數(shù)矩陣按三角檢索方法存儲，零元素已排除，不僅

32、節(jié)省了存儲空間，計算時也不必做零元素判斷，從而也節(jié)省了計算時間。 下面介紹的算法假定線性方程組系數(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.前代運算 按式（2-60）所示算法，寫出采用三角檢索存儲方式的按列前代算法流程 （2-71） 3、除法運算 （2-72） 4、回代運算 按

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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