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

数值计算方法NumericalComputationMethods信息科学与工程学院彭焱2第2章解线性方程组的直接方法线性方程组求解是一个基本的数学问题许多实际问题，都归结为求解线性方程组根据系数矩阵阶数的高低和含零元素的多少，线性方程组分为两类低阶稠密型~高阶稀疏型~求解方法：直接法（本章讨论）迭代法（第3章）3第2章解线性方程组的直接方法本章内容高斯消去法高斯列主元素消去法矩阵分解在解线性方程组中的应用杜利特尔分解向量与矩阵的范数误差分析直接法在不考虑舍入误差影响的条件下，经过有限次四则运算，求出线性方程组的准确解与前面讲的矛盾吗？不矛盾！因为实际计算时，舍入误差不可避免！引言5mn无解mn无穷多解求最优解（运筹学）m=nn阶方阵引言62.1高斯消去法以上线性方程组对应的矩阵表示：Ax=b其中，A为系数矩阵（非奇异矩阵），x为所求的未知向量，b为常数向量.......,...,...22112222212111212111nnnnnnnnnnbxaxaxabxaxaxabxaxaxa什么是非奇异矩阵？充要条件：A为可逆矩阵，其行列式不等于零。72.1高斯消去法用中学所学消去法，解线性方程组.132,435,31187321321321xxxxxxxxx消去第2，第3个方程中的，得如下等价方程：1x.71071076,713776733,311873232321xxxxxxx如果有n个方程呢？82.1高斯消去法消去第3个方程中的，得如下等价方程：2x.1112116,713776733,31187332321xxxxxx上三角线性方程组先后求出：回代再求：23x52x31x高斯消去法的定义---P20消元、回代92.1高斯消去法基于以上例子，讨论如何用消去法求解n阶线性方程组（特殊一般）增广矩阵进行初等变换上三角线性方程组第一次消元，选，消去第2~n个方程中的原理、步骤第2个方程减去第1个方程（左右均乘以）第3个方程减去第1个方程（左右均乘以）第n个方程减去第1个方程（左右均乘以）事实上，只是对增广矩阵（系数矩阵、常数向量）进行处理！11a1x经过第一次消元，第2~n行的第1列全部为0，其他系数也都变化，上标标记此变化思考：上标变化，是何意思？)1(11)1(21aa)1(11)1(31aa)1(11)1(1aan102.1高斯消去法继续推而广之第k次消元，选，消去第k+1~n个方程中的（i=k+1,k+2,…,n）原理、步骤第k+1个方程减去第k个方程（左右均乘以）……第n个方程减去第k个方程（左右均乘以）见P21（2.6）（2.7）经过n-1次消元后，得到P21（2.8）然后求出：根据公式，反复回代，求出方程组的解kkaikx)()()1(kkkkkkaa)()(kkkknkaanx112.1高斯消去法定理1若A为n阶非奇异矩阵，则可通过高斯消去法（及交换两行的初等变换），将一个线性方程组化为三角形线性方程组。高斯消去法正常工作的前提：引理主元的充要条件是：矩阵A的顺序主子式推论若n阶矩阵A的所有（各阶）顺序主子式，则),...,3,2,1(0)(nkakkk),...,3,2,1(0)(lkakkk),...,3,2,1(0lkDk)1,...,3,2,1(0nkDk),...,3,2(,1)(1)1(11nkDDaDakkkkk122.1高斯消去法定理2若n阶矩阵A的所有（各阶）顺序主子式，则可以通过高斯消去法将线性方程组化为三角形线性方程组。例2---P22高斯消去法的计算量（消元+回代）总的乘、除法运算次数：总的加、减法运算次数：),...,3,2,1(0nkDk33n33n13编程：高斯消去过程2.1高斯消去法15gauss.m2.1高斯消去法#includestdio.h#defineROW4voidtransferM(doublearray[][LEN]){introw1,row2,col;doublem;for(row1=0;row1ROW;row1++){for(row2=row1+1;row2ROW;row2++){m=array[row2][row1]/array[row1][row1];for(col=row1;colROW;col++){array[row2][col]-=array[row1][col]*m;}}}}16主元：主元为零，消元法不能顺利进行主元绝对值很小，不要作除数，否则导致舍入误差过大解决以上缺陷问题的方法消元过程中，每一步进行之前，尽可能选择绝对值较大的元素作为主元------高斯（列）主元消去法按列选主元，将最大值所在行与当前第k步对应的第k行对换（注意：行互换，不影响方程组的解）2.2高斯列主元消去法),...,3,2,1(0)(nkakkk1111maxiniaannnnniiniinbaaabaaabaaabaaa....................................................................................21212112221111211交换172.2高斯列主元消去法高斯列主元消去法的算法分析---P24注意：冲掉？表示什么？当时，说明什么？例4---P25“小主元”作除数，结果失真，解无效行标度化用该行最大的系数去除该行各元素找出真正的主元kikik存储空间，可以重新用新值写入行当前行即是最大值，作为主元，因此不用交换行，直接消元182.3矩阵分解在解线性方程组中的应用矩阵三角分解杜利特尔分解.13,3322,0221321321xxxxxxxx2100120121R1010120011L12100100012LRLLRLLARALL121111212)(或上三角192.3矩阵分解在解线性方程组中的应用方阵A可以分解成一个单位下三角矩阵与上三角矩阵的乘积杜利特尔/三角分解如果一个方阵A可以写成，则称A可三角分解（或LU分解、LR分解）称为A的一个三角分解或杜利特尔分解)(1211LLLLRA)R(11为单位上三角矩阵为对角矩阵、DLDRALRRLLRLLARALL121111212)(或LRALRAA为可逆矩阵时，R也是，其主对角线元都不为0，1DRR除主对角线元,其余元都是0的方阵称为对角矩阵202.3矩阵分解在解线性方程组中的应用定理3n阶方阵A有唯一的杜利特尔分解的充要条件是A的顺序主子式线性方程组：就等价于解两个三角形那么解线性方程组的杜利特尔分解若已知方阵bAxLRAA,)11(0nkDk)2.()1(,yRxbLy前推或追：当A可逆时，由(1)式可依次递推地解出赶：由(2)式回代，依次解出nyyy,...,,2111,...,,xxxnn定理3的作用？212.3矩阵分解在解线性方程组中的应用用杜利特尔分解来求线性方程组时，需要假设A的前n-1个顺序主子式不为零！例6---P29解题步骤：先要判断方阵的前n-1个顺序主子式不为零。然后用待定系数法，求L、R公式（2.15）---P29公式（2.16）---P30bAx).,...,1;1,...,3,2(/)(),,...,1,;,...,3,2(),,...,3,2(),...,2,1(1111111111nkinkrrlalnkkjnkrlarniralnjarkkkmmkimikikkmmjkmkjkjiijj).1,...,1(/)(,/),,...,3,2(,11111nirxryxryxniylbybyiinijjijiinnnnijjijii求第一行求R求L222.3矩阵分解在解线性方程组中的应用例7---P30三角矩阵分解法232.4向量与矩阵的范数向量与矩阵的范数度量向量和矩阵的“大小”为何要度量“大小”？研究线性方程组近似解的误差估计（度量误差）迭代法的收敛性在一维数轴上，实轴上任意一点x到原点的距离用|x|表示。而任意两点x1，x2之间距离用|x1-x2|表示。242.4向量与矩阵的范数而在二维平面上，平面上任意一点P(x,y)到原点的距离用表示。而平面上任意两点P1(x1,y1),P2(x2,y2)的距离用表示。推广到n维空间，则称为向量范数。||22OPyx22122121)()(||yyxxPP252.4向量与矩阵的范数向量与上的向量范数。为则称，有，对任意，有和任意对任意常数当且仅当，对任意满足条件，若记为数与之对应，按照一定的规则有一实如果向量定义组成的实线性空间。维列向量表示所有实的用nnnnTnnTnnRyxyxRyRxxxRxRxxxRxxxRxxxxxnR;)3(;)2(;)0,...,0,0(0;0)1(:,),...,,(21非负性齐次性三角不等式相容性262.4向量与矩阵的范数几种常用的向量范数pnipipniiniiiniTnxxxxxxxxxxxx112112211121)||(||||)||(||||||||||||max||||),...,,(设向量272.4向量与矩阵的范数计算向量不同类别的范数例13范数。范数，范数，的计算向量-2-1-)1,2,3(TxpnipipniiniiiniTnxxxxxxxxxxxx112112211121)||(||||)||(||||||||||||max||||),...,,(设向量282.4向量与矩阵的范数矩阵范数的概念定义：.,,max1AAAxRRAnRxnnnnn矩阵范数，记为）的（从属于向量范数的为称向量范数上的为阶实矩阵，设表示全体用也要满足向量范数的3个条件还要满足相容性条件：一个矩阵，可看作多个向量的集合---行、列向量集合;)4(xAAx292.4向量与矩阵的范数常用的三种从属的矩阵范数)()()(||||)(||max||||||||||max211111max是矩阵的特征值行和范数（列和范数）AAAAAaAaATTnjijniniijnj是矩阵的谱半径其中：)(AATAAT0:max)(AAEAATT302.4向量与矩阵的范数例14---P41312.4向量与矩阵的范数定理5---P41矩阵的范数与谱半径存在某种关系。计科5.7至此332.5误差分析方程组的病态线性方程组的系数，往往含有误差。此误差（扰动）对方程解的影响如何？P41例15列举了2个线性方程组，只有右端微小的差别，但它们的解却是完全不同的。---病态方程组需要定量“病态”，以了解其影响程度342.5误差分析针对线性方程组：Ax=b来讨论右端项b的扰动对解的影响)()(bbxxAbxAbAbAx11AbAAxx又：bbAAxx1352.5误差分析针对线性方程组：Ax=b来讨论系数矩阵A的扰动对解的影响bxxAA))((0)(xxAxA)()(11xxAAxxAAx11AAA足够小，那么假设：AA