资源描述:
《总结第3章线性方程组的数值解法.ppt》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、第3章线性代数计算方法§1高斯消去法§2高斯―约当消去法§3解实三对角线性方程组的追赶法§4矩阵的三角分解§5行列式和逆矩阵的计算§6迭代法§7迭代法的收敛性解线性方程组的两类方法:直接法:经过有限次运算后可求得方程组精确解的方法(不计舍入误差!)迭代法:从解的某个近似值出发,通过构造一个无穷序列去逼近精确解的方法(一般有限步内得不到精确解)§1高斯消去法高斯消去法是一个古老的直接法,由它改进的方法是目前计算机上常用的求低阶稠密矩阵方程组的有效方法。思路首先将方程组Ax=b化为上三角方程组,此过程称为消去过程,再求解上
2、三角方程组,此过程称为回代过程.一、顺序消去法解方程组①②③(3―6)§1高斯消去法作②-①消去②中的x1,作③-①×4消去③中的x1,则方程组(3―6)化为①②③(3―6′)对方程组(3―6′)作③-②×,得到三角形方程组①②③(3―6")从方程组(3―6“)的方程③解出x3,将所得的结果代入方程②求出x2,再把x3、x2同时代入方程①解出x1。这样可求出方程组的解为2、顺序高斯消去法的计算步骤:在计算机上实现时,我们常把方程组右端的常数项排于系数矩阵的第n+1列,1)消元过程对于k=1,2,…,n-1列,若按顺序有
3、某一ark≠0,r≥k,则交换k与r行,然后计算(3―11)2)回代过程对于k=n,n-1,…,2,1,计算(3―12)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二、主元素消去法1.列主元素消去法所谓列主元素消去法就是在每一步消元过程中取系数子矩阵的第一列元素中绝对值最大者作主元。取四位有效数字计算。解:第一列消元时,②中-18为主元,交换②和①得①②③①②③例1用列主元
4、素消去法解方程组②+①×12/18,③+①×1/18得①②③第二列消元时,主元为1.167,交换方程②和③得①②③③+②×1/1.167得①②③回代求得x1=1.000,x2=2.000,x3=3.001方程组的实际解x1=1,x2=2,x3=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计算(3―14)aij-aik
5、·akj/akk⇒aij(2)回代过程。对于k=n,n-1,…,1计算(3―16)图3.1图3.12.全主元素消去法所谓全主元素消去法,就是每步消元时选取系数子矩阵中绝对值最大的元素作主元。说明:若矩阵第i列与第j列对调,则未知数xi与xj也相应地对调了,xi的结果实质上为xj的结果。例2用全主元素消去法求解方程组①②③解:这里主元为-18,交换方程①与方程②得①②③①②③再全选主元,主元为2.333,交换x2和x3所在的两列,同时改变两未知数的排列号得①②③③-②×0.944/2.333得①②③已经化为三角方程组,回
6、代求解x1=1.000,x2=3.000,x3=2.000这里未知数x2与x3已对调,所以应恢复解的顺序,方程组的实际精确解为x1=1.000,x2=2.000,x3=3.000全主元素消去法的计算过程:(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,计算(3―18)
7、(3―19)(3―20)图3.2图3.2§2高斯―约当消去法前面所述的消去法均要进行两个过程,即消元过程和回代过程。但对消元过程稍加改变可以把方程组(3―1)化为对角形(3―21)§3解实三对角线性方程组的追赶法其中|a1|>|c1|>0|ak|≥|bk|+|ck|,bkck≠0,k=2,3,…,n-1|an|>|bn|>0我们将利用所谓“追赶法”解决令令其中当k=n时,因为bnxn-1+anxn=rn又xn-1=un-1-vn-1xn于是追赶追赶§4矩阵的三角分解对于线性方程组,若其系数矩阵A能够分解成两个三角形矩阵
8、相乘,譬如,A=LUL为下三角矩阵,U为上三角矩阵,则求解方程组(3―1)就化为求解LUx=b令Ux=y则Ly=b1.克劳特分解方法设A为n×n阶非奇异矩阵,且各阶主子矩阵为非奇异,则矩阵A的克劳特分解为A=LU其中这样,L、U中的元素都已求出。计算L的各列与U的各行的次序如下图所示。图3.4克劳特分解求解线性方程组的计算过程:①