数值计算方法课件：第二章-解线性方程组的迭代法.ppt

1、第二章 解线性方程组的迭代法计算方法 第二章解线性方程组的迭代法2.3 Jacobi方法与Gauss-Seidel方法2计算方法 第二章解线性方程组的迭代法一般迭代法的求解步骤依据方程组分离x得到迭代格式判断迭代格式是否收敛迭代求解满足终止条件,迭代结束xHxg(1)()kkxHxg()(1)kkxx()1H1H 3计算方法 第二章解线性方程组的迭代法2.3.1 Jacobi方法考虑方程组 Ax=b (2.3.1)其中 是非奇异的,为已知向量.将矩阵A写成如下 A=D-L-U (2.3.2)其中 为对角阵,-L,-U分别为A的严格下,上三角部分构成的三角阵n nARnbR11(,)nnDdia

2、g aa4计算方法 第二章解线性方程组的迭代法2131321200000nnaLaaaa 121312321,00000nnnnaaaaaUa5计算方法 第二章解线性方程组的迭代法当D非奇异,即aii0(i=1,2,n)时,利用(2.3.2)式,可将方程组(2.3.1)写成于是可得迭代格式称此格式为求解方程组(2.3.1)的Jacobi迭代法.注意到L+U=D-A,故(2.3.3)式也可写成11()xDLU xD b(2.3.3)(1)1()1()0,1,2,.kkxD L U xD bk(2.3.4)11()xID A xD b6计算方法 第二章解线性方程组的迭代法Jacobi方法的迭代矩阵

3、为Jacobi迭代法(2.3.4)式的分量形式为11()HDL UID A 1(1)()()111()1,2,1,2,.inkkkiijjijjijj iiixa xa xbin ka(2.3.6)7计算方法 第二章解线性方程组的迭代法例2.1 用Jacobi方法解方程组1231231238 1210 4 53xxxxxxxxx8计算方法 第二章解线性方程组的迭代法2.3.2 Gauss-Seidel方法简单迭代法(2.2.3)的分量形式是可以用这些新值来计算 ,于是可得迭代格式这种方法称为Seidel迭代法.1(1)()()1 1,2,.inkkkiijjijjijj ixh xh xgin

4、(1)kix1(1)(1)()1 inkkkiijjijjijj ixh xh xg(2.3.7)9计算方法 第二章解线性方程组的迭代法对Jacobi迭代(2.3.6)式运用Seidel技巧得到称(2.3.9)式为Gauss-Seidel迭代法,其矩阵形式为并可整理成一般迭代法的形式1(1)(1)()111()1,2,.inkkkiijjijjijj iiixa xa xbina(2.3.9)(1)1(1)()()kkkxDLxUxb(1)1()1()()kkxDLUxDLb(2.3.10)10计算方法 第二章解线性方程组的迭代法例2.1 用Jacobi和Gauss-Seidel方法解方程组1

5、231231238 1210 4 53xxxxxxxxx11计算方法 第二章解线性方程组的迭代法小结2131321200000nnaLaaaa 121312321,00000nnnnaaaaaUa12计算方法 第二章解线性方程组的迭代法小结Jacobi迭代法迭代矩阵迭代格式11()HDLUIDA1(1)()()111()1,2,1,2,.inkkkiijjijjijj iiixa xa xbin ka 13计算方法 第二章解线性方程组的迭代法GS方法迭代矩阵迭代格式1()HDLU1(1)(1)()111()1,2,.inkkkiijjijjijj iiixa xa xbina 14计算方法 第

6、二章解线性方程组的迭代法例 利用迭代法求解方程组讨论Jacobi和Gauss-Seidel方法的收敛性123123123221 2223xxxxxxxxx15计算方法 第二章解线性方程组的迭代法2.3.3 对角占优矩阵与不可约矩阵 定义2.4 若矩阵A=(aij)满足条件 且至少有一个i,使不等式严格成立,则称A为(按行)对角占优矩阵对角占优矩阵;若对i=1,n严格不等式均成立,则称A为(按行)严格对角占优矩阵严格对角占优矩阵.类似地,可以定义(按列)对角占优矩阵和(按列)严格对角占优矩阵.1,1,.nijiijj iaain(2.3.14)16计算方法 第二章解线性方程组的迭代法123123

7、1238 1210 4 53xxxxxxxxx17计算方法 第二章解线性方程组的迭代法定义2.5 设 ,若存在置换矩阵P,使得其中B和D是阶数1的方阵,O是零矩阵,则称A为可约的,否则称A为不可约的.定理2.6 若A为严格对角占优矩阵(或对角占优不可约矩阵),则A是非奇异的.(2)nnARnTBCP A POD18计算方法 第二章解线性方程组的迭代法2.3.4 迭代法收敛的充分条件定理2.7 若系数矩阵A满足1)按行(或列)严格对角占优,或者2)不可约按行(或列)对角占优,则Jacobi迭代法(2.3.6)式和Gauss-Seidel迭代法(2.3.9)式均收敛.1(1)(1)()111()1

8、,2,.inkkkiijjijjijj iiixa xa xbina(2.3.9)1(1)()()111()1,2,1,2,.inkkkiijjijjijj iiixa xa xbin ka(2.3.6)19计算方法 第二章解线性方程组的迭代法定理2.8 若A是对角元素大于零的实对称矩阵,则Jacobi方法收敛的充分必要条件是A和2D-A皆为正定矩阵.定理2.9 设A为对称正定矩阵,则解Ax=b的Gauss-Seidel方法收敛.20计算方法 第二章解线性方程组的迭代法2.4松弛法计算方法 第二章解线性方程组的迭代法22松弛技术的设计思想在实际计算中常常可以获得目标值F*的两个相伴随的近似值F

9、0与F1,于是可以取两者的某种加权平均去改善精度，即也就是说，适当选取权值系数来调整校正量，以将F0与F1加工成更高精度的结果。由于这种方法基于校正量的调整与松动，通常称之为松弛技术。)()1(01010FFFFFF计算方法 第二章解线性方程组的迭代法232.4.1Richardson迭代一般迭代法：Ax=b x=Hx+g(1)()0,1,2.kkxHxgk计算方法 第二章解线性方程组的迭代法242.4.1Richardson迭代一般迭代法：Ax=b x=Hx+g记令(1)()0,1,2.kkxHxgkgHxxkk)()1()1()()1()1(kkkxxx计算方法 第二章解线性方程组的迭代法

10、252.4.1Richardson迭代一般迭代法：Ax=b x=Hx+g记令得到：(1)()0,1,2.kkxHxgkgHxxkk)()1()1()()1()1(kkkxxx)()()()1(bAxxxkkk计算方法 第二章解线性方程组的迭代法262.4.1Richardson迭代一般迭代法：Ax=b x=Hx+g记令得到：(1)()0,1,2.kkxHxgkgHxxkk)()1()1()()1()1(kkkxxx(1)()()()kkkxxAxb计算方法 第二章解线性方程组的迭代法272.4.1Richardson迭代收敛性：H=I-A(H)=(I-A)1|1-A|1 A为A任意特征值当A为

11、对称正定矩阵时02/max A计算方法 第二章解线性方程组的迭代法282.4.2Jacobi松弛法Jacobi over relaxation(JOR)Jacobi迭代法：x(k+1)=(I-D-1A)x(k)+D-1b计算方法 第二章解线性方程组的迭代法292.4.2Jacobi松弛法Jacobi迭代法：x(k+1)=(I-D-1A)x(k)+D-1b记令bDxADIxkk1)(1)1()()1()()1()1(kkkxxx计算方法 第二章解线性方程组的迭代法302.4.2Jacobi松弛法Jacobi迭代法：x(k+1)=(I-D-1A)x(k)+D-1b记令得到：或者bDxADIxkk1

12、)(1)1()()1()()1()1(kkkxxx)()(1)()1(bAxDxxkkkbDxADIxkk1)(1)1()(计算方法 第二章解线性方程组的迭代法312.4.2Jacobi松弛法Jacobi迭代法：x(k+1)=(I-D-1A)x(k)+D-1b记令得到：或者bDxADIxkk1)(1)1()()1()()1()1(kkkxxx)()(1)()1(bAxDxxkkkbDxADIxkk1)(1)1()(计算方法 第二章解线性方程组的迭代法322.4.3 SOR方法对Gauss-Seidel方法施加松弛技术Successive over relaxation(SOR)Gauss-Se

13、idel迭代法：1(1)(1)()111iinkkkijjijjijj iiixa xa xba 计算方法 第二章解线性方程组的迭代法332.4.3 SOR方法Gauss-Seidel迭代法：记令1(1)(1)()111iinkkkijjijjijj iiixa xa xba 1(1)(1)()111iinkkkijjijjijj iiixa xa xba )1()()1()1(kikikixxx计算方法 第二章解线性方程组的迭代法342.4.3 SOR方法得到：矩阵形式：nijikjijijkjijiikikbxaxaaxxi)(11)1()()1()()()1(1)()1(bxUDLxDx

14、xkkkk计算方法 第二章解线性方程组的迭代法352.4.3 SOR方法得到：矩阵形式：nijikjijijkjijiikikbxaxaaxxi)(11)1()()1()()()1(1)()1(bxUDLxDxxkkkkbLDxLxkk1)()1()()1()(1UDLDL计算方法 第二章解线性方程组的迭代法第二章第二章小结小结36计算方法 第二章解线性方程组的迭代法小结向量范数向量范数矩阵范数矩阵范数谱半径谱半径37计算方法 第二章解线性方程组的迭代法常见的三种向量范数“1 1范数范数”“2 2范数范数”（欧氏范数）（欧氏范数）“范数范数”（最大范数）（最大范数）11niixx21/22 1

15、/2211()()nniiiixxx1maxiinxx 38计算方法 第二章解线性方程组的迭代法11111m a xm a xnijinjnijjniAaAa2A(ATA之最大特征值之最大特征值)1/2行和范数行和范数列和范数列和范数谱范数谱范数01maxmaxppppxxpAxAAxx（2.1.15）39计算方法 第二章解线性方程组的迭代法谱半径矩阵A的特征值的按模最大值称为A的谱半径记作，即其中是A的特征值。定理2.3对任意 ，有1()maxii nA()Ain nAR()1,2,pAAp40计算方法 第二章解线性方程组的迭代法一般迭代法的求解步骤依据方程组分离x得到迭代格式判断迭代格式是

16、否收敛迭代求解满足终止条件,迭代结束xHxg(1)()kkxHxg41()(1)kkxx()1H1H 计算方法 第二章解线性方程组的迭代法小结2131321200000nnaLaaaa 121312321,00000nnnnaaaaaUa42计算方法 第二章解线性方程组的迭代法小结Jacobi迭代法迭代矩阵迭代格式11()HDLUIDA1(1)()()111()1,2,1,2,.inkkkiijjijjijj iiixa xa xbin ka 43计算方法 第二章解线性方程组的迭代法GS方法迭代矩阵迭代格式1()HDLU1(1)(1)()111()1,2,.inkkkiijjijjijj iiixa xa xbina 44计算方法 第二章解线性方程组的迭代法定理2.7 若系数矩阵A满足1)按行(或列)严格对角占优,或者2)不可约按行(或列)对角占优,则Jacobi迭代法和Gauss-Seidel迭代法均收敛.定理2.8 若A是对角元素大于零的实对称矩阵,则Jacobi方法收敛的充分必要条件是A和2D-A皆为正定矩阵.定理2.9 设A为对称正定矩阵,则解Ax=b的Gauss-Seidel方法收敛.45计算方法 第二章解线性方程组的迭代法作业P58，3，6，7,9(1)，证明定理2.2 列和范数46