非線性方程組數(shù)值解法
——Newton法遇奇異點的處理

楊家?guī)X

(中國礦業(yè)大學(xué) 理學(xué)院,江蘇 徐州 221008)

設(shè)映像F：D?Rn→Rn,非線性方程組F(x)=0的數(shù)值解法——Newton法，xk+1=xk-[F'(xk)]-1F(xk),k=0,1,…中，當(dāng)F'(xk)奇異或病態(tài)時迭代就不能進行，以下給出三種避免F'(xk)奇異的方法.

1 經(jīng)典的引入阻尼因子λk法與KaHTOPOBHY定理

1.1 引入阻尼因子λk

引入?yún)?shù)λk使F'(xk)+λkI非病態(tài)，此時得到迭代序列

xk+1=xk-[F'(xk)+λkI]-1F(xk),k=0,1,…

(1)

λk稱阻尼因子，只要選取λk足夠大使得F' (xk)+λkI成為對角占優(yōu)就可以消除奇異性，且關(guān)于(1)的局部收斂定理如下.

定理1 設(shè)x*是非線性方程組F(x)=0的解：F:D?Rn→Rn在x*的鄰域S0?D上的連續(xù)可微且F' (x*)非奇異，又設(shè)μ1,…，μn為矩陣F' (x*)的特征值，令

若不存在Reμi>0或Reμi<0的特征值可分取β=+∞或η=+∞，則對任意λ∈(-β,η)，由(1)迭代產(chǎn)生的序列

{xk}?S0,

且收斂于x*.

證明 若對固定的λ∈(-β,η)，在S0上定義

A(x)=F'(x)+λI,

由于F'(x)在S0上連續(xù)，故A(x)在x*處連續(xù)，下面證明A(x*)非奇異，假定A(x*)奇異，則必存在μj使得μj+λ=0,λ≠0,若λ>0，因λ∈(-β,η)故有

這是不可能的，若λ<0，則μj>0，故有

這也不可能，這矛盾說明A(x*)非奇異,于是映像

G(x)=x-[F'(x)+λI]-1F(x)

在球S=S(x*,δ)?S0中適定且在x*處可導(dǎo)，并有

G'(x*)=I-[F'(x*)+λI]-1F'(x*),

即

這表明λ∈(-β,η)時，ρ(G'(x*))<1，從而只要(1)中λk∈(-β,η),則它產(chǎn)生的序列{xk}是收斂于x*的[1].

此定理的不足之處就是它需要事先知道方程組的解x*才能求出λ的范圍,但在實際問題中x*大都是未知的.

1.2 依據(jù)KaHTOPOBHY定理

定理2(KaHTOPOBHY) 假設(shè)F:D?Rn→Rn在凸集D0?D上F可導(dǎo)，并且對任何x,y∈D0，有常數(shù)r>0使

‖F(xiàn)'(x)-F'(y)‖≤r‖x-y‖,

2 Newton法與簡化Newton法相結(jié)合的方法

Newton迭代程序

xk+1=xk-[F'(xk)]-1F(xk)，k=0,1,2,…

(2)

若出現(xiàn)F'(xk)為奇異矩陣，則用F'(xk-1)代替F'(xk)，即在此時用一步簡化Newton法：xk+1=xk-[F'(xk-1)]-1F(xk).替代(2)式,還若F'(xk+1)再奇異繼續(xù)用F'(xk-1)代替F'(xk+1)，即用了兩步簡化Newton法，往后以此類推，若F'(xk+1)為非奇異矩陣，則再回到Newton迭代程序(2).

2.1 算法

步1 給出初始近似值x0及計算精度ε1和ε2；

步2 假定已經(jīng)進行了k次迭代，已求出xk及F(xk)，計算

F'(xk)=Ak,并記bk=F(xk);

步3 若|F'(xk)|=0，則F'(xk)→F'(xk-1)，轉(zhuǎn)4，否則直接轉(zhuǎn)4；

步4 解線性方程組AkΔxk=-bk得Δxk;

步5 求xk+1=xk+Δxk及F(xk+1);

步6 若‖ΔxK‖≤ε1‖xk‖或‖F(xiàn)(xk+1)‖≤ε2，則置x*=xk+1打印x*，‖F(xiàn)(x*)‖及‖Δxk‖，轉(zhuǎn)步7，否則k+1→k,xk+1→xk,F(xk+1)→F(xk)轉(zhuǎn)步2;

步7 結(jié)束.

2.2 收斂性證明

整個程序過程是：Newton法+若干步簡化Newton法(奇異處) +Newton法+若干步簡化Newton法(奇異處)+…，而Newton法是超線性收斂到方程組的解x*的[3],簡化Newton法是線性收斂到x*的[2]，所以整體得到的迭代序列是收斂到x*的.

其中Newton法的收斂域問題可詳見[4].這種避免奇異性的方法也可以用在其他Newton型迭代中，簡便易行.

參考文獻：

[1]李慶楊,莫孜聰,補力群.非線性方程組的數(shù)值解法[M].北京:科學(xué)出版社,1992.

[2]馮果忱.非線性方程組迭代解法[M].上海:上海科學(xué)技術(shù)出版社,1989.

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

[4]王興華，關(guān)于牛頓法的收斂域[J].科學(xué)通報數(shù)理化專輯，1980(1).