线性代数方程组的直接法.ppt

《线性代数方程组的直接法.ppt》由会员分享，可在线阅读，更多相关《线性代数方程组的直接法.ppt（80页珍藏版）》请在三一办公上搜索。

1、,2023/9/14,1,王 淑 栋办公室：J13-409电话：88032786（H）E-mail：,数 值 分 析（Numerical Analysis）,2023/9/14,2,第七章 解线性方程组的直接方法,数 值 分 析（Numerical Analysis）,AX=b,很多实际问题都可归结为求解线性方程组：,2023/9/14,3,写成矩阵形式：,线性方程组数值解法的分类：,直接法：经过有限步算术运算即可求得方程组精确解的方法（适用于中等规模的n阶线性方程组）Gauss消去法及其变形 矩阵的三角分解法,迭代法：用某种极限过程去逐步逼近线性方程组精确解的方法。（适用于高阶线性方程组）J

2、acobi迭代法 Gauss-Seidel迭代法 逐次超松弛法,2023/9/14,4,2023/9/14,5,1 Gauss消去法,或 AX=b,消元手续,2023/9/14,6,举例说明消去法的基本思想：,基本思想：用逐次消去未知数的方法把原来方程组AX=b化为与其等价的三角方程组，然后再用回代法写出方程组的解。事实上，将方程组化为与其等价的三角方程组的过程就是用行的初等变换将原来方程组的系数矩阵化为简单形式，然后再求解。,1消元,基本思想：通过消元手续将上述方程组化为三角形方程组进行求解。,2023/9/14,7,Guass消去法,消元公式,2023/9/14,8,2.回代,2023/9

3、/14,9,回代公式,2023/9/14,10,Gauss消去法可执行的前提：,【定理 1】按顺序Gauss消去法所形成的各主元素 的充要条件是 矩阵 的顺序主子式，即,2023/9/14,11,【推论】如果 的顺序主子式,2023/9/14,12,【定理 2】如果 的所有顺序主子式都不为零，即则可通过Gauss消去法将前面的方程组约化为三角方程组。,2023/9/14,13,作业：P197 1，2，7,不进行交换两行 的初等变换！,2023/9/14,14,矩阵的三角分解,借助矩阵理论分析消去法！建立Gauss消去法和矩阵理论间的关系！对于,或 AX=b,在Gauss消元法中，,每一步消去过

4、程相当于左乘初等变换矩阵Lk,2023/9/14,15,2023/9/14,16,A 的 LU 分解,其中 单位下三角形。,2023/9/14,17,【定理3】（矩阵的LU分解）设A为n n矩阵，如果解AX=b用高斯消去法（限制不进行行的交换，即）能够完成，则矩阵A可分解为单位下三角矩阵L与上三角矩阵U的乘积，即 A=LU且这种分解是唯一的。,2023/9/14,18,注：（1）L 为单位下三角阵而 U 为一般上三角阵的分解称为Doolittle 分解（2）L 为一般下三角阵而 U 为单位上三角阵的分解称为Crout 分解。,2023/9/14,19,2023/9/14,20,系数矩阵 的三角

5、分解！,21,计算量,（1）消元过程的计算量：第1步计算乘数mi1(i=1,2,n)，需要n-1次除法运算；计算需要 次乘法和次加、减法。,22,(2)计算b(n)计算量:进行 次乘法和 加、减法；,(3)回代过程的计算量:,总计算量：,次乘除法和 次加减法,较大时,乘除法次数：,较大时,加减法次数：,2 Gauss主元素消去法,【例4】用Gauss消去法解方程组,选主元素的必要性！,要求用具有舍入的10位浮点数进行计算。,精确到10位的精确解为：,【解法1】（高斯消去法）,消元：,舍去或者说被“吃”,舍去或者说被“吃”,计算解：,2023/9/14,23,显然,计算解与精确解解相差太大，原因

6、是用很小的数,作除数，使得舍入误差太大，从而计算结果不可靠。,【解法2】用行变换的高斯消去法,消元：,计算解:,该结果较好。该例子说明，在采用高斯消去法解方程组时，应避免采用绝对值很小主元素。对一般系数矩阵，最好保持乘数，因此在高斯消去法中引进选主元素技巧。,24,1、完全主元素消去法,选主元素消元法：,为非奇异矩阵，,第一步：（1）选主元素：在A中选取绝对值最大的元素作为主元素，即确定 使（2）交换行列：交换 中第1行和i1行元素，第1列和第j1列元素。注意调换 两未知量，并做记录。交换后 的元素仍记为。,（3）第1次消元计算：,重复进行上述过程，设已完成第1步至第k-1 步的选主元素、交换

7、行列和消元计算，使,为增广矩阵。,25,第k步：（1）选主元素：选取 使（2）交换行列：交换 中第k行和ik行元素，第k列和第jk列元素。,（3）消元计算：,2023/9/14,26,回代求解,工作量大。,经过上述过程，方程组约化为：,缺点：,优点：数值稳定,改进方法：,列主元消去法，且此时,其中 是未知数 调换后的顺序，则,完全主元素消去法优缺点：,完全主元素消去法步骤见P172!,27,列主元素法考虑依次按列选主元素，然后换行，再进行消元计算。设已完成第1步第k-1步计算，得到与原方程组等价的方程组 其中,方框内为第k步选主元素区域。,2、列主元素消去法,28,输入矩阵阶数n，增广矩阵 A

8、(n,n+1);,对于,(1)按列选主元：选取 l，使,(2)如果，交换 A(n,n+1)的第k行与第l 行元素,(3)消元计算：,回代计算,2023/9/14,29,列主元素消去法步骤见P173!,矩阵运算描述列主元素消去法！,30,先换行再消元！,【定理4】（列主元素的三角分解）如果为非奇异矩阵，则存在排列矩阵P，使得PA=LU，其中L是单位下三角阵，U是上三角阵。,【例5】用列主元素消去法解方程组,我们用4位浮点数进行计算。,解：消元：,已知精确解：,2023/9/14,回代计算解：,高斯选主元消去法的步骤：,注：该解若取两位有效数字，则与精确解完全相同。,优点：,数值稳定,修正方法：,

9、消元，回代。,高斯-约当（Gauss-Jordam）消去法。,缺点：,既消元，又回代,2023/9/14,32,3、高斯约当（GaussJordan)消去法,高斯消去法始终是消去对角线下方的元素，GaussJordan消去法要消去对角线下方和上方的元素。假设G-J消去法已完成第1步第k-1步，得到与原方程组等价的方程组，其中,第k步计算：,（1）按列选主元：即确定ik，使,（2）换行：交换 的第k行和第ik行元素,（3）消元计算：,33,（4）计算主行（主元素所在行）,计算解：,上述过程结束后，有,2023/9/14,34,说明：在解方程组，一般不用 高斯-约当消去法。因为计算量太大，但是在解

10、多个方程组而它们的系数矩阵相同时，用此方法，即求系数矩阵的逆矩阵A-1 时，比较合适。,设 为非奇异矩阵。如果用列主元G-J消去法将（A,I）化为（I,T），则。,不用回代，将A化为单位矩阵，则解为常数项列。,【定理5】（高斯约当法求逆矩阵）,优点：,缺点：计算量较大，大约是 次乘除法。,注：该方法与高等代数中求逆矩阵方法的不同之处是有选主元，,实际上选主元就是交换两行的位置，仍是初等变换，在一般的,求逆矩阵方法中也有交换两行元素。,2023/9/14,35,【例6】用列主元素G-J消去法求 的逆矩阵A-1,解：,2023/9/14,36,所以,G-J列主元求逆算法见P176算法3！,2023

11、/9/14,37,2023/9/14,38,作业：P199 12,2023/9/14,39,3 Gauss消去法 的变形,直接三角分解法,直接从矩阵A的元素得到计算，U元素的递推公式，而不需要任何中间步骤，称之为直接三角分解法。这样，AX=bL(UX)=b LY=b，UX=Y。不选主元的三角分解(Doolittle分解法),40,通过n步可以直接计算定出L，U的元素，其中第r步确定U的第r行和L的第r列元素。,第1步：,设第r-1步已确定U的第r-1行和L的第r-1列元素。,41,第r步：,故：,故：,LU 分解求解线性方程组:,2023/9/14,42,直接三角分解法解AX=b的计算公式:,

12、对于r=2,3,n，,(2)计算U的第r行元素,(3)计算L的第r 列元素(r n),(1),2023/9/14,43,(4),(5),2023/9/14,44,【例7】用直接三角分解法解,解：用分解计算公式得：,求解：,2023/9/14,45,2023/9/14,46,选主元的三角分解,选主元素三角分解算法见P179!,2.平方根法(对称正定矩阵而言),矩阵的LDR分解,【定理6】若n阶矩阵A的所有顺序主子式均不等于零，则矩阵A存在唯一的分解式A=LDR，其中L和R分别是n阶单位下三角阵和单位上三角阵，D是n阶对角元素不为零的对角阵，上述分解也称为A的LDR分解。,2023/9/14,47

13、,平方根法,如果A为对称矩阵，且A的所有顺序主子式均不等于零，则A可唯一分解为A=LDLT，其中L是n阶单位下三角阵和D是对角阵。,【定理7】（对称矩阵的三角分解定理）,2023/9/14,48,设A是对称 正定矩阵，做 LU 分解,A 对称,即,则 仍是下三角阵，且有,2023/9/14,49,【定理5】（对称正定矩阵的三角分解或Cholesky分解）,2023/9/14,50,如果A为对称正定矩阵，则存在一个实的非奇异下三角矩阵，使A=LLT，且当限定的对角元素为正时，这种分解是唯一的。,如何确定L呢？,下面用直接法确定L中元素。,2023/9/14,51,其中，注意到 所以,因此,用平方

14、根法解线性代数方程组的算法,（1）对矩阵A进行Cholesky分解，即A=LLT，由矩阵乘法：,对于 i=1,2,n 计算,2023/9/14,52,（2）求解下三角形方程组,（3）求解LTX=y,2023/9/14,53,改进平方根法,其中,2023/9/14,54,改进平方根法解对称正定方程组的算法,2023/9/14,55,令LTX=y，先解下三角形方程组 LDY=b 得,解上三角形方程组 LTX=Y 得,2023/9/14,56,3.追赶法,2023/9/14,57,2023/9/14,58,4 向量和矩阵的范数,1向量范数,【定义】设X R n，X 表示定义在Rn上的一个实值函数，称

15、之为X的范数，它具有下列性质：,（3）三角不等式：即对任意两个向量X,Y R n，恒有,(1)非负性：即对一切X R n，X 0,X 0,(2)齐次性：即对任何实数a R，X R n，,2023/9/14,59,由上可得：,设X=(x1,x2,xn)T，则有,（1）,（2）,（3）,三个常用的向量范数：,范数等价:设s 和t是Rn上任意两种范数，若存在 常数 c1，c2 0 使得:,则称 s 和t 等价。,2023/9/14,60,【定理5】(N(x)的连续性)定义在Rn上的向量范数 是X分量 的 连续函数。,推论：Rn上定义的任何两个范数都是等价的。,2023/9/14,61,对常用范数，容

16、易验证下列不等式：,2023/9/14,62,【定义2】设 为Rn中一向量序列，即,其中,若对任何i(i=1,2,n)都有,则向量,称为向量序列 的极限，或者说向量序列依坐标收敛于向量，记为,2023/9/14,63,【定理7.13】向量序列 依坐标收敛于X*的充要条件是,向量序列依范数收敛与依坐标收敛是等价的。,【定义3】设A为n 阶方阵，Rn中已定义了向量范数，则称 为矩阵A的范数或模，记为。即,2023/9/14,64,（1）当A=0时，0，当A 0时，0,（2）对任意实数k 和任意A，有,（3）对任意两个n阶矩阵A，B有,（4）对任意两个n阶矩阵A，B，有,2023/9/14,65,2

17、矩阵的范数,【定义3】（矩阵范数）如果矩阵的 某个非负的实值函数 满足条件：,则称 是 上的一个矩阵范数(模)。,2023/9/14,66,矩阵和向量相容的范数：其中,满足矩阵范数的定义，称为A的Frobenius范数。,【例5】,设A(aij)M。定义,证明：这样定义的非负实数不是相容的矩阵范数.,证明：设,从而,2023/9/14,67,【定理8】设n 阶方阵A=(aij)nn，则,（）与 相容的矩阵范数是,（）与 相容的矩阵范数是,其中1为矩阵ATA的最大特征值。,（）与 相容的矩阵范数是,上述三种范数分别称为矩阵的1-范数，2-范数和-范数。,2023/9/14,68,可以证明,对方阵

18、 和，有,2023/9/14,69,3矩阵范数与特征值之间的关系,【定理9】矩阵A 的任一特征值的绝对值不超过A的范数，即,【定义4】矩阵A 的诸特征值 的最大绝对值称为A的谱半径，,记为：,并且如果A为对称矩阵，则,2023/9/14,70,注:Rnn中的任意两个矩阵范数也是等价的。,【定义5】设|为Rnn上的矩阵范数，A,BRnn,称|A-B|为A与B之间的距离。,【定义6】设给定Rnn中的矩阵序列，若,则称矩阵序列 收敛于矩阵A，记为,2023/9/14,71,【定理10】设BRnn，则由B的各幂次得到的矩阵序列Bk,k=0,1,2)收敛于零矩阵的充要条件为。,2023/9/14,72,

19、求解 时，A 和 的误差对解 有何影响？,设 A 精确，有误差，得到的解为，即,绝对误差放大因子,又,相对误差放大因子,5 误差分析,2023/9/14,73,设 精确，A有误差，得到的解为，即,Wait a minute Who said that(I+A1 A)is invertible?,(只要 A充分小，使得,大,2023/9/14,74,【定义7】设A为n 阶非奇异矩阵，称数 为矩阵A的条件数。,条件数的性质：,）cond(A)1,）cond(kA)=cond(A),k 为非零常数,）若，则,2023/9/14,75,常用条件数有：,cond(A)2,特别地，若 A 对称，则,202

20、3/9/14,76,【例】Hilbert 阵,cond(H2)=,27,cond(H3),748,cond(H6)=,2.9 106,cond(Hn)当 n,注：现在用Matlab数学软件可以很方便求矩阵的状态数!,【定义2】设线性方程组的系数矩阵是非奇异的，如果cond(A)越大，就称这个方程组越病态。反之，cond(A)越小，就称这个方程组越良态。,2023/9/14,77,一般判断矩阵是否病态，并不计算A1，而由经验得出。行列式很大或很小（如某些行、列近似相关）；元素间相差大数量级，且无规则；主元消去过程中出现小主元；特征值相差大数量级。,2023/9/14,78,近似解的误差估计及改善：,设 的近似解为，则一般有,cond(A),改善方法(1)：,Step 1:近似解,Step 2:,Step 3:,Step 4:,若 可被精确解出，则有 就是精确解了。,经验表明：若 A 不是非常病态（例如：），则如此迭代可达到机器精度；但若 A 病态，则此算法也不能改进。,2023/9/14,79,改善方法(2),对方程组进行预处理，即适当选择非奇异对角阵D，C,使求解 Ax=b 的问题转化为求解等价方程组 DACC-1x=Db,且使DAC 的条件数得到改善。（P88，例3.10）,用双精度进行计算，以便改善和减轻病态矩阵的影响。,2023/9/14,80,