仿射反变条件下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．