第三章電力網(wǎng)絡計算中的稀疏技術(shù)

1、第三章電力網(wǎng)絡計算中的稀疏技術(shù)第三章-電力網(wǎng)絡計算中的稀疏技術(shù)3.1 3.1 概概 述述電網(wǎng)計算中要遇到大量的矩陣和矩陣的運算以及矩陣和矢量的運電網(wǎng)計算中要遇到大量的矩陣和矩陣的運算以及矩陣和矢量的運算算由電力網(wǎng)絡本身的結(jié)構(gòu)特點所決定，這些矩陣和矢量中往往只有少由電力網(wǎng)絡本身的結(jié)構(gòu)特點所決定，這些矩陣和矢量中往往只有少量的元素是非零元素，大部分元素都是零元素量的元素是非零元素，大部分元素都是零元素 。這些矩陣和矢量。這些矩陣和矢量是稀疏的。是稀疏的。矩陣稀疏度矩陣稀疏度: :一個一個n n m m階矩陣階矩陣A A，如果其中的非零元素有，如果其中的非零元素有,則定則定義矩陣義矩陣A A的稀疏度

2、是的稀疏度是: : 3.1 3.1 概概 述述 例如例如: :對于節(jié)點導納矩陣，如果電力網(wǎng)絡中每個節(jié)點的平均出對于節(jié)點導納矩陣，如果電力網(wǎng)絡中每個節(jié)點的平均出線度是線度是，即平均每個節(jié)點和，即平均每個節(jié)點和條支路條支路( (不包括接地支路不包括接地支路) )相連，相連，則節(jié)點導納矩陣的稀疏度為則節(jié)點導納矩陣的稀疏度為: :式中式中N N是節(jié)點數(shù)，即導納矩陣的維數(shù)對于實際電力系統(tǒng)，節(jié)點是節(jié)點數(shù)，即導納矩陣的維數(shù)對于實際電力系統(tǒng)，節(jié)點平均出線度一般為平均出線度一般為3 35 5，對，對500500個節(jié)點的電力系統(tǒng)，若個節(jié)點的電力系統(tǒng)，若 取取4 4，其導納矩陣的稀疏度僅為其導納矩陣的稀疏度僅為l

3、l。 對于稀疏矢量的稀疏度也有類似的定義。對于稀疏矢量的稀疏度也有類似的定義。 把稀疏度很小的矩陣和矢量稱為稀疏矩陣和稀疏矢量。把稀疏度很小的矩陣和矢量稱為稀疏矩陣和稀疏矢量。3.1 3.1 概概 述述在進行稀疏矩陣和稀疏矢量的運算中，可以采用在進行稀疏矩陣和稀疏矢量的運算中，可以采用“排零存儲排零存儲”、“排零運算排零運算”的辦法，可以大大減少存儲量，提高計算速度。的辦法，可以大大減少存儲量，提高計算速度。為實現(xiàn)這一作法所采用的程序技術(shù)稱為稀疏技術(shù)它包括了稀疏為實現(xiàn)這一作法所采用的程序技術(shù)稱為稀疏技術(shù)它包括了稀疏矩陣技術(shù)和稀疏矢量技術(shù)兩方面矩陣技術(shù)和稀疏矢量技術(shù)兩方面和不采用稀疏技術(shù)相比，采

4、用稀疏技術(shù)可以加快計算速度幾十甚至上和不采用稀疏技術(shù)相比，采用稀疏技術(shù)可以加快計算速度幾十甚至上百倍，而且對計算機的內(nèi)存要求也可以大大降低百倍，而且對計算機的內(nèi)存要求也可以大大降低電力系統(tǒng)規(guī)模越大，使用稀疏技術(shù)帶來的效益就越明顯可電力系統(tǒng)規(guī)模越大，使用稀疏技術(shù)帶來的效益就越明顯可以說，稀疏技術(shù)的引入是對電力系統(tǒng)計算技術(shù)的一次革命，以說，稀疏技術(shù)的引入是對電力系統(tǒng)計算技術(shù)的一次革命，使許多原來不能做的電網(wǎng)計算可以很容易地實現(xiàn)。使許多原來不能做的電網(wǎng)計算可以很容易地實現(xiàn)。3.1 3.1 概概 述述 最早將稀疏矩陣技術(shù)引入電力系統(tǒng)潮流計算的是美國學者最早將稀疏矩陣技術(shù)引入電力系統(tǒng)潮流計算的是美國學者

5、W WF FTinneyTinney他于他于19671967年發(fā)表了一篇關(guān)于利用稀疏矩陣和節(jié)年發(fā)表了一篇關(guān)于利用稀疏矩陣和節(jié)點優(yōu)化編號技術(shù)求解稀疏線性方程組的論文，并將稀疏矩陣技術(shù)點優(yōu)化編號技術(shù)求解稀疏線性方程組的論文，并將稀疏矩陣技術(shù)用于牛頓法潮流計算中，大大提高了潮流計算的計算速度。用于牛頓法潮流計算中，大大提高了潮流計算的計算速度。 6060年代，計算年代，計算100100節(jié)點的系統(tǒng)的潮流已是十分困難的了，使用稀疏節(jié)點的系統(tǒng)的潮流已是十分困難的了，使用稀疏矩陣技術(shù)以后，幾千個節(jié)點甚至上萬個節(jié)點的大系統(tǒng)的潮流計算都矩陣技術(shù)以后，幾千個節(jié)點甚至上萬個節(jié)點的大系統(tǒng)的潮流計算都可以實現(xiàn)了?？梢詫?/p>

6、現(xiàn)了。 到目前為止，幾乎所有實用的電力網(wǎng)絡分析程序都不同程度到目前為止，幾乎所有實用的電力網(wǎng)絡分析程序都不同程度地使用了稀疏矩陣技術(shù)。地使用了稀疏矩陣技術(shù)。 3.1 3.1 概概 述述 8080年代中期，在利用并開發(fā)了矩陣的稀疏性的基礎上，又進一步年代中期，在利用并開發(fā)了矩陣的稀疏性的基礎上，又進一步開發(fā)了矢量的稀疏性，即在求解稀疏線性代數(shù)方程組時，識別和開發(fā)了矢量的稀疏性，即在求解稀疏線性代數(shù)方程組時，識別和稀疏矢量有關(guān)的有效的計算步，排除不必要的計算步，進一步減稀疏矢量有關(guān)的有效的計算步，排除不必要的計算步，進一步減少了計算量，使整個計算的計算量減少到最低程度。少了計算量，使整個計算的計算

7、量減少到最低程度。 自從自從202X202X年年W W首次發(fā)表了稀疏矢量法的論文以來，雖然還不首次發(fā)表了稀疏矢量法的論文以來，雖然還不能說稀疏矢量法已為所有的電力系統(tǒng)計算工作者所掌握，但能說稀疏矢量法已為所有的電力系統(tǒng)計算工作者所掌握，但其計算效力巳在電網(wǎng)計算的許多領域中顯示出來，是一種很其計算效力巳在電網(wǎng)計算的許多領域中顯示出來，是一種很有發(fā)展前途的技術(shù)。掌握并靈活運用稀疏矩陣和稀疏矢量技有發(fā)展前途的技術(shù)。掌握并靈活運用稀疏矩陣和稀疏矢量技術(shù)可以大大改變現(xiàn)有電力網(wǎng)絡計算程序的面貌，使之達到一術(shù)可以大大改變現(xiàn)有電力網(wǎng)絡計算程序的面貌，使之達到一個新的更高的水平。個新的更高的水平。3 32 2

8、稀疏技術(shù)稀疏技術(shù)一、稀疏矢量和稀疏矩陣的存儲一、稀疏矢量和稀疏矩陣的存儲稀疏矢量和稀疏矩陣的存儲特點是排零存儲：只存儲其中的非零元稀疏矢量和稀疏矩陣的存儲特點是排零存儲：只存儲其中的非零元素和有關(guān)的檢索信息。素和有關(guān)的檢索信息。存儲的目的是為了在計算中能方便地訪問使用，這就要求存儲的目的是為了在計算中能方便地訪問使用，這就要求: :(1)(1)所采用的存儲格式節(jié)省內(nèi)存所采用的存儲格式節(jié)省內(nèi)存; ;(2)(2)方便地檢索和存取方便地檢索和存取; ;(3)(3)網(wǎng)絡矩陣結(jié)構(gòu)變化時能方便地對存儲的信息加以修改。網(wǎng)絡矩陣結(jié)構(gòu)變化時能方便地對存儲的信息加以修改。稀疏矢量的存儲：只需存儲矢量中的非零元素值

9、和相稀疏矢量的存儲：只需存儲矢量中的非零元素值和相應的下標。應的下標。對稀疏矩陣，有幾種不同的存儲方法，除了和矩陣的稀對稀疏矩陣，有幾種不同的存儲方法，除了和矩陣的稀疏結(jié)構(gòu)的特點有關(guān)，還和使用時所采用的算法有關(guān)。疏結(jié)構(gòu)的特點有關(guān)，還和使用時所采用的算法有關(guān)。不同的算法往往要求對稀疏矩陣中的非零元素有不不同的算法往往要求對稀疏矩陣中的非零元素有不同的檢索方式。因此，應根據(jù)應用對象的實際情況來同的檢索方式。因此，應根據(jù)應用對象的實際情況來選擇合適的存儲方式。選擇合適的存儲方式。3.2 3.2 稀疏技術(shù)稀疏技術(shù)1.1.散居格式散居格式定義三個數(shù)組，分別存儲下列信息：定義三個數(shù)組，分別存儲下列信息：V

10、AVA存儲存儲A A中非零元素中非零元素a aijij的值，共的值，共個，個，IAIA存儲存儲A A中非零元素中非零元素a aijij的行指標的行指標i i，共，共個，個，JAJA存儲存儲A A中非零元素中非零元素a aijij的列指標的列指標j,j,共共個。個?？偣残枰偣残枰?3個存儲單元。個存儲單元。3.2 3.2 稀疏技術(shù)稀疏技術(shù) 散居格式的優(yōu)點散居格式的優(yōu)點:A:A中的非零元在上面數(shù)組中的位置可任意排列，中的非零元在上面數(shù)組中的位置可任意排列，修改靈活；修改靈活； 缺點：因其存儲順序無一定規(guī)律，檢索起來不方便。缺點：因其存儲順序無一定規(guī)律，檢索起來不方便。 例如：在上面數(shù)組中查找下標

11、是例如：在上面數(shù)組中查找下標是i i，j j的元素的元素a aijij，需要在數(shù)組，需要在數(shù)組IAIA中找下標是中找下標是i i同時在同時在JAJA數(shù)組中的下標是數(shù)組中的下標是j j的元素，最壞的可能性要在整的元素，最壞的可能性要在整個數(shù)組中查找一遍，工作量極大。個數(shù)組中查找一遍，工作量極大。因此，有必要按某一事先約定的順序來存儲稀疏矩陣因此，有必要按某一事先約定的順序來存儲稀疏矩陣A A中的非零元，以中的非零元，以使查找更為方便快捷。使查找更為方便快捷。3.2 3.2 稀疏技術(shù)稀疏技術(shù)2.2.按行（列）存儲格式按行（列）存儲格式 按行按行( (列列) )順序依次存儲順序依次存儲A A中的非零

12、元，同一行中的非零元，同一行( (列列) )元素依次排在一起。元素依次排在一起。 以按行存儲為例，其存儲格式是：以按行存儲為例，其存儲格式是： VAVA按行存儲矩陣按行存儲矩陣A A中的非零元中的非零元a aijij，共，共個，個， JA JA按行存儲矩陣按行存儲矩陣A A中非零元的列號，共中非零元的列號，共個，個， IA IA記錄記錄A A中每行第一個非零元素在中每行第一個非零元素在VAVA中的位置，共中的位置，共n n個。個。3.2 3.2 稀疏技術(shù)稀疏技術(shù) 查找第查找第i i行的非零元素：即在行的非零元素：即在VAVA中取出從中取出從k=IA(i)k=IA(i)到到IA(i+1)IA(i

13、+1)共共IA(i+1)IA(i+1)IA(i)IA(i)個非零元就是個非零元就是A A中第中第i i行的全部非零元，非零行的全部非零元，非零元的值是元的值是VA(k)VA(k)，其列號由，其列號由JA(k)JA(k)給出。給出。找第找第i i行第行第j j列元素列元素a aijij在在VAVA中的位置：對中的位置：對k k從從IA(i)IA(i)到到IA(i+1)-1IA(i+1)-1，判，判列號列號JA(k)JA(k)是否等于是否等于j j，如等，則，如等，則VA(k)VA(k)即是要找的非零元即是要找的非零元a aijij。這種存儲方案可以用于存儲任意稀疏矩陣，這種存儲方案可以用于存儲任

14、意稀疏矩陣，A A可以不是正方矩陣?？梢圆皇钦骄仃嚒Ｈ绻绻鸄 A是方矩陣，可以把是方矩陣，可以把A A的對角元素提出來單獨存儲，而對角元的對角元素提出來單獨存儲，而對角元素的行列指標都無需記憶。素的行列指標都無需記憶。3.2 3.2 稀疏技術(shù)稀疏技術(shù)3 3三角檢索存儲格式三角檢索存儲格式 三角檢索的存儲格式特別適合稀疏矩陣的三角分解的計算格三角檢索的存儲格式特別適合稀疏矩陣的三角分解的計算格式。有幾種不同的存儲格式，這里以按行存儲式。有幾種不同的存儲格式，這里以按行存儲A A的上三角部分的上三角部分非零元，按列存非零元，按列存A A的下三角部分非零元這種存儲格式來說明。的下三角部分非零元這

15、種存儲格式來說明。令令A A是是n n n n階方陣：階方陣：UU存存A A的上三角部分的非零元的值，按行依次存儲；的上三角部分的非零元的值，按行依次存儲；JUJU存存A A的上三角部分的非零元的列號；的上三角部分的非零元的列號；IUIU存存A A中上三角部分每行第一個非零元在中上三角部分每行第一個非零元在U U中的位置中的位置 ( (首地址首地址) )；LL按列存儲按列存儲A A中下三角非零元素的值；中下三角非零元素的值；ILIL按列存儲按列存儲A A中下三角非零元素的行號；中下三角非零元素的行號；JLJL存儲存儲A A的下三角部分每列第一個非零元在的下三角部分每列第一個非零元在L L中的位

16、置中的位置( (首地首地址址) )；DD存儲存儲A A的對角元素的值，其檢索下標不需要存儲的對角元素的值，其檢索下標不需要存儲. .例：有了有了IUIU表即可知道表即可知道A A的上三角部分第的上三角部分第i i行的非行的非零元的數(shù)目：零元的數(shù)目：IU(i+1)-IU(i)IU(i+1)-IU(i)。第一行：。第一行： IU(2)-IU(1)IU(2)-IU(1)3 31 12 2。如果要查找如果要查找A A中的上三角第中的上三角第i i行所有非零元行所有非零元素，只要掃描素，只要掃描k k從從IU(i)IU(i)到到IU(i+1)-1IU(i+1)-1即可，即可，JU(k)JU(k)指出了該

17、元素的列號，指出了該元素的列號，U(k)U(k)是該非零是該非零元素的值元素的值對于按列存儲的格式進行查找的情況類同。對于按列存儲的格式進行查找的情況類同。列號列號位置位置3.2 3.2 稀疏技術(shù)稀疏技術(shù)三角檢索存儲格式在矩陣三角檢索存儲格式在矩陣A A的稀疏結(jié)構(gòu)已確定的情況下使用是的稀疏結(jié)構(gòu)已確定的情況下使用是十分方便的。但在計算過程中，如果十分方便的。但在計算過程中，如果A A的稀疏結(jié)構(gòu)發(fā)生了變化，的稀疏結(jié)構(gòu)發(fā)生了變化，即其中的非零元素的分布位置發(fā)生變化，相應的檢索信息也即其中的非零元素的分布位置發(fā)生變化，相應的檢索信息也要隨著變化，很不方便。有兩種辦法處理這類問題。要隨著變化，很不方便。

18、有兩種辦法處理這類問題。 第一種辦法事先估計出在隨后的計算中第一種辦法事先估計出在隨后的計算中A A的哪些位置可能產(chǎn)生的哪些位置可能產(chǎn)生注入元素注入元素( (即原來是零元素，在計算過程中變成非零元素即原來是零元素，在計算過程中變成非零元素) )，在存儲時事先留了位置，即把這個原來是零元素的也按非零在存儲時事先留了位置，即把這個原來是零元素的也按非零元素一樣來存儲，這樣在計算中該元素由零元素變成非零元元素一樣來存儲，這樣在計算中該元素由零元素變成非零元素時就不必改變原來的檢索信息。素時就不必改變原來的檢索信息。 第二種辦法可以用下面介紹的鏈表存儲格式。其特點是當矩第二種辦法可以用下面介紹的鏈表存

19、儲格式。其特點是當矩陣陣A A的結(jié)構(gòu)發(fā)生變化時修改靈活，不必事先存儲這些零元素，的結(jié)構(gòu)發(fā)生變化時修改靈活，不必事先存儲這些零元素，也不必在產(chǎn)生非零注入元素時進行插入等處理。也不必在產(chǎn)生非零注入元素時進行插入等處理。3 32 2 稀疏技術(shù)稀疏技術(shù)4.4.鏈表（鏈表（ Link) Link) 存儲格式存儲格式以按行存儲的格式為例來說明。以按行存儲的格式為例來說明。這時需要按行存儲格式中的三個數(shù)組外還需要增加數(shù)組：這時需要按行存儲格式中的三個數(shù)組外還需要增加數(shù)組： VAVA按行存儲矩陣按行存儲矩陣A A中的非零元中的非零元a aijij，共，共個，個， JA JA按行存儲矩陣按行存儲矩陣A A中非零

20、元的列號，共中非零元的列號，共個，個， IA IA記錄記錄A A中每行第一個非零元素在中每行第一個非零元素在VAVA中的位置，共中的位置，共n n個。個。 LINK LINK下一個非零元素在下一個非零元素在VAVA中的位置，對每行最后一個非零元中的位置，對每行最后一個非零元素，該值置為素，該值置為0 0。 NA NA每行非零元素的個數(shù)。每行非零元素的個數(shù)。當新增加一個非零元素時，可把它排當新增加一個非零元素時，可把它排在最后，并根據(jù)該非零元素在該行中在最后，并根據(jù)該非零元素在該行中的位置的不同來修改其相鄰元素的的位置的不同來修改其相鄰元素的LINKLINK值例如，新增值例如，新增a a1313

21、，把，把a13排在第排在第1111個位置，把個位置，把a a1212的的LINKLINK值由值由3 3改為改為1111， a13本身的本身的LINKLINK值置為值置為3 3，NA(1)NA(1)增加增加1 1，變?yōu)樽優(yōu)? 4。a13111134a1333.2 3.2 稀疏技術(shù)稀疏技術(shù)二、稀疏矩陣的因子分解二、稀疏矩陣的因子分解對對n n階矩陣階矩陣A可以通過可以通過LU分解的方法分解成為一個下三角矩陣分解的方法分解成為一個下三角矩陣L和一和一個單位上三角矩陣個單位上三角矩陣U的乘積：的乘積：ALULU分解分為兩步分解分為兩步： （1）按行規(guī)格化運算；）按行規(guī)格化運算； （2）消去運算或更新運

22、算。）消去運算或更新運算。也可以將也可以將A分解成一個單位下三角矩陣分解成一個單位下三角矩陣L、一個對角矩陣、一個對角矩陣D和一個單位和一個單位下三角矩陣下三角矩陣U的乘積形式。的乘積形式。 ALDU3 32 2 稀疏技術(shù)稀疏技術(shù)三、利用系數(shù)矩陣因子表求解稀疏線性代數(shù)方程組三、利用系數(shù)矩陣因子表求解稀疏線性代數(shù)方程組對對n維線性代數(shù)方程組：維線性代數(shù)方程組：1.1.前代運算前代運算將將L L分解成一個單位矩陣和一個嚴格下三角矩陣分解成一個單位矩陣和一個嚴格下三角矩陣 之和之和先求先求z z1 1，再求，再求 z z2 2 ，.，最，最后求后求z zn n。3 32 2 稀疏技術(shù)稀疏技術(shù)2.2.

23、除法運算除法運算3 32 2 稀疏技術(shù)稀疏技術(shù)3.3.回代運算：將回代運算：將U U分解為一個單位矩陣和一個嚴格上三角矩陣分解為一個單位矩陣和一個嚴格上三角矩陣 之和之和先求先求x xn n，.，最后求，最后求x x1 1節(jié)點編號優(yōu)化節(jié)點編號優(yōu)化 3.3 稀疏矩陣的圖論描述 在電力網(wǎng)絡分析中，稀疏線性代數(shù)方程組的系數(shù)矩陣的稀疏結(jié)構(gòu)和電在電力網(wǎng)絡分析中，稀疏線性代數(shù)方程組的系數(shù)矩陣的稀疏結(jié)構(gòu)和電力網(wǎng)絡的拓撲結(jié)構(gòu)相對應。節(jié)點導納矩陣的非對角非零元素和電力網(wǎng)絡的力網(wǎng)絡的拓撲結(jié)構(gòu)相對應。節(jié)點導納矩陣的非對角非零元素和電力網(wǎng)絡的串聯(lián)支路有一一對應的關(guān)系，導納矩陣的稀疏結(jié)構(gòu)可以用圖來描述。稀疏串聯(lián)支路有一

24、一對應的關(guān)系，導納矩陣的稀疏結(jié)構(gòu)可以用圖來描述。稀疏矩陣的因子表的稀疏結(jié)構(gòu)也可以用圖來描述。在因子分解的過程中，矩陣矩陣的因子表的稀疏結(jié)構(gòu)也可以用圖來描述。在因子分解的過程中，矩陣的稀疏結(jié)構(gòu)將發(fā)生變化，相應的圖的結(jié)構(gòu)也將發(fā)生變化。本節(jié)內(nèi)容就是利的稀疏結(jié)構(gòu)將發(fā)生變化，相應的圖的結(jié)構(gòu)也將發(fā)生變化。本節(jié)內(nèi)容就是利用網(wǎng)絡圖對稀疏矩陣的因子分解和稀疏矢量的前代回代過程進行分析。用網(wǎng)絡圖對稀疏矩陣的因子分解和稀疏矢量的前代回代過程進行分析。 電網(wǎng)電網(wǎng)矩陣（計算，變換矩陣（計算，變換) 矩陣矩陣網(wǎng)絡拓撲網(wǎng)絡拓撲1 基本定義和術(shù)語假設假設Ax=bAx=b中，中，A A是對稱的稀疏矩陣是對稱的稀疏矩陣( (3-

25、113-11) )，b b是獨立矢量，是獨立矢量，x x是解矢量。是解矢量。將將A A分解成因子表分解成因子表( (3-123-12) )，則，則A=UTDU （式（式1）。下面給出幾個定義：下面給出幾個定義： A A圖：是和矩陣圖：是和矩陣A A有相同拓撲關(guān)系的網(wǎng)絡圖。有相同拓撲關(guān)系的網(wǎng)絡圖。（圖圖） 有向有向A A圖：是在給定的圖：是在給定的A A圖上，對于給定的節(jié)點編號，圖上，對于給定的節(jié)點編號， 規(guī)定規(guī)定每條邊的正方向都是由小號節(jié)點指向大號節(jié)點，形成的有向圖。每條邊的正方向都是由小號節(jié)點指向大號節(jié)點，形成的有向圖。（圖（圖） 賦權(quán)有向賦權(quán)有向A A圖：在有向圖：在有向A A圖上，將圖上

26、，將A A的非對角非零元素所對應的邊的非對角非零元素所對應的邊稱為互邊，并將該邊的邊權(quán)賦之以該非零元素的值；將稱為互邊，并將該邊的邊權(quán)賦之以該非零元素的值；將A A的對角元的對角元素用接地邊模擬，稱為自邊，賦以該對角元素的值。這樣即得到賦素用接地邊模擬，稱為自邊，賦以該對角元素的值。這樣即得到賦權(quán)有向權(quán)有向A A圖，它保存了矩陣圖，它保存了矩陣A A中的所有信息。中的所有信息。（圖）圖） 按同樣的方式可以來描述因子表按同樣的方式可以來描述因子表U U。（。（見書見書57575858頁頁）轉(zhuǎn)到2.因子分解過程的圖論描述 將對稱矩陣將對稱矩陣A A因子分解就是要將因子分解就是要將（311）式的矩陣

27、式的矩陣A A分解成分解成（3 31212）式式的矩陣的矩陣U U和和D D， D D是對角線矩陣，并使是對角線矩陣，并使A=UTDU 。在圖上，就是要將賦權(quán)有。在圖上，就是要將賦權(quán)有向向A A圖變成賦權(quán)有向因子圖。因子分解的過程按照節(jié)點號由小到大的順序依次圖變成賦權(quán)有向因子圖。因子分解的過程按照節(jié)點號由小到大的順序依次進行，每步計算包括了規(guī)格化運算和消去運算兩個步驟。進行，每步計算包括了規(guī)格化運算和消去運算兩個步驟。也就是將第也就是將第4949頁上的計頁上的計算流程在圖上實現(xiàn)。算流程在圖上實現(xiàn)。 （1 1）規(guī)格化運算）規(guī)格化運算（圖） 由于由于A A是對稱矩陣，當需要對是對稱矩陣，當需要對A

28、 A的第的第p p行元素進行規(guī)格化計算時，只行元素進行規(guī)格化計算時，只需要對需要對A A 矩陣中上三角部分中的第矩陣中上三角部分中的第p p行非零元素進行。如圖，因子分解行非零元素進行。如圖，因子分解過程進行到第過程進行到第p p步時，需要規(guī)格化的三個元素的列號分別是步時，需要規(guī)格化的三個元素的列號分別是j j，k k，l l。規(guī)。規(guī)格化運算的公式為格化運算的公式為: :api = api/app pi, i=j, k, l pi, i=j, k, l （式（式2 2） 這在賦權(quán)有向這在賦權(quán)有向A A圖上，相當于對節(jié)點圖上，相當于對節(jié)點p p發(fā)出的所有互邊的邊權(quán)加以修正，發(fā)出的所有互邊的邊權(quán)加

29、以修正，新的邊權(quán)等于原邊權(quán)除以節(jié)點新的邊權(quán)等于原邊權(quán)除以節(jié)點p p的自邊邊權(quán)。這種操作只改變節(jié)點的自邊邊權(quán)。這種操作只改變節(jié)點p p發(fā)出的發(fā)出的互邊邊權(quán)，邊數(shù)并未增加。互邊邊權(quán)，邊數(shù)并未增加。 （2 2）消去運算）消去運算 (圖) 取第取第p p行第行第p p列為軸線，第列為軸線，第p p步的消去運算實際上就是要對處步的消去運算實際上就是要對處于軸線上的于軸線上的非零元素非零元素所在的行列相交叉的位置上的元素進行消去運所在的行列相交叉的位置上的元素進行消去運算。如圖，需要對處于第算。如圖，需要對處于第p p行第行第p p列上的非零元素所在的列上的非零元素所在的j j，k k，l l行和行和j

30、j，k k，l l列相交叉的位置上的共列相交叉的位置上的共9 9個元素進行消去運算。如果只保留上三角矩個元素進行消去運算。如果只保留上三角矩陣，只需要對三個對角元素和三個非對角元素進行消去運算。陣，只需要對三個對角元素和三個非對角元素進行消去運算。 對對角元素的修正公式是對對角元素的修正公式是 aii = aii - aipapi pi, i=j, k, l （式（式3） 因為在消去運算之前已經(jīng)對因為在消去運算之前已經(jīng)對api進行過規(guī)格化運算，而式中的進行過規(guī)格化運算，而式中的aip還沒有進行過規(guī)格化，而還沒有進行過規(guī)格化，而 aip = apiapp 因此使用上三角元素計算時，消去運算的公式

31、應該用下式：因此使用上三角元素計算時，消去運算的公式應該用下式： aii = aii api2app pi, i=j, k, l （式（式4） 在賦權(quán)有向在賦權(quán)有向A圖上，就是對節(jié)點圖上，就是對節(jié)點p發(fā)出的邊的收點發(fā)出的邊的收點j, k, l上上的自邊邊權(quán)進行修正，邊權(quán)減少的自邊邊權(quán)進行修正，邊權(quán)減少api2app。 對于上三角部分的非零元素，共有三個需要修正，即對于上三角部分的非零元素，共有三個需要修正，即a ajk jk, , a akl kl, , a ajl jl, , 如圖。如圖。對于非對角元素，消去運算的公式為：對于非對角元素，消去運算的公式為： a aim im = = a ai

32、m im a aip ipa apm pm im, pi, pmim, pi, pm i, m i, m從從j, k, lj, k, l中取值中取值 （式（式5 5） 因為只儲存因為只儲存A A的上三角部分，所以的上三角部分，所以a aip ip（下三角元素）應該用（下三角元素）應該用a api pi代替，代替，上述公式變?yōu)椋荷鲜龉阶優(yōu)椋?a aim im = = a aim im a api pia apmpma apppp im, pi, pmim, pi, pi/ ji，說明邊是由小號節(jié)點指向大號節(jié)點，說明邊是由小號節(jié)點指向大號節(jié)點 if uif uij ij0 0 then / ui

33、j0 / uij0 ，說明是上三角矩陣，說明是上三角矩陣U U中的非零元素中的非零元素 zj=zj-uijzi end if end loop 將這段程序和賦權(quán)有向因子圖連系起來看，將這段程序和賦權(quán)有向因子圖連系起來看， u uij ij0 0 就表示賦權(quán)有向因就表示賦權(quán)有向因子圖上節(jié)點子圖上節(jié)點i i，j j之間有邊；之間有邊； u uij ij0 0，則圖上不出現(xiàn)邊。，則圖上不出現(xiàn)邊。 把把z zi i 定義為賦權(quán)有向因子圖上的點位，用定義為賦權(quán)有向因子圖上的點位，用e ei i 表示；賦權(quán)有向因子圖上的互表示；賦權(quán)有向因子圖上的互邊的邊權(quán)是邊的邊權(quán)是u uij ij，則上面的程序可以寫成

34、：，則上面的程序可以寫成： ej = ej - uij ei ij, ji ij, ji （式（式7 7） 線性代數(shù)方程組中獨立矢量或解矢量中的非零元素可以用賦權(quán)有向因子圖上線性代數(shù)方程組中獨立矢量或解矢量中的非零元素可以用賦權(quán)有向因子圖上節(jié)點的點位來描述，而前代過程可在賦權(quán)有向因子圖上用點位的變化來描述。節(jié)點的點位來描述，而前代過程可在賦權(quán)有向因子圖上用點位的變化來描述。首先，在賦權(quán)有向因子圖上，將每個節(jié)點的點位賦值以獨立矢量首先，在賦權(quán)有向因子圖上，將每個節(jié)點的點位賦值以獨立矢量b b中相應的非零中相應的非零元素的值。然后在賦權(quán)有向因子圖上按節(jié)點號元素的值。然后在賦權(quán)有向因子圖上按節(jié)點號i

35、 i從小到大順序（因為是前代）依從小到大順序（因為是前代）依次按（式次按（式7 7）修正該節(jié)點）修正該節(jié)點i i發(fā)出邊的對端節(jié)點發(fā)出邊的對端節(jié)點j j的點位，將對端節(jié)點的點位，將對端節(jié)點j j的點位減小的點位減小u uij ij e ei i 。這一過程一種進行到將所有點都掃描完。如果節(jié)點這一過程一種進行到將所有點都掃描完。如果節(jié)點i i的點位為零，說明的點位為零，說明z zi i 為零，為零，上述修正不需要做。這一過程結(jié)束后，因子圖上的點位就是前代的結(jié)果。（對上述修正不需要做。這一過程結(jié)束后，因子圖上的點位就是前代的結(jié)果。（對照照5151頁式頁式3 36a6a） 2 . 2 . 規(guī)格化過程規(guī)

36、格化過程 規(guī)格化過程的實質(zhì)是求解規(guī)格化過程的實質(zhì)是求解Dy=z中的中的y y，D是對角元素矩陣，是對角元素矩陣，z在前代過程在前代過程中已經(jīng)求出。因此求解中已經(jīng)求出。因此求解y很容易，只需要做除法運算很容易，只需要做除法運算 yi = zi/dii 在賦權(quán)有向因子圖上，也就是將前代結(jié)束后節(jié)點在賦權(quán)有向因子圖上，也就是將前代結(jié)束后節(jié)點i i的點位的點位e ei i 除以節(jié)點除以節(jié)點i i的自的自邊邊權(quán)，即邊邊權(quán)，即 （式（式8 8）。）。 3. 3. 回代過程回代過程 令賦權(quán)有向因子圖上的點位已經(jīng)是經(jīng)過前代和規(guī)格化后的值。按節(jié)點號令賦權(quán)有向因子圖上的點位已經(jīng)是經(jīng)過前代和規(guī)格化后的值。按節(jié)點號j

37、j從從n n開始，由大到小，對所有指向開始，由大到小，對所有指向j j的邊其發(fā)端節(jié)點的邊其發(fā)端節(jié)點i i的點位進行修正（也就是逆著的點位進行修正（也就是逆著各邊的方向），修正公式為：各邊的方向），修正公式為： （式（式9 9） 當所有節(jié)點的點位都修正完畢，回代過程結(jié)束。當所有節(jié)點的點位都修正完畢，回代過程結(jié)束。 4. 4.總結(jié)總結(jié) 在圖上進行前代回代的計算步驟如下：在圖上進行前代回代的計算步驟如下： (1) 將獨立矢量將獨立矢量b的非零元素賦值為賦權(quán)有向因子圖上的點位。的非零元素賦值為賦權(quán)有向因子圖上的點位。 (2) 掃描掃描i從從1到到n-1。用（式用（式7）修正節(jié)點）修正節(jié)點i發(fā)出的邊的對端節(jié)點發(fā)出的邊的對端節(jié)點j 的點位。的點位。 （3） 對所有節(jié)點用（式對所有節(jié)點用（式8）對點位進行規(guī)格化。）對點位進行規(guī)格化。 （4） 掃描掃描j從從n到到2 。對所有指向節(jié)點。對所有指向節(jié)點j的邊的發(fā)端節(jié)點的邊的發(fā)端節(jié)點i，用，用 （式（式9）修正其點位。）修正其點位。 5. 例題（例題（63頁頁 ）板書）板書4.不對稱稀疏矩陣的圖上因子分解 定義（第定義（第6464頁）頁） 圖圖 圖圖 3.5 3.5 節(jié)點編號優(yōu)化節(jié)點編號優(yōu)化