总结线性方程组的数值解法.pptx

《总结线性方程组的数值解法.pptx》由会员分享，可在线阅读，更多相关《总结线性方程组的数值解法.pptx（60页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第1页/共60页解线性方程组的两类方法解线性方程组的两类方法:直接法直接法:经过有限次运算后可求得方经过有限次运算后可求得方程组程组精确解精确解的方法的方法(不计舍入误差不计舍入误差!)迭代法：迭代法：从解的某个近似值出发，通从解的某个近似值出发，通过构造一个无穷序列去过构造一个无穷序列去逼近精确解逼近精确解的的方法方法(一般有限步内得不到精确解一般有限步内得不到精确解)第2页/共60页1高斯消去法高斯消去法是一个古老的直接法，由它改进的方法是目前计算机上常用的求低阶稠密矩阵方程组的有效方法。思思路路首先将方程组首先将方程组Ax=b 化为上三角方程化为上三角方程组，此过程称为组，此过程称为消去

2、过程消去过程，再求解上，再求解上三角方程组，此过程称为三角方程组，此过程称为回代过程回代过程.第3页/共60页一、顺序消去法解方程组 (36)1高斯消去法第4页/共60页 作-消去中的x1,作-4消去中的x1,则方程组(36)化为 (36)对方程组(36)作-,得到三角形方程组 (36)第5页/共60页 从方程组(36“)的方程解出x3,将所得的结果代入方程求出x2,再把x3、x2同时代入方程解出x1。这样可求出方程组的解为 第6页/共60页2、顺序高斯消去法的计算步骤：在计算机上实现时,我们常把方程组右端的常数项排于系数矩阵的第n+1列，1）消元过程 对于k=1,2,n-1列,若按顺序有某一

3、ark0,rk,则交换k与r行,然后计算 (311)2）回代过程 对于对于k=n,n-1,k=n,n-1,2,1,2,1,计算计算(312)第7页/共60页3、计算量 N=NN=N1 1+N+N2 2=n(n-1)/2n(n-1)/2+n(n-1)(n+1)/3n(n-1)(n+1)/3=n=n3 3/3+n/3+n2 2-n/3-n/3Gauss消去法的运算次数与n3同阶，记为O(n3)克莱姆法则需运算次数为(n2-1)*n!+n第8页/共60页二、主元素消去法1.列主元素消去法所谓列主元素消去法就是在每一步消元过程中取系数子矩阵的第一列元素中绝对值最大者作主元。第9页/共60页取四位有效数

4、字计算。解：第一列消元时，中-18为主元,交换和得 例1 用列主元素消去法解方程组第10页/共60页+12/18,+1/18得 第二列消元时,主元为1.167,交换方程和得 第11页/共60页+1/1.167得 回代求得 x1=1.000,x2=2.000,x3=3.001方程组的实际解 x1=1,x2=2,x3=3第12页/共60页列主元素消去法的计算过程:(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计算(314)aij-aikak

5、j/akkaij(2)(2)回代过程。回代过程。对于对于k=n,n-1k=n,n-1,1 1计算计算(316)第13页/共60页图 3.1 第14页/共60页图 3.1 第15页/共60页2.全主元素消去法 所谓全主元素消去法,就是每步消元时选取系数子矩阵中绝对值最大的元素作主元。说明：若矩阵第i列与第j列对调,则未知数xi与xj也相应地对调了,xi的结果实质上为xj的结果。第16页/共60页例2用全主元素消去法求解方程组 解：这里主元为-18,交换方程与方程得 第17页/共60页再全选主元,主元为2.333,交换x2和x3所在的两列,同时改变两未知数的排列号得 -0.944/2.3330.9

6、44/2.333得得 已经化为三角方程组已经化为三角方程组,回代求解回代求解 x1=1.000,x2=3.000,x3=2.000 x1=1.000,x2=3.000,x3=2.000 这里未知数这里未知数x2x2与与x3x3已对调已对调,所以应恢复解的顺序所以应恢复解的顺序,方程组的实际精确解为方程组的实际精确解为 x1=1.000,x2=2.000,x3=3.000 x1=1.000,x2=2.000,x3=3.000第18页/共60页全主元素消去法的计算过程:(1)消元过程。对k=1,2,n-1进行下列运算:选主元选主元,确定确定r,tr,t使得使得 若若a art rt=0,=0,则则

7、系系数数矩矩阵阵为为奇奇异异的的,停停止止计计算算否否则则进进行下一步。行下一步。交交换换A A中中的的r r、t t两两行行及及t t、k k两两列列,并并记记下下交交换的足码换的足码t t、k k。对对i=k+1,k+2,i=k+1,k+2,n,n,j=k+1,k+2,j=k+1,k+2,n+1,n+1计计算算 (2)(2)回代过程。回代过程。对对k=n,n-1,k=n,n-1,1,1，计算，计算(318)(319)(320)第19页/共60页 图 3.2 第20页/共60页 图 3.2 第21页/共60页2高斯约当消去法前面所述的消去法均要进行两个过程,即消元过程和回代过程。但对消元过程

8、稍加改变可以把方程组(31)化为对角形(321)第22页/共60页3解实三对角线性方程组的追赶法 其中 a1c10 akbk+ck,bkck0,k=2,3,n-1 anbn0 我们将利用所谓“追赶法”解决第23页/共60页令 令 其中 当当k=nk=nk=nk=n时时,因为因为 b b b bn n n nx x x x n-1n-1n-1n-1+a+a+a+an n n nx x x xn n n n=r=r=r=rn n n n又又 x x x x n-1n-1n-1n-1=u=u=u=u n-1n-1n-1n-1-v-v-v-v n-1n-1n-1n-1 x x x xn n n n于是

9、于是追赶追赶第24页/共60页4矩阵的三角分解对于线性方程组，若其系数矩阵A能够分解成两个三角形矩阵相乘,譬如,A=LUL为下三角矩阵,U为上三角矩阵,则求解方程组(31)就化为求解LUx=b 令令 Ux=yUx=y 则则 Ly=bLy=b第25页/共60页1.克劳特分解方法 设A为nn阶非奇异矩阵,且各阶主子矩阵为非奇异,则矩阵A的克劳特分解为 A=LU其中 第26页/共60页 这样,L、U中的元素都已求出。计算L的各列与U的各行的次序如下图所示。图 3.4 第27页/共60页克劳特分解求解线性方程组的计算过程:LU分解过程:对于k=1,2,n依次计算在在L L与与U U的元素算出后就可以设

10、的元素算出后就可以设 Ly=b Ly=b Ux=y Ux=y解方程组解方程组LUx=b,LUx=b,从而求得方程组的解从而求得方程组的解。第28页/共60页 图 3.5 第29页/共60页 图 3.5 第30页/共60页例4用克劳特分解方法求解下列方程组解：令 第31页/共60页 利用矩阵乘法可得到 第32页/共60页 这样原方程组就化为依次求下列两个三角形方程组代入第二个方程组可求得原方程组的解为代入第二个方程组可求得原方程组的解为 第33页/共60页2.杜利特尔分解方法杜利特尔分解方法是令A=LU这里第34页/共60页 例5用杜利特尔分解方法求解下列方程组的解:解：解：利用式利用式(350

11、)(350)、(351)(351)可求得可求得 求得原方程组的解为求得原方程组的解为第35页/共60页5行列式和逆矩阵的计算5.1行列式的计算1.高斯消去法 第36页/共60页2.LU分解法克劳特分解法:detA=detLdetU=detL=l11l22lnn杜利特尔分解法:detA=detLdetU=detU=u11u22unn乔累斯基分解法:这里A为正定矩阵。detA=detLdetLT=l211l222l2nn或者detA=detLdetDdetLT=detD=d1d2dn第37页/共60页5.2逆矩阵的计算 前面介绍的求解线性方程组的方法均可用来计算逆矩阵第38页/共60页 例7 设

12、求求A A-1-1。解解:将方程组写成同一个增广矩阵将方程组写成同一个增广矩阵,即即 第39页/共60页 先对第一列消元,将a11化为1,a21、a31化为0,有再将第二列a32化为0,得 第40页/共60页 将a33化为1,并将a23、a13化为0,得 最后将a13化为0,得 所以 第41页/共60页6迭代法6.1简单迭代法设所给的线性方程组为Ax=b其中系数矩阵A为非奇异,b0。写成等价形式x=G(x)=Mx+fxk+1=Mxk+f改写的方改写的方法很多法很多单步迭代单步迭代法法第42页/共60页例如将A分解为两个矩阵之差A=B-C其中矩阵B可逆,于是方程组成为Ax=Bx-Cx=bBx=C

13、x+bx=B-1Cx+B-1b令M=B-1C,f=B-1b则x（k+1）=Mx（k）+fB B应该便于求逆应该便于求逆,如如B B为单位矩阵为单位矩阵或对角矩阵等或对角矩阵等第43页/共60页雅可比（Jacobi）迭代法取特别当M的对角元素均不为零且按绝对值来说较大时,则 M=B-1 C,f=B-1 b第44页/共60页 例8 用简单迭代法解下列方程组 解：将方程组写成等价形式解：将方程组写成等价形式第45页/共60页 取初始值x(0)=0,按迭代公式 表 31 第46页/共60页 图 3.8 第47页/共60页6.2赛德尔(Seidel)迭代法设方程组的等价形式为x=Mx+f将矩阵M分解为M

14、=B+C，其中第48页/共60页于是x=Bx+Cx+fx(k+1)=Bx(k+1)+Cx(k)+f,k=0,1,2,即：故多步迭代多步迭代法法第49页/共60页 例9 用高斯-赛德尔迭代法解方程组 解 将原方程组写成等价形式并构造高斯-赛德尔迭代公式第50页/共60页 表 32 第51页/共60页7迭代法的收敛性充分条件：设x=Mx+f是原方程组的等价形式,M为迭代矩阵,（1）若,则简单迭代法和赛德尔迭代法都收敛。（2）若,则简单迭代法和赛德尔迭代法都收敛。（3）若系数矩阵A满足，或，则雅可比迭代法收敛。（4）若系数矩阵A正定，则高斯-赛德尔迭代法对于任何初始向量收敛。第52页/共60页 如果

15、迭代矩阵 ，是否收敛呢？第53页/共60页谱半径：设nn阶矩阵A的特征值为i(i=1,2,n),则称为矩阵A的谱半径。第54页/共60页定理5对于任意初始向量x(0)和常数项f,由迭代公式x(k+1)=Mx(k)+f,k=0,1,2,收敛的充要条件是(A)1第55页/共60页例：已知线性方程组AX=b，其中讨论雅可比迭代法及高斯赛德尔迭代法的收敛性。第56页/共60页练习1：证明利用雅可比迭代法发散，而高斯赛德尔迭代法收敛解：雅可比迭代矩阵解：雅可比迭代矩阵A=DA=D-1-1C C高斯高斯-赛德尔迭代矩阵赛德尔迭代矩阵A=(D-L)A=(D-L)-1-1U U第57页/共60页练习：2、用雅可比迭代法，高斯赛德尔迭代法法求解下列线性方程组，并判断其收敛性。保留四位小数，精度为0.001。第58页/共60页练习：3、用列主元素消去法及全主元素消去法求解下列线性方程组，并求系数矩阵行列式值。4 4、利用克劳特分解法与杜利特尔分解法求解、利用克劳特分解法与杜利特尔分解法求解下列线性方程组的解，并求系数行列式值。下列线性方程组的解，并求系数行列式值。第59页/共60页谢谢您的观看！第60页/共60页