1、15 Linear equations 5.1 Gauss elimination 5.2 Pivoting5.3 LU factorisation 5.4 The determinant and Inverse of a matrix5.5 Banded matrices and Tridiagonal matrices5.6 Other approaches to solving linear systems2In this chapter we deal with basic matrix operations, such as the solution of linear equati
2、ons, calculate the inverse of a matrix, its determinant etc.35.1 Gauss elimination 4例1 用高斯消元法求解方程组=+=-+=+53213614282321321321xxxxxxxxx5=+=-+=+53213614282321321321xxxxxxxxx=+-=-+=+-91012414282321321321xxxxxxxxx704=-=-+=+12603114282321321321xxxxxxxxx001522814321=-=xxx111332=+=xx26123-=-=x6matrix opera
3、tions78910 x1 = x2 = x3 = 1.115.2 Pivoting主元交换法主元交换法列主元交换法列主元交换法行主元交换法行主元交换法125.2.1 Partial pivoting部分主元交换法部分主元交换法13行主元交换法行主元交换法14例如例如. .求解方程组求解方程组Tx)3675. 0 ,05104. 0,4904. 0(*-=xxx000. 3000. 2000. 1643. 5072. 1000. 2623. 4712. 3000. 1000. 3000. 2001. 0321=-:4,4位有效数字为精确解舍入到位浮点数进行计算用15用高斯顺序消去法求解.)40
4、00. 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(*-=16b6866.0500.0
5、000.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)36
6、75. 0 ,05104. 0,4904. 0(*-=175.2.2 Full pivoting全主元交换法全主元交换法1819而交换列时而交换列时解的解的次序发生改变次序发生改变解的次序不变。解的次序不变。交换行时交换行时, ,20；，对；中选绝对值最大者中选绝对值最大者从从选主元选主元、第一步消元、第一步消元jtilathenaifdonjnitlanjiaijijij= = =j. The diagonal is 1 and the upper matrix elements are zero. We solve thisequation column by column (increa
7、sing order of j). 54In a similar way we can define an equationwhich gives us the inverse of the matrix C, labelled E in the equation below. with the following general equation5511111111/ 11cece=2212111222121211/0cceecece-=+22222222/ 11cece=332312211113331323121311/ )(0cceceececece-=+56A calculation
8、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.57IAXn=IACnM=BInM.BA=-1定理定理 设A为非奇异矩阵，方程组的增广矩阵为，如果对C应用高斯-若当方法化为，则2.2高斯-若当方法58=5634
9、52231AA1-例例2 用高斯若当消元法求的逆矩阵. =1005630104520012313I |AC59 9103130012010001231-10133100012010035201- 11133100012010231001- -=-1330122311A605.5 Banded matrices and Tridiagonal matricesIn Banded matrices, the only non-zero elements fall within some distance of the leading diagonal. LU Factorisation may r
10、eadily be modified to account for banded structure. For example, if elements outside the range ai,ib to ai,i+b are all zero, then the summations in the LU Factorisation algorithm need be performed only from k=i or k=i+1 to k=i+b. Moreover, the factorisation loop FOR q=i+1 TO n can terminate at i+b i
11、nstead of n.61Tridiagonal matrices62=-nnnnnnnnnnaaaaaaaaaaA1111212322211211OOO63=-nnnnnbacbacbacbA11122211OOO64-nnnnnbacbacbacb11122211OOO65三对角方程组的追赶法66例例 用追赶法解三对角线方程组=+-=-+-=-+-=-120202124343232121xxxxxxxxxx6768Finally, an important property of hermitian and symmetric matrices is that they have rea
12、leigenvalues.69Real orthogonal matrices is1TA(A-=）IA(A(AA(1TTT=-）IA(A(A(AT1TT=-）ijkkkaa=jiijkkkiaa=j70矩阵特征值和特征向量的数值解法矩阵特征值和特征向量的数值解法幂法幂法逆幂法逆幂法古典古典Jacobi法法Jacobi法的改进法的改进QR算法算法71QR算法是目前求一般矩阵全部特征值和特征算法是目前求一般矩阵全部特征值和特征向量行之有效的一种方法，它适合于对称矩向量行之有效的一种方法，它适合于对称矩阵，也适合于非对称矩阵。阵，也适合于非对称矩阵。QR算法最早在算法最早在1961年由年由J.G.
13、Francis提出的，后来经一系列提出的，后来经一系列数学家进行深入讨论数学家进行深入讨论,并作出了做有成效的改并作出了做有成效的改进与发展。进与发展。QR算法算法72矩阵的矩阵的QR分解分解 QRA =定理定理: 设矩阵设矩阵A非奇异，则一定存在正交矩阵非奇异，则一定存在正交矩阵Q，上三角矩阵，上三角矩阵R，使，使且当要求且当要求R的主对角元素均为正数时，则上述分的主对角元素均为正数时，则上述分解式是唯一的。解式是唯一的。QR算法是对算法是对A进行一系列的正交相似变换，达进行一系列的正交相似变换，达到求出矩阵到求出矩阵A的全部特征值和相应的特征向量的全部特征值和相应的特征向量。735.6 O
14、ther approaches to solving linear systemsIteration74)(1)(1)(11122112323121222213132121111-=-=-=nnnnnnnnnnnnnxaxaxaraxxaxaxaraxxaxaxarax1. The Jacobi Iteration系数矩阵系数矩阵A可逆且主对角元素可逆且主对角元素nna,.,a ,a2211均不为零均不为零.75)(1)(1)(1)3)232)131333)13)2)323)121222)12)1)313)212111)11knnkkkknnkkkknnkkkxaxaxaraxxaxaxara
15、xxaxaxarax（-=-=-=+-+)1()1()(kikikixxx),()1()1(2)1(1+knkkxxx其中其中 Tnx,.x ,xx002010=为初始向量为初始向量.76bAx =2 .02 .1)0(x前三次叠代的结果，要求取前三次叠代的结果，要求取77)1 (21)22(4131)3(31)1)1)12)2)2)11kkkkkkxxxxxx（-=-=-=-=+1 .0)2 .11 (21)1 (21933.032 .0131)01)12)02)11-=-=-=-=-=（xxxxbAx =2 .02 .1)0(x781 .0)2 .11 (21)1 (211514933.0
16、32 .0131)01)12)02)11-=-=-=-=-=（xxxx301033.0)933.01 (21)1 (213031033.131 .0131)11)22)12)21=-=-=-=-=（xxxx601017.0)033.11 (21)1 (219089989.03033.0131)21)32)22)31-=-=-=-=-=-=（xxxx79-=017.0989.0)3(x-=100.0933.0)1(x=000.0000.1)(x=033.0033.1)2(x=180/1180/181)4(x80=1342AbAx =32b6 .02 .1*33336 .02 .0*2121)01
17、)12)02)11-=-=-=-=-=（xxxx=2 .02 .1)0(x816 .02 .1*33336 .02 .0*2121)01)12)02)11-=-=-=-=-=（xxxx2 .16 .0*33332 .26 .0*2121)11)22)12)21=-=-=+=-=（xxxx6 .32 .2*33334 .12 .1*2121)21)32)22)31=-=-=-=-=-=（xxxx82=-36332012361114238321xxxTx)0,0,0(0=用用JacobiJacobi迭代迭代法求解方程组法求解方程组 前三次叠代的结果，要求取前三次叠代的结果，要求取832. The
18、Gauss-Seidel Iteration)(1)(1)(1)3)232)131333)13)2)323)121222)12)1)313)212111)11knnkkkknnkkkknnkkkxaxaxaraxxaxaxaraxxaxaxarax（-=-=-=+In the Jacobi Iteration84)(1)(1)(1)3)1232)1131333)13)2)323)1121222)12)1)313)212111)11knnkkkknnkkkknnkkkxaxaxaraxxaxaxaraxxaxaxarax（-=-=-=+In the Gauss-Seidel Iteration-
19、+)1()1()(kikikixxx),()1()1(2)1(1+knkkxxx Tnx,.x ,xx002010=85高斯高斯赛得尔（赛得尔（Gauss-Seidel）迭代法）迭代法-=+=+-=+)(1)1(11)1(1kjnijijkjijijiiikixaxabax （i = 1, 2, n） FUxLxxkkk+=+)()1()1( FUxxLIkk+=-+)()1()(FLIUxLIxkk1)(1)1()()(-+-+-=86FLIUxLIxkk1)(1)1()()(-+-+-=FBXXkk+=+)()1(87bAx =2 .02 .1)0(x用用高斯高斯赛得尔（赛得尔（Gauss
20、-Seidel）迭代法）迭代法求解方求解方程组程组前三次叠代的结果，要求取前三次叠代的结果，要求取88)1 (21)22(4131)3(31)11)11)12)2)2)11+-=-=-=-=kkkkkkxxxxxx（033.0)933.01 (21)1 (21933.032 .0131)11)12)02)11=-=-=-=-=（xxxxbAx =2 .02 .1)0(x89033.0)933.01 (21)1 (21933.032 .0131)11)12)02)11=-=-=-=-=（xxxx0055.0)989.01 (21)1 (21989.03033.0131)21)22)12)21=-
21、=-=-=-=（xxxx001.0)998.01 (21)1 (21998.030055.0131)31)32)22)31=-=-=-=-=（xxxx90-=017.0989.0)3(x-=100.0933.0)1(x=000.0000.1)(x=033.0033.1)2(x=001.0998.0)3(x=033.0933.0)1(x=006.0989.0)2(xGauss-Seidel IterationJacobi Iteration91从此例看出从此例看出,高斯高斯塞德尔迭代法比雅可比迭代塞德尔迭代法比雅可比迭代法收敛快法收敛快(达到同样的精度所需迭代次数少达到同样的精度所需迭代次数少)
22、,但但这个结论这个结论,在一定条件下才是对的在一定条件下才是对的,甚至有这样的甚至有这样的方程组方程组,雅可比方法收敛，而高斯雅可比方法收敛，而高斯塞德尔迭代塞德尔迭代法却是发散的法却是发散的.92迭代收敛的充分条件迭代收敛的充分条件下面介绍迭代格式的矩阵表示：)(1)(1)(1)3)232)131333)13)2)323)121222)12)1)313)212111)11knnkkkknnkkkknnkkkxaxaxaraxxaxaxaraxxaxaxarax（-=-=-=+其中 Tnx,.x ,xx002010=为初始向量.), 2, 1(1)(1)1(nixabaxkjnijjijiii
23、ki=-=+93定义定义1：如果矩阵的每一行中，不在主对角线：如果矩阵的每一行中，不在主对角线上的所有元素绝对值之和小于主对角线上元素上的所有元素绝对值之和小于主对角线上元素的绝对值，即的绝对值，即niaaiinijjij, 2, 11=则称矩阵则称矩阵A按行严格对角占优，类似地，也有按行严格对角占优，类似地，也有按列严格对角占优。按列严格对角占优。94定理：若线性方程组定理：若线性方程组AX = b的系数矩的系数矩阵阵A按行严格对角占优，则雅克比迭代法和按行严格对角占优，则雅克比迭代法和高斯高斯赛得尔迭代法对任意给定初值均赛得尔迭代法对任意给定初值均收敛。收敛。如果矩阵如果矩阵A严格对角占优
24、，那么高斯严格对角占优，那么高斯赛得赛得尔迭代法的收敛速度快于雅克比迭代法的收敛尔迭代法的收敛速度快于雅克比迭代法的收敛速度。速度。95=-36203312362381114321xxxTx)0,0,0(0=用用 Gauss-Seidel迭代迭代法求解时方程组法求解时方程组 前三次叠代的结果，要求取前三次叠代的结果，要求取963. Successive Over Relaxation (SOR)超松驰法超松驰法使用迭代法的困难是计算量难以估计，有使用迭代法的困难是计算量难以估计，有些方程组的迭代格式虽然收敛，但收敛速些方程组的迭代格式虽然收敛，但收敛速度慢而使计算量变得很大。度慢而使计算量变得
25、很大。超松驰迭代法是一种线性加速方法超松驰迭代法是一种线性加速方法。超松驰迭代法是高斯超松驰迭代法是高斯塞德尔方法的一种加速塞德尔方法的一种加速方法，是解大型稀疏矩阵方程组的有效方法之方法，是解大型稀疏矩阵方程组的有效方法之一，它具有计算公式简单，程序设计容易一，它具有计算公式简单，程序设计容易,占用占用计算机内存较少等优点计算机内存较少等优点,但需要较好的加速因子但需要较好的加速因子(即最佳松驰因子即最佳松驰因子).97)(kix)1(+kix超松驰迭代法超松驰迭代法是一种线性加速方法是一种线性加速方法。这种方法将前一步的结果。这种方法将前一步的结果与高斯与高斯赛得尔方法的迭代值赛得尔方法的
26、迭代值适当进行线性组合，以构成一个收敛速度较适当进行线性组合，以构成一个收敛速度较快的近似解序列。改进后的迭代方案是：快的近似解序列。改进后的迭代方案是：98)b(11)11)1)1+=-=+-=nijkjijijkjijiiikixaxaax（In the Gauss-Seidel Iteration)b()1 ()11)1)1=-=+-+-=nijkjijijkjijiiikikixaxaaxx（ In the Successive Over Relaxation1)()1()1 (+-=kikikixxx), 2, 1(ni=20 1 ，即为超松驰法。，即为超松驰法。21要保证迭代格式收
27、敛必须要求要保证迭代格式收敛必须要求 100bAx = = 1.046=2 .02 .1)0(x101)1 (2)1 ()31 ()1 ()11)2)12)2)1)11+-+-=-+-=kkkkkkxxxxxx（026.0)1 (2046.1046.0921.0)31 (046.1046.0)11)02)12)02)01)11=-+-=-+-=（xxxxxxbAx =2 .02 .1)0(x102003.0)1 (2046.1046.0994.0)31 (046.1046.0)21)12)22)12)11)21=-+-=-+-=（xxxxxx026.0)1 (2046.1046.0921.0)31 (046.1046.0)11)02)12)02)01)11=-+-=-+-=（xxxxxx
