数值计算方法：ch2-2 Jacobi方法与Gauss-Seidel方法

1、第二章 解线性方程组的迭代法2.3 Jacobi方法与Gauss-Seidel方法2一般迭代法的求解步骤依据方程组分离x得到迭代格式判断迭代格式是否收敛迭代求解满足终止条件,迭代结束32.3.1 Jacobi方法考虑方程组 Ax=b (2.3.1)其中 是非奇异的, 为已知向量.将矩阵A写成如下 A=D-L-U (2.3.2)其中 为对角阵,-L,-U分别为A的严格下,上三角部分构成的三角阵45当D非奇异,即aii0(i=1,2,n)时,利用(2.3.2)式,可将方程组(2.3.1)写成于是可得迭代格式称此格式为求解方程组(2.3.1)的Jacobi迭代法.注意到L+U=D-A,故(2.3.3

2、)式也可写成(2.3.3)(2.3.4)6Jacobi方法的迭代矩阵为Jacobi迭代法(2.3.4)式的分量形式为(2.3.6)7例2.1 用Jacobi方法解方程组82.3.2 Gauss-Seidel方法简单迭代法(2.2.3)的分量形式是可以用这些新值来计算 ,于是可得迭代格式这种方法称为Seidel迭代法.(2.3.7)9对Jacobi迭代(2.3.6)式运用Seidel技巧得到称(2.3.9)式为Gauss-Seidel迭代法,其矩阵形式为并可整理成一般迭代法的形式(2.3.9)(2.3.10)10例2.1 用Jacobi和Gauss-Seidel方法解方程组11小结12小结Jac

3、obi迭代法迭代矩阵迭代格式13GS方法迭代矩阵迭代格式14例 利用迭代法求解方程组讨论Jacobi和Gauss-Seidel方法的收敛性152.3.3 对角占优矩阵与不可约矩阵 定义2.4 若矩阵A=(aij)满足条件 且至少有一个i,使不等式严格成立,则称A为(按行)对角占优矩阵;若对i=1,n严格不等式均成立,则称A为(按行)严格对角占优矩阵.类似地,可以定义(按列)对角占优矩阵和(按列)严格对角占优矩阵.(2.3.14)1617定义2.5 设 ,若存在置换矩阵P,使得其中B和D是阶数1的方阵, O是零矩阵,则称A为可约的,否则称A为不可约的.定理2.6 若A为严格对角占优矩阵(或对角占

4、优不可约矩阵),则A是非奇异的.182.3.4 迭代法收敛的充分条件定理2.7 若系数矩阵A满足1)按行(或列)严格对角占优,或者2)不可约按行(或列)对角占优,则Jacobi迭代法(2.3.6)式和Gauss-Seidel迭代法(2.3.9)式均收敛.(2.3.9)(2.3.6)19定理2.8 若A是对角元素大于零的实对称矩阵,则Jacobi方法收敛的充分必要条件是A和2D-A皆为正定矩阵.定理2.9 设A为对称正定矩阵,则解Ax=b的Gauss-Seidel方法收敛.202.4松弛法松弛技术的设计思想在实际计算中常常可以获得目标值F*的两个相伴随的近似值F0与F1 ,于是可以取两者的某种加

5、权平均去改善精度，即也就是说，适当选取权值系数来调整校正量，以将F0与F1加工成更高精度的结果。由于这种方法基于校正量的调整与松动，通常称之为松弛技术。2.4.1Richardson迭代一般迭代法：Ax=b x=Hx+g2.4.1Richardson迭代一般迭代法：Ax=b x=Hx+g记令2.4.1Richardson迭代一般迭代法：Ax=b x=Hx+g记令得到：2.4.1Richardson迭代一般迭代法：Ax=b x=Hx+g记令得到：2.4.1Richardson迭代收敛性：H=I- A(H)=(I- A)1|1- A|1 A为A任意特征值当A为对称正定矩阵时02/max A2.4.

6、2Jacobi松弛法Jacobi over relaxation (JOR)Jacobi迭代法：x(k+1)=(I-D-1A)x(k)+D-1b2.4.2Jacobi松弛法Jacobi迭代法：x(k+1)=(I-D-1A)x(k)+D-1b记令2.4.2Jacobi松弛法Jacobi迭代法：x(k+1)=(I-D-1A)x(k)+D-1b记令得到：或者2.4.2Jacobi松弛法Jacobi迭代法：x(k+1)=(I-D-1A)x(k)+D-1b记令得到：或者2.4.3 SOR方法对Gauss-Seidel方法施加松弛技术Successive over relaxation (SOR)Gaus

7、s-Seidel迭代法：2.4.3 SOR方法Gauss-Seidel迭代法：记令2.4.3 SOR方法得到：矩阵形式：2.4.3 SOR方法得到：矩阵形式：第二章小结36小结向量范数矩阵范数谱半径37常见的三种向量范数“1范数”“2范数”（欧氏范数）“范数”（最大范数）38(ATA之最大特征值)1/2行和范数列和范数谱范数（2.1.15）39谱半径矩阵A的特征值的按模最大值称为A的谱半径记作，即其中是A的特征值。定理2.3对任意 ，有40一般迭代法的求解步骤依据方程组分离x得到迭代格式判断迭代格式是否收敛迭代求解满足终止条件,迭代结束41小结42小结Jacobi迭代法迭代矩阵迭代格式43GS方法迭代矩阵迭代格式44定理2.7 若系数矩阵A满足1)按行(或列)严格对角占优,或者2)不可约按行(或列)对角占优,则Jacobi迭代法和Gauss-Seidel迭代法均收敛.定理2.8 若A是对角元素大于