第2章 线性方程组的直接法.ppt

《第2章 线性方程组的直接法.ppt》由会员分享，可在线阅读，更多相关《第2章 线性方程组的直接法.ppt（54页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第二章第二章 解线性方程组的直接方法解线性方程组的直接方法 高斯高斯(Gauss)(Gauss)消元法消元法 矩阵的三角分解法矩阵的三角分解法 矩阵的条件数与方程组的性态矩阵的条件数与方程组的性态解线性方程组的两类方法解线性方程组的两类方法:直接法直接法:经过有限次运算后可求得方程组精确解的方经过有限次运算后可求得方程组精确解的方法法(不计舍入误差不计舍入误差!)!)迭代法：从解的某个近似值出发，通过构造一个无穷迭代法：从解的某个近似值出发，通过构造一个无穷序列去逼近精确解的方法序列去逼近精确解的方法(一般有限步内得不到精确解一般有限步内得不到精确解)一、一、高斯消去法高斯消去法思思路路首先将

2、方程组首先将方程组Ax=b 化为上三角方程组化为上三角方程组，此过程称为此过程称为消去过程消去过程，再求解上三角方程，再求解上三角方程组，此过程称为组，此过程称为回代过程回代过程.2.1 高斯消去法和选主元高斯消去法高斯消去法和选主元高斯消去法将增广矩阵将增广矩阵的的第第 i 行行 +li1 第第1 1行行，得到：，得到：消去过程：消去过程：第一步第一步：设设 ，计算因子，计算因子其中其中第第k步：步：设设 ，计算因子，计算因子且计算且计算共进行共进行 n 1步，得到步，得到定理定理2.1：若若A的所有的所有顺序主子式顺序主子式 均不为均不为0，则高斯，则高斯消去法能顺序进行消元，得到唯一解。

3、消去法能顺序进行消元，得到唯一解。回代过程：回代过程：例例2.1.1 高斯消元法高斯消元法x1=-13x2=8x3=2二、二、选主元消去法选主元消去法为为避免这种情况的发生避免这种情况的发生,可通过交换方程的次序，选可通过交换方程的次序，选取绝对值大的元素作主元取绝对值大的元素作主元.基于这种思想导出了主元基于这种思想导出了主元素法素法在在高斯消去法消去过程中可能出现高斯消去法消去过程中可能出现 的情况，的情况，这时高斯消去法将无法进行；即使主元素这时高斯消去法将无法进行；即使主元素 但很小，其作除数但很小，其作除数，也会导致其它元素数量级的严，也会导致其它元素数量级的严重增长和舍入误差的扩散

4、重增长和舍入误差的扩散v 列主元消去法列主元消去法在第在第k步消元前，在系数矩阵第步消元前，在系数矩阵第k列的对角线以下列的对角线以下的元素中找出绝对值最大的元。的元素中找出绝对值最大的元。若若pk,交换第交换第k个与第个与第p个方程后个方程后,再继续消去计算再继续消去计算.这种方法称为这种方法称为列主元列主元GaussGauss消去法消去法。列主元列主元GaussGauss消去法保证了消去法保证了lik1 1(i=k+1,k+2,，n).).例例2.1.2 列主元法列主元法第一列中绝对值最大是第一列中绝对值最大是10，取，取10为主元为主元n阶方程组第阶方程组第k 轮消元时，选第轮消元时，选

5、第k 列的后列的后(n k+1)个个元素中绝对值最大作主元。元素中绝对值最大作主元。x3=6.2/6.2=1x2=(2.5-5x3)/2.5=-1x1=(7+7x2-0 x3)/10=0 x1=0 x2=-1x3=1第二列的后两个数中选出主元第二列的后两个数中选出主元 2.5v 全主元消去法全主元消去法在第在第k 步消去前，步消去前，在系数矩阵右下角的在系数矩阵右下角的n-k+1阶阶主子阵中，主子阵中，选绝对值最大的元素作为主元素选绝对值最大的元素作为主元素。(1)If p k then 交换第交换第 k 行与第行与第p 行行;If q k then 交换第交换第 k 列与第列与第 q 列列;

6、(2)消元消元注注注注：列交换改变了列交换改变了xi 的顺序，须记录的顺序，须记录交换次序交换次序，解完后再换回来。解完后再换回来。例例2.1.3 全主元解方程组全主元解方程组:运算量运算量（Amount of Computation）（1 1）用克莱姆用克莱姆（CramerCramer）法则求解法则求解n n阶线性方程组阶线性方程组每个行列式由每个行列式由n!项相加项相加,而每项包含了而每项包含了n个因子相乘个因子相乘,乘法运算次数为乘法运算次数为(n-1)n!次次.仅考虑乘仅考虑乘(除除)法运算法运算,计算解向量包括计算计算解向量包括计算n+1个个行列式和行列式和n次除法运算次除法运算,乘

7、乘(除除)法运算次数法运算次数N=(n+1)(n-1)n!+n.（2）高斯消去法高斯消去法:在第在第1个消去步个消去步,计算计算 li1(i=2,3,n),有有n-1次除法运算次除法运算.使使aij(1)变为变为 aij(2)以及使以及使bi(1)变为变为bi(2)有有n(n-1)次乘法运算次乘法运算和和 n(n-1)次加次加(减减)法运算法运算.在第在第k个消去步个消去步,有有n-k次除法运算次除法运算,(n-k+1)(n-k)次乘次乘法运算和相同的加法运算和相同的加(减减)法运算法运算.首先统计乘法运算总次数首先统计乘法运算总次数.将每个消去步的乘法运算将每个消去步的乘法运算次数相加次数相

8、加,有有 n(n-1)+(n-1)(n-2)+32+21=n(n-1)(n+1)/3加加(减减)法运算次数总计也为法运算次数总计也为n(n-1)(n+1)/3.除法运算总次数为除法运算总次数为n+(n-1)+1=n(n-1)/2回代过程的计算回代过程的计算除法运算次数为除法运算次数为n次次.乘法运算和加法运算的总次数乘法运算和加法运算的总次数都为都为n+(n-1)+1=n(n-1)/2次次 Gauss Gauss消去法消去法(顺序消去法顺序消去法)除法运算次数为除法运算次数为:n(n-1)/2+n=n(n+1)/2，乘法运算次数为乘法运算次数为:n(n-1)(n+1)/3+n(n-1)/2=n

9、(n-1)(2n+5)/6，加加(减减)法运算次数为法运算次数为:n(n-1)(2n+5)/6通常也说通常也说Gauss消去法的运算次数与消去法的运算次数与n3同阶同阶,记为记为O(n3)u全主远消去法全主远消去法:比比 高斯消去法多出高斯消去法多出 ,保证稳定保证稳定,但费时但费时.u 列主元消去法列主元消去法:比比 高斯消去法只多出高斯消去法只多出 的的 ,略省时略省时.2.22.2 三角分解法三角分解法 高斯消元法的矩阵形式：高斯消元法的矩阵形式：L U 分解分解 每一步消去过程相当于左乘初等变换矩阵每一步消去过程相当于左乘初等变换矩阵L1A 的的 LU 分解分解(LU factoriz

10、ation)定理定理2.2.1：若若A的所有顺序主子式的所有顺序主子式 均不为均不为0，则，则 A 的的 LU 分解唯一（其中分解唯一（其中 L 为为单位单位下三角阵）。下三角阵）。证明：证明：由由1中定理可知，中定理可知，LU 分解存在。下面证明唯一性。分解存在。下面证明唯一性。若不唯一，则可设若不唯一，则可设 A=L1U1=L2U2，推出推出上三角矩阵上三角矩阵对角线上为对角线上为1 1的的下三角矩阵下三角矩阵注注注注：（1 1）L 为单位下三角阵而为单位下三角阵而 U 为为一般一般上三角阵的分解上三角阵的分解称为称为Doolittle 分解分解（2）L 为一般下三角阵而为一般下三角阵而

11、U 为为单位单位上三角阵的分解称为上三角阵的分解称为Crout 分解分解。Doolittle分解法分解法 ：利用矩阵乘法，通过比较直接导出利用矩阵乘法，通过比较直接导出L 和和 U 的计算公式。的计算公式。思思路路一般计算公式L第一行乘第一行乘U 每一列：每一列：a11=u11,a1n=u1nL每一行乘每一行乘U 第一列：第一列：a21=l 21u11,an1=ln1u11l 21u12+u22=a22,l21u1n+u2n=a2n l31u12+l32u22=a32,ln1u12+ln2u22=an2L第二行乘第二行乘U 每一列：每一列：L每一行乘每一行乘U 第二列：第二列：注：注：该公式的

12、特点：该公式的特点：U 的元素按行求的元素按行求,L 的元素按列求的元素按列求;先求先求 U 的第的第k 行行,再求再求 L 的第的第k 列列,U 和和 L 一行一列交叉计算一行一列交叉计算.计算计算量与量与 Gauss 消去法同消去法同.u22=a22-l21u12,u2n=a2n-l21u1n l32=(a32-l31u12)/u22,ln2=(an2-ln1u12)/u22一般地：一般地：LU 分解求解线性方程组例例2.2.1 求矩阵的求矩阵的Doolittle分解分解 旧元素减去左边行与顶上列向量的点积旧元素减去左边行与顶上列向量的点积 计算行不用除法计算行不用除法 计算列要除主对角元

13、计算列要除主对角元注：注：求解正定方程组的求解正定方程组的Cholesky方法方法(平方根法平方根法)回顾：回顾：对称正定阵对称正定阵A的几个重要性质的几个重要性质（1）A 1 亦对称正定，且亦对称正定，且 aii 0（2）A 的顺序主子阵的顺序主子阵 Ak 亦对称正定亦对称正定（3）A 的特征值的特征值 i 0（4）A 的全部顺序主子式的全部顺序主子式 det(Ak)0定理定理2.2.2:设矩阵设矩阵A对称正定，则存在唯一的对角对称正定，则存在唯一的对角元全为正的下三角阵元全为正的下三角阵G 使得使得 AGGT计算格式为计算格式为:平方根法的优点：平方根法的优点：(1)乘除法运算量比一般乘除

14、法运算量比一般 LU分解要小得多；分解要小得多；(2)不选主元的平方根法是数值稳定的。不选主元的平方根法是数值稳定的。(3)缺点：缺点：有有n 个开方运算。个开方运算。为避免过多的开方运算，在更多情况下是将A分解为：A=LDLT，其中L为下三角，D为对角阵。事实上，由前面的讨论可知：A=LU，其中L 为单位下三角阵，U为上三角阵。记U的元素为uij，D=diag(uii)，由于A对称正定，必有uii0(i=1,2,n)，所以U=DU*，其中注：注：将矩阵将矩阵 A 作作Doolittle分解或分解或Crout分解分解,由矩阵乘由矩阵乘法可得法可得 A 的的 LDLT 分解。分解。解三对角方程组

15、的解三对角方程组的追赶法追赶法定理定理2.2.3：若若 A 为为对角占优对角占优 的三对角阵，且满足的三对角阵，且满足 则方程组有唯一的则方程组有唯一的LU分解。分解。第一步第一步:对对 A 作作Doolittle 分解分解追赶法公式的推导：追赶法公式的推导：（以四阶为例）以四阶为例）该过程称为该过程称为“追追”的过程。的过程。该过程称为该过程称为“赶赶”的过程。的过程。一般情形的三对角方程组计算公式：一般情形的三对角方程组计算公式：计算次序为：计算次序为：最最好好牢牢记记直接比较等式两边的元素，可得到计算公式：直接比较等式两边的元素，可得到计算公式：第一步第一步:对对 A 作作Crout 分

16、解：分解：注注:也可通过对也可通过对 A 作作Crout 分解进行求解分解进行求解第二步第二步:追追即解：即解：第三步第三步:赶赶即解：即解：2.3 矩阵的条件数与方程组的性态矩阵的条件数与方程组的性态预备知识预备知识范数范数 向量范数向量范数 (vector norms)对任意对任意定义定义1：Rn空间的空间的向量范数向量范数|,对任意对任意 满足下列条件满足下列条件常用向量范数：常用向量范数：向量向量 的的Lp范数定义为范数定义为:主要主要性质性质性质性质1:1:-x=x性质性质2 2:x-yx-y性质性质3 3:向量范数向量范数x是是Rn上向量上向量x的连续函数的连续函数.范数等价范数等

17、价:设设A 和和B是是R上任意两种范数，若存在上任意两种范数，若存在 常数常数 C1、C2 0 0 使得使得 ,则称则称 A 和和B 等价等价。定理定理1 Rn 上上一切范数一切范数都等价都等价。向量向量 x 的的1范数范数 向量向量 x 的的2范数范数 向量向量 x 的的范数范数 矩阵范数矩阵范数 (matrix norms)定义定义3:3:对任意对任意 ,称称|为为Rm n空间的空间的矩阵矩阵范数范数,指指|满足满足(1)-(3)(1)-(3)：对任意对任意(4)|AB|A|B|若还满足若还满足(4),(4),称为相容的矩阵范数称为相容的矩阵范数相容性相容性（1 1）矩阵）矩阵范数范数与与

18、矩阵矩阵范数范数的相容性的相容性:ABAB ABAB（2 2）矩阵范数与）矩阵范数与向量向量范数相容性范数相容性设设AM，AM 是矩阵范数是矩阵范数,xR n，xv 是向量是向量范数范数.如果满足不等式如果满足不等式:Axv AM xv则称矩阵范数则称矩阵范数AM 与向量范数与向量范数xv 相容相容.常用的算子范数常用的算子范数：由向量范数由向量范数|p 导出关于矩阵导出关于矩阵 A Rn n 的的p范数范数:则则（行和范数行和范数）（列和范数列和范数）（谱范数谱范数 (spectral norm)）(operator norm),又称为从属的矩阵范数又称为从属的矩阵范数:算子算子范数范数注：

19、注：称为称为A的谱半径。的谱半径。定理定理2对任意算子范数对任意算子范数|有有:证明：证明：由算子范数的相容性，得到由算子范数的相容性，得到将任意一个特征根将任意一个特征根 所对应的特征向量所对应的特征向量 代入代入命题命题若若A A对称，则有对称，则有:证明：证明：若若 是是 A 的一个特征根，则的一个特征根，则 2 必是必是 A2 的特征根。的特征根。又：对称矩阵的特征根为实数，即又：对称矩阵的特征根为实数，即 2(A)为非负实数，为非负实数，故得证。故得证。对某个对某个 A 的特征根的特征根 成立成立定理定理3若矩阵若矩阵 A 对某个算子范数满足对某个算子范数满足|A|1，则必有则必有.

20、可逆；可逆；.证明证明:若不然，则若不然，则 有非零解，即存在非零向量有非零解，即存在非零向量 使得使得 病态方程组病态方程组线性方程组的性态（误差分析）线性方程组的性态（误差分析）(Error Analysis for Linear system of Equations)例：方程组例：方程组有精确解有精确解(1,1),(1,1),对系数矩阵和右端常熟项作微小变化对系数矩阵和右端常熟项作微小变化,则则的解为的解为(10,-2).扰动后方程组的解面目全非。扰动后方程组的解面目全非。Def:如果方程组如果方程组 Ax=b 中中,矩阵矩阵A和右端项和右端项 b 的变化的变化|A|和和|b|微小微小

21、,引起解向量引起解向量 x 的变化的变化|x|很大很大,则称则称A为关于解为关于解方程组和矩阵求逆的病态矩阵方程组和矩阵求逆的病态矩阵,称相应的方程组为病态方程组称相应的方程组为病态方程组.反之反之,如果如果|A|和和|b|微小微小,|x|也微小也微小,则称则称 A为良态矩为良态矩阵阵,Ax=b 为良态方程组为良态方程组.思考思考:求解求解 时时,A 和和 的误差对解的误差对解 有何影响有何影响？设设 A 精确，精确，有误差有误差 ，得到的解为，得到的解为 ，即，即绝对误差放大因子绝对误差放大因子又又相对误差放大因子相对误差放大因子矩阵和方程组病态程度的刻划矩阵和方程组病态程度的刻划 设设 精

22、确，精确，A有误差有误差 ，得到的解为，得到的解为 ，即，即(只要只要 A充分小，使得充分小，使得 是关键是关键的误差放大因子，称为的误差放大因子，称为A的状态数的状态数(条件数条件数)，记为记为cond(A),注注:cond(cond(A)与与 所取的范数有关所取的范数有关常用条件数有：常用条件数有：cond 2(A)特别地，若特别地，若 A 对称，则对称，则cond 1(A)=A1 1cond (A)=A 3.4.2 矩阵的条件数矩阵的条件数Def：设设 存在，则称数存在，则称数 cond(A)=|A|为矩阵为矩阵 A 的的条件数，其中条件数，其中 是矩阵的算子范数。是矩阵的算子范数。1-

23、1-条件数条件数-条件数条件数2-2-条件数条件数例：例：Hilbert 阵阵cond(H2)=27cond(H3)748cond(H6)=2.9 106注：注：现在用现在用MatlabMatlab数学软件可以很方便求矩阵的条件数数学软件可以很方便求矩阵的条件数!说明说明:设线性方程组的系数矩阵是非奇异的设线性方程组的系数矩阵是非奇异的,如果如果cond(A)越越大大,就称这个方程组越病态就称这个方程组越病态.反之反之,cond(A)越小越小,就称这个方就称这个方程组越良态程组越良态.若若 A 对称正定，则对称正定，则其中其中 分别为分别为A的按模最大和最小的特征值的按模最大和最小的特征值。例例1：求矩阵：求矩阵 的条件数的条件数例例2:2:设设求求