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

1第5章解线性方程组的直接方法5.1引言与预备知识5.2高斯消去法5.3矩阵三角分解法5.4向量和矩阵的范数5.5误差分析25.1引言与预备知识5.1.1引言在自然科学和工程技术中很多问题的解决常常归结为解线性代数方程组,而这些方程组的系数矩阵大致分为两种:一种是低阶稠密矩阵(例如:阶数不超过150);另一种是大型稀疏矩阵(矩阵阶数高且零元素较多).3解线性方程组的方法(1)克莱姆法则1112121222120,nnnnnnaaaaaaDaaa当12,1,2,...,,.iiTinDxinDDD为中第i列换成(b,b,...,b)1112111212222212,nnnnnnnnaaaxbaaaxbaaaxb若n=30,需要计算31个30阶的行列式,计算31*30！*29次乘法和同样次数的加法.若用10亿次每秒乘法的计算机大约需要计算7.556*10^18年,因此,克莱姆法则此时没什么用。然而其计算每个解是相互独立的,在并行机上用Cramer法则有实用价值.4所以要介绍求解线性方程组的数值解法若利用矩阵逆,17*210.142857*212.99999.,x则需要一个除法和乘法运算而且产生不精确的结果.11(2),,.AxbxAbA然而计算很困难且有误差考虑方程721.x52.迭代法是用某种极限过程去逐步逼近线性方程组精确解的方法.(下章)线性方程组的数值解法一般有两类：1.直接法经过有限步算术运算，可求得方程组精确解的方法(若计算过程中没有舍入误差).（本章）基本定义、性质、定理(p138-142)(自学)65.2高斯消去法5.2.1引例下面通过具体实例对解方程组直接法进行介绍.解线性方程组解:法一.中学所学消元法法二.高等代数所学行、列变换12312312324326.225xxxxxxxxx71323123123(2)(3)211431261225033605491225EEEExxxxxx进行行、列变换右端增广矩阵右端特点:允许行运算,不允许行、列变换消去非零元(哪里容易化就去消去它,哪里运算简单就去哪里运算)85.2.2高斯消去法基本思想(1)最简单的方程组(系数矩阵A为三角阵)111122220000,00nnnnaxbaxbaxb/,1,2,...,iiiixbain计算机语言C(1,,)/iiiiforiiinxba9(2)方程组系数矩阵A为上三角阵1112111222220,00nnnnnnaaaxbaaxbaxb1/()/,1,2,...,1.nnnnniiijjiijixbaxbaxainn向后递推公式10(3)方程组系数矩阵A为下三角阵111121222212000,nnnnnnaxbaaxbaaaxb111111/()/,2,3,...,.iiiijjiijxbaxbaxain向前递推公式直接求解线性方程组的思路：(1)任何方程组均朝上述三种方程组方向转化,(2)转化方式不同决定了不同的方法.115.2.3高斯消去法基本方法(分消去过程和回代过程)设有线性方程组（2.1）或写为矩阵形式,2121212222111211mnmnmmnnbbbxxxaaaaaaaaa简记为.bAx11112211211222221122nnnnnnnnnnaxaxaxbaxaxaxbaxaxaxb12例2用消去法解方程组)4.2(.122)3.2(,54)2.2(,632132321xxxxxxxx解第1步.将方程(2.2)乘上加到方程(2.4)上去，消去(2.4)中的未知数得到,1x2)5.2(.11432xx第2步.将方程(2.3)加到方程(2.5)上去，消去方程(2.5)中的未知数,2x13得到与原方程组等价的三角形方程组.62)6.2(,54,6332321xxxxxx显然，方程组(2.6)是容易求解的，解为.)3,2,1(Tx上述过程相当于112251406111bA111405140611114620051401111331)2(rrr332rrr其中用表示矩阵的第行.iri由此看出，用消去法解方程组的基本思想是用逐次消去未知数的方法把原方程组化为与其等价的三角形方程组，而求解三角形方程组可用回代的方法.bAx上述过程就是用行的初等变换将原方程组系数矩阵化为简单形式(上三角矩阵)，从而将求解原方程组(2.1)的问题转化为求解简单方程组的问题.15或者说，对系数矩阵施行一些行变换(用一些简单矩阵)将其约化为上三角矩阵.A下面讨论求解一般线性方程组的高斯消去法.将(2.1)记为,)1()1(bxA.),()()1()1()1(bbaaAijij(1)第1步).1(k设首先计算乘数,0)1(11a.),,3,2(/)1(11)1(11miaamii用乘(2.1)的第一个方程，加到第个方程上，1imi(2,3,,)in消去(2.1)的从第二个方程到第个方程中n其中11112211211222221122nnnnnnnnnnaxaxaxbaxaxaxbaxaxaxb16的未知数得到与(2.1)等价的方程组,ix（2.7）(1)(1)(1)(1)1111211(2)(2)(2)22222(2)(2)(2)20.0nnnnnnnxaaabxaabxaab简记为,)2()2(bxA其中的元素计算公式为)2()2(,bA.,,3,2,,,3,2,)1(11)1()2()1(11)1()2(nibmbbnjiamaaiiijiijij17(2)第次消元k).,,2,1(nk设上述第1步，…，第步消元过程计算已经完成，1k（2.8）(1)(1)(1)(1)(1)11112111(2)(2)(2)(2)222222()()()()()(),knknkkkkkkknkkknnnknnnxaaaabxaaabxaabxaab即已计算好与(2.1)等价的方程组简记为.)()(kkbxA18设计算乘数,0)(kkka.),,1(/)()(nkiaamkkkkikik加到第个方程i),,,1(nki用乘(2.8)的第个方程，ikmk消去从第个方程到第个方程中的未知数得到与n,kx1k元素的计算公式为)1()1(,kkbA显然中从第1行到第行与相同.)1(kAk)(kA.)1()1(kkbxA(2.1)等价的方程组,,,1,,,1,)()()1()()()1(nkibmbbnkjiamaakkikkikikkjikkijkij（2.9）19(3)继续上述过程，且设),1,,2,1(0)(nkakkk直到完成第步消元计算.1n最后得到与原方程组等价的简单方程组,)()(nnbxA（2.10）.)()2(2)1(121)()2(2)2(22)1(1)1(12)1(11nnnnnnnnbbbxxxaaaaaa由(2.1)约化为(2.10)的过程称为消元过程.20如果是非奇异矩阵，且nnAR),1,,2,1(0)(nkakkk求解三角形方程组(2.10)，得到求解公式,/)()(nnnnnabx).1,,2,1(nnk（2.11）(2.10)的求解过程(2.11)称为回代.)(1)()(/)(kkknkjjkkjkkkaxabx21例如于是交换两行元素(即），将调到(1,1)位置，然后进行消元计算，这时右下角矩阵为阶非奇异矩阵.,011ia11irr11ia)2(A1n继续这过程，高斯消去法照样可进行计算.如果由于为非奇异矩阵，所以的第一列一定有元素不等于零.,011aAA22定理5设其中,bAx.RnnA(1)如果),,,2,1(0)(nkakkk将约化为等价的三角形方程组(2.10).bAx则可通过高斯消去法(a)消元计算)1,,2,1(nk),,,1(/)()(nkiaamkkkkikik),,,1,()()()1(nkjiamaakkjikkijkij).,,1()()()1(nkibmbbkkikkiki（2.10）.)()2(2)1(121)()2(2)2(22)1(1)1(12)1(11nnnnnnnnbbbxxxaaaaaa且计算公式为：23(b)回代计算,/)()(nnnnnabx).1,,2,1(/)()(1)()(nniaxabxiiinijjiijiii(2)如果为非奇异矩阵，则可通过高斯消去法(及交换两行的初等变换)将方程组约化为(2.10).AbAx（2.10）.)()2(2)1(121)()2(2)2(22)1(1)1(12)1(11nnnnnnnnbbbxxxaaaaaa24以上消元和回代过程的总乘除法次数为加减法次数为,333323nnnn.3323323nnnn高斯消去法的算法分析:消去过程:第k步需除法运算n-k次.乘法运算(n-k)(n+1-k)次减法运算(n-k)(n+1-k)次总共乘除法次数：减法次数：311()(1)33nknnnknk3211115()()(1)326nnkknnnnknknk回代过程:第k步需乘除法运算n(n+1)/2次.加减法运算n(n-1)/2次25高斯消去法对于某些简单的矩阵可能会失败，.0110A由此，需要对前述算法进行修改，首先需要研究原来的矩阵在什么条件下才能保证例如).,2,1(0)(kakkkAP146定理6约化的主元素的充要条件是矩阵的顺序主子式即),,2,1(0)(kiaiiiA).,,2,1(0kiDi,0111aD（2.12）).,,2,1(01111kiaaaaDiiiii26例题：用Gauss消去法解方程组1231231232350422xxxxxxxxx121311504122解：消去过程32:3/(12)1/4;36*(1/4)/(3)3/2xx回代过程12130363072101213036300123132*(3/2)(1)*(1/4)1/4x1231/4,3/2,1/4