解线性方程组的迭代方法省公共课一等奖全国赛课获奖课件.pptx

迭代法研究主要问题迭代法研究主要问题1 1）迭代格式结构；）迭代格式结构；2 2）迭代收敛性分析；）迭代收敛性分析；3 3）收敛速度分析；）收敛速度分析；4 4）复杂性分析；（计算工作量）复杂性分析；（计算工作量）5 5）初始值选择。）初始值选择。3.5 大型方程组迭代方法大型方程组迭代方法第1页 定义定义:设设xk是是Rn上向量序列，上向量序列，又设又设x*（x1 1*，x 2*,，x n*)是是Rn上向量上向量.则称向量则称向量x*是向量序列是向量序列x k极限极限 ，若一个向量序列有极限若一个向量序列有极限,称这个向量序列是称这个向量序列是收敛收敛.向量序列极限向量序列极限假如假如向量序列向量序列x k收敛于向量收敛于向量x x*充分必要充分必要（i=1,2,=1,2,n）条件是条件是第2页矩阵序列极限矩阵序列极限定义定义:设设Ak是是 上矩阵序列上矩阵序列.若存在矩阵若存在矩阵 则称矩阵则称矩阵A 是矩阵序列是矩阵序列A k极限，记为极限，记为若一个矩阵序列有极限若一个矩阵序列有极限,称这个矩阵序列是称这个矩阵序列是收敛收敛.使得使得矩阵序列矩阵序列A k收敛于矩阵收敛于矩阵A 充分必要充分必要（i,j=1,2,=1,2,n）条件是条件是这里这里第3页证：证：依次取依次取 x 为为 ，其中，其中则则所以所以充要条件是对任何充要条件是对任何xRn，有，有设矩阵设矩阵，则，则 充要条件是充要条件是(A)0,记记 xTLTx=a,则则有有xTLTx=xT(D L)xxTAx=xT(D L LT)x=p a a=p 2a 0所以所以第26页所以所以,迭代矩阵迭代矩阵BG-S谱半径谱半径(BG-S)1,从而当方程组从而当方程组 Ax=b系数矩阵系数矩阵A 是实对称正定矩阵时是实对称正定矩阵时,G-S 迭代法收迭代法收敛敛Remark:1)G-S迭代法计算过程比迭代法计算过程比Jacobi迭代法更简单。计迭代法更简单。计算过程中只需用一个一维数组存放迭代向量。算过程中只需用一个一维数组存放迭代向量。2)G-S迭代不一定比迭代不一定比Jacobi迭代收敛快。迭代收敛快。3)Jacobi迭代和迭代和G-S迭代收敛范围并不一致，即迭代收敛范围并不一致，即Jacobi迭代收敛，迭代收敛，G-S迭代不一定收敛，反之亦迭代不一定收敛，反之亦然。然。4)前面定理前面定理1、定理、定理2对于对于Jacobi迭代和迭代和G-S迭代都迭代都适用。适用。第27页(i=1,2,n;k=1,2,3,)四四 超松驰超松驰(SOR)(SOR)迭代法迭代法G-S迭代格式迭代格式第28页定理定理7.若若A 是对称正定矩阵是对称正定矩阵,则当则当02时时SOR迭代迭代法解方程组法解方程组 A x=b 是收敛是收敛定理定理8.若若A 是严格对角占优矩阵是严格对角占优矩阵,则当则当00,计算计算 r(k-1)=b Ax(0),若若|r0|结束结束;不然不然 p(1)r(k-1),k 1,转第二步转第二步;共轭梯度算法：共轭梯度算法：第二步第二步:计算计算 tk=(p(k),r(k-1)/(A p(k),p(k)x(k)=x(k-1)+tk p(k);第三步第三步:假如假如 k=n,则结束则结束;不然不然,计算计算 r(k-1)=b Ax(k);转第四步转第四步;第四步第四步:假如假如|r(k-1)|,则则结束结束;不然不然,计算计算:bkj=(A p(j),r(k)/(A p(j),p(j),(j=1,k)p(k+1)=r(k-1)(bk1 p(1)+bkk p(k)k k+1,转第二步。转第二步。第40页