线性方程组的迭代法yjs10n名师优质课赛课一等奖市公开课获奖课件

第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页1科大硕士学位课程2.1迭代法普通理论

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

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

表示。推广到n维空间，则称为向量范数。第3页3科大硕士学位课程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页4科大硕士学位课程记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‖,xRn第5页5科大硕士学位课程惯用三种向量范数满足以下等价关系

‖x‖‖x‖1

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

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

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

易见,

第6页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页7科大硕士学位课程

矩阵-范数:‖A‖

,也称为行范数.

矩阵F-范数:‖A‖F

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

解

‖A‖1=4,‖A‖=5,‖A‖F第8页8科大硕士学位课程设‖‖是一个向量范数,则定义称之为由向量范数派生矩阵算子范数.矩阵算子范数满足

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

Ax=x利用向量和矩阵范数相容性,则得||‖x‖=‖x‖=‖Ax‖‖A‖‖x‖于是||‖A‖设n阶矩阵An个特征值为1,2,…,n,则称为矩阵A谱半径.对矩阵任何一个相容范数都有(A)‖A‖另外,>0,一个相容范数,使‖A‖(A)+第10页10科大硕士学位课程任何两种矩阵范数也含有等价性m‖A‖‖A‖

M‖A‖,ARnn矩阵序列收敛性也定义为第11页11科大硕士学位课程第12页12科大硕士学位课程把n元线性方程组（2.1）或

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

（2.2）第13页13科大硕士学位课程由此建立方程组迭代格式

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页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页15科大硕士学位课程

若‖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页16科大硕士学位课程所以上述定理只是收敛充分条件,并无须要,如则‖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页17科大硕士学位课程,即若使‖x(k)–x*‖<,只需能够事先预计到达某一精度需要迭代多少步.线性方程组迭代法主要有Jocobi迭代法、Gauss-Seidel迭代法和超松弛(Sor)迭代法.第18页18科大硕士学位课程2.2．雅克比（Jacobi）迭代法若系数矩阵非奇异，且

(i=1,2,…,n)，将方程组改成第19页19科大硕士学位课程然后写成迭代格式（2.11）（2.11）式也能够简单地写为（2.11’）第20页20科大硕士学位课程写成矩阵形式：A=－L－UDBJacobi迭代阵(2.12)第21页21科大硕士学位课程算法2.1（Jacobi迭代法）：程序见P19。第22页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页23科大硕士学位课程证实：③由条件知，A为列对角占优阵，则AT为行对角占优阵，有＃证毕①A为行对角占优阵②A为列对角占优阵第24页24科大硕士学位课程为了加紧收敛速度，同时为了节约计算机内存，我们作以下改进：每算出一个分量近似值，马上用到下一个分量计算中去，即用迭代格式：

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

例用雅可比迭代法解方程组解：雅可比迭代格式为第28页28科大硕士学位课程kx1(k)

x2(k)x3(k)10.720.830.8420.9711.071.15…………111.0999931.1999931.299991121.0999981.1999981.299997取计算以下第29页29科大硕士学位课程

解：Gauss-Seidel

迭代格式为

例用Gauss—Seidel迭代法解上题。第30页30科大硕士学位课程取x(0)=(0,0,0)T

计算以下：kx1(k)

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

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

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