计算方法-第六章-解线性方程组的直接法

AX=bnnnnnnnnbbbbxxxXaaaaaaaaaA2121212222111211nnnnnnnnnnbxaxaxabxaxaxabxaxaxa22112222212111212111（3.1）第三章解线性方程组的直接法§1高斯消去法1．三角形方程组的解法nnnnnnbxaxaxabxaxabxa221122221211111（3.2）nnnnnnnnbxabxaxabxaxaxa2222211212111（3.3）首先将A化为上三角阵，再回代求解。=nnnniinnnnnnnnnnnbxaniabxaxabxaxabxaxaxa),......,2,1(0....................................................................................................111112222211212111其中Axb(一)高斯消去法的求解过程,可分为两个阶段:首先,把原方程组化为上三角形方程组,称之为“消元”过程;然后,用逆次序逐一求出三角方程组(原方程组的等价方程组)的解,并称之为“回代”过程.下面分别写出“消元”和“回代”两个过程的计算步骤.记,)()1()1(nnijaAA(1)(1)(1)1(,,)TnbbbbStep1：设，计算因子0)1(11a)...,,2(/)1(11)1(11niaamii将增广矩阵第i行mi1第1行，得到)...,,2,()1(11)1()2()1(11)1()2(njibmbbamaaiiijiijij其中(1)(1)(1)(1)111211(2)(2)...naaabOAbStepk：设，计算因子0)(kkka)...,,1(/)()(nkiaamkkkkikik)...,,1,()()()1()()()1(nkjibmbbamaakkikkikikkjikkijkij共进行？步)()2(2)1(121)()2(2)2(22)1(1)1(12)1(11..................nnnnnnnnbbbxxxaaaaaan1且计算回代)()(/nnnnnnabx若A的所有顺序主子式均不为0，则高斯消元无需换行即可进行到底，得到惟一解。)1...,,1()(1)()(niaxabxiiinijjiijiii利用高斯消元法求解方程组:解：§1.2高斯消元法_例题分析12341234123412346x-2x+2x+4x=1212x-8x+6x+10x=343x-13x+9x+3x=27-6x+4x+x-18x=-3812341234123412346x-2x+2x+4x=1212x-8x+6x+10x=34(1)3x-13x+9x+3x=27-6x+4x+x-18x=-38,i=2,3,4.i1i111r-r12342342342346x-2x+2x+4x=12-4x+2x+2x=10(2)-12x+8x+x=212x+3x-14x=-26利用得利用,i=3,4.(2)i2i2(2)22αr-rα得123423434346x-2x+2x+4x=12-4x+2x+2x=10(3)2x-5x=-94x-13x=-21利用得显然，方程组(4)与(1)是等价的，其系数矩阵为上三角状的，易于求解.称以上过程为高斯消去法的消去过程.通过方程组(4)的回代求解，可以得到准确解为T*=[1-3-21]x这一过程为高斯消去法的回代过程。,i=4.(3)i3i3(3)33αr-rα12342343446x-2x+2x+4x=12-4x+2x+2x=10(4)2x-5x=-9-3x=-3nkinkjaaaankkjaaakkjkikkijkijkkkkkjkkj,11,,11,,1,)()1()1()()1()1()(消元公式1,,11)()(1,)(1,nkxaaxaxnkjjkkjknkknnnn回代公式§1.3高斯消元法_选主元消去法Gauss消元法第k次消元是用第k个方程主元素及其选取问题)()()(kknkknkkkkbxaxa来消去第k+1,…,n个方程中的xk,条件是.()0kkka)(kkka是实现第k次消元的关键元素，称为第k次消去的主元.Gauss消元法存在的问题是：例：单精度解方程组211021219xxxx/*精确解为和*/...1000...00.1101191x8个...8999...99.0212xx8个用GaussianElimination计算：911212110/aam9992221a1m10.0...011010108个92121012mb9991010011100,112xx用小主元10-9作除数，致使其它元素的数量级大大增加，舍入误差的扩散将准确解淹没了。§1.3高斯消元法_选主元消去法全主元消去法每一步选绝对值最大的元素为主元素，保证。1||ikmStepk:①选取;0||max||,ijnjikjiaakk②Ifikkthen交换第k行与第ik行;Ifjkkthen交换第k列与第jk列;③消元注：列交换改变了xi的顺序，须记录交换次序，解完后再换回来。算法：1.消元过程，对(1)选主元，找使得(2)若，则停止，推出(3)若，则换行，(4)消元，对有考虑在整个矩阵范围选主元，这就是所谓的全主元消去法，此时要注意的是，在做列的变换时，要同时记录当前变量的次序，以免自变量的含义不清。1,2,,1kn()0kkika{,1,,}kikkn()()maxkkkikikkinaadet0Akik()()(,,1)kkkkjijaajkn1,,ikn()()/kkikikkkmaa1,,1jkn有(1)()()kkkijijikkjaama回代过程：(1)若，则停止(2)对det0A()()(),11()/nnnniinijjiijixaaxa()0nnna,,1in例：211111091,112xx11021111102119注：列主元法没有全主元法稳定。0,112xx例：211101019999991010010101列主元消去法0||max||,iknikkiaak在计算机上实现全主元素消去法意味着进行数的比较操作，选全主元素法需要相当多的计算时间，因此常采用局部选主元素的方法.省去换列的步骤，每次仅选一列中最大的元。例题分析（Guass全选主元法)精确解为：x1=1.9273,x2=-0.698496,x3=0.9004233123121230.0022.0002.0000.4001.0000.781251.38163.9965.56254.0007.4178xxxxxxxx例题分析（Guass列选主元法)精确解为：x1=1.9273,x2=-0.698496,x3=0.9004233123121230.0022.0002.0000.4001.0000.781251.38163.9965.56254.0007.4178xxxxxxxx列主元消去法计算步骤：1、输入矩阵阶数n，增广矩阵A(n,n+1);2、对于nk,,2,1(1)按列选主元：选取l使0maxikniklkaa(2)如果，交换A(n,n+1)的第k行与底l行元素kl(3)消元计算：nkiaamkkikik,,11,,1,,1,nkjnkiamaakjikijij3、回代计算1,,1,11,nnixaaxnijjijnii4．无回代过程的主元消去法算法：第一步：选主元，在第一列中选绝对值最大的元素，设第k行为主元行，将主元行换至第一行，将第一个方程中x1的系数变为1，并从其余n–1个方程中消去x1。第二步：在第二列后n–1个元素中选主元，将第二个方程中x2的系数变为1，并从其它n–1个方程中消去x2。第k步：在第k列后n–k个元素中选主元，换行，将第k个方程xk的系数变为1，从其它n-1个方程中消去变量xk，…………nkkinkkjaaaankkjaaakkjkikkijkijkkkkkjkkj,,1,1,,11,,1,1,,1,)()1()1()()1()1()(消元公式为：对k=1,2,…,按上述步骤进行到第n步后，方程组变为：)(1,)(1,22)(1,11nnnnnnnnaxaxax即为所求的解5．无回代消去法的应用（1）解线性方程组系设要解的线性方程组系为：AX=b1,AX=b2,…AX=bmniaaabxxXaaaaAinninininnnnn,,2,1)(1,)(1,2)(1,111111上述方程组系可以写为AX=B=(b1,…,bm)因此X=A-1B即为线性方程组系的解。在计算机上只需要增加几组右端常数项的存贮单元，其结构和解一个方程组时一样。行n21nnnnnnaaaaaaaaa212222111211)(1,)1(1,)(1,2)1(1,2)(1,1)1(1,1mnnnnmnnmnnaaaaaa系数右端（2）求逆矩阵设A=(aij)nn是非奇矩阵，A0，且令nnijXAX)(1由于AA-1=AX=I因此，求A-1的问题相当于解下列线性方程组1010,,0012112111nnnnnxxxAxxxA相当于（1）中m=n,B=I的情形。（3）求行列式的值用高斯消去法将A化成)()1(11)()2(22)1(11nnnnnnaaaaaA§2解三对角方程组的追赶法nnnnnnnnnnnnkkkkkkkdxbxadxcxbxadxcxbxadxcxbxadxcxb111112111232221212111nnnnnkkkbacbacbacbacbA11122211nkarbaydyarbcrbdybcrkkkkkkkkkkkk,,3,21111111111,,2,11nnkxryxyxkkkknn高斯消元法的矩阵形式:Step1:)0(/111111aaamii§3矩阵的三角分解及其在解方程组中的应用记L1=1...11121nmmL1－1=1...11121nmm记AA)1(于是)1(1)1(22)1(21)1(1)1(12)1(11)1(11)1(1)1(11