預(yù)條件下含參數(shù)的JOR迭代法斂散性分析

王慧勤，雷 剛

（寶雞文理學(xué)院數(shù)學(xué)系，陜西寶雞721013）

預(yù)條件下含參數(shù)的JOR迭代法斂散性分析

王慧勤，雷 剛

（寶雞文理學(xué)院數(shù)學(xué)系，陜西寶雞721013）

對于JOR迭代法求解線性方程組Ax＝b，運(yùn)用了預(yù)條件加速JOR迭代法的收斂性，在預(yù)條件后引入?yún)?shù)α，給出更一般的預(yù)條件下含參數(shù)形式的JOR迭代方法.證明了這類方法能夠加速JOR迭代法的收斂性，找到了參數(shù)的最佳取值，并且用數(shù)值算例加以驗(yàn)證.

JOR迭代法；收斂性；預(yù)條件；譜半徑

在有限元分析以及差分方程的數(shù)值求解過程中，大型線性方程組的求解幾乎決定了整個數(shù)值求解的快慢，隨著計(jì)算機(jī)的快速發(fā)展與應(yīng)用，對大型線性方程組的求解大都采用迭代法求解，那么對迭代法是否收斂以及迭代法的收斂速度的研究就成為近年來關(guān)注的熱點(diǎn)［1－3］.基本的迭代法有Jacobi，Gauss－Seidel迭代法，在此基礎(chǔ)上發(fā)展了JOR，SOR，AOR等迭代法，各種迭代法互有優(yōu)缺點(diǎn)，為改變迭代法的收斂性或加速迭代法的收斂速度，預(yù)條件方法已經(jīng)成為一類基本的改善收斂性的方法.

1 預(yù)備知識

運(yùn)用預(yù)條件方法解大型線性方程組Ax＝b（其中A＝（aij）n×n∈Rn×n；x，b∈Rn）就是引入一個非奇異矩陣［1］P∈Rn×n，使原方程變?yōu)?/p>

結(jié)合矩陣變換，為討論方便，假設(shè)A＝I－L－U為非奇異矩陣（當(dāng)A為奇異矩陣時，可通過矩陣變換為低階的非奇異矩陣），I是單位矩陣，－L和－U分別是由矩陣A的嚴(yán)格下三角部分和嚴(yán)格上三角部分組成的矩陣.雅可比超松弛法（簡稱JOR法）就是在Jacobi迭代法的基礎(chǔ)上引入?yún)?shù)ω，將Ax＝b的系數(shù)矩陣A分解為（當(dāng)ω＝1時即為Jacobi迭代法），相應(yīng)的迭代形式為

迭代矩陣為

在文獻(xiàn)［1］預(yù)條件P＝（I＋C）作用下，

其中：CL＝0；CU＝D1＋L1＋U1；C的矩陣形式為

a21，a31，…，an1分別是系數(shù)矩陣A對應(yīng)位置上的元素.那么預(yù)條件后JOR迭代法的迭代矩陣為

易知當(dāng)α＝1時，TJCα＝TJC，即為一般的預(yù)條件JOR方法.本文討論預(yù)條件對JOR迭代法收斂性的影響，并找到在能加速收斂性的條件下尋找參數(shù)α的最優(yōu)取值.

2 定義和引理

定義1［4］記n階實(shí)方陣A＝（aij）所組成的集合為Rn，n，記Rn，n的子集Zn，n為

當(dāng)矩陣A∈Zn，n，并且aii＞0（?i）成立時，稱矩陣A為L－矩陣.

定義2［5－6］如果矩陣A能表示為A＝sI－B，I為n階的單位矩陣，B≥0，當(dāng)s≥ρ（B）時，稱A為M－矩陣，特別當(dāng)s＞ρ（B）時，稱A為非奇異的M－矩陣；當(dāng)s＝ρ（B）時，稱A為奇異M－矩陣.其中ρ（B）為B的譜半徑.

定義3［5－6］設(shè)方陣A＝（aij）∈Rn×n，如果存在排列矩陣P，使得

其中：F和H是方陣，0是零矩陣.則稱A為可約矩陣；否則稱A為不可約矩陣.

引理1［4］（Perron－Frobenius定理） 如果矩陣A為n階非負(fù)方陣，那么就有：

（1）A有非負(fù)特征值等于其譜半徑ρ（A）；

（2）A有與ρ（A）相對應(yīng)的非負(fù)特征向量；

（3）A的任一元素增加時，ρ（A）不減.

引理2［6］設(shè)A為非負(fù)矩陣，則：

（1）若αx≤Ax對某一個非負(fù)向量x且x≠0成立，那么就有α≤ρ（A）.

（2）若Ax≤βx對某一個正向量x成立，那么就有ρ（A）≤β；如果A不可約且有0≠αx≤Ax≤βx，αx≠Ax，Ax≠βx對某一個非負(fù)向量x成立，則α＜ρ（A）＜β.

引理3［7］設(shè)矩陣A－1≥0，滿足A＝~M－~N＝M－N是弱正規(guī)的分裂.如果M－1≤~M－1，且N≥0那么就有ρ（~M－1~N）≤ρ（M－1N）.

3 結(jié)果與證明

JOR迭代法的收斂性通常用譜半徑是否小于1來判定，如果譜半徑小于1，那么迭代法就收斂，否則迭代法就發(fā)散.而且譜半徑越小，迭代法的收斂速度就越快.

定理1 對線性方程組Ax＝b，TJ和TJCα分別是由（3）和（5）式給出的JOR迭代法的迭代矩陣，如果矩陣A＝I－L－U是嚴(yán)格對角占優(yōu)的L－矩陣，滿足0＜ai1a1i≤1，i＝2，3，…，n，0＜ω≤1，那么當(dāng)0≤α≤時，就有：

（1）當(dāng)ρ（TJ）＞1時，ρ（TJCα）≥ρ（TJ）；

（2）當(dāng)ρ（TJ）＝1時，ρ（TJCα）＝ρ（TJ）；

（3）當(dāng)ρ（TJ）＜1時，ρ（TJCα）≤ρ（TJ）.

證明在含參數(shù)的分裂形式下，（I－αD1）是對角矩陣，結(jié)合當(dāng)0＜ai1a1i≤1，i＝2，3，…，n時，有可知（I－αD1）≥0，從而（I－αD1）－1≥0.

同理易知TJ也是一個不可約的非負(fù)矩陣，利用Perron－Frobenius定理知存在一個正向量x＝（x1，x2，…，xn）T，滿足TJx＝ρ（TJ）x，即

對（6）式兩邊同時左乘矩陣C，利用CL＝0可以得到ωCUx＝［（λ－1）C＋ωC）］x.結(jié)合矩陣比較定理，考慮

如果令r＝（I－αD1）－1（αD1＋C）x，由D1和C的取值以及（I－αD1）－1≥0可得r＞0.利用文獻(xiàn)［4］的結(jié)論可得：

定理2 對線性方程組Ax＝b，TJC和TJCα分別是由（4）和（5）式給出的JOR迭代法的迭代矩陣，如果矩陣A＝I－L－U是嚴(yán)格對角占優(yōu)的L－矩陣，滿足0＜ai1a1i≤1，i＝2，3，…，n，0＜ω≤1，那么當(dāng)1≤α≤，就有ρ（TJCα）≤ρ（TJC）≤ρ（TJ）＜1.

證明由其中MJC＝（I－D1），NJC＝（I－D1）－ωPA，利用定理1的證明有MJC＝（I－D1）－1≥0，從L和C的構(gòu)造可得LC≥0，結(jié)合0＜ω≤1，有

再比較MJCα和MJC，結(jié)合條件有（I－αD1）≤（I－D1），所以可得，按照引理有ρ（TJCα）≤ρ（TJC），綜合文獻(xiàn)［6，8］以及定理1中α＝1時的情形就有ρ（TJCα）≤ρ（TJC）≤ρ（TJ）＜1.定理3 對線性方程組Ax＝b，TJ和TJCα分別是由（3）式和（5）式給出的JOR迭代法的迭代矩陣，如果矩陣A＝I－L－U是嚴(yán)格對角占優(yōu)的L矩陣，且0＜ai1a1i≤1，i＝2，3，…，n，0＜ω≤1，當(dāng)αi滿足1≤那么當(dāng)α1＜α2時，就有：

（1）當(dāng)ρ（TJ）＜1時，ρ（TJCα2）≤ρ（TJCα1）；

（2）當(dāng)ρ（TJ）≥1時，ρ（TJCα2）≥ρ（TJCα1）.

證明由定理2的證明知，TJCα是非負(fù)矩陣，結(jié)合Perron－Frobenius定理可知其譜半徑是它的某個特征值，且有該特征值對應(yīng)的非負(fù)向量x＝（x1，x2，…，xn）T滿足TJCαx＝ρ（TJCα）x.那么當(dāng)αi滿足1≤且α1＜α2時，有（I－α1D1）≥（I－α2D1），結(jié)合其為對角矩陣，所以有（I－α1D1）－1≤（I－α2D1）－1.利用定理2考慮

也就是

當(dāng)ρ（TJ）＜1，且α1＜α2時，上述不等式右端小于零，從而ρ（TJCα2）≤ρ（TJCα1）；

當(dāng)ρ（TJ）≥1，α1＜α2時，考慮

所以，當(dāng)ρ（T）＝λ≥1時，上述不等式右端大于或等于零，即ρ（TJCα2）≥ρ（TJCα1）.

注從定理3的證明可以看出，當(dāng)線性方程組Ax＝b的JOR迭代法收斂時，隨著參數(shù)α的增大，ρ（TJCα）在減小，所以當(dāng)，這種預(yù)條件后含參數(shù)分裂形式的JOR迭代法的譜半徑達(dá)到最小.

4 數(shù)值例子

如果線性方程組Ax＝b的系數(shù)矩陣

那么通過計(jì)算可知，以A為線性方程組的系數(shù)矩陣，對不同的松弛因子ω，JOR迭代法在預(yù)條件前后的譜半徑比較如表1.

從表1可以看出，隨著松弛因子ω的增大，JOR迭代法的譜半徑逐漸減小.在預(yù)條件因子P＝（I＋C）的作用下，相應(yīng)的預(yù)條件后的JOR迭代法的譜半徑都能減小，從而可知預(yù)條件方法能加快JOR迭代法的收斂性.

在引入?yún)?shù)α改變預(yù)條件后JOR迭代法的分裂形式，當(dāng)取定一個確定的松弛因子ω時，隨著參數(shù)α的變化，可以發(fā)現(xiàn)改進(jìn)分裂形式后的JOR迭代法的收斂速度要優(yōu)于一般的預(yù)條件方法.

從表2可知，不論松弛因子ω＝0.6或者ω＝0.8，當(dāng)參數(shù)α＝1時，改進(jìn)分裂形式的JOR迭代法的譜半徑都等于一般預(yù)條件后的JOR迭代法的譜半徑，符合分裂的情況.隨著參數(shù)α的增大，新分裂形式下的迭代法的譜半徑都在減小，具體的取ω＝0.6，隨著參數(shù)α的一直增大，改進(jìn)分裂形式的JOR迭代法的譜半徑隨α的變化情況如圖1所示.

從圖1可以看出，隨著參數(shù)α的增大，譜半徑ρ（TJCα）逐漸減小，但是當(dāng)參數(shù)，譜半徑ρ（TJCα）突然增大，并且不再收斂，這符合定理3的結(jié)論.

5 結(jié)論

從理論證明和數(shù)值分析可以看出，不但預(yù)條件方法能夠加速JOR迭代法的收斂性，而且在預(yù)條件后引入?yún)?shù)改進(jìn)矩陣的分裂形式也能加速迭代法的收斂性，同時隨著參數(shù)取值的不同可以更好地加速JOR迭代法的收斂性.這些可以給在有限元等問題中涉及的大型線性方程組的迭代求解提供新的理論依據(jù).

［1］ JAE HEON YUN.Compaison results of the preconditioned AOR methods for L－matrices［J］.Applied Mathematics and Computation，2011，218：3399－3413.

［2］ QINGBING LIU，GUOLING CHEN，JING CAI.Convergence analysis of the preconditioned Gauss－Seidel method for H－matrices［J］.Computers and Mathematics with Applications，2008，56：2048－2053.

［3］ HIROSHI NIKI，KYOUJI HARADA，MUNENORI MORIMOTO，et al.The survey of preconditioners used for accelerating the rate of convergence in the Gauss－Seidel method［J］.Journal of Computational and Applied Mathematics，2004，165：587－600.

［4］ DAVID M YONG.Iterative solution of large linear systems［M］.New York：Academic Press，1971：26－49.

［5］ RICHARD S VARGA.Matrix iterative analysis［M］.Heidelberg：Spring－Verlag，2000：60－80.

［6］ 張謀成，黎穩(wěn).非負(fù)矩陣論［M］.廣州：廣東高等教育出版社，1995：71－93.

［7］ ZHUAN－DE WANG，TING－ZHU HUANG.Comparison result between Jacobi and other iterative methods［J］.Journal of Computational and Applied Mathematics，2004，169：45－51.

［8］ XUE－ZHONG WANG，TING－ZHU HUANG，YING－DING FU.Comparison results on preconditioned SOR－type iterative method for Z－matrices linear systems［J］.Journal of Computational and Applied Mathematics，2007，206：726－732.

Convergence and diverge analysis of the JOR iterative method with parameter in preconditioned

WANG Hui－qin，LEI Gang

（Department of Mathematics，Baoji University of Arts and Sciences，Baoji 721013，China）

For the JOR iteration method to solving the linear system Ax＝b，this paper apply the preconditioner to accelerate convergence of the JOR iteration method，and give a more generally preconditioned JOR iteration method by leading into parameterα.It prove that the rate of convergence of this method is faster than normal JOR iteration method，then have found the parameter optimal numerical.Last the results are verified by numerical example.

the JOR iteration method；convergence；precondition；spectral radius

O 241.6 ［學(xué)科代碼］ 110·6150 ［

］ A

（責(zé)任編輯：陶理）

1000－1832（2015）01－0043－05

10.16163／j.cnki.22－1123／n.2015.01.009

2013－10－12

國家自然科學(xué)基金資助項(xiàng)目（11371031）；陜西省教育廳計(jì)劃項(xiàng)目（14JK1052）；陜西省自然科學(xué)基礎(chǔ)研究計(jì)劃項(xiàng)目

（2013JM1001）.

王慧勤（1979—），女，碩士，講師，主要從事數(shù)值計(jì)算與數(shù)據(jù)挖掘研究；雷剛（1977—），男，碩士，副教授，主要從事數(shù)值計(jì)算與并行分析研究.