1、非線性方程組的求解摘要：非線性方程組求解是數(shù)學(xué)教學(xué)中，數(shù)值分析課程的一個重要組成部分， 作為一門學(xué)科，其研究對象是非線性方程組。求解非線性方程組主要有兩種方法： 一種是傳統(tǒng)的數(shù)學(xué)方法，如牛頓法、梯度法、共腕方向法、混沌法、BFGSI、單純形法等。傳統(tǒng)數(shù)值方法的優(yōu)點(diǎn)是計(jì)算精度高，缺點(diǎn)是對初始迭代值具有敏感性， 同時(shí)傳統(tǒng)數(shù)值方法還會遇到計(jì)算函數(shù)的導(dǎo)數(shù)和矩陣求逆的問題，對于某些導(dǎo)數(shù)不存在或是導(dǎo)數(shù)難求的方程，傳統(tǒng)數(shù)值方法具有一定局限性。另一種方法是進(jìn)化算 法，如遺傳算法、粒子群算法、人工魚群算法、差分進(jìn)化算法等。進(jìn)化算法的優(yōu)點(diǎn)是對函數(shù)本身沒有要求，不需求導(dǎo)，計(jì)算速度快，但是精度不高。關(guān)鍵字：非線性方程

2、組、牛頓法、BFG法、記憶,$度法、Memetic算法1：三種牛頓法：Newton法、簡化Newton法、修改的Newton法”求解非線性方程組的Newton法是一個最基本而且十分重要的方法，目前使用的很多有效的迭代法都是以Newton法為基礎(chǔ)，或由它派生而來。n個變量n個方程的非線性方程組，其一般形式如下：'fl(X,X2，Xn) =0,f2(Xi,X2，Xn) =0(1).fn(Xi,X2，4 產(chǎn)0式(1)中，屋兌區(qū),.4) ( i=1, ?, n) 是定義在n維Euclid空間Rnt開域D上 的實(shí)值函數(shù)。若用向量記號，令:xjX2X =, F(X)=1 . IHn 1-fl(Xi

3、,X2,.Xn) =0 - -fi(X) f2(Xi,X2,.Xn) =0 = f2(X)". ._fn(Xi,X2,.Xn) =01 _fn(X )則方程組(1)也可表示為:F(X)=0其中：X三Rn,F : Rn-R°, F(X) Rn, Rn為賦值空間。一般地，若在包含的某鄰域D內(nèi)，按某種近似意義，用線性函數(shù)：ik(x)=ax bk近似地代替向量值函數(shù)F(X),此處A是n階矩陣，則可將線性方程組：ik(x)= ax +bk(4)的解作為非線性方程組(2)的近似解。1.1 Newton 法1NewtonS的迭代公式為：X k 書=X k + AX kk =0,1,2,.

4、(5)F'(Xk)gXk)=-F(Xk)其中 X k = X k 1- X k.1.2 簡化 Newton 法 1盡管Newton法具有較高的收斂速度，但在每一步迭代中，要計(jì)算 n個函數(shù) 值f,以及n2個導(dǎo)數(shù)值f '形成Jacobi矩陣f'(Xk),而且要求f'(Xk)的逆陣或者 解一個n階線性方程組，計(jì)算量很大。為了減少計(jì)算量，在上述 Newton法中對 一切k=0,1,2,., 取f'(Xk)為f'(X.),于是迭代公式修改為：(6)Xk1 =Xkf'(Xk)尸 f(Xk), k =0,1,2.式(5)即為簡化的Newton法。該方法

5、能使計(jì)算量大為減少，但卻大大降低了收斂速度。簡化的Newton法的算法與Newton法的算法區(qū)別就在于只由給定的初始近似值計(jì)算一次f'(X),以后在每一次迭代過程中不再計(jì)算 f'(XJ，保持初始計(jì)算值。1.3 修正的Newton法吸取Newton法收斂快與簡化的Newton法工作量省的優(yōu)點(diǎn)，文獻(xiàn)【2】把m步簡化的Newton步合并成一次Newton步。則可以得到下列迭代程序:Xk,0 =Xk'Xk,j =Xk,jf'(Xk)f(Xk,j)>Xk+ =Xk,m式中：j=1,2,?, m, k=0, 1,2,?,該式稱為修正的Newton法。通過分析Newto

6、n法、簡化的Newton法和修正Newton法的原理，并通過對算例的分析比較，我們可知：Newton法(5)式具有較高的收斂速度，但計(jì)算量大，在 每一步迭代中，要計(jì)算 n個函數(shù)值f ,以及n2個導(dǎo)數(shù)值f形成Jacobi矩陣 f'(Xk)，而且要求f'(Xk)的逆陣或者解一個n階線性方程組；簡化的Newton法(6)式，它用迭代初值為來計(jì)算f'(Xk),并在每個迭代步中保持不變，它能使每步迭代過程的計(jì)算量大為減少，但大大降低了收斂速度。修正Newton(7)與Newtorfe(5)相比，在每步迭代過程中增加計(jì)算n個函數(shù)值，并不增加求逆次數(shù)，然而收斂速度提高了2:BFGS

7、法【4-6】非線性方程組一般形式為：方程組(1)將其轉(zhuǎn)化為一個全局優(yōu)化問題。構(gòu)造n能量函數(shù)：(X)=£ fi2(X),X =(xi,x2,.xn)求非線性方程組解的問題就轉(zhuǎn)化為 i =1求解能量函數(shù)極小值的問題。即給定一個充分小的實(shí)常數(shù)6 ,搜索x* =(x；,x2,.k)使得小(X*)<名則X*即是非線性方程組(1)對應(yīng)的近似解。2.1 BFGS查分算法文獻(xiàn)【4】將傳統(tǒng)的BFG算法和查分算法有機(jī)融合，用來求解非線性方程組,效果顯著，可以較為廣泛地應(yīng)用于非線性方程組的求解。BFGSf法是由Broyden、Fletcher、Goldfarb和Shanno等人在1970年提出的。它

8、是一個擬牛頓方法，具有二次終止性、整體收斂性和超線性收斂性，且算法所產(chǎn)生的搜索方向是共腕的。BFGS?法是一個有效的局部算法，用來求解極小值的。例如方程組阡1(Xi,X2，Xn) = A(8)f 2 ( xi, x2，xn ) = A2fn(Xi,X2，Xn) =A可將它夠著適應(yīng)度函數(shù)nF(X) = fi(x)-A|(9)i 1那么求非線性方程組(8)的根問題就轉(zhuǎn)化成了求適應(yīng)度函數(shù) F (X)最小值的優(yōu) 化問題。這就是它最基本的思想。DEET法(差分進(jìn)化算法)(文獻(xiàn)【5】)具有良好的全局搜索能力，并具有對初 始值、參數(shù)選擇不敏感、魯棒性強(qiáng)、原理簡單、容易操作等優(yōu)點(diǎn)，是一種較好的 全局優(yōu)化方法。

9、但在優(yōu)化后期DEJ法的收斂速度明顯變慢，而且搜索結(jié)果僅獲得 滿意解域而不是精確解。為了克服這些缺點(diǎn)，該文在DEJ法的進(jìn)化后期階段引入 BFGS?法，利用BFGS方法的整體收斂性和超收斂性來加快收斂速度。BFGS?法屬于局部算法，其優(yōu)化結(jié)果的優(yōu)劣在很大程度上取決于初始值的選取，為此可以利用具有全局搜索能力的DEJ法提供給BFGSf法良好的初始值。2.2 改進(jìn)的BFGS變尺度法對于高維的大型問題(維數(shù)大于100),變尺度法由于收斂快、效果好，被認(rèn) 為是最好的優(yōu)化方法之一。其中BFGS法的數(shù)值穩(wěn)定性較好，是最成功的一種變 尺度法。BFGS1中有2個非常關(guān)鍵的環(huán)節(jié)：求函數(shù)的偏導(dǎo)數(shù)和一維探索。 這2個環(huán)

10、 節(jié)的算法精度對最后結(jié)果的精度影響很大。2.2.1 改進(jìn)的遺傳算法 遺傳算法的優(yōu)越性主要表現(xiàn)在：算法具有固有的并行性，通過對種群的遺傳 處理可處理大量的模式，并且容易并行實(shí)現(xiàn)。(a)選擇復(fù)制操作采用保優(yōu)操作與比例復(fù)制相結(jié)合，即最優(yōu)秀的個體被無條件保留下來，其余的以正比于個體適配值的概率來選擇相應(yīng)的個體。(b)交叉操作采用保優(yōu)操作與算數(shù)交叉結(jié)合，即最優(yōu)秀的個體被無條件保留下來，其余的以 交叉概率進(jìn)行算數(shù)交叉。算數(shù)交叉的方式為：X1 = ： X1 (1 -： )X2,X2 = ：X2 (1 - ： )X1(10)式中aw (0,1) ; X1,X2為父代個體；X1,X2為后代個體。(c)變異操作采

11、用保優(yōu)操作與擾動變異結(jié)合，即最優(yōu)秀的個體被無條件保留下來，其余的以 變異概率進(jìn)行擾動變異。擾動變異的方式為X'= X 十慎o式中U為滿足正態(tài)分布 的隨機(jī)擾動；列為尺度參數(shù)；X為父代個體；X'為后代個體。2.3 混合優(yōu)化改進(jìn)的BFGS方法是一種非常有效而且收斂速度很快的局部搜索算法，而改進(jìn)的遺傳算法實(shí)現(xiàn)并行搜索，有非常強(qiáng)的全局搜索的能力。文獻(xiàn)【7】將2種方法 混合起來，實(shí)現(xiàn)了并行與串行，全局與局部的融合，極大地提高了優(yōu)化性能、優(yōu)化效率和魯棒性-尤其對于高維復(fù)雜函數(shù)效果非常好。混合法的步驟為(1)給定算法參數(shù)，初始化種群。(2)評價(jià)當(dāng)前種群中各個體。(3)判斷算法 收斂準(zhǔn)則是否滿足

12、。若滿足則輸出搜索結(jié)果，否則轉(zhuǎn)(4)。(4)執(zhí)行改進(jìn)的遺傳算 法的選擇復(fù)制操作。(5)執(zhí)行改進(jìn)的遺傳算法的交叉操作。(6)執(zhí)行改進(jìn)的遺傳算 法的變異操作。(7)以當(dāng)前種群中各個個體作為改進(jìn)的BFGSf法的初始解，分別 用改進(jìn)的BFGSf法進(jìn)行搜索得到新的個體，將這些新的個體組成新的種群，轉(zhuǎn)(2)。3: 記憶梯度法8-10考慮非線性方程組F(x)=0,xwRn ,(11)其中F : Rn t Rn是非線性映射。定義F(x) =(FMx),F2(x)，F(xiàn)(xn)T ,其雅可比矩陣J(X)。記憶梯度法(文獻(xiàn)【8-9】) 是求解無約束優(yōu)化問題非常有效的方法，該方法在每步迭代時(shí)不需計(jì)算和存儲矩 陣，結(jié)構(gòu)

13、簡單，因而適于求解大型優(yōu)化問題。算法的基本思想是：首先將非線性方程組問題(12)轉(zhuǎn)化為一個無約束極小 化問題min f (x),x Rn,(12)i1.2其中 f (x) =3 F(x) I o這里|. |采用二范數(shù)，然后利用記憶梯度法求解問題 (13)。因?yàn)閒( x) > 0。所 以如果x*是無約束優(yōu)化問題(12)的最優(yōu)解，那么x*必是非線性方程組(11)的 近似最優(yōu)解。設(shè)f(X)的梯度為g(x),則g(x)= f(x)=J(x)F(x).求解無約束優(yōu)化問題 的記憶梯度法應(yīng)用于求解非線性方程組，給出了一類新的求解非線性方程組的記 憶梯度算法，并分析了算法的全局收斂性。該算法無需求雅克比

14、矩陣的逆矩陣,所以具有更廣泛的應(yīng)用性。止匕外，算法在迭代過程中也無需每一步都計(jì)算 F(X)的 雅克比矩陣，大大減少了算法的計(jì)算量，節(jié)省了運(yùn)算時(shí)間。與牛頓法相比，記憶 梯度法更適于求解大規(guī)模非線性方程組。4：基于Memetic算法的非線性方程組求解算法Memetic算法是建立在模擬文化進(jìn)化基礎(chǔ)上的優(yōu)化算法，它實(shí)質(zhì)上是一種基 于種群的全局搜索和基于個體的局部啟發(fā)式搜索的結(jié)合體。Memetic算法流程和GA有很大的相似。其關(guān)鍵區(qū)別是Memeti峭法在交叉和變異后多了一個局部搜索 優(yōu)化的過程。針對函數(shù)優(yōu)化問題，傳統(tǒng)的遺傳算法雖然能夠全局尋優(yōu)，但是它很 容易早熟。對于傳統(tǒng)的局部搜索算法，它一個初始解開始

15、，在其鄰域中搜尋比其 更好的解，它可以快速求出較優(yōu)解，其不足主要是只有當(dāng)?shù)踔翟谡鎸?shí)解附近 時(shí)，其較快的局部搜索性能才能得以發(fā)揮。Memetic算法充分吸收了遺傳算法和 傳統(tǒng)局部搜索算法的優(yōu)點(diǎn)，采用遺傳算法的操作流程，但是在每次交叉和變異后 進(jìn)行局部搜索，通過優(yōu)化種群分布及早剔除不良種群，進(jìn)而減少迭代次數(shù)，在 Memetic算法的設(shè)計(jì)過程中各個參數(shù)的選擇策略對算法求解結(jié)果具有重要的影 響。仍然以方程組(1)為例，現(xiàn)在定義：f(x)= £ fJ(X)(13),i 1則求解方程組(1)等價(jià)于求解這樣一個極值優(yōu)化問題：若在方程組(1)的解空 間內(nèi)找到一組X =XX2,Xn,使得式(13)

16、達(dá)到最小值則此時(shí)的 X =X1,X2，Xn就是方程組(1)的解。(1)適應(yīng)度評價(jià)與選擇總結(jié)文獻(xiàn)【11】的算法大致思路：先初始化種群，看其是否滿足停止準(zhǔn)則， 是的話顯示結(jié)果，算法結(jié)束。否則的話，進(jìn)行以下步驟:(2)染色體多點(diǎn)交叉。(3)擬牛頓局部搜索(4)染色體隨機(jī)變異。(5)擬牛頓局部搜索。返回看是否滿足停止準(zhǔn)則，滿足顯示結(jié)果，不滿足繼續(xù)循環(huán)。Memetic算法充分發(fā)揮了 Memetic®法大范圍搜索全局解的特點(diǎn)以及擬牛頓 算子局部細(xì)致搜索的特點(diǎn)，對非單調(diào)多峰函數(shù)組成的非線性方程組，求到解的概 率顯著高于擬牛頓法和GA實(shí)驗(yàn)表明基于Memetic算法求解非線性方程組具有較 高的收斂可靠

17、性和較高的精度。綜上，非線性方程組求解是實(shí)際工程領(lǐng)域的一個重要問題，在數(shù)值天氣預(yù)報(bào)、石油地質(zhì)勘探、計(jì)算生物化學(xué)、控制領(lǐng)域和軌道設(shè)計(jì)等方面均有較強(qiáng)的應(yīng)用背景。 從實(shí)際應(yīng)用角度出發(fā)，有必要探索高效可靠的算法去求解，可以解決我們生活中 的很多問題。參考文獻(xiàn)1謝世坤,段芳，李強(qiáng)征，羅志揚(yáng)，鄭慧.非線性方程組求解的三種Newtonfe比較 J.井岡山學(xué)院學(xué)報(bào)(自然科學(xué)),2006,27(8):8-11.2余芝云，陳爭，馬昌鳳.求解對稱非線性方程組基于信賴域的修正牛頓法J.福建師范大學(xué)學(xué)報(bào)(自然科學(xué)版),2010,26(1):22-27.3Li D H , Cheng W Y. Recent progre

18、ss in the global convergence of quasi-Newton methods for nonlinear equations J. Hokkaido Math J, 2007, 36 ( 2) : 729-7434劉利斌，歐陽艾嘉，許衛(wèi)明，李肯立.求解非線性方程組的BFG嵯分進(jìn)化算法 J.2011,47(33):55-58.5周麗，姜長生.非線性方程組求解的一種新方法J.小型微型計(jì)算機(jī)系統(tǒng),2008,9:1709-1713.6張飛飛，馬群，黃家慶，佟曉君.求解非線性方程組的二分法J.科技創(chuàng)新導(dǎo)報(bào)，2009,08 (c):146-149.7李濤，劉華偉，陳耀元.非線性方程組求解的新方法J.武漢理工大學(xué)學(xué)報(bào)(交 通科學(xué)與工程版),2009,33(3):569-572.8李敏，蘇酉1 ,時(shí)貞.求解非線性方程組的記憶梯度算法J.工程數(shù)學(xué)學(xué)報(bào)，2009,26 (3): 563-566.9Shi Z J . A new super-memory gradient method for unconstrained optimization J. Advances