计算方法第六章 解线性方程组的直接法ppt课件.ppt

AX = b,（3.1）,第三章 解线性方程组的直接法,1 高斯消去法,1三角形方程组的解法,（3.2）,（3.3）,首先将A化为上三角阵 ，再回代求解 。,(一) 高斯消去法的求解过程,可分为两个阶段: 首先,把原方程组化为上三角形方程组,称之为 “消元”过程; 然后,用逆次序逐一求出三角方程组(原方程组的等价方程组)的解,并称之为“回代”过程.,下面分别写出“消元”和“回代” 两个过程的计算步骤.,记,Step 1：设 ，计算因子,将增广矩阵第 i 行 mi1 第1行，得到,其中,Step k：设 ，计算因子,共进行 ？ 步,n 1,且计算,回代,若A的所有顺序主子式 均不为0，则高斯消元无需换行即可进行到底，得到惟一解。,利用高斯消元法求解方程组:,解：,1.2 高斯消元法_例题分析,利用,得,利用,得,利用,得,显然，方程组(4)与(1)是等价的，其系数矩阵为上三角状的，易于求解.称以上过程为高斯消去法的消去过程.通过方程组(4)的回代求解，可以得到准确解为,这一过程为高斯消去法的回代过程。,消元公式,回代公式,1.3 高斯消元法_选主元消去法,Gauss消元法第 k 次消元是用第 k 个方程,主元素及其选取问题,来消去第 k+1,n 个方程中的 xk , 条件是 .,是实现第 k 次消元的关键元素，称为第k次消去的主元.,Gauss消元法存在的问题是：,例：单精度解方程组,用Gaussian Elimination计算：,8个,用小主元10-9作除数，致使其它元素的数量级大大增加，舍入误差的扩散将准确解淹没了。,1.3 高斯消元法_选主元消去法,全主元消去法,每一步选绝对值最大的元素为主元素，保证 。,Step k: 选取, If ik k then 交换第 k 行与第 ik 行; If jk k then 交换第 k 列与第 jk 列;, 消元,注：列交换改变了 xi 的顺序，须记录交换次序，解完后再换回来。,算法：1. 消元过程，对 (1) 选主元，找 使得 (2) 若 ，则停止，推出 (3) 若 ，则换行， (4) 消元，对 有,考虑在整个矩阵范围选主元，这就是所谓的全主元消去法，此时要注意的是，在做列的变换时，要同时记录当前变量的次序，以免自变量的含义不清。,有,回代过程：(1)若 ，则停止(2)对,例：,注：列主元法没有全主元法稳定。,例：,列主元消去法,在计算机上实现全主元素消去法意味着进行数的比较操作，选全主元素法需要相当多的计算时间，因此常采用局部选主元素的方法.省去换列的步骤，每次仅选一列中最大的元。,例题分析（Guass全选主元法),精确解为：x1=1.9273, x2=-0.698496, x3=0.9004233,例题分析（Guass列选主元法),精确解为：x1=1.9273, x2=-0.698496, x3=0.9004233,列主元消去法计算步骤：,1、输入矩阵阶数n，增广矩阵 A(n,n+1);,2、对于,(1) 按列选主元：选取 l 使,(2) 如果 ，交换 A(n,n+1) 的第k行与底l 行元素,(3) 消元计算 ：,3、回代计算,4无回代过程的主元消去法,算法：,第一步：选主元，在第一列中选绝对值最大的元素，设第k行为主元行， 将主元行换至第一行，将第一个方程中x1的系数变为1，并从 其余n 1个方程中消去x1。,第二步：在第二列后n 1个元素中选主元，将第二个方程中x2的 系数变为1，并从其它n 1个方程中消去x2。,第k步：在第k列后n k个元素中选主元，换行，将第k个方程xk的系数 变为1，从其它n - 1个方程中消去变量xk，,消元公式为：,对k = 1, 2, , 按上述步骤进行到第n步后，方程组变为：,即为所求的解,5无回代消去法的应用,（1）解线性方程组系,设要解的线性方程组系为：,AX = b1, AX = b2, AX = bm,上述方程组系可以写为,AX = B = (b1, , bm),因此X = A-1B 即为线性方程组系的解。,在计算机上只需要增加几组右端常数项的存贮单元，其结构和解一个方程组时一样。,行,系数,右端,（2）求逆矩阵,设A = (aij)nn是非奇矩阵，A 0，且令,由于 AA-1 = AX = I,因此，求A-1的问题相当于解下列线性方程组,相当于（1）中m = n, B = I 的情形。,（3）求行列式的值,用高斯消去法将 A化成,2 解三对角方程组的追赶法, 高斯消元法的矩阵形式:,Step 1:,3 矩阵的三角分解及其在解方程组中的应用,记,于是,Step n 1:,其中,由上述讨论可知，高斯消去法实质上产生了一个将系数矩阵A分解为上三角阵与下三角阵相乘的因式分解。,若A的所有顺序主子式 均不为0，则 A 的 LU 分解唯一（其中 L 为单位下三角阵）。,设有方程组AX=b,并设A=LU,于是 AX=LUX=b,令UX=Y, 则 LY=b.,于是求解AX=b的问题等价于求解两个方程组UX=Y和LY=b,（1）利用顺推过程解LY=b, 其计算公式为:,（2）利用回代过程解UX=Y , 其计算公式为:,定理1：（矩阵的三角分解）设A为n n实矩阵，如果解AX = b用高斯消去法能够完成（限制不进行行的交换，即 ），则矩阵A可分解为单位下三角矩阵L与上三角知阵U的乘积。A = LU且这种分解是唯一的。,定理2：约化主元素（ , i = 1, 2, , k） 充要条件是矩阵A的顺序主子式,矩阵的三角分解,通过比较法直接导出L 和 U 的计算公式。,思路,（1）对i=1,2,n,（2）计算 U 的第 r 行, L 的第 r 列元素,对r =2,3,n,直接三角分解法解AX = b的计算公式,对于r = 2, 3, , n计算,（2）计算U的第r行元素,（3）计算L的第r 列元素 (r n),(1),(4),(5),4 平方根法,1矩阵的LDR分解,定理3：如果n阶矩阵A的所有顺序主子式均不等于零，则矩阵A存在唯一的分解式A = LDR其中L和R分别是n阶单位下三角阵和单位上三角阵，D是n阶对角元素的不为零的对角阵，上述分解也称为A的LDR分解。,2平方根法,如果A为对称正定矩阵，则存在一个实的非奇异下三角矩阵，使A=LLT ，且当限定的对角元素为正时，这种分解是唯一的。,定理4：（对称正定矩阵的三角分解）,将对称 正定阵 A 做 LU 分解,即,则 仍是下三角阵,注： 对于对称正定阵 A ，从 可知对任意k i 有 。即 L 的元素不会增大，误差可控，不需选主元。,用平方根法解线性代数方程组的算法,（1）对矩阵A进行Cholesky分解，即A=LLT，由矩阵乘法：,对于 i = 1, 2, n 计算,（2）求解下三角形方程组,（3）求解LTX = y,3改进平方根法,其中,改进平方根法解对称正定方程组的算法,令LTX = y，先解下三角形方程组LDY = b得,解上三角形方程组LTX = Y得,5 向量和矩阵的范数,1向量的范数,定义1：设X R n， 表示定义在Rn上的一个实值函数，称之为X的范数，它具有下列性质：,（3）三角不等式：即对任意两个向量X、Y R n，恒有,(1) 非负性：即对一切X R n，X 0, 0,(2) 齐次性：即对任何实数a R，X R n，,-(1),-(2),-(3),-(4),常用的向量x的范数有,下述范数的几何意义是:,例3 求下列向量的各种常用范数,例3 求下列向量的各种常用范数,解:,1*499/4*4=9,范数等价的定义:,设A 和B 是R上任意两种范数，若存在常数 C1、C2 0 使得,则称 和 等价。,显然,并且由于,注意:一般有向量的等价关系,对常用范数，容易验证下列不等式：,定义2：设给定Rn中的向量序列 ，即,其中,若对任何i (i = 1, 2, n )都有,则向量,称为向量序列 的极限，或者说向量序列 依坐标收敛于向量，记为,定理2：向量序列Xk依坐标收敛于X*的充要条件是,向量序列依范数收敛与依坐标收敛是等价的。,2矩阵的范数,定义3：设A为n 阶方阵，Rn中已定义了向量范数 ， 则称 为矩阵A的范数或模， 记为 。,矩阵范数的基本性质：,（1）当A = 0时， 0，当A 0时， 0,（2）对任意实数和任意A，有,（3）对任意两个n阶矩阵A、B有,（4）对任意向量XRn，和任意矩阵A，有,（5）对任意两个n阶矩阵A、B，有,常用的矩阵范数,-(5),-(6),-(7), 向量| |2的推广 Frobenius 范数,-(8),例5,求矩阵A的各种常用范数,解:,由于,例5,求矩阵A的各种常用范数,解(续):,由于,特征方程为,例5,求矩阵A的各种常用范数,解(续):,由于,特征方程为,容易计算,对矩阵元素的变化比较敏感,较少使用,使用最广泛,性质较好,使用最广泛,计算较复杂,定义4,-(9),显然,设A为n阶方阵,则对任意算子范数 | | 有,证明：,由算子范数的相容性，得到,将任意一个特征根 所对应的特征向量 代入,定理3,若A对称，则有,证明：,若 是 A 的一个特征根，则2 必是 A2 的特征根。,又对称矩阵的特征根为实数，即 2(A) 为非负实数，故得证。,对某个 A 的特征根 成立,定理4,定理5.,证明:略,返回,这里只证性质（7）。假定 不可逆，则线性齐次方程组 有非零解 ，从而,矛盾。这说明 可逆， 存在。于是,从而知,证毕,求解 时，A 和 的误差对解 有何影响？, 设 A 精确， 有误差 ，得到的解为 ，即,绝对误差放大因子,又,相对误差放大因子,6 线性方程组的性态和解的误差分析,2 Error Analysis for ., 设 精确，A有误差 ，得到的解为 ，即,Wait a minute Who said that ( I + A1 A ) is invertible?,(只要 A充分小，使得,大,定义5：设A 为n 阶非奇矩阵，称数 为矩阵A的条件数，,条件数的性质：,）cond ( A )1,）cond ( kA )= cond ( A ) k 为非零常数,）若 ， 则,记为cond( A )。,例题,已知, 求A的条件数.,解：由,说明由A构成的系数矩阵方程组是“病态”的 。,392061.,cond (H2) =,27,cond (H3) ,748,cond (H6) =,2.9 106,cond (Hn) as n ,注：一般判断矩阵是否病态，并不计算A1，而由经验得出。 行列式很大或很小（如某些行、列近似相关）； 元素间相差大数量级，且无规则； 主元消去过程中出现小主元； 特征值相差大数量级。, 近似解的误差估计及改善：,设 的近似解为 ，则一般有,cond (A), 改善方法：,Step 1:近似解,Step 2:,Step 3:,Step 4:,若 可被精确解出，则有 就是精确解了。,经验表明：若 A 不是非常病态（例如： ），则如此迭代可达到机器精度；但若 A 病态，则此算法也不能改进。,