第6章 面向方程模擬法N

第6章面向(miànxiànɡ)方程模擬法共六十二頁(yè)第一節(jié)原理第二節(jié)面向方程模擬法與序貫?zāi)M法的比較第三節(jié)大型稀疏非線(xiàn)性方程組的降維解法

一、輸出變量的指定

二、回路(huílù)搜索法分解方程組

三、不可分解方程組的斷裂降維解法第四節(jié)稀疏矩陣的壓縮存儲(chǔ)

一、稀疏矩陣壓縮存儲(chǔ)的信息鏈指針

二、靜態(tài)存儲(chǔ)（列表法）

三、動(dòng)態(tài)存儲(chǔ)（三地址法）第一節(jié)原理(yuánlǐ)EquationOrientedMethod聯(lián)立方程模擬法共六十二頁(yè)面向方程法將整個(gè)系統(tǒng)聯(lián)合建模Subflow(S1,ALFA,S2,S3,S4)S2=S1+S4’以上混合器模型(móxíng)方程

S3=S2*ALFAS4=S2*(1–ALFA)’以上

分割器模型方程EndSub整個(gè)系統(tǒng)方程組，整體求解

序貫法模：每個(gè)單元為獨(dú)立(dúlì)子程序?qū)ν馓峁┙Y(jié)果需要迭代循環(huán)物流的去哪里？共六十二頁(yè)過(guò)程(guòchéng)系統(tǒng)的模型方程模型(móxíng)方程：模型方程決策變量狀態(tài)變量①各種平衡方程②單元聯(lián)結(jié)方程③設(shè)計(jì)規(guī)定方程④物性方程⑤現(xiàn)象方程共六十二頁(yè)模型(móxíng)變量決策變量所有單元模塊的設(shè)備(shèbèi)參數(shù)進(jìn)料流股變量狀態(tài)參數(shù)所有中間變量產(chǎn)品流股變量?jī)?nèi)部變量等共六十二頁(yè)模擬(mónǐ)結(jié)構(gòu)循環(huán)物流方程(fāngchéng)設(shè)計(jì)規(guī)定方程僅提供方程多!!!特殊處理共六十二頁(yè)物性系統(tǒng)(xìtǒng)的處理占用70~80%的計(jì)算量處理方法(fāngfǎ)：1）不提供方程組，僅提供子程序方程數(shù)量大幅減少，但需經(jīng)常調(diào)用物性子程序，效果有限2）提供k,h

的方程組，其它物性由子程序調(diào)用

k,h最常用，其它較少用到。效果很好物性：焓、相平衡常數(shù)、密度、粘度、導(dǎo)熱系數(shù)等共六十二頁(yè)第一節(jié)原理第二節(jié)面向方程模擬法與序貫?zāi)M法的比較第三節(jié)大型稀疏非線(xiàn)性方程組的降維解法

一、輸出變量的指定

二、回路搜索法分解方程組

三、不可(bùkě)分解方程組的斷裂降維解法第四節(jié)稀疏矩陣的壓縮存儲(chǔ)

一、稀疏矩陣壓縮存儲(chǔ)的信息鏈指針

二、靜態(tài)存儲(chǔ)（列表法）

三、動(dòng)態(tài)存儲(chǔ)（三地址法）第二節(jié)面向(miànxiànɡ)方程模擬法與序貫?zāi)M法的比較共六十二頁(yè)模擬(mónǐ)方法結(jié)構(gòu)特征序貫?zāi)K(mókuài)模擬法面向方程模擬法共六十二頁(yè)1.序貫?zāi)K(mókuài)法優(yōu)點(diǎn)：

①與實(shí)際過(guò)程的直觀(guān)聯(lián)系(liánxì)強(qiáng)，軟件的建立、維護(hù)和擴(kuò)充很方便；

②易于通用化；

③需要的計(jì)算機(jī)內(nèi)存較??；

④易于診斷出錯(cuò)位置；缺點(diǎn)：

循環(huán)物流及設(shè)計(jì)問(wèn)題：慢共六十二頁(yè)2.面向(miànxiànɡ)方程法優(yōu)點(diǎn)

①便于實(shí)際用戶(hù)的提出的質(zhì)量性能要求。有設(shè)計(jì)規(guī)定的系統(tǒng)，僅增加幾個(gè)方程

②用空間換取時(shí)間。相同的過(guò)程單元出現(xiàn)多次，將占用更多的存儲(chǔ)空間，自由度的選擇也可能各不相同

③以空間換取求解的數(shù)值穩(wěn)定性。有較多回流(huíliú)高度交互作用流程相對(duì)容易收斂共六十二頁(yè)2.面向(miànxiànɡ)方程法缺點(diǎn)

①要求提供(tígōng)較好的初值

②難于自動(dòng)產(chǎn)生流程的模型方程組，難以通用化

③不容易診斷出現(xiàn)錯(cuò)誤的地方。共六十二頁(yè)序貫法與聯(lián)立方程(liánlìfānɡchénɡ)法對(duì)比內(nèi)容序貫法聯(lián)立方程法占用存儲(chǔ)空間小大迭代循環(huán)圈多少計(jì)算效率低高指定設(shè)計(jì)規(guī)定不靈活靈活初值要求低高錯(cuò)誤診斷易難編程、調(diào)試較易較難共六十二頁(yè)聯(lián)立模塊(mókuài)法序貫?zāi)K法建立流程簡(jiǎn)單，處理循環(huán)流與設(shè)計(jì)規(guī)定需迭代聯(lián)立方程法同時(shí)求解，但建模困難聯(lián)立模塊法又稱(chēng)雙層法，將過(guò)程系統(tǒng)的近似模型方程與單元(dānyuán)模塊交替求解聯(lián)立模塊法兼有序貫?zāi)K法和面向方程法的優(yōu)點(diǎn)。既能使用序貫?zāi)K法積累的大量模塊，又能將最費(fèi)計(jì)算時(shí)間的流程收斂和設(shè)計(jì)約束收斂等迭代循環(huán)合并處理，通過(guò)聯(lián)立求解達(dá)到同時(shí)收斂共六十二頁(yè)斷裂變量(biànliàng)不迭代簡(jiǎn)化(jiǎnhuà)模型的產(chǎn)生??？共六十二頁(yè)聯(lián)立模塊(mókuài)法特點(diǎn)以簡(jiǎn)化模型聯(lián)立求解取代序貫法的回路迭代計(jì)算和設(shè)計(jì)規(guī)定計(jì)算可利用原有的序貫法資源方程數(shù)量較聯(lián)立方程法要少得多，求解難度(nádù)大大降低難點(diǎn)：簡(jiǎn)化方程的產(chǎn)生及其適用范圍共六十二頁(yè)過(guò)程系統(tǒng)(xìtǒng)穩(wěn)態(tài)模擬三種方法的比較方法優(yōu)點(diǎn)缺點(diǎn)代表軟件系統(tǒng)序貫?zāi)K法與工程師直觀(guān)經(jīng)驗(yàn)一致，便于學(xué)習(xí)使用；易于通用化，已積累了豐富的單元模塊；需要計(jì)算機(jī)內(nèi)存較?。挥绣e(cuò)誤易于診斷檢查；再循環(huán)引起的收斂迭代很費(fèi)機(jī)時(shí)；進(jìn)行設(shè)計(jì)型計(jì)算時(shí)，很費(fèi)機(jī)時(shí)；不宜用于最優(yōu)化計(jì)算；PROCESS(美)CONCEPT(英)CAPES(日)ASPEN(美)FLOWTRAN(美)面向方程法解算快；模擬型計(jì)算與設(shè)計(jì)型計(jì)算一樣；適合最優(yōu)化計(jì)算，效率高；便于與動(dòng)態(tài)模擬聯(lián)合實(shí)現(xiàn)；要求給定較好的初值，否則可能得不到解；計(jì)算失敗后診斷錯(cuò)誤所在困難；形成通用化程序有困難有，故使用不便；難以繼承已有的單元操作模塊。ASCEND-Ⅱ(美)SPEEDUP(英)（雙層法）聯(lián)立模塊法可以利用前人開(kāi)發(fā)的單元操作模塊；可以避免序貫?zāi)K法中的循環(huán)流迭代；比較容易實(shí)現(xiàn)通用。將嚴(yán)格模型做成簡(jiǎn)化模型時(shí)，需要花費(fèi)機(jī)時(shí)；用簡(jiǎn)化模型來(lái)尋求優(yōu)化時(shí)，其解與嚴(yán)格與嚴(yán)格模型優(yōu)化解是否一致，有爭(zhēng)論。TISFLO（德）FLOWPACK-Ⅱ(英)共六十二頁(yè)第一節(jié)原理第二節(jié)面向方程模擬法與序貫?zāi)M法的比較第三節(jié)大型稀疏非線(xiàn)性方程組的降維解法

一、輸出變量(biànliàng)的指定

二、回路搜索法分解方程組

三、不可分解方程組的斷裂降維解法第四節(jié)稀疏矩陣的壓縮存儲(chǔ)

一、稀疏矩陣壓縮存儲(chǔ)的信息鏈指針

二、靜態(tài)存儲(chǔ)（列表法）

三、動(dòng)態(tài)存儲(chǔ)（三地址法）第三節(jié)大型(dàxíng)稀疏非線(xiàn)性方程組的降維解法共六十二頁(yè)系統(tǒng)方程多，整體(zhěngtǐ)求解難度很多處理(chǔlǐ)方法：方程組分解過(guò)程系統(tǒng)方程組的特點(diǎn)： 方程數(shù)多，變量多每個(gè)方程包含的變量不多每個(gè)變量存在的方程(出現(xiàn)次數(shù))不多稀疏方程組稀疏比將方程組轉(zhuǎn)化為有向圖，再應(yīng)用系統(tǒng)分解的手段分解成可順序求解的子方程組共六十二頁(yè)第一節(jié)原理第二節(jié)面向方程模擬法與序貫?zāi)M法的比較第三節(jié)大型稀疏非線(xiàn)性方程組的降維解法

一、輸出變量的指定

二、回路(huílù)搜索法分解方程組

三、不可分解方程組的斷裂降維解法第四節(jié)稀疏矩陣的壓縮存儲(chǔ)

一、稀疏矩陣壓縮存儲(chǔ)的信息鏈指針

二、靜態(tài)存儲(chǔ)（列表法）

三、動(dòng)態(tài)存儲(chǔ)（三地址法）

一、輸出(shūchū)變量的指定共六十二頁(yè)Hall各異條件(tiáojiàn)？方程組有解的必要條件(bìyàotiáojiàn)！輸出變量？介紹方程組決策變量影響時(shí)學(xué)過(guò)！將f2(x,y,z)=0改寫(xiě)為y=f2’(x,z)，y則稱(chēng)為f2的輸出變量N維方程組可指定N個(gè)不同的輸出變量失敗！x2出現(xiàn)最少，應(yīng)先考慮f3包含的變量最少，也應(yīng)優(yōu)先考慮！成功！包含變量少的方程和出現(xiàn)次數(shù)少的變量應(yīng)先考慮共六十二頁(yè)輸出變量(biànliàng)的指定方法：1)選事件矩陣中元素最少的行和其與元素最少的列的交點(diǎn)處元素對(duì)應(yīng)的變量作為優(yōu)先指定的輸出變量，然后從事件矩陣中刪去相應(yīng)的行和列。2)重復(fù)上述過(guò)程∶①若矩陣的所有行和列被刪除，則指定完畢。②若有行或列無(wú)法刪除，則表示與剩余(shèngyú)列對(duì)應(yīng)的變量不存在于與剩余(shèngyú)的行對(duì)應(yīng)的方程中。共六十二頁(yè)“Steward”通路(tōnglù)∶a)從矩陣的不飽和行(無(wú)輸出(shūchū)變量的行)或不飽和列(無(wú)輸出變量的列)的某一非輸出變量開(kāi)始，垂直找到與該元素在一列或一行的輸出變量。再轉(zhuǎn)90

，找到另一個(gè)非輸出變量，再垂直找到輸出變量，直到找到不飽和列或行中的某一非零元素。b)此軌跡就是“Steward”通路。將此通路上的輸出變量與非輸出變量互換，即可增加一個(gè)輸出變量。共六十二頁(yè)f1f2f3指定輸出(shūchū)變量的作用？將方程組轉(zhuǎn)化(zhuǎnhuà)為有向圖！可應(yīng)用過(guò)程系統(tǒng)分解的手段對(duì)方程系統(tǒng)進(jìn)行分解可及矩陣法索引矩陣法Steward通路搜索法Sargent-Westerberg搜索法（圖解法）共六十二頁(yè)例×不飽和行不飽和列共六十二頁(yè)×從不飽和行的任一非零開(kāi)始(kāishǐ)將出現(xiàn)(chūxiàn)死循環(huán)將Steward通路上的輸出變量與非輸出變量互換可增加一個(gè)輸出變量！Steward通路例共六十二頁(yè)第一節(jié)原理第二節(jié)面向方程模擬法與序貫?zāi)M法的比較第三節(jié)大型稀疏非線(xiàn)性方程組的降維解法

一、輸出變量的指定

二、回路搜索法分解方程組

三、不可分解方程組的斷裂降維解法第四節(jié)稀疏矩陣的壓縮存儲(chǔ)

一、稀疏矩陣壓縮存儲(chǔ)的信息(xìnxī)鏈指針

二、靜態(tài)存儲(chǔ)（列表法）

三、動(dòng)態(tài)存儲(chǔ)（三地址法）

二、回路(huílù)搜索法分解方程組共六十二頁(yè)回路搜索法分解方程組步驟:1）寫(xiě)出方程組事件矩陣，指定輸出變量2）如果每個(gè)方程都指定了一個(gè)不同的輸出變量，則方程組滿(mǎn)足(mǎnzú)Hall各異條件，轉(zhuǎn)6；否則轉(zhuǎn)3。

3）從不飽和行的一個(gè)非零開(kāi)始搜索Steward通路。如果能從不飽和行走到不飽和列，轉(zhuǎn)4；否則轉(zhuǎn)5。4）不能增加輸出變量數(shù)目，方程組無(wú)解，停止。

5）將Steward通路上的輸出變量與非輸出變量類(lèi)型互換，則可增加一個(gè)輸出變量。如果此時(shí)輸出變量的數(shù)目與方程數(shù)目相等，轉(zhuǎn)6；否則轉(zhuǎn)3）

6）將方程以節(jié)點(diǎn)形式排成一行，將每個(gè)方程與其輸出變量出現(xiàn)的方程節(jié)點(diǎn)以有向弧相連，即形成了方程組的有向圖。7）可以用可及矩陣法、索引矩陣法、Steward通路搜索法和圖解法等分解方程組。共六十二頁(yè)不飽和行不飽和列0從不飽和行開(kāi)始(kāishǐ)找Steward通路不飽和列將Steward通路上的輸出(shūchū)變量與非輸出(shūchū)變量對(duì)換指定輸出變量：共六十二頁(yè)最終的輸出(shūchū)變量指定：共六十二頁(yè)f1繪制(huìzhì)有向圖：f2f3f4f5f1x4f1f2x3f2f3x2f3f4x1f4f5x5f5共六十二頁(yè)f1f4f5f2f3搜索(sōusuǒ)回路：f2f3f1

f2

f5

f2

，

f2f5構(gòu)成(gòuchéng)回路，將f2f5作為組合節(jié)點(diǎn)，改寫(xiě)有向圖f1f2f5f3f4f2f5f1f4f5內(nèi)部弧內(nèi)部弧f1f2f3f4f5共六十二頁(yè)搜索(sōusuǒ)回路：f1

f2f5，無(wú)路可走！刪除f2f5，計(jì)入次序(cìxù)表，改寫(xiě)有向圖f1f3f4次序表f2f5f2f5f2f5f1

f3，無(wú)路可走！刪除f3，計(jì)入次序表，改寫(xiě)有向圖f3f3f1

f4

f1，構(gòu)成回路，形成最后一個(gè)組合節(jié)點(diǎn)，刪除f1f4，計(jì)入次序表f1f4計(jì)算順序共六十二頁(yè)第一節(jié)原理第二節(jié)面向方程模擬法與序貫?zāi)M法的比較第三節(jié)大型稀疏(xīshū)非線(xiàn)性方程組的降維解法

一、輸出變量的指定

二、回路搜索法分解方程組

三、不可分解方程組的斷裂降維解法第四節(jié)稀疏矩陣的壓縮存儲(chǔ)

一、稀疏矩陣壓縮存儲(chǔ)的信息鏈指針

二、靜態(tài)存儲(chǔ)（列表法）

三、動(dòng)態(tài)存儲(chǔ)（三地址法）

三、不可分解(fēnjiě)方程組的斷裂降維解法共六十二頁(yè)大規(guī)模方程組的處理(chǔlǐ)：分解成小規(guī)模方程組，順序求解問(wèn)題：子方程組規(guī)模(guīmó)仍很大整個(gè)方程組本身不可分解？必須聯(lián)立求解?。繑嗔呀稻S求解共六十二頁(yè)方程組的斷裂求解步驟(bùzhòu)如下∶

1)選輸出變量，分解方程組；

2)在分解后的子方程組中選擇包含變量數(shù)最少的方程(

=k)中的k-1變量作為斷裂變量；選擇k-1個(gè)包含變量數(shù)最多的方程作為驗(yàn)算方程；

3)降維后用回路搜索法進(jìn)一步分解；

4)給斷裂變量賦初值，求解降維后的方程組；

5)驗(yàn)算斷裂變量直到收斂。共六十二頁(yè)例整個(gè)方程組不可(bùkě)分解斷裂降維求解(qiújiě)

––迭代求解迭代求解––要求最少的斷裂變量！––選變量數(shù)最少的方程斷裂斷裂x1，即給定x1初值x3=f4’(x1)斷裂變量，賦初值斷裂1個(gè)變量，可排除一個(gè)方程，2個(gè)變量共六十二頁(yè)例斷裂(duànliè)變量狀態(tài)變量驗(yàn)算(yànsuàn)方程驗(yàn)算方程應(yīng)選擇含變量數(shù)最多的方程方程數(shù)比變量數(shù)多1個(gè)指定輸出變量分解方程組共六十二頁(yè)f1f3f5f6求解(qiújiě)順序：f5f6

f1f3共六十二頁(yè)計(jì)算(jìsuàn)步驟：假設(shè)x1初值由f4計(jì)算出x3聯(lián)合求解f1

f3

，得出x2,x4將x1,x2,x3,x4代入f5

f6聯(lián)合求解得x5,x6驗(yàn)算f2是否滿(mǎn)足，若滿(mǎn)足則結(jié)束(jiéshù)，否則轉(zhuǎn)6)重新假設(shè)x1初值轉(zhuǎn)2)共六十二頁(yè)四、n<m型稀疏(xīshū)非方程組的處理選決策變量獲得的方程組的結(jié)構(gòu)方程組進(jìn)行分解或斷裂降維按順序聯(lián)立求解(qiújiě)獲迭代求解(qiújiě)分解后的子方程組共六十二頁(yè)五、n>m型稀疏(xīshū)非方程組的處理①利用最小二乘法取得一組妥協(xié)(tuǒxié)解。②求解其中的m個(gè)方程共六十二頁(yè)第一節(jié)原理第二節(jié)面向方程模擬法與序貫?zāi)M法的比較第三節(jié)大型稀疏非線(xiàn)性方程組的降維解法

一、輸出變量的指定

二、回路搜索法分解(fēnjiě)方程組

三、不可分解方程組的斷裂降維解法第四節(jié)稀疏矩陣的壓縮存儲(chǔ)

一、稀疏矩陣壓縮存儲(chǔ)的信息鏈指針

二、靜態(tài)存儲(chǔ)（列表法）

三、動(dòng)態(tài)存儲(chǔ)（三地址法）第四節(jié)稀疏矩陣(jǔzhèn)的壓縮存儲(chǔ)共六十二頁(yè)n=1000，N=2000，

=0.2%全部存儲(chǔ)(cúnchǔ)，占用n2即106存儲(chǔ)單位其中998000個(gè)為零一次高斯消去運(yùn)算需1/3n3次加法和乘法運(yùn)算，約3.33億次以1微秒/次計(jì)，耗機(jī)時(shí)333秒以上采用稀疏矩陣存儲(chǔ)法只存儲(chǔ)非零元素，只對(duì)非零元素進(jìn)行運(yùn)算需占用10000個(gè)存儲(chǔ)單位，進(jìn)行20000次運(yùn)算需20毫秒共六十二頁(yè)第一節(jié)原理第二節(jié)面向方程模擬法與序貫?zāi)M法的比較第三節(jié)大型稀疏非線(xiàn)性方程組的降維解法

一、輸出變量的指定

二、回路搜索法分解方程組

三、不可分解方程組的斷裂(duànliè)降維解法第四節(jié)稀疏矩陣的壓縮存儲(chǔ)

一、稀疏矩陣壓縮存儲(chǔ)的信息鏈指針

二、靜態(tài)存儲(chǔ)（列表法）

三、動(dòng)態(tài)存儲(chǔ)（三地址法）

一、稀疏矩陣壓縮存儲(chǔ)的信息(xìnxī)鏈指針共六十二頁(yè)非零元素(yuánsù)屬性∶l

行標(biāo)；l

列標(biāo)；l

指向本行中下一個(gè)非零元素(yuánsù)的指針；l

指向本列中下一個(gè)非零元素的指針；l

指向本行中前一個(gè)非零元素的指針；l

指向本列中前一個(gè)非零元素的指針；共六十二頁(yè)第一節(jié)原理第二節(jié)面向方程(fāngchéng)模擬法與序貫?zāi)M法的比較第三節(jié)大型稀疏非線(xiàn)性方程組的降維解法

一、輸出變量的指定

二、回路搜索法分解方程組

三、不可分解方程組的斷裂降維解法第四節(jié)稀疏矩陣的壓縮存儲(chǔ)

一、稀疏矩陣壓縮存儲(chǔ)的信息鏈指針

二、靜態(tài)存儲(chǔ)（列表法）

三、動(dòng)態(tài)存儲(chǔ)（三地址法）

二、靜態(tài)(jìngtài)存儲(chǔ)（列表法）共六十二頁(yè)一、靜態(tài)存儲(chǔ)(cúnchǔ)(列表法)需三個(gè)數(shù)組：LA

矩陣元素值；LB

非零矩陣元素的列標(biāo)；LC

每行的第一個(gè)非零元素在LA中的存儲(chǔ)(cúnchǔ)位置；特點(diǎn)：按行或按列順序存儲(chǔ)共六十二頁(yè)例LA-346-11233LB12431434LC1457

共六十二頁(yè)元素aij訪(fǎng)問(wèn)(fǎngwèn)步驟∶1)找i行的第一個(gè)非零元素的存儲(chǔ)位置，K1=LC(i);2)找i

行的最后一個(gè)非零元素的存儲(chǔ)位置，K2=LC(i+1)

1;3)比較該行的非零元素下標(biāo)，找出aij。①令k=K1，若LB(k)=j，則說(shuō)明已找到aij；aij=LA(k)；②否則(fǒuzé)，令k=k+1，返回①；最多從d1做到d2，若找不到，則aij值即為零共六十二頁(yè)例:訪(fǎng)問(wèn)(fǎngwèn)a34(i=3,j=4)LA-346-11233LB12431434LC1457

1）找第3行第一個(gè)非零位置(wèizhi)：

LC(3)=5(d1)2）找第3行最后一個(gè)非零位置：

LC(3+1)–1=7–1=6(d2)3）對(duì)比列標(biāo)：

LB(5)=1≠j4）對(duì)比本行下一非零的列標(biāo)：

LB(5+1)=4=j5）已找到aij

，取元素值：

LA(5+1)=2共六十二頁(yè)第一節(jié)原理第二節(jié)面向方程模擬法與序貫?zāi)M法的比較第三節(jié)大型稀疏非線(xiàn)性方程組的降維解法

一、輸出變量的指定

二、回路搜索法分解方程組

三、不可分解方程組的斷裂降維解法第四節(jié)稀疏矩陣的壓縮存儲(chǔ)

一、稀疏矩陣壓縮存儲(chǔ)的信息鏈指針

二、靜態(tài)(jìngtài)存儲(chǔ)（列表法）

三、動(dòng)態(tài)存儲(chǔ)（三地址法）

三、動(dòng)態(tài)(dòngtài)存儲(chǔ)（三地址法）共六十二頁(yè)1)Bending-Hutchison法采用屬性①和②及非零元素值構(gòu)成(gòuchéng)鏈表包括五列∶①序號(hào)∶可作為存儲(chǔ)數(shù)組的下標(biāo)數(shù)值，不占用存儲(chǔ)空間；②變量號(hào)(列標(biāo))；③方程號(hào)(行標(biāo))；④非零元素的數(shù)值；⑤非零元素的狀態(tài)屬性。共六十二頁(yè)2)三地址(dìzhǐ)法（按列存儲(chǔ)）由屬性①、②和④及非零元素值構(gòu)成：每列第一個(gè)非零元素在存儲(chǔ)(cúnchǔ)鏈中的位置

──列首址BC[1，n]；2)信息條INF[1∶3(N+M)]；信息條由三個(gè)單元構(gòu)成∶①非零元素值的行號(hào)；②非零元素的數(shù)值；③該列的下一個(gè)非零元素存儲(chǔ)位置。3)第一個(gè)空白區(qū)的位置─空白區(qū)首址S[L]；123d1d2d3共六十二頁(yè)例123456789101112131415161718192021222324列首址BC：信息(xìnxī)條INF：空白(kòngbái)區(qū)首址S：13行號(hào)元素值下一非零位置本列結(jié)束開(kāi)始下列1-34350072-1224301320最后一列去空白區(qū)190結(jié)束按列存儲(chǔ)位置動(dòng)態(tài)！1016共六十二頁(yè)(1)找aij①計(jì)算(jìsuàn)第j列的第一個(gè)非零元素存儲(chǔ)位置∶d=BC(j)；②找j列中的第一個(gè)非零元素所在行∶k=INF(d)；③若k=i，則aij=INF(d+1)；

k

i，令d=INF(d+2)，轉(zhuǎn)②；共六十二頁(yè)例:找a431234567891011121314151617181920212223243203502-12201-34101643013071列首址BC：信息(xìnxī)條INF：空白(kòngbái)區(qū)首址S：19第3列第一個(gè)非零對(duì)比行號(hào)不等于4去下行對(duì)比行號(hào)找到啦!取值i=4j=3共六十二頁(yè)(2)插入(chārù)aij，i1<i<i2①找到d1，d2;(j列中與aij相鄰的上下兩個(gè)非零位置)②令L=S=d3；③S=INF(L+2);(將d4作為第一個(gè)空白區(qū))④INF(L)=i(在d3保存行號(hào)(xínɡhào))INF(L+1)=aij(保存元素值)INF(L+2)=d2(將ai,j與ai2,j相連)⑤INF(d1+2)=L(將ai1,j與ai,j相連)Sd3…d1d1+1d1+2…d2d2+1d2+2…d3d3+1d3+2d4d4+1INF…i1

ai1,j

d2

…i2

ai2,j

d3…d4…d1d2d4占用第一空白區(qū)存儲(chǔ)aijd3共