数值分析~第2章 线性方程组的迭代法yjs11

第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章2.1迭代法的一般理论

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

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

表示。推广到n维空间，则称为向量范数。3数值分析第2章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章记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数值分析第2章常用的三种向量范数满足如下等价关系

‖x‖‖x‖1

n‖x‖,xRn定义

设向量序列

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

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

易见,

6数值分析第2章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章

矩阵的-范数:‖A‖

,也称为行范数.

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

例

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

解

‖A‖1=4,‖A‖=5,‖A‖F8数值分析第2章设‖‖是一种向量范数,则定义称之为由向量范数派生的矩阵算子范数.

矩阵的算子范数满足

‖Ax‖‖A‖‖x‖,xRn把满足上式的矩阵范数称为与向量范数相容的矩阵范数.

对于p=1,2,,矩阵范数‖A‖p是由向量范数‖x‖p派生的矩阵算子范数,所以‖A‖p是与‖x‖p相容的矩阵范数.但‖A‖F不是一种算子范数,却与‖x‖2是相容的.设‖‖是一种算子范数,则9数值分析第2章矩阵的范数与矩阵的特征值之间也有密切的联系.设是矩阵A的特征值,x是对应的特征向量,则有

Ax=x利用向量和矩阵范数的相容性,则得

||‖x‖=‖x‖=‖Ax‖‖A‖‖x‖于是||‖A‖设n阶矩阵A的n个特征值为1,2,…,n,则称

为矩阵A的谱半径.

定理2.1对矩阵的任何一种相容范数都有

(A)‖A‖另外,定理2.2：对

>0,一种相容范数,使‖A‖(A)+.10数值分析第2章

任何两种矩阵范数也具有等价性

m‖A‖‖A‖

M‖A‖,ARnn

矩阵序列的收敛性也定义为

证若‖Ak‖0,则k(A)=(Ak)‖Ak‖0,所以(A)<1.

若(A)<1,则存在>0,使得(A)+<1.则定理设A是一n*n的矩阵,则

的充分必要条件是(A)<1.‖Ak‖‖A‖k

((A)+)k

0.（定理2.2）11数值分析第2章12数值分析第2章把n元线性方程组

（2.1）

或

Ax=b改写成等价的方程组

或x=Mx+f2.1.2迭代格式的构造

（2.2）

13数值分析第2章由此建立方程组的迭代格式

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数值分析第2章

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)0Mk

O.

对任意初始向量x(0),迭代法收敛(M)<1.定理2.4证:(必要性）

若(M)<1,则存在>0,使得(M)+<1.则由定理2.2若‖Mk‖0,k(M)=(Mk)‖M

k‖0,所以(M)<1.2.1.3迭代的收敛性‖Mk‖‖M‖k

((M)+)k0.15数值分析第2章

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

定理2.5-6证:先证式(2.10).考虑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数值分析第2章上述定理只是收敛的充分条件,并不必要,如则‖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)‖<作为迭代终止的条件.若使‖x(k)–x*‖<,只需即可以事先估计达到某一精度需要迭代多少步.17数值分析第2章2.2．雅克比（Jacobi）迭代法若系数矩阵非奇异，且

(i=1,2,…,n)，将方程组改成18数值分析第2章然后写成迭代格式（2.11）（2.11）式也可以简单地写为（2.11’）19数值分析第2章写成矩阵形式：A=－L－UDBJacobi迭代阵(2.12)20数值分析第2章算法2.1（Jacobi迭代法）：程序见P19。举例2.11.输入矩阵A=(aij),b=(b1,…,bn),初始向量x(0)=(x1(0),…,xn(0)),精度要求ε，最大的迭代次数N，置k=0;

2.对i=1,2,…,n,计算3.若‖x(k+1)-x(k)‖<ε,则停算，输出x(k+1)为近似解；否则，转4

4.若k<N,置k:=k+1,转步2；否则，停算，输出迭代失败信息.

21数值分析第2章2.2.2Jacobi迭代法的收敛条件迭代格式收敛(B)<1

。若‖B‖<1迭代法收敛.定理2.7：若系数矩阵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)22数值分析第2章证明：③

由条件知，A为列对角占优阵，则AT为行对角占优阵，有＃证毕①A为行对角占优阵②A为列对角占优阵23数值分析第2章例设线性方程组Ax=b的系数矩阵其中a为参数，问a为何值时，Jacobi迭代法收敛？所以，Jacobi迭代迭代矩阵为求BJ的特征根24数值分析第2章若用充分条件显然，充分条件比充要条件弱。25数值分析第2章为了加快收敛速度，同时为了节省计算机的内存，我们作如下的改进：每算出一个分量的近似值，立即用到下一个分量的计算中去，即用迭代格式：

2.3高斯――赛得尔(Gauss-Seidel)迭代法逐一写出来即为26数值分析第2章…………只存一组向量即可。写成矩阵形式：BGauss-Seidel

迭代阵(2.14)(2.16)27数值分析第2章程序见P23。算法2.2（Gauss-Seidel迭代法）：1.输入矩阵A=(aij),b=(b1,…,bn),初始向量x(0)=(x1(0),…,xn(0)),精度要求ε，最大的迭代次数N，置k=0;

2.计算对i=2,…,n-1,计算3.若‖x(k+1)-x(k)‖<ε,则停算，输出x(k+1)为近似解；否则，转4

4.若k<N,置k:=k+1,转步2；否则，停算，输出迭代失败信息.

28数值分析第2章

例

用雅可比迭代法解方程组解：雅可比迭代格式为29数值分析第2章kx1(k)

x2(k)x3(k)10.720.830.8420.9711.071.15…………111.0999931.1999931.299991121.0999981.1999981.299997取计算如下30数值分析第2章

解：Gauss-Seidel迭代格式

例

用Gauss—Seidel迭代法解上题。31数值分析第2章取x(0)=(0,0,0)T

计算如下：kx1(k)

x2(k)x3(k)10.720.9021.1644…………81.0999981.1999991.332数值分析第2章2.3.2Gauss-Seidel迭代法收敛条件考察Gauss-Seidel迭代法收敛的充分条件定理：若A满足下列条件之一，则Seideli迭代收敛。①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)=0若||1,

则矩阵(D-L)-U

是严格对角占优矩阵,这与det((D-L)-U)=0矛盾,所以||<1,于是(B)<1.33数值分析第2章注：二种方法都存在收敛性问题。有例子表明：Gauss-Seidel法收敛时，Jacobi法可能不收敛；而Jacobi法收敛时，Gauss-Seidel法也可能不收敛。例设线性方程组Ax=b的系数矩阵判断解Ax=b的Jacobi迭代法和G-S迭代法的收敛性。解：易见A是严格对角占优矩阵，故J法和G-S法收敛。34数值分析第2章1、Jacobi迭代的迭代矩阵特征值为2、Gauss－Siedel迭代例已知方程组的系数矩阵判断解Ax=b的Jacobi迭代法和G-S迭代法的收敛性。35数值分析第2章2.4逐次超松弛迭代法记则可以看作在前一步上加一个修正量。若在修正量前乘以一个因子，有对Gauss－Seidel迭代格式有(2.22)故SOR(SuccessiveOverRelaxation)的迭代格式（2.23）36数值分析第2章SOR的迭代矩阵用分量形式讨论，设松弛（2.24）是松驰因子(0<<2),当0<<1时叫低松弛，>1时叫超松弛，=1时，就是Gauss-Seidel迭代法。37数值分析第2章程序见P28。算法2.3（SOR迭代法）1.输入矩阵A=(aij),b=(b1,…,bn),初始向量x(0)=(x1(0),…,xn(0)),精度要求ε，最大的迭代次数N，参数ω；置k=0;

2.计算对i=2,…,n-1,计算3.若‖x(k+1)-x(k)‖<ε,则停算，输出x(k+1)为近似解；否则，转4

4.若k<N,置k:=k+1,转步2；否则，停算，输出迭代失败信息.

38数值分析第2章

例用SOR方法解线性方程组解SOR方法迭代公式(2.24)为方程组的精确解是x*=(2,1,-1)T.取x(0)=(0,0,0)T,=1.46,计算结果如下:39数值分析第2章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次以上.40数值分析第2章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<<241数值分析第2章

定理2.11

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

证设是B的任一特征值,y是对应的特征向量(复向量),则[(1-)D+U]y=

(D-L)y于是作内积，有(1-)(Dy,