1、1/29/20232第五章第五章 解线性方程组的直接方法解线性方程组的直接方法 5.1 5.1 引言引言解线性方程组的两类方法：直接法:经过有限次运算后可求得方程组精确解的方法(不计舍入误差)迭代法：从解的某个近似值出发，通过构造一个无穷序列去逼近精确解的方法。（一般有限步内得不到精确解）1/29/20239子阵作如上计算：对除第一行第一列外的，若第二步消元：0 )2(22a 00000 3332211(3)3333333322223222111131121113bbbbbaaaaaaaaaaaA)(n)()()()(nn)(n)(n)()(n)()()(n)()()()(=，aamamaai
2、jijij)2(22)2(2i2)2(2i2)2()3(322223 4,()()()iii ,n i jbbbm1/29/202310bxA)()(33 =得到同解方程组行下去则此消去过程可依次进，若 0)3(33a()()1 nnnxbA第步消去过程后，得到等价三角方程组。(1)(1)(1)(1)(1)11112213311(2)(2)(2)(2)22223322(3)(3)(3)33333 nnnnnna x a xa xa xba xa xa xba xa xb()()nnnnnna xb1/29/202311(1)(1)(1)(1)(1)11121311(2)(2)(2)(2)222
3、322(n)()(3)(3)(3)3333()()0 00000bnnnnnnnnnaaaabaaabAaabab，系数矩阵与常数项：1/29/202312回代过程:(1)(1)(1)(1)111111()()()(1)(1)(1)11111 iinniiiiiiinninnnnnnnnnna xa xa xba xa xbaxaxb()()nnnnnna xb abx)n(nn)n(nn=()()()1()in1,n2,1niiiiiijjiij ixba xa 1/29/20231312323123133233 6;45;221.11161116|041504152211041111116
4、04150026 (2),xxxxxxxxA brrrrrr例1：用消去法解方程组解：用增广矩阵表示求解过程1/29/202314消去第一列的 n-1 个系数要计算n*(n-1）个乘法。21 2 )*(n-(n-n-二)(nnk)(k nk13 212乘法总计21 11)n(n k nk除法1 2n(n)回代总计算量321(30,9890)33 nnnn总 乘 除 法 共为5.2.2 5.2.2 高斯消去法计算量高斯消去法计算量1/29/202315(2)(1)(2)(1)11112111113111 ,1101 2 3001L()()iin i,nbbAL ALmm aamm记：其中每一步消
5、去过程相当于左乘初等变换矩阵Lk5.2.3 5.2.3 矩阵的三角分解矩阵的三角分解1/29/202316(3)(2)(3)(2)222222223222 ,10101 3 4001L()()iini,nbbAL ALm aamm记：(3)(1)(3)(1)2121 ,bbAL L AL L1/29/20231711211121(n)()nn(n)()nn ALLL AbbLLL-1i1,1,110 10111 01010101 i iiiiininiLLmmmm列 i列i+1行 i+1行-1 iiLL与依次递推1/29/202318LUULLLAAn111211)1(111212111121
6、1mmmnnnLLLL定理定理7 7（矩阵的（矩阵的LULU分解）分解）设A为n阶矩阵，如果A的顺序主子式顺序主子式 D Di i0 0（i=1，2，n-1），则A可分解为一个单位下 三角矩阵L和一个上三角矩阵U的乘积，且这种分解是 唯一唯一的。)(nAU 1/29/202319()()213132 111161116|041504152211041111116 04150026 (1,)0,2,1,kikkikkkAbamiknammm 例 2：对 于 例，由 增 广 矩 阵 表 示 消 元 过 程 有由 故 有100111 010041.211002ALU 1/29/2023205.3 5
7、.3 高斯主元素消去法高斯主元素消去法()()00kkkkkkaa在高斯法消元过程中可能出现的情况，这时消去法将无法进行；即使主元素但很小，用其作除数，也会导致其他元素数量级的严重增长和舍入误差的扩散。为避免此种情况的发生，可通过交换方程的次序，选取绝对值大绝对值大的元素作主元。5.3.1 列主元素消去法1/29/202321nkkjiaakijkkk,1,max)()(选取或nkkiaakikkkk,1,max)()(称此方法为全主元素高斯消去法称此方法为列主元素高斯消去法1/29/202322123*0.0012.000 3.0001.000 31.000 3.712 4.6232.000
8、2.000 1.072 5.6433.000(0.4904,0.05104,0.3675)10.0012.000 3.000 1.000|1.000TxxxxA b 例：阶方程组四位有效数字精确解为解：（）高斯消去法212232100020001.9973.712 4.623 2.0002.000 1.072 5.643 3.0000.001 2.000 3.000 1.0000.001 2.000 3.000 1.000020043005100202004300510020400160062003005.000 2.000(0.mmmx 400,0.09989,0.4000)T3m31=-2
9、0001/29/20232321220.50000.000522.000 1.072 5.643 3.000|1.000 3.712 4.623 2.0000.0012.000 3.000 1.0002.000 1.072 5.643 3.000 03.712 1.801 0.50002.001 3.003 1.002mmA b （）交换行，避免绝对值小的主元作除数。（列主元素法）320.63002.000 1.072 5.643 3.000 03.712 1.801 0.500001.868 0.687 (0.4900,0.05113,0.3678)mTx 31rr m31=-0.00051
10、/29/202324定理8（列主元素的三角分解定理）如果A为非奇异 矩阵，则存在排列矩阵P使 PA=LU 其中L为单位下三角阵，U为上三角阵。1/29/2023253 2GaussJordanAn消去对角线下方和上方的元素，此方法称消去法。G-J方法将 约化为单位矩阵，计算解就在常数项得到，无需回代求解。计算量大约需次乘除法，要比高斯消去法大。G-J方法主要用途是求一个矩阵的逆矩阵。1123 5 G-J245.356123100356001|245010245010356001123100nAAA I例：用法求的逆矩阵解：5.3.2 5.3.2 高斯高斯若当消去法若当消去法1/29/20232
11、6115/32001/3 02/31012/301/31101/3101/205/22013/203/21001/211/20100132 010331|.001210nIA1/29/2023275.4 矩阵三角分解法矩阵三角分解法5.4.1 直接三角分解法直接三角分解法将高斯消去法改写为紧凑形式，可以直接从矩阵A的元素得到计算L,U元素的递推公式，而不需要任何中间步骤，这就是直接三角分解法。由于A=LU，求解Ax=b的问题就等价于求解两个三角形方程组 Ly=b，求y；Ux=y，求x.1/29/2023281、不选主元的三角分解法nnnnnnuuuuuulllA222112112121111A
12、=LU其中L为单位下三角阵，U为上三角阵（4.1）1/29/202329一、直接计算 A 的 LU 分解(例)000000 1010010001 4434334423221413121143424132312144434241343332312423222114131211uuuuuuuuuullllllaaaaaaaaaaaaaaaauulululululululululuululuulululululuuluuluululuuuu443443244214413343234213412242124111413424321431332332133122321231113124142123132
13、1221221112114131211+1/29/202330uulululululululululuululuulululululuuluuluululuuuu4434432442144133432342134122421241114134243214313323321331223212311131241421231321221221112114131211+n.,3,i -;-,-2 n,2,j ,-;-,-,-u2n,2,i ,;,1 n,1,j ,;,12212i22i22212414242221231323212122j142124241321232312212222111i1114
14、14111313111212111j1414131312121111uulaluulaluulalulauulauulauulauualualualualauauauauau)()()(lluijjij列行列行1/29/202331二、一般计算公式n ,2,i ,n,1,j ,111i111ualauijjn)r,n;,r (i)/(,nr,ri n),(rrLrUuulalulaurrrkkrikirirrkkirkriri且1);1(321111列元素的第行，的第计算1/29/202332三、LU 分解求解线性方程组 LY b,UXY AXb112221313212(1)1111121n2
15、2222nnn111 1 U Xnnnnn nnnybybLYbybxyxyYxylllllluuuuuu 1/29/20233311-11,2,3,1,Y iiijijjinybyybl解：1ijii ,in1,1 2,x nnnniijijnyxuyxu xu解：矩阵A的直接分解法称为杜利特尔（Doolittle）分解1/29/202334例1：将方程组7109576910688565710787104321432143214321xxxxxxxxxxxxxxxx的系数矩阵A作LU分解，并求方程组的解1/29/202335解710957691068856571078710bALU分解的紧凑
16、格式为5.05.117.03248.01.04.01.07.0787101/29/202336推出：5.0321.04.01.07871015.117.0148.017.01A86110y由Ly=b得1/29/202337由Ux=y，即861105.0321.04.01.0787104321xxxx用回代法解得60,102,27,161234xxxx即为线性方程组的解1/29/2023382、选主元的三角分解法采用与列主元消去法类似的方法，通过交换A的行实现矩阵PA的LU分解。1/29/202339本章作业1、设Ax=b，用LU分解法求此方程组11115675781079108610975bA2、P230 740 结束语结束语
