5Linearequations5.1Gausselimination5.2Pivoting5.3LUfactorisation5.4ThedeterminantandInverseofamatrix5.5BandedmatricesandTridiagonalmatrices5.6Otherapproachestosolvinglinearsystems1Inthischapterwedealwithbasicmatrixoperations,suchasthesolutionoflinearequations,calculatetheinverseofamatrix,itsdeterminantetc.25.1Gausselimination3例1 用高斯消元法求解方程组=+=-+=+53213614282321321321xxxxxxxxx4=+=-+=+53213614282321321321xxxxxxxxx=+-=-+=+-91012414282321321321xxxxxxxxx704=-=-+=+12603114282321321321xxxxxxxxx001522814321=-=xxx111332=+=xx26123-=-=x5matrixoperations6789x1 = x2 = x3 = 1.105.2Pivoting主元交换法主元交换法列主元交换法列主元交换法行主元交换法行主元交换法115.2.1 Partial pivoting部分主元交换法部分主元交换法12行主元交换法行主元交换法13例如例如. .求解方程组求解方程组Tx)3675. 0 ,05104. 0,4904. 0(*-=xxx000. 3000. 2000. 1643. 5072. 1000. 2623. 4712. 3000. 1000. 3000. 2001. 0321=-:4,4位有效数字为精确解舍入到位浮点数进行计算用14用高斯顺序消去法求解.)4000. 0 ,09980. 0,4000. 0(是一个很坏的解是一个很坏的解解得解得Tx- - -= =00. 2002. 1000. 100. 500005. 32.0040000. 3000. 2001. 0003. 2002. 1000. 1006. 6001. 40005. 32.0040000. 3000. 2001. 0000. 3000. 2000. 1643. 5072. 1000. 2623. 4712. 3000. 1000. 3000. 2001. 0)|A(.b - - -= =Tx)3675. 0 ,05104. 0,4904. 0(*-=15b6866.0500.0000.38676.1008015.13.17605.6431.00722.000-0015.1500.0000.30023.30005.208015.13.17605.6431.00722.000-000.1000.2000.3000.3000.2001.0623.43.7121.000-643.5072.1000.2000.3000.2000.1643.5072.1000.2623.4712.3000.1000.3000.2001.0)|A(.3i - - - - -= = =Tx)3676.0,51080.0,88544.0(- - -= =得得用主元交换法求解用主元交换法求解Tx)3675. 0 ,05104. 0,4904. 0(*-=165.2.2 Full pivoting全主元交换法全主元交换法1718而交换列时而交换列时解的解的次序发生改变次序发生改变解的次序不变。解的次序不变。交换行时交换行时, ,19；，对；中选绝对值最大者中选绝对值最大者从从选主元选主元、第一步消元、第一步消元jtilathenaifdonjnitlanjiaijijij= = =j. The diagonal is 1 and the upper matrix elements are zero. We solve thisequation column by column (increasing order of j). 53In a similar way we can define an equationwhich gives us the inverse of the matrix C, labelled Ein the equation below. with the following general equation5455A calculation of the inverse of a matrix could then be implemented in the following way:Set up the matrix to be inverted.Call the LU decomposition function.Check whether the determinant is zero or not.Then solve column by column eqs.56定理定理 设A为非奇异矩阵，方程组的增广矩阵为，如果对C应用高斯-若当方法化为，则2.2高斯-若当方法57例例2用高斯若当消元法求的逆矩阵. 58 595.5BandedmatricesandTridiagonalmatricesInBandedmatrices,theonlynon-zeroelementsfallwithinsomedistanceoftheleadingdiagonal.LUFactorisationmayreadilybemodifiedtoaccountforbandedstructure.Forexample,ifelementsoutsidetherangeai,ibtoai,i+bareallzero,thenthesummationsintheLUFactorisationalgorithmneedbeperformedonlyfromk=iork=i+1tok=i+b.Moreover,thefactorisationloopFORq=i+1TOncanterminateati+binsteadofn.60Tridiagonalmatrices6162=-nnnnnbacbacbacbA11122211OOO63-nnnnnbacbacbacb11122211OOO64三对角方程组的追赶法65例例 用追赶法解三对角线方程组 66u1=1/2,game1=0u1=1/2,game1=0game2=-1/(2-0)=-1/2game2=-1/(2-0)=-1/2u2=(0+1/2)/(2-1/2)=1/3u2=(0+1/2)/(2-1/2)=1/3game3=-1/(2-1/2)=-2/3game3=-1/(2-1/2)=-2/3u3=1/3/(2-2/3)=1/4u3=1/3/(2-2/3)=1/4Game4=-1/(2-2/3)=3/4Game4=-1/(2-2/3)=3/4u4=(1+1/4)/(2+3/4)=5/11u4=(1+1/4)/(2+3/4)=5/11u3=1/4-15/44=-1/11u3=1/4-15/44=-1/11u2=1/3-2/33=3/11u2=1/3-2/33=3/11u1=1/2+3/22=7/11u1=1/2+3/22=7/1167Finally, an important property of hermitian and symmetric matrices is that they have realeigenvalues.68Real orthogonal matrices is69矩阵特征值和特征向量的数值解法矩阵特征值和特征向量的数值解法幂法幂法逆幂法逆幂法古典古典Jacobi法法Jacobi法的改进法的改进QR算法算法70QR算法是目前求一般矩阵全部特征值和特征算法是目前求一般矩阵全部特征值和特征向量行之有效的一种方法，它适合于对称矩向量行之有效的一种方法，它适合于对称矩阵，也适合于非对称矩阵。阵，也适合于非对称矩阵。QR算法最早在算法最早在1961年由年由J.G.Francis提出的，后来经一系列提出的，后来经一系列数学家进行深入讨论数学家进行深入讨论,并作出了做有成效的改并作出了做有成效的改进与发展。进与发展。QR算法算法71矩阵的矩阵的QR分解分解定理定理:设矩阵设矩阵A非奇异，则一定存在正交矩阵非奇异，则一定存在正交矩阵Q，上三角矩阵，上三角矩阵R，使，使且当要求且当要求R的主对角元素均为正数时，则上述分的主对角元素均为正数时，则上述分解式是唯一的。解式是唯一的。QR算法是对算法是对A进行一系列的正交相似变换，达进行一系列的正交相似变换，达到求出矩阵到求出矩阵A的全部特征值和相应的特征向量。的全部特征值和相应的特征向量。725.6OtherapproachestosolvinglinearsystemsIteration731.TheJacobiIteration系数矩系数矩阵A可逆且主可逆且主对角元素角元素均不均不为零零.74其中其中为初始向量初始向量.75前三次叠代的结果，要求取前三次叠代的结果，要求取767778798081用用JacobiJacobi 迭代迭代法求解方程组法求解方程组 前三次叠代的结果，要求取前三次叠代的结果，要求取822.TheGauss-SeidelIterationIntheJacobiIteration83In the Gauss-Seidel Iteration84高斯高斯赛得尔（赛得尔（Gauss-Seidel）迭代法）迭代法（i = 1,2,n） 8586用用高斯高斯赛得尔（赛得尔（Gauss-Seidel）迭代法）迭代法求解求解方程组方程组前三次叠代的结果，要求取前三次叠代的结果，要求取878889Gauss-SeidelIterationJacobiIteration90从此例看出从此例看出,高斯高斯塞德尔迭代法比雅可比迭代塞德尔迭代法比雅可比迭代法收敛快法收敛快(达到同样的精度所需迭代次数少达到同样的精度所需迭代次数少),但但这个结论这个结论,在一定条件下才是对的在一定条件下才是对的,甚至有这样的甚至有这样的方程组方程组,雅可比方法收敛，而高斯雅可比方法收敛，而高斯塞德尔迭代塞德尔迭代法却是发散的法却是发散的.91迭代收敛的充分条件迭代收敛的充分条件下面介绍迭代格式的矩阵表示：其中为初始向量.92定义定义1：如果矩阵的每一行中，不在主对角线：如果矩阵的每一行中，不在主对角线上的所有元素绝对值之和小于主对角线上元素上的所有元素绝对值之和小于主对角线上元素的绝对值，即的绝对值，即则称矩阵则称矩阵A按行严格对角占优，类似地，也有按行严格对角占优，类似地，也有按列严格对角占优。按列严格对角占优。93定理：若线性方程组定理：若线性方程组AX=b的系数矩的系数矩阵阵A按行严格对角占优，则雅克比迭代法和按行严格对角占优，则雅克比迭代法和高斯高斯赛得尔迭代法对任意给定初值均收赛得尔迭代法对任意给定初值均收敛。敛。如果矩阵如果矩阵A严格对角占优，那么高斯严格对角占优，那么高斯赛得尔赛得尔迭代法的收敛速度快于雅克比迭代法的收敛速迭代法的收敛速度快于雅克比迭代法的收敛速度。度。94用用 Gauss-Seidel 迭代迭代法求解时方程组法求解时方程组前三次叠代的结果，要求取前三次叠代的结果，要求取953.SuccessiveOverRelaxation(SOR)超松驰法超松驰法使用迭代法的困难是计算量难以估计，有使用迭代法的困难是计算量难以估计，有些方程组的迭代格式虽然收敛，但收敛速些方程组的迭代格式虽然收敛，但收敛速度慢而使计算量变得很大。度慢而使计算量变得很大。超松驰迭代法是一种线性加速方法。超松驰迭代法是一种线性加速方法。超松驰迭代法是高斯超松驰迭代法是高斯塞德尔方法的一种加速塞德尔方法的一种加速方法，是解大型稀疏矩阵方程组的有效方法之方法，是解大型稀疏矩阵方程组的有效方法之一，它具有计算公式简单，程序设计容易一，它具有计算公式简单，程序设计容易,占用占用计算机内存较少等优点计算机内存较少等优点,但需要较好的加速因子但需要较好的加速因子(即最佳松驰因子即最佳松驰因子).96超松驰迭代法超松驰迭代法是一种线性加速方法。是一种线性加速方法。这种方法将前一步的结果这种方法将前一步的结果与高斯与高斯赛得尔方法的迭代值赛得尔方法的迭代值适当进行线性组合，以构成一个收敛速度较适当进行线性组合，以构成一个收敛速度较快的近似解序列。改进后的迭代方案是：快的近似解序列。改进后的迭代方案是：97In the Gauss-Seidel IterationIn theSuccessiveOverRelaxation其中系数其中系数要保证迭代格式收敛必须要求要保证迭代格式收敛必须要求称松驰因子。可以证明，称松驰因子。可以证明，98当当=1时，即为高斯时，即为高斯赛得尔迭代法，为使赛得尔迭代法，为使松驰因子的选取对迭代格式的收敛速度影松驰因子的选取对迭代格式的收敛速度影响极大。实际计算时，可以根据系数矩阵的性响极大。实际计算时，可以根据系数矩阵的性质，结合经验通过反复计算来确定松驰因子。质，结合经验通过反复计算来确定松驰因子。收敛速度加快，通常取收敛速度加快，通常取1，即为超松驰法。，即为超松驰法。要保证迭代格式收敛必须要求要保证迭代格式收敛必须要求99=1.046100101102