關于解一類奇異非線性方程組的牛頓法的收斂性

楊家嶺, 曹德欣

(中國礦業大學 理學院 江蘇 徐州 221116)

?

關于解一類奇異非線性方程組的牛頓法的收斂性

楊家嶺, 曹德欣

(中國礦業大學 理學院 江蘇 徐州 221116)

對一類奇異非線性方程組，運用Moore-Penrose廣義逆建立牛頓迭代法，分析了其局部收斂性、半局部收斂性以及收斂半徑的估計，數值例子也表明了算法的有效性.

奇異非線性方程組； 牛頓法； Moore-Penrose逆； 半局部收斂

0 引言

許多應用數學和工程問題都可歸結為對非線性方程組的求解[1-3], 其中也存在著大量的奇異非線性方程組, 并且引起了人們的廣泛關注[4-7].作者考慮如下形式的奇異非線性方程組的求解問題：

F(x)=0,

(1)

這里F:D?Rn→Rm,F(x)=(f1(x),f2(x),…,fm(x))T,x=(x1,x2,…,xn)T,n≤m.

牛頓迭代格式

xk+1=xk-DF(xk)-1F(xk),k=0,1,…

(2)

及其變形是求解非線性方程組最有效的方法. 關于牛頓法的收斂性有兩個最為重要的結果： 一是著名的Kantorovich定理[8], 其半局部收斂性定理及證明方法對迭代法的研究產生了深遠的影響；二是Smale點估計理論[9], 該定理給出了僅依賴于算子在初始點的信息來逼近零點的判斷依據. 關于牛頓法收斂半徑的估計還可以參見文獻[10-11].

對于方程組(1)而言,F的Frechet導算子DF(xk)不一定可逆, 尤其是當n

xk+1=xk-DF(xk)?F(xk),k=0,1,…

(3)

格式(3)的不動點x*是方程組F(x)=0的最小二乘解, 但若DF(x*)是滿秩, 則x*是方程組F(x)=0的解.

對于n≥m情況下的奇異問題，文獻[4-7]已經進行了詳細的論述, 特別是文獻[7]對F在初始點x0∈D處的Jacobian矩陣J(x0)為行滿秩的條件下研究了(3)式的收斂性. 那么, 對于n≤m情況下的奇異問題, 在J(x0)對應為列滿秩的條件下是否有相關的結論呢?在研究方法上與文獻[7]又有何異同?由于列滿秩的J(x0)與行滿秩的J(x0)所對應的Moore-Penrose逆矩陣的性質有很大差異, 所以要想得到相關的結果就必須在方法上另找出路. 作者將重新定義Lipschitz條件, 在DF(x*),DF(x0)為列滿秩,DF(x)DF(x*)?及DF(x)DF(x0)?滿足新定義的Lipschitz條件下, 求解奇異非線性方程組(1)的牛頓迭代格式(3)的收斂判據, 并得出了(3)式的局部收斂性、半局部收斂性和收斂半徑的估計.

1 預備知識

設A∈Rm×n, 則A?稱為A的Moore-Penrose逆, 若下列4個等式成立:

AA?A=A,A?AA?=A?, (AA?)T=AA?, (A?A)T=A?A.

令kerA和ImA表示A的核與象,∏E表示Rn在子空間E?Rn上的正交投影,E⊥表示E在Rn上的正交補空間. 則有

A?A=∏(ker A)⊥,AA?=∏Im A.

(4)

當A為列滿秩時，有

A?A=IRn,

(5)

更多關于Moore-Penrose逆的結果可參見文獻[12].

定義1 設常數L>0, 實數r>0,x*∈Rn且DF(x*)為列滿秩，則稱DF(x)DF(x*)?在B(x*,r)中滿足關于L的中心Lipschitz條件, 若

‖(DF(x)-DF(x*))DF(x*)?‖≤L‖x-x*‖, ?x∈B(x*,r).

(6)

證明 由(6)式可以得到

‖(DF(x)-DF(x*))DF(x*)?‖≤L‖x-x*‖<1,

由Banach引理得到IRm-(DF(x*)-DF(x))DF(x*)?可逆, 注意到

IRm-DF(x*)DF(x*)?=∏(Im DF(x*))⊥，

所以

IRm-(DF(x*)-DF(x))DF(x*)?=∏(Im DF(x*))⊥+DF(x)DF(x*)?.

因此∏(Im DF(x*))⊥+DF(x)DF(x*)?可逆,根據(5)式，

DF(x*)?DF(x*)=IRn,

及

DF(x)=(∏(Im DF(x*))⊥+DF(x)DF(x*)?)DF(x*),

又因為DF(x*)為列滿秩, 從而對任意一點x∈B(x*,r),DF(x)為列滿秩.

引理2[12]設A∈Rm×n,rank(A+E)=rank(A)且‖A?‖2‖E‖2<1,則

(7)

2 牛頓法的局部收斂性

‖DF(x′)-DF(x″)‖<ε,

(8)

當然對?x∈B(x*,δ)，也有

‖DF(x)-DF(x*)‖<ε.

rank(DF(x))=rank(DF(x*)).

rank(A+E(x))=rank(A),

并且有

(9)

所以根據引理2可得

(10)

現任取x0∈B(x*,r), 假設由格式(3)產生的點xk∈B(x*,r), 并且根據DF(xk)?DF(xk)=IRn及Banach空間微分中值定理, 不等式(10)及DF(x)在B(x*,r)中的一致連續性可以得到

‖xk+1-x*‖=‖xk-x*-DF(xk)?F(xk)‖=

‖xk-x*-DF(xk)?F(xk)+DF(xk)?F(x*)‖=

‖xk-x*-DF(xk)?(F(xk)-F(x*))‖=

‖DF(xk)?DF(xk)(xk-x*)-DF(xk)?(F(xk)-F(x*))‖≤

‖DF(xk)?‖‖DF(xk)(xk-x*)-(F(xk)-F(x*))‖≤

3 牛頓法的半局部收斂性

‖(DF(x′)?-DF(x″)?)F(x″)‖≤α‖x′-x″‖,α<1,

(11)

(12)

ε0‖DF(x)?‖+α≤ε0N+α∶=M<1.

(13)

‖DF(x′)-DF(x″)‖<ε0.

(14)

(i) 對所有k=0,1,…, 下列兩式成立:

(15)

(16)

(i)的證明. 由定理2的假設知, 當k=0時,

結論成立; 設j=1,…,k-1時結論成立, 即有

(17)

由(17)得

由格式(3)得

xk+1-xk=-DF(xk)?F(xk)=xk-xk-1-DF(xk)?F(xk)+DF(xk-1)?F(xk-1).

由于DF(xk-1)?DF(xk-1) =IRn, 故

xk+1-xk=DF(xk-1)?DF(xk-1)(xk-xk-1)-DF(xk)?F(xk)+DF(xk-1)?F(xk-1)=

-DF(xk-1)?(F(xk)-F(xk-1)-DF(xk-1)(xk-xk-1))+(DF(xk-1)?-DF(xk)?)F(xk).

所以

‖xk+1-xk‖≤‖-DF(xk-1)?(F(xk)-F(xk-1)-DF(xk-1)(xk-xk-1))‖+

‖(DF(xk-1)?-DF(xk)?)F(xk)‖≤

‖(DF(xk-1)?-DF(xk)?)F(xk)‖.

由(16), (14)和(11)得

‖xk+1-xk‖≤‖DF(xk-1)?‖ε0+α‖xk-xk-1‖.

再由(13)和(17)式得到

(18)

這樣就根據數學歸納法證明了(15)式，從而證明了(i)的結論.

(ii)的證明.當m≥n時, 由(15)式可得

‖xm+1-xn‖≤‖xm+1-xm‖+‖xm-xm-1‖+…+‖xn+1-xn‖<

(19)

因為DF(x∞)?為列滿秩, 從而F(x∞)=0.

(iii)的證明. 由(19)式得

(20)

定理2證畢.

4 數值例子

下面給出一個相關的數值例子：

(21)

方程F(x)=0的精確解是x*=(1,1,0)T, 相應的Jacobian矩陣是

且J(x*)為列滿秩矩陣. 數值試驗結果參見表1和表2.

表1 以x0=(0.3,0.4,0.25)T為初值的數值結果Tab.1 The numerical results with initial value of x0=(0.3,0.4,0.25)T

表2 以x0=(1.4,1.5,-0.2)T為初值的數值結果Tab.2 The numerical results with initial value of x0=(1.4,1.5,-0.2)T

從表1可以看出實驗數值穩定并逐漸趨向于方程組的解，并且從表2可知，如果初值選取恰當數值，收斂速度也較快. 另外, 從定理1和定理2的證明中可以看到, 若再有DF(x)關于某一常數滿足Lipschitz條件, (11)式的條件再稍加強一些, 則可以得到格式(3)的更高階的收斂性.

[1] 賀婷婷，馬飛遙.兩個非線性偏微分方程強解的持續性質[J]．鄭州大學學報：理學版，2015，47(1)：14-23．

[3] Dedieu J P．Estimations for the separation number of a polynomial system[J]．J Symbolic Comput，1997，24(6)：683-693．

[4] Decker D W，Keller H B, Kelley C T．Convergence rates for Newton’s method at singular points[J]．SIAM J Numer Anal，1983，20(2)：296-314．

[5] Griewank A．On solving nonlinear equations with simple singularities or nearly singular solutions[J]．Siam Rev，1985，27(4)：537-563．

[6] Allgower E L，B?hmer K．Resolving singular nonlinear equations[J]．Rocky Mount J Math，1988，18(2)：225-268．

[7] 吳國楨，王金華．關于奇異非線性方程組的Newton法的收斂性[J]．浙江大學學報：理學版，2008，35(1)：27-31．

[8] Kantorovich L V，Akilov G P．Functional Analysis[M]．Oxford: Pergamon Press，1982：536-544．

[9] Smale S．Newton’s method estimates from data at one point[M]//Ewing R E，Gross K I，Martin C F．The Merging of Disciplines: New Directions in Pure, Applied and Computational Mathematics. New York: Springer，1986：185-196．

[10]Traub J F，Wózniakowski H．Convergence and complexity of Newton iteration for operator equations[J]．J Assoc Comput Math，1979，26(2)：250-258．

[11]王興華．Newton 方法的收斂性[J]．科學通報： 數理化專輯，1980，25(1)：36-37．

[12]Wang Guorong，Wei Yimin，Qiao Sanzheng．Generalized Inverses: Theory and Computations[M]．Beijing: Science Press，2004：5-7．

(責任編輯：孔 薇)

Convergence Property of Newton’s Method for Solving a Class of Singular Nonlinear Equations

YANG Jia-ling， CAO De-xin

(CollegeofSciences,ChinaUniversityofMiningandTechnology,Xuzhou221116,China)

Moore-Penrose inverse was used to construct Newton’s method for solving a class of singular nonlinear equations. The local and semilocal convergence were established, and the radius of convergence ball was also obtained. The validity of the algorithm was indicated by a numerical example.

singular nonlinear equations； Newton’s method； Moore-Penrose inverse； semilocal convergence

2015-06-25

國家自然科學基金資助項目，編號70901073；中央高?；究蒲袠I務費專項資金資助項目，編號JGK101676.

楊家嶺(1988-)，男，安徽六安人，碩士研究生，主要從事方程數值解及數值優化研究，E-mail: aa603781849@163.com；通訊作者：曹德欣(1962-)，男，河北石家莊人，教授，博士生導師，主要從事方程數值解、數值優化、區間算法及智能算法研究.

楊家嶺，曹德欣.關于解一類奇異非線性方程組的牛頓法的收斂性[J].鄭州大學學報：理學版，2015,47(3)：1-6.

O241

A

1671-6841(2015)03-0001-06

10.3969/j.issn.1671-6841.2015.03.001