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

第二章 電力網(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ò)模型常為非線性潮流方程，而非線性潮流方程也必須通過(guò)求解線性的修正方程才能得到其解。所以，無(wú)論是電力系統(tǒng)穩(wěn)態(tài)分析，還是暫態(tài)分析幾乎都會(huì)涉及線性方程組的求解問(wèn)題，而且線性方程組的求解往往是計(jì)算量最大的一部份工作。所以，研究線性方程組的求解技術(shù)對(duì)電力系統(tǒng)分析計(jì)算有重要的意義。線性方程組的解法可歸納為直接法和迭代法。從理論上來(lái)說(shuō)，假定每一步運(yùn)算過(guò)程中沒(méi)有舍入誤差，直接法經(jīng)過(guò)有限次運(yùn)算，最后得到方程組的解就是精確解。但是，這只是理想化的假定，在計(jì)算過(guò)程中，完全杜絕舍入誤差是不可能的，只能控制和約束由有限位算術(shù)運(yùn)算帶來(lái)的舍入誤差的增長(zhǎng)和危害，這樣直接法得到的解也不一定是絕對(duì)精確的。迭代法就是用某種極限過(guò)程去逐步逼近線性方程組精確解的方法。該方法具有對(duì)計(jì)算機(jī)的存貯單元需求少，程序設(shè)計(jì)簡(jiǎn)單、原始系數(shù)矩陣在計(jì)算過(guò)程中不變等優(yōu)點(diǎn)，是求解大型稀疏系數(shù)矩陣方程組的重要方法。迭代法不是用有限步運(yùn)算求精確解，而是通過(guò)迭代得到滿足一定精度要求的方程組的近似解。在數(shù)值計(jì)算歷史上，直接解法和迭代解法交替生輝。一種解法的興旺與計(jì)算機(jī)的硬件環(huán)境和問(wèn)題規(guī)模是密切相關(guān)的。一般說(shuō)來(lái)，對(duì)同等規(guī)模的線性方程組，直接法對(duì)計(jì)算機(jī)的要求高于迭代法。對(duì)于中等規(guī)模的線性方程組，由于直接法的準(zhǔn)確性和可靠性高，一般都用直接法求解。對(duì)于高階方程組和稀疏方程組，用迭代法可避免直接法帶來(lái)的高舍入誤差。計(jì)算機(jī)在電力系統(tǒng)應(yīng)用的初期，曾經(jīng)因?yàn)閮?nèi)存容量的限制采用過(guò)迭代法求解電力網(wǎng)絡(luò)的線性方程式組。迭代法的致命缺點(diǎn)是存在收斂性問(wèn)題。自從稀疏技術(shù)成功地在電力系統(tǒng)應(yīng)用之后，迭代法幾乎完全被所代替。但隨著電力系統(tǒng)規(guī)模的快速擴(kuò)大，使得直接法很難滿足在線應(yīng)用的要求，要求采用并行計(jì)算技術(shù)提高電力系統(tǒng)分析計(jì)算的速度。由于迭代法有較好的并行性，也許會(huì)再次得到廣泛的應(yīng)用。由于電力網(wǎng)絡(luò)結(jié)構(gòu)的特點(diǎn)，在以導(dǎo)納矩陣表示的電力網(wǎng)絡(luò)方程中系數(shù)矩陣和常數(shù)矢量中非零元素非常少，這種情況下的矩陣和矢量是稀疏的。在與稀疏矩陣和稀疏矢量相關(guān)的運(yùn)算中，有零元素參與的運(yùn)算是沒(méi)有必要進(jìn)行的，對(duì)零元素的存儲(chǔ)也是多余的。所以，可以采用“排零存儲(chǔ)”、“排零運(yùn)算”的辦法，只存儲(chǔ)稀疏矩陣和稀疏矢量中的非零元素及必要的檢索信息，只取這些非零元素來(lái)進(jìn)行運(yùn)算，省去對(duì)零元素的存儲(chǔ)和與零元素進(jìn)行的運(yùn)算，這樣可以大大減少存儲(chǔ)量，提高計(jì)算速度。這種作法用計(jì)算機(jī)程序來(lái)實(shí)現(xiàn)就是稀疏技術(shù)。它包括了稀疏矩陣技術(shù)和稀疏矢量技術(shù)兩方面。和不采用稀疏技術(shù)相比，采用稀疏技術(shù)可以加快計(jì)算速度幾十甚至上百倍，而且對(duì)計(jì)算機(jī)的內(nèi)存要求也可以大大降低。電力系統(tǒng)規(guī)模越大，使用稀疏技術(shù)帶來(lái)的效益就越明顯?？梢哉f(shuō)，稀疏技術(shù)的引入是對(duì)電力系統(tǒng)計(jì)算技術(shù)的一次革命，使許多原來(lái)不能做的電網(wǎng)計(jì)算可以很容易地實(shí)現(xiàn)。第一節(jié) 線性方程組的迭代解法一、 線性方程組的迭代解法的思路用迭代法求解線性方程組就是對(duì)方程組進(jìn)行等價(jià)變換，構(gòu)造同解方程組，以此構(gòu)造迭代關(guān)系式 （2-1）式中，稱為迭代矩陣。任取初始矢量，代入式（2-1）中，經(jīng)迭代計(jì)算得到解序列。若解序列收斂，設(shè)的極限為，對(duì)迭代式兩邊取極限即，是方程組的解，此時(shí)稱迭代法收斂，否則稱迭代法發(fā)散。迭代法的優(yōu)點(diǎn)是占有存儲(chǔ)空間少，程序?qū)崿F(xiàn)簡(jiǎn)單，尤其適用于大型稀疏矩陣；不盡人意之處是要面對(duì)判斷迭代是否收斂和收斂速度的問(wèn)題。迭代式（2-1）收斂與否完全決定于迭代矩陣的性質(zhì)，與迭代初始值的選取無(wú)關(guān)?？梢宰C明迭代矩陣的譜半徑 （2-2）是迭代收斂的充分必要條件，其中是矩陣的特征根。因此，稱譜半徑小于1的矩陣為收斂矩陣。計(jì)算矩陣的譜半徑，需要求解矩陣的特征值，通常這是較為繁重的工作?？梢酝ㄟ^(guò)計(jì)算矩陣的范數(shù)等方法簡(jiǎn)化判斷收斂的工作，其中，計(jì)算矩陣的1范數(shù)和范數(shù)的方法比較簡(jiǎn)單。（向量的1范數(shù)等于向量元素絕對(duì)值之和，向量的范數(shù)范數(shù)等于向量元素絕對(duì)值的最大值。矩陣的1范數(shù)等于矩陣列向量的1范數(shù)的最大值；矩陣的范數(shù)等于矩陣行向量的1范數(shù)的最大值。） （2-3） （2-4）式（2-3）、式（2-4）分別是矩陣1范數(shù)和范數(shù)的計(jì)算公式。可以證明，只要迭代矩陣滿足或，就可以判斷迭代序列是收斂的。但要注意的是，當(dāng)或時(shí)，可以有，因此不能判斷迭代序列發(fā)散。在計(jì)算中當(dāng)相鄰兩次的向量誤差的某種范數(shù)小于給定精度時(shí)，則停止迭代計(jì)算，并視為方程組的近似解。二、 雅可比（Jacobi）迭代法1、 雅可比迭代格式設(shè)元線性方程組 （2-5）其矩陣形式為。若將式（2-5）中每個(gè)方程的留在方程左邊，其余各項(xiàng)移到方程右邊；方程兩邊除以則得到下列同解方程組： 記構(gòu)造迭代形式或?qū)懗删仃囆问?（2-6）式（2-6）稱為雅可比迭代。令 （2-8） （2-9）得雅克比迭代式的矩陣形式 （2-10）式中，為雅克比迭代矩陣。2、 雅可比迭代收斂條件當(dāng)方程組的系數(shù)矩陣具有某些性質(zhì)時(shí)，可直接判定由它生成的雅可比迭代矩陣是收斂的。定理：若方程組的系數(shù)矩陣，滿足下列條件之一，則其雅可比迭代法是收斂的。（1）為行對(duì)角占優(yōu)陣，即（2）為列對(duì)角占優(yōu)陣，即定理：若方程組的系數(shù)矩陣為對(duì)稱正定陣，并且也為對(duì)稱正定，則雅可比迭代收斂。（為的對(duì)角線元素組成的對(duì)角線矩陣）3、 雅可比迭代算法三、 高斯-塞德?tīng)枺℅auss-Seidel）迭代法1、 高斯-塞德?tīng)柕袷皆谘趴杀鹊?，的?jì)算公式是 (2-11)事實(shí)上，在計(jì)算前，已經(jīng)得到的值，不妨將已算出的分量直接代入迭代式中，及時(shí)使用最新計(jì)算出的分量值。因此的計(jì)算公式可改為： (2-12)式（2-12）稱為高斯塞德?tīng)柕健?、 高斯塞德?tīng)柕氖諗織l件定理：若方程組系數(shù)矩陣A為列或行對(duì)角優(yōu)時(shí)，則高斯塞德?tīng)柕諗俊６ɡ恚喝舴匠探M系數(shù)矩陣A為對(duì)稱正定陣，則高斯塞德?tīng)柕諗?。?duì)于方程組，如果由它構(gòu)造高斯-塞德?tīng)柕脱趴杀鹊际諗?，那么，多?shù)情況下高斯塞德?tīng)柕妊趴杀鹊氖諗啃Ч?，但是情況并非總是如此。3、 高斯塞德?tīng)柕惴ㄋ摹?逐次超松弛（SOR）迭代法1、 逐次超松弛迭代格式方程組的雅可比迭代形式，記其中是下三角矩陣，是上三角矩陣。得高斯-塞德?tīng)柕牡问剑?（2-13）記，有 （2-14）這樣可視為的修正量，如果將改為加上修正量乘一個(gè)因子，迭代格改為：整理得 （2-15）這里為修正因子，稱為松弛因子，而式（2-15）稱為松弛迭代。2、 逐次超松弛迭代收斂的條件定理：逐次超松弛迭代收斂的必要條件。定理：若為正定矩陣，則當(dāng)時(shí)，逐次超松弛迭代恒收斂。以上定理給出了逐次超松弛迭代因子的范圍。對(duì)于每個(gè)給定的方程組，確定究竟取多少為最佳，這是比較困難的問(wèn)題。通常，把的迭代稱為亞松弛迭代，把的迭代稱為高斯-塞德?tīng)柕训牡Q為松弛迭代。3、 逐次超松弛迭代算法第二節(jié) 線性方程組的直接解法 線性方程組可以用消去法直接求解，雖然是很古老的方法，但是計(jì)算實(shí)踐表明，對(duì)電力系統(tǒng)來(lái)說(shuō)是很有效的。這是因?yàn)殡娏ο到y(tǒng)中常見(jiàn)的大型線性方程組的系數(shù)矩陣，如導(dǎo)納矩陣是十分稀疏的，所以當(dāng)充分利用矩陣的稀疏性時(shí)，直接解法的計(jì)算速度很快。與上節(jié)介紹的迭代法相比，雖然直接解法占用計(jì)算機(jī)的內(nèi)存量要大一些，但是它沒(méi)有收斂性問(wèn)題。本節(jié)對(duì)消去法進(jìn)行一般的數(shù)學(xué)描述，給出適用于電子數(shù)字計(jì)算機(jī)的表達(dá)式，并介紹它的常用變態(tài)形式因子表解法和三角分解解法。一、 高斯消去法高斯順序消去法的基本思想是：對(duì)線性代數(shù)方程組所對(duì)應(yīng)的增廣矩陣（A|B）進(jìn)行一系列“把某一行元素倍加到另一行上”的初等變換，使得（A|B）中A的對(duì)角線以下的元素消去為0，從而使原方程組等價(jià)的轉(zhuǎn)化為容易求解的上三角形線性代數(shù)方程組，再通過(guò)回代得到上三角形線性代數(shù)方程組的解，即可求得原方程組的解。高斯消去法求解線性方程組分為兩個(gè)步驟：消去運(yùn)算（前代運(yùn)算）和回代運(yùn)算。1、 消去（前代）運(yùn)算設(shè)有線性方程組： （2-16）將系數(shù)矩陣和常數(shù)向量合并寫(xiě)成增廣矩陣： （2-17）消去運(yùn)算有兩種方法，按列消去和按行消去。首先討論按列消去的過(guò)程，其步驟是：第一步，消去第一列。首先，把增廣矩陣的第一行規(guī)格化為1 （2-18）式中： （2-19）然后，用式（2-18）所表示的行消去的第一列對(duì)角線以下各元素，結(jié)果使的第2n行其他元素化為 （2-20） 式中：上標(biāo)（1）表示該元素第一次運(yùn)算的結(jié)果。這時(shí)矩陣變?yōu)椋号c之對(duì)應(yīng)的方程組是,它與同解。矩陣未標(biāo)出的元素為零，下同。第二步，消去第二列。首先，把增廣矩陣的第二行規(guī)格化為0 1 （2-21）式中： （2-22）然后，用式（2-21）所表示的行消去的第二列對(duì)角線以下各元素,，結(jié)果使的第3n行其他元素化為 （2-23）式中：上標(biāo)（2）表示該元素第二次運(yùn)算的結(jié)果。這時(shí)矩陣變?yōu)椋阂话愕?，在消去第k列時(shí)要做以下的運(yùn)算： （2-24） （2-25）式（2-24）稱為規(guī)格化運(yùn)算，式（2-25）稱為消去運(yùn)算。經(jīng)過(guò)對(duì)矩陣的n次消去運(yùn)算，即k從1依次取到n按式（2-24），（2-25）運(yùn)算，使矩陣A對(duì)角線以下的元素全部化為零，從而得到增廣矩陣 （2-26） 與之對(duì)應(yīng)的方程組是，即 （2-27）它與原方程組同解。以上算法首先消去中第一列對(duì)角線下的元素，然后消去第二列對(duì)角線下的元素，依次直到對(duì)角線下的所有元素都被消去為止。這種消去算法稱為按列消去法。下面介紹按行消去法，它首先消去中第二行對(duì)角線左邊的元素，然后消去第三行對(duì)角線左邊的元素，依次直到對(duì)角線左邊的所有元素都被消去為止。其步驟是：第一步，首先對(duì)增廣矩陣的第一行做規(guī)格化運(yùn)算，結(jié)果為：1 （2-28）式中： （2-29）第二步，首先用式（2-28）所表示的行消去的第二行對(duì)角線左邊的元素，結(jié)果使的第2行其他元素化為 （2-30）這時(shí)矩陣變?yōu)椋喝缓?，?duì)增廣矩陣的第二行做規(guī)格化運(yùn)算，變?yōu)椋? 1 （2-31）式中： （2-32）這時(shí)矩陣變?yōu)椋猴@然，與之對(duì)應(yīng)的方程組是,它與同解。第三步，首先用式（2-28）所表示的行消去的第三行對(duì)角線左邊的第一元素；然后用式（2-31）所表示的行消去的第三行對(duì)角線左邊的第二元素；最后用第三行對(duì)角線元素對(duì)第三行做規(guī)格化運(yùn)算。一般地，在消去第k行時(shí)要做如下的運(yùn)算： （2-33） （2-34）經(jīng)過(guò)n次消去運(yùn)算，得到與式（2-26）相同的增廣矩陣，和與式（2-26）相同的同解方程。2、 回代運(yùn)算將方程組展開(kāi)為： （2-35）可見(jiàn)，經(jīng)消去運(yùn)算后系數(shù)矩陣變?yōu)橐簧先蔷仃嚵??；卮\(yùn)算就是由式（2-35）求出原方程解的過(guò)程。可以采用按行回代算法或按列回代算法。按行回代以行自下而上的順序進(jìn)行。其過(guò)程為：首先由第個(gè)方程得到解： （2-36）然后，將代入第個(gè)方程，解出： （2-37）再將將，代入第個(gè)方程可解出： （2-38）如此，如已得到的解分量，得出求解分量的算法 （2-39）式（2-39）就是按行回代的一般公式。按列回代的計(jì)算公式是： （2-40）也是按，的順序依次求各位置數(shù)。二、 因子表法1、 因子表從上節(jié)高斯消去過(guò)程可以看出線性方程組常數(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ù)矩陣保持不變。在這種情況下，如每次求解都做一次對(duì)系數(shù)矩陣和常數(shù)項(xiàng)完整消去運(yùn)算，很明顯將會(huì)有大量重復(fù)的運(yùn)算。如果常數(shù)項(xiàng)變化時(shí)，只需對(duì)常數(shù)項(xiàng)做消去運(yùn)算就行了，這就是因子表法。因子表就是記錄線性方程組求解過(guò)程中消去（前代）和回代運(yùn)算所需數(shù)據(jù)的一種表格?；卮\(yùn)算所需數(shù)據(jù)由對(duì)系數(shù)矩陣消去運(yùn)算所得的上三角矩陣元素確定。為了對(duì)常數(shù)項(xiàng)進(jìn)行消去（前代）運(yùn)算，還必須記錄消去（前代）過(guò)程中所需的運(yùn)算數(shù)據(jù)。消去（前代）過(guò)程又分為規(guī)格化和消去運(yùn)行，以按列消去為例，由式（2-24）和（2-25）可知，消去（前代）過(guò)程對(duì)常數(shù)項(xiàng)第個(gè)元素的運(yùn)算包括 （2-41） （2-42） 可見(jiàn)，常數(shù)項(xiàng)的消去運(yùn)算只與系數(shù)矩陣的下三角部分和常數(shù)項(xiàng)有關(guān)。將式（2-31）和（2-42）中的運(yùn)算因子按它們下標(biāo)指定的位置放在下三角部分，和消去運(yùn)算得到的上三角矩陣放在一起，就得到了因子表 （2-43）式（2-43）因子表中對(duì)角線元素為消去過(guò)程中規(guī)格化為1之前的對(duì)角元素；下三角元素為消去過(guò)程中消去為0之前的下三角元素。式中，對(duì)角線及下三角部分用于對(duì)常數(shù)項(xiàng)的消去（前代）運(yùn)算，上三角元素用來(lái)進(jìn)行回代元算。因子表也常寫(xiě)成如下的形式： （2-44）式中 2、 使用因子表解線性方程組（1） 形成因子表（按列消去） （2） 對(duì)常數(shù)項(xiàng)做消去運(yùn)算（3） 回代運(yùn)算得方程的解三、 三角分解法1、 矩陣的三角分解設(shè)方陣A可用一個(gè)下三角矩陣L與一個(gè)單位上三角矩陣U的乘積表示，即： （2-45）展開(kāi)為： （2-46）將式（2-46）右邊兩矩陣相乘，其元素應(yīng)與左邊矩陣相應(yīng)元素的值相等。比較第一行元素，得： （2-47）可見(jiàn)，L中第一列的對(duì)角線元素與A中第一列的對(duì)角線元素相同，U中第一行非對(duì)角線元素等于A中第一行非對(duì)角線元素用對(duì)角線元素規(guī)格化以后的值。比較第一列元素，得： （2-48）可見(jiàn)，L中第一列非對(duì)角線元素與A中第一列非對(duì)角線元素相同。比較第二行（），得： （2-49）可見(jiàn)，L中第二列的對(duì)角線元素等于A中第二列對(duì)角線元素經(jīng)第一次消去后的值。U中第二行非對(duì)角線元素等于A中第二行上三角非對(duì)角線元素經(jīng)第二次消去后的值。比較第二列（）（2-50）可見(jiàn)，L中第二列非對(duì)角線元素等于A中第二列下三角非對(duì)角線元素經(jīng)第一次消去后的值。以上分析得到的結(jié)論是：三角分解的L矩陣中的下三角元素與式（2-44）因子表的下三角部分（包括對(duì)角線元素）相等；U矩陣中的上三角元素與式（2-34）因子表的上三角部分（不包括對(duì)角線元素）相等。L矩陣、U矩陣稱為因子表矩陣，可由高斯消去法得到。另一種三角分解的方法是將A分解為單位下三角矩陣L、對(duì)角線矩陣D和單位上三角矩陣的乘積 （2-51）展開(kāi)為 （2-52）式中，如取U與式（2-45）中的U相同；D為角線矩陣，由式（2-45）中L矩陣的對(duì)角線元素組成。則式（2-51）中L的非對(duì)角元素為式（2-45）中L中的非對(duì)角元除以所在列的對(duì)角線元素而得。當(dāng)A為對(duì)稱矩陣時(shí)，有即，當(dāng)A為對(duì)稱矩陣時(shí)，式（2-51）中的L和U互為轉(zhuǎn)置。2、 用三角分解法解線性方程組設(shè)線性方程組： （2-53）系數(shù)矩陣分解為，引入中間矢量和，并令： （2-54） （2-55）則方程組（2-53）變?yōu)?（2-56）這樣，解線性方程組（2-53）可由以下幾個(gè)步驟完成：1）由式（2-56）求出，稱為前代運(yùn)算。2）由式（2-55）求出，稱為除法運(yùn)算。3）由式（2-54）求出，稱為回代運(yùn)算。（1）前代運(yùn)算將L分解為一個(gè)單位矩陣與一個(gè)嚴(yán)格下三角矩陣的和，式（2-56）變?yōu)椋?（2-57）將式（2-57）展開(kāi)，得 （2-58）按式（2-58）寫(xiě)出求解的計(jì)算流程如式（2-59），稱為按行前代。 （2-59）式（2-57）展開(kāi)也可寫(xiě)成如下的形式： （2-60）按式（2-60）寫(xiě)出求解的另一計(jì)算流程為如式（2-61），稱為按列前代。 （2-61）前代運(yùn)算從下標(biāo)小的元素開(kāi)始，由前向后進(jìn)行。實(shí)際上就是用對(duì)常數(shù)項(xiàng)的消去運(yùn)算。（2）除法運(yùn)算按式（2-55） （2-62）（3）回代運(yùn)算將U分解為一個(gè)單位矩陣與一個(gè)嚴(yán)格上三角矩陣的和，式（2-54）式變?yōu)椋?（2-63）將式（2-52）兩邊展開(kāi) （2-64）按式（2-64）寫(xiě)出求解的計(jì)算流程如式（2-65），稱為按行回代。 （2-65）式（2-64）也可展開(kāi)為如下的形式： （2-66）按式（2-66）寫(xiě)出求解的另一計(jì)算流程如式（2-67），稱為按列回代。 （2-67）回代運(yùn)算從下標(biāo)大的元素開(kāi)始，由后向前進(jìn)行。可見(jiàn)，利用方程組系數(shù)矩陣三角分解得到的因子表，先用因子表的下三角部分對(duì)常數(shù)項(xiàng)做前代運(yùn)算，然后用因子表的對(duì)角線部分對(duì)回代的結(jié)果做除法運(yùn)算，再用因子表的上三角部分對(duì)除法運(yùn)算的結(jié)果做回代運(yùn)算，就得到了方程的解。第三節(jié) 稀疏存儲(chǔ)技術(shù)稀疏矩陣是零元素占有很大比例的矩陣。電力網(wǎng)絡(luò)的導(dǎo)納矩陣就是稀疏矩陣，而且網(wǎng)絡(luò)越大稀疏程度越大。在求解電力網(wǎng)絡(luò)方程時(shí)，利用稀疏技術(shù)進(jìn)行“排零存儲(chǔ)，排零計(jì)算”可以節(jié)省大量的存儲(chǔ)空間和計(jì)算時(shí)間。一、稀疏存儲(chǔ)稀疏存儲(chǔ)就是只存儲(chǔ)矩陣中的非零元素，有多種方法，其中三角檢索存儲(chǔ)方法特別適合于矩陣三角分解的算法。這里介紹按行存儲(chǔ)上三角部分非零元素，按列存儲(chǔ)下三角部分非零元素的方法。令矩陣A是n階方陣，定義數(shù)組：U：大小等于A的上三角部分非零元素個(gè)數(shù)的一維數(shù)組，用于按行存儲(chǔ)A的上三角部分非零元素的值；JU：大小等于A的上三角部分非零元素個(gè)數(shù)的一維數(shù)組，用于按行存儲(chǔ)A的上三角部分非零元素的列號(hào)；IU：大小等于A的階數(shù)（行數(shù)）的一維數(shù)組，用于存儲(chǔ)A中上三角部分每行第一個(gè)非零元素在U中的位置；L：大小等于A的下三角部分非零元素個(gè)數(shù)的一維數(shù)組，用于按列存儲(chǔ)A的下三角部分非零元素的值；IL：大小等于A的下三角部分非零元素個(gè)數(shù)的一維數(shù)組，用于按列存儲(chǔ)A的下三角部分非零元素的行號(hào)；JL：大小等于A的階數(shù)（列數(shù)）的一維數(shù)組，用于存儲(chǔ)A中下三角部分每列第一個(gè)非零元素在L中的位置；D：大小等于A的階數(shù)的一維數(shù)組，用于存儲(chǔ)A中對(duì)角線元素的值。如方陣：采用三角檢索存儲(chǔ)方法時(shí)各數(shù)組的內(nèi)容如下：序號(hào)1234UJU243IU1344LIL244JL1234D用這種方式存儲(chǔ)了矩陣元素后，檢索可采用如下的流程： （2-68）二、稀疏存儲(chǔ)技術(shù)在求解線性方程組中的應(yīng)用1.形成因子表設(shè)線性方程組系數(shù)矩陣A的階數(shù)為n，為其第行，第列的元素，由第二節(jié)所述因子表和高斯消去法的關(guān)系，先寫(xiě)出常規(guī)不采用稀疏存儲(chǔ)技術(shù)時(shí)形成因子表的算法流程： （2-69）式（2-69）所示流程執(zhí)行完畢，矩陣A的上三角部分就是式（2-45）中矩陣U的上三角元素；矩陣A的下三角部分就是式（2-45）中矩陣L的下三角元素。在上算法中，顯然，如果，規(guī)格化計(jì)算不必做；如果或，消去計(jì)算不必做。如果要實(shí)現(xiàn)排零計(jì)算，上述算法需要添加判斷語(yǔ)句，反而會(huì)增加計(jì)算量。如果系數(shù)矩陣按三角檢索方法存儲(chǔ)，零元素已排除，不僅節(jié)省了存儲(chǔ)空間，計(jì)算時(shí)也不必做零元素判斷，從而也節(jié)省了計(jì)算時(shí)間。下面介紹的算法假定線性方程組系數(shù)矩陣已按三角檢索方法存儲(chǔ)，數(shù)組U、IU、JU、L、IL、JL、D開(kāi)始時(shí)存儲(chǔ)系數(shù)矩陣，因子分解后存儲(chǔ)因子表。并假定已為在分解過(guò)程中新生成的非零元素預(yù)留了空間。算法流程如下： （2-70）（2-70）流程執(zhí)行完畢數(shù)組U、D、L中存放的數(shù)據(jù)為式（2-51）三角分解式矩陣U、D、L的元素。2.前代運(yùn)算按式（2-60）所示算法，寫(xiě)出采用三角檢索存儲(chǔ)方式的按列前代算法流程 （2-71）3、除法運(yùn)算 （2-72）4、回代運(yùn)算按式（2-5）所示算法，寫(xiě)出采用三角檢索存儲(chǔ)方式的按行回代算法流程 （2-73）第四節(jié) 因子表法的圖形描述電力網(wǎng)絡(luò)節(jié)的節(jié)點(diǎn)導(dǎo)納矩陣與電力網(wǎng)絡(luò)的結(jié)構(gòu)有對(duì)應(yīng)關(guān)系，其上三角或下三角中的非對(duì)角元非零元素與電力網(wǎng)絡(luò)的支路一一對(duì)應(yīng)。因子分解得到的因子表矩陣也可與一個(gè)圖對(duì)應(yīng)起來(lái)。本節(jié)利用網(wǎng)絡(luò)圖形象地說(shuō)明稀疏矩陣的因子表分解和前代、回代過(guò)程，進(jìn)而引出稀疏矢量技術(shù)。一、定義和術(shù)語(yǔ)令A(yù)是對(duì)稱陣，其非零元素的分布為： （2-74）U是A的因子表上三角矩陣，且A=UTDU。U的非零元素分布為： （2-75）式中，“”表示在因子分解的過(guò)程中出現(xiàn)的新非零元素，稱為注入元。將A與一由邊和邊兩端的節(jié)點(diǎn)組成的圖對(duì)應(yīng)起來(lái)，并做如下定義：A圖：與矩陣A的上三角部分有相同網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的網(wǎng)絡(luò)圖。節(jié)點(diǎn)號(hào)與A的行號(hào)相對(duì)應(yīng)。邊與A的上三角部分非零非對(duì)角元相對(duì)應(yīng)。有向A圖：在A圖上，將每條邊規(guī)定方向?yàn)閺男√?hào)節(jié)點(diǎn)指向大號(hào)節(jié)點(diǎn)所得到的圖。小號(hào)節(jié)點(diǎn)為邊的發(fā)點(diǎn)，大號(hào)節(jié)點(diǎn)為邊的收點(diǎn)。賦權(quán)有向A圖A圖有向A圖 賦權(quán)有向A圖：在有向A圖上，與A中非零非對(duì)角元對(duì)應(yīng)的邊稱為節(jié)點(diǎn)間的互邊，并賦邊權(quán)為該元素的值。在有向A圖節(jié)點(diǎn)上添加接地邊，稱之為節(jié)點(diǎn)的自邊，并用A的對(duì)角元值賦邊權(quán)值。這樣得到的圖為賦權(quán)有向A圖。同樣地，因子表矩陣U也可用圖來(lái)描述，其因子圖、有向因子圖、賦權(quán)有向因子圖的定義與A圖、有向A圖、賦權(quán)有向A圖的定義類(lèi)似。因子圖有向因子圖賦權(quán)有向因子圖 二、因子分解過(guò)程的圖形描述因子分解過(guò)程從小號(hào)節(jié)點(diǎn)到大號(hào)節(jié)點(diǎn)依次進(jìn)行，為規(guī)格化和消去兩個(gè)步驟。1、規(guī)格化運(yùn)算第次消去的規(guī)格化運(yùn)算就是用第行的對(duì)角元去除第行上三角部分的所用元素，零元素不必計(jì)算。 （2-76）參見(jiàn)圖，規(guī)格化運(yùn)算就是用式（2-76）對(duì)節(jié)點(diǎn)發(fā)出的所有互邊的邊權(quán)進(jìn)行修正。在圖上就是對(duì)節(jié)點(diǎn)發(fā)出的所有互邊的邊權(quán)修正為除以節(jié)點(diǎn)的自邊權(quán)后的值。 規(guī)格化運(yùn)算不增加新的邊，即不產(chǎn)生注入元。2、消去運(yùn)算消去運(yùn)算只需在行（）與列（）軸線相交的位置上進(jìn)行，公式為： （2-77）由于A是對(duì)稱陣，節(jié)點(diǎn)的列元素可用規(guī)格化后的行元素代替，即上式變?yōu)椋?（2-78）同樣由于A是對(duì)稱陣，消去運(yùn)算只需在上三角部分進(jìn)行（消去后下三角部分元素與上三角部分對(duì)稱元素相等），所以式（2-78）中每個(gè)元素的列號(hào)都大于行號(hào)，即。當(dāng)時(shí)，是對(duì)對(duì)角元的消去運(yùn)算，式（2-78）變?yōu)椋?（2-79）式（2-79）的作用是修正節(jié)點(diǎn)發(fā)出的所有互邊的收點(diǎn)的自邊權(quán)，即將收點(diǎn)的自邊權(quán)修正為減去互邊權(quán)的平方乘與節(jié)點(diǎn)的自邊權(quán)的積后的值。當(dāng)時(shí)，是對(duì)上三角部分的非對(duì)角元的消去元算。在圖上就是對(duì)節(jié)點(diǎn)發(fā)出的所有互邊的收點(diǎn)兩兩之間的互邊進(jìn)行修正。按式（2-78），對(duì)節(jié)點(diǎn)之間的互邊修正的公式為： （2-80）可見(jiàn)，對(duì)非對(duì)角元消去就是將節(jié)點(diǎn)發(fā)出的所有互邊的收點(diǎn)兩兩之間的互邊權(quán)值修正為減去兩條相夾邊邊權(quán)與節(jié)點(diǎn)自邊權(quán)三者的乘積后的值。如兩個(gè)收點(diǎn)之間原來(lái)無(wú)互邊，消去運(yùn)算后會(huì)生成新的互邊，這就是因子分解過(guò)程中出現(xiàn)的注入元。當(dāng)所用節(jié)點(diǎn)按從小到大的順序做完規(guī)格化和消去運(yùn)算后，賦權(quán)有向A圖就變成了賦權(quán)有向因子圖。3、算法流程總結(jié)在圖上進(jìn)行因子分解就是以賦權(quán)有向A圖為起始，按節(jié)點(diǎn)號(hào)從小到大的順序執(zhí)行下面的操作。如已執(zhí)行到節(jié)點(diǎn)：（1）規(guī)格化運(yùn)算，將節(jié)點(diǎn)發(fā)出的所用互邊權(quán)值修正為除以節(jié)點(diǎn)自邊權(quán)值后的值。（2）對(duì)角元消去運(yùn)算，將節(jié)點(diǎn)發(fā)出的所用互邊的收點(diǎn)的自邊權(quán)值修正為減去該收點(diǎn)與節(jié)點(diǎn)的互邊權(quán)值的平方與節(jié)點(diǎn)自邊權(quán)值的乘積后的值。（3）非對(duì)角元消去運(yùn)算，將節(jié)點(diǎn)發(fā)出的所用互邊的收點(diǎn)兩兩之間的互邊權(quán)值修正為減去該兩收點(diǎn)分別與節(jié)點(diǎn)的互邊權(quán)值及節(jié)點(diǎn)自邊權(quán)值三者乘積后的值。三、前代、回代過(guò)程的圖形描述1、前代過(guò)程當(dāng)A為對(duì)稱矩陣時(shí)L=UT ，在按列前代流程（2-61）中由代替，前代過(guò)程可表述為將算法與因子矩陣和因子圖對(duì)應(yīng)起來(lái)，有：（1）對(duì)應(yīng)節(jié)點(diǎn)號(hào)；（2）前代的順序是從小號(hào)節(jié)點(diǎn)到大號(hào)節(jié)點(diǎn)，；（3）之間的邊由指向，是發(fā)點(diǎn)，是收點(diǎn)；（4）為之間互邊權(quán)值，對(duì)應(yīng)之間無(wú)互邊，在圖中不出現(xiàn)；（5）z元素的初值為b中的元素；如果定義為節(jié)點(diǎn)的點(diǎn)位，其初值為第個(gè)常數(shù)項(xiàng)的值。上述流程就是在圖上用小號(hào)節(jié)點(diǎn)的點(diǎn)位修正大號(hào)節(jié)點(diǎn)的點(diǎn)位的操作，修正公式為： （2-81）可見(jiàn)，前代過(guò)程就是以節(jié)點(diǎn)號(hào)從小到大的順序?qū)?jié)點(diǎn)發(fā)出的邊的收點(diǎn)的點(diǎn)位按（2-81）修正的過(guò)程。的邊不在圖上出現(xiàn)，隱含地使用了稀疏技術(shù)。若小號(hào)節(jié)點(diǎn)的點(diǎn)位，也不必修正。2、規(guī)格化過(guò)程將前代結(jié)束后規(guī)格化就是各點(diǎn)的點(diǎn)位除以因子圖上各自節(jié)點(diǎn)的自邊權(quán)值： （2-82）3、回代過(guò)程將第二節(jié)按列回代流程（2-67）重寫(xiě)如下：將算法與結(jié)合因子矩陣和因子圖對(duì)應(yīng)起來(lái)，有：（1）對(duì)應(yīng)節(jié)點(diǎn)號(hào)；（2）回代的順序是從大號(hào)節(jié)點(diǎn)到小號(hào)節(jié)點(diǎn)，；（3）之間的邊由指向，是發(fā)點(diǎn)，是收點(diǎn)；（4）為之間互邊權(quán)值，對(duì)應(yīng)之間無(wú)互邊，在圖中不出現(xiàn)；（5）x的元素初值是規(guī)格化運(yùn)算后各節(jié)點(diǎn)的點(diǎn)位；上述流程就是在圖上用大號(hào)節(jié)點(diǎn)點(diǎn)位修正小號(hào)節(jié)點(diǎn)點(diǎn)位的操作，修正公式為： （2-83）可見(jiàn)，回代過(guò)程就是以節(jié)點(diǎn)號(hào)從大到小的順序?qū)χ赶蚬?jié)點(diǎn)的邊的發(fā)點(diǎn)的點(diǎn)位按（2-83）修正的過(guò)程。的邊不在圖上出現(xiàn)，隱含地使用了稀疏技術(shù)。若大號(hào)節(jié)點(diǎn)的點(diǎn)位，不必修正。4、流程總結(jié)（1）將常數(shù)矢量（獨(dú)立矢量）的元素值賦值為賦權(quán)有向因子圖相應(yīng)節(jié)點(diǎn)的初始點(diǎn)位；（2）以節(jié)點(diǎn)號(hào)從小到大的順序?qū)?jié)點(diǎn)發(fā)出的邊的收點(diǎn)的點(diǎn)位按（2-81）修正。如已前代到節(jié)點(diǎn)，則將節(jié)點(diǎn)對(duì)應(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）式對(duì)點(diǎn)位規(guī)格化，點(diǎn)位為零不必計(jì)算；（4）以節(jié)點(diǎn)號(hào)從大到小的順序?qū)χ赶蚬?jié)點(diǎn)的邊的發(fā)點(diǎn)的點(diǎn)位按（2-83）修正。如已回代到節(jié)點(diǎn)，則將節(jié)點(diǎn)對(duì)應(yīng)的所用發(fā)點(diǎn)的點(diǎn)位修正為減去該發(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àn)，將因子表分解的每一步過(guò)程都是在圖的節(jié)點(diǎn)、節(jié)點(diǎn)發(fā)出的邊、收點(diǎn)、收點(diǎn)間的邊上進(jìn)行的。由于零元素不在圖上出現(xiàn)，所以在圖上進(jìn)行因子分解自然地實(shí)現(xiàn)了“排零存儲(chǔ)、排零運(yùn)算”。前代運(yùn)算是用小號(hào)節(jié)點(diǎn)的點(diǎn)位去修正所發(fā)出的邊的收點(diǎn)的電位；回代元算是用大號(hào)節(jié)點(diǎn)的電位去修正該節(jié)點(diǎn)對(duì)應(yīng)的所用發(fā)點(diǎn)的電位。由于導(dǎo)納矩陣的零元素沒(méi)有圖中對(duì)應(yīng)的邊，所以圖上的前代、回代運(yùn)算自然就“排零運(yùn)算”了。第五節(jié) 稀疏矢量技術(shù)上節(jié)用圖上因子分解的方法說(shuō)明了在因子分解過(guò)程中如何利用稀疏矩陣的特點(diǎn)。在因子分解的每一步，不論是規(guī)格化運(yùn)算還是消去運(yùn)算，都是在某點(diǎn)相聯(lián)的邊上進(jìn)行的，這在矩陣中相當(dāng)于以行和列為軸線，只取用軸線上的非零元素以及只在行列軸線上的非零元素相交叉的位置上進(jìn)行操作運(yùn)算。計(jì)算中自然地實(shí)現(xiàn)了排零計(jì)算。在前代回代過(guò)程中，如果前代之前獨(dú)立矢量b中只有少數(shù)是非零元素，即圖上只有少數(shù)的節(jié)點(diǎn)的點(diǎn)位不是零，大多數(shù)節(jié)點(diǎn)的點(diǎn)位都是零，由圖上的前代過(guò)程可知，前代中對(duì)零點(diǎn)位的點(diǎn)進(jìn)行的前代操作是多余的，可以省略。如果在解矢量x中，我們只對(duì)其中的少數(shù)幾個(gè)元素感興趣，解矢量中大多數(shù)元素盡管回代后其值不等于零，但我們對(duì)它們不感興趣，即我們只取用回代后點(diǎn)位中少數(shù)感興趣的節(jié)點(diǎn)的點(diǎn)位。則在回代過(guò)程中與這些待求點(diǎn)位無(wú)關(guān)的回代操作也是多余的，可以省略。在前代回代中，哪些計(jì)算步是必不可少的，哪些計(jì)算步是多余的，這是稀疏矢量法要解決的間題。仍以對(duì)稱矩陣的情況討論。一、概念和定義稀疏獨(dú)立矢量：一個(gè)給定的只有少量非零元素的獨(dú)立矢量。稀疏解矢量：一個(gè)只有少數(shù)元素待求的解矢量。道路樹(shù)：在有向因子圖上，僅取從每個(gè)節(jié)點(diǎn)發(fā)出的邊的收點(diǎn)為最小號(hào)的邊得到的有向樹(shù)。在連通的A圖形成的因子圖上。道路樹(shù)只有一顆，且只有一個(gè)根節(jié)點(diǎn)。根節(jié)點(diǎn)是編號(hào)最大的節(jié)點(diǎn)，無(wú)發(fā)出的邊。點(diǎn)的路：在道路樹(shù)上節(jié)點(diǎn)沿道路樹(shù)到根節(jié)點(diǎn)所經(jīng)過(guò)的路徑，是道路樹(shù)的一個(gè)子集。每個(gè)點(diǎn)的路只有一條。點(diǎn)集的路集：一個(gè)點(diǎn)集中所有點(diǎn)的路的并集。也是道路樹(shù)的一個(gè)子樹(shù)。二、性質(zhì)和定理性質(zhì)1：有向因子圖上任一點(diǎn)發(fā)出的邊的收點(diǎn)必在該點(diǎn)的路上。性質(zhì)2：有向因子圖上任何邊的兩個(gè)端節(jié)點(diǎn)的路集就是其中編號(hào)小的節(jié)點(diǎn)的路。即邊的大號(hào)節(jié)點(diǎn)一定在小號(hào)節(jié)點(diǎn)的路上。性質(zhì)3：如果有向因子圖中任何一組點(diǎn)集中的節(jié)點(diǎn)兩兩之間都有邊，則該點(diǎn)集的路集就是該點(diǎn)集中編號(hào)最小的節(jié)點(diǎn)的路。定理1：在有向因子圖上，前代運(yùn)算只在稀疏獨(dú)立矢量中非零元點(diǎn)集的路集上進(jìn)行。（那些點(diǎn)需要做前代）定理2：路集上任一點(diǎn)的前代運(yùn)算必須在路集上比該點(diǎn)編號(hào)小且其路經(jīng)過(guò)該點(diǎn)的點(diǎn)的前代完成之后才能進(jìn)行，而路集中分支點(diǎn)以上的幾條路先做哪個(gè)沒(méi)有關(guān)系。（做前代的順序）定理3：在有向因子圖上，回代運(yùn)算只在稀疏解矢量的待解元素的點(diǎn)集的路集上進(jìn)行。（那些點(diǎn)需要做回代）定理4：任一點(diǎn)的回代運(yùn)算都必須在該點(diǎn)的道路上比該點(diǎn)編號(hào)大的點(diǎn)的回代運(yùn)算完成之后進(jìn)行，而路集中分支點(diǎn)以上幾條路先沿那條路回代沒(méi)有關(guān)系。（做回代的順序）注意：定理1、3說(shuō)明了那些點(diǎn)需要做前代、回代運(yùn)算，使用時(shí)一是要注意前代、回代的順序，二是要注意前代、回代運(yùn)算還是要按賦權(quán)有向因子圖節(jié)點(diǎn)之間的關(guān)系進(jìn)行，而不是按路集圖節(jié)點(diǎn)間的關(guān)系進(jìn)行。三、路集的形成以上可見(jiàn)，稀疏矢量技術(shù)使用的基礎(chǔ)是形成稀疏獨(dú)立矢量和稀疏解矢量的路集。形成單個(gè)節(jié)點(diǎn)的路的算法流程： （2-84）式中：IU(p)：因子表矩陣中節(jié)點(diǎn)p對(duì)應(yīng)的行的上三角部分第一各個(gè)非零非對(duì)角元在U中的位置；JU(IU(p)：IU(p)對(duì)應(yīng)的列號(hào)，有向因子圖上即節(jié)點(diǎn)p發(fā)出的最小節(jié)點(diǎn)號(hào)。形成點(diǎn)集的路集的算法流程： （2-85）式中：G為點(diǎn)集。第六節(jié) 節(jié)點(diǎn)優(yōu)化編號(hào)稀疏技術(shù)的核心關(guān)鍵有兩點(diǎn)，一是排零存儲(chǔ)和排零運(yùn)算，二是節(jié)點(diǎn)優(yōu)化編號(hào)。排零存儲(chǔ)和排零運(yùn)算有效地避免對(duì)計(jì)算結(jié)果沒(méi)有影響的存儲(chǔ)和計(jì)算，大大提高程序的計(jì)算效力。節(jié)點(diǎn)的編號(hào)是指節(jié)點(diǎn)在導(dǎo)納矩陣中的排列順序，對(duì)于計(jì)算效率的影響也是至關(guān)重要的，它直接影響到矩陣A的因子表矩陣的稀疏度。嚴(yán)格地說(shuō)，最優(yōu)編號(hào)是一個(gè)組合優(yōu)化問(wèn)題，求其最優(yōu)解是困難的，但在實(shí)際工程中，有許多實(shí)用的次優(yōu)的編號(hào)方法得到了廣泛的應(yīng)用。1.Tinney-1編號(hào)法（靜動(dòng)態(tài)編號(hào)法）這種方法也稱靜態(tài)節(jié)點(diǎn)優(yōu)化編號(hào)方法。這種方法統(tǒng)計(jì)每一個(gè)節(jié)點(diǎn)的出線度，即該節(jié)點(diǎn)和其它節(jié)點(diǎn)相連結(jié)的支路數(shù)，然后按節(jié)點(diǎn)出線度由小到大按順序進(jìn)行編號(hào)。對(duì)于出線度相同的節(jié)點(diǎn)。哪個(gè)排在前邊是任意的。這種編一號(hào)方法的出發(fā)點(diǎn)是認(rèn)為在圖上因子分解的過(guò)程中出線度小的節(jié)點(diǎn)消去時(shí)產(chǎn)生注入元的可能性也小。這種編號(hào)方法簡(jiǎn)單，但編號(hào)效果較差。由因子分解過(guò)程可知：出線度少的節(jié)點(diǎn)消去后產(chǎn)生的注入元不一定比出線度多的節(jié)點(diǎn)消去后產(chǎn)生的注入元少；已編號(hào)的節(jié)點(diǎn)消去后，未消去節(jié)點(diǎn)的出線度會(huì)發(fā)生變化?；诘邳c(diǎn)，引出了半動(dòng)態(tài)節(jié)點(diǎn)優(yōu)化編號(hào)算法。2.Tinney-2編號(hào)法（半動(dòng)態(tài)編號(hào)法）這種方法也稱最小度算法。首先統(tǒng)計(jì)所有節(jié)點(diǎn)的出線度，然后選出出線度最小的節(jié)點(diǎn)先進(jìn)行編號(hào)。編號(hào)后，用因子分解的辦法消去該節(jié)點(diǎn)，消去時(shí)只進(jìn)行網(wǎng)絡(luò)結(jié)構(gòu)變化的處理，而不進(jìn)行實(shí)際的消去運(yùn)算。在消去節(jié)點(diǎn)剩下的子圖上重復(fù)上述編號(hào)過(guò)程，直到所有節(jié)點(diǎn)都編了號(hào)為止。這種方法可使注入元數(shù)大大減少，而程序復(fù)雜性和計(jì)算量又增加不多，是一種使用十分廣泛的編號(hào)方法。但是，由于每步編號(hào)仍按最小出線度作為編號(hào)準(zhǔn)則，而出線度最少不等于消去該節(jié)點(diǎn)時(shí)產(chǎn)生的注入元最少，因此。也可以按產(chǎn)生注入元最少作為準(zhǔn)則來(lái)編號(hào)，這就是動(dòng)態(tài)節(jié)點(diǎn)優(yōu)化編號(hào)方法。3.Tinney-3編號(hào)法（動(dòng)態(tài)編號(hào)法） 動(dòng)態(tài)節(jié)點(diǎn)優(yōu)化編號(hào)法和上面的Tinney-2編號(hào)的不同之處是對(duì)所有待編號(hào)的節(jié)點(diǎn)，統(tǒng)計(jì)消去該節(jié)點(diǎn)時(shí)產(chǎn)生的注入元數(shù)目，并以該數(shù)目最小為優(yōu)先編號(hào)的準(zhǔn)則。節(jié)點(diǎn)編號(hào)后，將其消去，在剩下的子圖上重復(fù)上述編號(hào)過(guò)程，直到所有節(jié)點(diǎn)都編了號(hào)為止。這種方法在每步編號(hào)前都要對(duì)所有待編號(hào)節(jié)點(diǎn)統(tǒng)計(jì)消去后產(chǎn)生的注入元數(shù)，程序的復(fù)雜程度和計(jì)算量都很大，而最終編號(hào)結(jié)果相對(duì)于Tinney-2的結(jié)果略有改善，效益改善并不特別明顯，所以Tinney-3編號(hào)沒(méi)有Tinney-2編號(hào)用的普遍。4.Tinney-2編號(hào)法流程和算法（1） 進(jìn)行隨意的人工編號(hào)（2） 統(tǒng)計(jì)原始網(wǎng)絡(luò)各節(jié)點(diǎn)所連接的支路數(shù)，并保存各節(jié)點(diǎn)連接的支路的對(duì)端節(jié)點(diǎn)號(hào)。（3） 找出未優(yōu)化編號(hào)的網(wǎng)絡(luò)中連接支路最少的接點(diǎn)，如為k。（4） 修正消去節(jié)點(diǎn)k后新網(wǎng)絡(luò)各節(jié)點(diǎn)連接的支路數(shù)和對(duì)端節(jié)點(diǎn)號(hào)。做法是：與節(jié)點(diǎn)k相連的節(jié)點(diǎn)的連接支路數(shù)-1，并在這些節(jié)點(diǎn)的對(duì)端節(jié)點(diǎn)中去掉k。與節(jié)點(diǎn)k相連的節(jié)點(diǎn)每?jī)蓛芍g如果原來(lái)沒(méi)有支路，則此兩個(gè)節(jié)點(diǎn)的連接支路數(shù)+1，并將節(jié)點(diǎn)號(hào)分別保存在對(duì)端節(jié)點(diǎn)號(hào)中。（5） 返回（3），直到所有節(jié)點(diǎn)都參與了優(yōu)化。Tinney-2節(jié)點(diǎn)優(yōu)化編號(hào)的算法流程如下（2-86）式中：n：節(jié)點(diǎn)數(shù)；LN(n)：一維數(shù)組，按原始節(jié)點(diǎn)編號(hào)存放節(jié)點(diǎn)相連的支路（節(jié)點(diǎn)）數(shù)，不包括接地支路；NN(n)()：二維動(dòng)態(tài)數(shù)組，存放節(jié)點(diǎn)相連接的節(jié)點(diǎn)。第二維在執(zhí)行過(guò)程中可擴(kuò)展；NP(n)：一維數(shù)組，開(kāi)始時(shí)存放原始節(jié)點(diǎn)編號(hào)順序，執(zhí)行完后存放優(yōu)化后的節(jié)點(diǎn)編號(hào)順序。作業(yè)：1、 加文件輸入、輸出部分，編制高斯-賽德?tīng)柕ㄇ蠼饩€性方程組的計(jì)算機(jī)程序；2、 分別用三種節(jié)點(diǎn)優(yōu)化編號(hào)法重新排列節(jié)點(diǎn)順序，重新形成節(jié)點(diǎn)導(dǎo)納矩陣，并做三角分解，比較三種方法的效果。3、 編寫(xiě)采用稀疏技術(shù)的求解線性方程組的計(jì)算機(jī)程序；