教学第2章线性方程组的迭代法课件

第2章解线性方程组的迭代法n元线性方程组（2.1）或

Ax=b思路与解f(x)=0的不动点迭代相似……,将Ax=b等价改写为x=Mx+f,建立迭代x(k+1)=Mx(k)+f,从初值x(0)出发，得到序列{x(k)}.研究内容：如何建立迭代格式？收敛速度？向量序列的收敛条件？误差估计？（2.2）1科大研究生学位课程第2章解线性方程组的迭代法n元线性方程组（2.1）2.1迭代法的一般理论

为了研究线性方程组近似解的误差估计和迭代法的收敛性，我们需要对Rn(n维向量空间)中的向量或Rnxn中矩阵的“大小”引入一种度量，——向量和矩阵的范数。在一维数轴上，实轴上任意一点x到原点的距离用|x|表示。而任意两点x1，x2之间距离用|x1-x2|表示。2科大研究生学位课程2.1迭代法的一般理论 为了研究线性方程组近似解的向量和矩阵的范数

而在二维平面上，平面上任意一点P(x,y)到原点的距离用表示。而平面上任意两点P1(x1,y1),P2(x2,y2)的距离用

表示。推广到n维空间，则称为向量范数。3科大研究生学位课程向量和矩阵的范数 而在二维平面上，平面上任意一点P(x,y)2.1.1向量和矩阵的范数向量的范数

定义2.2设‖‖是向量空间Rn上的实值函数,且满足条件:(1)非负性:对任何向量xRn

,‖x‖0,且‖x‖=0当且仅当x=0(2)齐次性:对任何向量x

Rn

和实数,

‖x‖=||‖x‖(3)三角不等式:对任何向量x,yRn

‖x+y‖‖x‖+‖y‖则称‖‖为空间Rn上的范数,‖x‖为向量x的范数.

4科大研究生学位课程2.1.1向量和矩阵的范数向量的范数定义2.2记x=(x1,x2,…,xn)T,常用的向量范数有:

向量的1-范数:‖x‖1=|x1|+|x2|+…+|xn|

向量的2-范数:‖x‖2=

向量的-范数:‖x‖=

例设向量x=(2,-4,3,1)T,求向量范数‖x‖p,p=1,2,.

解由定义‖x‖1=10,‖x‖2=

,‖x‖=4.虽然不同范数的值可能不同，但它们间存在等价关系.定理(范数的等价性)对于Rn上的任何两种范数‖‖和‖‖,存在正常数m,M,使得m‖x‖‖x‖

M‖x‖,xRn5科大研究生学位课程记x=(x1,x2,…,xn)T,常用的向量范数有常用的三种向量范数满足如下等价关系

‖x‖‖x‖1

n‖x‖,xRn定义设向量序列

k=1,2,…,向量如果

则称向量序列{x(k)}收敛于向量x*,记作

易见,

6科大研究生学位课程常用的三种向量范数满足如下等价关系定义2.矩阵的范数

定义2.3设‖‖是以n阶方阵为变量的实值函数,且满足条件:(1)非负性:‖A‖0,且‖A‖=0当且仅当A=0(2)齐次性:‖A‖=||‖A‖,R(3)三角不等式:‖A+B‖‖A‖+‖B‖(4)相容性:‖AB‖‖A‖‖B‖则称‖A‖为矩阵A的范数.

记A=(aij),常用的矩阵范数有:

矩阵的1-范数:‖A‖1

,也称矩阵的列范数.

矩阵的2-范数:‖A‖2

,也称为谱范数.7科大研究生学位课程2.矩阵的范数定义2.3设‖‖是以n阶方阵为变

矩阵的-范数:‖A‖

,也称为行范数.

矩阵的F-范数:‖A‖F

例设矩阵求矩阵A的范数‖A‖p,p=1,2,,F.

解

‖A‖1=4,‖A‖=5,‖A‖F8科大研究生学位课程矩阵的-范数:‖A‖,也称为行范数.矩设‖‖是一种向量范数,则定义称之为由向量范数派生的矩阵算子范数.矩阵的算子范数满足

‖Ax‖‖A‖‖x‖,xRn把满足上式的矩阵范数称为与向量范数相容的矩阵范数.对于p=1,2,,矩阵范数‖A‖p是由向量范数‖x‖p派生的矩阵算子范数,所以‖A‖p是与‖x‖p相容的矩阵范数.但‖A‖F不是一种算子范数,却与‖x‖2是相容的.设‖‖是一种算子范数,则9科大研究生学位课程设‖‖是一种向量范数,则定义称之为由向量范数派生矩阵的范数与矩阵的特征值之间也有密切的联系.设是矩阵A的特征值,x是对应的特征向量,则有

Ax=x利用向量和矩阵范数的相容性,则得||‖x‖=‖x‖=‖Ax‖‖A‖‖x‖于是||‖A‖设n阶矩阵A的n个特征值为1,2,…,n,则称为矩阵A的谱半径.对矩阵的任何一种相容范数都有(A)‖A‖另外,>0,一种相容范数,使‖A‖(A)+10科大研究生学位课程矩阵的范数与矩阵的特征值之间也有密切的联系.任何两种矩阵范数也具有等价性m‖A‖‖A‖

M‖A‖,ARnn矩阵序列的收敛性也定义为11科大研究生学位课程任何两种矩阵范数也具有等价性矩阵序列的收敛性12科大研究生学位课程12科大研究生学位课程把n元线性方程组（2.1）或

Ax=b改写成等价的方程组或x=Mx+f2.1.2迭代格式的构造

（2.2）13科大研究生学位课程把n元线性方程组（2.1）或Ax=b改写成等价由此建立方程组的迭代格式

x(k+1)=Mx(k)+f,k=0,1,2,…(2.5)其中M称为迭代矩阵。对任意取定的初始向量x(0),由(2.5)式可逐次算出迭代向量x(k),k=1,2,…,如果向量序列{x(k)}收敛于x*,由(2.5)式可得x*=Mx*+f

从而x*是方程组x=Mx+f的解,也就是方程组Ax=b的解.对迭代格式(2.5),定义误差向量

e(k)=x(k)-x*,则迭代法收敛就是e(k)0.由于

x(k+1)=Mx(k)+f

k=0,1,2,…

x*=Mx*+f

k=0,1,2,…14科大研究生学位课程由此建立方程组的迭代格式

x(k+1)=Mx(k)+f

k=0,1,2,…

x*=Mx*+f

k=0,1,2,…所以

e(k+1)=Me(k),

k=0,1,2,…递推可得

e(k)=Mke(0),

k=0,1,2,…可见,当k时,e(k)0MkO.对任意初始向量x(0),迭代法收敛(M)<1.定理2.4证:(必要性）若(M)<1,则存在>0,使得(M)+<1.则由定理2.2‖Mk‖‖M‖k((M)+)k0.若‖Mk‖0,k(M)=(Mk)‖Mk‖0,所以(M)<1.15科大研究生学位课程x(k+1)=Mx(k)+f

若‖M‖<1,则对任意x(0),迭代法收敛,而且

定理2.5-6

证由于

x(k+1)=Mx(k)+f,x(k)=Mx(k-1)+f

x*=Mx*+f所以

x(k+1)-x(k)=M(x

(k)-x(k-1)),x(k+1)–x*=M(x

(k)–x*)于是有

‖x(k+1)-x(k)‖‖M‖‖x

(k)-x(k-1)‖

‖x(k+1)–x*‖‖M‖‖x

(k)–x*‖

‖x(k+1)-x(k)‖=‖(x

(k+1)–x*)-(x(k)–x*)‖‖x

(k)–x*‖-‖x(k+1)–x*‖(1-‖M‖)‖x(k)–x*‖16科大研究生学位课程若‖M‖<1,则对任意x(0),迭代所以上述定理只是收敛的充分条件,并不必要,如则‖M‖1=1.2,‖M‖=1.3,‖M‖2=1.09,‖M‖F=1.17但(M)=0.8<1,所以迭代法是收敛的.由(2.10)式可见,‖M‖越小收敛越快,且当‖x

(k)-x(k-1)‖很小时,‖x(k)–x*‖就很小,实际上用‖x

(k)-x(k-1)‖<作为迭代终止的条件.17科大研究生学位课程所以上述定理只是收敛的充分条件,并不必要,如则‖M‖1,即若使‖x(k)–x*‖<,只需可以事先估计达到某一精度需要迭代多少步.线性方程组的迭代法主要有Jocobi迭代法、Gauss-Seidel迭代法和超松弛(Sor)迭代法.18科大研究生学位课程

2.2．雅克比（Jacobi）迭代法若系数矩阵非奇异，且

(i=1,2,…,n)，将方程组改成19科大研究生学位课程2.2．雅克比（Jacobi）迭代法若系数矩阵非奇异，且然后写成迭代格式（2.11）（2.11）式也可以简单地写为（2.11’）20科大研究生学位课程然后写成迭代格式（2.11）（2.11）式也可以简单地写为（写成矩阵形式：A=－L－UDBJacobi迭代阵(2.12)21科大研究生学位课程写成矩阵形式：A=－L－UDBJacobi迭代阵(2.1算法2.1（Jacobi迭代法）：程序见P19。22科大研究生学位课程算法2.1（Jacobi迭代法）：程序见P19。22科大研究2.2.2Jacobi迭代法的收敛条件迭代格式收敛(B)<1

。若‖B‖<1迭代法收敛.定理：若系数矩阵A满足下列条件之一，则Jacobi迭代收敛。①A为行对角占优阵②A为列对角占优阵③A满足对于Jacobi迭代，我们有一些保证收敛的充分条件.

引理若A是严格对角占优矩阵,则det(A)0.

证

A=D-L-U=D(I-D-1(L+U))=因为A是严格对角占优矩阵,所以det(D)0,而且因此,(B)‖B‖<1,故=1不是B的特征值,det(I-B)0.所以,det(A)0.D(I-B)23科大研究生学位课程2.2.2Jacobi迭代法的收敛条件迭代格式收敛证明：③由条件知，A为列对角占优阵，则AT为行对角占优阵，有＃证毕①A为行对角占优阵②A为列对角占优阵24科大研究生学位课程证明：③由条件知，A为列对角占优阵，则AT为行对角占优阵，为了加快收敛速度，同时为了节省计算机的内存，我们作如下的改进：每算出一个分量的近似值，立即用到下一个分量的计算中去，即用迭代格式：

2.3高斯――赛得尔(Gauss-Seidel)迭代法逐一写出来即为25科大研究生学位课程2.3高斯――赛得尔(Gauss-S…………只存一组向量即可。写成矩阵形式：BGauss-Seidel迭代阵2.3高斯――赛得尔(Gauss-Seidel)迭代法(2.14)(2.16)26科大研究生学位课程…………只存一组向量即可。写成矩阵形程序见P23。算法2.2（Gauss-Seidel迭代法）：27科大研究生学位课程程序见P23。算法2.2（Gauss-Seidel迭代法）：

例用雅可比迭代法解方程组解：雅可比迭代格式为28科大研究生学位课程例用雅可比迭代法解方程组解：雅28科大研究生学位课kx1(k)

x2(k)x3(k)10.720.830.8420.9711.071.15…………111.0999931.1999931.299991121.0999981.1999981.299997取计算如下29科大研究生学位课程kx1(k)x2(k)x3(k)10.720.830.84

解：Gauss-Seidel

迭代格式为

例用Gauss—Seidel迭代法解上题。30科大研究生学位课程Gauss-Seidel迭代格式为例用Gaus取x(0)=(0,0,0)T

计算如下：kx1(k)

x2(k)x3(k)10.720.9021.1644…………81.0999981.1999991.331科大研究生学位课程kx1(k)x2(k)x3(k)10.720.9021.12.3.2收敛条件我们看一下Gauss-Seidel迭代法收敛的充分条件定理：若A满足下列条件之一，则Seidel

i迭代收敛。①A为行或列对角占优阵②A对称正定阵（证略书上定理2.9）迭代格式收敛(B)<1

。若‖B‖<1迭代法收敛.

det(I-B)=det(I-(D-L)-1U)证明：=det((D-L)-1)det((D-L)-U)=0所以有det((D-L)-U)=032科大研究生学位课程2.3.2收敛条件我们看一下Gauss-Seidel迭若||1,则矩阵(D-L)-U是严格对角占优矩阵,这与det((D-L)-U)=0矛盾,所以||<1,于是(B)<1.注：二种方法都存在收敛性问题。有例子表明：Gauss-Seidel法收敛时，Jacobi法可能不收敛；而Jacobi法收敛时，Gauss-Seidel法也可能不收敛。33科大研究生学位课程若||1,则矩阵(D-L)-U是2.4逐次超松弛迭代法记则可以看作在前一步上加一个修正量。若在修正量前乘以一个因子，有对Gauss－Seidel迭代格式(2.22)34科大研究生学位课程2.4逐次超松弛迭代法记则可以看作在前一步上加一个修正量。故SOR的迭代格式（2.23）SOR的迭代矩阵35科大研究生学位课程故SOR的迭代格式（2.23）SOR的迭代矩阵35科大研究生用分量形式讨论，设加速（迭代公式）是松驰因子(0<<2),当0<<1时叫低松弛，>1时叫超松弛，=1时，就是Gauss-Seidel迭代法。36科大研究生学位课程用分量形式讨论，设加速（迭代公式）是松驰因子(0<<2)程序见P28。算法2.3（SOR迭代法）：37科大研究生学位课程程序见P28。算法2.3（SOR迭代法）：37科大研究生学位例用SOR方法解线性方程组解SOR方法迭代公式为方程组的精确解是x*=(2,1,-1)T.取x(0)=(0,0,0)T,=1.46,计算结果如下:38科大研究生学位课程例用SOR方法解线性方程组解SOR方法迭代公式为方程kx1(k)x2(k)x3(k)0123…2003.652.321669102.5661399……1.999998700.88458820.42309390.6948261……1.00000130-0.2021098-0.22243214-0.4952594……-1.0000034从结果可见,迭代20次时已获得精确到小数点后五位的近似解.如果取=1.25,则需要迭代56次才能得到具有同样精度的近似解;如果取=1,则需迭代110次以上.39科大研究生学位课程kx1(k)x2(k)x3(k)0000从结果可见2.4.2SOR迭代法的收敛条件迭代格式收敛(B)<1

。若‖B‖<1迭代法收敛.对于SOR迭代，我们有一些收敛的结果.定理2.10

SOR方法收敛的必要条件是0<<2.证设SOR方法收敛,则(B)<1,所以|det(B)|=|12…n|<1而det(B)=det[(D-L)-1((1-)D+U)]=det[(I-D-1L)-1]det[(1-)I+D-1U)]=(1-)n于是|1-|<1,或0<<240科大研究生学位课程2.4.2SOR迭代法的收敛条件迭代格式

定理2.11设A是对称正定矩阵,则当0<<2时,解方程组Ax=b的SOR方法收敛.

证设是B的任一特征值,y是对应的特征向量,则[(1-)D+U]y=(D-L)y于是(1-)(Dy,y)+(Uy,y)=[(Dy,y)-(Ly,y)]由于A=D-L-U是对称正定的,所以D是正定矩阵,且L=UT.若记(Ly,y)=+i,则有(Dy,y)=>041科大研究生学位课程定理2.11设A是对称正定矩阵,则当0<<2时(Dy,y)=>0(Uy,y)=(y,Ly)=(Ly,y)=-i0<(Ay,y)=(Dy,y)-(Ly,y)-(Uy,y)=-2所以当0<<2时,有(-+)2-(-)2=(2-)(2-)=(2-)(2-)<0所以||2<1,因此(B)<1,即S0R方法收敛.42科大研究生学位课程(Dy,y)=>0(Uy,y)=(y,Ly)=(Ly

推论2.1

A是对称正定矩阵,Jacobi迭代法收敛的充要条件是2D-A也对称正定。

证设是Jacobi迭代矩阵B的任一特征值,y是对应的特征向量,则(L+U)y=Dy于是(Ly,y)+(Uy,y)=(Dy,y)可得=2/当A对称正定时,即2-<0时,||<12+>0而((2D-A)y,y)=(Dy,y)+(Ly,y)+(Uy,y)=+2即,当A对称正定时,Jacobi迭代法收敛2D-A正定.43科大研究生学位课程推论2.1A是对称正定矩阵,Jacobi迭代法收

SOR方法收敛的快慢与松弛因子的选择有密切关系.但是如何选取最佳松弛因子,即选取=*,使(B)达到最小,是一个尚未很好解决的问题.实际上可采用试算的方法来确定较好的松弛因子.经验上可取1.4<<1.6.44科大研究生学位课程SOR方法收敛的快慢与松弛因子的选择有密切关系.第2章解线性方程组的迭代法n元线性方程组（2.1）或

Ax=b思路与解f(x)=0的不动点迭代相似……,将Ax=b等价改写为x=Mx+f,建立迭代x(k+1)=Mx(k)+f,从初值x(0)出发，得到序列{x(k)}.研究内容：如何建立迭代格式？收敛速度？向量序列的收敛条件？误差估计？（2.2）45科大研究生学位课程第2章解线性方程组的迭代法n元线性方程组（2.1）2.1迭代法的一般理论

为了研究线性方程组近似解的误差估计和迭代法的收敛性，我们需要对Rn(n维向量空间)中的向量或Rnxn中矩阵的“大小”引入一种度量，——向量和矩阵的范数。在一维数轴上，实轴上任意一点x到原点的距离用|x|表示。而任意两点x1，x2之间距离用|x1-x2|表示。46科大研究生学位课程2.1迭代法的一般理论 为了研究线性方程组近似解的向量和矩阵的范数

而在二维平面上，平面上任意一点P(x,y)到原点的距离用表示。而平面上任意两点P1(x1,y1),P2(x2,y2)的距离用

表示。推广到n维空间，则称为向量范数。47科大研究生学位课程向量和矩阵的范数 而在二维平面上，平面上任意一点P(x,y)2.1.1向量和矩阵的范数向量的范数

定义2.2设‖‖是向量空间Rn上的实值函数,且满足条件:(1)非负性:对任何向量xRn

,‖x‖0,且‖x‖=0当且仅当x=0(2)齐次性:对任何向量x

Rn

和实数,

‖x‖=||‖x‖(3)三角不等式:对任何向量x,yRn

‖x+y‖‖x‖+‖y‖则称‖‖为空间Rn上的范数,‖x‖为向量x的范数.

48科大研究生学位课程2.1.1向量和矩阵的范数向量的范数定义2.2记x=(x1,x2,…,xn)T,常用的向量范数有:

向量的1-范数:‖x‖1=|x1|+|x2|+…+|xn|

向量的2-范数:‖x‖2=

向量的-范数:‖x‖=

例设向量x=(2,-4,3,1)T,求向量范数‖x‖p,p=1,2,.

解由定义‖x‖1=10,‖x‖2=

,‖x‖=4.虽然不同范数的值可能不同，但它们间存在等价关系.定理(范数的等价性)对于Rn上的任何两种范数‖‖和‖‖,存在正常数m,M,使得m‖x‖‖x‖

M‖x‖,xRn49科大研究生学位课程记x=(x1,x2,…,xn)T,常用的向量范数有常用的三种向量范数满足如下等价关系

‖x‖‖x‖1

n‖x‖,xRn定义设向量序列

k=1,2,…,向量如果

则称向量序列{x(k)}收敛于向量x*,记作

易见,

50科大研究生学位课程常用的三种向量范数满足如下等价关系定义2.矩阵的范数

定义2.3设‖‖是以n阶方阵为变量的实值函数,且满足条件:(1)非负性:‖A‖0,且‖A‖=0当且仅当A=0(2)齐次性:‖A‖=||‖A‖,R(3)三角不等式:‖A+B‖‖A‖+‖B‖(4)相容性:‖AB‖‖A‖‖B‖则称‖A‖为矩阵A的范数.

记A=(aij),常用的矩阵范数有:

矩阵的1-范数:‖A‖1

,也称矩阵的列范数.

矩阵的2-范数:‖A‖2

,也称为谱范数.51科大研究生学位课程2.矩阵的范数定义2.3设‖‖是以n阶方阵为变

矩阵的-范数:‖A‖

,也称为行范数.

矩阵的F-范数:‖A‖F

例设矩阵求矩阵A的范数‖A‖p,p=1,2,,F.

解

‖A‖1=4,‖A‖=5,‖A‖F52科大研究生学位课程矩阵的-范数:‖A‖,也称为行范数.矩设‖‖是一种向量范数,则定义称之为由向量范数派生的矩阵算子范数.矩阵的算子范数满足

‖Ax‖‖A‖‖x‖,xRn把满足上式的矩阵范数称为与向量范数相容的矩阵范数.对于p=1,2,,矩阵范数‖A‖p是由向量范数‖x‖p派生的矩阵算子范数,所以‖A‖p是与‖x‖p相容的矩阵范数.但‖A‖F不是一种算子范数,却与‖x‖2是相容的.设‖‖是一种算子范数,则53科大研究生学位课程设‖‖是一种向量范数,则定义称之为由向量范数派生矩阵的范数与矩阵的特征值之间也有密切的联系.设是矩阵A的特征值,x是对应的特征向量,则有

Ax=x利用向量和矩阵范数的相容性,则得||‖x‖=‖x‖=‖Ax‖‖A‖‖x‖于是||‖A‖设n阶矩阵A的n个特征值为1,2,…,n,则称为矩阵A的谱半径.对矩阵的任何一种相容范数都有(A)‖A‖另外,>0,一种相容范数,使‖A‖(A)+54科大研究生学位课程矩阵的范数与矩阵的特征值之间也有密切的联系.任何两种矩阵范数也具有等价性m‖A‖‖A‖

M‖A‖,ARnn矩阵序列的收敛性也定义为55科大研究生学位课程任何两种矩阵范数也具有等价性矩阵序列的收敛性56科大研究生学位课程12科大研究生学位课程把n元线性方程组（2.1）或

Ax=b改写成等价的方程组或x=Mx+f2.1.2迭代格式的构造

（2.2）57科大研究生学位课程把n元线性方程组（2.1）或Ax=b改写成等价由此建立方程组的迭代格式

x(k+1)=Mx(k)+f,k=0,1,2,…(2.5)其中M称为迭代矩阵。对任意取定的初始向量x(0),由(2.5)式可逐次算出迭代向量x(k),k=1,2,…,如果向量序列{x(k)}收敛于x*,由(2.5)式可得x*=Mx*+f

从而x*是方程组x=Mx+f的解,也就是方程组Ax=b的解.对迭代格式(2.5),定义误差向量

e(k)=x(k)-x*,则迭代法收敛就是e(k)0.由于

x(k+1)=Mx(k)+f

k=0,1,2,…

x*=Mx*+f

k=0,1,2,…58科大研究生学位课程由此建立方程组的迭代格式

x(k+1)=Mx(k)+f

k=0,1,2,…

x*=Mx*+f

k=0,1,2,…所以

e(k+1)=Me(k),

k=0,1,2,…递推可得

e(k)=Mke(0),

k=0,1,2,…可见,当k时,e(k)0MkO.对任意初始向量x(0),迭代法收敛(M)<1.定理2.4证:(必要性）若(M)<1,则存在>0,使得(M)+<1.则由定理2.2‖Mk‖‖M‖k((M)+)k0.若‖Mk‖0,k(M)=(Mk)‖Mk‖0,所以(M)<1.59科大研究生学位课程x(k+1)=Mx(k)+f

若‖M‖<1,则对任意x(0),迭代法收敛,而且

定理2.5-6

证由于

x(k+1)=Mx(k)+f,x(k)=Mx(k-1)+f

x*=Mx*+f所以

x(k+1)-x(k)=M(x

(k)-x(k-1)),x(k+1)–x*=M(x

(k)–x*)于是有

‖x(k+1)-x(k)‖‖M‖‖x

(k)-x(k-1)‖

‖x(k+1)–x*‖‖M‖‖x

(k)–x*‖

‖x(k+1)-x(k)‖=‖(x

(k+1)–x*)-(x(k)–x*)‖‖x

(k)–x*‖-‖x(k+1)–x*‖(1-‖M‖)‖x(k)–x*‖60科大研究生学位课程若‖M‖<1,则对任意x(0),迭代所以上述定理只是收敛的充分条件,并不必要,如则‖M‖1=1.2,‖M‖=1.3,‖M‖2=1.09,‖M‖F=1.17但(M)=0.8<1,所以迭代法是收敛的.由(2.10)式可见,‖M‖越小收敛越快,且当‖x

(k)-x(k-1)‖很小时,‖x(k)–x*‖就很小,实际上用‖x

(k)-x(k-1)‖<作为迭代终止的条件.61科大研究生学位课程所以上述定理只是收敛的充分条件,并不必要,如则‖M‖1,即若使‖x(k)–x*‖<,只需可以事先估计达到某一精度需要迭代多少步.线性方程组的迭代法主要有Jocobi迭代法、Gauss-Seidel迭代法和超松弛(Sor)迭代法.62科大研究生学位课程

2.2．雅克比（Jacobi）迭代法若系数矩阵非奇异，且

(i=1,2,…,n)，将方程组改成63科大研究生学位课程2.2．雅克比（Jacobi）迭代法若系数矩阵非奇异，且然后写成迭代格式（2.11）（2.11）式也可以简单地写为（2.11’）64科大研究生学位课程然后写成迭代格式（2.11）（2.11）式也可以简单地写为（写成矩阵形式：A=－L－UDBJacobi迭代阵(2.12)65科大研究生学位课程写成矩阵形式：A=－L－UDBJacobi迭代阵(2.1算法2.1（Jacobi迭代法）：程序见P19。66科大研究生学位课程算法2.1（Jacobi迭代法）：程序见P19。22科大研究2.2.2Jacobi迭代法的收敛条件迭代格式收敛(B)<1

。若‖B‖<1迭代法收敛.定理：若系数矩阵A满足下列条件之一，则Jacobi迭代收敛。①A为行对角占优阵②A为列对角占优阵③A满足对于Jacobi迭代，我们有一些保证收敛的充分条件.

引理若A是严格对角占优矩阵,则det(A)0.

证

A=D-L-U=D(I-D-1(L+U))=因为A是严格对角占优矩阵,所以det(D)0,而且因此,(B)‖B‖<1,故=1不是B的特征值,det(I-B)0.所以,det(A)0.D(I-B)67科大研究生学位课程2.2.2Jacobi迭代法的收敛条件迭代格式收敛证明：③由条件知，A为列对角占优阵，则AT为行对角占优阵，有＃证毕①A为行对角占优阵②A为列对角占优阵68科大研究生学位课程证明：③由条件知，A为列对角占优阵，则AT为行对角占优阵，为了加快收敛速度，同时为了节省计算机的内存，我们作如下的改进：每算出一个分量的近似值，立即用到下一个分量的计算中去，即用迭代格式：

2.3高斯――赛得尔(Gauss-Seidel)迭代法逐一写出来即为69科大研究生学位课程2.3高斯――赛得尔(Gauss-S…………只存一组向量即可。写成矩阵形式：BGauss-Seidel迭代阵2.3高斯――赛得尔(Gauss-Seidel)迭代法(2.14)(2.16)70科大研究生学位课程…………只存一组向量即可。写成矩阵形程序见P23。算法2.2（Gauss-Seidel迭代法）：71科大研究生学位课程程序见P23。算法2.2（Gauss-Seidel迭代法）：

例用雅可比迭代法解方程组解：雅可比迭代格式为72科大研究生学位课程例用雅可比迭代法解方程组解：雅28科大研究生学位课kx1(k)

x2(k)x3(k)10.720.830.8420.9711.071.15…………111.0999931.1999931.299991121.0999981.1999981.299997取计算如下73科大研究生学位课程kx1(k)x2(k)x3(k)10.720.830.84

解：Gauss-Seidel

迭代格式为

例用Gauss—Seidel迭代法解上题。74科大研究生学位课程Gauss-Seidel迭代格式为例用Gaus取x(0)=(0,0,0)T

计算如下：kx1(k)

x2(k)x3(k)10.720.9021.1644…………81.0999981.1999991.375科大研究生学位课程kx1(k)x2(k)x3(k)10.720.9021.12.3.2收敛条件我们看一下Gauss-Seidel迭代法收敛的充分条件定理：若A满足下列条件之一，则Seidel

i迭代收敛。①A为行或列对角占优阵②A对称正定阵（证略书上定理2.9）迭代格式收敛(B)<1

。若‖B‖<1迭代法收敛.

det(I-B)=det(I-(D-L)-1U)证明：=det((D-L)-1)det((D-L)-U)=0所以有det((D-L)-U)=076科大研究生学位课程2.3.2收敛条件我们看一下Gauss-Seidel迭若||1,则矩阵(D-L)-U是严格对角占优矩阵,这与det((D-L)-U)=0矛盾,所以||<1,于是(B)<1.注：二种方法都存在收敛性问题。有例子表明：Gauss-Seidel法收敛时，Jacobi法可能不收敛；而Jacobi法收敛时，Gauss-Seidel法也可能不收敛。77科大研究生学位课程若||1,则矩阵(D-L)-U是2.4逐次超松弛迭代法记则可以看作在前一步上加一个修正量。若在修正量前乘以一个因子，有对Gauss－Seidel迭代格式(2.22)78科大研究生学位课程2.4逐次超松弛迭代法记则可以看作在前一步上加一个修正量。故SOR的迭代格式（2.23）SOR的迭代矩阵79科大研究生学位课程故SOR的迭代格式（2.23）SOR的迭代矩阵35科大研究生用分量形式讨论，设加速（迭代公式）是松驰因子(0<<2),当0<<1时叫低松弛，>1时叫超松弛，=1时，就是Gauss-Seidel迭代法。80科大研究生学位课程用分量形式讨论，设加速（迭代公式）是松驰因子(0<<2)程序见P28。算法2.3（SOR迭代法）：81科大研究生学位课程程序见P28。算法2.3（SOR迭代法）