求解非線性方程組的三種算法

葉海

【摘要】對(duì)于非線性問(wèn)題，大多數(shù)轉(zhuǎn)化為非線性方程（組）來(lái)求解，具體的解決方法有牛頓法、割線法、延拓法、搜索法、梯度法、信賴(lài)域法、共軛方向法、變尺度法等.本文主要介紹求解非線性方程組的牛頓型算法、信賴(lài)域算法、遺傳算法三種方法.

【關(guān)鍵詞】非線性方程組；牛頓型算法；信賴(lài)域算法；遺傳算法

一、引言

非線性科學(xué)在工業(yè)、農(nóng)業(yè)、科學(xué)研究領(lǐng)域占有重要地位，絕大多數(shù)問(wèn)題最終都能轉(zhuǎn)化為非線性方程（組）的求解問(wèn)題，傳統(tǒng)的解決方法有：牛頓法、割線法、延拓法、搜索法、梯度法、信賴(lài)域法、共軛方向法、變尺度法等.本文著重介紹信賴(lài)域算法、牛頓型算法、遺傳算法三種方法.

非線性方程組為

fj（x1，x2，…，xn）=0（j=1，2，…，m）.（1）

其中X=（x1，x2，…，xn）∈DRn，D={（x1，x2，…，xn）|ai≤xi≤bi，i=1，2，…，n}.

解非線性方程組一般分為兩類(lèi)方法：一類(lèi)屬于線性化方法，即把非線性方程組轉(zhuǎn)化為一種近似的非線性方程組，構(gòu)造出迭代格式，然后逐次接近準(zhǔn)確解，達(dá)到滿足精度要求就終止計(jì)算；一類(lèi)屬于求函數(shù)極值方法，即由非線性函數(shù)構(gòu)造出一個(gè)目標(biāo)函數(shù)，把方程組的求解問(wèn)題轉(zhuǎn)化為求目標(biāo)函數(shù)的極值點(diǎn)問(wèn)題.構(gòu)造目標(biāo)函數(shù)：

F（x1，x2，…，xn）=∑mi=1|fi（x1，x2，…，xn）|.

這樣，在區(qū)域內(nèi)求解非線性方程組問(wèn)題（1）就轉(zhuǎn)化為了函數(shù)優(yōu)化問(wèn)題：

minF（x1，x2，…，xn）s.t（x1，x2，…，xn）∈D.（2）

顯然，滿足F（x*1，x*2，…，x*n）=0的非線性方程組的解X*（x*1，x*2，…，x*n）就是函數(shù)優(yōu)化問(wèn)題（2）的最優(yōu)解.

二、牛頓型算法

求解非線性方程組的線性化方法為：

xk+1=xk-[A（xk）]-1F（xk）（k≥1）.（3）

若取A（xk）=

SymbolQC@ F（xk），則得到求解非線性方程組的牛頓型迭代算法.

1牛頓法

牛頓法算法程序構(gòu)造過(guò)程實(shí)際上是對(duì)非線性方程組（1）左端的非線性函數(shù)逐步線性化的過(guò)程.假定F：D∈Rn→Rn在開(kāi)凸集內(nèi)二次G-可導(dǎo)，且F″（x）在D內(nèi)連續(xù).設(shè)x*∈D是（1）式的解，x0∈D是x*的初始近似值.牛頓法雖然有收斂速度快和自校正等優(yōu)點(diǎn)，但應(yīng)用到實(shí)際計(jì)算中仍存在不少問(wèn)題：迭代初始值x0要求與解x*很接近；每次迭代計(jì)算Jacobi矩陣F′（xk）和求解一個(gè)線性方程F′（xk）Δx=-F（xk），工作量較大；當(dāng)F′（xk）奇異或是病態(tài)時(shí)，計(jì)算將無(wú)法進(jìn)行下去.為了解決這些問(wèn)題，牛頓法有了如下幾種變形.

2修正牛頓法

修正牛頓法主要是針對(duì)牛頓法計(jì)算量較大進(jìn)行簡(jiǎn)化和改進(jìn)，將牛頓法收斂快和簡(jiǎn)化牛頓法工作量省的優(yōu)點(diǎn)結(jié)合起來(lái)，得到如下迭代程序：

x0k=xkxik=xi-1kxk+1=xmk-[F′（xk）]-1F（xi-1k）（i=1，…m；k=1，2，3，…）.（4）

從xk計(jì)算到xk+1中間做m次簡(jiǎn)化，只需計(jì)算一次Jacobi矩陣F′（xk）和求一次逆矩陣[F′（xk）]-1，這種修正牛頓法具有m+1階收斂速度.

3參數(shù)牛頓法

參數(shù)牛頓法是為了保證每一步迭代中的F′（xk）非奇異或非病態(tài)，而引入所謂的阻尼因子λk使F′（xk）+λkI（這里I為n階單位矩陣）非病態(tài)，此時(shí)得到迭代程序?yàn)椋?/p>

xk+1=xk-[F′（xk）+λkI]-1F（xk）（k=0，1，2，…）.（5）

當(dāng)λk選得足夠大，可以使矩陣F′（xk）+λkI對(duì)角占優(yōu)，從而消除F′（xk）的奇異性，并具有局部收斂性.

4下降牛頓法

為了克服牛頓法的局部收斂，初始點(diǎn)x0選取要很靠近解x*，引入迭代參數(shù)，采用下降法思想具有大范圍收斂的牛頓下降法，其迭代程序?yàn)椋?/p>

xk+1=xk-ωk[F′（xk）]-1F（xk）（k=0，1，…）.（6）

其中0<ωk≤1是迭代參數(shù)，可以證明迭代式具有大范圍收斂性，但實(shí)際應(yīng)用中選擇ωk仍比較困難.

牛頓法及其改進(jìn)形式是最基礎(chǔ)、應(yīng)用廣泛的求解非線性方程組方法，但由于牛頓法需要每步計(jì)算函數(shù)的導(dǎo)數(shù)，若導(dǎo)數(shù)不能直接表示出來(lái)，則很難求解，且在實(shí)際應(yīng)用中往往受到很多條件的限制，它的收斂性和性能特征在很大程度上依賴(lài)于初始點(diǎn)的選擇；另外，牛頓型算法在處理某些形式比較復(fù)雜的非線性方程組時(shí)效果不好.因此，牛頓法的各種變型都是針對(duì)牛頓法的某一缺陷而考慮的，實(shí)際應(yīng)用時(shí)只能根據(jù)要解決主要問(wèn)題采取相應(yīng)的策略.

三、信賴(lài)域方法

信賴(lài)域方法首先定義一個(gè)在當(dāng)前點(diǎn)與目標(biāo)函數(shù)近似的二次模型，利用目標(biāo)函數(shù)在一定的區(qū)域內(nèi)與二次模型的充分近似，取二次模型的最優(yōu)值作為信賴(lài)域方法的下一個(gè)迭代點(diǎn).其出發(fā)點(diǎn)是利用目標(biāo)函數(shù)的二次模型的近似程度來(lái)調(diào)節(jié)信賴(lài)域的大?。喝粜碌牡c(diǎn)不能使目標(biāo)函數(shù)值有充分的下降，說(shuō)明二次模型與目標(biāo)函數(shù)的近似程度不夠好，需要縮小信賴(lài)域半徑；否則就擴(kuò)大信賴(lài)域半徑.

對(duì)非線性方程組F（x）=0的求解可轉(zhuǎn)化為如下無(wú)約束優(yōu)化問(wèn)題：

minf（x）x∈RN=12‖F(xiàn)（x）‖2.（7）

相應(yīng)的二次信賴(lài)域優(yōu)化模型：

mk（d）=12‖F(xiàn)k+Jkd‖2=fk+dTJTkFk+12dTgTkJkd.

其中，Jk=

SymbolQC@ F（xk）為F（x）在xk點(diǎn)Jacobi矩陣.

對(duì)于（7），在xk點(diǎn)的下降方向dk有下述信賴(lài)域子問(wèn)題產(chǎn)生.

minmk（d）s.t.‖d‖≤Δk（其中Δk>0為信賴(lài)域半徑）.（8）

四、遺傳算法

求解非線性方程組對(duì)于傳統(tǒng)算法的選擇、構(gòu)造與所要解決問(wèn)題的特性有很大關(guān)系.遺傳算法不采用確定性規(guī)則，而采用概率的變遷規(guī)則來(lái)指導(dǎo)它的搜索方向，是一種靈活的自適應(yīng)算法，無(wú)需過(guò)多考慮問(wèn)題的具體形式.由于非線性方程組改造成的函數(shù)多數(shù)是多峰值函數(shù)，遺傳算法在其求解應(yīng)用中具有較大優(yōu)勢(shì)，尤其在一些非線性方程組沒(méi)有精確解的時(shí)候，遺傳算法顯得更為有效，近幾年利用遺傳算法求解非線性方程組的數(shù)值問(wèn)題也有相關(guān)的研究成果.

劉燦文等“基于求解非線性方程組的并行遺傳算法的設(shè)計(jì)”提出了將非線性方程組的數(shù)值求解問(wèn)題（1）轉(zhuǎn)化為線性約束最優(yōu)化問(wèn)題：

min{gf（x）}，x∈D.

其中g(shù)f（x）=1n∑ni=1|fi（x）|為非線性方程組（1）的誤差度量函數(shù).將遺傳算法改進(jìn)為自適應(yīng)并行遺傳算法求解該最優(yōu)化問(wèn)題，從另一角度為求解非線性方程組提供了一條比較有效的途徑.

曾毅“改進(jìn)的遺傳算法在非線性方程組求解中的應(yīng)用”提出利用改進(jìn)的遺傳算法求非線性方程組的解，數(shù)值模擬結(jié)果表明改進(jìn)后的遺傳算法不僅可以求得高精度的解，而且大大提高了遺傳算法的局部尋優(yōu)能力.曾毅“浮點(diǎn)遺傳算法在非線性方程組求解中的應(yīng)用”提出利用浮點(diǎn)遺傳算法適應(yīng)值的分布和實(shí)數(shù)編碼的特點(diǎn)，通過(guò)縮小、移動(dòng)搜索空間的方法，將整體和局部尋優(yōu)能力有機(jī)結(jié)合，數(shù)值模擬結(jié)果表明該算法求精確解的有效性.吳國(guó)輝等“一種新的求解非線性方程組的混合遺傳算法”提出利用浮點(diǎn)遺傳算法全局群體搜索能力及起始搜索速度快的特點(diǎn)，快速得到接近精確解的較優(yōu)解，之后將其作為擬牛頓法迭代的初始值，利用其局部尋優(yōu)能力非常強(qiáng)的特點(diǎn)快速迭代至精確解，該算法融合了遺傳算法和擬牛頓法的優(yōu)點(diǎn)，具有較好的收斂速度和相當(dāng)精度的收斂解.杜娟等“一種新的非線性方程組的混合量子遺傳算法”綜合考慮了量子遺傳算法和擬牛頓法的各自優(yōu)點(diǎn)，結(jié)合兩者提出一種求解非線性方程組的有效算法，充分發(fā)揮量子遺傳算法的群體搜索和全局收斂性，同時(shí)采用擬牛頓法作為一個(gè)強(qiáng)局部搜索算子，把量子遺傳算法的尋優(yōu)結(jié)果作為擬牛頓算法的初值，有效地解決了擬牛頓法對(duì)初始值的敏感問(wèn)題，提高了算法的局部搜索能力，仿真實(shí)驗(yàn)表明此算法具有較高的求解精度與成功率.

總之，遺傳算法在求解非線性方程組具有一定的優(yōu)勢(shì)，但仍存在一些問(wèn)題有待于進(jìn)一步研究，如增強(qiáng)局部搜索能力、快速達(dá)到最優(yōu)解、改造遺傳算法防止早熟、恰當(dāng)選擇參數(shù)等問(wèn)題.如何改進(jìn)遺傳算法或結(jié)合傳統(tǒng)的算法，更好地應(yīng)用于解決各類(lèi)復(fù)雜的非線性系統(tǒng)，這將是需要繼續(xù)探索的課題.