- 相關(guān)推薦
非線性方程組的求解
非線性方程組的求解
摘要：非線性方程組求解是數(shù)學教學中，數(shù)值分析課程的一個重要組成部分，作為一門學科，其研究對象是非線性方程組。求解非線性方程組主要有兩種方法：一種是傳統(tǒng)的數(shù)學方法，如牛頓法、梯度法、共軛方向法、混沌法、BFGS法、單純形法等。傳統(tǒng)數(shù)值方法的優(yōu)點是計算精度高，缺點是對初始迭代值具有敏感性，同時傳統(tǒng)數(shù)值方法還會遇到計算函數(shù)的導數(shù)和矩陣求逆的問題，對于某些導數(shù)不存在或是導數(shù)難求的方程，傳統(tǒng)數(shù)值方法具有一定局限性。另一種方法是進化算法，如遺傳算法、粒子群算法、人工魚群算法、差分進化算法等。進化算法的優(yōu)點是對函數(shù)本身沒有要求，不需求導，計算速度快，但是精度不高。 關(guān)鍵字：非線性方程組、牛頓法、BFGS法、記憶梯度法、Memetic算法
1： 三種牛頓法：Newton 法、簡化Newton 法、修改的Newton 法【1-3】 求解非線性方程組的Newton 法是一個最基本而且十分重要的方法, 目前使用的很多有效的迭代法都是以Newton 法為基礎(chǔ), 或由它派生而來。 n 個變量n 個方程的非線性方程組, 其一般形式如下:
?f1(x1,x2,...xn)?0?f(x,x,...x)?0?212n??...
??fn(x1,x2,...xn)?0 （1）
式(1)中,fi(x1,x2,...xn)( i=1, ?, n) 是定義在n 維Euclid空間Rn中開域 D上 的實值函數(shù)。若用向量記號，令：
?f1(x1,x2,...xn)?0??f1(X)??x1?????x??f(X)f(x,x,..x)?022212n???? X???,F(X)???...??...?...????????xf(X)f(x,x,...x)?0??n???n?n12??n
則方程組（1）也可表示為：
F(X)?0 （2）
其中：X?Rn,F∶Rn→R0, F(X) ∈Rn, Rn為賦值空間。一般地， 若在包含的某鄰域
D 內(nèi), 按某種近似意義,用線性函數(shù):
lk(X)?AkX?bk （3）
近似地代替向量值函數(shù)F(X),此處Ak 是n 階矩陣，則可將線性方程組:
lk(X)?AkX?bk （4）
的解作為非線性方程組( 2) 的近似解。
1.1 Newton法[1]
Newton法的迭代公式為：
?Xk?1?Xk??Xkk?0,1,2,... (5）??F'(Xk)(?Xk)?-F(Xk)
其中?Xk?Xk?1-Xk.
1.2 簡化Newton 法[1]
盡管Newton 法具有較高的收斂速度，但在每一步迭代中，要計算n 個函數(shù)值f，以及n2個導數(shù)值f′形成Jacobi矩陣f'(Xk)，而且要求f'(Xk)的逆陣或者解一個n 階線性方程組，計算量很大。為了減少計算量，在上述Newton 法中對一切k=0,1,2,...,取f'(Xk)為f'(X.)，于是迭代公式修改為：
Xk?1?Xk??f'(Xk)?f(Xk),k?0,1,2... (6) ?1
式( 5) 即為簡化的Newton 法。該方法能使計算量大為減少，但卻大大降低了收斂速度。簡化的Newton 法的算法與Newton 法的算法區(qū)別就在于只由給定的初始近似值計算一次f'(X)，以后在每一次迭代過程中不再計算f'(Xk)，保持初始計算值。
1.3 修正的Newton 法
吸取Newton 法收斂快與簡化的Newton 法工作量省的優(yōu)點，文獻【2】把m 步簡化的Newton 步合并成一次Newton 步。則可以得到下列迭代程序: [2]
Xk,0?Xk???1Xk,j?Xk,j?f'(Xk)f(Xk,j?1)? (7)
?Xk?1?Xk,m?
式中: j=1, 2, ?, m, k=0, 1, 2, ?, 該式稱為修正的Newton 法。
通過分析Newton 法、簡化的Newton 法和修正Newton 法的原理, 并通過對算例的分析比較，我們可知: Newton 法(5)式具有較高的收斂速度，但計算量大，在每一步迭代中，要計算n個函數(shù)值f，以及n2個導數(shù)值f'形成Jacobi 矩陣
而且要求f'(Xk)的逆陣或者解一個n 階線性方程組；簡化的Newton 法f'(Xk) ，
( 6) 式，它用迭代初值X0來計算f'(Xk)，并在每個迭代步中保持不變，它能使每步迭代過程的計算量大為減少，但大大降低了收斂速度。修正Newton法(7)與Newton法(5)相比，在每步迭代過程中增加計算n個函數(shù)值，并不增加求逆次數(shù)，然而收斂速度提高了。
2： BFGS法【4-6】
非線性方程組一般形式為:方程組（1）將其轉(zhuǎn)化為一個全局優(yōu)化問題。構(gòu)造能量函數(shù)：?（X）求非線性方程組解的問題就轉(zhuǎn)化為??fi2(X),X?（x1,x2,...xn）
i?1n
求解能量函數(shù)極小值的問題。即給定一個充分小的實常數(shù)?，搜索
***使得?（X*）??則X*即是非線性方程組（1）對應的近似解。 X*?（x1,x2,...xn）
2.1 BFGS查分算法【4】
文獻【4】將傳統(tǒng)的BFGS算法和查分算法有機融合，用來求解非線性方程組，效果顯著，可以較為廣泛地應用于非線性方程組的求解。BFGS方法是由Broyden、
Fletcher、Goldfarb和Shanno 等人在1970年提出的。它是一個擬牛頓方法，具有二次終止性、整體收斂性和超線性收斂性，且算法所產(chǎn)生的搜索方向是共軛的。BFGS方法是一個有效的局部算法，用來求解極小值的。
例如方程組
?f1(x1,x2,...xn)?A1?f(x,x,...x)?A?212n2??...
??fn(x1,x2,...xn)?An （8）
可將它夠著適應度函數(shù)
F(X)??|fi(x)?Ai|
i?1n (9)
那么求非線性方程組（8）的根問題就轉(zhuǎn)化成了求適應度函數(shù)F（X） 最小值的優(yōu)化問題。這就是它最基本的思想。
DE算法(差分進化算法)（文獻【5】）具有良好的全局搜索能力，并具有對初始值、參數(shù)選擇不敏感、魯棒性強、原理簡單、容易操作等優(yōu)點，是一種較好的全局優(yōu)化方法。但在優(yōu)化后期DE算法的收斂速度明顯變慢，而且搜索結(jié)果僅獲得滿意解域而不是精確解。為了克服這些缺點，該文在DE算法的進化后期階段引入BFGS方法，利用BFGS 方法的整體收斂性和超收斂性來加快收斂速度。BFGS方法屬于局部算法，其優(yōu)化結(jié)果的優(yōu)劣在很大程度上取決于初始值的選取，為此可以利用具有全局搜索能力的DE算法提供給BFGS方法良好的初始值。
2.2 改進的BFGS 變尺度法【4】
對于高維的大型問題（維數(shù)大于100），變尺度法由于收斂快、效果好，被認為是最好的優(yōu)化方法之一。其中BFGS 法的數(shù)值穩(wěn)定性較好，是最成功的一種變尺度法。BFGS法中有2個非常關(guān)鍵的環(huán)節(jié)：求函數(shù)的偏導數(shù)和一維探索。這2個環(huán)
節(jié)的算法精度對最后結(jié)果的精度影響很大。
2.2.1 改進的遺傳算法【7】
遺傳算法的優(yōu)越性主要表現(xiàn)在：算法具有固有的并行性，通過對種群的遺傳處理可處理大量的模式，并且容易并行實現(xiàn)。
(a) 選擇復制操作
采用保優(yōu)操作與比例復制相結(jié)合, 即最優(yōu)秀的個體被無條件保留下來,其余的以正比于個體適配值的概率來選擇相應的個體。
(b) 交叉操作
采用保優(yōu)操作與算數(shù)交叉結(jié)合,即最優(yōu)秀的個體被無條件保留下來，其余的以交叉概率進行算數(shù)交叉。算數(shù)交叉的方式為:
(10) X1??X1?(1??)X2,X2??X2?(1??)X1
式中??（0,1）；X1,X2為父代個體；X1,X2為后代個體。
（c）變異操作
采用保優(yōu)操作與擾動變異結(jié)合,即最優(yōu)秀的個體被無條件保留下來，其余的以變異概率進行擾動變異。擾動變異的方式為X'?X???。式中?為滿足正態(tài)分布的隨機擾動；?為尺度參數(shù); X為父代個體; X'為后代個體。
2.3 混合優(yōu)化【7】
改進的BFGS 方法是一種非常有效而且收斂速度很快的局部搜索算法，而改進的遺傳算法實現(xiàn)并行搜索，有非常強的全局搜索的能力。文獻【7】將2種方法混合起來，實現(xiàn)了并行與串行，全局與局部的融合，極大地提高了優(yōu)化性能、優(yōu)化效率和魯棒性.。尤其對于高維復雜函數(shù)效果非常好。
混合法的步驟為:
(1)給定算法參數(shù)，初始化種群。(2)評價當前種群中各個體。（3)判斷算法收斂準則是否滿足。若滿足則輸出搜索結(jié)果，否則轉(zhuǎn)(4)。(4)執(zhí)行改進的遺傳算法的選擇復制操作。（5)執(zhí)行改進的遺傳算法的交叉操作。（6)執(zhí)行改進的遺傳算法的變異操作。(7)以當前種群中各個個體作為改進的BFGS方法的初始解，分別用改進的BFGS方法進行搜索得到新的個體，將這些新的個體組成新的種群，轉(zhuǎn)
（2）。
3： 記憶梯度法[8-10]
考慮非線性方程組
（11） F(x)?0,x?Rn ，
其中F:Rn?Rn是非線性映射。
定義F(x)?(F1(x),F2(x),...F(xn))T，其雅可比矩陣J(X)。記憶梯度法(文獻【8-9】)是求解無約束優(yōu)化問題非常有效的方法，該方法在每步迭代時不需計算和存儲矩陣，結(jié)構(gòu)簡單，因而適于求解大型優(yōu)化問題。
算法的基本思想是: 首先將非線性方程組問題(12)轉(zhuǎn)化為一個無約束極小化問題
minf(x),x?Rn, (12) 其中f(x)?1F(x)22。 這里采用二范數(shù)，然后利用記憶梯度法求解問題(13)。因為f( x) ≥ 0。所以如果x* 是無約束優(yōu)化問題(12)的最優(yōu)解，那么x* 必是非線性方程組(11) 的近似最優(yōu)解。設f(X)的梯度為g(x)，則g(x)=▽f(x)=J(x)F(x).求解無約束優(yōu)化問題的記憶梯度法應用于求解非線性方程組，給出了一類新的求解非線性方程組的記憶梯度算法，并分析了算法的全局收斂性。該算法無需求雅克比矩陣的逆矩陣，
所以具有更廣泛的應用性。此外，算法在迭代過程中也無需每一步都計算F(X) 的雅克比矩陣，大大減少了算法的計算量，節(jié)省了運算時間。與牛頓法相比，記憶梯度法更適于求解大規(guī)模非線性方程組。
4： 基于Memetic算法的非線性方程組求解算法【11-12】
Memetic 算法是建立在模擬文化進化基礎(chǔ)上的優(yōu)化算法，它實質(zhì)上是一種基于種群的全局搜索和基于個體的局部啟發(fā)式搜索的結(jié)合體。Memetic 算法流程和GA 有很大的相似。其關(guān)鍵區(qū)別是Memetic算法在交叉和變異后多了一個局部搜索優(yōu)化的過程。針對函數(shù)優(yōu)化問題,傳統(tǒng)的遺傳算法雖然能夠全局尋優(yōu)，但是它很容易早熟。對于傳統(tǒng)的局部搜索算法，它一個初始解開始，在其鄰域中搜尋比其更好的解，它可以快速求出較優(yōu)解，其不足主要是只有當?shù)踔翟谡鎸嵔飧浇鼤r，其較快的局部搜索性能才能得以發(fā)揮。Memetic 算法充分吸收了遺傳算法和傳統(tǒng)局部搜索算法的優(yōu)點，采用遺傳算法的操作流程，但是在每次交叉和變異后進行局部搜索，通過優(yōu)化種群分布及早剔除不良種群，進而減少迭代次數(shù)，在Memetic算法的設計過程中各個參數(shù)的選擇策略對算法求解結(jié)果具有重要的影響。
仍然以方程組（1）為例，現(xiàn)在定義：
f(x)??f
i?1n2i(X) (13)
則求解方程組( 1) 等價于求解這樣一個極值優(yōu)化問題: 若在方程組( 1) 的解空間內(nèi)找到一組X?[X1,X2,...Xn]，使得式(13)達到最小值則此時的X?[X1,X2,...Xn] 就是方程組( 1) 的解。
總結(jié)文獻【11】的算法大致思路：先初始化種群，看其是否滿足停止準則，是的話顯示結(jié)果，算法結(jié)束。否則的話，進行以下步驟：(1)適應度評價與選擇。
（2）染色體多點交叉。（3）擬牛頓局部搜索。（4）染色體隨機變異。（5）擬牛頓局部搜索。返回看是否滿足停止準則，滿足顯示結(jié)果，不滿足繼續(xù)循環(huán)。
Memetic算法充分發(fā)揮了Memetic算法大范圍搜索全局解的特點以及擬牛頓算子局部細致搜索的特點，對非單調(diào)多峰函數(shù)組成的非線性方程組，求到解的概率顯著高于擬牛頓法和GA，實驗表明基于Memetic算法求解非線性方程組具有較高的收斂可靠性和較高的精度。
綜上，非線性方程組求解是實際工程領(lǐng)域的一個重要問題，在數(shù)值天氣預報、石油地質(zhì)勘探、計算生物化學、控制領(lǐng)域和軌道設計等方面均有較強的應用背景。從實際應用角度出發(fā)，有必要探索高效可靠的算法去求解，可以解決我們生活中的很多問題。
參考文獻
[1]謝世坤,段芳,李強征,羅志揚,鄭慧.非線性方程組求解的三種Newton法比較
[J].井岡山學院學報( 自然科學),2006,27(8):8-11.
[2]余芝云,陳爭,馬昌鳳.求解對稱非線性方程組基于信賴域的修正牛頓法[J].福建師范大學學報( 自然科學版),2010,26(1):22-27.
[3]Li D H，Cheng W Y． Recent progress in the global convergence of quasi-Newton methods for nonlinear equations［J］． Hokkaido Math J，2007， 36 ( 2) : 729-743．
[4]劉利斌,歐陽艾嘉,許衛(wèi)明,李肯立.求解非線性方程組的BFGS差分進化算法
[J].2011,47(33):55-58.
[5]周麗,姜長生.非線性方程組求解的一種新方法[J].小型微型計算機系統(tǒng),2008,9:1709-1713.
[6]張飛飛,馬群,黃家慶,佟曉君.求解非線性方程組的二分法[J].科技創(chuàng)新導報，2009,08（c):146-149.
[7]李濤,劉華偉,陳耀元.非線性方程組求解的新方法[J].武漢理工大學學報(交通科學與工程版),2009,33(3):569-572.
[8]李敏,蘇醒,時貞.求解非線性方程組的記憶梯度算法[J]. 工程數(shù)學學報，2009,26（3）：563-566.
[9]Shi Z J． A new super-memory gradient method for unconstrained optimization［J］． Advances in Mathematics，2006，3( 35) : 265-273．
[10]陳長憶,葉永春.基于粒子群算法的非線性方程組求解[J].計算機應用與軟件,2006,23(5):137-139.
[11]屈愛平，李敏.MEMETIC算法在非線性方程組求解中的應用[J].湖南文理學院學 報(自然科學版),2009,21(4):13-15.
[12]Sudholt D.The impact of parametrization in memetic evolutionary algorithms[J] .Theoretical Computer Science, 2009, 26(410) : 2 511-2528.
。
【非線性方程組的求解】相關(guān)文章：
沿等壓路徑求解疏松材料Hugoniot關(guān)系的微分方程組及其求解04-26
求解約束規(guī)劃的一個非線性Lagrange函數(shù)05-01
基于神經(jīng)網(wǎng)絡的病態(tài)線性方程組求解04-30
奇異非線性邊界流耦合熱方程組的熄滅速率04-29
解非線性方程組的神經(jīng)網(wǎng)絡方法05-02