第2章-解线性方程组的直接方法

数值计算方法,NumericalComputationMethods,信息科学与工程学院彭焱,2,第2章解线性方程组的直接方法,线性方程组求解是一个基本的数学问题许多实际问题，都归结为求解线性方程组根据系数矩阵阶数的高低和含零元素的多少，线性方程组分为两类,低阶稠密型,高阶稀疏型,求解方法：,直接法（本章讨论）,迭代法（第3章）,3,第2章解线性方程组的直接方法,本章内容高斯消去法高斯列主元素消去法矩阵分解在解线性方程组中的应用杜利特尔分解向量与矩阵的范数误差分析,直接法在不考虑舍入误差影响的条件下，经过有限次四则运算，求出线性方程组的准确解与前面讲的矛盾吗？,不矛盾！因为实际计算时，舍入误差不可避免！,引言,5,mn无解mn无穷多解求最优解（运筹学）m=nn阶方阵,引言,6,2.1高斯消去法,以上线性方程组对应的矩阵表示：Ax=b其中，A为系数矩阵（非奇异矩阵），x为所求的未知向量，b为常数向量,什么是非奇异矩阵？,充要条件：A为可逆矩阵，其行列式不等于零。,7,2.1高斯消去法,用中学所学消去法，解线性方程组,消去第2，第3个方程中的，得如下等价方程：,如果有n个方程呢？,8,2.1高斯消去法,消去第3个方程中的，得如下等价方程：,上三角线性方程组先后求出：回代再求：,高斯消去法的定义-P20消元、回代,9,2.1高斯消去法,基于以上例子，讨论如何用消去法求解n阶线性方程组（特殊一般）增广矩阵进行初等变换上三角线性方程组第一次消元，选，消去第2n个方程中的原理、步骤第2个方程减去第1个方程（左右均乘以）第3个方程减去第1个方程（左右均乘以）第n个方程减去第1个方程（左右均乘以）事实上，只是对增广矩阵（系数矩阵、常数向量）进行处理！,经过第一次消元，第2n行的第1列全部为0，其他系数也都变化，上标标记此变化,思考：上标变化，是何意思？,10,2.1高斯消去法,继续推而广之第k次消元，选，消去第k+1n个方程中的（i=k+1,k+2,n）原理、步骤第k+1个方程减去第k个方程（左右均乘以）第n个方程减去第k个方程（左右均乘以）见P21（2.6）（2.7）经过n-1次消元后，得到P21（2.8）然后求出：根据公式，反复回代，求出方程组的解,11,2.1高斯消去法,定理1若A为n阶非奇异矩阵，则可通过高斯消去法（及交换两行的初等变换），将一个线性方程组化为三角形线性方程组。高斯消去法正常工作的前提：引理主元的充要条件是：矩阵A的顺序主子式推论若n阶矩阵A的所有（各阶）顺序主子式，则,12,2.1高斯消去法,定理2若n阶矩阵A的所有（各阶）顺序主子式，则可以通过高斯消去法将线性方程组化为三角形线性方程组。例2-P22高斯消去法的计算量（消元+回代）总的乘、除法运算次数：总的加、减法运算次数：,13,编程：高斯消去过程,2.1高斯消去法,15,gauss.m,2.1高斯消去法,#include#defineROW4voidtransferM(doublearrayLEN)introw1,row2,col;doublem;for(row1=0;row1ROW;row1+)for(row2=row1+1;row2ROW;row2+)m=arrayrow2row1/arrayrow1row1;for(col=row1;colROW;col+)arrayrow2col-=arrayrow1col*m;,16,主元：主元为零，消元法不能顺利进行主元绝对值很小，不要作除数，否则导致舍入误差过大解决以上缺陷问题的方法消元过程中，每一步进行之前，尽可能选择绝对值较大的元素作为主元-高斯（列）主元消去法按列选主元，将最大值所在行与当前第k步对应的第k行对换（注意：行互换，不影响方程组的解）,2.2高斯列主元消去法,17,2.2高斯列主元消去法,高斯列主元消去法的算法分析-P24注意：冲掉？表示什么？当时，说明什么？例4-P25“小主元”作除数，结果失真，解无效行标度化用该行最大的系数去除该行各元素找出真正的主元,存储空间，可以重新用新值写入,行,当前行即是最大值，作为主元，因此不用交换行，直接消元,18,2.3矩阵分解在解线性方程组中的应用,矩阵三角分解杜利特尔分解,上三角,19,2.3矩阵分解在解线性方程组中的应用,方阵A可以分解成一个单位下三角矩阵与上三角矩阵的乘积杜利特尔/三角分解如果一个方阵A可以写成，则称A可三角分解（或LU分解、LR分解）称为A的一个三角分解或杜利特尔分解,A为可逆矩阵时，R也是，其主对角线元都不为0，,除主对角线元,其余元都是0的方阵称为对角矩阵,20,2.3矩阵分解在解线性方程组中的应用,定理3n阶方阵A有唯一的杜利特尔分解的充要条件是A的顺序主子式,前推或追：当A可逆时，由(1)式可依次递推地解出赶：由(2)式回代，依次解出,定理3的作用？,21,2.3矩阵分解在解线性方程组中的应用,用杜利特尔分解来求线性方程组时，需要假设A的前n-1个顺序主子式不为零！例6-P29解题步骤：先要判断方阵的前n-1个顺序主子式不为零。然后用待定系数法，求L、R公式（2.15）-P29公式（2.16）-P30,求第一行,求R,求L,22,2.3矩阵分解在解线性方程组中的应用,例7-P30三角矩阵分解法,23,2.4向量与矩阵的范数,向量与矩阵的范数度量向量和矩阵的“大小”为何要度量“大小”？研究线性方程组近似解的误差估计（度量误差）迭代法的收敛性在一维数轴上，实轴上任意一点x到原点的距离用|x|表示。而任意两点x1，x2之间距离用|x1-x2|表示。,24,2.4向量与矩阵的范数,而在二维平面上，平面上任意一点P(x,y)到原点的距离用表示。而平面上任意两点P1(x1,y1),P2(x2,y2)的距离用表示。推广到n维空间，则称为向量范数。,25,2.4向量与矩阵的范数,向量与,非负性,齐次性,三角不等式,相容性,26,2.4向量与矩阵的范数,几种常用的向量范数,27,2.4向量与矩阵的范数,计算向量不同类别的范数例13,28,2.4向量与矩阵的范数,矩阵范数的概念定义：,也要满足向量范数的3个条件还要满足相容性条件：一个矩阵，可看作多个向量的集合-行、列向量集合,29,2.4向量与矩阵的范数,常用的三种从属的矩阵范数,是矩阵的谱半径其中：,30,2.4向量与矩阵的范数,例14-P41,31,2.4向量与矩阵的范数,定理5-P41矩阵的范数与谱半径存在某种关系。,计科5.7至此,33,2.5误差分析,方程组的病态线性方程组的系数，往往含有误差。此误差（扰动）对方程解的影响如何？P41例15列举了2个线性方程组，只有右端微小的差别，但它们的解却是完全不同的。-病态方程组需要定量“病态”，以了解其影响程度,34,2.5误差分析,针对线性方程组：Ax=b来讨论右端项b的扰动对解的影响,35,2.5误差分析,针对线性方程组：Ax=b来讨论系数矩阵A的扰动对解的影响,36,2.5误差分析,结论两种扰动情况下，对解的影响与cond(A)条件数的大小有关。cond(A)定量描述了方程组的“病态”程度矩阵的cond(A)与所用的范数有关,37,2.5误差分析,利用cond条件数来判断方程组是不是“病态”的。P43利用条件数，对（2.29）方程组（如下）的进一步分析。为何它是病态的？其条件数太大,38,2.5误差分析,精度分析将近似解代入原方程组中，求出余量r，其中r很小，就认为近似解够精确。余量即扰动量。,