仿射反變條件下Newton迭代法的半局部收斂性＊

謝尚宜， 徐秀斌

(浙江師范大學數理與信息工程學院，浙江金華 321004)

0 引言

令X和Y是歐氏空間或一般的Banach空間，D是X的一個開凸子集，設F:D?X→Y是一個Fréchet可導的非線性算子，考慮如下一般的非線性方程:

求解非線性方程(1)的近似解是一個重要的問題，因為大量的不同類型的實際問題都可歸結為對非線性方程的求解，例如微分方程、邊界值問題、積分方程等．目前，Newton法是求解非線性方程(1)的最有效的方法之一，其迭代格式定義為(初始點x0給定)

關于Newton法半局部收斂性的最重要結果是Newton-Kantorovich定理［1］，它是Kantorovich在1948年應用Banach壓縮映射原理得到的，該定理在理論和應用上都相當重要，也是解方程算法現代研究的起點．之后，有大量的文獻對該定理的條件“F"有界”進行了改進弱化，例如，Ortega等［2］在1968年把它弱化成F'滿足Lipschitz條件

進一步，Rokne［3］在1972 年將 Lipschitz條件推廣為 H?lder條件

最近，Ezquerro和Hernández［4］研究了在如下更弱的條件下的收斂行為:

其中ω:R+→R+是連續非遞減的函數．易知，當ω(z)=Lz時，條件(5)即為Lipschitz條件(式(3));當ω(z)=Kzp時，條件(5)即為 H?lder條件(式(4))．

此外，Newton-Mysovskikh定理［5］是另一個關于Newton法(式(2))半局部收斂性的重要結果．同樣，對于該定理亦有很多改進結果，詳見文獻［2］及其所列相關文獻．

需要特別注意的是，Newton法(式(2))所產生的序列{xn}在仿射變換條件下具有不變性．這一重要性質由Deuflhard和Heindl［6］在1979年首先給出明確的論述．之后，Deuflhard［7］進一步完善了Newton法的仿射不變性理論．根據Deuflhard的理論，有2個特別重要的仿射變換性，分別稱為仿射共變性(affine covariance)和仿射反變性(affine contravariance)．上述的Lipschitz條件和H?lder條件均有相應的仿射共變和仿射反變形式．例如:條件‖F'(x0)-1［F'(y)-F'(x)］‖≤L‖y-x‖(x，y∈D)稱為仿射共變 Lipschitz條件［6］;條件‖(F'(y)-F'(x))(y-x)‖≤L‖F'(x)(y-x)‖2(x，y ∈D)稱為仿射反變Lipschitz條件，該條件首先由Hohmann在文獻［8］中用于Newton法的收斂性研究，爾后由Deuflhard在文獻［7］中用于其他Newton型法的研究．

大多數文獻是在假設滿足仿射共變條件下研究Newton法(式(2))的收斂性，而對仿射反變條件下的研究較少．本文將結合文獻［4，7］的思想，引入一個新的更一般的仿射反變條件，研究Newton法(式(2))的收斂性，所得結果推廣了Hohmann在文獻［8］中的相應結果．

1 一些概念

定義1 設F:D?X→Y，A是X到Y上的任一線性算子，對于任意的x，b∈D，稱 F(x)=Ax+b為X上的仿射映射．

考慮非線性方程的仿射變換G(y)=AF(By)=0，x=By，有

定義2 若固定F的原空間，即令B=I，則仿射變換G(x)=AF(x)=0稱為仿射共變變換;若固定F的像空間，即令A=I，則稱G(y)=F(By)=0(其中x=By)為仿射反變變換．

為說明仿射變換的意義，考慮非線性方程的仿射共變變換G(y)=AF(By)=AF(x)=0，x=By［7］．盡管上述仿射變換并沒有改變方程組的解，但是對于某些復雜的非線性方程組，以牛頓方法為例，對算子F作如下仿射共變變換:G(y)=AF(By)=AF(x)=0，y=x．其中:A∈L(Rn)為非奇異矩陣;B=I．則

這說明牛頓迭代序列{xk}在仿射變換下是不變量，因而收斂性亦不變．但仿射變換前后所涉及的一些范數卻不同，如在Newton-Kantorovich收斂定理中用到的‖［F'(x0)］-1‖與‖［AF'(x0)］-1‖，這就可能使收斂定理的收斂域擴大，說明了仿射變換在求解非線性方程組中具有重要的意義．下面給出本文要討論的仿射反變的H?lder條件和仿射反變的ω-條件．

定義3 設F:D?Rn→Rn在開凸集D上是連續可微的，若存在常數L≥0及p∈(0，1］，使得

對所有x，y∈D成立，則稱 F'在D上滿足仿射反變H?lder條件．

定義4 設ω:R+→R+是一個連續非遞減的函數，且滿足ω(0)≥0，如果

并假設存在一個非遞減函數 h∈C［0，1］，使得 ω(tz)≤h(t)ω(z)，?t∈［0，1］，z∈［0，+∞］，則稱 F'在D上滿足仿射反變ω-條件．

注1 令G(y)=F(By)，x=By，B為可逆線性算子，則式(6)和式(7)的左右兩邊是獨立于B的．由于所以式(6)和式(7)具有仿射反變不變性．

引理1［2］(中值定理) 若映射F:D?Rn→Rm在開凸集D0上G可導，F'(x)在D0半連續，則對任何

2 在仿射反變條件下的Newton法的半局部收斂性

定理1 設F:D?Rn→Rn在開凸集D上是連續可微的，假設F'(x)對任意x∈D均可逆，并設F'滿足仿射反變ω-條件(式(7))．定義開水平集

根據仿射反變的ω-條件可得

因此

定理1中的仿射反變ω-條件可以特殊化到H?lder類條件與Lipschitz類條件，即:1+pp

下面可得到仿射反變H?lder條件下的Newton法的半局部收斂性定理．

定理2 設F:D?Rn→Rn在開凸集D上是連續可微的，假設F'(x)對任意x∈D均可逆，并設F'滿足仿射反變H?lder條件(式(6))．定義開水平集

證明 令 ω(z)=Lzp，h(t)=tp，則

推論1其實就是文獻［8］中的一個重要定理，因此，本文是對該定理的推廣，更具有一般性．

［1］Kantorvich L V，Akilov G P．Functional Analysis［M］．Oxford:Pergamon Press，1982．

［2］Ortega J M，Rheinboldt W C．Iterative Solution of Nonlinear Equations in Several Variables［M］．New York:Academic Press，1970．

［3］Rokne J．Newton's Method under Mild Differentiability Conditions with Error Analysis［J］．Numer Math，1972，18(5):401-412．

［4］Ezquerro J A，Hernández M A．Generalized differentiability conditions for Newton's method［J］．IMA Journal of Numerical Analysis，2002，22(2):187-205．

［5］Mysovskikh I．On Convergence of Newton's Method(Russian)［J］．Trudy Mat Inst Steklov，1949，28(1):145-147．

［6］Deuflhard P，Heindl G．Affine Invariant Convergence Theorems for Newton's Method and Extensions to Related Methods［J］．SIAM J Numer Anal，1979，16(1):1-10．

［7］Deuflhard P．Newton Methods for Nonlinear Problems:Affine Invariance and Adaptive Algorithms［M］．Berlin:Springer-Verlag，2004．

［8］Hohmann A．Inexact Gauss Newton Methods for Parameter Dependent Nolinear Problems［D］．Berlin:Freie Universit?t，1994．