化工過程模擬與分析(第四章非線性方程組的求解).ppt

1、第四章 非線性方程組的求解,4.1 概述,一、非線性方程組的一般形式,解法： 迭代逼近的方法：牛頓法等 最優(yōu)化方法,或,二、解的存在性壓縮映射原理,不動(dòng)點(diǎn),壓縮映射,壓縮映射原理,若G在閉集D0上是壓縮映射，且G D0 D0 ，則G (x)在D0上存在唯一的不動(dòng)點(diǎn),收斂性 對(duì)于某個(gè)非線性方程組，若其解為,，某一算法產(chǎn)生,迭代序列x (k)，且有下式成立，則稱該算法收斂。,收斂速度 對(duì)于一個(gè)收斂于解的序列x (k)，若存在一個(gè)正實(shí)數(shù)和一個(gè)與迭代步數(shù)k無關(guān)的正常數(shù)q，由某k0開始下式成立，則稱該迭代序列具有階收斂速度。,三、算法選擇標(biāo)準(zhǔn),1、迭代算法適應(yīng)性 收斂域越大越好，即壓縮映射D0應(yīng)盡量大

2、2、迭代算法收斂性 除需要在解附近，對(duì)初始點(diǎn)的其他要求越少越好 3、迭代算法收斂速度 越快越好 4、計(jì)算量,四、非線性方程組的線性展開,對(duì)于一個(gè)n維多元函數(shù)組 f (x)，在某一點(diǎn)附近，有：,其中J被稱為雅可比矩陣，其計(jì)算如下：,非線性方程組線性展開示例,下列方程組在2, 2處線性展開,五、誤差分析,誤差分類 模型誤差、觀測(cè)誤差、方法誤差、舍入誤差、初值誤差,數(shù)值穩(wěn)定性 某算法在運(yùn)算過程中，誤差不增長(zhǎng)或增長(zhǎng)很少，則稱該算法數(shù)值穩(wěn)定性較好。,收斂檢驗(yàn),4.2 f (x) = 0的求解,一、牛頓-拉弗遜法（Newton-Raphson method）,原理 第k步迭代時(shí)，將非線性方程組展開為線性方

3、程組 L (x)=0，并將線性方程組的解作為下一個(gè)迭代點(diǎn)。,迭代公式,在解附近 二階收斂,二、牛頓-拉弗遜法的修正,1、在迭代公式中引入搜索步長(zhǎng),步長(zhǎng)用一維搜 索確定,目的：擴(kuò)大收斂域,2、引入阻尼因子（Damping factor）,目的：克服J的奇異和病態(tài),阻尼因子應(yīng)使J非奇異； 且迭代點(diǎn)更靠近解,3、雅可比矩陣計(jì)算的簡(jiǎn)化,迭代k0步之后，固定J為,通常取k0=2，此時(shí)算法具有三階收斂速度。,對(duì)于規(guī)模較大的化工問題，上述算法不適合。,計(jì)算量太大 J表達(dá)式過于復(fù)雜,三、擬牛頓法（Quasi Newton method）,研究目的：避免雅可比矩陣的計(jì)算和求逆,一般迭代公式：,實(shí)質(zhì)：割線法在多維

4、空間的拓展,最常用形式：Newton-Broyden法,概述,Newton-Broyden法原理,設(shè)第k步解已求出，則可計(jì)算出：,則第k+1步迭代時(shí)的雅克比矩陣可以通過修正獲得：,其中,n個(gè)方程，nn個(gè)自變量,n個(gè)方程，2n個(gè)自變量,則可得到：,由此，只要確定了初始矩陣J，則后面迭代中可通過秩一修正來計(jì)算矩陣J，減少了計(jì)算量。,Sherman-Morrison公式,迭代中可 對(duì)矩陣逆修正,Newton-Broyden法迭代公式：,或,效果較好,超線性收斂,以增加內(nèi)存占用 提高計(jì)算效率.,也可通過一維搜索最優(yōu)步長(zhǎng)因子加快收斂。,inv_J1 = 0.3373 0.1557 0.1103 0.51

5、24,iJ1 = 0.2710 0.1232 0.0371 0.4040,理論結(jié)果與實(shí)際計(jì)算結(jié)果：,四、阻尼最小二乘法（Levenberg-Marquardt method）,而此最小化問題，可通過牛頓法來求解：,其中：,m n m=n為方程組求解,阻尼因子,以上述迭代公式為基礎(chǔ)，即可得到LM算法，除用于求解非線性方程組，也可用于非線性參數(shù)估計(jì)。,該方法計(jì)算量較大，但效果較好，實(shí)際中阻尼因子需要通過迭代進(jìn)行調(diào)節(jié)。,阻尼因子設(shè)置和調(diào)整原則 初始可設(shè) =0.001 當(dāng)函數(shù)值未下降時(shí)，增加阻尼因子值； 函數(shù)值下降時(shí)，減小阻尼因子值。,很 大趨向于最速下降法 很小則趨向于牛頓法,mu_init = 1

6、e-3; mu_inc = 10; mu_dec = 0.1; mu_max = 1e5; while (mu = mu_max) dx = -(jj+ii*mu) je; 計(jì)算新的函數(shù)值new_f if (new_f f), break, end mu = mu * mu_inc; end,尤其適合于參數(shù) 估值問題,4.3 x = (x)的求解,大部分穩(wěn)態(tài)流程模擬需要求解此類顯式方程組； 顯式方程解法不適合于求解隱式方程。,概述,解法分類 直接迭代法 部分迭代法,松弛因子,對(duì)于多維問題，松弛因子應(yīng)為一對(duì)角矩陣。,一、韋格施坦法（ Wegstein method）,迭代公式,一個(gè)方程收斂 一個(gè)

7、變量,只適合變量交互作用較弱的情況,變量交互作用較弱意味著方程組的雅可比矩陣在解的附近是個(gè)嚴(yán)格對(duì)角占優(yōu)矩陣。,二、優(yōu)勢(shì)特征值法（Dominant eigenvalue method）,作用：加速迭代收斂。,通常在其他迭代法迭代若干輪之后使用。,原理,F主特征值,且k 時(shí)有,對(duì)于線性方程組,對(duì)于非線性方程組,同樣要求每輪 F 1,實(shí)踐證明,相鄰2輪之間解之差.,1輪迭代起到了 p輪迭代作用,優(yōu)勢(shì)特征值法（DEM）迭代公式,DEM的使用方式： 以其他迭代法為主，每間隔45輪應(yīng)用一次DEM公式,4.4 基于信賴域的方法（Dogleg method）,4.5 同倫延拓法（Homotopy contin

8、uation method）,研究背景：求解非線性方程組時(shí)，初始點(diǎn)難以選擇。,原理：引入?yún)?shù)t，構(gòu)造一簇同倫映射,代替向量函數(shù) f (x)，且H （x, t）滿足：,牛頓同倫,x (t)構(gòu)成了n維空間中的一條曲線； 非線性方程 f (x)有解轉(zhuǎn)換為曲線x (t)存在。,一、數(shù)值延拓法,對(duì)于,，將t離散化：,順序求解非線性方程組：,k =1的 初始點(diǎn),獲得第N個(gè)方程的解后，則可以其為初始點(diǎn)進(jìn)行迭代求解出非線性方程組的解。,對(duì)于任意給定的初始點(diǎn)，該方法總可以二階速度收斂至方程組的解。,同倫路徑,同倫路徑x (tk)可穿越非線性方程（組）所有的解。,同倫映射通用形式：,牛頓同倫（或全局同倫）,不動(dòng)點(diǎn)

9、同倫,仿射同倫（Affine homotopy）,同倫路徑存在的要求：在每一個(gè)tk處滿足隱函數(shù)存在定理,對(duì)t=0時(shí)同倫方程解的要求：唯一且,對(duì)同倫路徑的要求：不穿越原方程組的定義域,二、參數(shù)微分法 (Path parameterization by the homotopy parameter),為減少獲得同倫路徑x (t)的計(jì)算量，可將同倫方程等價(jià)變換為下列常微分方程組初值問題：,t=1時(shí)的解做為原方程解的初始點(diǎn),對(duì)于牛頓同倫，常微分方程組初始值問題為：,對(duì)于仿射同倫，則等價(jià)問題為：,也可每次歐拉法預(yù)測(cè)后 用牛頓迭代法使得 (x, t)更靠近同倫路徑,若同倫曲線有轉(zhuǎn)折點(diǎn)，則該法失效,三、弧長(zhǎng)

10、參數(shù)微分法(Path parameterization by arc length),曲線x (t)的弧長(zhǎng),dt,dx,ds,對(duì)于n維向量函數(shù)xi=xi(t)，下式成立：,此即廣義Pythagorean定理,根據(jù)廣義勾股定理，可利用弧長(zhǎng)參數(shù)微分法求取同倫曲線,n個(gè)常微分方程，n+1個(gè)自變量,與廣義勾股定理聯(lián)立即可求解,該問題如何求解最方便？,數(shù)值方法每求解出dx和dt后，可應(yīng)用牛頓拉佛遜法修正一次以使(x (t), t)更接近同倫曲線。,初始條件為：,該方程組方程數(shù)比自變量數(shù)少1,聯(lián)立求解則可獲得修正值,弧長(zhǎng)參數(shù)微分法步驟： （1）給定初始值，循環(huán)（2）（4）直至收斂； （2）求解弧長(zhǎng)常微分方

11、程獲得dx, dt, 更正x和t; （3）使用牛頓拉佛遜法獲得x, t，再次更正x和t;,萬錫人 計(jì)算非線性方程組所有解的同倫連續(xù)法 南京化工學(xué)院學(xué)報(bào)，vol 16, No. 3，8894，1994.,同倫算法在化工中的應(yīng)用： 多重定態(tài)問題、反應(yīng)蒸餾、全局優(yōu)化,T.L. Wayburn & J.D. Seader. Homotopy continuation method for computer-aided process design. Comput. Chem. Engng, 11 (1), 725, 1987.,J.D. Seader etal. Mapped continuation methods for computing all solutions to general systems of nonlinear equations. Comput. C