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

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

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

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

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

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

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

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

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

10、AVA存儲(chǔ)存儲(chǔ)A A中非零元素中非零元素a aijij的值，共的值，共個(gè)，個(gè)，IAIA存儲(chǔ)存儲(chǔ)A A中非零元素中非零元素a aijij的行指標(biāo)的行指標(biāo)i i，共，共個(gè)，個(gè)，JAJA存儲(chǔ)存儲(chǔ)A A中非零元素中非零元素a aijij的列指標(biāo)的列指標(biāo)j,j,共共個(gè)。個(gè)。總共需要總共需要33個(gè)存儲(chǔ)單元。個(gè)存儲(chǔ)單元。3.2 3.2 稀疏技術(shù)稀疏技術(shù) 散居格式的優(yōu)點(diǎn)散居格式的優(yōu)點(diǎn):A:A中的非零元在上面數(shù)組中的位置可任意排列，中的非零元在上面數(shù)組中的位置可任意排列，修改靈活；修改靈活； 缺點(diǎn)：因其存儲(chǔ)順序無(wú)一定規(guī)律，檢索起來(lái)不方便。缺點(diǎn)：因其存儲(chǔ)順序無(wú)一定規(guī)律，檢索起來(lái)不方便。 例如：在上面數(shù)組中查找下標(biāo)

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

12、元，同一行中的非零元，同一行( (列列) )元素依次排在一起。元素依次排在一起。 以按行存儲(chǔ)為例，其存儲(chǔ)格式是：以按行存儲(chǔ)為例，其存儲(chǔ)格式是： VAVA按行存儲(chǔ)矩陣按行存儲(chǔ)矩陣A A中的非零元中的非零元a aijij，共，共個(gè)，個(gè)， JA JA按行存儲(chǔ)矩陣按行存儲(chǔ)矩陣A A中非零元的列號(hào)，共中非零元的列號(hào)，共個(gè)，個(gè)， IA IA記錄記錄A A中每行第一個(gè)非零元素在中每行第一個(gè)非零元素在VAVA中的位置，共中的位置，共n n個(gè)。個(gè)。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)個(gè)非零元就是個(gè)非零元就是A A中第中第i i行的全部非零元，非零行的全部非零元，非零元的值是元的值是VA(k)VA(k)，其列號(hào)由，其列號(hào)由JA(k)JA(k)給出。給出。找第找第i i行第行第j j列元素列元素a aijij在在VAVA中的位置：對(duì)中的位置：對(duì)k k從從IA(i)IA(i)到到IA(i+1)-1IA(i+1)-1，判，判列號(hào)列號(hào)JA(k)JA(k)是否等于是否等于j j，如等，則，如等，則VA(k)VA(k)即是要找的非零元即是要找的非零元a aijij。這種存儲(chǔ)方案可以用于存儲(chǔ)任意稀疏矩陣，這種存儲(chǔ)方案可以用于存儲(chǔ)任

14、意稀疏矩陣，A A可以不是正方矩陣。可以不是正方矩陣。如果如果A A是方矩陣，可以把是方矩陣，可以把A A的對(duì)角元素提出來(lái)單獨(dú)存儲(chǔ)，而對(duì)角元的對(duì)角元素提出來(lái)單獨(dú)存儲(chǔ)，而對(duì)角元素的行列指標(biāo)都無(wú)需記憶。素的行列指標(biāo)都無(wú)需記憶。3.2 3.2 稀疏技術(shù)稀疏技術(shù)3 3三角檢索存儲(chǔ)格式三角檢索存儲(chǔ)格式 三角檢索的存儲(chǔ)格式特別適合稀疏矩陣的三角分解的計(jì)算格三角檢索的存儲(chǔ)格式特別適合稀疏矩陣的三角分解的計(jì)算格式。有幾種不同的存儲(chǔ)格式，這里以按行存儲(chǔ)式。有幾種不同的存儲(chǔ)格式，這里以按行存儲(chǔ)A A的上三角部分的上三角部分非零元，按列存非零元，按列存A A的下三角部分非零元這種存儲(chǔ)格式來(lái)說(shuō)明。的下三角部分非零元這

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

16、置中的位置( (首地首地址址) )；DD存儲(chǔ)存儲(chǔ)A A的對(duì)角元素的值，其檢索下標(biāo)不需要存儲(chǔ)的對(duì)角元素的值，其檢索下標(biāo)不需要存儲(chǔ). .例：有了有了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、元素的列號(hào)，指出了該元素的列號(hào)，U(k)U(k)是該非零是該非零元素的值元素的值對(duì)于按列存儲(chǔ)的格式進(jìn)行查找的情況類同。對(duì)于按列存儲(chǔ)的格式進(jìn)行查找的情況類同。列號(hào)列號(hào)位置位置3.2 3.2 稀疏技術(shù)稀疏技術(shù)三角檢索存儲(chǔ)格式在矩陣三角檢索存儲(chǔ)格式在矩陣A A的稀疏結(jié)構(gòu)已確定的情況下使用是的稀疏結(jié)構(gòu)已確定的情況下使用是十分方便的。但在計(jì)算過(guò)程中，如果十分方便的。但在計(jì)算過(guò)程中，如果A A的稀疏結(jié)構(gòu)發(fā)生了變化，的稀疏結(jié)構(gòu)發(fā)生了變化，即其中的非零元素的分布位置發(fā)生變化，相應(yīng)的檢索信息也即其中的非零元素的分布位置發(fā)生變化，相應(yīng)的檢索信息也要隨著變化，很不方便。有兩種辦法處理這類問(wèn)題。要隨著變化，很不方便。

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

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

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

21、，把，把a(bǔ)13排在第排在第1111個(gè)位置，把個(gè)位置，把a(bǔ) 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ù)二、稀疏矩陣的因子分解二、稀疏矩陣的因子分解對(duì)對(duì)n n階矩陣階矩陣A可以通過(guò)可以通過(guò)LU分解的方法分解成為一個(gè)下三角矩陣分解的方法分解成為一個(gè)下三角矩陣L和一和一個(gè)單位上三角矩陣個(gè)單位上三角矩陣U的乘積：的乘積：ALULU分解分為兩步分解分為兩步： （1）按行規(guī)格化運(yùn)算；）按行規(guī)格化運(yùn)算； （2）消去運(yùn)算或更新運(yùn)

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

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

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

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

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

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

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

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

30、j，k k，l l列相交叉的位置上的共列相交叉的位置上的共9 9個(gè)元素進(jìn)行消去運(yùn)算。如果只保留上三角矩個(gè)元素進(jìn)行消去運(yùn)算。如果只保留上三角矩陣，只需要對(duì)三個(gè)對(duì)角元素和三個(gè)非對(duì)角元素進(jìn)行消去運(yùn)算。陣，只需要對(duì)三個(gè)對(duì)角元素和三個(gè)非對(duì)角元素進(jìn)行消去運(yùn)算。 對(duì)對(duì)角元素的修正公式是對(duì)對(duì)角元素的修正公式是 aii = aii - aipapi pi, i=j, k, l （式（式3） 因?yàn)樵谙ミ\(yùn)算之前已經(jīng)對(duì)因?yàn)樵谙ミ\(yùn)算之前已經(jīng)對(duì)api進(jìn)行過(guò)規(guī)格化運(yùn)算，而式中的進(jìn)行過(guò)規(guī)格化運(yùn)算，而式中的aip還沒(méi)有進(jìn)行過(guò)規(guī)格化，而還沒(méi)有進(jìn)行過(guò)規(guī)格化，而 aip = apiapp 因此使用上三角元素計(jì)算時(shí)，消去運(yùn)算的公式

31、應(yīng)該用下式：因此使用上三角元素計(jì)算時(shí)，消去運(yùn)算的公式應(yīng)該用下式： aii = aii api2app pi, i=j, k, l （式（式4） 在賦權(quán)有向在賦權(quán)有向A圖上，就是對(duì)節(jié)點(diǎn)圖上，就是對(duì)節(jié)點(diǎn)p發(fā)出的邊的收點(diǎn)發(fā)出的邊的收點(diǎn)j, k, l上上的自邊邊權(quán)進(jìn)行修正，邊權(quán)減少的自邊邊權(quán)進(jìn)行修正，邊權(quán)減少api2app。 對(duì)于上三角部分的非零元素，共有三個(gè)需要修正，即對(duì)于上三角部分的非零元素，共有三個(gè)需要修正，即a ajk jk, , a akl kl, , a ajl jl, , 如圖。如圖。對(duì)于非對(duì)角元素，消去運(yùn)算的公式為：對(duì)于非對(duì)角元素，消去運(yùn)算的公式為： 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） 因?yàn)橹粌?chǔ)存因?yàn)橹粌?chǔ)存A A的上三角部分，所以的上三角部分，所以a aip ip（下三角元素）應(yīng)該用（下三角元素）應(yīng)該用a api pi代替，代替，上述公式變?yōu)椋荷鲜龉阶優(yōu)椋?a aim im = = a aim im a api pia apmpma apppp im, pi, pmim, pi, pi/ ji，說(shuō)明邊是由小號(hào)節(jié)點(diǎn)指向大號(hào)節(jié)點(diǎn)，說(shuō)明邊是由小號(hào)節(jié)點(diǎn)指向大號(hào)節(jié)點(diǎn) if uif uij ij0 0 then / ui

33、j0 / uij0 ，說(shuō)明是上三角矩陣，說(shuō)明是上三角矩陣U U中的非零元素中的非零元素 zj=zj-uijzi end if end loop 將這段程序和賦權(quán)有向因子圖連系起來(lái)看，將這段程序和賦權(quán)有向因子圖連系起來(lái)看， u uij ij0 0 就表示賦權(quán)有向因就表示賦權(quán)有向因子圖上節(jié)點(diǎn)子圖上節(jié)點(diǎn)i i，j j之間有邊；之間有邊； u uij ij0 0，則圖上不出現(xiàn)邊。，則圖上不出現(xiàn)邊。 把把z zi i 定義為賦權(quán)有向因子圖上的點(diǎn)位，用定義為賦權(quán)有向因子圖上的點(diǎ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ù)方程組中獨(dú)立矢量或解矢量中的非零元素可以用賦權(quán)有向因子圖上線性代數(shù)方程組中獨(dú)立矢量或解矢量中的非零元素可以用賦權(quán)有向因子圖上節(jié)點(diǎn)的點(diǎn)位來(lái)描述，而前代過(guò)程可在賦權(quán)有向因子圖上用點(diǎn)位的變化來(lái)描述。節(jié)點(diǎn)的點(diǎn)位來(lái)描述，而前代過(guò)程可在賦權(quán)有向因子圖上用點(diǎn)位的變化來(lái)描述。首先，在賦權(quán)有向因子圖上，將每個(gè)節(jié)點(diǎn)的點(diǎn)位賦值以獨(dú)立矢量首先，在賦權(quán)有向因子圖上，將每個(gè)節(jié)點(diǎn)的點(diǎn)位賦值以獨(dú)立矢量b b中相應(yīng)的非零中相應(yīng)的非零元素的值。然后在賦權(quán)有向因子圖上按節(jié)點(diǎn)號(hào)元素的值。然后在賦權(quán)有向因子圖上按節(jié)點(diǎn)號(hào)i

35、 i從小到大順序（因?yàn)槭乔按┮缽男〉酱箜樞颍ㄒ驗(yàn)槭乔按┮来伟矗ㄊ酱伟矗ㄊ? 7）修正該節(jié)點(diǎn)）修正該節(jié)點(diǎn)i i發(fā)出邊的對(duì)端節(jié)點(diǎn)發(fā)出邊的對(duì)端節(jié)點(diǎn)j j的點(diǎn)位，將對(duì)端節(jié)點(diǎn)的點(diǎn)位，將對(duì)端節(jié)點(diǎn)j j的點(diǎn)位減小的點(diǎn)位減小u uij ij e ei i 。這一過(guò)程一種進(jìn)行到將所有點(diǎn)都掃描完。如果節(jié)點(diǎn)這一過(guò)程一種進(jìn)行到將所有點(diǎn)都掃描完。如果節(jié)點(diǎn)i i的點(diǎn)位為零，說(shuō)明的點(diǎn)位為零，說(shuō)明z zi i 為零，為零，上述修正不需要做。這一過(guò)程結(jié)束后，因子圖上的點(diǎn)位就是前代的結(jié)果。（對(duì)上述修正不需要做。這一過(guò)程結(jié)束后，因子圖上的點(diǎn)位就是前代的結(jié)果。（對(duì)照照5151頁(yè)式頁(yè)式3 36a6a） 2 . 2 . 規(guī)格化過(guò)程規(guī)

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

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