王海波， 秦 梅

（上海理工大學(xué)理學(xué)院，上海 200093）

牛頓法在新的仿射逆變條件下的半局部收斂性分析

王海波， 秦 梅

（上海理工大學(xué)理學(xué)院，上海 200093）

非線性方程及非線性方程組的數(shù)值求解一直是計(jì)算數(shù)學(xué)所關(guān)注的問題，公認(rèn)的經(jīng)典算法是牛頓法，對(duì)于它的局部收斂性已有很多研究.在經(jīng)典牛頓法的半局部收斂Kantorovich定理的基礎(chǔ)上引入仿射逆變性，研究了牛頓法在仿射逆變Lipschitz條件和仿射逆變Holder條件下的半局部收斂性.簡(jiǎn)化了牛頓法的收斂行為，得到了相應(yīng)的半局部收斂性定理及誤差估計(jì).推廣并改進(jìn)了相關(guān)文獻(xiàn)的結(jié)果，表明了該方法的有效性.

牛頓法；仿射逆變Lipschitz條件；仿射逆變Holder條件；半局部收斂性

考慮非線性方程組其中F：Rn→Rn是連續(xù)可微函數(shù).求解該非線性方程組的近似解是一個(gè)很重要的問題，因?yàn)榇罅康牟煌愋偷膶?shí)際問題都可以歸結(jié)為非線性方程的求解，如常微分或偏微分方程邊值問題、積分方程、極小化問題等［1-7］.為此，研究非線性方程組的求解算法具有重要的實(shí)際意義.

目前，牛頓法是求解非線性方程組（1）的最有效方法之一.其迭代格式為迭代法的收斂性已經(jīng)成為研究的一個(gè)核心問題.一般情況下，收斂性分析有以下三種類型［2］：局部收斂性、半局部收斂性和全局收斂性.本文主要研究牛頓法在仿射逆變條件下的半局部收斂性.半局部收斂性是在不知方程解x*存在的情況下，根據(jù)F在某一初始點(diǎn)x0的局部條件來研究有關(guān)的收斂性質(zhì).

關(guān)于半局部收斂性的最著名的結(jié)果是Newton-Kantorovich定理［5］，該定理在理論和應(yīng)用上相當(dāng)重要，也是解方程算法現(xiàn)代研究的起點(diǎn).很多研究學(xué)者對(duì)Kantorovich定理?xiàng)l件進(jìn)行改進(jìn)，得到了不少好的半局部收斂性結(jié)果.Deuflhard［8-9］首先將仿射不變性引入到牛頓法中，提出牛頓法的仿射不變性理論，而后由Hohmann得到進(jìn)一步拓展.Nashed等［10］研究了阻尼牛頓法在仿射逆變條件下的局部收斂性.白中治［11］給出了不精確牛頓法在仿射協(xié)變條件下的不精確牛頓法的半局部收斂性.徐秀斌［12］研究了在弱Lipschitz條件下Halley方法的半局部收斂性.

大多數(shù)文獻(xiàn)是在假設(shè)滿足仿射協(xié)變條件下研究牛頓法的收斂性，而對(duì)仿射逆變條件下的研究較少.本文將結(jié)合文獻(xiàn)［9］的思想，主要研究加入新的仿射逆變性后的牛頓法的半局部收斂性，并在更弱的仿射逆變條件下牛頓法的半局部收斂性得到了更一般的結(jié)果.

1 預(yù)備知識(shí)

考慮非線性方程組F（x）=0.其中F：D?X→Y的連續(xù)可微映射，X和Y為Banach空間.普通牛頓法對(duì)F（x）=0進(jìn)行求解時(shí)，實(shí)際是求解線性方程組

求得上述方程組的精確解Δxk后，由xk+1=xk+ Δxk進(jìn)行校正.顯然，普通牛頓法使非線性方程組F（x）=0的求解問題變成線性方程組（3）來解決.

上面的線性方程組（3）的可解性的必要條件是：對(duì)所有的x∈D，雅克比矩陣F′（x）是可逆的.在經(jīng)典的收斂定理中通常要求F′（x）-1存在且有界，即

從實(shí)際計(jì)算的角度看，除了一些簡(jiǎn)單的例子外，理論上的量β是不容易得到的.然而，

是可取的.

研究上面的牛頓迭代的收斂性質(zhì)，F(xiàn)（x）的二次導(dǎo)數(shù)信息是必要的.有大量的文獻(xiàn)對(duì)式（4）進(jìn)行弱化，Kelley［3］將其弱化為F＇的Lipschitz連續(xù)：存在一個(gè)常數(shù)L＞0，使得

經(jīng)典的收斂性定理的假設(shè)條件都是式（4）、（5）、（6）的組合.現(xiàn)給出2個(gè)重要的收斂定理.

普通牛頓法缺乏仿射不變性.Hohmann在牛頓法中加入仿射逆變性，收到了很好的效果.相對(duì)于經(jīng)典的牛頓法，利用仿射逆變性令收斂定理的證明更加簡(jiǎn)潔.為此，給出仿射映射的定義.

定義1 設(shè)F∈D?X→Y的映射，A是X到Y(jié)上的任意線性算子，對(duì)于任意的x，b∈D，稱F（x）=A x+b為X上的仿射映射.

設(shè)A，B∈Rn×n是任意非奇異的n階矩陣，考慮非線性系統(tǒng)的仿射變換

則將牛頓法應(yīng)用到G（y）上可得

由于G′（yk）=A F′（xk）B和初始點(diǎn)y0=B-1x0，故對(duì)任意的k∈N，有xk=B yk.

很顯然，他們僅僅是通過B的一個(gè)變換得到的.因此，有牛頓法產(chǎn)生的序列｛xk｝在仿射變換條件下具有不變性.

定義2 若固定F的像空間，即令A(yù)=I，則稱G（y）=F（B y）=0，x=B y，B∈GL（n）為仿射逆變性.

對(duì)于這個(gè)問題，普通牛頓法推不出關(guān)于｛yk｝的迭代序列，但是可以導(dǎo)出關(guān)于殘差｛F（xk）｝的序列，這與B的選擇無關(guān).另外，在經(jīng)典的收斂定理中，F(xiàn)′（x）的Lipschitz連續(xù)是必要的.加入仿射逆變性后，將Lipschitz條件和‖F(xiàn)′（x）-1‖≤M結(jié)合得到仿射逆變Lipschitz條件

考慮到Lipschitz條件是Holder條件的特例，將Holder條件與‖F(xiàn)′（x）-1‖≤M結(jié)合得到仿射逆變Holder條件

顯然，這兩個(gè)條件滿足仿射逆變性，因?yàn)閷?duì)任意可逆線性算子B，若對(duì)非線性方程（1）作仿射逆變變換G（y）=F（By）=0，則

下面給出仿射逆變Lipschitz條件和仿射逆變Holder條件的定義.

定義3 （仿射逆變Lipschitz條件）設(shè)F：D?X→Y連續(xù)可微，對(duì)于任意的x，y∈D，如果對(duì)任意的v∈D有

則稱為F′在D上滿足仿射逆變Lipschitz條件.

定義4 （仿射逆變Holder條件）設(shè)F：D?X→Y連續(xù)可微，如果對(duì)于任意的v∈D有

則稱為F′在D上滿足仿射逆變Holder條件.

在Kantorovich定理的基礎(chǔ)上給出仿射Lipschitz條件半局部收斂性分析，并由此推出更弱的仿射逆變Holder條件下的半局部收斂性分析，后者是前者的推廣.得到了牛頓法在仿射逆變條件下的更一般的結(jié)果.

2 牛頓法在新的仿射逆變條件下的半局部收斂性分析

討論牛頓法的半局部收斂性，最著名的定理是康托洛維奇定理.

引理3 （康托洛維奇定理［5］）設(shè)F：D?Rn→Rn及初始近似x0滿足下列條件：

引理4 （中值定理［5］）若映射F：D?Rn→Rn在開凸集D上可導(dǎo)，F(xiàn)′（x）在D上連續(xù)，則對(duì)任何x，y∈D，有

康托洛維奇定理有很大的理論價(jià)值，一方面是定理的收斂條件，另一方面就是定理的證明方法，為研究仿射逆變條件下牛頓法的半局部收斂性做了指導(dǎo).在此基礎(chǔ)上，在牛頓法中引入仿射逆變性，先研究牛頓法在仿射逆變Lipschitz條件下半局部收斂性.

定理1 （仿射逆變Lipschitz條件下半局部收斂性定理）設(shè)F：D→Rn是在D上的連續(xù)可微映射，D?Rn是一個(gè)開的凸集.F′（x）對(duì)任意x∈D均可逆，并設(shè)F′滿足仿射逆變Lipschitz條件成立，即

接下來在定理1的基礎(chǔ)上研究比仿射逆變Lipschitz條件更弱條件下（仿射逆變Holder條件）的牛頓法的半局部收斂性.

定理2 （仿射逆變Holder條件下半局部收斂性定理） 設(shè)F：D→Rn是在D上的連續(xù)可微映射，D?Rn是一個(gè)開的凸集.F′（x）對(duì)任意x∈D均可逆，并設(shè)F′滿足仿射逆變Holder條件成立，即p+1

因此定理2是定理1的推廣.需要注意的是，當(dāng)水平集確定時(shí)，只要取其中任意一點(diǎn)作為初始迭代點(diǎn)便可以保證所產(chǎn)生的序列仍在水平集內(nèi)且是收斂的.從而此結(jié)果推廣并改進(jìn)了經(jīng)典的半局部收斂性定理.

3 結(jié) 論

主要研究了仿射逆變Lipschitz條件下牛頓法的半局部收斂性，并在此基礎(chǔ)上給出了仿射逆變HolderF條件下牛頓法的半局部收斂性定理，得到了更一般的結(jié)果.由此可以得出結(jié)論：定理2是定理1的推廣.此結(jié)果推廣并改進(jìn)了經(jīng)典的半局部收斂性定理.

而對(duì)于牛頓法的高階推廣迭代算法，如Halley法和Chebyshev法是否能夠建立仿射逆變條件下的收斂性，這一點(diǎn)目前還沒有人做深入的探討.一個(gè)關(guān)鍵的切入點(diǎn)是需要論證這些高階算法是否具有仿射逆變性，如果滿足該不變性，那么便可能可以建立相應(yīng)的仿射逆變收斂結(jié)果.

［1］ Deuflhard P.Newton methods for nonlinear problems ［M］.北京：科學(xué)出版社，2006.

［2］ 袁亞湘.最優(yōu)化理論與算法［M］.北京：科學(xué)出版社，1997.

［3］ Kelley C T.Solving nonlinear equations with Newton method［M］.Philadelphia：Society for Industrial& Applied Mathematics，2003.

［4］ Deuflhard P.Affine invariant adaptive Newton codes for discretized PDEs［J］.2002（10）：1-27.

［5］ 黃象鼎，等.非線性數(shù)值分析［M］.武漢：武漢大學(xué)出版社，2010.

［6］ 于淼，高巖.擬可微方程組牛頓法的二次收斂性［J］.上海理工大學(xué)學(xué)報(bào)，2009，31（4）：354-358.

［7］ 劉晶，高巖.求解一類無限維非光滑算子方程的光滑化牛頓法［J］.上海理工大學(xué)學(xué)報(bào)，2008，30（2）：167-170.

［8］ Deuflhard P，Heindl G.Affine invariant convergence theorems for Newton’s method and extensions to related methods［J］.SIAM Numer Anal，1979，16（1）：1-10.

［9］ Deuflhard P.Newton methods for nonlinear problems：affine invariance and adaptive algorithms［M］.Berlin：Springer-Verlag，2004.

［10］ Nashed M Z，Chen X.On the semilocal convergence of damped Newton method［J］.Applied Mathematics and Computation，2012（219）：2808-2824.

［11］ 白中治.不精確Newton法與Broyden法的仿射不變性［J］.電子科技大學(xué)學(xué)報(bào)，1994，23（5）：535-537.

［12］ Xu X B，Ling Y H.Semi-local convergence for Halley’s method under weak Lipschitz condition［J］. Applied Mathematics and Computation，2009，215（8）：3057-3067.

（編輯：董 偉）

Semi-local Convergence for Newton Method under New Affine Contravariant Conditions

WANGHai-bo， QINMei
（College of Science，University of Shanghai for Science and Technology，Shanghai 200093，China）

Numerical solutions for nonlinear equations and systems of nonlinear equations are always appealing greatly to people.There are many papers discussing the local convergence of Newton method，a universally acknowledged classical algorithm.In the paper，on the basis of the Kantorovich theorem about the classic semi-local convergence of Newton method，affine contravariant conditions were introduced and the semi-local convergence of Newton method under affine contravariant Lipschitz conditions and affine contravariant Holder conditions was analysed. The convergence behavior of Newton method was simplified.The semi-local convergence theorems were presented and the estimations of the iterative residual were obtained.The results extend and improve the results in the related paper，which show that the method is efficient.

Newton method；affine contravariant Lipschitz conditions；affine contravariant Holder conditions；semi-local convergence

O 241文獻(xiàn)標(biāo)示碼：A

1007-6735（2014）05-0429-05

10.13255／j.cnki.jusst.2014.05.004

2013-09-04

王海波（1987-），男，碩士研究生.研究方向：計(jì)算數(shù)學(xué).E-mail：nunywanghaibo＠126.com

秦 梅（1975-），女，副教授.研究方向：計(jì)算數(shù)學(xué).E-mail：qinmay2012＠sina.com