解线性方程组的直接法

《解线性方程组的直接法》由会员分享，可在线阅读，更多相关《解线性方程组的直接法（72页珍藏版）》请在金锄头文库上搜索。

1、主讲教师：主讲教师： 高小辉高小辉 E-mail:第四章第四章 线性方程组线性方程组AX=B的数值解法的数值解法 (The Solution of Linear Systems AX=B)1求解求解4.1 4.1 引言引言许多实际问题可归结为线性（代数）方程组许多实际问题可归结为线性（代数）方程组机械设备、土建结构的受力分析；机械设备、土建结构的受力分析； 经济计划经济计划输电网络、管道系统的参数计算；输电网络、管道系统的参数计算； 企业管理企业管理大型的方程组需要有效的数值解法。大型的方程组需要有效的数值解法。数值解法的稳定性和收敛性问题需要注意。数值解法的稳定性和收敛性问题需要注意。2小行

2、星轨道计算问题小行星轨道计算问题3天文学家要确定一小行星的轨道天文学家要确定一小行星的轨道,在轨道平面建立以太阳为原点的在轨道平面建立以太阳为原点的直角坐标系直角坐标系.在坐标轴上取天文单位在坐标轴上取天文单位(地球到太地球到太阳的平均距离阳的平均距离),对小行星作对小行星作5次观察次观察, 测得坐标测得坐标数据数据 (x1,y1), (x2,y2), (x3,y3), (x4,y4), (x5,y5)将数据代入椭圆的一般方程将数据代入椭圆的一般方程: a1x2 + a2xy + a3y2 + a4x + a5y + 1 = 0得得a1xk2 + a2xkyk + a3yk2 + a4xk +

3、 a5yk + 1 = 0(k = 1, 2, 3, 4, 5)4即求解方程组即求解方程组可可确定椭圆方程确定椭圆方程(小行星轨道方程小行星轨道方程)5对一般线性方程组对一般线性方程组: A X = b, 其中其中当当系数矩阵系数矩阵A的行列式的行列式|A|0时时,则方程组有唯一则方程组有唯一解解.6求解线性方程组求解线性方程组: A X = b的的一般过程一般过程:输入：A，b解方程组算法输出： X直接法：经过有限步算术运算求得精确解直接法：经过有限步算术运算求得精确解迭代法：从初始解出发，逐步求出近似解来逼近迭代法：从初始解出发，逐步求出近似解来逼近在求解在求解小型小型(未知数较少未知数较

4、少)方程组时方程组时,直接法很有直接法很有效效.在求解大型方程组时在求解大型方程组时,迭代法是最有效的方法迭代法是最有效的方法.74.2 4.2 高斯消去法高斯消去法( (Gaussian Elimination ) ) 1. 上三角线性方程组上三角线性方程组(Upper-triangular Linear System) 定义定义4.1 N4.1 N N N矩阵矩阵A=A=a aijij 中的元素满足对所中的元素满足对所有有ij,ij,有有a aijij=0,=0,则称则称N N N N矩阵矩阵A=A=a aijij 为为上上三角三角矩阵矩阵。如果。如果A A中的元素满足对所有中的元素满足对

5、所有ij,ij,有有a aijij=0,=0,则称则称N N N N矩阵矩阵A=A=a aijij 为为下三角矩阵下三角矩阵。4.2.1 顺序高斯消去法89AX=BAX=B上上三角线性方程组表示为：三角线性方程组表示为：a a1111x x1 1+ a+ a1212x x2 2 +a+a1313x x3 3 + a+ a1n-11n-1x xn-1 n-1 + a+ a1n1nx xn n =b=b1 1 a a2222x x2 2 +a+a2323x x3 3 + a+ a2n-12n-1x xn-1 n-1 + a+ a2n2nx xn n =b=b2 2 a a3333x x3 3 +

6、a+ a3n-13n-1x xn-1 n-1 + a+ a3n3nx xn n =b=b3 3 . . a an-1n-1n-1n-1x xn-1 n-1 + a+ an-1nn-1nx xn n =b=bn-1n-1 a annnnx xn n = =b bn n2. 2. 回代回代(Back Substitution)(Back Substitution) 设设AX=BAX=B是上三角线性方程组，如果：是上三角线性方程组，如果：a akkkk 0,0,k=1,2.n,k=1,2.n,则方程组存在唯一解。则方程组存在唯一解。10证明：证明：a a1111x x1 1+ a+ a1212x x

7、2 2 +a+a1313x x3 3 + a+ a1n-11n-1x xn-1 n-1 + a+ a1n1nx xn n =b=b1 1 a a2222x x2 2 +a+a2323x x3 3 + a+ a2n-12n-1x xn-1 n-1 + a+ a2n2nx xn n =b=b2 2 a a3333x x3 3 + a+ a3n-13n-1x xn-1 n-1 + a+ a3n3nx xn n =b=b3 3 . . a an-1n-1n-1n-1x xn-1 n-1 + a+ an-1nn-1nx xn n =b=bn-1n-1 a annnnx xn n = =b bn n唯一唯

8、一用归纳法可证明用归纳法可证明x n-1,x n-2.x1是唯一的是唯一的11例例4.24.2：证明下列线性方程组无解证明下列线性方程组无解 4x4x1 1 x x2 2 + 2x+ 2x3 3 + 3x+ 3x4 4 =20=20 7x 7x3 3 - 4x- 4x4 4 =-7=-7 6x 6x3 3 + 5x+ 5x4 4 = 4= 4 3x 3x4 4 = 6= 6例例4.14.1：利用回代法求解线性方程组利用回代法求解线性方程组 4x4x1 1 x x2 2 + 2x+ 2x3 3 + 3x+ 3x4 4 =20=20 2x 2x2 2 + 7x+ 7x3 3 - 4x- 4x4 4

9、 =-7=-7 6x 6x3 3 + 5x+ 5x4 4 = 4= 4 3x 3x4 4 = 6= 6 x x4 4 = 6/3=2= 6/3=2x x3 3 = (4-5x= (4-5x4 4)/6=-1)/6=-1x x2 2 = (-7-7x= (-7-7x3 3 + 4x+ 4x4 4 )/-2=-4)/-2=-4x x1 1 = (20 + x= (20 + x2 2 - 2x- 2x3 3 - 3x- 3x4 4 )/4=3)/4=3x x4 4 = 2= 2x x3 3 = -1= -1x x3 3 = 1/7= 1/7a22=00x2 +12例例4.34.3：证明下列线性方程组

10、有无穷解证明下列线性方程组有无穷解 4x4x1 1 x x2 2 + 2x+ 2x3 3 + 3x+ 3x4 4 =20=20 0x0x2 2 + 7x+ 7x3 3 - - 0x0x4 4 =-7=-7 6x 6x3 3 + 5x+ 5x4 4 = 4= 4 3x 3x4 4 = 6= 6x x4 4 = 2= 2x x3 3 = -1= -1x x3 3 = -1= -1x x2 2 = 4x= 4x1 1 -16-16无穷解无穷解a22=013如如A A是是N N N N矩阵矩阵a a1111 a a12 12 a a13 13 a a1n 1n a a2121 a a22 22 a a

11、23 23 a a2n2n a an1n1 a an2 n2 a an3 n3 a annnnA A= =则则A A的行列式为：的行列式为：划掉划掉A A的第的第i i行和第行和第j j列列后后的的行列式行列式第第i i行展开行展开第第j j列展开列展开142 23 83 83 3-4 5 -4 5 -1 14 47 -6 7 -6 9 9A=A=j=2,det(A)=-3 +5 +6 =77 j=2,det(A)=-3 +5 +6 =77 -4 -1-4 -17 97 92 82 87 97 9 2 8 2 8-4 -1-4 -1i=1,det(A)=2 -3 +8 i=1,det(A)=2

12、 -3 +8 =2(45-6)-3(-36+7)+8(24-35)=77 =2(45-6)-3(-36+7)+8(24-35)=77 5 -15 -1-6 9-6 9-4 -1-4 -17 97 9-4 5-4 57 -67 -6153.3. 如果如果N N N N矩阵矩阵A=A=a aijij 是上三角是上三角矩阵或下矩阵或下三角三角矩阵，则：矩阵，则： 定理定理：A A是是N N N N方方阵，线性方程组阵，线性方程组AX=BAX=B有唯一解有唯一解当且仅当当且仅当det(A)det(A) 0 016 高斯消元法：高斯消元法：思思路路首先将首先将A化为上三角阵化为上三角阵 ，再回代求解，再

13、回代求解。=174 4 初等变换初等变换(Elementary Transformation)(Elementary Transformation) 下列三种变换可使一个线性方程组变换成另下列三种变换可使一个线性方程组变换成另一个等价的线性方程组一个等价的线性方程组交换变换交换变换：对调方程组的两行：对调方程组的两行比例变换比例变换：用非零常数乘方程组的某一行：用非零常数乘方程组的某一行替换变换替换变换：将方程组的某一行乘一个常数再加到：将方程组的某一行乘一个常数再加到 另一行另一行 18例例4.44.4：求抛物线：求抛物线y=A+Bx+Cxy=A+Bx+Cx2 2, ,它它经过三点经过三点(

14、1,1),(2,-1),(3,1)(1,1),(2,-1),(3,1)。 (2)-(1)(2)-(1) A+B+C=1 (1) A+B+C=1 (1) B+3C=-2 (2) B+3C=-2 (2) 2B+8C=0 (3) 2B+8C=0 (3)(3)-2(2)(3)-2(2) A+B+C=1 (1) A+B+C=1 (1) B+3C=-2 (2) B+3C=-2 (2) 2C=4 (3) 2C=4 (3)C=2,B=-8,A=7C=2,B=-8,A=7抛物线方程抛物线方程y=7-8x+2xy=7-8x+2x2 2A+ B+ C=1 (1)A+2B+4C=-1 (2) A+3B+9C=1 (3

15、)(3)-(1)(3-1)(3-2)19 上述求解方程组的方法就是高斯上述求解方程组的方法就是高斯(Gauss)消消元法。从式元法。从式(4-1)到到 (4-2)的过程称为消元过程的过程称为消元过程而由而由(4-2)求出求出C、B、A的过程称为回代过程。的过程称为回代过程。因此用高斯消去法求解性方程组要经过消元和因此用高斯消去法求解性方程组要经过消元和回代两个过程。回代两个过程。 20 可可将将线性方程组线性方程组AX=BAX=B的系数存在的系数存在N N (N+1)(N+1)增增广矩阵中广矩阵中a a1111 a a12 12 a a13 13 a a1n 1n b b0 0a a2121

16、a a22 22 a a23 23 a a2n 2n b b1 1 a an1n1 a an2 n2 a an3 n3 a annnn b bn nA|B=A|B=215 5 初等行变换初等行变换(Elementary Row Operation)(Elementary Row Operation) 对对增广矩阵进行增广矩阵进行如下变换可得到一个等价的如下变换可得到一个等价的线性方程组线性方程组交换行变换交换行变换：对调：对调矩阵矩阵两行两行比例行变换比例行变换：用非零常数乘：用非零常数乘矩阵矩阵某一行所有的元某一行所有的元 素素替换行变换替换行变换：将：将矩阵矩阵的某一行的所有元素乘一个的某

17、一行的所有元素乘一个 常数再加到另一行对应的元素上常数再加到另一行对应的元素上 去。去。 224.2.2 4.2.2 主元素（主元素（Pivot）高斯消去法高斯消去法 系数矩阵系数矩阵A A中的元素中的元素a arrrr用来消去用来消去a akrkr(k(k=r+1,=r+1,r+2,r+2,N),aN),arrrr为第为第r r个主元，第个主元，第r r行为主元行。行为主元行。例例4.64.6 用用增广矩阵表示下列线性方程组，并求等增广矩阵表示下列线性方程组，并求等价上三角线性方程组和方程组的解。价上三角线性方程组和方程组的解。 x x1 1 +2x+2x2 2 + x+ x3 3 + 4x

18、+ 4x4 4 =13=13 2x 2x1 1 +0x+0x2 2 + 4x+ 4x3 3 + 3x+ 3x4 4 =28=28 4x 4x1 1 +2x+2x2 2 + 2x+ 2x3 3 + x+ x4 4 =20=20-3x-3x1 1 + x+ x2 2 + 3x+ 3x3 3 + 2x+ 2x4 4 =6 =6 23 x x1 1 +2x+2x2 2 + x+ x3 3 + 4x+ 4x4 4 =13=13 2x 2x1 1 +0x+0x2 2 + 4x+ 4x3 3 + 3x+ 3x4 4 =28=28 4x 4x1 1 +2x+2x2 2 + 2x+ 2x3 3 + x+ x4

19、4 =20=20-3x-3x1 1 + x+ x2 2 + 3x+ 3x3 3 + 2x+ 2x4 4 =6 =6 1 2 1 41 2 1 4 13132 0 4 32 0 4 3 2828 4 2 2 1 204 2 2 1 20-3 1 3 2-3 1 3 2 6 60 7 6 14 450 7 6 14 45- -主元行主元行2 2- -主元行主元行4 4- -主元行主元行-3-31 2 1 41 2 1 4 13130 4 2 -50 4 2 -5 2 2 0 6 2 15 -32 0 6 2 15 -32 24- -主元行主元行-1.75-1.75- -主元行主元行1.51.50

20、7 6 14 450 7 6 14 451 2 1 41 2 1 4 13130 4 2 -50 4 2 -5 2 2 0 6 2 15 -32 0 6 2 15 -32 0 0 9.5 5.25 48.50 0 9.5 5.25 48.51 2 1 41 2 1 4 13130 4 2 -50 4 2 -5 2 2 0 0 5 7.5 -35 0 0 5 7.5 -35 0 0 0 0 9 -180 0 0 0 9 -181 2 1 41 2 1 4 13130 4 2 -50 4 2 -5 2 2 0 0 5 7.5 -35 0 0 5 7.5 -35 - -主元行主元行1.91.9回回代

21、：代：x x4 4=2,x=2,x3 3=4,=4,x x2 2=-1,x=-1,x1 1=3=3消元过消元过程程25有回代的高斯消去法有回代的高斯消去法( (Gaussian Elimination with Back Gaussian Elimination with Back SubstitutionSubstitution) ) 如果如果A A是是N N N N非奇异矩阵（存在非奇异矩阵（存在A A-1-1），），则存在则存在线性方程组线性方程组UX=YUX=Y与线性方程组与线性方程组AX=BAX=B等价，这里等价，这里U U是上三角矩阵，并且是上三角矩阵，并且a akkkk 0 0。

22、当构造出当构造出U U和和Y Y后，后，可用回代法求解可用回代法求解UX=YUX=Y，并得到方程组的解并得到方程组的解X X。26记记27Step 1：设设 ，计算因子，计算因子将增广矩阵将增广矩阵第第 i 行行 mi1 第第1 1行行，得到，得到其中其中28 一般地，假定已完成了一般地，假定已完成了(k-1)步消元，即已将步消元，即已将A(1)|B(1)转化为以下形式：转化为以下形式：29Step k：设设 ，计算因子，计算因子共进行共进行 ？ 步步n 1且计算且计算3031消元法消元法步骤步骤(以以4阶为例阶为例)：增广矩阵增广矩阵 32计算计算3个消元因子个消元因子(乘子向量乘子向量)

23、(1) 设设a11 0, m21 m31 m41T = a21 a31 a41T / a11 用用-m21乘矩阵第一行后加到矩阵第二行乘矩阵第一行后加到矩阵第二行;用用-m31乘矩阵第一行后加到矩阵第三行乘矩阵第一行后加到矩阵第三行;用用-m41乘矩阵第一行后加到矩阵第四行乘矩阵第一行后加到矩阵第四行;消消元元33用用-m31乘矩阵第一行后加到矩阵第三行乘矩阵第一行后加到矩阵第三行;消消元元34用用-m41乘矩阵第一行后加到矩阵第四行乘矩阵第一行后加到矩阵第四行;消消元元35第二轮消元后第二轮消元后(2) 设设a22(1) 0,计算第二个消元因子计算第二个消元因子m32 m42T = a32(

24、1) a42(1)T / a22(1) 用用-m32乘矩阵第二行后加到矩阵第三行乘矩阵第二行后加到矩阵第三行;用用-m42乘矩阵第二行后加到矩阵第四行乘矩阵第二行后加到矩阵第四行;36第三轮消元后第三轮消元后用用-m43乘矩阵第三行后加到矩阵第四行乘矩阵第三行后加到矩阵第四行;(3)设设a33(2) 0,计算第三个消元因子计算第三个消元因子: m43=a43(2)/a33(2)对应三角形方程组对应三角形方程组37消消元元过程中过程中,消消元因子可排列为元因子可排列为一矩阵一矩阵用回代算法即可用回代算法即可得出方程组的解得出方程组的解.38由初等变换的知识可得由初等变换的知识可得.L U = A

25、在消元在消元过程中过程中,我们得到两个矩阵我们得到两个矩阵此即为此即为矩阵矩阵A的的L U分解分解.39高斯消元法的高斯消元法的主要缺陷主要缺陷1.计算消元因子计算消元因子mik=aik/akk当分母当分母akk为零时为零时,计算无法进行计算无法进行;2.分母分母akk的绝对值非常小时的绝对值非常小时,也将会对计算结也将会对计算结果误差产生很大影响果误差产生很大影响解决办法解决办法40选主元以避免选主元以避免a apppp(p)(p)=0=0 如果如果 a apppp(p)(p)=0,=0,寻找第寻找第p p行下满足行下满足a akpkp(p(p) ) 0 0的的第一行，设为第第一行，设为第k

26、 k行，然后交换行行，然后交换行k k和行和行p p，使新，使新a apppp(p)(p) 0 0。如果如果 a apppp(p)(p)00则不交换。此方法称则不交换。此方法称为为平凡选主元方法平凡选主元方法。41 将将列主元列主元所在行与第所在行与第k行交换后行交换后,再按上面再按上面的高斯消元法进行下去的高斯消元法进行下去,此法即称为此法即称为列主元消列主元消元法元法。选选|aik(k)|(i=k, ,n)最大的一个最大的一个(列主列主元元)选主元以减少误差选主元以减少误差 在每一步消元过程中取系数子矩阵的第一在每一步消元过程中取系数子矩阵的第一列元素中绝对值最大者作主元。列元素中绝对值最

27、大者作主元。42例例4.7:4.7: 值值x x1 1=x=x2 2=1.000=1.000是如下方程组的解是如下方程组的解： 1.133x1.133x1 1+5.281x+5.281x2 2=6.414=6.414 24.14x 24.14x1 1-1.210x-1.210x2 2=22.93=22.93 用用4 4位有效数字及选主元的高斯法求方程的解。位有效数字及选主元的高斯法求方程的解。 行行2-2-行行1 124.14/1.133: 24.14/1.133: 1.133x 1.133x1 1+5.281x+5.281x2 2=6.414=6.414 -113.7x -113.7x2 2

28、=-113.8=-113.8 x x2 2=1.001, =1.001, x x1 1=0.9956=0.995643例例4.84.8： 24.14x24.14x1 1-1.210x-1.210x2 2=22.93=22.93 1.133x 1.133x1 1+5.281x+5.281x2 2=6.414=6.414 行行2-2-行行1 11.133/24.14 : 1.133/24.14 : 24.14x 24.14x1 1-1.210x-1.210x2 2=22.93 =22.93 5.338x 5.338x2 2=5.338=5.338 x x2 2=1.000, =1.000, x x

29、1 1=1.000=1.00044例例 用列主元法解用列主元法解第一列中绝对值最大是第一列中绝对值最大是10，取，取10为主元为主元45第二列的后两个数中选出主元第二列的后两个数中选出主元 2.546X3=6.2/6.2=1X2=(2.5-5X3)/2.5=-1X1=(7+7x2-0x3)/10=0X1=0X2=-1X3=1N阶方程组第阶方程组第k轮消元时，选第轮消元时，选第k列的后列的后(n-k+1)个元素个元素中绝对值最大者作主元。中绝对值最大者作主元。474.3 4.3 矩阵三角分解法（矩阵三角分解法（TrianguarTrianguar Factorization Factorizat

30、ion） 定义定义 如果非奇异矩阵如果非奇异矩阵A可表示为下三角矩阵可表示为下三角矩阵L和上和上 三角矩阵三角矩阵U的乘积的乘积A=LU，则，则A存在一个三角存在一个三角 分解。分解。4.3.1 高斯消去法和矩阵三角分解法高斯消去法和矩阵三角分解法a a1111x x1 1+ a+ a1212x x2 2 +a+a1313x x3 3 + a+ a1n-11n-1x xn-1 n-1 + a+ a1n1nx xn n =b=b1 1a a2121x x1 1+ a+ a2222x x2 2 +a+a2323x x3 3 + a+ a2n-12n-1x xn-1 n-1 + a+ a2n2nx

31、xn n =b=b2 2a a3131x x1 1+ a+ a3232x x2 2 +a+a3333x x3 3 + a+ a3n-13n-1x xn-1 n-1 + a+ a3n3nx xn n =b=b3 3a an1n1x x1 1+ a+ an2n2x x2 2 +a+an3n3x x3 3 + a+ ann-1nn-1x xn-1 n-1 + + a annnnx xn n = =b bn n48a11 a12 a13 a1n a21 a22 a23 a2n a31 a32 a33 a3n an1 an2 an3 ann=1 0 0 0 m21 1 0 0 m31 m32 1 0 m

32、n1 mn2 mn3 1u11 u12 u13 u1n 0 u22 u23 u2n 0 0 u33 u3n 0 0 0 unn49a a1111 a a12 12 a a13 13 a a1n 1n a a2121 a a22 22 a a23 23 a a2n 2n a a3131 a a32 32 a a33 33 a a3n 3n a an1n1 a an2 n2 a an3 n3 a annnnx x1 1x x2 2x x3 3x xn n=b b1 1b b2 2b b3 3b bn n1 0 0 01 0 0 0 m m2121 1 0 0 1 0 0 m m3131 m m32

33、 32 1 01 0 m mn1n1 m mn2 n2 m mn3 n3 1 1u u1111 u u12 12 u u13 13 u u1n 1n 0 u0 u22 22 u u23 23 u u2n 2n 0 00 0 u u33 33 u u3n 3n 0 00 0 0 0 u unnnnx x1 1x x2 2x x3 3x xn n=b b1 1b b2 2b b3 3b bn ny y1 1y y2 2y y3 3y yn n501 0 0 01 0 0 0 m m2121 1 0 0 1 0 0 m m3131 m m32 32 1 01 0 m mn1n1 m mn2 n2 m

34、 mn3 n3 1 1y y1 1y y2 2y y3 3y yn n=b b1 1b b2 2b b3 3b bn nu u1111 u u12 12 u u13 13 u u1n 1n 0 u0 u22 22 u u23 23 u u2n 2n 0 00 0 u u33 33 u u3n 3n 0 00 0 0 0 u unnnnx x1 1x x2 2x x3 3x xn n=y y1 1y y2 2y y3 3y yn n UX=YLY=bYX51由初等变换的知识可得由初等变换的知识可得.L U = A在高斯消在高斯消元元过程中过程中,我们得到两个矩阵我们得到两个矩阵此即为此即为矩阵矩

35、阵A的的L U分解分解.52例例4.3.2 求解：求解： x x1 1+ 2x+ 2x2 2 + 4x+ 4x3 3+ x+ x4 4 =21=212x2x1 1+ 8x+ 8x2 2 + 6x+ 6x3 3+4x+4x4 4 =52=523x3x1 1+10x+10x2 2 + 8x+ 8x3 3+8x+8x4 4 =79=794x4x1 1+12x+12x2 2 +10x+10x3 3+6x+6x4 4 =82=821 2 4 11 2 4 1 2 8 6 42 8 6 4 3 10 8 83 10 8 84 12 10 64 12 10 61 0 0 01 0 0 0 2 1 0 02

36、1 0 0 3 1 1 03 1 1 04 1 2 14 1 2 11 2 4 11 2 4 1 0 4 -2 20 4 -2 2 0 0 -2 30 0 -2 30 0 0 -60 0 0 -6A= = =LU531 0 0 0 2 1 0 0 3 1 1 04 1 2 11 2 4 1 0 4 -2 2 0 0 -2 30 0 0 -6x1x2x3x4=215279821 0 0 0 2 1 0 0 3 1 1 04 1 2 1y1y2y3y4=21527982 y1 =21 y2 =10 y3 =6 y4 = -24 54 x4 =4 x3 =3 x2 =2 x1 =1 1 2 4 1

37、0 4 -2 2 0 0 -2 30 0 0 -6x1x2x3x4=2110 6-24554.3.2 直接三角分解法直接三角分解法例例4.3.1 使用高斯消去构造下列矩阵的三角分解：使用高斯消去构造下列矩阵的三角分解：4 3 -14 3 -1 -2 -4 5-2 -4 51 2 61 2 6A= 1 1 0 00 02 2-0.5 1 -0.5 1 0 03 30.25 0 0.25 0 1 14 3 -14 3 -1 0 -2.5 4.50 -2.5 4.50 1.25 6.250 1.25 6.251 10 00 02 20 1 0 1 0 03 30 0 0 0 1 1= 4 3 -14

38、 3 -1 -2 -4 5-2 -4 51 2 61 2 6行行2-行行1*(-2/4)行行3-行行1*(1/4)1 1 0 00 02 2-0.5 1 -0.5 1 0 03 30.25 0.25 0.5 10.5 14 3 -14 3 -1 0 -2.5 4.50 -2.5 4.50 0 8.50 0 8.5行行3-行行2*(1.25/-2.5)4 3 -14 3 -1-0.5 -2.5 4.5-0.5 -2.5 4.50.25 0.5 0.25 0.5 8.58.556定理定理 设无行交换变换的高斯消去法可求解一般线性方设无行交换变换的高斯消去法可求解一般线性方程组程组AX=B，则矩阵，

39、则矩阵A可分解为一个下三角矩阵可分解为一个下三角矩阵L和一和一个上三角矩阵个上三角矩阵U的乘积：的乘积：A=LU，而且而且L对角线元素为对角线元素为1，U的对角线元素非零。得到的对角线元素非零。得到L和和U后，可通过如下后，可通过如下步骤得到步骤得到X： 1、利用前向替换法对方程组利用前向替换法对方程组LY=B求解求解Y 2、利用回代法对方程组利用回代法对方程组UX=Y求解求解X574.4 置换矩阵置换矩阵 可能一个非奇异矩阵不能直接分解为可能一个非奇异矩阵不能直接分解为A=LU例例4.4.1 证明下列矩阵不能直接分解为证明下列矩阵不能直接分解为A=LU：1 2 61 2 6 4 8 -14

40、8 -1-2 3 5-2 3 5A= 581 2 61 2 6 4 8 -14 8 -1-2 3 5-2 3 5A= =1 0 01 0 0 m m2121 1 0 1 0m m3131 m m3232 1 1u u1111 u u1212 u u1313 0 0 u u22 22 u u23230 0 0 0 u u3333 1= u u11 11 4= m 4= m21 21 u u11 11 = m= m21 21 -2= m-2= m31 31 u u11 11 = m= m31 31 2= u u12 12 8= m 8= m21 21 u u12 12 + u+ u22 22 =4

41、*2+0=4*2+0 3= m 3= m31 31 u u12 12 + + m m32 32 u u22 22 =(-2)*2+ m=(-2)*2+ m32 32 *0*0 =-4=-459一个一个N N置换矩阵置换矩阵P是是一个在每一行和每一列只有一个在每一行和每一列只有一个元素为一个元素为1，而其它元素为，而其它元素为0的矩阵。的矩阵。P的列是单的列是单位矩阵行的置换，可表示为：位矩阵行的置换，可表示为：P=Ek1 Ek2 Ekn Pij=1j=ki0 其它情况其它情况如：如：0 1 0 00 1 0 0 1 0 0 01 0 0 00 0 0 1 0 0 0 1 0 0 1 00 0

42、1 0 P= =E2 E1 E4 E3 60定理定理 设设P= Ek1 Ek2 Ekn 是一个置换是一个置换矩矩阵。阵。PA是一个新的矩阵，它的行是将是一个新的矩阵，它的行是将A中的行中的行按行按行k1A,行行k2A，行行knA调整顺序后形成的。调整顺序后形成的。例例4.4.2 设设A为为4 4矩阵，矩阵，P为上式中的置换矩阵，则为上式中的置换矩阵，则PA矩阵中的行是将矩阵中的行是将A中的行调整顺序后形成的，顺序为第中的行调整顺序后形成的，顺序为第1，2，3，4行对应于行对应于A中的第中的第2，1，4，3行。行。 610 1 0 00 1 0 0 1 0 0 01 0 0 00 0 0 1 0

43、 0 0 1 0 0 1 00 0 1 0 a a1111 a a12 12 a a13 13 a a14 14 a a2121 a a22 22 a a23 23 a a24 24 a a3131 a a32 32 a a33 33 a a34 34 a a4141 a a42 42 a a43 43 a a4444=a a2121 a a22 22 a a23 23 a a2424a a1111 a a12 12 a a13 13 a a14 14 a a4141 a a42 42 a a43 43 a a4444a a3131 a a32 32 a a33 33 a a34 34 62定

44、理定理 如果如果A是非奇异矩阵，则存在一个置换矩阵是非奇异矩阵，则存在一个置换矩阵P，使使得得PA存在三角分解：存在三角分解：PA=LU例例4.4.3 设设A为非奇异矩阵为非奇异矩阵1 2 61 2 6 4 8 -14 8 -1-2 3 5-2 3 5A= 1 2 61 2 6 4 8 -14 8 -1-2 3 5-2 3 5PA= 1 0 01 0 0 0 0 10 0 10 1 00 1 0=1 2 61 2 6 -2 3 5-2 3 54 8 -14 8 -11 2 61 2 6 0 7 170 7 170 0 -250 0 -25可可分解分解U634.5 扩展高斯消去过程扩展高斯消去过

45、程定理定理（非直接分解：（非直接分解：PA=LU）设设A是一是一N N矩阵。假设高斯消去法可求解经过行变换矩阵。假设高斯消去法可求解经过行变换的一般线性方程组的一般线性方程组AX=B。则存在一个置换矩阵则存在一个置换矩阵P，使，使得得PA可分解为一个下三角矩阵可分解为一个下三角矩阵L和一个上三角矩阵和一个上三角矩阵U：PA=LU。而且。而且L的主对角线元素为的主对角线元素为1，U的主对角线元的主对角线元素非零。素非零。可用如下可用如下4步求出步求出X：1、构造矩阵构造矩阵L，U，P2、计算列向量计算列向量PB3、用前向替换法对方程组用前向替换法对方程组LY=PB求解求解Y4、用回代法对方程组用

46、回代法对方程组UX=Y求解求解X如何求如何求P P64a a1111 a a12 12 a a13 13 a a14 14 a a2121 a a22 22 a a23 23 a a24 24 a a3131 a a32 32 a a33 33 a a34 34 a a4141 a a42 42 a a43 43 a a44440 0 1 00 0 1 0 0 1 0 00 1 0 01 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 P=a a3131 a a32 32 a a33 33 a a3434a a2121 a a22 22 a a23 23 a a24 24 a a1

47、111 a a12 12 a a13 13 a a1414a a4141 a a42 42 a a43 43 a a44 44 通过选通过选列主元列主元0 0 1 00 0 1 0 0 0 0 10 0 0 11 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 P=PAX=PBAX=B65 x x1 1+ 2x+ 2x2 2 + 4x+ 4x3 3+ x+ x4 4 =21=212x2x1 1+ 8x+ 8x2 2 + 6x+ 6x3 3+4x+4x4 4 =52=523x3x1 1+10x+10x2 2 + + 8x8x3 3+8x+8x4 4 =79=794x4x1 1+12x

48、+12x2 2 +10x+10x3 3+6x+6x4 4 =82=821 2 4 11 2 4 1 2 8 6 42 8 6 4 3 10 8 83 10 8 84 12 10 64 12 10 6A=1、构造矩阵构造矩阵L，U，P4 12 10 64 12 10 62 8 6 42 8 6 4 3 10 8 83 10 8 81 2 4 11 2 4 10 0 0 10 0 0 1 0 1 0 00 1 0 00 0 1 0 0 0 1 0 1 0 0 0 1 0 0 0 P=4 12 10 64 12 10 61/2 2 1 11/2 2 1 1 3/4 1 0.5 3.53/4 1 0.

49、5 3.51/4 1 1.5 1/4 1 1.5 0.50.5664 12 10 64 12 10 61/2 2 1 11/2 2 1 1 3/4 1 0.5 3.53/4 1 0.5 3.51/4 1 1.5 1/4 1 1.5 0.50.50 0 0 10 0 0 1 0 1 0 00 1 0 00 0 1 0 0 0 1 0 1 0 0 0 1 0 0 0 P=4 12 10 64 12 10 61/2 2 1 11/2 2 1 1 3/4 1 0.5 3.53/4 1 0.5 3.51/4 1 1.5 1/4 1 1.5 0.50.54 12 10 64 12 10 61/2 2 1

50、11/2 2 1 1 3/4 1/2 0 33/4 1/2 0 31/4 1/2 2 01/4 1/2 2 0=0 0 0 10 0 0 1 0 1 0 00 1 0 01 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 4 12 10 64 12 10 61/2 2 1 11/2 2 1 1 1/4 1/2 2 01/4 1/2 2 03/4 1/2 0 33/4 1/2 0 3U2、计算列向量计算列向量PBL2121525279798282P=8282525221217979673、用前向替换法对方程组用前向替换法对方程组LY=PB求解求解Y1 0 0 01 0 0 01/2

51、1 0 01/2 1 0 0 1/4 1/2 1 1/4 1/2 1 0 03/4 1/2 0 13/4 1/2 0 1y y1 1y y2 2y y3 3y y4 4=828252522121797982821111 6 612124、用回代法对方程组用回代法对方程组UX=Y求解求解X4 12 10 64 12 10 60 2 1 10 2 1 1 0 0 2 00 0 2 00 0 0 30 0 0 3x x1 1x x2 2x x3 3x x4 4=828211116 612121 12 23 34 468 %构造构造Pp=zeros(n,n);for i=1:n p(i,i)=1;en

52、dfor k=1:n-1 amax,j=max(abs(a(k:n,k); c=a(k,:); a(k,:)=a(j+k-1,:); a(j+k-1,:)=c; c=p(k,:); p(k,:)=p(j+k-1,:); p(j+k-1,:)=c; 69 for i=k+1:n m=a(i,k)/a(k,k); a(i,k)=m; a(i,k+1:n)=a(i,k+1:n)-m*a(k,k+1:n); endend %求求L、U%计算列向量计算列向量PBb=p*b;70用前向替换法对方程组用前向替换法对方程组LY=PB求解求解Yy(1)=b(1);y(1)=b(1);for i=2:nfor i

53、=2:n y(i)=b(i)-a(i,1:i-1)*y(1:i-1); y(i)=b(i)-a(i,1:i-1)*y(1:i-1);endend1 0 0 01 0 0 0 a a2121 1 0 0 1 0 0 a a3131 a a32 32 1 01 0 a an1n1 a an2 n2 a an3 n3 1 1y y1 1y y2 2y y3 3y yn n=b b1 1b b2 2b b3 3b bn n71用回代法对方程组用回代法对方程组UX=Y求解求解Xx(n)=y(n)/a(n,n);x(n)=y(n)/a(n,n);for i=n-1:-1:1for i=n-1:-1:1 x(ix(i)=(y(i)-a(i,i+1:n)*x(i+1:n)/a(i,i)=(y(i)-a(i,i+1:n)*x(i+1:n)/a(i,i)endenda a1111 a a12 12 a a13 13 a a1n 1n 0 a0 a22 22 a a23 23 a a2n 2n 0 00 0 a a33 33 a a3n 3n 0 00 0 0 0 a annnnx x1 1x x2 2x x3 3x xn n=y y1 1y y2 2y y3 3y yn n72