第2章-解线性方程组的直接法

第2章解线性方程组的直接法[教学目的与要求]1．理解求解线性方程组的直接法和迭代法的基本思想。2．掌握一般线性方程组的直接解法；3．掌握三对角线性带型方程组的解法；4．掌握线性方程组的迭代解法；5．掌握矩阵的三角分解。[重点与难点]重点：一般线性方程组的直接解法和迭代解法。难点：矩阵的三角分解。[教学安排]主要内容学时课后作业1直接法与三角形方程组的求解2Gauss列主元素消去法2P20~P218，15，23，29题3直接三角分解法2P44~P4515，17，21，22题4平方根法5追赶法2[授课内容]2.1直接法与三角形方程组的求解一、主要问题许多科学技术问题要归结为解含有多个未知量x1,x2,…,xn的线性方程组nnnnnnnnnnbxaxaxabxaxaxabxaxaxa22112222212111212111其矩阵形式为：Ax=b其中nnnnnnnnbbbbxxxxaaaaaaaaaA2121212222111211由克莱姆法则知，若|A|≠0,则线性方程组具有唯一解niAAxii,,2,1克莱姆法的计算量：n阶行列式的计算量：(n-1)n!次乘法.需要计算的行列式数量：n+1个n阶行列式除法数量：n次总共需要做乘除法数量：(n2-1)n!+n当n=10,乘除法的运算次数共为32659210次;当n=40,乘除法运算次数可达3.18*1049次.结论：在理论上完美的克莱姆法则，在实际计算中没有什么用！二、高斯消去法思想：利用方程组的同解变换，每次消去一个未知数，将原方程组化为低一阶的线性方程组，直到得到一个一元一次方程，然后解出该程的解并逐次回代求出全部解。1、消元过程：将（A|b）进行变换为)~|~(bA，其中A~是上三角矩阵。2、回代过程：由)~|~(bA解出11,,,xxxnn。三、直接三角分解法思想：将矩阵A分解成两个三角形矩阵L和U的乘积，其中L为下三角矩阵，U为上三角矩阵，即：1121,,,,,,xxxyUxyyybLybLUxbAxnnn，求，求2.2高斯消去法一、顺序消去法例：求解线性方程组1142331124342321321321xxxxxxxxx解：1160116000111011110221211521121011101111022121152112105212110221211114231124322121111423112434112解之得，3,1,1123xxx1、方法：对于AX=B1）、消元过程：将（A|B）进行变换为)~|~(BA，其中A~是上三角矩阵。即：nnnnnnnnnnnnbababaabaaabaaabaaa0010122111221222221111211k从1到n-1a、归一化kkkkkjkkkjbabnkjaaa/,,1,/b、消元nkibbabnkjnkiaaaaikikiijkjikij,,1,,,1;,,1,2）、回代过程：由)~|~(BA解出11,,,xxxnn。1,2,,1,/1nkbbabbabknkjjkjknnnn2、算法分析1）算法时间复杂度考虑乘除法次数a、归一、消元工作量第K次归一化：n-k+1次除法消元：(n-k+1)(n-k)次乘法合计：nknnnkn12)12)(1(61)1(（含计算xn的一次除法）b、回代工作量计算xk：(n-k)次乘法：回代合计：)1(21)(11nnknnk总计：nknknnnnknkn13211231)13(31)()1(2）算法的空间复杂度原地工作3）能用性与数值稳定性a、当|akk|=0时，运算中断b、当|akk|很小时，损失精度，商太大溢出结论：该算法数值计算是不稳定的二、列选主元消去法思想：主元要做除数，为减少舍入误差，主元的绝对值应尽量大。在进行第K步消元时，对K列选取绝对值最大元素iknikamax作为主元。三、全选主元消去法思想：在进行第K步消元时，对所剩下的k,k+1,…,n行和列选取绝对值最大元素ijnjika,max作为主元。问题：如何保存列交换信息。方法：设一个长度为n的一维数组JS(1:n)，其中JS(k)保存第k步时进行交换的列号。恢复时，将结果中的第k个分量与JS(k)个分量进行对换。四、高斯-约当消去法思想：将（A|B）进行变换为)~|~(BA，其中A~是单位矩阵，则B~为解向量。算法中无回代过程。算法时间复杂度：第K次归一化：n-k+1次除法消元：(n-k+1)(n-1)次乘法合计：nknnnnkn13221)1(21)1(2.3直接三角分解法一、问题A=LUL：主对角线为1的下三角矩阵U：上三角矩阵二、分解条件A的各阶顺序主子式不为0三、方法考虑高斯消去法的消元过程第一次消元：设1001011121211nlllL，其中1111aalii，则)1()2(3)1(2)1(3)1(33)1(32)1(2)1(23)1(2211312113213333231223222111312111212110001001011nnnnnnnnnnnnnnnnaaaaaaaaaaaaaaaaaaaaaaaaaaaaalllAL其中：jiijijalaa11)1(第K次消元：ALLLk12101010101,1nkkkkllL，其中)1()1(kkkkikikaal，则)()(1,)(,1)(1,1)1()1(1,)1()1(2)1(1,2)1(2)1(2211,111211000000000knnkkbknkkkkkknkkkkkknkknkkkaaaaaaaaaaaaaaaaA其中：)1()1()(kkjikkijkijalaa如此下去，则有ALLLAnn1211其中为1nA上三角矩阵。令1nAU，则ULLLAUALLLnn11211121令11211nLLLL，即有LUA。不难验证1111321212121nnnllllllL四、实现令nnnknnknkkkknknknullluulluuuluuuuIULQ2121222221111211并将Q中元素仍存放在A中，则：k从1到n-1nkjnkiaaaankiaaaijkjikijikkkik,1;,1,/,1,/算法时间复杂度：第K次：除法n-k次，乘法(n-k)(n-k)次总计：31131)1)((nknknnk例：设矩阵11242142612332442A求L和U。解：95/192205013632/324429192205013632/324421122214161232/3244211242142612332442A9000050036302442,15/192201010012/30001UL五、矩阵三角分解在解线性方程组中的应用1121,,,,,,xxxYUXyyyBLYBLUXBAXnnn，求，求优点：对于系数相同的线性方程组，避免重复消元，每次解方程只需增加n2次乘法运算。问题：不能进行全选主元2.4平方根法一、对称正定矩阵的三角分解(Cholesky(乔里斯基)分解)1、对称正定矩阵对称矩阵：TAA。对称正定矩阵：特征值都大于0实对称矩阵。特征值：方程0EA的n个根n,,,21即为A的n个特征值。充要条件：对称正定矩阵当且仅当A的所有顺序主子式都大于零。2、Cholesky(乔里斯基)分解ULA~~nkULAkkk,,2,1~~0~1~det~detdet1kiiikkkuULAkkkkkkiiikuAuuA~det~~det1110detdet~1kkkkAAu规定1det0ADUuuuuuuuuuuuuuuuuuuuuuuuuuuUnnnnnnnnnnnnn1~~1~~~~1~~~~~~1~~~~~~~~~~~~~~~1,1,1222222311111131112332211333223221131211令)~,,~,~(221121nnuuudiagD，则12121))(~(~~LUUDDLULA又因为TAA所以有TTLULU11因分解的唯一性，所以有TLU1即有TLLA定理(Cholesky分解)：设A是对称正定矩阵，则存在对角元全是正数的下三角形矩阵L，使得TLLA且该分解式唯一。二、分解条件A的各阶顺序主子式不为0三、方法讨论计算L，设11212212nnnnlllLlll假定已算出L的第1至1j列元素，比较TLLA中第j列主对角元以下（含主对角元）的对应元素，有),,1,(11njjillllajjijjkkjikij112jkjkjjjjlal11(1,,)jijikjkkijjjalllijnl规定上式中的010ikjkkll。用计算机实现时，可只存A的下三角部分于二维数组A中，用ijl冲掉ija。四、平方根法求解方程组Axb。完成对系数矩阵A的Cholesky分解后，解Axb化为解下面两个三角形方程组。(1)解Lyb，111111,(2,3,,)iiikkkiiibylblyyinl（2）解TLxy，注意TL的元素'ikkill，有1,(1,,2,1)nnnnnikikkiiiiyxlylxxinl例：用平方根法解对称正定方程组1171124471134241101110xxx解：先分解系数矩阵A，只对A的下三角形部分运算即可，故A只存系数矩阵的下三角形部分。以下A表示二维数组。1,2,3421711-2=L4211713114222jA分解解Ly=b，130,,24Ty解TLxy，25133,,64164Tx。五．平方根法的数值稳定性平方根法的分解过程没有选主元，方法的数值稳定性呢？有21(1,2,,)jjkjjklajn另外，L的对角元全都大于0，故1110maxmax