总结第3章线性方程组的数值解法

第3章线性方程组的数值解法第3章线性代数计算方法§1高斯消去法§2高斯―约当消去法§3解实三对角线性方程组的追赶法§4矩阵的三角分解§5行列式和逆矩阵的计算§6迭代法§7迭代法的收敛性第3章线性方程组的数值解法11112211211222221122nnnnnnnnnnnaxaxaxbaxaxaxbaxaxaxb阶线性方程组：[],X,11TnnijAXbTAnn,,),,)(x(bxbab矩阵表示记为这里第3章线性方程组的数值解法解线性方程组的两类方法:直接法:经过有限次运算后可求得方程组精确解的方法(不计舍入误差!)迭代法：从解的某个近似值出发，通过构造一个无穷序列去逼近精确解的方法(一般有限步内得不到精确解)第3章线性方程组的数值解法§1高斯消去法高斯消去法是一个古老的直接法，由它改进的方法是目前计算机上常用的求低阶稠密矩阵方程组的有效方法。思路首先将方程组Ax=b化为上三角方程组，此过程称为消去过程，再求解上三角方程组，此过程称为回代过程.第3章线性方程组的数值解法一、顺序消去法解方程组①②③(3―6)2x2xx40x5xx3xx2x321321321§1高斯消去法第3章线性方程组的数值解法作②-①消去②中的x1,作③-①×4消去③中的x1,则方程组(3―6)化为123232323363723xxxxxxx①②③(3―6′)对方程组(3―6′)作③-②×,得到三角形方程组7312323323363123xxxxxx①②③(3―6)第3章线性方程组的数值解法从方程组(3―6“)的方程③解出x3,将所得的结果代入方程②求出x2,再把x3、x2同时代入方程①解出x1。这样可求出方程组的解为123131,,424xxx12323323363123xxxxxx第3章线性方程组的数值解法2、顺序高斯消去法的计算步骤：在计算机上实现时,我们常把方程组右端的常数项排于系数矩阵的第n+1列，1）消元过程对于k=1,2,…,n-1列,若按顺序有某一ark≠0,r≥k,则交换k与r行,然后计算1,2,,/,1,2,,1ijkjikkkijikknaaaaajkkn(3―11)2）回代过程对于k=n,n-1,…,2,1,计算11()/nkknkjjkkjkxaaxa(3―12)第3章线性方程组的数值解法3、计算量N=N1+N2=n(n-1)/2+n(n-1)(n+1)/3=n3/3+n2-n/3Gauss消去法的运算次数与n3同阶，记为O(n3)克莱姆法则需运算次数为(n2-1)*n!+n第3章线性方程组的数值解法二、主元素消去法1.列主元素消去法所谓列主元素消去法就是在每一步消元过程中取系数子矩阵的第一列元素中绝对值最大者作主元。第3章线性方程组的数值解法取四位有效数字计算。解：第一列消元时，②中-18为主元,交换②和①得123123123123315183156xxxxxxxxx①②③123123123183151233156xxxxxxxxx①②③例1用列主元素消去法解方程组第3章线性方程组的数值解法②+①×12/18,③+①×1/18得1232323183152.3335.0001.1670.9445.167xxxxxxx①②③第二列消元时,主元为1.167,交换方程②和③得1232323183151.1670.9445.1672.3335.000xxxxxxx①②③第3章线性方程组的数值解法③+②×1/1.167得123233183151.670.944153.1429.428xxxxxx①②③回代求得x1=1.000,x2=2.000,x3=3.001方程组的实际解x1=1,x2=2,x3=3第3章线性方程组的数值解法列主元素消去法的计算过程:(1)消元过程。对于k=1,2,…,n-1进行下述运算:①选主元,确定r,使得若ark=0,说明系数矩阵为奇异,则停止计算；否则进行下一步。②交换A的r、k两行③对i=k+1,k+2,…,n,j=k+1,k+2,…,n+1计算maxrkrkikaa(3―14)aij-aik·akj/akk⇒aij(2)回代过程。对于k=n,n-1,…,1计算(3―16)11()/nkknkjjkkjkxaaxa第3章线性方程组的数值解法图3.1第3章线性方程组的数值解法图3.1第3章线性方程组的数值解法2.全主元素消去法所谓全主元素消去法,就是每步消元时选取系数子矩阵中绝对值最大的元素作主元。说明：若矩阵第i列与第j列对调,则未知数xi与xj也相应地对调了,xi的结果实质上为xj的结果。第3章线性方程组的数值解法例2用全主元素消去法求解方程组123123123123315183156xxxxxxxxx①②③解：这里主元为-18,交换方程①与方程②得1232323183152.333151.1670.9445.167xxxxxxx①②③123123123183151233156xxxxxxxxx①②③第3章线性方程组的数值解法再全选主元,主元为2.333,交换x2和x3所在的两列,同时改变两未知数的排列号得1232323183152.3335.0000.9441.1675.167xxxxxxx①②③③-②×0.944/2.333得123233183152.3335.0001.5723.144xxxxxx①②③已经化为三角方程组,回代求解x1=1.000,x2=3.000,x3=2.000这里未知数x2与x3已对调,所以应恢复解的顺序,方程组的实际精确解为x1=1.000,x2=2.000,x3=3.000第3章线性方程组的数值解法全主元素消去法的计算过程:(1)消元过程。对k=1,2,…,n-1进行下列运算:①选主元,确定r,t使得若art=0,则系数矩阵为奇异的,停止计算否则进行下一步。②交换A中的r、t两行及t、k两列,并记下交换的足码t、k。③对i=k+1,k+2,…,n,j=k+1,k+2,…,n+1计算(2)回代过程。对k=n,n-1,…,1，计算,maxnijijkaa(3―18)/ijikkjkkijaaaaa(3―19)11()/nkknkjjkkjkxaaxa(3―20)第3章线性方程组的数值解法图3.2第3章线性方程组的数值解法图3.2第3章线性方程组的数值解法§2高斯―约当消去法前面所述的消去法均要进行两个过程,即消元过程和回代过程。但对消元过程稍加改变可以把方程组(3―1)化为对角形*Dxb(3―21)1ndDd第3章线性方程组的数值解法§3解实三对角线性方程组的追赶法其中｜a1｜＞｜c1｜＞0｜ak｜≥｜bk｜+｜ck｜,bkck≠0,k=2,3,…,n-1｜an｜＞｜bn｜＞0我们将利用所谓“追赶法”解决第3章线性方程组的数值解法2122232122122122222122122223,rubcxxavbavbrubcuvavbavbxuvx111211111111,rcxxaarcuvaa令1112xuvx111kkkkkkkkkkkkrubuavbcvaubnnnnnnnnnnnnrxaxbrxcxaxbrxcxaxbrxcxaxbrxcxa111112134333232322212121111kkkkxuvx令其中当k=n时,因为bnxn-1+anxn=rn又xn-1=un-1-vn-1xn于是11nnnnnnnrubxavb追赶追赶第3章线性方程组的数值解法§4矩阵的三角分解对于线性方程组，若其系数矩阵A能够分解成两个三角形矩阵相乘,譬如,A=LUL为下三角矩阵,U为上三角矩阵,则求解方程组(3―1)就化为求解LUx=b令Ux=y则Ly=b第3章线性方程组的数值解法1.克劳特分解方法设A为n×n阶非奇异矩阵,且各阶主子矩阵为非奇异,则矩阵A的克劳特分解为A=LU其中nnn3n2n1333231222111llllllllllL1u1uu1uuu1U3n2n231n1312第3章线性方程组的数值解法这样,L、U中的元素都已求出。计算L的各列与U的各行的次序如下图所示。图3.4第3章线性方程组的数值解法克劳特分解求解线性方程组的计算过程:①LU分解过程:对于k=1,2,…,n依次计算1111,,1,,()/,1,2,,kikikisskskkjkjkssjkkslaluikknualuljkkn111()/,1,2,,,1,,1kkkkjjkkjnkkkjjjkyblylknxyuxknn②在L与U的元素算出后就可以设Ly=bUx=y解方程组LUx=b,从而求得方程组的解。第3章线性方程组的数值解法图3.5第3章线性方程组的数值解法图3.5第3章线性方程组的数值解法例4用克劳特分解方法求解下列方程组123121311504122xxx解：令111213212223313233001121001115001412luullulll第3章线性方程组的数值解法利用矩阵乘法可得到1121223132331213230010001304712112101012001001lllllluuu第3章线性方程组的数值解法这样原方程组就化为依次求下列两个三角形方程组1231122331003130047122121012001yyyxyxyxy12313,1,4yyy代入第二个方程组可求得原方程组的解为123131,,424xxx第3章线性方程组的数值解法2.杜利特尔分解方法杜利特尔分解方法是令A=LU这里nnn3n2n13n3332312n2322211n131211aaaaaaaaaaaaaaaaA第3章线性方程组的数值解法例5用杜利特尔分解方法求解下列方程组的解:1112132223331210036000012uuuUuuu123121311504122xxx解：利用式(3―50)、(3―51)可求得21313210010010110147/31Llll求得原方程组的解为123131,,424xxx第3章线性方程组的数值解法§5行列式和逆矩阵的计算5.1行列式的计算1.高斯消去法1122det(1)nnArrr第3章线性方程组的数值解法2.LU分解法①克劳特分解法:detA=detL·detU=detL=l11l22…lnn②杜利特尔分解法:detA=detL·detU=detU=u11u22…unn③乔累斯基分解法:这里A为正定矩阵。