非線性方程組數值解法

n個變量n個方程(n >1)的方程組表示為

(1)

式中ƒi(x1,x2,…,xn)是定義在n維歐氏空間R 的開域D上的實函數。若ƒi中至少有一個非線性函數，則稱(1)為非線性方程組。在R 中記

ƒ=

則(1)簡寫為ƒ(尣)=0。若存在尣∈D，使ƒ(尣)=0，則稱尣為非線性方程組的解。方程組(1)可能有一個解或多個解，也可能有無窮多解或無解。對非線性方程組解的存在性的研究遠不如線性方程組那樣成熟，現有的解法也不象線性方程組那樣有效。除極特殊的方程外，一般不能用直接方法求得精確解，主要採用迭代法求近似解。根據不同思想構造收斂於解尣的迭代序列{尣}(k=0，1，…)，即可得到求解非線性方程組的各種迭代法，其中最著名的是牛頓法。

非線性方程組數值解法 - 牛頓法及其變形 牛頓法基本思想是將非線性問題逐步線性化而形成如下迭代程序：

(2)

式中

是ƒ(尣)的雅可比矩陣,尣是方程(1)的解尣的初始近似。

這個程序至少具有2階收斂速度。由尣算到尣的步驟為:①由尣算出ƒ(尣)及

;②用直接法求線性方程組

的解Δ尣；③求

。

由此看到迭代一次需計算n個分量函數值和 n個分量偏導數值，並求解一次n階線性方程組。

為了評價非線性方程組不同迭代法的優劣，通常用效率

作為衡量標準,其中P為迭代法的收斂階,W為每迭代步計算函數值ƒi及偏導數值

的總個數（每迭代步中求一次逆的工作量相同,均不算在W 內）。效率e越大表示此迭代法花費代價越小,根據效率定義，牛頓法(2)的效率為

。

牛頓法有很多變形,如當

奇異或嚴重病態時，可引進阻尼因子λk，得到阻尼牛頓法，即

式中I是單位矩陣。牛頓法是局部收斂方法,因而對初始近似尣限制較嚴，為放寬對尣的要求,擴大收斂範圍,通常可引進鬆弛因子ωk，得到牛頓下降法：

(3)

式中ωk的選擇應使

成立。

為減少解線性方程組次數，提高效率，可使用修正牛頓程序

(4)

這種算法也稱為薩馬斯基技巧，它的收斂階為 p =m+1，由尣 計算

的工作量為W =n+mn，於是該法的效率

。當n=10,m=7時,

當n=100,m=37時,

，由此看到修正牛頓法(4)比牛頓法效率高，且m 越大效果越明顯。

在計算機上往往採用不計算偏導數的離散牛頓法，即

(5)

式中

，

其中ej為基向量,

,若取

，則(5)仍具有2階收斂速度。其效率與牛頓法相同。

若在牛頓法(2)中解線性方程組不用直接法,而採用迭代法則得到一類解非線性方程組的雙重迭代法。按解線性方程組採用的方法不同就得到不同名稱的迭代法，如牛頓－賽德爾迭代法，牛頓－SOR迭代法，牛頓－ADI迭代法，等等。這些方法都具有超線性收斂速度，工作量也比牛頓法大，除了對某些特殊稀疏方程組外，通常用得校少。若將解線性方程組迭代法的思想直接用於非線性方程組(1)，然後把(1)化為一維方程求解，可得到另一類雙重迭代法，由於採用的迭代法與解一維非線性方程的方法不同，則得到不同的雙重迭代法。如果利用SOR迭代法後再用牛頓法解一維方程則得SOR－牛頓迭代法，在牛頓法中只計算一步而不進行迭代，則得一步的SOR－牛頓迭代，其計算公式可表示為

式中記號嬠iƒi表示

；ω為迭代參數，當ω=1時就是賽德爾-牛頓迭代法,這類方法對解維數高的稀疏的非線性方程組是有效的。

若對方程組 (1)線性化時使用插值方法確定線性方程組

(6)

中的Ak和bk,則可得到一類稱為割線法的迭代序列。假定已知第k步近似尣k，為確定Ak和bk,可在尣附近取n個輔助點у忋(j=1,2,…,n),使n個向量

線性無關，由插值條件可知

由此可求得

由(6)解得

以此作為方程 (1)的新近似，記作

，於是得到

(7)

(7)稱為解非線性方程組的割線法。輔助點у忋 取得不同就得到不同的割線法程序，例如取

為常數(j=1,2,…,n)，就得到與(5)相同的程序，由於它只依賴於尣點的信息，故也稱一點割線法,若取

它依賴於點尣及

, 稱為兩點割線法。其他多點割線法由於穩定性差，使用較少。

非線性方程組數值解法 - 布朗方法 布朗採用對每個分量方程 ƒi(尣)=0逐個進行線性化並逐個消元的步驟，即在每迭代步中用三角分解求線性方程組的解，得到了一個效率比牛頓法提高近一倍的迭代法，即

式中

(8)中當i=n時求得xn記作

,再逐次回代,求出

(i=n-1,n-2,…,1)就完成了一個迭代步。布朗迭代程序的斂速仍保持p=2，而每一迭代步的工作量

，故效率

對這方法還可與牛頓法一樣進行改進，得到一些效率更高的算法。這類方法是70年代以來數值軟件包中常用的求解非線性方程組的算法。

非線性方程組數值解法 - 擬牛頓法 為減少牛頓法的計算量，避免計算雅可比矩陣及其逆，60年代中期出現了一類稱為擬牛頓法的新算法,它有不同的形式，常用的一類是秩1的擬牛頓法，其中不求逆的程序為

式中

,

,

，稱為逆擬牛頓公式。計算時先給出尣及 B0，由(9)逐步迭代到滿足精度要求為止。每步只算 n個分量函數值及O(n)的計算量,比牛頓法一步計算量少得多。理論上已證明，當尣及B0選得合適時,它具有超線性收斂速度,但實踐表明效率並不高於牛頓法，理論上尚無嚴格證明。

非線性方程組數值解法 - 最優化方法 求方程組 (1)的問題等價於求目標函數為

的極小問題,因此可用無約束最優化方法求問題(1)的解（見無約束優化方法）。 非線性方程組數值解法 - 連續法 又稱嵌入法，它可以從任意初值出發求得方程組(1)的一個足夠好的近似解,是一種求出好的迭代初值的方法。連續法的基本思想是引入參數 t∈【0,b】，構造算子H(尣,t)，使它滿足條件：H(尣,0)=ƒ0(尣),H(尣,b)=ƒ(尣)，其中ƒ0(尣)=0的解尣0是已知，方程：

(10)

在t∈【0,b】上有解尣=尣(t)，則尣(b)=尣就是方程(1)的解。當b有限時，通常取b=1，例如可構造。

(11)

這裏尣是任意初值,顯然H(尣,0)=0,H(尣,1)=ƒ(尣)。為了求得(10)在t=1的解尣=尣(1),可取分點0=t0<t1<…<tN=1在每個分點ti(i=1,2,…,N)上，求方程組 H(尣,ti)=0 (i=1,2,…,N) (12)

的解尣，如果取尣為初值，只要

足夠小，牛頓迭代就收斂，但這樣做工作量較大。已經證明，如果方程組(12)只用一步牛頓法，當t=tN=1時，再用牛頓迭代，結果仍具有2階收斂速度。以(11)為例,得到連續法的程序為：

若H(尣,t)的偏導數Ht(尣,t)及

在D×【0,1】嶅R

上連續。且

非奇異，則由(10)對t求導可得到等價的微分方程初值問題:

(13)

於是求方程(10)的解就等價於求常微初值問題(13)的解，求(13)的解可用數值方法由t=0計算到t=tN=b得到數值解

。已經證明只要N足夠大,以尣為初值再進行牛頓迭代可收斂到方程(1)的解x，這種算法稱為參數微分法。

20世紀60年代中期以後，發展了兩種求解非線性方程組(1)的新方法。一種稱為區間迭代法或稱區間牛頓法，它用區間變量代替點變量進行區間迭代，每迭代一步都可判斷在所給區間解的存在惟一性或者是無解。這是區間迭代法的主要優點，其缺點是計算量大。另一種方法稱為不動點算法或稱單純形法，它對求解域進行單純形剖分，對剖分的頂點給一種恰當標號，並用一種有規則的搜索方法找到全標號單純形,從而得到方程(1)的近似解。這種方法優點是，不要求ƒ(尣)的導數存在,也不用求逆，且具有大範圍收斂性，缺點是計算量大。

J.M.Ortega and W.G.Rheinboldt,Iterative Solution of Nonlinear Equations in Several variables,Academic Press,New York,1970.