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

第二章解线性方程组的迭代法第二章解线性方程组的迭代法2.3Jacobi方法与Gauss-Seidel方法22.3Jacobi方法与Gauss-Seidel方法2一般迭代法的求解步骤依据方程组分离x得到迭代格式判断迭代格式是否收敛迭代求解满足终止条件,迭代结束3一般迭代法的求解步骤依据方程组分离x32.3.1Jacobi方法考虑方程组

Ax=b

(2.3.1)其中是非奇异的,为已知向量.将矩阵A写成如下

A=D-L-U(2.3.2)其中为对角阵,-L,-U分别为A的严格下,上三角部分构成的三角阵42.3.1Jacobi方法考虑方程组455当D非奇异,即aii≠0(i=1,2,…,n)时,利用(2.3.2)式,可将方程组(2.3.1)写成于是可得迭代格式称此格式为求解方程组(2.3.1)的Jacobi迭代法.注意到L+U=D-A,故(2.3.3)式也可写成(2.3.3)(2.3.4)6当D非奇异,即aii≠0(i=1,2,…,n)时,利用(2.Jacobi方法的迭代矩阵为Jacobi迭代法(2.3.4)式的分量形式为(2.3.6)7Jacobi方法的迭代矩阵为(2.3.6)7例2.1用Jacobi方法解方程组8例2.1用Jacobi方法解方程组82.3.2Gauss-Seidel方法简单迭代法(2.2.3)的分量形式是可以用这些新值来计算,于是可得迭代格式这种方法称为Seidel迭代法.(2.3.7)92.3.2Gauss-Seidel方法简单迭代法(2.2.对Jacobi迭代(2.3.6)式运用Seidel技巧得到称(2.3.9)式为Gauss-Seidel迭代法,其矩阵形式为并可整理成一般迭代法的形式(2.3.9)(2.3.10)10对Jacobi迭代(2.3.6)式运用Seidel技巧得到(例2.1用Jacobi和Gauss-Seidel方法解方程组11例2.1用Jacobi和Gauss-Seidel方法解方程小结12小结12小结Jacobi迭代法迭代矩阵迭代格式13小结Jacobi迭代法13G－S方法迭代矩阵迭代格式14G－S方法14例利用迭代法求解方程组讨论Jacobi和Gauss-Seidel方法的收敛性15例利用迭代法求解方程组152.3.3对角占优矩阵与不可约矩阵定义2.4若矩阵A=(aij)满足条件且至少有一个i,使不等式严格成立,则称A为(按行)对角占优矩阵;若对i=1,…,n严格不等式均成立,则称A为(按行)严格对角占优矩阵.类似地,可以定义(按列)对角占优矩阵和(按列)严格对角占优矩阵.(2.3.14)162.3.3对角占优矩阵与不可约矩阵定义2.4若矩阵A1717定义2.5

设,若存在置换矩阵P,使得其中B和D是阶数≥1的方阵,O是零矩阵,则称A为可约的,否则称A为不可约的.定理2.6

若A为严格对角占优矩阵(或对角占优不可约矩阵),则A是非奇异的.18定义2.5设2.3.4迭代法收敛的充分条件定理2.7

若系数矩阵A满足1)按行(或列)严格对角占优,或者2)不可约按行(或列)对角占优,则Jacobi迭代法(2.3.6)式和Gauss-Seidel迭代法(2.3.9)式均收敛.(2.3.9)(2.3.6)192.3.4迭代法收敛的充分条件定理2.7若系数矩阵A满足定理2.8若A是对角元素大于零的实对称矩阵,则Jacobi方法收敛的充分必要条件是A和2D-A皆为正定矩阵.定理2.9设A为对称正定矩阵,则解Ax=b的Gauss-Seidel方法收敛.20定理2.8若A是对角元素大于零的实对称矩阵,则Jacobi2.4松弛法

2.4松弛法

松弛技术的设计思想在实际计算中常常可以获得目标值F*的两个相伴随的近似值F0与F1,于是可以取两者的某种加权平均去改善精度，即也就是说，适当选取权值系数ω来调整校正量，以将F0与F1加工成更高精度的结果。由于这种方法基于校正量的调整与松动，通常称之为松弛技术。松弛技术的设计思想在实际计算中常常可以获得目标值F*的两个相2.4.1Richardson迭代一般迭代法：Ax=bx=Hx+g2.4.1Richardson迭代一般迭代法：2.4.1Richardson迭代一般迭代法：Ax=bx=Hx+g记令2.4.1Richardson迭代一般迭代法：2.4.1Richardson迭代一般迭代法：Ax=bx=Hx+g记令得到：2.4.1Richardson迭代一般迭代法：2.4.1Richardson迭代一般迭代法：Ax=bx=Hx+g记令得到：2.4.1Richardson迭代一般迭代法：2.4.1Richardson迭代收敛性：H=I-

ωA(H)=(I-ωA)<1|1-

ωA|<1A为A任意特征值当A为对称正定矩阵时0<ω<2/max

A2.4.1Richardson迭代收敛性：2.4.2Jacobi松弛法Jacobioverrelaxation(JOR)Jacobi迭代法：x(k+1)=(I-D-1A)x(k)+D-1b2.4.2Jacobi松弛法Jacobioverrela2.4.2Jacobi松弛法Jacobi迭代法：x(k+1)=(I-D-1A)x(k)+D-1b记令2.4.2Jacobi松弛法Jacobi迭代法：2.4.2Jacobi松弛法Jacobi迭代法：x(k+1)=(I-D-1A)x(k)+D-1b记令得到：或者2.4.2Jacobi松弛法Jacobi迭代法：2.4.2Jacobi松弛法Jacobi迭代法：x(k+1)=(I-D-1A)x(k)+D-1b记令得到：或者2.4.2Jacobi松弛法Jacobi迭代法：2.4.3SOR方法对Gauss-Seidel方法施加松弛技术Successiveoverrelaxation(SOR)Gauss-Seidel迭代法：2.4.3SOR方法对Gauss-Seidel方法施加松弛2.4.3SOR方法Gauss-Seidel迭代法：记令2.4.3SOR方法Gauss-Seidel迭代法：2.4.3SOR方法得到：矩阵形式：2.4.3SOR方法得到：2.4.3SOR方法得到：矩阵形式：2.4.3SOR方法得到：第二章小结36第二章小结36小结向量范数矩阵范数谱半径37小结37常见的三种向量范数“1－范数”“2－范数”（欧氏范数）“∞－范数”（最大范数）38常见的三种向量范数“1－范数”38(ATA之最大特征值)1/2行和范数列和范数谱范数（2.1.15）39(ATA之最大特征值)1/2行和范数列和范数谱范数（2.1.谱半径矩阵A的特征值的按模最大值称为A的谱半径记作，即其中是A的特征值。定理2.3对任意，有40谱半径矩阵A的特征值的按模最大值称为A的谱半径记作，即4一般迭代法的求解步骤依据方程组分离x得到迭代格式判断迭代格式是否收敛迭代求解满足终止条件,迭代结束41一般迭代法的求解步骤依据方程组分离x41小结42小结42小结Jacobi迭代法迭代矩阵迭代格式43小结Jacobi迭代法43G－S方法迭代矩阵迭代格式44G－S方法44定理2.7

若系数矩阵A满足1)按行(或列)严格对角占优,或者2)不可约按行(或列)对角占优,则Jacobi迭代法和Gauss-Seidel迭代法均收敛.定理2.8若A是对角元素大于零的实对称矩阵,则Jacobi方法收敛的充分必要条件是A和2D-A皆为正定矩阵.定理2.9设A为对称正定矩阵,则解Ax=b的Gauss-Seidel方法收敛.45定理2.7若系数矩阵A满足1)按行(或列)严格对角占优,作业P58，3，6，7,9(1)，证明定理2.2列和范数46作业46第二章解线性方程组的迭代法第二章解线性方程组的迭代法2.3Jacobi方法与Gauss-Seidel方法482.3Jacobi方法与Gauss-Seidel方法2一般迭代法的求解步骤依据方程组分离x得到迭代格式判断迭代格式是否收敛迭代求解满足终止条件,迭代结束49一般迭代法的求解步骤依据方程组分离x32.3.1Jacobi方法考虑方程组

Ax=b

(2.3.1)其中是非奇异的,为已知向量.将矩阵A写成如下

A=D-L-U(2.3.2)其中为对角阵,-L,-U分别为A的严格下,上三角部分构成的三角阵502.3.1Jacobi方法考虑方程组4515当D非奇异,即aii≠0(i=1,2,…,n)时,利用(2.3.2)式,可将方程组(2.3.1)写成于是可得迭代格式称此格式为求解方程组(2.3.1)的Jacobi迭代法.注意到L+U=D-A,故(2.3.3)式也可写成(2.3.3)(2.3.4)52当D非奇异,即aii≠0(i=1,2,…,n)时,利用(2.Jacobi方法的迭代矩阵为Jacobi迭代法(2.3.4)式的分量形式为(2.3.6)53Jacobi方法的迭代矩阵为(2.3.6)7例2.1用Jacobi方法解方程组54例2.1用Jacobi方法解方程组82.3.2Gauss-Seidel方法简单迭代法(2.2.3)的分量形式是可以用这些新值来计算,于是可得迭代格式这种方法称为Seidel迭代法.(2.3.7)552.3.2Gauss-Seidel方法简单迭代法(2.2.对Jacobi迭代(2.3.6)式运用Seidel技巧得到称(2.3.9)式为Gauss-Seidel迭代法,其矩阵形式为并可整理成一般迭代法的形式(2.3.9)(2.3.10)56对Jacobi迭代(2.3.6)式运用Seidel技巧得到(例2.1用Jacobi和Gauss-Seidel方法解方程组57例2.1用Jacobi和Gauss-Seidel方法解方程小结58小结12小结Jacobi迭代法迭代矩阵迭代格式59小结Jacobi迭代法13G－S方法迭代矩阵迭代格式60G－S方法14例利用迭代法求解方程组讨论Jacobi和Gauss-Seidel方法的收敛性61例利用迭代法求解方程组152.3.3对角占优矩阵与不可约矩阵定义2.4若矩阵A=(aij)满足条件且至少有一个i,使不等式严格成立,则称A为(按行)对角占优矩阵;若对i=1,…,n严格不等式均成立,则称A为(按行)严格对角占优矩阵.类似地,可以定义(按列)对角占优矩阵和(按列)严格对角占优矩阵.(2.3.14)622.3.3对角占优矩阵与不可约矩阵定义2.4若矩阵A6317定义2.5

设,若存在置换矩阵P,使得其中B和D是阶数≥1的方阵,O是零矩阵,则称A为可约的,否则称A为不可约的.定理2.6

若A为严格对角占优矩阵(或对角占优不可约矩阵),则A是非奇异的.64定义2.5设2.3.4迭代法收敛的充分条件定理2.7

若系数矩阵A满足1)按行(或列)严格对角占优,或者2)不可约按行(或列)对角占优,则Jacobi迭代法(2.3.6)式和Gauss-Seidel迭代法(2.3.9)式均收敛.(2.3.9)(2.3.6)652.3.4迭代法收敛的充分条件定理2.7若系数矩阵A满足定理2.8若A是对角元素大于零的实对称矩阵,则Jacobi方法收敛的充分必要条件是A和2D-A皆为正定矩阵.定理2.9设A为对称正定矩阵,则解Ax=b的Gauss-Seidel方法收敛.66定理2.8若A是对角元素大于零的实对称矩阵,则Jacobi2.4松弛法

2.4松弛法

松弛技术的设计思想在实际计算中常常可以获得目标值F*的两个相伴随的近似值F0与F1,于是可以取两者的某种加权平均去改善精度，即也就是说，适当选取权值系数ω来调整校正量，以将F0与F1加工成更高精度的结果。由于这种方法基于校正量的调整与松动，通常称之为松弛技术。松弛技术的设计思想在实际计算中常常可以获得目标值F*的两个相2.4.1Richardson迭代一般迭代法：Ax=bx=Hx+g2.4.1Richardson迭代一般迭代法：2.4.1Richardson迭代一般迭代法：Ax=bx=Hx+g记令2.4.1Richardson迭代一般迭代法：2.4.1Richardson迭代一般迭代法：Ax=bx=Hx+g记令得到：2.4.1Richardson迭代一般迭代法：2.4.1Richardson迭代一般迭代法：Ax=bx=Hx+g记令得到：2.4.1Richardson迭代一般迭代法：2.4.1Richardson迭代收敛性：H=I-

ωA(H)=(I-ωA)<1|1-

ωA|<1A为A任意特征值当A为对称正定矩阵时0<ω<2/max

A2.4.1Richardson迭代收敛性：2.4.2Jacobi松弛法Jacobioverrelaxation(JOR)Jacobi迭代法：x(k+1)=(I-D-1A)x(k)+D-1b2.4.2Jacobi松弛法Jacobioverrela2.4.2Jacobi松弛法Jacobi迭代法：x(k+1)=(I-D-1A)x(k)+D-1b记令2.4.2Jacobi松弛法Jacobi迭代法：2.4.2Jacobi松弛法Jacobi迭代法：x(k+1)=(I-D-1A)x(k)+D-1b记令得到：或者2.4.2Jacobi松弛法Jacobi迭代法：2.4.2Jacobi松弛法Jacobi迭代法：x(k+1)=(I-D-1A)x(k)+D-1b记令得到：或者2.4.2Jacobi松弛法Jacobi迭代法：2.4.3SOR方法对Gauss-Seidel方法施加松弛技术Successiveoverrelaxation(SOR)Gauss-Seidel迭代法：2.4.3SOR方法对Gauss-Seidel方法施加松弛2.4.3SOR方法Gauss-Seidel迭代法：记令2.4.3SOR方法Gauss-Seidel迭代法：2.4.3SOR方法得到