第3章线性方程组迭代法

第3章解线性方程组的迭代法

(IterationMethodsforLinearSystems)

直接法得到的解是理论上准确的，但是它们的计算量是n3数量级，存储量为n2量级，这在n比较小的时候还比较合适，但是对很多实际问题，往往要我们求解很大型的矩阵，而且这些矩阵含有大量的零元素。对于这类矩阵，在用直接法时就会耗费大量的时间和存储单元。因此引入一类新的方法：迭代法。

第3章解线性方程组的迭代法

(IterationMethodsforLinearSystems)

迭代法的思想：逐次逼近；

将求一组解转换为求一个近似解序列的过程。考虑三个问题：1.迭代的初始值：选取是否有范围限制，对迭代结果有无最终影响；2.迭代的算法：考虑怎样由当前的迭代结果得出下一次的初始值，不同的算法带来不同的误差，误差是放大还是缩小；3.迭代的收敛性：迭代是否收敛，收敛过程的快慢。

将方程组Ax=b变形为x=Bx+g如：令，则

定义1

任取初始向量x

(0)

，由迭代公式得序列x

(k)

作为原方程组的近似解,这种方法为迭代法。B称为迭代矩阵。§3.1

基本迭代法引言将方程组Ax=b变形为x=Bx+g

定义1

任取初始向量x

(0)

，由迭代公式得序列x

(k)

作为原方程组的近似解,这种方法为迭代法。B称为迭代矩阵。引例

求解线性方程组解：

将原方程组或记为x=Bx+g其中取初始值

x(0)=(0,0,0)T迭代10次，得x(10)=(3.000032,1.999838,0.9998813)T精确解为：

x*=(3,2,1)T一、Jacobi迭代法1.迭代思想：设方程组为从第i个方程解出xi格式很简单：把迭代前的值代入左边，由计算得到等式左边的值作为一次迭代的新值带入右边，如此反复得到Jacobi迭代公式2.Jacobi迭代矩阵记A=-L-UDJacobi迭代矩阵表示为：Jacobi迭代矩阵为代入方程组得：二、Gauss－Seidel迭代法1.迭代思想：在Jacobi迭代中，使用最新计算出的分量值得2.Gauss－Seidel迭代矩阵例1：用Jacobi迭代法求解解：解：仍取x(0)=(0,0,0)T,带入迭代式得例2：用Gauss-Seidel迭代法求解如此继续下去，得x(5)=(10.9989,11.9993,12.9996)T,精确解为x=(11,12,13)T

上例结果表明，Gauss-seidel迭代法比Jacobi迭代法效果好。事实上，对有些问题Gauss-seidel迭代确实比Jacobi迭代法收敛得快，但也有Gauss-seidel迭代比Jacobi迭代法收敛得慢，甚至有Jacobi迭代收敛而Gauss-seidel迭代发散的情形。只是Gauss-seidel与Jacobi相比，只需一组工作单元存放近似解。

松弛迭代法是高斯-赛德尔迭代法的一种加速方法，其基本思想是将高斯-赛德尔迭代法得到的第k+1次近似解向量与第k次近似解向量做加权平均，当权因子选取适当时，加速效果显著。三、超松弛迭代法(SOR)

（SuccessiveOverRelaxationMethod）换个角度看Gauss-Seidel

方法：其中ri(m)=相当于在的基础上加个余项生成。=1Gauss-Seidel

法下面令，希望通过选取合适的来加速收敛，这就是逐次超松弛迭代法，简记SOR法

。称为松弛因子1.基本思想记则可以看作在前一步上加一个修正量。若在修正量前乘以一个因子,有2.SOR迭代矩阵对Gauss－Seidel迭代格式引入松弛因子整理得所以BSORg例3

用SOR法解方程组解从上表可见，本例的最佳松弛因子应该在1和1.1之间。k0.10.20.30.40.50.60.70.80.911637749342620151296k1.11.21.31.41.51.61.71.81.968101317223151105SOR方法收敛的快慢与松弛因子的选择有密切关系.但是如何选取最佳松弛因子,是一个尚未很好解决的问题.实际上可采用试算的方法来确定较好的松弛因子.当时，上式称为低松弛迭代法（SUR法），常用于使不收敛的迭代过程收敛；当时，上式称为超松弛迭代法（SOR法），常用于加速收敛的迭代过程；当时即为高斯-赛德尔迭代法。

经验上可取1.4<<1.6.几点说明迭代法：将方程组Ax=b变形为x=Bx+g，构造迭代公式任取初始向量x

(0)

，由迭代公式得序列{x

(k)}作为原方程组的近似解,这种方法为迭代法。B称为迭代矩阵。迭代法JacobiiterationGauss-SeideliterationSORiteration迭代原理从第i个方程中解出xi，以右边为初值，带入左边计算xi(k+1)时需要x(k)的i+1~n个分量对Gauss－Seidel迭代格式使用松弛因子迭代矩阵优缺点计算x(k+1)时需要x(k)的所有分量，因此需开两组存储单元分别存放x(k)和x(k+1)x(k+1)的前i个分量可存贮在x(k)的前i个分量所占的存储单元，无需开两组存储单元.选择合适的松弛因子，可加快收敛速度§3.2范数及方程组的性态、条件数

1．向量的范数定义1：设xRn，x

表示定义在Rn上的一个实值函数，称之为x的范数，它具有下列性质：（3）三角不等式：即对任意两个向量x、yRn，恒有

(1)

非负性：即对一切xRn，x0,x>0(2)

齐次性：即对任何实数aR，xRn，

设X=(x1,x2,…,xn)T，则有

（1）（2）（3）三个常用的范数：定理1：定义在Rn上的向量范数

是变量X分量的

一致连续函数。定理2：在Rn上定义的任一向量范数

都与范数

等价，

即存在正数

M

与m(M>m)

对一切XRn，不等式成立。推论：Rn上定义的任何两个范数都是等价的。

对常用范数，容易验证下列不等式：

定义1矩阵范数设A∈Rn×n，定义一个非负实值函数||A||，若满足：

(1)非负性：||A||≥0，且||A||=0当且仅当A=0；(2)齐次性：||aA||=|a|||A||，a∈R；则称||A||为A的矩阵范数。2．矩阵的范数(3)三角不等式：||A+B||≤||A||+||B||，A,B∈Rn×n;(4)相容性：；A,B∈Rn×n;定义2：设A为n

阶方阵，Rn中已定义了向量范数，

则称

为由向量范数导出的矩阵范数或模，

记为。矩阵范数与向量范数的相容性：||Ax||v||A||M·||x||v，xRn定理3：设n阶方阵A=(aij)nn，则（Ⅰ）与相容的矩阵范数是（Ⅱ）与相容的矩阵范数是其中1为矩阵ATA的最大特征值。（Ⅲ）与相容的矩阵范数是（行和范数）（列和范数）（谱范数(spectralnorm

)

）矩阵范数的基本性质：

（1）当A=0时，＝0，当A0时，>0（2）对任意实数和任意A，有（3）对任意两个n阶矩阵A、B有（4）对任意向量XRn，和任意矩阵A，有A

的范数与A

的特征值之间的关系定理4：矩阵A

的任一特征值的绝对值不超过A的范数。定义3：矩阵A的诸特征值的最大绝对值称为A的谱半径，记为：

定义：若方程组Ax=b的系数矩阵A与右端向量b的微小变化（小扰动）,将引起解向量x产生巨大变化，则称此方程组为病态方程组，其系数矩阵A称为病态矩阵，否则称Ax=b为良态方程组，称A为良态矩阵

.

方程组的病态程度与Ax=b对A和b的扰动的敏感程度有关。方程组的病态与良态是关键的误差放大因子，称为A的条件数，记为cond(A),越大，则A越病态，难得准确解。注:

1）cond(A)的具体大小与||·||的取法有关，但相对大小一致，常用的范数为:2）cond(A)取决于A，与解题方法无关。cond

(A)=||A||||A-1||cond

1(A)=||A||1||A-1||1，cond

2(A)特别地，A为对称矩阵时，（1）A可逆，则cond

p

(A)1；（2）A可逆，R

则cond(

A)=cond(A)；（3）A正交，则cond

2

(A)

=1；（4）A可逆，R正交，则cond

2

(RA)

=cond

2

(AR)=cond(A)2

。条件数的性质：精确解为例计算cond

2(A)

。A1=解：考察A

的特征根39206>>1定义2

设有矩阵序列及，如果则称收敛于A，记为定理1：若，称该迭代法收敛，否则称该迭代法发散定义1§3.3收敛性分析

定义3：（收敛矩阵）定理2：至少存在一种从属范数||·||<1定理3迭代法收敛的充要条件是迭代矩阵B的谱半径由迭代法收敛定义可得：所以，序列收敛与初值的选取无关

定理4（迭代法收敛的充分条件）若迭代矩阵B的某种范数||B||<1，则迭代法收敛。1.Jacobi迭代法与G-S迭代法收敛性Jacobi迭代法收敛G-S迭代法收敛定理1

定理2：若AX=b

的系数矩阵A∈R

nn为严格对角占优阵，则解此方程组的雅可比迭代法和高斯-赛德尔迭代法都收敛。定理3：若AX=b的系数矩阵A∈R

nn

为对称正定矩阵，则解此线性方程组的高斯-赛德尔迭代法收敛；Jacobi迭代收敛的充要条件为矩阵2D-A也对称正定注意的问题（2）Jacobi迭代法和Gauss-Seidel迭代法的收敛性没有必然的联系：即当Gauss-Seidel法收敛时，Jacobi法可能不收敛；而Jacobi法收敛时，

Gauss-Seidel法也可能不收敛。（1）Jacobi迭代法和Gauss-Seidel迭代法的迭代矩阵不同：BJ=D-1(L+U),B

G-S=(D-L)-1U用Jacobi迭代法求解收敛，但用G-S法不收敛。

BJ的特征值为0,0,0,而BG－S的特征值为0,2,2.例系数矩阵A是正定矩阵，因此用Gauss-Seidel法收敛不是正定矩阵，因此用Jacobi迭代法不收敛A是有正对角元的n阶对称矩阵例

定理2

若SOR方法收敛,则0<<2.

证设SOR方法收敛,则(B)<1,所以

|det(B)|=|12…n|<1

而

det(B)=det[(D-L)-1((1-)D+U)]

=det[(E-D-1L)-1]det[(1-)E+D-1U)]

=(1-)n于是

|1-|<1,或

0<<2定理1