影響阻尼牛頓法收斂性的兩個重要參數(shù)

張建軍,李春泉,張烈輝

(1.西南石油大學理學院,四川成都 610500；2.西南石油大學石油工程學院,四川成都 610500)

影響阻尼牛頓法收斂性的兩個重要參數(shù)

張建軍1,李春泉1,張烈輝2

(1.西南石油大學理學院,四川成都 610500；2.西南石油大學石油工程學院,四川成都 610500)

對阻尼牛頓算法作了適當?shù)母倪M,證明了新算法的收斂性.基于新算法,運用計算機代數(shù)系統(tǒng)Matlab,研究了迭代次數(shù)k,參數(shù)對(μ,λ)與初值x0三者間的依賴關(guān)系,研究了病態(tài)問題在新算法下趨于穩(wěn)定的漸變(瞬變)過程.數(shù)值結(jié)果表明:(1)阻尼牛頓迭代中,參數(shù)對(μ,λ)與迭代次數(shù)k間存在特有的非線性關(guān)系；(2)適當?shù)膮?shù)對(μ,λ)與阻尼因子α的共同作用能夠在迭代中大幅度地降低病態(tài)問題的Jacobi陣的條件數(shù),使病態(tài)問題逐漸趨于穩(wěn)定,從而改變原問題的收斂性與收斂速度.

阻尼牛頓法；雅可比矩陣的條件數(shù)；病態(tài)問題；參數(shù)對(μ,λ)

1 引言

目前,非線性方程組求解的數(shù)值方法有Newton法,同倫型法,單純形法與胞腔排除法[13].

牛頓迭代法是一種非常實用的計算方法,迭代公式如下:選擇參數(shù)α的原則是使之滿足:其中μ∈(0,1)為某定數(shù),‖·‖表示向量或矩陣的任何一種范數(shù).

按(3)和(4)式進行迭代修正的方法稱為阻尼牛頓法,參數(shù)α稱為阻尼因子,當α=1時,就是牛頓法.牛頓法的顯著缺點是,它是局部收斂的.它要求初始近似x0適當接近非線性方程組(1)的解x*,這個條件難以界定,阻尼牛頓法是基于下降算法,并具有大范圍收斂性的一種迭代法.文獻[4]給出了求解非線性方程組(1)的阻尼牛頓算法,并給出了特殊情形下阻尼牛頓法的大范圍收斂性結(jié)果.文獻[4]中涉及到兩個重要參數(shù)μ,λ.但在文獻所給算法的5個步驟中沒有明確參數(shù)λ的作用；文獻中關(guān)于算法的收斂性定理也與參數(shù)λ沒有直接的關(guān)聯(lián).

本文結(jié)構(gòu)安排如下:

第二節(jié)對文獻[4]的算法作了適當?shù)母倪M,證明了新算法的收斂性.新的算法與相應的收斂性定理均明確了參數(shù)μ與λ各自的作用與相互關(guān)系.第三節(jié)研究了阻尼牛頓迭代中迭代次數(shù)k,參數(shù)對(μ,λ)與初值x0三者間的關(guān)系；第三節(jié)還研究了病態(tài)問題在適當?shù)膮?shù)對(μ,λ)和阻尼因子α的共同作用下趨于穩(wěn)定的漸變(瞬變)過程.

2 主要結(jié)果

2.1 改進的阻尼牛頓算法

設μ,λ為固定的數(shù),且滿足

2.2 收斂性定理

下面證明,上述算法的第4步到第5步循環(huán)可在有限步內(nèi)完成.

從而由(9)式推得(4)式對這個擴充的參數(shù)域成立.

這個定理指出,若F′(x)在D中非奇異,則阻尼牛頓法在每個迭代中,α僅改變有限多次.

3 數(shù)值試驗

3.1 迭代次數(shù)k、參數(shù)對(μ,λ)與初值x0三者間的關(guān)系

為了考察新算法中參數(shù)μ與λ對迭代過程的影響,選擇文獻[4-5]中的非線性方程組為例加以說明.

例1考慮非線性方程組

兩組近似解分別為(0.4597,-0.9038,-0.5494)與(0.4404,-1.0948,-0.5546),精度要求:ε=10-5. (一)固定初值x0=(5,5,5)T,令參數(shù)對(μ,λ)取10種不同的線性關(guān)系(滿足(5)式)

對每個參數(shù)對(μ,λ)計算取得近似解所需要的迭代次數(shù)k,參見圖1.圖中10條直線(與10條曲線相對應)反映的是參數(shù)μ與λ的不同線性關(guān)系,而10條曲線反映的是相應的直線上各點所對應的迭代次數(shù).不同線性關(guān)系下的最小,最大迭代次數(shù)分別為7,10,11,12,13,15,17,19,24,33與282,286,294,495,533,564,591,1000,1000,1000.

圖1 迭代次數(shù)k、參數(shù)對(μ,λ)與初值x0的關(guān)系(1)

計算結(jié)果表明:①在不同線性關(guān)系中,l越小,取得近似解所需的迭代次數(shù)越小.②在不同線性關(guān)系中,參數(shù)對(μ,λ)與迭代次數(shù)k間存在相似的非線性關(guān)系,即隨著直線的下降,迭代次數(shù)先減后增.在直線的前端或中部位置,迭代次數(shù)達到最小.在直線的末端,隨著直線的下降,迭代次數(shù)劇烈增加.

(二)固定參數(shù)μ與λ的線性關(guān)系,令初值x0變化

在(14)式中取l=1/10.初值(x0,y0,z0)分別取為(5,5,5),(-5,-5,-5),(20,20,20),(-20, -20,-20).四種初值下的最小迭代次數(shù)分別為7,9,15與12(參見圖2).計算結(jié)果表明:①初值越接近非線性方程組的解x*,取得近似解所需的迭代次數(shù)越小.②當初值偏離近似解較大時,參數(shù)對(μ,λ)與迭代次數(shù)k的依賴關(guān)系可能會出現(xiàn)較大的波動,如初值為(20,20,20),(-20,-20,-20)時,出現(xiàn)迭代次數(shù)超過1000的情形.

圖2 迭代次數(shù)k、參數(shù)對(μ,λ)與初值x0的關(guān)系(2)

值得注意的是,即使是對應同一初值,在某些參數(shù)對(μ,λ)下,迭代過程收斂于(0.4404, -1.0948,-0.5546)；而在另一些參數(shù)對(μ,λ)下,迭代過程收斂于(0.4597,-0.9038,-0.5 494).

為了說明新算法相對于牛頓法的優(yōu)越性,應用牛頓法求解例1給出的非線性方程組.在初值(5,5,5),(-5,-5,-5),(-20,-20,-20)下牛頓法收斂,迭代次數(shù)分別為9,9,11.與阻尼牛頓法相比,牛頓法的收斂速度更快.原因是上述初值下,牛頓迭代中方程組并沒有出現(xiàn)奇異或數(shù)值穩(wěn)定性問題.在初值(20,20,20)處,由于牛頓迭代中第一次近似解的雅可比矩陣的條件數(shù)為無窮大,計算機停止計算,牛頓法失敗.此時,阻尼牛頓法顯示出了優(yōu)越性,如圖2所示,在100對(μ,λ)中,97對收斂且迭代次數(shù)均小于400,最小迭代次數(shù)為15.

3.2 病態(tài)問題趨于穩(wěn)定的漸變(瞬變)過程分析

由于函數(shù)F在近似解處的Jacobi陣的條件數(shù)的大小能夠反映方程組的數(shù)值穩(wěn)定性.因此,本文通過計算條件數(shù)跟蹤研究了新算法下病態(tài)問題趨于穩(wěn)定的漸變(瞬變)過程.

例2繼續(xù)研究例1中的非線性方程組.如前所述,在牛頓迭代中,一旦初值遠離所給非線性方程組的解x*,牛頓法就可能失敗.表1給出了4組初值下牛頓迭代的計算結(jié)果(其中:ck=cond(F′(xk)),k=1,2,···表示第k次近似解的Jacobi陣的條件數(shù)).所列4組初值下牛頓法不收斂.原因之一是計算的穩(wěn)定性,第一次迭代后,它們的近似解的Jacobi陣的條件數(shù)都很大(或由于Jacobi陣的某些元素為無窮大而使計算機無法確定其條件數(shù)),導致了計算過程的不穩(wěn)定.因此,它們均屬于病態(tài)問題.另一個原因是計算的效率問題,根據(jù)文獻[6-8],當函數(shù)F在近似解處的Jacobi陣的條件數(shù)很大時,可能導致迭代中產(chǎn)生很小的步長,從而降低算法的效率.

表1 牛頓迭代中的病態(tài)問題舉例

新算法下,上述病態(tài)問題都能在15步之內(nèi)取得滿足誤差精度的近似解.跟蹤計算了收斂過程中條件數(shù)ck的變化狀況.計算結(jié)果見表2.通過對該表的觀察與對比,發(fā)現(xiàn)條件數(shù)的變化呈現(xiàn)出一定的規(guī)律性:①通過選擇適當?shù)膮?shù)對(μ,λ)及對阻尼因子α的調(diào)整,使得第一次近似解的Jacobi陣的條件數(shù)都得到大幅度地下降.②從第二步迭代開始,各次近似解的Jacobi陣的條件數(shù)以兩種方式下降,直至收斂.對某些病態(tài)問題(如P01等),迭代中Jacobi陣的條件數(shù)逐漸變小(單調(diào)下降方式或小幅波動下降方式)而使迭代過程收斂.而對另一些病態(tài)問題(如P02、P03、P04等),Jacobi陣的條件數(shù)先逐漸變大,達到最大值后,陡然變小而使迭代過程收斂.

表2 阻尼牛頓迭代中條件數(shù)ck的變化狀況

參考文獻

[1]Xu Z B,Zhang J S,Wang W.A cell exclusion algorithm for determining all the solutions of a nonlinear system of equation[J].Appl.Math.and Computation,1996,80:181-203.

[2]Zhang J S,You Z Y,Xu Z B.A cell method for finding all solutions of a nonlinear equations and optimization problems[J].Math.Numerica Sinica,1994,16:195-203.

[3]孟彪龍,邢志棟.非線性方程組求全部解的胞腔排除法[J].純粹數(shù)學與應用數(shù)學,1999,15(2):72-76.

[4]黃象鼎,曾鐘鋼,馬亞南.非線性數(shù)值分析的理論與方法[M].武漢:武漢大學出版社,2004.

[5]施妙根,顧麗珍.科學和工程計算基礎(chǔ)[M].北京:清華大學出版社,1999.

[6]Deuflhard P.A modified Newton method for the solution of ill-conditioned systems of nonlinear equations with applications to multiple shooting[J].Numer.Math.,1974,22:289-315.

[7]曾金平,劉星果.自然水平函數(shù)在求解病態(tài)非線性方程組的阻尼牛頓法中的應用[J].湖南大學學報:自然科學版,2003,30(1):8-10.

[8]周碩,郭麗杰,吳柏生.Jacobi迭代預處理的條件數(shù)與迭代次數(shù)的關(guān)系[J].東北電力學院學報,2003,23(6):57-60.

The effect of two important parameter upon the convergence in damped Newton method

Zhang Jianjun1,Li Chunquan1,Zhang Liehui2

(1.College of Science,Southwest Petroleum University,Chengdu610500,China； 2.College of Petroleum Engineering,Southwest Petroleum University,Chengdu,610500China)

In this paper,the damped Newton method is improved suitably and the convergence for new method is proved.Based on the new algorithm,a program is proposed and fulfilled by numerical and symbolic computations in Matlab,we study the relation among the iteration degrees k,parameters(μ,λ)and initial value x0.We also study the gradual(transient)process of the ill-conditioned systems nonlinear equations tending stable.Numerical results show that there is a special nonlinear relation between the parameters(μ,λ)and the iteration degrees k for damped Newton method and that the suitable parameters(μ,λ)and damping coefficient α can greatly decrease condition number of Jacobi matrix of ill-conditioned systems nonlinear equations.The ill-conditioned problems can gradually become stable and thus the convergence and the convergence speed of the ill-conditioned systems nonlinear equations can be changed.

damped Newton method,condition number of the Jacobi matrix, ill-conditioned systems equations,parameters(μ,λ)

O241.7

A

201109018(2012)04-0433-07

2011-09-24.

四川省教育廳2011年重點科研項目(10ZA073).

張建軍(1958-),博士,副教授,研究方向：石油工程信息分析與處理.

2010 MSC:65k05,90C30