解线性方程组的迭代方法

关于解线性方程组的迭代方法第一页，共40页幻灯片

定义:设｛xk｝是Rn上的向量序列，

又设x*＝（x1*，x2*,…，xn*)Ｔ是Rn上的向量.

则称向量x*是向量序列｛xk｝的极限，若一个向量序列有极限,称这个向量序列是收敛的.向量序列的极限如果向量序列｛xk｝收敛于向量x*的充分必要定理1（i=1,2,…,n）条件是第二页，共40页幻灯片矩阵序列的极限定义:设｛Ak｝是

上的矩阵序列.若存在矩阵则称矩阵A是矩阵序列｛Ak｝的极限，记为若一个矩阵序列有极限,称这个矩阵序列是收敛的.使得矩阵序列｛Ak｝收敛于矩阵A的充分必要定理2（i,j=1,2,…,n）条件是这里第三页，共40页幻灯片证：依次取x为，其中则所以定理3的充要条件是对任何x∈Rn，有设矩阵定理4，则的充要条件是ρ(A)<1第四页，共40页幻灯片证：矩阵A相似于其Jordan标准型,即存在可逆矩阵P,使得J为对角分块矩阵(Ji称为Jordan块):其中:ni为特征值λi的重数,且n1+n2+…+nr=n由于第五页，共40页幻灯片所以而第六页，共40页幻灯片一、简单迭代思想设矩阵A可逆，把矩阵A分裂为则

迭代过程B称为迭代矩阵。给定初值就得到向量序列第七页，共40页幻灯片定义：若称简单迭代法收敛，否则，称逐次逼近法不收敛或发散。问题：是否是方程组x=Bx+f的解？结论1：任意给定初始向量，若由迭代公式(1)产生的迭代序列收敛到，则是方程组x=Bx+f的解。证：又如何判定所给迭代格式(1)是否收敛哪？第八页，共40页幻灯片迭代法收敛的条件定理1：对任意初始向量，由（1）得到的迭代序列收敛的充要条件是迭代矩阵的谱半径证：因此结论2：设矩阵，则注：要检验一个矩阵的谱半径小于1比较困难，所以我们希望用别的办法判断迭代格式是否收敛。第九页，共40页幻灯片定理2：若迭代法的迭代矩阵满足（矩阵的某一种算子范数），则迭代格式产生的序列收敛于x=Bx+f的精确解x*，且有误差估计式：证：由定理1、结论1和知迭代格式产生的序列收敛于x=Bx+f

的精确解x*

。且第十页，共40页幻灯片整理即得估计式。Remark:

因为矩阵范数，都可以直接用矩阵的元素计算，因此，用定理2，容易判别迭代法的收敛性。定理2的条件只是充分的，而不是必要的，也就是说：如果，则迭代法收敛；但若，我们并不能断定迭代法就一定发散，此时需要用定理1来判定迭代法的敛散性。

第十一页，共40页幻灯片

迭代格式的收敛速度与初始值x(0)有关，同时也与||B||和(B)有关，一般来说，||B||和(B)越小，收敛速度越快。Def：称为迭代法的渐近收敛速度。第十二页，共40页幻灯片二、Jacobi迭代法例1：用迭代法解方程组解:将方程组化为等价形式:构造迭代格式:取初始值代入计算，得第十三页，共40页幻灯片注：如何判断迭代过程终止？利用定理2的误差估计式可以判断迭代过程是否可以终止，但这种方法比较麻烦，通常采用的方法是通过前后两次迭代近似值的差来判断，即利用：终止迭代过程。上述这种求解方程组的方法称为Jacobi迭代法。第十四页，共40页幻灯片Jacobi迭代法的步骤：3、判断迭代格式的收敛性。取初值x(0)带入计算。1、写出等价方程组—即将第i个方程的xi

解出。2、写出相应的迭代格式分量式：假设A非奇异,且aii≠0,i=1,2,…,n第十五页，共40页幻灯片Jacobi迭代矩阵形式第十六页，共40页幻灯片记则有迭代格式：

上式称为Jacobi迭代格式，其中BJ称为Jacobi迭代矩阵。第十七页，共40页幻灯片注：Jacobi迭代矩阵BJ

：其中的元素恰为原方程组系数矩阵A中的主对角线元素换为0，而其余元素即为除以该行主对角元素后的相反数。Jacobi迭代法在计算xi(k+1)时所用分量仍为上一次近似值的各个分量，但此时，我们已经求出了新近似值的分量x1(k+1),x2(k+1),…,xi-1(k+1)，计算xi(k+1)时，用新分量x1(k+1),x2(k+1),…,xi-1(k+1)代替原来相应的分量，则得到一种新的迭代格式，即Gauss-Seidel迭代格式。第十八页，共40页幻灯片三、Gauss-Seidel迭代法假设Jacobi迭代新分量代替旧分量↖第十九页，共40页幻灯片矩阵表示：记上式整理可得：这是一种简单迭代格式，其中的BG-S称为G—S迭代矩阵。第二十页，共40页幻灯片例2：用G-S迭代法解方程组：解：原方程可化为等价形式：建立迭代格式：第二十一页，共40页幻灯片取初始向量x(0)=(0,0,0)T代入迭代格式，得：两种迭代法收敛性判定：

希望直接对系数矩阵A研究这俩种迭代收敛条件。引理：

A按行（列）严格对角占优（）证：（提示）第二十二页，共40页幻灯片定理4：若A为(行或列)严格对角占优矩阵，则相应的G-S迭代格式收敛。

定理3:

A按行(列)严格对角占优，则Jacobi迭代收敛。证：(仅证按行占优，反证)

设是任一特征值，x

是相应特征向量。设若则第二十三页，共40页幻灯片定理5：设A是有正对角元的n阶对称矩阵，则Jacobi迭代收敛A和2D-A同为正定矩阵。证：记则即，从而有相同的谱半径。由A的对称性，也对称，因而特征值全为实数，记为则的任一特征值为。第二十四页，共40页幻灯片定理6：若A为对称正定矩阵，则相应的G-S迭代格式收敛。正定。又，故正定。A正定正定，特征值小于1.若

正定,特征值小于1,所以特征值大于－1。第二十五页，共40页幻灯片证明:由A=D–L–LT

BG-S=(D–L)-1LT设λ为BG-S的任一特征值,x为其特征向量,则(D–L)-1LTx=λx

LTx=λ(D–L)x

A正定,故

p=xTDx>0,记xTLTx=a,则有xTLTx=λxT(D–L)xxTAx=xT(D–L–LT)x=p–a–a=p–2a>0所以第二十六页，共40页幻灯片所以,迭代矩阵BG-S的谱半径ρ(BG-S)<1,从而当方程组

Ax=b的系数矩阵A是实对称正定矩阵时,G-S迭代法收敛Remark:G-S迭代法的计算过程比Jacobi迭代法更简单。计算过程中只需用一个一维数组存放迭代向量。G-S迭代不一定比Jacobi迭代收敛快。Jacobi迭代和G-S迭代的收敛范围并不一致，即Jacobi迭代收敛，G-S迭代不一定收敛，反之亦然。前面的定理1、定理2对于Jacobi迭代和G-S迭代都适用。第二十七页，共40页幻灯片(i=1,2,···,n;k=1,2,3,···)四超松驰(SOR)迭代法G-S迭代格式第二十八页，共40页幻灯片定理7.

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

若A是严格对角占优矩阵,则当0<ω<1时SOR迭代法解方程组Ax=b是收敛的.迭代矩阵：第二十九页，共40页幻灯片例3：用松弛迭代法解方程组：解：松弛法迭代格式为：第三十页，共40页幻灯片★设x,y∈Rn,记(x,y)=xTy(x,y)=(y,x);(tx,y)=t(x,y);(x+y,z)=(x,z)+(y,z);(x,x)≥0,且(x,x)=0x=0;I方程组问题:Ax=bII极值问题:

★设A是n阶对称阵(Ax,y)=(x,Ay);(Ax，x)≥0,且(Ax,x)=0x=0五最速下降法第三十一页，共40页幻灯片定理9.

设A=(aij)n×n为实对称正定矩阵,b,x∈Rn,则x使二次函数取极小值x是线性方程组

Ax=b的解。

证明:(1)u是方程组Ax=b的解

Au–b=0.任意x∈Rn,令y=x–u

(Ay,y)≥0(2)设u使f(x)取极小值.任取非零

x∈Rn,任意

t∈R

第三十二页，共40页幻灯片令g(t)=f(u+tx),当t=0时,g(0)=f(u)达到极小值,所以

,即(Au–b,x)=0Au–b=0所以,u是方程组

Ax=b

的解.最速下降法基本思想：从初值点x

(0)

出发,以负梯度方向

r

为搜索方向，选择步长t1,得x(1)=x(0)+t1r,求函数f(x)极小值在

x处，梯度方向是

f(x)增长最快方向；负梯度方向是

f(x)下降最快方向。第三十三页，共40页幻灯片梯度:由f(x)的表达式，易知对于任意x(0)

∈Rn,f(x)在x

(0)处的负梯度方向为记r(0)

=b-Ax(0)，即r(0)的方向就是负梯度的方向，也是Ax=b的对应于x(0)的残向量。若r(0)

=0，则x(0)即为Ax=b的解，若r(0)

≠0

，则从x(0)出发，沿r(0)方向的x为：其中α为参数，这里x表明在r(0)方向上以α为步长，对x(0)做了一次修正，为确定α

，使函数第三十四页，共40页幻灯片取最小值。令解得：又所以，α=α0时f(x)取最小值，令x

(1)=x

(0)+α0r(0)，从x(1)出发沿f(x)在x(1)处的负梯度方向r(1)

=b-Ax(1)上求使f(x)的值最小的点，记为x(2)，则第三十五页，共40页幻灯片x(1)=x(0)+α0

r(0)继续下去则得迭代格式：第三十六页，共40页幻灯片结论1：第m+1次和第m次负梯度方向是正交的，即

(r(m+1),r

(m))=0结论2：最速下降法有误差估计式这里λ1和λn

为A的最大和最小特征值，||·||A

定义为注：由结论2可以看出，当λ1和λn

相差较大时，最速下降法收敛缓慢。第三十七页，共40页幻灯片六共轭梯度法A是n阶对称正定矩阵,非零向量p1,p2∈Rn▲

n