《计算方法教学课件（共八章）第二章线性代数方程组的数值解1》由会员分享，可在线阅读，更多相关《计算方法教学课件（共八章）第二章线性代数方程组的数值解1（110页珍藏版）》请在金锄头文库上搜索。
1、计算方法1第2章 线性代数方程组的数值解2.1 引入2.2 高斯消元法2.3 矩阵的三角分解2.4 消元法在计算机上的实现2.5 向量和矩阵范数2.6 矩阵的条件数与病态方程组2.7 迭代法22.1 引入3PageRankM-网页间的链接矩阵 42.1 引入MPr=Pr(M-I)Pr=0 问题转换为求解一个4阶的线性方程组的问题 解 Pr = 0.26471, 0.23529, 0.20588, 0.29412T52.1 引入62.1 引入 数值天气预报、石油地震数据处理、计算流体力学； 许多其他数学模型的求解往往最后也能转化成线性方程组的求解，如有限元模型的求解、偏微分方程的数值解； 线性方
2、程组的数值解是计算方法最基础，也是最核心的内容之一。72.1 引入线性代数方程组 对于n个变元m个方程所组成的线性代数方程组: 当右端常数项b1=b2=bm=0时，称为n元齐次线性代数方程组，否则称为n元非齐次线性代数方程组。 对于一般的线性代数方程组来说，所谓方程组(1)的一个解就是指由n个数k1，k2，kn组成的一个有序数组( k1，k2，kn )，当x1，x2，xn分别用k1，k2，kn代入后，使(1)中的每个等式都变成恒等式。 方程组(1)的解的全体称为它的解集合。 如果两个方程组有相同的解集合，我们就称它们是同解的。(1)8 n个变元n个方程组成的线性代数方程组9线性代数方程组10线
3、性代数方程组写为矩阵形式简记为 Axb11线性代数方程组求解线性代数方程组的数值方法分类直接法假设计算过程中不产生舍入误差，经过有限次运算可求得方程组的精确解的方法。低阶稠密矩阵方程组分为消元法和三角法迭代法从解的某个近似值出发，通过构造一个无穷序列去逼近精确解的方法。大型稀疏矩阵方程组12预备知识 分别表示n维实和复向量空间，用 表示nn阶实矩阵的向量空间.为实数为复数13转置矩阵单位矩阵其中非奇异矩阵设。如果ABBAI，则称B是A的逆矩阵，记为A-1，且 。如果A-1存在，则称A为非奇异矩阵。如果 均为非奇异矩阵，则14矩阵的行列式 设 ，则A的行列式可按任一行（或列）展开，即 其中Aij
4、 为aij的代数余子式， Aij=(-1)i+j Mij ,Mij为元素aij的余子式。行列式性质(a) det(AB)=det(A)det(B), (b) det(AT)=det(A),(c) det(cA)=cndet(A)(d) 是非奇异矩阵.15设对角矩阵 如果当 时，aij=0对称矩阵 如果 AT=A对称正定矩阵 如果(a) AT=A,(b)对任意非零向量 ，正交矩阵 如果A-1=AT16上三角矩阵及单位上三角矩阵下三角矩阵及单位下三角矩阵17设A是一个mn矩阵，对A施行一次初等行变换，相当于在A的左边乘以相应的m阶初等方阵；对A施行一次初等列变换，相当于在A的右边乘以相应的n阶初等
5、方阵。18(1) 用非零的数乘矩阵的某行（列）；19 逆矩阵： Ti(m) -1= Ti(1/m)(1) 用非零的数乘矩阵的某行（列）；20(2)互换矩阵的某两行（列） ；21 逆矩阵即自身： Tij-1=Tij(2)互换矩阵的某两行（列） ；22(3) 将矩阵的某行（列）的若干倍加到另一行(列)23(3) 将矩阵的某行（列）的若干倍加到另一行(列) 逆矩阵： Tij(m)-1=Tij(-m)24定理 设 ，则下述命题等价：(1)对任何 ,方程组Ax=b有唯一解；(2)齐次方程组Ax=0只有唯一解x=0；(3)(4)A-1存在(5)A的秩rank(A)=n.252.2 Gauss消元法262.
6、2 Gauss消元法消元过程回代过程计算量与存储272.2 Gauss消元法Gauss消元法，又称Gauss消去法，是以德国著名数学家Gauss（1777年4月30日1855年2月23日）命名的求解线性方程组的方法。然而最早记载该方法的却是中国的九章算术。九章算术是中国古代最重要的数学经典，是通过多人之手逐次整理、修改、补充而成的，是集体劳动的结晶。一般认为其成书大概在公元1世纪后半段，比Gauss的出生足足早了1700年！28 Gauss消元法的基本思想用消元法解方程组实际上就是反复地对方程组进行以下三种变换将其化为阶梯形式求解： (1) 用一个非零的数乘某一个方程； (2) 把一个方程的倍
7、数加到另一个方程上； (3) 互换两个方程的位置。 我们称这样的三种变换为方程组的初等变换。 可以证明，初等变换总是把方程组变成同解的方程组。2929问：今有上禾三秉，中禾二秉，下禾一秉，实三十九斗；上禾二秉，中禾三秉，下禾一秉，实三十四斗；上禾一秉，中禾二秉，下禾三秉，实二十六斗。问上、中、下禾实一秉各几何？九章算术的第8卷的第1题30九章算术中对问题给出了详细的解答，其方法步骤与所谓的Gauss消元法完全等价。该问题相当于求解一个三元的线性代数方程组： (2.2.1)31求解这个方程组的第一步是用第二个方程减去第一个方程的2/3倍，用第三个方程减去第一个方程的1/3倍，得到与(2.2.1)
8、等价的方程组，其中第二、三个方程中的x1已经被消去了 (2.2.2) 消元过程32类似地，继续从第三个方程中减去第二个方程的4/5倍，又可消去第三个方程中的变量x2，得到与(2.2.1)同解的方程组回代过程。这个方程很容易求解，从第三个方程可以解出x3 = 11/4，将其代入第二个方程可解出x2 = 17/4，再将x3, x2代入第一个方程解出x1 = 37/4。33 (2.2.3)33342 回代过过程1 消元过程34Gauss 消元法分为两个过程消元过程把原方程组化为阶梯形方程组回代过程求解方程组的解3535Gauss 消元法的消元过程分别表示n维实和复向量空间，用表示nn阶实矩阵空间考虑
9、线性方程组 Ax=b (2.2.4)其中36为实数为复数36其分量形式为记其增广矩阵为37(2.2.5)37Gauss 消元法的消元过程Gauss消元的第一步：假设a110，第1个方程称为主方程，a11称为主元。用a11消去a21, , an1, 为此，将： (第i个方程) (第1个方程) ai1/ a11，i = 2, 3, , n于是我们得到了与(2.2.4)等价的方程组，其增广矩阵为3838Gauss 消元法的消元过程其中，3939Gauss 消元法的消元过程第二步：假设a22(1)0，第2个方程称为主方程，a22(1)称为主元。用a22(1)消去a32(1), , an2(1), 为此
10、，(第i个方程) (第2个方程) ai2(1) / a22(1)，i = 3, 4, , n于是得到等价方程组的增广矩阵为4040Gauss 消元法的消元过程其中，4141Gauss 消元法的消元过程设第k-1步的增广矩阵为：4242Gauss 消元法的消元过程第k步假设akk(k-1)0，第k个方程称为主方程， akk(k-1)称为主元。用akk(k-1)消去ak+1,k(k-1), , ank(k-1), 为此用(第i个方程) (第k个方程) aik(k-1) / akk(k-1) i = k+1, , n于是得到等价方程组的增广矩阵为4343Gauss 消元法的消元过程其中，4444Ga
11、uss 消元法的消元过程如此继续，共做n-1步，便将方程组(2.2.4)的系数矩阵化成易于求解的上三角矩阵形式。这就是Gauss消元法的消元过程。需要注意的是这里假定每步都有aii (i-1)0。因为每步都重复相同形式的运算，所以易于在计算机上实现，算法如下：4545Gauss 消元法的消元过程for k = 1: n-1 for i = k+1: n lik = aik(k-1) / akk(k-1); b i (k) = b i (k-1)- lik b k (k-1); for j = k+1: n aij (k) = aij (k-1)- lik akj(k-1); endfor en
12、dforendfor 这里，aij (0) = aij。4646Gauss 消元法的消元过程Gauss 消元法的回代过程消元过程结束后，我们得到的等价方程组的增广矩阵为4747现在xn可由第n个方程直接求出，代入第n-1个方程可以求得xn-1，如此继续依次求得xn，xn-1，x1，这个过程叫做回代过程。其算法如下：for k = n: 1 xk = (b k (k-1) - akn(k-1) xn - - akk+1(k-1) xk+1) / akk(k-1)endfor这样，我们就得到了方程组的解。4848Gauss 消元法的回代过程思考如何通过变换消元过程，使得不需要回代？4949Gaus
13、s消元法的计算量因为在计算机上作一次乘除法运算所需的时间比一次加减法所需的时间要多很多，所以我们在估算计算量的时候一般只需要考虑乘除法的运算次数。不难看出，回代过程的乘除法次数为5050 在第k步计算A(k)和b(k)时，需要计算(n-k)个lik和(n-k) (n-k+1)个aij(k)和bi(k)。而计算每个元素只需要一次乘除法，因此第k步消元过程需要乘除法的次数为(n-k) (n-k+2)。这样n-1步消元过程总计需要计算乘除法的次数为51消元过程的乘除法次数51 因此，整个Gauss消元法所需的计算量为 SGauss(20)=3060 SCramer(20)= 5.1110195252
14、线性方程组的增广矩阵需要存入计算机中，共需要存储n(n+1)个单元。在用主元a11消去a21, , an1时，这些元素变成了0，无需存储，因此可以将它们存储成相应的数据l21, , ln1。而消元后得到的aij(1) 和bi (1)可以直接存储到原来的aij和bi上，因为后者在后面的消元过程中不再需要。这样，在消元过程结束之后，原来的增广矩阵换成了下面的新数据：53532.3 矩阵的三角分解542.3矩阵的三角分解 2.3.1 矩阵的LU分解2.3.2 杜利特尔分解2.3.3 对称正定矩阵的平方根法和LDLT分解2.3.4 解三对角方程组的追赶法552.3.1矩阵的LU分解56Gauss消元过
15、程的第一步，写成矩阵形式就是其中57Gauss消元过程的矩阵描述57整个消元过程写成矩阵的形式为其中58 (2.3.1)58注意到则有5959 记U = A(n-1), y=b(n-1) 由(2.3.1)式有 (2.3.2)这就是说，消元过程将矩阵A分解为单位下三角矩阵L与上三角矩阵U的乘积： A = LU (2.3.3)同时由方程组 L y = b (2.3.4)解出y。其中，L，U，y分别对应于(2.2.8)式中原矩阵A的下三角部分（L的对角线都为1没有包含）、矩阵A的上三角部分以及原常数向量b部分。6060Gauss消元法的回代过程相当于解系数矩阵为上三角矩阵的方程组 U x = y (
16、2.3.5)6161经过这样的变换之后，原方程组 Ax=b变为 LUx=b则求解方程可以先由 L y = b (2.3.4)解出y。再由 Uxy (2.3.5)解出x.62线性方程组三角解法的步骤62有些实际问题，需要求解若干个具有相同系数矩阵，而右端不同的方程组，即 AX=B对于这样的方程组，只需将A作一次LU分解(2.3.2)，然后针对不同的B解方程组(2.3.3)和(2.3.4)，这样就节省了很多计算量。6363定理2.1（LU分解）设A的前n-1阶顺序主子矩阵非奇异，则存在单位下三角矩阵L及上三角矩阵U，使得A=LU，而且这样的分解是唯一。64若L为单位下三角阵， 则称为Doolittle分解。若U为单位上三角阵， 则称为Crout分解。ALU652.3.2 杜利特尔分解66662.3.2 杜利特尔分解由待定系数法求LU6767682.3.2 杜利特尔分解68692.3.2 杜利特尔分解69702.3.2 杜利特尔分解70 Crout分解：一个单位上三角矩阵和一般下三角矩阵的乘积LDU分解：D = diag(d1, d2, ,dn)是对角矩阵，L和U分别是单位下三角矩阵和单位上
