数值分析第六章线性方程组迭代解法

1第六章

线性方程组的迭代解法数值分析——迭代法基本概念2线性方程组迭代解法运算量大，不适合大规模的线性方程组求解无法充分利用系数矩阵的稀疏性直接法的缺点：从一个初始向量出发，按照一定的迭代格式，构造出一个趋向于真解的无穷序列只需存储系数矩阵中的非零元素运算量不超过O(kn2)，其中k为迭代步数迭代法迭代法是目前求解大规模线性方程组的主要方法3矩阵分裂迭代法矩阵分裂迭代法基本思想Ax=bk=0,1,2,…给定一个初始向量x(0)，可得迭代格式其中

B=M-1N

称为迭代矩阵

A=M-NMx=Nx

+

bM非奇异A

的一个矩阵分裂4向量序列的极限定义：设向量序列，

，若存在向量，使得i=1,2,…,n则称向量序列收敛到x，记作相类似地，可以定义矩阵序列的极限与收敛5矩阵分裂迭代法k=0,1,2,…定义：若存在，则称该迭代法收敛，否则称为发散性质：若，则x*

为原方程组Ax=b

的解引入误差向量,由得迭代法收敛：那么B满足什么条件有？6向量序列的极限定理：定理：定理：定理：7收敛性分析定理：对任意初始向量x(0)，上述迭代格式收敛的充要条件是定理：若存在算子范数||·

||，使得||B||<1，对任意的初始向量x(0)，上述迭代格式收敛。例：考虑迭代法x(k+1)=Bx(k)+f

的收敛性，其中基本收敛定理充分条件8收敛性分析B=M-1N定理：若存在算子范数||·

||，使得||B||=q<1，则迭代法收敛

9收敛速度第k

步的误差：平均每次迭代后的误差压缩率约为：若要求k

步迭代后上述误差比值不超过，则10收敛速度定义：迭代格式x(k+1)=Bx(k)+f

的平均收敛速度为渐进收敛速度为

(B)

越小，收敛越快11第六章

线性方程组的迭代解法数值分析——基本的矩阵分裂迭代法12本讲内容

Jacobi迭代算法Gauss-Seidel迭代算法SOR迭代算法收敛性分析矩阵分裂迭代法的典型代表13Jacobi迭代考虑线性方程组Ax=b其中A=(aij)nn

非奇异，且对角线元素全不为0。将A

分裂成A=D-L-

U，

其中14Jacobi迭代k=0,1,2,…令M=D，N

=L

+U，可得雅可比(Jacobi)迭代方法Jacobi迭代迭代矩阵记为：分量形式：i=1,2,…,

n，k=0,1,2,…15Jacobi迭代Jacobi迭代的分量形式：16Gauss-Seidel迭代在计算时，如果用代替，则可能会得到更好的收敛效果。17Gauss-Seidel迭代写成矩阵形式:此迭代方法称为高斯-塞德尔(Gauss-Seidel)迭代法k=0,1,2,…可得迭代矩阵记为：18举例例：分别用Jacobi、G-S迭代解线性方程组取初始向量x(0)=(0,0,0)，迭代过程中小数点后保留4位。解：Jacobi迭代：迭代可得：x(1)=(0.5000,2.6667,-2.5000)Tx(21)=(2.0000,3.0000,-1.0000)T19举例G-S迭代：x(1)=(0.5000,2.8333,-1.0833)Tx(9)=(2.0000,3.0000,-1.0000)T迭代可得：20Jacobi迭代收敛的充要条件(J)<1

G-S迭代收敛的充要条件(G)<1收敛性收敛性定理Jacobi迭代收敛的充分条件||J||<1

G-S迭代收敛的充分条件||G||<121SOR迭代为了得到更好的收敛效果，可在修正项前乘以一个松弛因子，于是可得迭代格式在G-S迭代中22SOR迭代写成矩阵形式:可得——SOR(SuccessiveOver-Relaxation)迭代方法迭代矩阵记为：

SOR的优点：通过选取合适的，可获得更快的收敛速度

SOR的缺点：最优参数的选取比较困难23Jacobi、G-S、SOR

Jacobi迭代

SOR迭代

G-S迭代24举例例：分别用Jacobi、G-S、SOR迭代解线性方程组取初始向量x(0)=(0,0,0)，迭代过程中小数点后保留4位。解：Jacobi迭代：迭代可得：x(1)=(0.5000,2.6667,-2.5000)Tx(21)=(2.0000,3.0000,-1.0000)T25举例G-S迭代：x(1)=(0.5000,2.8333,-1.0833)Tx(9)=(2.0000,3.0000,-1.0000)T迭代可得：26举例SOR迭代：取

=1.1，迭代可得x(1)=(0.5500,3.1350,-1.0257)Tx(7)=(2.0000,3.0000,-1.0000)T如何确定SOR迭代中的最优松弛因子是一件很困难的事27Jacobi迭代收敛的充要条件(J)<1

G-S迭代收敛的充要条件(G)<1

SOR迭代收敛的充要条件(L)<1收敛性收敛性定理Jacobi迭代收敛的充分条件||J||<1

G-S迭代收敛的充分条件||G||<1

SOR迭代收敛的充分条件||L||<128对角占优矩阵且至少有一个不等式严格成立，则称A

为弱对角占优；若所有不等式都严格成立，则称A

为严格对角占优。(i=1,2,...,n)定义：设ARnn，若29

收敛性定理：若A严格对角占优，则Jacobi迭代和