非線性方程組數(shù)值解法n個變量n個方程（n>1）的方程組表示為'⑴式中人（％,%,…,％）是定義在n維歐氏空間Rn的開域D上的實函數(shù)。若人中至少有一個非線性函數(shù)，則稱（i）為非線性方程組。在心中記/=0/，…，竺=0麗 貝以1）簡寫為/（允）二0。若存在允*ED，使/（允*）=0，則稱允*為非線性方程組的解。方程組（1）可能有一個解或多個解，也可能有無窮多解或無解。對非線性方程組解的存在性的研究遠不如線性方程組那樣成熟，現(xiàn)有的解法也不象線性方程組那樣有效。除極特殊的方程外，一般不能用直接方法求得精確解，目前主要采用迭代法求近似解。根據(jù)不同思想構(gòu)造收斂于解允*的迭代序列｛允對（k=0，1，…），即可得到求解非線性方程組的各種迭代法，其中最著名的是牛頓法牛頓法及其變形 牛頓法基本思想是將非線性問題逐步線性化而形成如下迭代程序：式中是/（允k）的雅可比矩陣,允0是方程（1）的解允的初始近似。這個程序至少具有2階收斂速度。由允k算到允k+的步驟為:①由允k算出/（允k）及;②用直接法求線性方程組（護）的解A允k；;②用直接法求線性方程組（護）的解A允k；③求由此看到迭代一次需計算n個分量函數(shù)值和n2個分量偏導(dǎo)數(shù)值，并求解一次n階線性方程組。Inpe= 為了評價非線性方程組不同迭代法的優(yōu)劣，通常用效率 /作為衡量標準，其中P為迭代法的收斂階,W為每迭代步計算函數(shù)值人及偏導(dǎo)數(shù)值‘叼的總個數(shù)（每迭代步中求一次逆的工作量相同，均不算在W內(nèi)）。效率e越大表示此迭代法花費代價越小，根據(jù)效率定結(jié)構(gòu)計算連續(xù)體模型-基礎(chǔ)方程式既*-噤啜值分析一數(shù)值解義，牛頓法（2）結(jié)構(gòu)計算連續(xù)體模型-基礎(chǔ)方程式既*-噤啜值分析一數(shù)值解義，牛頓法（2）的效率為L離散體模型一數(shù)值分析一數(shù)值解牛頓法有很多變形，如當 奇異或嚴重病態(tài)時，可引進阻尼因子久k，得到阻尼牛頓法，即

式中I是單位矩陣。牛頓法是局部收斂方法，因而對初始近似允。限制較嚴，為放寬對允0的要求，擴大收斂范圍,通常可引進松弛因子3k，得到牛頓下降法：0=SL…），（3）式中3k的選擇應(yīng)使1|/^+1）11<1|/^）11成立。為減少解線性方程組次數(shù)，提高效率，可使用修正牛頓程序=妒, \妒疝=妒”」藉，（妒村），>

盧=4卜12…移;SCW刃⑷這種算法也稱為薩馬斯基技巧，它的收斂階為P=m+1，由允k計算""'的工作量為W=n2『.Inte+1）+mn，于是該法的效率*疝+咐。當n=10,m=7時，，L94,當n=i00,m=37時，現(xiàn)州用）聲（M）=對七由此看到修正牛頓法（4）比牛頓法效率高，且m越大效果越明顯。在計算機上往往采用不計算偏導(dǎo)數(shù)的離散牛頓法，即妒'=菸（妒島圳一了（『）,0二口,1,...），⑸式中，其中e.為基向量業(yè)=（誠,?5若取礦=婦”（妒）L則（5）仍具有2階收斂速度。其效率與牛頓法相同。若在牛頓法(2)中解線性方程組不用直接法，而采用迭代法則得到一類解非線性方程組的雙重迭代法。按解線性方程組采用的方法不同就得到不同名稱的迭代法，如牛頓一賽德爾迭代法，牛頓一SOR迭代法，牛頓一ADI迭代法，等等。這些方法都具有超線性收斂速度，工作量也比牛頓法大，除了對某些特殊稀疏方程組外，通常用得校少。若將解線性方程組迭代法的思想直接用于非線性方程組(1)，然后把(1)化為一維方程求解，可得到另一類雙重迭代法，由于采用的迭代法與解一維非線性方程的方法不同，則得到不同的雙重迭代法。如果利用SOR迭代法后再用牛頓法解一維方程則得SOR一牛頓迭代法，在牛頓法中只計算一步而不進行迭代，則得一步的SOR一牛頓迭代，其計算公式可表示為(2=1,2,■■■,?；氐=竺式中記號媒"表示'明；s為迭代參數(shù)，當s=1時就是賽德爾-牛頓迭代法，這類方法對解維數(shù)高的稀疏的非線性方程組是有效的。割線法若對方程組(1)線性化時使用插值方法確定線性方程組"=機=0 ⑹中的Ak和bk,則可得到一類稱為割線法的迭代序列。假定已知第k步近似允k，為確定Ak和bk,可在允k附近取n個輔助點y4'己(j=1,2,…,n),使n個向量1-#切-妒，…，就-必線性無關(guān)，由插值條件可知A"+4=叫仃=1,幻…，心&疽+竦由此可求得如勇-璀）=兒葉）-貝挪）（廣以…洲垃=/（『）-且對L由（6）解得#=一線板=、-入？了3\以此作為方程⑴的新近似，記伊*',于是得到廣=妒—妃m,妒=函-妒，…成-妒子仲-了（妒、）,>..S”）佇 〔⑺（7）稱為解非線性方程組的割線法。輔助點y4'己取得不同就得到不同的割線法程序，例如取為=*+為％矽=婦仃（那）||,也，口為常數(shù)（j=i,2,...,n）,就得到與⑸相同的程序，由于它只依賴于允k點的信息，故也稱一點割線法若取財=*—*=它依賴于點允k及菸'稱為兩點割線法。其他多點割線法由于穩(wěn)定性差，使用較少。布朗方法 布朗采用對每個分量方程"（允）二0逐個進行線性化并逐個消元的步驟，即在每迭代步中用三角分解求線性方程組的解，得到了一個效率比牛頓法提高近一倍的迭代法，即TOC\o"1-5"\h\zr n -冷*-（A擴耳（妒）-￡如約-勺L j=i+i _=岳（弒+1冉+私…，跖0， （8）式中

心=［以3+效勺）-貝3）凈g"）=￡（扇,…,&-1,叫，…,Q=1）2<--）?；7=靜+⑻中當i=n時求得xn記作破+1,再逐次回代，求出時+1=氐庇+1，…，、)(i=n-1,n-2,…,1)就完成了一個迭代步。布朗迭代程序的斂速仍保持p=2,而每一迭代步的工作量故效率對這方法還可與牛頓法樣進行改進，得到一些效故效率對這方法還可與牛頓法樣進行改進，得到一些效率更高的算法。這類方法是70年代以來數(shù)值軟件包中常用的求解非線性方程組的算法。擬牛頓法 為減少牛頓法的計算量，避免計算雅可比矩陣及其逆，60年代中期出現(xiàn)了一類稱為擬牛頓法的新算法，它有不同的形式，常用的一類是秩1的擬牛頓法，其中不求逆的程序為［微分方程數(shù)值解法一數(shù)值積分法，差分法，松弛法，蒙特卡洛法，等等數(shù)值解法加極余重法一配置法，最小二乘法，矩法，伽遼數(shù)值解法變分法一瑞利-里茲法，坎托羅維奇法，有限元TA，守寺式中恥**-「哈=f(wm,虻玖么葺，稱為逆擬牛頓公式。計算時先給出允0及B0，由(9)逐步迭代到滿足精度要求為止。每步只算n個分量函數(shù)值及O(n2)的計算量，比牛頓法一步計算量少得多。理論上已證明，當允0及B0選得合適時，它具有超線性收斂速度，但實踐表明效率并不高于牛頓法，理論上尚無嚴格證明。最優(yōu)化方法 求方程組(1)的問題等價于求目標函數(shù)為*=了("了3)的極小問題,因此可用無約束最優(yōu)化方法求問題(1)的解(見無約束優(yōu)化方法)。連續(xù)法 又稱嵌入法，它可以從任意初值出發(fā)求得方程組(1)的一個足夠好的近似解,是一種求出好的迭代初值的方法。連續(xù)法的基本思想是引入?yún)?shù)tE【0,b】，構(gòu)造算子H（允,t）,使它滿足條件：H（允,0）二/0（允），H（允,b）二/（允），其中/0（允）=0的解允0是已知，方程:（10）在t￡【0,b】上有解允=允（七），則允（b）。*就是方程（1）的解。當b有限時，通常取b=1,例如可構(gòu)造。"[5),(11)這里允0是任意初值，顯然H（允0,0）=0,H（允，1）二/（允）。為了求得（10）在t=1的解允*=允（1）,可取分點0=t0<t1<^<tN=1在每個分點tj（i=1,2,…,N）上，求方程組H(允,眼二0(i=1,2,…,N)(12)的解允i,如果取允「1為初值，只要山上1=弓一上1足夠小，牛頓迭代就收斂，但這樣做工作量較大。已經(jīng)證明，如果方程組（12）只用一步牛頓法，當t=tN=1時，再用牛頓迭代，結(jié)果仍具有2階收斂速度。以（11）為例,得到連續(xù)法的程序為:若H(允,t)的偏導(dǎo)數(shù)Ht(允,t)及物在DX【0,1】嶅R*上連續(xù)。且物非奇異，則由(10)對t求導(dǎo)可得到等價的微分方程初值問題：(13)于是求方程(10)的解就等價于求常微初值問題(13)的解，求(13)的解可用數(shù)值方法由t=0計算到t=tN=b得到數(shù)值解時蘭嶺)=航。已經(jīng)證明只要N足夠大，以允n為初值再進行牛頓迭代可收斂到方程(1)的解x*,這種算法稱為參數(shù)微分法。20世紀60年代中期以后，發(fā)展了兩種求解非線性方程組(1)的新方法。一種稱為區(qū)間迭代法或稱區(qū)間牛頓法，它用區(qū)間變量代替點變量進行區(qū)間迭代，每迭代一步都可判斷在所給區(qū)間解的存在惟一性或者是無解。這是區(qū)間迭代法的主要優(yōu)點，其缺點是計算量大。另一種方法稱為不動點算法或稱單純形法，它對求解域進行單純形剖分，對剖分的頂點給一種恰當標號，并用一種有規(guī)則的搜索方法找到全標