《线性代数方程组的直接法》由会员分享，可在线阅读，更多相关《线性代数方程组的直接法（80页珍藏版）》请在金锄头文库上搜索。
1、,2018/9/1,1,王 淑 栋 办公室：J13-409 电话：88032786（H）, 15269283087 E-mail：,数 值 分 析 （Numerical Analysis）,2018/9/1,2,第七章 解线性方程组的直接方法,数 值 分 析 （Numerical Analysis）,AX = b,很多实际问题都可归结为求解线性方程组：,2018/9/1,3,写成矩阵形式：,线性方程组数值解法的分类：,直接法：经过有限步算术运算即可求得方程组精确解的方法（适用于中等规模的n阶线性方程组） Gauss消去法及其变形矩阵的三角分解法,迭代法：用某种极限过程去逐步逼近线性方程组精确解
2、的方法。（适用于高阶线性方程组）Jacobi迭代法 Gauss-Seidel迭代法逐次超松弛法,2018/9/1,4,2018/9/1,5,1 Gauss消去法,或 AX = b,消元手续,2018/9/1,6,举例说明消去法的基本思想：,基本思想：用逐次消去未知数的方法把原来方程组AX = b化为与其等价的三角方程组，然后再用回代法写出方程组的解。事实上，将方程组化为与其等价的三角方程组的过程就是用行的初等变换将原来方程组的系数矩阵化为简单形式，然后再求解。,1消元,基本思想：通过消元手续将上述方程组化为三角形方程组进行求解。,2018/9/1,7,Guass消去法,消元公式,2018/9/
3、1,8,2. 回代,2018/9/1,9,回代公式,2018/9/1,10,Gauss消去法可执行的前提：,【定理 1】 按顺序Gauss消去法所形成的各主元素 的充要条件是 矩阵 的顺序主子式 ，即,2018/9/1,11,【推论】如果 的顺序主子式,2018/9/1,12,【定理 2】如果 的所有顺序主子式都不为零，即 则可通过Gauss消去法将前面的方程组约化为三角方程组。,2018/9/1,13,作业： P197 1，2，7,不进行交换两行 的初等变换！,2018/9/1,14,矩阵的三角分解,借助矩阵理论分析消去法！建立Gauss消去法和矩阵理论间的关系！对于,或 AX = b,在G
4、auss消元法中，,每一步消去过程相当于左乘初等变换矩阵Lk,2018/9/1,15,2018/9/1,16,A 的 LU 分解,其中 单位下三角形。,2018/9/1,17,【定理3】（矩阵的LU分解）设A为n n矩阵，如果 解AX = b用高斯消去法（限制不进行行的交换，即 ）能够完成，则矩阵A可分解为单位下三角矩阵L与上三角矩阵U的乘积，即A = LU 且这种分解是唯一的。,2018/9/1,18,注： （1） L 为单位下三角阵而 U 为一般上三角阵的分解称为Doolittle 分解（2）L 为一般下三角阵而 U 为单位上三角阵的分解称为Crout 分解。,2018/9/1,19,20
5、18/9/1,20,系数矩阵 的三角分解！,21,计算量,（1）消元过程的计算量：第1步计算乘数mi1(i=1,2,n)，需要n-1次除法运算；计算需要 次乘法和 次加、减法。,22,(2) 计算b(n)计算量:进行 次乘法和 加、减法；,(3) 回代过程的计算量:,总计算量：,次乘除法和 次加减法,较大时,乘除法次数：,较大时,加减法次数：,2 Gauss主元素消去法,【例4 】用Gauss消去法解方程组,选主元素的必要性！,要求用具有舍入的10位浮点数进行计算。,精确到10位的精确解为：,【解法1】（高斯消去法）,消元：,舍去或者说被“吃”,舍去或者说被“吃”,计算解：,2018/9/1,
6、23,显然,计算解与精确解解相差太大，原因是用很小的数,作除数，使得舍入误差太大，从而计算结果不可靠。,【解法2 】 用行变换的高斯消去法,消元：,计算解:,该结果较好。该例子说明，在采用高斯消去法解方程组时，应避免采用绝对值很小主元素 。对一般系数矩阵，最好保持乘数 ， 因此在高斯消去法中引进选主元素技巧。,24,1、完全主元素消去法,选主元素消元法：,为非奇异矩阵，,第一步： （1）选主元素：在A中选取绝对值最大的元素作为主元素，即确定 使 （2）交换行列：交换 中第1行和i1行元素，第1列和第j1列元素。注意调换 两未知量，并做记录。交换后 的元素仍记为 。,（3）第1次消元计算：,重复
7、进行上述过程，设已完成第1步至第k-1 步的选主元素、交换行列和消元计算，使,为增广矩阵。,25,第k步： （1）选主元素：选取 使 （2）交换行列：交换 中第k行和ik行元素，第k列和第jk列元素。,（3）消元计算：,2018/9/1,26,回代求解,工作量大。,经过上述过程，方程组约化为：,缺点：,优点：数值稳定,改进方法：,列主元消去法，且此时,其中 是未知数 调换后的顺序，则,完全主元素消去法优缺点：,完全主元素消去法步骤见P172!,27,列主元素法考虑依次按列选主元素，然后换行，再进行消元计算。设已完成第1步第k-1步计算，得到与原方程组等价的方程组 其中,方框内为第k步选主元素区
8、域。,2、列主元素消去法,28,输入矩阵阶数n，增广矩阵 A(n, n+1);,对于,(1) 按列选主元：选取 l ， 使,(2) 如果 ，交换 A(n, n+1) 的第k行与第l 行元素,(3) 消元计算 ：,回代计算,2018/9/1,29,列主元素消去法步骤见P173!,矩阵运算描述列主元素消去法！,30,先换行再消元！,【定理4】（列主元素的三角分解）如果为非奇异矩阵，则存在排列矩阵P，使得PA=LU，其中L是单位下三角阵，U是上三角阵。,【例5】 用列主元素消去法解方程组,我们用4位浮点数进行计算。,解 ：消元：,已知精确解：,2018/9/1,回代计算解：,高斯选主元消去法的步骤：
9、,注：该解若取两位有效数字，则与精确解完全相同。,优点：,数值稳定,修正方法：,消元，回代。,高斯-约当（Gauss-Jordam）消去法。,缺点：,既消元，又回代,2018/9/1,32,3、高斯约当（GaussJordan)消去法,高斯消去法始终是消去对角线下方的元素，GaussJordan消去法要消去对角线下方和上方的元素。假设G-J消去法已完成第1步第k-1步，得到与原方程组等价的方程组 ，其中,第k步计算：,（1）按列选主元：即确定ik，使,（2）换行：交换 的第k行和第ik行元素,（3）消元计算：,33,（4）计算主行（主元素所在行）,计算解：,上述过程结束后，有,2018/9/1
10、,34,说明：在解方程组，一般不用 高斯-约当消去法。因为计算量太大，但是在解多个方程组而它们的系数矩阵相同时，用此方法，即求系数矩阵的逆矩阵A-1 时，比较合适。,设 为非奇异矩阵。如果用列主元G-J消去法将（A, I）化为（I, T），则 。,不用回代，将A化为单位矩阵，则解为常数项列。,【定理5】 （高斯约当法求逆矩阵）,优点：,缺点：计算量较大，大约是 次乘除法。,注：该方法与高等代数中求逆矩阵方法的不同之处是有选主元，,实际上选主元就是交换两行的位置，仍是初等变换，在一般的,求逆矩阵方法中也有交换两行元素。,2018/9/1,35,【例6】 用列主元素G-J消去法求 的逆矩阵A-1,
11、解：,2018/9/1,36,所以,G-J列主元求逆算法见P176算法3！,2018/9/1,37,2018/9/1,38,作业： P199 12,2018/9/1,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 分
12、解求解线性方程组:,2018/9/1,42,直接三角分解法解AX = b的计算公式:,对于r = 2, 3, , n，,(2) 计算U的第r行元素,(3) 计算L的第r 列元素 (r n),(1),2018/9/1,43,(4),(5),2018/9/1,44,【例7】用直接三角分解法解,解：用分解计算公式得：,求解：,2018/9/1,45,2018/9/1,46,选主元的三角分解,选主元素三角分解算法见P179!,2.平方根法(对称正定矩阵而言),矩阵的LDR分解,【定理6】若n阶矩阵A的所有顺序主子式均不等于零， 则矩阵A存在唯一的分解式A =LDR，其中L和R分别是 n阶单位下三角阵和
13、单位上三角阵，D是n阶对角元素 不为零的对角阵，上述分解也称为A的LDR分解。,2018/9/1,47,平方根法,如果A为对称矩阵， 且A的所有顺序主子式均不等于零，则A可唯一分解为A=LDLT，其中L是 n阶单位下三角阵和D是对角阵。,【定理7】（对称矩阵的三角分解定理）,2018/9/1,48,设A是对称 正定矩阵， 做 LU 分解,A 对称,即,则 仍是下三角阵，且有,2018/9/1,49,【定理5】（对称正定矩阵的三角分解或Cholesky分解）,2018/9/1,50,如果A为对称正定矩阵，则存在一个实的非奇异下三 角矩阵，使A=LLT ，且当限定的对角元素为正时， 这种分解是唯一
14、的。,如何确定L呢？,下面用直接法确定L中元素。,2018/9/1,51,其中 ，注意到 所以,因此,用平方根法解线性代数方程组的算法,（1）对矩阵A进行Cholesky分解，即A=LLT，由矩阵乘法：,对于 i = 1, 2, n 计算,2018/9/1,52,（2）求解下三角形方程组,（3）求解LTX = y,2018/9/1,53,改进平方根法,其中,2018/9/1,54,改进平方根法解对称正定方程组的算法,2018/9/1,55,令LTX = y，先解下三角形方程组 LDY = b 得,解上三角形方程组 LTX = Y 得,2018/9/1,56,3. 追赶法,2018/9/1,57
15、,2018/9/1,58,4 向量和矩阵的范数,1向量范数,【定义】设X R n， X 表示定义在Rn上的一个实值函数， 称之为X的范数，它具有下列性质：,（3）三角不等式：即对任意两个向量X, Y R n，恒有,(1) 非负性：即对一切X R n，X 0, X 0,(2) 齐次性：即对任何实数a R，X R n，,2018/9/1,59,由上可得：,设X = (x1, x2, xn)T，则有,（1）,（2）,（3）,三个常用的向量范数：,范数等价: 设s 和t是Rn上任意两种范数，若存在常数 c1，c2 0 使得: , 则称 s 和t 等价。,2018/9/1,60,【定理5】(N(x)的连续性)定义在Rn上的向量范数是X分量 的 连续函数。,推论：Rn上定义的任何两个范数都是等价的。,2018/9/1,61,对常用范数，容易验证下列不等式：,2018/9/1,
