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

(1)

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

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

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

　(2)

式中

是 f( x k)的雅可比矩陣， x 0是方程(1)的解 x *的初始近似。

　　這個程序至少具有2階收斂速度。由xk算到xk+的步驟為：①由xk算出f(xk)及

；②用直接法求線性方程組 的解Δ x k；③求 。

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

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

作為衡量標準，其中 P為迭代法的收斂階， W為每迭代步計算函數值 f i及偏導數值 的總個數（每迭代步中求一次逆的工作量相同，均不算在 W內）。效率 e越大表示此迭代法花費代價越小，根據效率定義，牛頓法(2)的效率為 。

　　牛頓法有很多變形，如當

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

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

(3)

式中 ω k的選擇應使 成立。

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

(4)

這種算法也稱為薩馬斯基技巧，它的收斂階為 p= m+1，由 x k計算 的工作量為 W= n 2+ m n，於是該法的效率 。當 n=10， m＝7時， 當 n＝100， m＝37時， ，由此看到修正牛頓法(4)比牛頓法效率高，且 m越大效果越明顯。

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

(5)

式中

，

其中 e j為基向量， ，若取 ，則(5)仍具有2階收斂速度。其效率與牛頓法相同。

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

式中記號∂ i f i表示 ； ω為迭代參數，當 ω=1時就是賽德爾-牛頓迭代法，這類方法對解維數高的稀疏的非線性方程組是有效的。

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

　　　　 (6)

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

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

由此可求得

由(6)解得 以此作為方程(1)的新近似，記作 ，於是得到

(7)

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

為常數( j=1，2，…， n)，就得到與(5)相同的程序，由於它隻依賴於 x k點的信息，故也稱一點割線法，若取 它依賴於點 x k及 ，稱為兩點割線法。其他多點割線法由於穩定性差，使用較少。

　　佈朗方法　佈朗采用對每個分量方程fi(x)=0逐個進行線性化並逐個消元的步驟，即在每迭代步中用三角分解求線性方程組的解，得到瞭一個效率比牛頓法提高近一倍的迭代法，即

式中

　　 　　

(8)中當 i= n時求得 x n記作 ，再逐次回代，求出

( i= n-1， n-2，…，1)就完成瞭一個迭代步。佈朗迭代程序的斂速仍保持 p＝2，而每一迭代步的工作量 ，故效率 對這方法還可與牛頓法一樣進行改進，得到一些效率更高的算法。這類方法是70年代以來數值軟件包中常用的求解非線性方程組的算法。

　　擬牛頓法　為減少牛頓法的計算量，避免計算雅可比矩陣及其逆，60年代中期出現瞭一類稱為擬牛頓法的新算法，它有不同的形式，常用的一類是秩1的擬牛頓法，其中不求逆的程序為

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

　　最優化方法　求方程組(1)的問題等價於求目標函數為

的極小問題，因此可用無約束最優化方法求問題(1)的解（見 無約束優化方法）。

　　連續法　又稱嵌入法，它可以從任意初值出發求得方程組(1)的一個足夠好的近似解，是一種求出好的迭代初值的方法。連續法的基本思想是引入參數t∈[0，b]，構造算子H(x，t)，使它滿足條件：H(x，0)=f0(x)，H(x，b)=f(x)，其中f0(x)=0的解x0是已知，方程：

　　　(10)

在 t∈[0， b]上有解 x= x( t)，則 x( b)= x *就是方程(1)的解。當 b有限時，通常取 b=1，例如可構造。

(11)

這裡 x 0是任意初值，顯然 H( x 0，0)=0， H( x，1)= f( x)。為瞭求得(10)在 t=1的解 x *= x(1)，可取分點0= t 0＜ t 1<…＜ t N=1在每個分點 t i( i=1，2，…， N)上，求方程組

H(x，ti)=0(i=1，2，…，N) (12)

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

　　若H(x，t)的偏導數Ht(x，t)及

在 D×[0，1]⊂ R 上連續。且 非奇異，則由(10)對 t求導可得到等價的微分方程初值問題：

　　　 (13)

於是求方程(10)的解就等價於求常微初值問題(13)的解，求(13)的解可用數值方法由 t=0計算到 t= t N= b得到數值解 。已經證明隻要 N足夠大，以 x N為初值再進行牛頓迭代可收斂到方程(1)的解 x *，這種算法稱為參數微分法。

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

　　

參考書目

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