第6章 面向方程模擬法N

1、第第6章章 面向面向方程方程模擬法模擬法 第第6章章 面向方程模擬法面向方程模擬法 第一節(jié)第一節(jié) 原理原理 第二節(jié)第二節(jié) 面向方程模擬法與序貫?zāi)M法的比較面向方程模擬法與序貫?zāi)M法的比較 第三節(jié)第三節(jié) 大型稀疏非線性方程組的降維解法大型稀疏非線性方程組的降維解法 一、輸出變量的指定一、輸出變量的指定 二、回路搜索法分解方程組二、回路搜索法分解方程組 三、不可分解方程組的斷裂降維解法三、不可分解方程組的斷裂降維解法 第四節(jié)第四節(jié) 稀疏矩陣的壓縮存儲(chǔ)稀疏矩陣的壓縮存儲(chǔ) 一、稀疏矩陣壓縮存儲(chǔ)的信息鏈指針一、稀疏矩陣壓縮存儲(chǔ)的信息鏈指針 二、靜態(tài)存儲(chǔ)（列表法）二、靜態(tài)存儲(chǔ)（列表法） 三、動(dòng)態(tài)存儲(chǔ)（三地

2、址法）三、動(dòng)態(tài)存儲(chǔ)（三地址法） 第一節(jié)第一節(jié) 原理原理 Equation Oriented Method 聯(lián)立方程模擬法聯(lián)立方程模擬法 第第6章章 面向方程模擬法面向方程模擬法 SPLTMIX S1S2S3 S4 面向方程法將整個(gè)系統(tǒng)聯(lián)合建模面向方程法將整個(gè)系統(tǒng)聯(lián)合建模 Sub flow( S1, ALFA, S2, S3, S4 ) S2 = S1 + S4 以上混合器模型方程以上混合器模型方程 S3 = S2 * ALFA S4 = S2 * ( 1 ALFA ) 以上以上 分割器模型方程分割器模型方程 End Sub 整個(gè)系統(tǒng)方程組，整體求解整個(gè)系統(tǒng)方程組，整體求解 序貫法模：序貫法模：

3、 每個(gè)單元為獨(dú)立子程序每個(gè)單元為獨(dú)立子程序 對(duì)外提供結(jié)果對(duì)外提供結(jié)果 需要迭代需要迭代 循環(huán)物流的去哪里？循環(huán)物流的去哪里？ 第第6章章 面向方程模擬法面向方程模擬法 過(guò)程系統(tǒng)的模型方程過(guò)程系統(tǒng)的模型方程 模型方程：模型方程： F x w( , ) 0 模型方程模型方程決策變量決策變量 狀態(tài)變量狀態(tài)變量 各種平衡方程各種平衡方程 單元聯(lián)結(jié)方程單元聯(lián)結(jié)方程 設(shè)計(jì)規(guī)定方程設(shè)計(jì)規(guī)定方程 物性方程物性方程 現(xiàn)象方程現(xiàn)象方程 第第6章章 面向方程模擬法面向方程模擬法 模型變量模型變量 決策變量決策變量 所有單元模塊的設(shè)備參數(shù)所有單元模塊的設(shè)備參數(shù) 進(jìn)料流股變量進(jìn)料流股變量 狀態(tài)參數(shù)狀態(tài)參數(shù) 所有中間變量

4、所有中間變量 產(chǎn)品流股變量產(chǎn)品流股變量 內(nèi)部變量等內(nèi)部變量等 第第6章章 面向方程模擬法面向方程模擬法 模擬結(jié)構(gòu)模擬結(jié)構(gòu) 循環(huán)物流方程循環(huán)物流方程 設(shè)計(jì)規(guī)定方程設(shè)計(jì)規(guī)定方程 僅提供方程僅提供方程 多多! 特殊處理特殊處理 第第6章章 面向方程模擬法面向方程模擬法 物性系統(tǒng)的處理物性系統(tǒng)的處理 占用占用7080%的計(jì)算量的計(jì)算量 處理方法：處理方法： 1）不提供方程組，僅提供子程序）不提供方程組，僅提供子程序 方程數(shù)量大幅減少，但需經(jīng)常調(diào)用物性子程方程數(shù)量大幅減少，但需經(jīng)常調(diào)用物性子程 序，效果有限序，效果有限 2）提供）提供 k, h 的方程組，其它物性由子程序調(diào)的方程組，其它物性由子程序調(diào)

5、用用 k, h最常用，其它較少用到。最常用，其它較少用到。 效果很好效果很好 物性：焓、相平衡常數(shù)、密度、粘度、導(dǎo)熱系數(shù)等物性：焓、相平衡常數(shù)、密度、粘度、導(dǎo)熱系數(shù)等 第第6章章 面向方程模擬法面向方程模擬法 第一節(jié)第一節(jié) 原理原理 第二節(jié)第二節(jié) 面向方程模擬法與序貫?zāi)M法的比較面向方程模擬法與序貫?zāi)M法的比較 第三節(jié)第三節(jié) 大型稀疏非線性方程組的降維解法大型稀疏非線性方程組的降維解法 一、輸出變量的指定一、輸出變量的指定 二、回路搜索法分解方程組二、回路搜索法分解方程組 三、不可分解方程組的斷裂降維解法三、不可分解方程組的斷裂降維解法 第四節(jié)第四節(jié) 稀疏矩陣的壓縮存儲(chǔ)稀疏矩陣的壓縮存儲(chǔ) 一、

6、稀疏矩陣壓縮存儲(chǔ)的信息鏈指針一、稀疏矩陣壓縮存儲(chǔ)的信息鏈指針 二、靜態(tài)存儲(chǔ)（列表法）二、靜態(tài)存儲(chǔ)（列表法） 三、動(dòng)態(tài)存儲(chǔ)（三地址法）三、動(dòng)態(tài)存儲(chǔ)（三地址法） 第二節(jié)第二節(jié) 面向方程模擬法與序貫?zāi)M法的比較面向方程模擬法與序貫?zāi)M法的比較 第第6章章 面向方程模擬法面向方程模擬法 模擬方法結(jié)構(gòu)特征模擬方法結(jié)構(gòu)特征 序貫?zāi)K模擬法序貫?zāi)K模擬法面向方程面向方程模擬法模擬法 第第6章章 面向方程模擬法面向方程模擬法 1. 1. 序貫?zāi)K法序貫?zāi)K法 優(yōu)點(diǎn)：優(yōu)點(diǎn)： 與實(shí)際過(guò)程的直觀聯(lián)系強(qiáng)，與實(shí)際過(guò)程的直觀聯(lián)系強(qiáng)， 軟件的建軟件的建 立、維護(hù)和擴(kuò)充很方便；立、維護(hù)和擴(kuò)充很方便； 易于通用化；易于通用化；

7、 需要的計(jì)算機(jī)內(nèi)存較?。恍枰挠?jì)算機(jī)內(nèi)存較?。?易于診斷出錯(cuò)位置；易于診斷出錯(cuò)位置； 缺點(diǎn)：缺點(diǎn)： 循環(huán)循環(huán)物流及設(shè)計(jì)問(wèn)題：慢物流及設(shè)計(jì)問(wèn)題：慢 第第6章章 面向方程模擬法面向方程模擬法 2. 2. 面向方程法面向方程法 優(yōu)點(diǎn)優(yōu)點(diǎn) 便于實(shí)際用戶的提出的質(zhì)量性能要求。便于實(shí)際用戶的提出的質(zhì)量性能要求。 有設(shè)計(jì)規(guī)定的系統(tǒng)，僅增加幾個(gè)方程有設(shè)計(jì)規(guī)定的系統(tǒng)，僅增加幾個(gè)方程 用空間換取時(shí)間。用空間換取時(shí)間。 相同的過(guò)程單元出現(xiàn)多次，將占用更多的相同的過(guò)程單元出現(xiàn)多次，將占用更多的 存儲(chǔ)空間，自由度的選擇也可能各不相同存儲(chǔ)空間，自由度的選擇也可能各不相同 以空間換取求解的數(shù)值穩(wěn)定性。以空間換取求解的數(shù)值穩(wěn)

8、定性。 有較多回流高度交互作用流程相對(duì)容易收斂有較多回流高度交互作用流程相對(duì)容易收斂 第第6章章 面向方程模擬法面向方程模擬法 2. 2. 面向方程法面向方程法 缺點(diǎn)缺點(diǎn) 要求提供較好的初值要求提供較好的初值 難于自動(dòng)產(chǎn)生流程的模型方程組，難于自動(dòng)產(chǎn)生流程的模型方程組， 難以通用化難以通用化 不容易診斷出現(xiàn)錯(cuò)誤的地方。不容易診斷出現(xiàn)錯(cuò)誤的地方。 第第6章章 面向方程模擬法面向方程模擬法 序貫法與聯(lián)立方程法對(duì)比序貫法與聯(lián)立方程法對(duì)比 內(nèi)內(nèi) 容容序貫法序貫法聯(lián)立方程法聯(lián)立方程法 占用存儲(chǔ)空間占用存儲(chǔ)空間小小大大 迭代循環(huán)圈迭代循環(huán)圈多多少少 計(jì)算效率計(jì)算效率低低高高 指定設(shè)計(jì)規(guī)定指定設(shè)計(jì)規(guī)定不靈活

9、不靈活靈活靈活 初值要求初值要求低低高高 錯(cuò)誤診斷錯(cuò)誤診斷易易難難 編程、調(diào)試編程、調(diào)試較易較易較難較難 第第6章章 面向方程模擬法面向方程模擬法 聯(lián)立模塊法聯(lián)立模塊法 序貫?zāi)K法建立流程簡(jiǎn)單，處理循環(huán)流與設(shè)計(jì)規(guī)定序貫?zāi)K法建立流程簡(jiǎn)單，處理循環(huán)流與設(shè)計(jì)規(guī)定 需迭代需迭代 聯(lián)立方程法同時(shí)求解，但建模困難聯(lián)立方程法同時(shí)求解，但建模困難 聯(lián)立模塊法聯(lián)立模塊法又稱雙層法，將過(guò)程系統(tǒng)的近似模型方又稱雙層法，將過(guò)程系統(tǒng)的近似模型方 程與單元模塊交替求解程與單元模塊交替求解 聯(lián)立模塊法聯(lián)立模塊法兼有序貫?zāi)K法和面向方程法的優(yōu)點(diǎn)。兼有序貫?zāi)K法和面向方程法的優(yōu)點(diǎn)。 既能使用序貫?zāi)K法積累的大量模塊，又能將最

10、費(fèi)既能使用序貫?zāi)K法積累的大量模塊，又能將最費(fèi) 計(jì)算時(shí)間的流程收斂和設(shè)計(jì)約束收斂等迭代循環(huán)合計(jì)算時(shí)間的流程收斂和設(shè)計(jì)約束收斂等迭代循環(huán)合 并處理，通過(guò)聯(lián)立求解達(dá)到同時(shí)收斂并處理，通過(guò)聯(lián)立求解達(dá)到同時(shí)收斂 第第6章章 面向方程模擬法面向方程模擬法 斷裂變量不迭代斷裂變量不迭代 簡(jiǎn)化模型的產(chǎn)生??？簡(jiǎn)化模型的產(chǎn)生??？ 第第6章章 面向方程模擬法面向方程模擬法 聯(lián)立模塊法特點(diǎn)聯(lián)立模塊法特點(diǎn) 以簡(jiǎn)化模型聯(lián)立求解取代序貫法的回路迭代計(jì)算以簡(jiǎn)化模型聯(lián)立求解取代序貫法的回路迭代計(jì)算 和設(shè)計(jì)規(guī)定計(jì)算和設(shè)計(jì)規(guī)定計(jì)算 可利用原有的序貫法資源可利用原有的序貫法資源 方程數(shù)量較聯(lián)立方程法要少得多，求解難度大大方程數(shù)量較

11、聯(lián)立方程法要少得多，求解難度大大 降低降低 難點(diǎn)難點(diǎn)： 簡(jiǎn)化方程的產(chǎn)生及其適用范圍簡(jiǎn)化方程的產(chǎn)生及其適用范圍 第第6章章 面向方程模擬法面向方程模擬法 過(guò)程系統(tǒng)穩(wěn)態(tài)模擬三種方法的比較過(guò)程系統(tǒng)穩(wěn)態(tài)模擬三種方法的比較 方法方法優(yōu)點(diǎn)優(yōu)點(diǎn)缺點(diǎn)缺點(diǎn)代表軟件系統(tǒng)代表軟件系統(tǒng) 序序 貫貫 模模 塊塊 法法 與工程師直觀經(jīng)驗(yàn)一致，與工程師直觀經(jīng)驗(yàn)一致， 便于學(xué)習(xí)使用；便于學(xué)習(xí)使用； 易于通用化，已積累了易于通用化，已積累了 豐富的單元模塊；豐富的單元模塊； 需要計(jì)算機(jī)內(nèi)存較??；需要計(jì)算機(jī)內(nèi)存較??； 有錯(cuò)誤易于診斷檢查有錯(cuò)誤易于診斷檢查； 再循環(huán)引起的收斂迭代很費(fèi)再循環(huán)引起的收斂迭代很費(fèi) 機(jī)時(shí)；機(jī)時(shí)； 進(jìn)行設(shè)計(jì)

12、型計(jì)算時(shí)，很費(fèi)機(jī)進(jìn)行設(shè)計(jì)型計(jì)算時(shí)，很費(fèi)機(jī) 時(shí)；時(shí)； 不宜用于最優(yōu)化計(jì)算；不宜用于最優(yōu)化計(jì)算； PROCESS(美美) CONCEPT(英英) CAPES(日日) ASPEN(美美) FLOWTRAN(美美) 面面 向向 方方 程程 法法 解算快；解算快； 模擬型計(jì)算與設(shè)計(jì)型計(jì)模擬型計(jì)算與設(shè)計(jì)型計(jì) 算一樣；適合最優(yōu)化計(jì)算一樣；適合最優(yōu)化計(jì) 算，效率高；算，效率高； 便于與動(dòng)態(tài)模擬聯(lián)合實(shí)便于與動(dòng)態(tài)模擬聯(lián)合實(shí) 現(xiàn)；現(xiàn)； 要求給定較好的初值，否則要求給定較好的初值，否則 可能得不到解；計(jì)算失敗后可能得不到解；計(jì)算失敗后 診斷錯(cuò)誤所在困難；形成通診斷錯(cuò)誤所在困難；形成通 用化程序有困難有，故使用用化程序

13、有困難有，故使用 不便；難以繼承已有的單元不便；難以繼承已有的單元 操作模塊。操作模塊。 ASCEND-(美美) SPEEDUP(英英) （雙層法）（雙層法） 聯(lián)立模塊法聯(lián)立模塊法 可以利用前人開(kāi)發(fā)的單可以利用前人開(kāi)發(fā)的單 元操作模塊；元操作模塊； 可以避免序貫?zāi)K法中可以避免序貫?zāi)K法中 的循環(huán)流迭代；比較容的循環(huán)流迭代；比較容 易實(shí)現(xiàn)通用。易實(shí)現(xiàn)通用。 將嚴(yán)格模型做成簡(jiǎn)化模型時(shí)，將嚴(yán)格模型做成簡(jiǎn)化模型時(shí)， 需要花費(fèi)機(jī)時(shí)；需要花費(fèi)機(jī)時(shí)； 用簡(jiǎn)化模型來(lái)尋求優(yōu)化時(shí)，用簡(jiǎn)化模型來(lái)尋求優(yōu)化時(shí)， 其解與嚴(yán)格與嚴(yán)格模型優(yōu)化其解與嚴(yán)格與嚴(yán)格模型優(yōu)化 解是否一致，有爭(zhēng)論。解是否一致，有爭(zhēng)論。 TISFLO（

14、德）（德） FLOWPACK-(英英) 第第6章章 面向方程模擬法面向方程模擬法 第一節(jié)第一節(jié) 原理原理 第二節(jié)第二節(jié) 面向方程模擬法與序貫?zāi)M法的比較面向方程模擬法與序貫?zāi)M法的比較 第三節(jié)第三節(jié) 大型稀疏非線性方程組的降維解法大型稀疏非線性方程組的降維解法 一、輸出變量的指定一、輸出變量的指定 二、回路搜索法分解方程組二、回路搜索法分解方程組 三、不可分解方程組的斷裂降維解法三、不可分解方程組的斷裂降維解法 第四節(jié)第四節(jié) 稀疏矩陣的壓縮存儲(chǔ)稀疏矩陣的壓縮存儲(chǔ) 一、稀疏矩陣壓縮存儲(chǔ)的信息鏈指針一、稀疏矩陣壓縮存儲(chǔ)的信息鏈指針 二、靜態(tài)存儲(chǔ)（列表法）二、靜態(tài)存儲(chǔ)（列表法） 三、動(dòng)態(tài)存儲(chǔ)（三地址

15、法）三、動(dòng)態(tài)存儲(chǔ)（三地址法） 第三節(jié)第三節(jié) 大型稀疏非線性方程組的降維解法大型稀疏非線性方程組的降維解法 第第6章章 面向方程模擬法面向方程模擬法 系統(tǒng)方程多，整體求解難度很多系統(tǒng)方程多，整體求解難度很多 處理方法：處理方法： 方程組分解方程組分解 過(guò)程系統(tǒng)方程組的特點(diǎn)：過(guò)程系統(tǒng)方程組的特點(diǎn)： 方程數(shù)多，變量多方程數(shù)多，變量多 每個(gè)方程包含的變量不多每個(gè)方程包含的變量不多 每個(gè)變量存在的方程每個(gè)變量存在的方程( (出現(xiàn)次數(shù)出現(xiàn)次數(shù)) )不多不多 稀疏方程組稀疏方程組 2 () N n 非非零零系系數(shù)數(shù)數(shù)數(shù)目目 方方程程組組維維數(shù)數(shù) 稀疏比稀疏比 將方程組轉(zhuǎn)化為有向圖，再應(yīng)用系統(tǒng)分解的手段將方程

16、組轉(zhuǎn)化為有向圖，再應(yīng)用系統(tǒng)分解的手段 分解成可順序求解的子方程組分解成可順序求解的子方程組 第第6章章 面向方程模擬法面向方程模擬法 第一節(jié)第一節(jié) 原理原理 第二節(jié)第二節(jié) 面向方程模擬法與序貫?zāi)M法的比較面向方程模擬法與序貫?zāi)M法的比較 第三節(jié)第三節(jié) 大型稀疏非線性方程組的降維解法大型稀疏非線性方程組的降維解法 一、輸出變量的指定一、輸出變量的指定 二、回路搜索法分解方程組二、回路搜索法分解方程組 三、不可分解方程組的斷裂降維解法三、不可分解方程組的斷裂降維解法 第四節(jié)第四節(jié) 稀疏矩陣的壓縮存儲(chǔ)稀疏矩陣的壓縮存儲(chǔ) 一、稀疏矩陣壓縮存儲(chǔ)的信息鏈指針一、稀疏矩陣壓縮存儲(chǔ)的信息鏈指針 二、靜態(tài)存儲(chǔ)（

17、列表法）二、靜態(tài)存儲(chǔ)（列表法） 三、動(dòng)態(tài)存儲(chǔ)（三地址法）三、動(dòng)態(tài)存儲(chǔ)（三地址法） 一、輸出變量的指定一、輸出變量的指定 第第6章章 面向方程模擬法面向方程模擬法 Hall各異條件？各異條件？ 方程組有解的必要條件！方程組有解的必要條件！ 輸出變量？輸出變量？ 介紹方程組決策變量影響時(shí)學(xué)過(guò)！介紹方程組決策變量影響時(shí)學(xué)過(guò)！ 將將f2(x,y,z)=0改寫(xiě)為改寫(xiě)為y=f2(x,z)，y則稱為則稱為f2的輸出變量的輸出變量 N維方程組可指定維方程組可指定N個(gè)不同的輸出變量個(gè)不同的輸出變量 123 1 2 3 111 1 1 xxx f f f 失??！失??！ 123 1 2 3 111 1 1 xxx

18、f f f x2出現(xiàn)最少，應(yīng)先考慮出現(xiàn)最少，應(yīng)先考慮 f3包含的變量最少，也應(yīng)優(yōu)先考慮！包含的變量最少，也應(yīng)優(yōu)先考慮！ 成功！成功！ 包含變量少的方程和出現(xiàn)次數(shù)少包含變量少的方程和出現(xiàn)次數(shù)少 的變量應(yīng)先考慮的變量應(yīng)先考慮 第第6章章 面向方程模擬法面向方程模擬法 輸出變量的指定方法輸出變量的指定方法 ： 1) 1) 選事件矩陣中元素選事件矩陣中元素最少的行最少的行和其與元素和其與元素最少的最少的 列列的的交點(diǎn)交點(diǎn)處元素對(duì)應(yīng)的變量作為優(yōu)先指定的輸出變處元素對(duì)應(yīng)的變量作為優(yōu)先指定的輸出變 量，然后從事件矩陣中刪去相應(yīng)的行和列。量，然后從事件矩陣中刪去相應(yīng)的行和列。 2) 2) 重復(fù)上述過(guò)程重復(fù)上述

19、過(guò)程 若矩陣的所有行和列被刪除，則指定完畢。若矩陣的所有行和列被刪除，則指定完畢。 若有行或列無(wú)法刪除，則表示與剩余列對(duì)應(yīng)若有行或列無(wú)法刪除，則表示與剩余列對(duì)應(yīng) 的變量不存在于與剩余的行對(duì)應(yīng)的方程中。的變量不存在于與剩余的行對(duì)應(yīng)的方程中。 第第6章章 面向方程模擬法面向方程模擬法 “Steward”通路通路 a) 從矩陣的不飽和行從矩陣的不飽和行(無(wú)輸出變量的行無(wú)輸出變量的行)或不飽和列或不飽和列 (無(wú)輸出變量的列無(wú)輸出變量的列)的某一非輸出變量開(kāi)始，垂直找的某一非輸出變量開(kāi)始，垂直找 到與該元素在一列或一行的輸出變量。再轉(zhuǎn)到與該元素在一列或一行的輸出變量。再轉(zhuǎn)90 ，找，找 到另一個(gè)非輸出變

20、量，再垂直找到輸出變量，直到到另一個(gè)非輸出變量，再垂直找到輸出變量，直到 找到不飽和列或行中的某一非零元素。找到不飽和列或行中的某一非零元素。 b) 此軌跡就是此軌跡就是“Steward”通路。將此通路上的輸出通路。將此通路上的輸出 變量與非輸出變量互換，即可增加一個(gè)輸出變量。變量與非輸出變量互換，即可增加一個(gè)輸出變量。 第第6章章 面向方程模擬法面向方程模擬法 f1f2f3 指定輸出變量的作用？指定輸出變量的作用？ 將方程組轉(zhuǎn)化為有向圖！將方程組轉(zhuǎn)化為有向圖！ 可應(yīng)用過(guò)程系統(tǒng)分解的手段對(duì)方程系統(tǒng)進(jìn)行分解可應(yīng)用過(guò)程系統(tǒng)分解的手段對(duì)方程系統(tǒng)進(jìn)行分解 可及矩陣法可及矩陣法 索引矩陣法索引矩陣法 S

21、teward通路搜索法通路搜索法 Sargent-Westerberg搜索法（圖解法）搜索法（圖解法） 第第6章章 面向方程模擬法面向方程模擬法 例例 12345678910 1 2 3 4 5 6 7 8 9 10 11111 11 111111 11 1111 11 111 11 11111 111 xxxxxxxxxx f f f f f f f f f f 不飽和行不飽和行 不飽和列不飽和列 第第6章章 面向方程模擬法面向方程模擬法 12345678910 1 2 3 4 5 6 7 8 9 10 11111 11 111111 11 1111 11 111 11 11111 111

22、xxxxxxxxxx f f f f f f f f f f 從不飽和行的任一非零開(kāi)始從不飽和行的任一非零開(kāi)始 將出現(xiàn)死循環(huán)將出現(xiàn)死循環(huán) 將將Steward通路上的輸出變量與非輸出變量互換通路上的輸出變量與非輸出變量互換 可增加一個(gè)輸出變量！可增加一個(gè)輸出變量！ Steward通路通路 例例 第第6章章 面向方程模擬法面向方程模擬法 第一節(jié)第一節(jié) 原理原理 第二節(jié)第二節(jié) 面向方程模擬法與序貫?zāi)M法的比較面向方程模擬法與序貫?zāi)M法的比較 第三節(jié)第三節(jié) 大型稀疏非線性方程組的降維解法大型稀疏非線性方程組的降維解法 一、輸出變量的指定一、輸出變量的指定 二、回路搜索法分解方程組二、回路搜索法分解方程

23、組 三、不可分解方程組的斷裂降維解法三、不可分解方程組的斷裂降維解法 第四節(jié)第四節(jié) 稀疏矩陣的壓縮存儲(chǔ)稀疏矩陣的壓縮存儲(chǔ) 一、稀疏矩陣壓縮存儲(chǔ)的信息鏈指針一、稀疏矩陣壓縮存儲(chǔ)的信息鏈指針 二、靜態(tài)存儲(chǔ)（列表法）二、靜態(tài)存儲(chǔ)（列表法） 三、動(dòng)態(tài)存儲(chǔ)（三地址法）三、動(dòng)態(tài)存儲(chǔ)（三地址法） 二、回路搜索法分解方程組二、回路搜索法分解方程組 第第6章章 面向方程模擬法面向方程模擬法 回路搜索法分解方程組步驟回路搜索法分解方程組步驟: 1）寫(xiě)出方程組事件矩陣，指定輸出變量）寫(xiě)出方程組事件矩陣，指定輸出變量 2）如果每個(gè)方程都指定了一個(gè)不同的輸出變量，則方）如果每個(gè)方程都指定了一個(gè)不同的輸出變量，則方 程組

24、滿足程組滿足Hall各異條件，轉(zhuǎn)各異條件，轉(zhuǎn)6；否則轉(zhuǎn)；否則轉(zhuǎn)3。 3）從不飽和行的一個(gè)非零開(kāi)始搜索）從不飽和行的一個(gè)非零開(kāi)始搜索Steward通路。如通路。如 果能從不飽和行走到不飽和列，轉(zhuǎn)果能從不飽和行走到不飽和列，轉(zhuǎn)4；否則轉(zhuǎn)；否則轉(zhuǎn)5。 4）不能增加輸出變量數(shù)目，方程組無(wú)解，停止。）不能增加輸出變量數(shù)目，方程組無(wú)解，停止。 5）將）將Steward通路上的輸出變量與非輸出變量類(lèi)型互通路上的輸出變量與非輸出變量類(lèi)型互 換，則可增加一個(gè)輸出變量。如果此時(shí)輸出變量的數(shù)目換，則可增加一個(gè)輸出變量。如果此時(shí)輸出變量的數(shù)目 與方程數(shù)目相等，轉(zhuǎn)與方程數(shù)目相等，轉(zhuǎn)6；否則轉(zhuǎn)；否則轉(zhuǎn)3） 6）將方程以節(jié)

25、點(diǎn)形式排成一行，將每個(gè)方程與其輸出）將方程以節(jié)點(diǎn)形式排成一行，將每個(gè)方程與其輸出 變量出現(xiàn)的方程節(jié)點(diǎn)以有向弧相連，即形成了方程組的變量出現(xiàn)的方程節(jié)點(diǎn)以有向弧相連，即形成了方程組的 有向圖。有向圖。 7）可以用可及矩陣法、索引矩陣法、）可以用可及矩陣法、索引矩陣法、Steward通路搜通路搜 索法和圖解法等分解方程組。索法和圖解法等分解方程組。 第第6章章 面向方程模擬法面向方程模擬法 不飽和行不飽和行 不飽和列不飽和列 0 從不飽和行開(kāi)始找從不飽和行開(kāi)始找Steward通路通路 不飽和列不飽和列 將將Steward通路上的輸出變量與非輸出變量對(duì)換通路上的輸出變量與非輸出變量對(duì)換 指定輸出變量：

26、指定輸出變量： 12345 1 2 3 4 5 11 1111 111 11 111 xxxxx f f f f f 第第6章章 面向方程模擬法面向方程模擬法 12345 1 2 3 4 5 11 1111 111 11 111 xxxxx f f f f f 最終的輸出變量指定：最終的輸出變量指定： 第第6章章 面向方程模擬法面向方程模擬法 12345 1 2 3 4 5 11 1111 111 11 111 xxxxx f f f f f f1 繪制有向圖：繪制有向圖： f2f3f4f5 f1 x4 f1 f2 x3 f2 f3 x2 f3 f4 x1 f4 f5 x5 f5 第第6章章

27、面向方程模擬法面向方程模擬法 f1f4f5f2f3 搜索回路：搜索回路： f2f3 f1f2 f5 f2 ， f2f5構(gòu)成回路，構(gòu)成回路， 將將f2f5作為組合節(jié)點(diǎn)，改寫(xiě)有向圖作為組合節(jié)點(diǎn)，改寫(xiě)有向圖 f1f2f5f3f4f2f5 f1f4f5 內(nèi)部弧內(nèi)部弧 內(nèi)部弧內(nèi)部弧 f1f2f3f4f5 第第6章章 面向方程模擬法面向方程模擬法 搜索回路：搜索回路： f1f2f5，無(wú)路可走！，無(wú)路可走！ 刪除刪除f2f5，計(jì)入次序表，改寫(xiě)有向圖，計(jì)入次序表，改寫(xiě)有向圖 f1f3f4 次序表次序表 f2f5 f2f5f2f5 f1f3，無(wú)路可走！，無(wú)路可走！ 刪除刪除f3，計(jì)入次序表，改寫(xiě)有向圖，計(jì)入次序

28、表，改寫(xiě)有向圖 f3 f3 f1f4 f1 ，構(gòu)成回路，形成，構(gòu)成回路，形成最后一個(gè)組最后一個(gè)組 合節(jié)點(diǎn)，刪除合節(jié)點(diǎn)，刪除f1f4，計(jì)入次序表，計(jì)入次序表 f1f4 計(jì)算順序計(jì)算順序 第第6章章 面向方程模擬法面向方程模擬法 第一節(jié)第一節(jié) 原理原理 第二節(jié)第二節(jié) 面向方程模擬法與序貫?zāi)M法的比較面向方程模擬法與序貫?zāi)M法的比較 第三節(jié)第三節(jié) 大型稀疏非線性方程組的降維解法大型稀疏非線性方程組的降維解法 一、輸出變量的指定一、輸出變量的指定 二、回路搜索法分解方程組二、回路搜索法分解方程組 三、不可分解方程組的斷裂降維解法三、不可分解方程組的斷裂降維解法 第四節(jié)第四節(jié) 稀疏矩陣的壓縮存儲(chǔ)稀疏矩陣

29、的壓縮存儲(chǔ) 一、稀疏矩陣壓縮存儲(chǔ)的信息鏈指針一、稀疏矩陣壓縮存儲(chǔ)的信息鏈指針 二、靜態(tài)存儲(chǔ)（列表法）二、靜態(tài)存儲(chǔ)（列表法） 三、動(dòng)態(tài)存儲(chǔ)（三地址法）三、動(dòng)態(tài)存儲(chǔ)（三地址法） 三、不可分解方程組的斷裂降維解法三、不可分解方程組的斷裂降維解法 第第6章章 面向方程模擬法面向方程模擬法 大規(guī)模方程組的處理：大規(guī)模方程組的處理： 分解成小規(guī)模方程組，順序求解分解成小規(guī)模方程組，順序求解 問(wèn)題：?jiǎn)栴}： 子方程組規(guī)模仍很大子方程組規(guī)模仍很大 整個(gè)方程組本身不可分解整個(gè)方程組本身不可分解？ 必須聯(lián)立求解?。勘仨毬?lián)立求解??？ 斷裂降維求解斷裂降維求解 第第6章章 面向方程模擬法面向方程模擬法 方程組的斷裂求解

30、步驟如下方程組的斷裂求解步驟如下 1) 選輸出變量，分解方程組；選輸出變量，分解方程組； 2) 在分解后的子方程組中選擇包含變量數(shù)最少的在分解后的子方程組中選擇包含變量數(shù)最少的 方程方程( =k)中的中的k- -1變量作為斷裂變量；變量作為斷裂變量；選擇選擇k- -1個(gè)包個(gè)包 含變量數(shù)最多的方程作為驗(yàn)算方程含變量數(shù)最多的方程作為驗(yàn)算方程； 3) 降維后用回路搜索法進(jìn)一步分解；降維后用回路搜索法進(jìn)一步分解； 4) 給斷裂變量賦初值，求解降維后的方程組；給斷裂變量賦初值，求解降維后的方程組； 5) 驗(yàn)算斷裂變量直到收斂。驗(yàn)算斷裂變量直到收斂。 第第6章章 面向方程模擬法面向方程模擬法 例例 123

31、456 1 2 3 4 5 6 11111 1111 11 11 11 1111 xxxxxx f f f f f f 整個(gè)方程組整個(gè)方程組 不可分解不可分解 斷裂降維求解斷裂降維求解 迭代求解迭代求解 迭代求解迭代求解 要求最少的斷裂變量！要求最少的斷裂變量！ 選變量數(shù)最少的方程斷裂選變量數(shù)最少的方程斷裂 斷裂斷裂x1，即給定，即給定x1初值初值 x3=f4(x1) 斷裂變量，賦初值斷裂變量，賦初值 斷裂斷裂1個(gè)變量，可排除個(gè)變量，可排除 一個(gè)方程，一個(gè)方程，2個(gè)變量個(gè)變量 第第6章章 面向方程模擬法面向方程模擬法 1111 11 11 11 1111 11111 6 5 4 3 2 1 6

32、54321 f f f f f f xxxxxx 例例 斷裂變量斷裂變量狀態(tài)變量狀態(tài)變量 驗(yàn)算方程驗(yàn)算方程 驗(yàn)算方程應(yīng)選擇含驗(yàn)算方程應(yīng)選擇含 變量數(shù)最多的方程變量數(shù)最多的方程 方程數(shù)比變量數(shù)多方程數(shù)比變量數(shù)多1個(gè)個(gè) 指定輸出變量指定輸出變量 分解方程組分解方程組 第第6章章 面向方程模擬法面向方程模擬法 1111 11 11 11 1111 11111 6 5 4 3 2 1 654321 f f f f f f xxxxxx f1f3f5f6 求解順序：求解順序： f5f6f1f3 第第6章章 面向方程模擬法面向方程模擬法 計(jì)算步驟：計(jì)算步驟： 1)假設(shè)假設(shè)x1初值初值 2)由由f4計(jì)算出計(jì)

33、算出x3 3)聯(lián)合求解聯(lián)合求解f1 f3 ，得出，得出x2, x4 4)將將x1, x2 , x3, x4代入代入f5 f6聯(lián)合求解得聯(lián)合求解得x5, x6 5)驗(yàn)算驗(yàn)算f2是否滿足，若滿足則結(jié)束，否則轉(zhuǎn)是否滿足，若滿足則結(jié)束，否則轉(zhuǎn)6) 6)重新假設(shè)重新假設(shè)x1初值轉(zhuǎn)初值轉(zhuǎn)2) 第第6章章 面向方程模擬法面向方程模擬法 四、四、n m 型稀疏非方程組的處理型稀疏非方程組的處理 利用最小二乘法取得一組妥協(xié)解。利用最小二乘法取得一組妥協(xié)解。 求解其中的求解其中的m m個(gè)方程個(gè)方程 第第6章章 面向方程模擬法面向方程模擬法 第一節(jié)第一節(jié) 原理原理 第二節(jié)第二節(jié) 面向方程模擬法與序貫?zāi)M法的比較面向

34、方程模擬法與序貫?zāi)M法的比較 第三節(jié)第三節(jié) 大型稀疏非線性方程組的降維解法大型稀疏非線性方程組的降維解法 一、輸出變量的指定一、輸出變量的指定 二、回路搜索法分解方程組二、回路搜索法分解方程組 三、不可分解方程組的斷裂降維解法三、不可分解方程組的斷裂降維解法 第四節(jié)第四節(jié) 稀疏矩陣的壓縮存儲(chǔ)稀疏矩陣的壓縮存儲(chǔ) 一、稀疏矩陣壓縮存儲(chǔ)的信息鏈指針一、稀疏矩陣壓縮存儲(chǔ)的信息鏈指針 二、靜態(tài)存儲(chǔ)（列表法）二、靜態(tài)存儲(chǔ)（列表法） 三、動(dòng)態(tài)存儲(chǔ)（三地址法）三、動(dòng)態(tài)存儲(chǔ)（三地址法） 第四節(jié)第四節(jié) 稀疏矩陣的壓縮存儲(chǔ)稀疏矩陣的壓縮存儲(chǔ) 第第6章章 面向方程模擬法面向方程模擬法 n = 1000，N = 200

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

36、較面向方程模擬法與序貫?zāi)M法的比較 第三節(jié)第三節(jié) 大型稀疏非線性方程組的降維解法大型稀疏非線性方程組的降維解法 一、輸出變量的指定一、輸出變量的指定 二、回路搜索法分解方程組二、回路搜索法分解方程組 三、不可分解方程組的斷裂降維解法三、不可分解方程組的斷裂降維解法 第四節(jié)第四節(jié) 稀疏矩陣的壓縮存儲(chǔ)稀疏矩陣的壓縮存儲(chǔ) 一、稀疏矩陣壓縮存儲(chǔ)的信息鏈指針一、稀疏矩陣壓縮存儲(chǔ)的信息鏈指針 二、靜態(tài)存儲(chǔ)（列表法）二、靜態(tài)存儲(chǔ)（列表法） 三、動(dòng)態(tài)存儲(chǔ)（三地址法）三、動(dòng)態(tài)存儲(chǔ)（三地址法） 一、稀疏矩陣壓縮存儲(chǔ)的信息鏈指針一、稀疏矩陣壓縮存儲(chǔ)的信息鏈指針 第第6章章 面向方程模擬法面向方程模擬法 非零元素屬性

37、非零元素屬性 l l 行標(biāo)；行標(biāo)； l l 列標(biāo)；列標(biāo)； l l 指向本行中下一個(gè)非零元素的指針；指向本行中下一個(gè)非零元素的指針； l l 指向本列中下一個(gè)非零元素的指針；指向本列中下一個(gè)非零元素的指針； l l 指向本行中前一個(gè)非零元素的指針；指向本行中前一個(gè)非零元素的指針； l l 指向本列中前一個(gè)非零元素的指針；指向本列中前一個(gè)非零元素的指針； 第第6章章 面向方程模擬法面向方程模擬法 第一節(jié)第一節(jié) 原理原理 第二節(jié)第二節(jié) 面向方程模擬法與序貫?zāi)M法的比較面向方程模擬法與序貫?zāi)M法的比較 第三節(jié)第三節(jié) 大型稀疏非線性方程組的降維解法大型稀疏非線性方程組的降維解法 一、輸出變量的指定一、輸

38、出變量的指定 二、回路搜索法分解方程組二、回路搜索法分解方程組 三、不可分解方程組的斷裂降維解法三、不可分解方程組的斷裂降維解法 第四節(jié)第四節(jié) 稀疏矩陣的壓縮存儲(chǔ)稀疏矩陣的壓縮存儲(chǔ) 一、稀疏矩陣壓縮存儲(chǔ)的信息鏈指針一、稀疏矩陣壓縮存儲(chǔ)的信息鏈指針 二、靜態(tài)存儲(chǔ)（列表法）二、靜態(tài)存儲(chǔ)（列表法） 三、動(dòng)態(tài)存儲(chǔ)（三地址法）三、動(dòng)態(tài)存儲(chǔ)（三地址法） 二、靜態(tài)存儲(chǔ)（列表法） 第第6章章 面向方程模擬法面向方程模擬法 一、靜態(tài)存儲(chǔ)一、靜態(tài)存儲(chǔ)( (列表法列表法) ) 需三個(gè)數(shù)組：需三個(gè)數(shù)組： LALA矩陣元素值；矩陣元素值； LBLB非零矩陣元素的列標(biāo)；非零矩陣元素的列標(biāo)； LCLC每行的第一個(gè)非零元素在

39、每行的第一個(gè)非零元素在LALA中的存儲(chǔ)位置；中的存儲(chǔ)位置； 特點(diǎn)：按行或按列特點(diǎn)：按行或按列順序順序存儲(chǔ)存儲(chǔ) 第第6章章 面向方程模擬法面向方程模擬法 例例 3406 0010 1002 0033 LA-346-11233 LB12431434 LC1457 第第6章章 面向方程模擬法面向方程模擬法 元素元素aij訪問(wèn)步驟訪問(wèn)步驟 1) 找找 i 行的第一個(gè)非零元素的存儲(chǔ)位置，行的第一個(gè)非零元素的存儲(chǔ)位置， K1=LC(i); 2) 找找 i 行的最后一個(gè)非零元素的存儲(chǔ)位置，行的最后一個(gè)非零元素的存儲(chǔ)位置，K2 = LC(i+1) 1; 3) 比較該行的非零元素下標(biāo)，找出比較該行的非零元素下標(biāo)

40、，找出aij。 令令k=K1，若，若LB(k)= j，則說(shuō)明已找到，則說(shuō)明已找到aij；aij =LA(k)； 否則，令否則，令k = k +1，返回；，返回； 最多從最多從d1做到做到d2，若，若 找不到，找不到， 則則aij值即為零值即為零 第第6章章 面向方程模擬法面向方程模擬法 例例: 訪問(wèn)訪問(wèn)a34 (i=3, j=4) 3300 2001 0100 6043LA-346-11233 LB12431434 LC1457 1）找第）找第3行第一個(gè)非零位置：行第一個(gè)非零位置： LC(3) = 5 (d1) 2）找第）找第3行最后一個(gè)非零位置：行最后一個(gè)非零位置： LC(3+1) 1 =

41、7 1 = 6 (d2) 3）對(duì)比列標(biāo)：）對(duì)比列標(biāo)： LB(5) = 1j 4）對(duì)比本行下一非零的列標(biāo)：）對(duì)比本行下一非零的列標(biāo)： LB(5+1) = 4 = j 5）已找到）已找到 aij ，取元素值：，取元素值： LA(5+1) = 2 第第6章章 面向方程模擬法面向方程模擬法 第一節(jié)第一節(jié) 原理原理 第二節(jié)第二節(jié) 面向方程模擬法與序貫?zāi)M法的比較面向方程模擬法與序貫?zāi)M法的比較 第三節(jié)第三節(jié) 大型稀疏非線性方程組的降維解法大型稀疏非線性方程組的降維解法 一、輸出變量的指定一、輸出變量的指定 二、回路搜索法分解方程組二、回路搜索法分解方程組 三、不可分解方程組的斷裂降維解法三、不可分解方程

42、組的斷裂降維解法 第四節(jié)第四節(jié) 稀疏矩陣的壓縮存儲(chǔ)稀疏矩陣的壓縮存儲(chǔ) 一、稀疏矩陣壓縮存儲(chǔ)的信息鏈指針一、稀疏矩陣壓縮存儲(chǔ)的信息鏈指針 二、靜態(tài)存儲(chǔ)（列表法）二、靜態(tài)存儲(chǔ)（列表法） 三、動(dòng)態(tài)存儲(chǔ)（三地址法）三、動(dòng)態(tài)存儲(chǔ)（三地址法）三、動(dòng)態(tài)存儲(chǔ)（三地址法） 第第6章章 面向方程模擬法面向方程模擬法 1) Bending-Hutchison法法 采用屬性和及非零元素值構(gòu)成鏈表采用屬性和及非零元素值構(gòu)成鏈表 包括五列包括五列 序號(hào)序號(hào)可作為存儲(chǔ)數(shù)組的下標(biāo)數(shù)值，不占用可作為存儲(chǔ)數(shù)組的下標(biāo)數(shù)值，不占用 存儲(chǔ)空間；存儲(chǔ)空間； 變量號(hào)變量號(hào)( (列標(biāo)列標(biāo)) )； 方程號(hào)方程號(hào)( (行標(biāo)行標(biāo)) ) ； 非零元

43、素的數(shù)值；非零元素的數(shù)值； 非零元素的狀態(tài)屬性。非零元素的狀態(tài)屬性。 第第6章章 面向方程模擬法面向方程模擬法 2) 三地址法（按列存儲(chǔ)）三地址法（按列存儲(chǔ)） 由屬性、和及非零元素值構(gòu)成：由屬性、和及非零元素值構(gòu)成： 1) 每列第一個(gè)非零元素在存儲(chǔ)鏈中的位置每列第一個(gè)非零元素在存儲(chǔ)鏈中的位置 列首址列首址BC1，n； 2) 信息條信息條INF1 3(N+M)； 信息條由三個(gè)單元構(gòu)成信息條由三個(gè)單元構(gòu)成 非零元素值的行號(hào)；非零元素值的行號(hào)； 非零元素的數(shù)值；非零元素的數(shù)值； 該列的下一個(gè)非零元素存儲(chǔ)位置。該列的下一個(gè)非零元素存儲(chǔ)位置。 3) 第一個(gè)空白區(qū)的位置第一個(gè)空白區(qū)的位置空白區(qū)首址空白區(qū)首

44、址SL； 123 d1 d2 d3 第第6章章 面向方程模擬法面向方程模擬法 例例 123456789 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 0300 2005 0100 0003 列首址列首址BC： 信息條信息條INF： 空白區(qū)首址空白區(qū)首址S： 13 行號(hào)行號(hào) 元素值元素值下一非下一非 零位置零位置 本列結(jié)束本列結(jié)束 開(kāi)始下列開(kāi)始下列 1 -34350 07 2 -1 22430 1 320 最后一列最后一列 去空白區(qū)去空白區(qū) 19 0 結(jié)束結(jié)束 按列存儲(chǔ)按列存儲(chǔ) 位置動(dòng)態(tài)！位置動(dòng)態(tài)！ 1016 第第6章章 面向方程模擬法面向方程模擬法 (1) 找找aij 計(jì)算第計(jì)算第j列的第一個(gè)非零元素存儲(chǔ)位置列的第一個(gè)非零元素存儲(chǔ)位置 d=BC(j)； 找找j列中的第一個(gè)非零元素所在行列中的第一個(gè)非零元素所在行 k=INF(d)； 若若 k=i，則，則