毕业论文线性方程组的欲条件解法_线性方程组的解法论文

毕业论文线性方程组的欲条件解法由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“线性方程组的解法论文”。

学校代码：10206 学生学号：051074210

白城师范学院

毕业论文

线性方程组的预条件解法

Pre-conditions for Solution of System of Linear Equations

学生姓名：孙雷 指导教师：牟欣 讲师 学科专业：数学与应用数学 所在单位：数学系

2011年 6 月

摘要

摘 要

随着计算机的发展，在许多实际应用和数学研究中，经常遇到求解线性方程组的问题，而数值代数己经成为处理这些问题的强大工具。在本文中，主要研究了对线性方程组的几种预条件迭代解法。使用预条件矩阵来加速迭代方法的收敛性是通常所采用的方法，预条件迭代法对于解决系数矩阵是大型稀疏矩阵的情况有较好的效果。

证明了当线性方程组的系数矩阵A为不可约L-矩阵时的预条件AOR方法，并且证明了其收敛性，最后用数值试验验证所提出的理论结果。当选取最优参数时，通过数值试验可看出我们的方法所得迭代矩阵的谱半径比小。

提出以SSOR多分裂作为内分裂的松弛不定常二级多分裂法，然后研究了所提出的方法在求解当系数矩阵为H-矩阵的线性系统的收敛性，最后具体给出此方法收敛性的论证及其应用。

关键词： L-矩阵，H-矩阵，M-矩阵，预条件AOR法，SSOR多分裂

I

Abstract

Abstract With the development of the computers, numerical analysis concerned with the solution of linear systems of equations is always used in the practical and mathematic problems.For a linear system, we study the several preconditioning method in this paper.It is quite common to use preconditioning to accelerate the convergence of a basic iterative scheme which is very useful to solve the large sparse coefficient matrix.We improve the preconditioned AOR iterative scheme for irreducible L-matrices considered and then we prove the convergence of our method.Lastly, numerical experiments to illustrate the theoretical results are provided.When choosing the approximately optimal parameters, our scheme has small spectral radii of the iterative matrices than the spectral radii of AOR iterative scheme, which is shown through numerical examples.We present the relaxed nonstationary two-stage multisplitting method using an outer splitting and the SSOR multisplitting as inner splitting.Then, we study the convergence of the proposed method for solving the linear system whose coefficient matrix is an H-matrix.At last, we give the specific convergence of this method of argumentation and its application.KeyWords： L-matrix, H-matrix, M-matrix, preconditioned AOR method, SSOR multisplitting

II

目录

目 录 绪论.............................................................................................................................................1

1.1引言....................................................................................................................................1 1.2常见的预条件方法............................................................................................................2 2 预条件AOR迭代法....................................................................................................................4

2.1概论....................................................................................................................................4 2.2预备知识............................................................................................................................5

2.2.1本章中用到的定义................................................................................................7 2.2.2本章中用到的定理................................................................................................7 2.3主要结果............................................................................................................................7 2.4小结..................................................................................................................................13 3 预条件多分裂迭代法...............................................................................................................14 3.1概论..................................................................................................................................14 3.2预备知识..........................................................................................................................14 3.2.1本章中用到的定义..............................................................................................14 3.2.2几种常见的分裂方式..........................................................................................15 3.2.3本文中用到的定理..............................................................................................16 3.3主要结果..........................................................................................................................17 3.4小结..................................................................................................................................19 结论................................................................................................................................................20 参考文献.........................................................................................................................................21 致谢................................................................................................................................................22

I

绪论 绪论

1.1引言

很多科学问题的解决都需要解这样一个线性方程组，求解线性方程组是数值线性代数的一个基本问题，即给定ACnn,bCm，寻找解向量xCn使得Axb。解线性方程组的传统方法是用Gauian消元法，假设系数矩阵A是一个这样用Gauian消元法直接解的运算量是On3。并且许多微nn的非退化阵，分方程经过适当差分或有限元离散所产生的线性代数方程组的系数矩阵，不仅具有大型稀疏的特性，而且常常呈现出规则的分块结果。当n很大且A稀疏时，用直接法就很不划算，而且需要很大的存储空间，人们开始考虑和研究用迭代法求方程组Axb的近似解，即用某种极限过程去逐渐逼近精确解，并发展了许多非常有效的迭代方法，常见的如Jacobi方法、Gau-Seidel方法、SOR方法、SSOR方法，这几种迭代方法是最常用的一阶线性定常迭代法。

即若系数矩阵A的一个分裂：A=M-N，M为可逆矩阵，线性方程组

Ax=b

(M-N)x=b Mx=Nx+b

x =M1Nx+M1b

得到迭代方法的一般公式：

x(k1)Hx(k)d

其中：HM1N，dM1b，H称为迭代矩阵，它的收敛性直接关系到方程组的求解，收敛性迭代矩阵M1N的谱半径有关，谱半径小于1时就收敛，否则就发散，而且谱半径越小，迭代矩阵收敛速度就越快。

若假设A是nn阶矩阵，且AILU，L和U分别是的严格下三角和严格上三角部分，则经典的Gau-Seidel迭代法的迭代矩阵为H(IL)1U。迭代法解线性方程组时都假设矩阵A是非奇异矩阵，当矩阵A是奇异矩阵时，可以通过变换把Axb变为一个和它同解的新的系数矩阵为非奇异的线性方程组。

为改善迭代法的收敛性和收敛速度，Hadjidioms于1978年提出一种快速超松弛迭代法(简称AOR迭代法)，它含有两个参数ω，τ，当时ω=τ，这种方法就

绪论

变为逐次超松弛迭代法(简称SOR迭代法)；随着并行计算机的发展，1983年Misirlis提出一种解线性方程组的方法，称为并行Jacobi型方法，它的突出优点是适合大型并行机的计算。胡家赣[1]在1992年提出了两参并行的Jacobi型方法(简称2PPJ型方法)，使Misirlis提出的方法成为2PPJ型方法的特例。另外，结合实际的需要，还产生了一些如SSOR型迭代法、SAOR型迭代法、PSD型迭代法等一系列迭代方法，目的都在于改善迭代矩阵的收敛性和收敛的速度。

1.2常见的预条件方法

在实际的计算过程中，收敛性的改善不仅取决于迭代方法以及迭代矩阵中参 数的选取，而且同方程组自身的某些变化也密切相关，例如可以对方程组两边左 乘一个非奇异矩阵P(预处理)。通过这种技巧，线性方程组Ax=b等价变为

PAx=Pb

(1-1)如果PA还有分裂PAMANA，那么(1-1)对应的迭代格式为

x(k1)MA1NAx(k)MA1Pb,k0,1,...(1-2)

式(1-1)称为预条件方法。1991年，Gunawardena等提出了修改的Gaue-Seidel方法（简称MGS方法）如下：令(1-2)式中的P=I+S，其中

a1200000a023

S000an1,n0000文献[3]证明了该预条件用于Gaue-Seidel迭代法的收敛性。为了进一步研究MGS方法并改善其收敛速度，1997年Kohno等利用带有n-1个参数的预条件矩阵PIS，其中



S0000a1a120000a2a23000 an1an1,n00并采用与文献[3]相同的迭代格式（只把S改成S），将文献[3]的结果进行了推广。随后文献[5]将文献[4]中的预条件方法应用到H-矩阵类。国内外很多学者对于这类方法都进行了进一步的研究，如GAOR迭代法，并且给出了当A为H-矩阵时的一些收敛性结论。

本文的第二章将考虑用如下两种预条件矩阵形式：

绪论

PPS1 和 PPS2

这里PS1IS1,PS2IS2，其中

0a2a21S1a3a31aann10000000S200000a1a120000a2a23000

an1an1n,00

并讨论了该预条件用于AOR迭代法的收敛性。当选取不同的参数值时，通过实例可以看出，我们所提出的预条件迭代矩阵的谱半径要比文献中所提到的预条件迭代矩阵谱半径小的多，在一定程度上改进了迭代法的收敛速度。

若A=MN是A的一个分裂，则三角阵(Mk,Nk,Ek),k1l称为A的一个多分裂，Ek是非负矩阵，并且

Ek1lkI。由此多分裂，我们得到了求解线性系统Ax=b的多分裂法，Bai，Sun和Wang在统一的算法框架下建立了矩阵多分裂迭代算法的收敛理论。多分裂法首先由O’Leary和White所提出，后来又被许多学者进行了进一步的研究。多分裂法被广泛的应用于二级分裂迭代法中，其中ILU多分裂法在文献里对于系数矩阵为H-矩阵或M-矩阵等的收敛性以及由此做出的预条件矩阵已做了深入研究和讨论，并得到了较好的收敛效果，但还有许多分裂法仍可用于二级迭代法中，及其他一些特殊类型的矩阵的多分裂法还可做进一步讨论。本文第三章将考虑当系数矩阵为H-矩阵时用SSOR多分裂作为内分裂的二级多分裂法的预条件法，并讨论了该预条件迭代法的收敛性，并与SSOR多分裂法进行了比较，数值表明我们的算法要优于SSOR多分裂法。

预条件AOR迭代法预条件AOR迭代法

2.1概论

在第一章中已经提到，当线性方程组Axb的系数矩阵A是大型稀疏矩阵或具有某些特殊性质时，对方程组的系数矩阵A进行预条件处理是一种不但常用而且较为有效的方法。其基本思想就是寻找一个特殊的可逆矩阵P，左乘方程组Axb后，使得矩阵PA相应分裂的迭代矩阵的谱半径较小。近年有好多学者对系数矩阵为特殊情形进行了深入的研究。

在本章中，我们考虑当线性方程组的系数矩阵A为不可约L-矩阵时，预条件迭代法的构造及其具体应用。主要构造了二种预条件矩阵，把这二种预条件矩阵应用到AOR迭代法中，比较在此迭代法中的作用，还讨论了预条件AOR迭代法收敛性同预条件矩阵的参数之间关系。

考虑线性方程组

Axb

(2-1)

其中x,b∈Rn，A(aij)nn在实际应用中，Gau消去法及Cholesky分解法是常见的直接解法，但当系数矩阵A具有某些特殊性质时，这时迭代法具有了相当的优势，相比之下，直接解法往往很不实用，效果不佳。

上面我们已就相关内容的展开作了铺垫性的说明，对于应具备的理论背景作了扼要的介绍，下面我们就系数矩阵为不可约L-矩阵的线性方程组预条件矩阵的选取作详细的论证。

为了更好的求解线性方程组Ax=b，这里A(aij)nnRnn是非奇异矩阵，常用某些非奇异矩阵P对(1-1)式进行预处理，即考虑方程组

PAx=Pb 这里P称为预条件矩阵。1991年，Gunawardena提出了修改的Gaue-Seidel方法（简称MGS方法）如下：令上式中的P=I+S，其中

a1200000a023S

000an1,n0000文献[3]证明了该预条件用于Gaue-Seidel迭代法的收敛性。为了进一步研究MGS方法并改善其收敛速度，1997年Kohno利用带有n-1个参数的预条件矩阵PIS，其中

预条件AOR迭代法



S0000a1a120000a2a23000 an1an1,n00并采用与文献[3]相同的迭代格式（只把S改成S），将文献[3]的结果进行了推广。随后文献[5]将文献[4]中的预条件方法应用到H-矩阵类。

本文则考虑用如下两种预条件矩阵形式：

PPS1 和 PPS2 这里PS1IS1，PS2IS2，其中

0a2a21S1a3a31aann100000000S20000a1a120000a2a23000

an1an1,n00并讨论了该预条件用于AOR迭代法的收敛性。

2.2预备知识

考虑线性方程组Ax=b，这里A(aij)nnRnn是非奇异矩阵，我们考虑用迭代法求解此方程组。对于矩阵A的一个分裂AMN，其中M0，则有求解线性方程组(2-1)的基本迭代法为：

xj1M1NxjM1b k0,1,...不失一般性，设矩阵A的一个分裂形式为ADLU，这里D，L和U分别是A的对角、严格下三角和严格上三角矩阵。不妨设D=I，则定义A的AOR迭代矩阵为：

x(j1)(IrL)1[(l)I(r)LU]x(i)(IrL)1b

(2-2)

则有AOR迭代法的迭代矩阵为：

Tr(IrL)1[(l)I(r)LU]

(2-3)这里参数ω和r都为正的。

现在我们将原来的线性方程组(2-1)转换为预条件系统

PAx=Pb

(2-4)

这里矩阵P称为预条件矩阵。则求解线性方程组(2-4)的基本迭代法为：

xk1Mp1NpxkMp1Pb(2-5)

预条件AOR迭代法

其中x0为初始向量，PAMpNp是矩阵PA的一个分裂。

i(i2,3,...,n)是实参数并且对所有的i=2,3,…,n都有i >0。特别的，若令i1(i2,3,...,n)，则所对应的预条件矩阵就为[6]中所讨论的形式。

令

PA, SUDLU

A1S1这里D，L和U分别是A的对角、严格下三角和严格上三角矩阵。由于S1L=0，我们可得

(IS)(ILU)ILDSSUDLU(2-6)A111ID,LLSL,UUU。其中D1令APS2A和S2LD*L*，其中D*是对角矩阵，L*是严格下三角矩阵，则我们可得到：

LU(2-7)A(IS2)(ILU)ILDS2S2UD其中D =I D*，LL L*，UUS2S2U。

若我们将AOR迭代法用在预条件线性系统（2-4），则我们得到预处理AOR迭代法，其迭代矩阵为：

(DrL)1((1)D(r)LU)

若PP

(2-8)TS1r或

Tr(DrL)1((1)D(r)LU)

若PPS(2-9)

当ω=r时，则（预条件）AOR迭代法就是（预条件）SOR迭代法[5]。对ω=r及，T，由(2-3)，(2-8)，(2-9)可得到相应的迭代矩阵T，T，迭代矩阵Tr，TrrT，即：

T(IrL)1((l)IU)

(2-10)(DrL)1((l)DU)

(2-11)

T

T(DrL)((l)DU)

(2-12)

1

预条件AOR迭代法

2.2.1本章中用到的定义

定义2.2.1.1设A(aij)为n×n的矩阵，若aij0(ij),则我们称之为Z-矩阵。

定义2.2.1.2记所有n×n实矩阵A(aij)所组成的集合为Rnn,Rnn的子集为Znn{A(aij)ARnn,aij0,(i,j,ij)}。当AZnn，且aij0()i成立时，称矩阵A为L-矩阵。

定义2.2.1.3设Aaij,Bbij是同阶矩阵，若i,j,aijbij，则称AB;i,j,a则称AB。ijbij,2.2.2本章中用到的定理

定理2.2.2.1设A为n阶非负不可约方阵，则

(a)ρ(A)为A的一个正特征值；

(b)A对于ρ(A)，相应地存在一个正的特征向量x>0；(c)ρ(A)为A的一个简单特征值。

定理2.2.2.2设A为n阶非负方阵，则有如下结论成立：

(a)若存在一非负向量x，x≠0，使得Ax≥βx，则有ρ(A)≥β；

(b)存在一正向量x，使得Ax≤γx，则有ρ(A)≤γ；进一地的，如果A是不可约的且0≠βx≤Ax≤γx对某一非负向量成立，则β≤ρ(A)≤γ成立，并且是一正向量。

2.3主要结果

nn

定理2.3.1设AaijR是一个L-矩阵，A2:n,2:n是A的不可约子

阵。假设存在一个非空集N12,3,n和实参数i0，i=2,3,…,n，使得

i0ia1iai11,  若

aa0,iN11ii1若0≤r≤ω≤1(ω≠0,r≠1)，则有：

设(2-3)和(2-8)定义的矩阵分别为Tr和Tr；(a)若Tr1，则TrTr；(b)若Tr1，则TrTr

预条件AOR迭代法

。(c)若Tr1，则TrTr

证明 由(2-3)，Tr可表示为

Tr= 1I1rLUH

(2-13)

这里H是一个非负矩阵。由于A是一个L-矩阵，故L和U也是非负的。由(2-13)可得

Tr0。由于A2:n,2:n是不可约矩阵，对所有的i∈β，都有a1iai10，所以可得矩阵A也是不可约的。由于ω≠0,r≠1，A是不可约矩阵，得1rLU是不可约矩阵。故由(2-13)得Tr是不可约矩阵。由定理2.2.2.1，则存在一个正向量x，使得Trxx，我们很容易的可得：

1I1rLUxIrLx

S1Ux1S1x

(2-14)

由(2-8)和(2-14)有：

1rLUDrLx

TrxxDrL1D1rrLUx

DrL1DrL11DrrLSUx D1rL11D1rLrrSSUx D111DrL1DrLrr1S1x

rL1DrL1rSx

(2-15)1D1LU也是L-矩阵，,L由于0ia1iai11，得D,L和S1是非负的。由于A则D都为非负矩阵。经简单计算，T可表示为： 和Ur1T1112

Tr1I1rDLDUH

(2-16)T220是一非负矩阵，0是1n1阶矩阵，0是n1n1阶矩阵。这里H TT1222是一非零矩阵A2:n,2:n是不可约的，我们由于对所有的i∈β，a1i0，故T128

预条件AOR迭代法

2:n,2:n也是不可约的。由于ω≠0,r≠1,由(2-16)得很容易得到A2:n,2:nT是不可约的。令 Tr221

及

zDrLyDrL1rS1x y

(2-17)

对所有的i∈β，ai10，当r1及x>0时y0是一非负向量且y向量的第一个rL元素都为0。由于D1是非负的下三角矩阵，故z≥0是一非负向量且z向量的第一个元素都为0。所以，我们可令

x10

x

及

z

(2-18)

x2z2这里x1R10,x2Rn10,z2Rn10是一非负向量。由(2-15)-(2-18)，得

xx1z，故 Trx

(2-19)

1x1T122xx1z

(2-20)

T22222当λ>1时，由(2-20)，我们可得：

xx

及

Txx

(2-21)

T22222222。由于011，有： 由式(2-20)及定理2.2.2.2，有T22TT

Tr22r当λ

xx

及

Txx

(2-22)

T222222220是不可约的且x0，由(2-22)式及定理2.2.2.2得 T222T22

(2-23)

0是非负的且x0，有Tx0。由(2-19)，1xx，及 由于T21212211

(2-24)

T。max1,T,由(2-23)及(2-24)得T由于Trrr22xx。因此，由定理2.2.2.2可得： 当λ=1时，由式（2-15）TrT Trr9

预条件AOR迭代法

推论2.3.2设AaijRnn是一个L-矩阵，A(2:n,2:n)是A的不可约子阵。假设存在一个非空集N12,3,...,n和实参数ai0,i2,3,...,n,使得

i0aia1iai11  若

aa0iN1ii11。若0

（1）若T1,则TT;（2）若T1,则TT。（3）若T1,则T注: 若r=ω=1时，则（预条件）AOR法就是我们所说的（预条件）Gau-Seidel

不一定可约，故定理法。对于r=ω=1，由于在定理2.3.1的证明中矩阵Tr和T222.3.1就不一定成立。因此，当r=ω=1时，推论2.3.2就不一定成立。在今后的工作中我们会进一步讨论当r=ω=1时推论2.3.2成立的条件。

引理2.3.3设AaijRnn是一个L-矩阵，假设存在一个非空集

i0,i2,3,...,n使得对所有的iN2，都有N21,2,3,...n,和实参数1ai1ai,j1ai1,j1设(2-3)和(2-9)定义的矩阵分别为Tr和Tr。如果0≤r≤ω≤1(ω≠0,r≠1)，且A是不可约的，对所有的i,令ai,j10,则有Tr和Tr是非负不可约的。

证明由已知对所有的i,ai,j10,A是不可约的，故AILU是不可约的。因此由(2-13)，Tr是非负不可约矩阵。令：

AP2AIS2ADLU

这里D,L及U为(2-7)式中所定义的矩阵。由于A是L-矩阵，并且对所有的iN2,有i1ai,j1ai1,j1故可得A是L-矩阵，并且D,L和U为全都是非负矩阵。对所有的i∈γ，当ai,j10时A矩阵的非零结构与A的非零结构相同，故由假设可知A也是不可约的。这时Tr可表示为如下形式：

预条件AOR迭代法

11

Tr1I1rD1L1DUH

(2-25)这里H是一个非负矩阵。由(2-25)可得，Tr也是非负的。由于ω≠0,r≠1，A是不可约的，则1rD1L1D1U1也是不可约矩阵。因此，由(2-25)，Tr是不可约矩阵。

nn

定理2.3.4设AaijR是一个L-矩阵，假设存在一个非空集

N21,2,3,...,n1使得对所有的i∈γ满足条件ai,j10，以及实参数ai0,i=2,3,…,n，使得对所有的iN2，都有i1ai,j1ai1,j1。设(2-3)和(2-9)所定义的矩阵分别为Tr和Tr。如果0≤r≤ω≤1(ω≠0,r≠1)，且A是不可约的，对所有的i∈γ，令ai,j10，则有：

(1)若Tr1，则TrTr；(2)若Tr1，则TrTr；(3)若Tr1，则TrTr。证明

由引理2.3.4，Tr是非负不可约矩阵。由定理2.2.2.1得，存在一个正的向量x>0，使得Trxx，这里Tr。由Trxx，我们很容易得到：

1IrLUxIrLx

1SrrSLxSUx

(2-26)

2221由(2-9)和(2-26)得： TrxxDrL1DrLUDrLx

1DrrLUx DrLDrLDrLDrL111DrrLSUSx22

11(DS2)rr(LS2L)S2x211D1SrrDx11

预条件AOR迭代法

DrL1rr1D1Sx

2

1DrL1rD1S2x

(2-27)由于0ia1iai11，得D，D，L和S2是非负的。令

y((1r)DS2)x

及

z(DrL)1y

(2-28)

对所有的i∈γ，ai,j10，当r≠1及x>0时有y(yi)0是一非负向量且对所有

rL)1是非负的下三角矩阵，故z≥0是一非负向的i∈γ，yi都不为零。由于(D量且对所有的i∈γ，zi都不为零。由(2-27)和(2-28)，我们可得：

Trxx1z

(2-29)

当λ=1和λ>1时，由定理2.3.1和定理2.3.3，我们可直接相应的得到Trxx及Trxx(Trxx)。当λ

推论2.3.5设A(aij)Rnn是一个L-矩阵，假设存在一个非空集N21,2,3,...,n1使得对所有的i∈γ满足条件ai,j10，以及实参数使得对所有的iN2，都有i1ai,j1ai1,j1。设(2-10)和(2-12)ai0,i2,3,...,n，所定义的矩阵分别为Tr和Tr。如果0

(1)若Tr1，则TrTr；(2)若Tr1，则TrTr；(3)若Tr1，则TrTr。

注: 若r=ω=1时，由于在定理2.3.4的证明中矩阵Tr和Tr不一定可约，故定理2.3.4就不一定成立。因此，当r=ω=1时，推论2.3.2就不一定成立。在今后

预条件AOR迭代法的工作中我们会进一步讨论当r=ω=1时推论2.3.6成立的条件。

2.4小结

在这一章中，我们首先提出了对于不可约L-矩阵的AOR迭代法的预条件矩阵，并且证明了其收敛性。特别的，我们还可以讨论如何选取一组参数值，使得我们所提出方法的收敛速度有进一步的提高。如何选取一组最优参数将是我们今后继续研究的课题。

预条件多分裂迭代法预条件多分裂迭代法

3.1概论

对方程组的系数矩阵A进行预条件处理是一种不但常用而且较为有效的方法，因而，众多学者致力于系数矩阵A的预条件研究，比如Pool和Ortega[23]所用不完全矩阵因子分解预条件方法；Johnson和Saad所用多项式矩阵分裂预条件方法。在本章中，我们首先提出以SSOR多分裂作为内分裂的松弛不定常二级多分裂法，并且研究了所提出的方法在求解当系数矩阵为H-矩阵的线性系统的收敛性。通过具体的数据实例，我们可以看出，当选取一组近似最优参数时，所提出的方法的收敛速度比松弛SSOR多分裂法快。下面我们就具体给出此方法收敛性的论证及其应用。

3.2预备知识

考虑线性方程组Ax=b，这里A(aij)Rnn是非奇异H-矩阵，我们考虑用迭代法求解此方程组。自从O’Leary和White基于矩阵的多分裂提出了并行多分裂迭代法。

3.2.1本章中用到的定义

下面对本文将要涉及的矩阵理论作简单介绍。

定义3.2.1.1记所有n×n实数矩阵A(aij)所成集合为Rn,n，Rn,n的子集为nnRA(aij)ARnn,aii0,(i) ZnnA(aij)ARnn,aii0,(i,j,ij)当ARnn且aii0,(i)时，称A为L阵。

定义3.2.1.2设A(aij)，B(bij)是同阶矩阵，若i,j,aijbij，则称A≥B；若i,j，aijbij，则称A>B。

定义3.2.1.3 若ARnn，且A可表示为A=sI-B，I为n阶单位矩阵，B≥0，14

预条件多分裂迭代法

那么当sB时，称A为M-矩阵，特别的当sB时，称A为非奇异M-矩阵，如果有sB，则称A为奇异M-矩阵。

定义3.2.1.4 若AZnn，A可逆且A10，则称A为非奇异M-矩阵。定义3.2.1.5 若A为L阵，且有分解ADC,Ddiag(A)那么A为非奇异M-矩阵的等价条件为(D1C)1。

由定义可看出，定义3.2.1.3，定义3.2.1.4，定义3.2.1.5是等价的，L-矩阵在线性迭代理论中很大程度上指M-矩阵，M-矩阵在迭代法中主要指非奇异M-矩阵，很少涉及奇异M-矩阵。

定义3.2.1.6 Aij称为A的比较矩阵，若满足条件

(a)当i=j时，ijaij；(b)当i=j，ijaij。

定义3.2.1.7 若A的比较阵A是M-矩阵，则称A为H-矩阵。

3.2.2几种常见的分裂方式

定义3.2.2.1如果A是方阵，且M为非奇异M-矩阵，N≥0，那么A=M-N称为矩阵A的M-分裂。

定义3.2.2.2如果A是方阵，A有分裂A=M-N，则(1)如果M10，N0，那么这种分裂叫正规分裂。

(2)如果M10，M1N0，那么这种分裂叫弱正规分裂。

(3)如果M10，N0，且M为非奇异M-矩阵，那么这种分裂叫M-分裂。显然，M-分裂正规分裂弱正规分裂。

定义3.2.2.3 称MkNkEkk1是矩阵A的一个多分裂，若：(1)AMkNk,k1,2,...,l是A的一个分裂；

(2)Ek0,k1,2,...,l，是一个非负对角矩阵，称为权矩阵；(3)EkI，这里I是一个单位矩阵。k1l

预条件多分裂迭代法

对于矩阵A的一个多分裂MkNkEkk1，松弛参数β为一个正数，对于求解线性系统Ax=b的松弛多分裂算法如下：

算法3.2.2.4松弛多分裂法：

给定一个初始向量x0

For i=1,2,…,直到收敛

for

k =1 to l

MkykNkxkb, EkIMkykNkxkbxiEkyk(1)xi1

k1k1ll

注3.2.2.5 若MkNkEkk1是矩阵A的一个多分裂的一个多分裂，对每一个k，MkBkCk是Mk的一个分裂，松弛参数β为一个正数，则对于求解线性系统Ax=b的松弛非定常二级多分裂算法如下：

算法3.2.2.6松弛非定常二级多分裂法：

给定一个初始向量x0

For

i=1,2,…,直到收敛

for k=1…l

ykoxi1

for

j =1 to sk,i

yk,jBk1(Ckyk,j1Nkxi1b)(1)yk,j1

xiEkyk,sk,i

k1l 注3.2.2.7在算法3.2.2.6中，分裂AMkNk称为外分裂，分裂MkBkCk称为内分裂。当A是一个单调矩阵（即, A10）或A是一个H-矩阵，在算法3.2.2.6中当内迭代数sk,i用一个常量s代替，即s与变量k和i无关时，则我们得到了松弛二级多分裂法(即算法3.2.2.8)。3.2.3本文中用到的定理

引理3.2.3.1 设ADB是H-矩阵，这里D=diag(A)，则有以下结论成立：

预条件多分裂迭代法

(a)A和D是非奇异矩阵，且(D(b)A1A11B)1。

s 定义3.2.3.2 设0

Mk()1/2DLkD1DUk

Nk()1/2(1)DLkD1(1)DUk

3.3主要结果

定理3.3.1 设A是一个n×n阶的H-矩阵，且

ss是严格下三角矩阵，UkADBDLkUk(1kl，这里D=diag(A)，Lk是一般矩阵，若

MkNkEkk1,k1,2,...,l是A的一个多分裂，ADLkUk,k1,2,...,l。则当0

(a)Mk1Mk；(b)NkMk1N。

(c)Mk1NkMkk其中：

11/2DL MkkDDU

1k(1)if01Nk Nk(2)

if12/1Nk(1)1/2((1)DL)D1((1)DU)

Nkkk(2)1/2((1)DL)D1((1)DU)Nkkk17

预条件多分裂迭代法

证明 显然，当ω>0时，设CDUk，则CDUDLk是H-矩阵。111k是矩阵C的一个正规分裂。当ω

DLkD1DL1kD(DLk)1

(DU1k)D(DL1k)DU1kDDL1k

(DU11k)D(DLk)由(3-1)，M1k()M1k()。(a)证毕。下面我们证明(b)和(c)。情况1：令0

1DLkD11DUk

1DL1kD1DUk

1DLD1k1DUk

因此M1k()Nk()M1k()Nk()M(1)k()N(1)k()M1k()Nk()情况2：令1

((1)DL1k)D(1)DUk

(1)DL1kD(1)DUk

(1)DL1kD(1)DUk

因此N)N(2)k(k()Nk()，则 M1k()Nk()M1k()Nk()M1k()N(2)k()M1k()Nk()至此，(b)和(c)证毕。

(3-1)

(3-3)

(3-2)预条件多分裂迭代法

3.4小结

在本章中，我们讨论了在求解线性系统Ax=b（这里ARnn是一个H-矩阵）时，用SSOR多分裂作为内分裂的松弛非定常二级多分裂法的收敛性。

为了有效的加快我们所提出方法的收敛性，如何选取一组参数将是我们今后所要探讨的问题，有待于进一步的研究。

结论

结论

我们首先提出了对于不可约L-矩阵的AOR迭代法的预条件矩阵，并且证明了其收敛性。特别的，我们还可以讨论如何选取一组参数值，使得我们所提出方法的收敛速度有进一步的提高。如何选取一组最优参数将是我们今后继续研究的课题。

我们在本文中还讨论了在求解线性系统Axb(这里ARnn是一个H矩阵)时，用SSOR多分裂作为内分裂的松弛非定常二级多分裂法的收敛性，当选取近似最优参数时，我们所提出的算法其收敛速度更快。为了更有效的加快我们所提出方法的收敛性，如何选取一组参数将是我们今后所要探讨的问题，还有许多多分裂法仍可用于二级迭代法中，及其他一些特殊类型的矩阵的多分裂法还有待进一步讨论。

参考文献

参考文献

[1]A.D.Hadjidimos.Accelerated over relaxation method [J].Mathematics of computation, 1978, 32:149-157 [2]胡家赣.双参并行Jacobi型方法及其收敛性[J].计算数学,1992,14(1):70-78 [3]Gunawardena A.D., Jain S.K., Snyder L.Modified iterative methods for consistent linear Systems[J].Linear Algebra Appl, 1991, 12:123-143

[4]Kohno T.Improving modified iterative methods for Z-matrices [J].Linear Algebra Appl, 1997, 267:113-123 [5]孙丽英.解线性方程组的预条件迭代方法[J].高等学校计算数学学报,2002,24(2):155-162 [6]胡家赣.线性代数方程组的迭代解法[M].北京:科学教育出版社,1991 [7]Niki H, Harada K, Morimoto M, Sakakibara M.The survey of preconditioners used for accelerating the rate of convergence in the Gau-Seidel method [J].Comput Appl.Math, 2004, 13:587-600 [8]张谋成,黎稳.非负矩阵论[M].广州:广东高等教育出版社,1995 [9]Usni M, Niki H, KohnoT.Adaptive Gau-Seidel method for linear systems[J].Int J of Comput and Math, 1994,51:119-125 [10]曹志浩.数值线性代数[M].上海:复旦大学出版社，1996

致谢

致谢

在论文撰写过程中，得到了系里各位老师的支持与鼓励，尤其是指导教师牟欣老师，从确定题目到定稿打印，一直不顾劳累，抽出时间对论文的写作目的和方向予以指导和改正。对论文中出现的疑难问题，牟欣老师又帮忙查阅资料、文献，使论文能够顺利完成。在此对牟欣老师及系里的各位老师表示深深的感谢。