第八节-雅可比与高斯-塞德尔迭代法课件

生成向量序列{x(k)

}，若称为迭代格式（1）的迭代矩阵。则有x*

=Bx*+f，即x*为原方程组Ax=b的解，B基本思想：将方程组Ax=b(|A|0)转化为与其

等价的方程组x=Bx+fx(k+1)=Bx(k)

+f（k=0,1,2,)

(1)取初始向量x(0)按下列迭代格式

第八节雅可比迭代法

与高斯—塞德尔迭代法生成向量序列{x(k)}，若称为迭代格式（1）的迭代矩阵序列{x(k)}的收敛条件，收敛速度，误差估计等。问题：如何构造迭代格式，迭代法产生的向量设方程组一、雅可比迭代法序列{x(k)}的收敛条件，收敛速度，误差估计等。问题：如何其中

aii0(i=1,2,…,n)等价方程组其中aii0(i=1,2,…,n)等建立迭代格式建立迭代格式

称为雅可比(Jacobi)迭代法，又称简单迭代法。或缩写为称为雅可比(Jacobi)迭代法，又称简单迭代法。记矩阵A=D-L-U

，其中记矩阵A=D-L-U，其中于是雅可比迭代法可写为矩阵形式其Jacobi迭代矩阵为B1=BJ=D-1(L+U)，即于是雅可比迭代法可写为矩阵形式其Jacobi迭代矩阵为B1例如已知线性方程组Ax=b的矩阵为其雅可比迭代矩阵为例如已知线性方程组Ax=b的矩阵为其雅可比迭代矩阵为在Jacobi

迭代中,计算xi(k+1)（2in）时,使用xj(k+1)代替xj(k)

（1ji-1），即建立迭代格式二、高斯——塞德尔迭代法在Jacobi迭代中,计算xi(k+1)（2i或缩写为称为高斯—塞德尔（Gauss—Seidel）迭代法。其G-S迭代矩阵为B2=BG=(D-L)-1U于是高斯—塞德尔迭代法可写为矩阵形式或缩写为称为高斯—塞德尔（Gauss—Seidel）迭代例如已知线性方程组Ax=b的矩阵为其G-S迭代矩阵为例如已知线性方程组Ax=b的矩阵为其G-S迭代矩阵为

例1

用雅可比迭代法解方程组解：Jacobi

迭代格式为精确解是例1用雅可比迭代法解方程组解：精确解是kx1(k)x2(k)x3(k)10.720.830.8420.9711.071.15…………111.0999931.1999931.299991121.0999981.1999981.299997

取计算如下kx1(k)x2(k)x3(k)10.720.830.842

解：

Gauss-Seidel迭代格式为

例2

用Gauss—Seidel迭代法解上题。解：例2用Gauss—Seidel迭代法解上取x(0)=(0,0,0)T

计算如下：kx1(k)

x2(k)x3(k)10.720.9021.1644…………81.0999981.1999991.3取x(0)=(0,0,0)T计算如下：kx1(k)x定理1

在下列任一条件下，雅克比迭代法收敛。三、迭代收敛的充分条件

定理1在下列任一条件下，雅克比迭代法收敛。三、迭代收敛定理2

设B1,B2分别为雅克比迭代矩阵与高斯—塞德尔迭代矩阵，则.从而，当时，高斯—塞德尔迭代法收敛。定义1

设n阶矩阵A=(aij)n×n，如果

则称矩阵A为行（或列）严格对角占优。或(证明见书P77)定理2设B1,B2分别为雅克比迭代矩阵与高斯—塞定理3若矩阵A行（或列）严格对角占优，则解线性方程组Ax=b的Jacobi

迭代法和Gauss-Seidel

迭代法均收敛

。

证

①设矩阵A行严格对角占优,由定理3若矩阵A行（或列）严格对角占优，则解线性方程由此根据第五节定理4知道(I-BJ)是非奇异矩阵，因此A=D(I-BJ)也是非奇异矩阵.因为所以Jacobi迭代收敛.所以有结论

若矩阵A行(或列)严格对角占优，则A是非奇异矩阵.由此根据第五节定理4知道(I-BJ)是非

②下面证明Gauss—Seidel迭代法收敛.，得

由下面证明||<1.若不然,即有使||1,则这说明(D-L)-U是奇异矩阵.②下面证明Gauss—Seidel迭代法收敛.，得是行严格对角占优矩阵,由结论知它是非奇异矩阵,这与式(1)矛盾,所以||<1,从而(BG)<1,即Gauss—Seidel迭代法收敛.即矩阵是行严格对角占优矩阵,由结论知它是非奇异矩阵,这与式(1

定理4

若A为正定矩阵，则方程组Ax=b的Gauss—Seidel迭代法收敛。证因为A是对称正定的,所以有A=D-L-LT,对BG

=(D-L)-1LT

，设为BG的特征值，

y为对应的特征向量，即有(D-L)-1LTy=

y，LTy=(D-L)y

，则[LTy,y]=[(D-L)y,y]从而定理4若A为正定矩阵，则方程组Ax=b的

因A正定，所以D正定，故设[D

y,y]=>0。所以||<1，从而(BG)<1，故Gauss—Seidel迭代法收敛。

令-[Ly,y]=a+ib，则由复向量内积的性质有因A正定，所以D正定，故设[Dy,y]=定理5

若Jacobi迭代矩阵BJ为非负矩阵，则下列关系有一个且仅有一个成立：(1)(BJ)=(BG)=0；(2)0<(BG)<(BJ)<1；(3)(BJ)=(BG)=1；(4)1<(BJ)<(BG).说明：当Jacobi

迭代矩阵BJ为非负矩阵时,

Jacobi

方法和

Gauss—Seidel

方法同时收敛或同时发散,若为同时收敛,则后者比前者收敛快。定理5若Jacobi迭代矩阵BJ为非负矩阵，

例

3

已知方程组判断雅可比迭代法和高斯—塞德尔法的敛散性？解雅可比迭代矩阵例3已知方程组判断雅可比迭代法和高斯—塞德尔法的故Jacobi迭代法收敛。

再由定理5

的

2)或由A是对称正定阵知Gauss—Seidel迭代法也收敛，且比Jacobi迭代法收敛得快。故Jacobi迭代法收敛。再由定理5的2)或由A生成向量序列{x(k)

}，若称为迭代格式（1）的迭代矩阵。则有x*

=Bx*+f，即x*为原方程组Ax=b的解，B基本思想：将方程组Ax=b(|A|0)转化为与其

等价的方程组x=Bx+fx(k+1)=Bx(k)

+f（k=0,1,2,)

(1)取初始向量x(0)按下列迭代格式

第八节雅可比迭代法

与高斯—塞德尔迭代法生成向量序列{x(k)}，若称为迭代格式（1）的迭代矩阵序列{x(k)}的收敛条件，收敛速度，误差估计等。问题：如何构造迭代格式，迭代法产生的向量设方程组一、雅可比迭代法序列{x(k)}的收敛条件，收敛速度，误差估计等。问题：如何其中

aii0(i=1,2,…,n)等价方程组其中aii0(i=1,2,…,n)等建立迭代格式建立迭代格式

称为雅可比(Jacobi)迭代法，又称简单迭代法。或缩写为称为雅可比(Jacobi)迭代法，又称简单迭代法。记矩阵A=D-L-U

，其中记矩阵A=D-L-U，其中于是雅可比迭代法可写为矩阵形式其Jacobi迭代矩阵为B1=BJ=D-1(L+U)，即于是雅可比迭代法可写为矩阵形式其Jacobi迭代矩阵为B1例如已知线性方程组Ax=b的矩阵为其雅可比迭代矩阵为例如已知线性方程组Ax=b的矩阵为其雅可比迭代矩阵为在Jacobi

迭代中,计算xi(k+1)（2in）时,使用xj(k+1)代替xj(k)

（1ji-1），即建立迭代格式二、高斯——塞德尔迭代法在Jacobi迭代中,计算xi(k+1)（2i或缩写为称为高斯—塞德尔（Gauss—Seidel）迭代法。其G-S迭代矩阵为B2=BG=(D-L)-1U于是高斯—塞德尔迭代法可写为矩阵形式或缩写为称为高斯—塞德尔（Gauss—Seidel）迭代例如已知线性方程组Ax=b的矩阵为其G-S迭代矩阵为例如已知线性方程组Ax=b的矩阵为其G-S迭代矩阵为

例1

用雅可比迭代法解方程组解：Jacobi

迭代格式为精确解是例1用雅可比迭代法解方程组解：精确解是kx1(k)x2(k)x3(k)10.720.830.8420.9711.071.15…………111.0999931.1999931.299991121.0999981.1999981.299997

取计算如下kx1(k)x2(k)x3(k)10.720.830.842

解：

Gauss-Seidel迭代格式为

例2

用Gauss—Seidel迭代法解上题。解：例2用Gauss—Seidel迭代法解上取x(0)=(0,0,0)T

计算如下：kx1(k)

x2(k)x3(k)10.720.9021.1644…………81.0999981.1999991.3取x(0)=(0,0,0)T计算如下：kx1(k)x定理1

在下列任一条件下，雅克比迭代法收敛。三、迭代收敛的充分条件

定理1在下列任一条件下，雅克比迭代法收敛。三、迭代收敛定理2

设B1,B2分别为雅克比迭代矩阵与高斯—塞德尔迭代矩阵，则.从而，当时，高斯—塞德尔迭代法收敛。定义1

设n阶矩阵A=(aij)n×n，如果

则称矩阵A为行（或列）严格对角占优。或(证明见书P77)定理2设B1,B2分别为雅克比迭代矩阵与高斯—塞定理3若矩阵A行（或列）严格对角占优，则解线性方程组Ax=b的Jacobi

迭代法和Gauss-Seidel

迭代法均收敛

。

证

①设矩阵A行严格对角占优,由定理3若矩阵A行（或列）严格对角占优，则解线性方程由此根据第五节定理4知道(I-BJ)是非奇异矩阵，因此A=D(I-BJ)也是非奇异矩阵.因为所以Jacobi迭代收敛.所以有结论

若矩阵A行(或列)严格对角占优，则A是非奇异矩阵.由此根据第五节定理4知道(I-BJ)是非

②下面证明Gauss—Seidel迭代法收敛.，得

由下面证明||<1.若不然,即有使||1,则这说明(D-L)-U是奇异矩阵.②下面证明Gauss—Seidel迭代法收敛.，得是行严格对角占优矩阵,由结论知它是非奇异矩阵,这与式(1)矛盾,所以||<1,从而(BG)<1,即Gauss—Seidel迭代法收敛.即矩阵是行严格对角占优矩阵,由结论知它是非奇异矩阵,这与式(1

定理4

若A为正定矩阵，则方程组Ax=b的Gauss—Seidel迭代法收敛。证因为A是对称正定的,所以有A=D-L-LT,对BG

=(D-L)-1LT

，设为BG的特征值，

y为对应的特征向量，即有(D-L)-1LTy=

y，LTy=(D-L)y

，则[LTy,y]=[(D-L)y,y]从而定理4若A为正定矩阵，则方程组Ax=b的

因