預條件下含參數的JOR迭代法斂散性分析

王慧勤，雷 剛

（寶雞文理學院數學系，陜西寶雞721013）

預條件下含參數的JOR迭代法斂散性分析

王慧勤，雷 剛

（寶雞文理學院數學系，陜西寶雞721013）

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

JOR迭代法；收斂性；預條件；譜半徑

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

1 預備知識

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

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

迭代矩陣為

在文獻［1］預條件P＝（I＋C）作用下，

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

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

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

2 定義和引理

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

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

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

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

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

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

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

（2）A有與ρ（A）相對應的非負特征向量；

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

引理2［6］設A為非負矩陣，則：

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

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

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

3 結果與證明

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

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

（1）當ρ（TJ）＞1時，ρ（TJCα）≥ρ（TJ）；

（2）當ρ（TJ）＝1時，ρ（TJCα）＝ρ（TJ）；

（3）當ρ（TJ）＜1時，ρ（TJCα）≤ρ（TJ）.

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

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

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

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

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

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

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

（1）當ρ（TJ）＜1時，ρ（TJCα2）≤ρ（TJCα1）；

（2）當ρ（TJ）≥1時，ρ（TJCα2）≥ρ（TJCα1）.

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

也就是

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

當ρ（TJ）≥1，α1＜α2時，考慮

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

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

4 數值例子

如果線性方程組Ax＝b的系數矩陣

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

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

在引入參數α改變預條件后JOR迭代法的分裂形式，當取定一個確定的松弛因子ω時，隨著參數α的變化，可以發現改進分裂形式后的JOR迭代法的收斂速度要優于一般的預條件方法.

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

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

5 結論

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

［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］ 張謀成，黎穩.非負矩陣論［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 ［學科代碼］ 110·6150 ［

］ A

（責任編輯：陶理）

1000－1832（2015）01－0043－05

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

2013－10－12

國家自然科學基金資助項目（11371031）；陜西省教育廳計劃項目（14JK1052）；陜西省自然科學基礎研究計劃項目

（2013JM1001）.

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