求解线性方程组的迭代法.pptx

哈哈尔尔滨滨工工程程大大学学 数数值值逼逼近近与与数数值值代代数数1 引言第6章 求解线性方程组的迭代法考虑线性方程组考虑线性方程组也就是也就是 AX=b.(1.1)AX=b.(1.1)低阶稠密的线性方程组用直接法低阶稠密的线性方程组用直接法(如高斯消去法和三角分解法如高斯消去法和三角分解法)。哈哈尔尔滨滨工工程程大大学学 数数值值逼逼近近与与数数值值代代数数大型稀疏非带状的线性方程组大型稀疏非带状的线性方程组(n(n很大很大,且零元素很多且零元素很多.如偏微方如偏微方程数值解产生的线性方程组程数值解产生的线性方程组,n10,n104 4)的求解问题？的求解问题？零元素多，适合用迭代法。零元素多，适合用迭代法。我们将介绍迭代法的一般理论及雅可比迭代法、高斯我们将介绍迭代法的一般理论及雅可比迭代法、高斯塞德塞德尔迭代法、超松弛迭代法，研究它们的收敛性。尔迭代法、超松弛迭代法，研究它们的收敛性。例1 求解线性方程组求解线性方程组 哈哈尔尔滨滨工工程程大大学学 数数值值逼逼近近与与数数值值代代数数记为记为Ax=b,Ax=b,即即精确解精确解x x*=(3,2,1)=(3,2,1)T T.改写改写(1.2)(1.2)为为或写为或写为x=Bx=B0 0 x+f,x+f,即即 哈哈尔尔滨滨工工程程大大学学 数数值值逼逼近近与与数数值值代代数数任取初值任取初值,如如x x(0)(0)=(0,0,0)=(0,0,0)T T,代入代入(1.3)(1.3)得到得到x x(1)(1)=(2.5,3,3)(2.5,3,3)T T.反复迭代反复迭代即即 x x(k+1)(k+1)=B=B0 0 x x(k)(k)+f+f，(k=0,1,2,)(k=0,1,2,)哈哈尔尔滨滨工工程程大大学学 数数值值逼逼近近与与数数值值代代数数 哈哈尔尔滨滨工工程程大大学学 数数值值逼逼近近与与数数值值代代数数 哈哈尔尔滨滨工工程程大大学学 数数值值逼逼近近与与数数值值代代数数2 基本迭代法考虑线性方程组考虑线性方程组也就是也就是 Ax=b.(2.1)Ax=b.(2.1)进行矩阵分裂进行矩阵分裂 A=M-N,(2.2)A=M-N,(2.2)其中其中M M为可选择的非奇异矩阵为可选择的非奇异矩阵,且使且使Mx=dMx=d容易求解容易求解.于是于是,Ax=b,Ax=bx=Mx=M-1-1Nx+MNx+M-1-1b.b.可得一阶定常迭代法可得一阶定常迭代法:哈哈尔尔滨滨工工程程大大学学 数数值值逼逼近近与与数数值值代代数数 哈哈尔尔滨滨工工程程大大学学 数数值值逼逼近近与与数数值值代代数数一、雅可比迭代法可以得到计算公式可以得到计算公式(雅可比迭代法)：对：对k=0,1,k=0,1,哈哈尔尔滨滨工工程程大大学学 数数值值逼逼近近与与数数值值代代数数 哈哈尔尔滨滨工工程程大大学学 数数值值逼逼近近与与数数值值代代数数二、高斯塞德尔迭代法还可得到迭代计算公式：对还可得到迭代计算公式：对k=0,1,k=0,1,称为称为高斯塞德尔迭代法.哈哈尔尔滨滨工工程程大大学学 数数值值逼逼近近与与数数值值代代数数 哈哈尔尔滨滨工工程程大大学学 数数值值逼逼近近与与数数值值代代数数例2 求解线性方程组求解线性方程组(1.2)(1.2)取初值取初值x x(0)(0)=(0,0,0)=(0,0,0)T T,哈哈尔尔滨滨工工程程大大学学 数数值值逼逼近近与与数数值值代代数数高斯高斯塞德尔迭代法又等价于：对塞德尔迭代法又等价于：对k=0,1,k=0,1,哈哈尔尔滨滨工工程程大大学学 数数值值逼逼近近与与数数值值代代数数SORSOR迭代法的计算公式迭代法的计算公式:对对k=0,1,k=0,1,三、逐次超松驰(SOR)迭代法 哈哈尔尔滨滨工工程程大大学学 数数值值逼逼近近与与数数值值代代数数说明:1)1)=1,GS;=1,GS;2)2)运算量运算量;3)3)11超松驰超松驰,11低松驰低松驰;4)4)控制迭代终止的条件控制迭代终止的条件:例3 用上述迭代法解线性代数方程组用上述迭代法解线性代数方程组初值初值x x(0)(0)=0=0，写出计算格式。，写出计算格式。P242.P242.作业:P259,2.:P259,2.哈哈尔尔滨滨工工程程大大学学 数数值值逼逼近近与与数数值值代代数数3 迭代法的收敛性分析一、一阶定常迭代法的基本定理 哈哈尔尔滨滨工工程程大大学学 数数值值逼逼近近与与数数值值代代数数 哈哈尔尔滨滨工工程程大大学学 数数值值逼逼近近与与数数值值代代数数 哈哈尔尔滨滨工工程程大大学学 数数值值逼逼近近与与数数值值代代数数1)Jacobi:B1)Jacobi:BJ J=D=D-1-1(L+U)(L+U)，f fJ J=D=D-1-1b;b;2)Gauss-Seidel:B2)Gauss-Seidel:BG G=(D-L)=(D-L)-1-1U U，f fG G=(D-L)=(D-L)-1-1b;b;3)SOR:B3)SOR:BSORSOR=(D-wL)=(D-wL)-1-1(1-w)D+wU(1-w)D+wU，f fSORSOR=w(D-wL)=w(D-wL)-1-1b.b.迭代的统一格式：x(k+1)=Bx(k)+f 哈哈尔尔滨滨工工程程大大学学 数数值值逼逼近近与与数数值值代代数数例5 考察用雅可比迭代法求解线性方程组考察用雅可比迭代法求解线性方程组 哈哈尔尔滨滨工工程程大大学学 数数值值逼逼近近与与数数值值代代数数 哈哈尔尔滨滨工工程程大大学学 数数值值逼逼近近与与数数值值代代数数定义3 （1 1）按行严格对角占优：）按行严格对角占优：（2 2）按行弱对角占优：）按行弱对角占优：上式至少有一个不等号严格成立。二、某些特殊方程组的迭代收敛性 哈哈尔尔滨滨工工程程大大学学 数数值值逼逼近近与与数数值值代代数数 哈哈尔尔滨滨工工程程大大学学 数数值值逼逼近近与与数数值值代代数数*定义 每行每列只有一个元素是每行每列只有一个元素是1,1,其余元素是零的方阵称为置换阵其余元素是零的方阵称为置换阵(或或排列阵排列阵).).作业:P259,5.:P259,5.哈哈尔尔滨滨工工程程大大学学 数数值值逼逼近近与与数数值值代代数数定理6(对角占优定理对角占优定理)若矩阵若矩阵A按行按行(或列或列)严格对角占优，或按行严格对角占优，或按行(或列或列)弱弱对角占优且不可约；则矩阵对角占优且不可约；则矩阵A非奇异。非奇异。定理7 若矩阵若矩阵A按行按行(或列或列)严格对角占优严格对角占优,或按行或按行(或列或列)弱对角占优不可约；弱对角占优不可约；则则JacobiJacobi迭代、迭代、Gauss-SeidelGauss-Seidel迭代都收敛。迭代都收敛。哈哈尔尔滨滨工工程程大大学学 数数值值逼逼近近与与数数值值代代数数证明证明 若矩阵A按行严格对角占优，或按行(或列)弱对角占优不可约，则GS迭代收敛。假若不然，(BG)1，即迭代矩阵BG的某一特征值使得|1，并且 哈哈尔尔滨滨工工程程大大学学 数数值值逼逼近近与与数数值值代代数数类似地，若矩阵A按行严格对角占优，或按行(或列)弱对角占优不可约，则Jacobi迭代收敛。假若不然，(BJ)1，即迭代矩阵BJ的某一特征值使得|1，并且 哈哈尔尔滨滨工工程程大大学学 数数值值逼逼近近与与数数值值代代数数 哈哈尔尔滨滨工工程程大大学学 数数值值逼逼近近与与数数值值代代数数定理9 对于线性方程组对于线性方程组Ax=b，若，若A为对称正定矩阵，则当为对称正定矩阵，则当0022时，时，SORSOR迭代收敛迭代收敛.证明 只需证明只需证明1（其中（其中为为L的任一特征值）的任一特征值）.哈哈尔尔滨滨工工程程大大学学 数数值值逼逼近近与与数数值值代代数数定理10 对于线性代数方程组对于线性代数方程组Ax=bAx=b，若若A A按行按行(或列或列)严格对角占优，严格对角占优，或按行或按行(或列或列)弱对角占优不可约；弱对角占优不可约；则当则当0w10w1时，时，SORSOR迭代收敛。迭代收敛。哈哈尔尔滨滨工工程程大大学学 数数值值逼逼近近与与数数值值代代数数作业:P260,7,8.:P260,7,8.