《现代数值分析课件第2章线性方程组的直接法》由会员分享，可在线阅读，更多相关《现代数值分析课件第2章线性方程组的直接法（54页珍藏版）》请在金锄头文库上搜索。
1、第二章 解线性方程组的直接方法,高斯(Gauss)消元法 矩阵的三角分解法 矩阵的条件数与方程组的性态,解线性方程组的两类方法: 直接法: 经过有限次运算后可求得方程组精确解的方法(不计舍入误差!) 迭代法：从解的某个近似值出发，通过构造一个无穷序列去逼近精确解的方法(一般有限步内得不到精确解),一、高斯消去法,2.1 高斯消去法和选主元高斯消去法,将增广矩阵的第 i 行 + li1 第1行，得到：,消去过程：,第一步：设 ，计算因子,第k步：设 ，计算因子 且计算,共进行 n 1步，得到,定理2.1：若A的所有顺序主子式 均不为0，则高斯消去法能顺序进行消元，得到唯一解。,回代过程：,例2.
2、1.1 高斯消元法,x1 = -13 x2 = 8 x3 = 2,二、选主元消去法,为避免这种情况的发生, 可通过交换方程的次序，选取绝对值大的元素作主元. 基于这种思想导出了主元素法,在高斯消去法消去过程中可能出现 的情况， 这时高斯消去法将无法进行；即使主元素 但很小，其作除数 ，也会导致其它元素数量级的严 重增长和舍入误差的扩散,列主元消去法,在第k步消元前，在系数矩阵第k列的对角线以下的元素中找出绝对值最大的元。,列主元Gauss消去法保证了lik1 ( i = k +1, k +2,，n ).,例2.1.2 列主元法,第一列中绝对值最大是10，取10为主元,n阶方程组第k 轮消元时，
3、选第k 列的后( n k + 1 )个元素中绝对值最大作主元。,x3=6.2/6.2=1,x2=(2.5-5x3)/2.5= -1,x1=(7+7x2-0x3)/10=0,x1=0 x2= -1 x3=1,第二列的后两个数中选出主元 2.5,全主元消去法,在第k 步消去前， 在系数矩阵右下角的n- k+1阶主子阵中，选绝对值最大的元素作为主元素。,(1) If p k then 交换第 k 行与第p 行; If q k then 交换第 k 列与第 q 列;,(2) 消元,注：列交换改变了xi 的顺序，须记录交换次序，解完后再换回来。,例2.1.3 全主元解方程组:, 运算量 （Amount
4、of Computation）,（1）用克莱姆（Cramer）法则求解n阶线性方程组,每个行列式由n!项相加, 而每项包含了n个因子相乘,乘法运算次数为(n-1) n!次.,仅考虑乘(除)法运算, 计算解向量包括计算n+1个行列式和n次除法运算, 乘(除)法运算次数 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)次乘法运算
5、和相同的加(减)法运算.,首先统计乘法运算总次数. 将每个消去步的乘法运算次数相加,有 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消去法(顺序消去法) 除法运算次数为: n(n-1)/2+n= n(n+1)/2， 乘法运算次数为: n(n-1)(n+1)/3+n(n-1)/2= n(n-1)(2n+5)/6， 加(减)法运算次数为
6、: n(n-1)(2n+5)/6,通常也说Gauss消去法的运算次数与n3同阶,记为O(n3),全主远消去法:,比 高斯消去法多出 , 保证稳定, 但费时.,列主元消去法:,比 高斯消去法只多出 的 , 略省时.,2.2 三角分解法, 高斯消元法的矩阵形式：L U 分解,每一步消去过程相当于左乘初等变换矩阵L1,A 的 LU 分解 ( LU factorization ),定理2.2.1： 若A的所有顺序主子式 均不为0，则 A 的 LU 分解唯一（其中 L 为单位下三角阵）。,证明：由1中定理可知，LU 分解存在。下面证明唯一性。,若不唯一，则可设 A = L1U1 = L2U2 ，推出,上
7、三角矩阵,对角线上为1的下三角矩阵,注： （1） L 为单位下三角阵而 U 为一般上三角阵的分解称为Doolittle 分解 （2）L 为一般下三角阵而 U 为单位上三角阵的分解称为Crout 分解。, Doolittle分解法 ：,一般计算公式,L第一行乘U 每一列： a11= u11, , a1n= u1n,L每一行乘U 第一列： a21 = l 21u11, , an1 = ln1u11,l 21u12+ u22=a22, , l21u1n+ u2n=a2n,l31u12+ l32u22=a32, , ln1u12+ ln2u22=an2,L第二行乘U 每一列：,L每一行乘U 第二列：,
8、注：该公式的特点：U 的元素按行求, L 的元素按列求; 先求 U 的第k 行, 再求 L 的第k 列, U 和 L 一行一列交叉计算. 计算量与 Gauss 消去法同.,一般地：,LU 分解求解线性方程组,例2.2.1 求矩阵的Doolittle分解, 求解正定方程组的Cholesky方法(平方根法),回顾：对称正定阵A的几个重要性质 （1）A1 亦对称正定，且 aii 0 （2）A 的顺序主子阵 Ak 亦对称正定 （3）A 的特征值 i 0 （4）A 的全部顺序主子式 det ( Ak ) 0,定理2.2.2: 设矩阵A对称正定，则存在唯一的对角元全为正的下三角阵G 使得 AGGT,计算格
9、式为:,平方根法的优点： (1) 乘除法运算量比一般 LU分解要小得多； 不选主元的平方根法是数值稳定的。 缺点：有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 分解。, 解三对角方程组的追赶法,定理2.2.3：若 A 为对角占优 的三对角阵，且
10、满足 则方程组有唯一的LU分解。,第一步 : 对 A 作Doolittle 分解,追赶法公式的推导：（以四阶为例）,该过程称为“追”的过程。,该过程称为“赶”的过程。,一般情形的三对角方程组计算公式：,计算次序为：,最 好 牢记,直接比较等式两边的元素，可得到计算公式：,第一步: 对 A 作Crout 分解：,注: 也可通过对 A 作Crout 分解进行求解,第二步: 追即解：,第三步: 赶即解：, 2.3 矩阵的条件数与方程组的性态,预备知识范数, 向量范数 ( vector norms ),对任意,定义1：Rn空间的向量范数 | | ,对任意 满足下列条件,常用向量范数：, 向量 的Lp范
11、数定义为:,主要性质,性质1:-x=x,性质2:x-yx-y,性质3: 向量范数x是Rn上向量x的连续函数.,范数等价:设A 和B是R上任意两种范数，若存在 常数 C1、C2 0 使得 ,则称 A 和B 等价。,定理1,Rn 上一切范数都等价。,向量 x 的1范数 向量 x 的2范数 向量 x 的范数, 矩阵范数 ( matrix norms ),定义3:对任意 ,称| | 为Rmn空间的矩阵范数, 指| |满足(1)-(3)：,对任意,(4) | AB | | A | | B |,若还满足(4),称为相容的矩阵范数,相容性,（1）矩阵范数与矩阵范数的相容性: ABAB,（2）矩阵范数与向量范
12、数相容性,常用的算子范数：,由向量范数 | |p 导出关于矩阵 A Rnn 的p范数:,则,注： 称为A的谱半径。,证明：,由算子范数的相容性，得到,将任意一个特征根 所对应的特征向量 代入,命题,若A对称，则有:,证明：,若 是 A 的一个特征根，则2 必是 A2 的特征根。,又：对称矩阵的特征根为实数，即 2(A) 为非负实数，故得证。,对某个 A 的特征根 成立,定理3,若矩阵 A 对某个算子范数满足 |A| 1，则必有,.,可逆；,.,证明:, 若不然，则 有非零解，即存在非零向量 使得, 病态方程组线性方程组的性态（误差分析） ( Error Analysis for Linear
13、system of Equations ),例：方程组,有精确解(1,1),对系数矩阵和右端常熟项作微小变化,则,的解为(10, -2). 扰动后方程组的解面目全非。 Def :如果方程组 Ax = b 中, 矩阵A和右端项 b 的变化|A|和 |b |微小, 引起解向量 x 的变化|x |很大, 则称A为关于解 方程组和矩阵求逆的病态矩阵, 称相应的方程组为病态方程组. 反之, 如果|A|和|b |微小, |x |也微小, 则称 A为良态矩 阵, Ax=b 为良态方程组.,思考:求解 时, A 和 的误差对解 有何影响？, 设 A 精确， 有误差 ，得到的解为 ，即,绝对误差放大因子,又,相
14、对误差放大因子,矩阵和方程组病态程度的刻划, 设 精确，A有误差 ，得到的解为 ，即,(只要 A充分小，使得,常用条件数有：,cond 2(A),特别地，若 A 对称，则,3.4.2 矩阵的条件数,Def：设 存在，则称数 cond ( A )=| | A | 为矩阵 A 的 条件数，其中 是矩阵的算子范数。,1-条件数,-条件数,2-条件数,例：Hilbert 阵,注：现在用Matlab数学软件可以很方便求矩阵的条件数!,说明: 设线性方程组的系数矩阵是非奇异的, 如果cond(A)越大, 就称这个方程组越病态. 反之, cond(A) 越小, 就称这个方程组越良态.,若 A 对称正定，则,其中 分别为A的按模最大和最小的特征值。,例1：求矩阵 的条件数,例2: 设,求,
