解线性方程组的直接方法主元素方法

1第二章解线性方程组的直接方法)(kkka1nGauss消去法简单易行，但其计算过程中，要求(称为主元素)均不为零，因而适用范围小，只适用于从1到先看一个例子。阶顺序主子式均不为零的矩阵A，计算实践还表明,Gauss消去法的数值稳定性差,当出现小主元素时,会严重影响计算结果的精度,甚至导出错误的结果.§2主元素法第二章解线性方程组的直接方法96.05.696.00.5020.036.05.40.20.61.31.150.0321321321xxxxxxxxx(2-10a)式（2-10a）中所有系数均有2位有效数字.[解]为减少误差，计算过程中保留3位有效数字.按Gauss消去法步骤，第一次消元得同解方程组123230501131600100120240.x.x.x..x.x.例2求解方程组223100245590.x.x.3第二章解线性方程组的直接方法第二次消元得246012200.240.12100.00.61.31.150.0332321xxxxxx80.5,40.2,02.2123xxx00.2,00.1,60.2321xxx回代得解容易验证，方程组（2-10）的准确解为显然两者相差很大.但若在解方程组前,先把方程的次序4第二章解线性方程组的直接方法交换一下,如把（2-10a）改写成0.61.31.150.0020.036.05.40.296.05.696.00.5321321321xxxxxxxxx)102(b99.599.2364.024.212.496.05.696.00.5332321xxxxxx再用Gauss消去法求解，消元后得同解方程5第二章解线性方程组的直接方法60.2,00.1,00.2123xxx(1)(2)11220.50,0.100aa产生上述现象的原因在于舍入误差.因为按式(2-10)的方程顺序进行消元时，主元回代得解与准确解相同.都比较小，以它们为除数就增长了舍入误差，从而导致计算结果不准确。为了在计算过程中，抑制舍入误差的增长,应尽量避免小主元的出现.如例2中第二种解法,通过交换方程次序,选取绝对值大的元素作主元.基于这种想法导出了主元素法.6第二章解线性方程组的直接方法nnnnnnnbaaabaaabaaabA21222221111211],[)112(2.2.1列主元素法为简便起见，我们用方程组（2-1）的增广矩阵表示它，并直接在增广矩阵上进行运算.7第二章解线性方程组的直接方法是在每次消元前，在要消去未知数的系数中找到绝对值最大的系数作主元，通过方程对换将其换到对角线上，然后进行消元。具体步骤如下：11,ia||max||1111iniiaa1i],[)1()1(bA第一步：首先在矩阵（2-11）的第1列中选取绝对值则中第1行与第矩阵为，然后进行第一次消元，得矩阵最大的元，比如为将(2-11)行互换.为方便起见,记行互换后的增广列主元素法基本思想:8第二章解线性方程组的直接方法)2()2()2(2)2(2)2(2)2(22)1(1)1(1)1(12)1(11)2()2(],[nnnnnnbaabaabaaabA],[)2()2(bA2(2)2,ia2(2)(2)222||max||.iiinaa],[)2()2(bA2i],[)3()3(bA第二步：在矩阵的第2列中选主元，比如使将矩阵行与第行互换，再进行第二次消元，得矩阵的第2k],[)()(kkbA(),kkika()()||max||.kkkikikkinaa],[)()(kkbAkkik第步：在矩阵的第k列中选主元，如使将的第行与第行互换，进行第次消元.9第二章解线性方程组的直接方法1n),,,,()(nkkjiakij1如此经过步，增广矩阵（2-11）被化成上三角形，最后由回代过程求解。在上述过程中，主元是按列选取的，列主元素法由此得名.例2中的第二种解法就是按列主元素法进行的.2.2.2全主元素法如果不是按列选主元，而是在全体待选系数中选取主元，则得到全主元素法，其计算过程如下：p1110第二章解线性方程组的直接方法),,1,(njiaij)1(11a],[)2()2(bAk)(kA)1(kn),,1,,()(nkkjiakij)(kkkak1n第一步：在全体系数值最大的元作为主元，并通过行与列的互换把它换到中选取绝对的位置，然后进行第一次消元,得到矩阵第步：在矩阵的右下方阶子矩阵的所有元素中,选取绝对值最大的元作为主元,并通过行与列的互换将它换到的位置，然后进行第次消元.经过次消元后,得到与方程组(2-1)同解的上三角形方程组,再由回代过程求解.11第二章解线性方程组的直接方法例3用主元素法求解线性方程组231231236123315183151xxxxxxxxx计算过程保留三位小数。[解]按列主元素法，求解过程如下:1116123315311518p13p912第二章解线性方程组的直接方法3115123315111618第一行与第三行互换3115012.333500.9445.167181.167第一次消元311500.9445.167012.3335181.167第二，三行互换311500.9445.167003.1429.428181.167第二次消元13第二章解线性方程组的直接方法001.33x000.22x000.11x由回代过程得解按全主元素法，求解过程如下:11161233153115183115123315111618第一行与第三行互换p1114311501501.1670.9445.167182.333第一次消元131501500.9441.1675.167182.333第二，三列互换1x2x3xb1x2x3xb15第二章解线性方程组的直接方法1315015001.5723.144182.333第二次消元22.000,x33.000,x000.11x由回代过程得解例3的计算结果表明，全主元素法的精度优于主元素法,这是由于全主元素是在全体系数中选主元，故它对控制同解方程组为13218315xxx1x2x3xb21.5723.144x322.3335xx16第二章解线性方程组的直接方法舍入误差十分有效。但全主元素法在计算过程中，需同时作行与列的互换，因而程序比较复杂，计算时间较长.列主元素法的精度虽稍低于全主元素法，但其计算简单,工作量大为减少,且计算经验与理论分析均表明,它与全主元素法同样具有良好的数值稳定性，故列主元素法是求解中小型稠密线性方程组的最好方法之一.17第二章解线性方程组的直接方法§2.3直接三角分解法2.3.1Gauss消去法的矩阵形式如果用矩阵形式表示，Gauss消去法的消元过程是对方程组（2-1）的增广矩阵[A，b]进行一系列行初等变换，将系数矩阵A化成上三角形矩阵的过程.将系数矩阵A化成上三角形矩阵的过程，也等价于用一串初等矩阵去左乘增广矩阵，因此消元过程可以通过矩阵运算来表示。我们知道,对矩阵进行一次初等行变换,相当于用相应的初等矩阵去左乘原来的矩阵.18的系数矩阵A的顺序主子式不为零bAx1112121222120,1,2,,1,kkkkkkkaaaaaaAknaaa在Gauss消去法中,第一次消元时等价于用单位下三角阵设方程组19第二章解线性方程组的直接方法1000100010001131211nlllL(1)(1)[,][,],AbAb),,,(/)()(niaalii32111111(2)(2)(1)(1)1[,][,]AbLAb其中（2-12）左乘矩阵即20,)(0)det((2)22(1)1122aaA,0(2)22a进行第二次消元时等价于用矩阵232210000100010001nLll左乘],[)()(22bA其中),,,(/)()(niaalii43222222于是有(3)(3)(2)(2)2[,][,]AbLAb第二章解线性方程组的直接方法11111kkknkOLOllO),,(/)()(nkiaalkkkkikik11n一般地，第k次消元等价于用矩阵其中经过次消元后得到（2-13）左乘矩阵21()()[,],kkAb2122第二章解线性方程组的直接方法)()()()()()()()()()()(],[nnnnnnnnnbabaabaaabA022222221111112111)1,,2,1(nkLk因为的逆矩阵存在。容易求出],[)1()1(1nnnbAL],[)1()1(121bALLLnn均为非奇异阵，故它们23第二章解线性方程组的直接方法111111kkknkOLlOlO（2-14）令23242131321111211231100010010101nnnnnnlllLLLLllll(1)(1)[,][,]AbAb()()[,][,]nnAbLALb于是有(2-15)即（2-16）()()(1)(1)121[,][,]nnnnAbLLLAb121()()121[,]nnnLLLAb25第二章解线性方程组的直接方法LUALU其中为单位下三角矩阵，为上三角矩阵。这说明，消元过程实际上是把系数矩阵A分解成单位下三角阵与上三角矩阵的乘积的过程。2131321,11,21,31231100001000100101nnnnnnnnlllLlllllll26第二章解线性方程组的直接方法1112131222320nnnnuuuuuuuUuLUbAxbLyyUx上述分解称为杜利特尔（Doolittle）分解，也称为的问题就变得十分容易，它等价与求解两个三角形方程组和分解.当系数矩阵进行三角分解后，求解方程组因此，解线性方程组问题可转)(bLUxLUA27第二章解线性方程组的直接方法化为矩阵的三角分解问题。)1,,2,1(niAi1j0111aA2.3.2矩阵的三角分解正如Gauss消去法要在一定条件下才能进行到底一样矩阵A也必须满足一定条件才能进行三角分解.定理2.１设Ａ为n阶方阵，若Ａ的顺序主子式［证明］当均不为零，则矩阵Ａ存在唯一的Doolittle分解。时，因为由３.１段的讨论，存在矩阵p3328第二章解线性方程组的直接方法2111111nOlLlO),3,2(/1111niaaliiALA1)2()2()2(2)2(2)2(22112110nnnnnaaaaaaa其中,使得29第二章解线性方程组的直接方法由行列式的性质易得)2(A)1,,2,1()2(niAi0detdet)2(iiAA的各阶顺序主子式满足)()()()()2(2)2(221