ch06a线性方程组迭代解法基本概念

1第六章

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

B=M-1N

称为迭代矩阵

A=M-NMx=Nx

+

bM非奇异A

的一个矩阵分裂4矩阵分裂迭代法k=0,1,2,…定义：若存在，则称该迭代法收敛，否则称为发散性质：若，则x*

为原方程组Ax=b

的解5向量序列的极限定义：设向量序列，

，若存在向量，使得i=1,2,…,n则称向量序列收敛到x，记作定理：6向量序列的极限定理：定理：(其中||·||为任一算子范数)相类似地，可以定义矩阵序列的极限与收敛7收敛性分析基本定理：对任意初始向量x(0)，上述迭代格式收敛的充要条件是定理：若存在算子范数||·

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

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

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

9Jacobi迭代考虑线性方程组Ax=b其中A=(aij)n

n

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

分裂成A=D-L-

U，

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

=L

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

n，k=0,1,2,…A=M-N11Gauss-Seidel迭代写成矩阵形式:此迭代方法称为高斯-塞德尔(Gauss-Seidel)迭代法k=0,1,2,…可得迭代矩阵记为：12SOR迭代写成矩阵形式:可得——SOR(SuccessiveOver-Relaxation)迭代方法迭代矩阵记为：

SOR的优点：通过选取合适的

，可获得更快的收敛速度

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

Jacobi迭代

SOR迭代

G-S迭代14举例例：分别用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)T

exJ_GS_SOR.m15举例G-S迭代：x(1)=(0.5000,2.8333,-1.0833)Tx(9)=(2.0000,3.0000,-1.0000)T迭代可得：16举例SOR迭代：取

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

(J)<1

G-S迭代收敛的充要条件

(G)<1

SOR迭代收敛的充要条件

(L

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

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

SOR迭代收敛的充分条件||L

||<118对角占优矩阵且至少有一个不等式严格成立，则称A

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

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

n，若19可约与不可约定义：设ARn

n，若存在排列矩阵P使得

则称A

为可约矩阵；否则称为不可约矩阵。如果A

是可约矩阵，则方程组Ax=b

等价于y即可以把原方程组化成两个低阶的方程组来处理。f20Jacobi、G-S收敛性定理：若A严格对角占优或不可约弱对角占优，则A非奇异定理：若A严格对角占优或不可约弱对角占优，则Jacobi迭代和G-S迭代均收敛定理：若A对称，且对角线元素均大于0，则Jacobi迭代收敛的充要条件是A与2D-A均正定；G-S迭代收敛的充要条件是A正定。21SOR收敛性定理：若SOR迭代收敛，则0<

<2。SOR收敛的必要条件定理：若A

对称正定，且0<

<2，则SOR迭代收敛。SOR收敛的充分条件定理：若A

严格对角占优或不可弱约对角占优，且0<

1，则SOR迭代收敛。22举例例：设，给出Jacobi和G-S收敛的充要条件解：A对称，且对角线元素均大于0，故(1)Jacobi收敛的充要条件是A和2D-A均正定(2)G-S收敛的充要条件是A正定A

正定2D-A

正定Jacobi收敛的充要条件是：-0.5<a<0.5G-S收敛的充要条件是：-0.5<a<123举例解法二：Jacobi的迭代矩阵为设